44. Двойственные задачи. Основные понятия.

Симметричные двойственные задачи.

Парой симметричных двойственных задач называются две, тесно связанные между собой задачи ЛП, которые удобно записать схематически в виде системы (1). Задача ЛП, в которой целевая функция максимизируется, а все неравенства «типа », называется стандартной задачей максимизации; если целевая функция минимизируется, а все неравенства «типа » - стандартной задачей минимизации. Пара симметричных двойственных задач состоит из стандартной задачи максимизации и стандартной задачи минимизации, причем эти задачи обладают рядом особенностей, которые хорошо видны в схеме (1) и позволяют сформулировать правила составления двойственных задач.

Задача 1 Max При условиях:

Задача 2 Min При условиях: (1)

Правила составления пары симметричных двойственных задач.

1. Одна из задач является стандартной задачей максимизации, другая – стандартной задачей минимизации.

2. Количество неизвестных в одной из задач равно количеству основных ограничений в другой задаче.

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

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

5. Строки, стоящие в схеме (1) в одной строке напротив друг друга, называются парой сопряженных неравенств.

Если решить одну из двойственных задач, то на основании теорем двойственности можно сделать вывод о существовании или отсутствии решения другой задачи.

Проверка правильности найденных оптимальных планов осуществляется на основании критериев оптимальности планов двойственности задач.

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

Второй критерий. Для того, чтобы план одной из двойственных задач был оптимальным, необходимо и достаточно, чтобы существовал план другой задачи, такой что в каждой паре сопряженных неравенств строгому неравенству соответствовало бы равенство, то есть хотя бы одно из пары сопряженных неравенств должно выполняться как равенство.

Для проверки критериев необходимо найденные оптимальные планы подставить в схему (1).

Несимметричные двойственные задачи.

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

На схеме (2) приведен пример несимметричной двойственной задачи.

Задача 1 Max При условиях:

Задача 2 Min При условиях: (2) - любого знака - любого знака

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