Основы теории двойственности.

Правила построения задачи, двойственной к данной.

1.) Если целевая функция одной задачи в паре стремится к минимуму, то целевая функция другой задачи стремится к максимуму.

2) Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой.

3) Количество переменных в двойственной задаче равно числу ограничений в исходной.

4)Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.

5) Задача на максимум – все ограничения с . В задаче на минимум – все ограничения с .

6) Если в системе ограничений задачи k-е ограничение является равенством, то на k-ю переменную в двойственной задаче не накладывается условие неотрицательности.

Первая теорема двойственности:

Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение. Причём значения целевых функций этих задач на своих оптимальных решениях совпадают.

Оптимальное решение одной из задач можно найти из решения симплекс методом другой задачи, прибавив к оценкам разложений по базису оптимального решения векторов, входящих в начальный базис начального решения соответствующие коэффициенты целевой функции.

Если одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений.

Вторая теорема двойственности:

Допустимые решения и являются оптимальными решениями пары двойственных задач тогда и только тогда, когда и

Симплекс метод.

Симплекс метод – это метод целенаправленного перебора опорных решений задачи линейного программирования (ЗЛП).

Основания для применения симплекс метода:

1) ОДР ЗЛП – выпуклое множество с конечным числом угловых точек;

2) оптимальное решение ЗЛП – это одна из угловых точек ОДР;

3) угловые точки ОДР – базисные решения (опорные планы) системы ограничений.

Базисные решения – допустимые решения вида , содержащие r базисных и n-r свободных переменных.

Все свободные переменные равны нулю, а базисные переменные равны соответствующим свободным членам в преобразованной (разрешённой относительно базисных переменных) системе ограничений.

Чтобы решения системы уравнений ограничений были допустимыми, должно выполняться

условие неотрицательности свободных членов:

Не нашли, что искали? Воспользуйтесь поиском: