![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Постановка задачи. В общем виде задача линейного программирования записывается следующим образом:
В общем виде задача линейного программирования записывается следующим образом: Дано: 1. Множество переменных (неизвестных) задачи
2. Множество допустимых решений задачи Q (система условий задачи), задаваемое в виде системы линейных ограничений a11· x1 + … + a1j· xj +…+ a1n· xn = b1 ………………………………….. ai1· x1 + … + aij· xj +… + ain· xn = bi …………………………………..
ak+1 1· x1 + … + a k+1 j· xj+…+ a k+1 n· xn≤ b k+1 ………………………………….. am1· x1 + … + amj· xj+ … + amn· xn≤ bm xj≥ 0 для
3. Функционал задачи (линейная форма задачи) F(x)=f1· x1 + … + fj· xj+… + fn· xn F(x)=f· x, где f=(f1, f2, … fj, …, fn) – вектор строка коэффициентов функционала. 4. Матрица условий задачи 5. Вектор столбец правой части ограничений 6. Матричная форма задачи оптимизации
![]() Если ищется максимум функционала Найти: Если ищется минимум функционала Найти: Область Q, заданная системой линейных уравнений и неравенств, представляет собой выпуклый многогранник в n -мерном пространстве, а экстремум линейной функции Канонической формой модели линейного программирования является модель, в которой система ограничений
Задача линейного программирования, записанная в общем виде, легко сводится к канонической форме путем ввода дополнительных неотрицательных переменных
В функционал задачи переменные Во всех случаях, когда задача линейного программирования разрешима, ее решение сводится к упорядоченному перебору вершин n -мерного многогранника.
|