Правила построения задачи, двойственной к данной.
1.) Если целевая функция одной задачи в паре стремится к минимуму, то целевая функция другой задачи стремится к максимуму.
2) Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой.
3) Количество переменных в двойственной задаче равно числу ограничений в исходной.
4)Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.
5) Задача на максимум – все ограничения с . В задаче на минимум – все ограничения с .
6) Если в системе ограничений задачи k-е ограничение является равенством, то на k-ю переменную в двойственной задаче не накладывается условие неотрицательности.
Первая теорема двойственности:
Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение. Причём значения целевых функций этих задач на своих оптимальных решениях совпадают.
Оптимальное решение одной из задач можно найти из решения симплекс методом другой задачи, прибавив к оценкам разложений по базису оптимального решения векторов, входящих в начальный базис начального решения соответствующие коэффициенты целевой функции.
|
|
Если одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений.
Вторая теорема двойственности:
Допустимые решения и являются оптимальными решениями пары двойственных задач тогда и только тогда, когда и
4. Симплекс метод.
Симплекс метод – это метод целенаправленного перебора опорных решений задачи линейного программирования (ЗЛП).
Основания для применения симплекс метода:
1) ОДР ЗЛП – выпуклое множество с конечным числом угловых точек;
2) оптимальное решение ЗЛП – это одна из угловых точек ОДР;
3) угловые точки ОДР – базисные решения (опорные планы) системы ограничений.
Базисные решения – допустимые решения вида , содержащие r базисных и n-r свободных переменных.
Все свободные переменные равны нулю, а базисные переменные равны соответствующим свободным членам в преобразованной (разрешённой относительно базисных переменных) системе ограничений.
Чтобы решения системы уравнений ограничений были допустимыми, должно выполняться
условие неотрицательности свободных членов: