4.2. Общие правила составления двойственных задач

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

Привило 1. Во всех ограничениях исходной задачи свободные члены должны находиться в правой части, а члены с неизвестными – в левой.

Правило 2. Ограничения-неравенства должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.

Правило 3. Если знаки неравенств в ограничениях исходной задачи «», то целевая функция Z(X) должна максимизироваться, а если «» - минимизироваться.

Правило 4. Каждому ограничению исходной задачи соответствует неизвестное в двойственной задаче; при этом неизвестное, отвечающее ограничению-неравенству, должно удовлетворять условию неотрицательности, а неизвестное, отвечающее ограничению-равенству, может быть любого знака.

Правило 5. Целевая функция двойственной задачи имеет вид

F(Y) = b₁y₁ + b₂y₂+…+b_my_m,

b₁,b₂,...,b_m – свободные члены в ограничениях исходной задачи, при этом b_i – свободный член именно того ограничения, которому соответствует переменная y_i ; у₁,у₂,...,у_т – неизвестные в двойственной задаче.

Правило 6. Целевая функция F(Y) двойственной задачи должна оптимизироваться противоположным по сравнению с Z(X) образом, т.е. если

Z(X)  max, то F(Y)  min, если Z(X)  min, то F(Y)  maх.

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

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

Пример 1. Составить задачу, двойственную к данной

Z(X) = -x₁ +2x₂  max,

□1. Так как исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду «», для чего обе части первого и четвертого неравенств умножим на (-1). Получим

Вводим четыре оценки у₁,у₂,у₃,у₄ по числу ограничений.

2. Запишем матрицу системы ограничений А и А^Т:

А = А^Т =

3. Записываем целевую функцию

F (Y) = -y₁ + 24y₂ + 3y₃ – 5y₄  min.

4. Умножаем матрицу А^Т на столбец новых переменных, получим

Таким образом, нужно минимизировать целевую функцию

F(Y) = -y₁ + 24y₂ + 3y₃ – 5y₄  min,

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

Теоремы двойственности позволяют установить взаимосвязь между оптимальными решениями пары двойственных задач. Решив одну из них, можно или найти оптимальное решение другой задачи, не решая ее, или установить его отсутствие. Возможны следующие случаи: 1) обе задачи из пары двойственных задач имеют оптимальные решения; 2) одна из задач не имеет решения ввиду неограниченности целевой функции, а другая – ввиду несовместности системы ограничений.

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

Z^*(X) = F^*(Y)