Общие правила составления двойственных задач
Правило 1. Во всех ограничениях исходной задачи свободные члены должны находиться в правой части, а члены с неизвестными – в левой.
Правило 2. Ограничения-неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.
Правило 3. Если знаки неравенств в ограничениях исходной задачи « », то целевая функция , а если « », то .
Правило 4. Каждому ограничению исходной задачи соответствует неизвестное в двойственной задаче, при этом неизвестное, отвечающее ограничению-неравенству, должно удовлетворять условию неотрицательности, а неизвестное, отвечающее ограничению-равенству, может быть любого знака.
Правило 5. Целевая функция двойственной задачи имеет вид
,
где – свободные члены в ограничениях исходной задачи.
Правило 6. Целевая функция должна оптимизироваться противоположным по сравнению с образом.
Правило 7. Каждому неизвестному хj , j = 1, 2, …, n исходной задачи соответствует ограничение в двойственной задаче. Совокупность этих n ограничений (вместе с условиями неотрицательности неизвестных yi , соответствующих ограничениям-неравенствам исходной задачи) образует систему ограничений двойственной задачи. Все ограничения двойственной задачи имеют вид неравенств, свободные члены которых находятся в правых частях, а члены с неизвестными y1, y2, …, – в левых.
Все знаки неравенств имеют вид « », если , и « », то .
Одновременное решение прямой
И двойственной задач
Одновременное решение прямой и двойственной задач основано на использовании теорем двойственности. Теоремы двойственности позволяют установить взаимосвязь между оптимальными решениями пары двойственных задач. Решив одну из пары двойственных задач, можно или найти оптимальное решение другой задачи, не решая ее, или установить его отсутствие. Возможны следующие случаи:
- обе задачи из пары двойственных имеют оптимальные решения;
- одна из задач не имеет решения в виду неограниченности целевой функции, а другая не имеет решения ввиду несовместности системы ограничений.
Теорема 6.2.1 (1-я теорема двойственности). Если одна из задач взаимно двойственной пары разрешима, то разрешима и другая задача, при этом оптимальные значения целевых функций совпадают. Если целевая функция одной из задач не ограничена (сверху – для задачи максимизации, снизу – для задачи минимизации), то множество допустимых планов другой задачи пусто.
Из этой теоремы вытекает следующее
Следствие. Для того, чтобы допустимые решения и двойственной пары задач были оптимальны, необходимо и достаточно, чтобы значения целевых функций на этих планах совпадали: .
Теорема 6.2.2 (2-я теорема двойственности). Пусть имеется симметричная пара двойственных задач
, , (6.2.1)
, ; , .
Для того чтобы допустимые решения , являлись оптимальными решениями пары двойственных задач, необходимо и достаточно, чтобы выполнялись следующие равенства:
, ; (6.2.2)
, . (6.2.3)
Иначе, если при подстановке оптимального решения в систему ограничений i-е ограничение исходной задачи выполняется как строгое неравенство, то i-я координата оптимального решения двойственной задачи равна нулю, и, наоборот, если i-я координата оптимального решения двойственной задачи отлична от нуля, то i-е ограничение исходной задачи удовлетворяется оптимальным решением как равенство.
Пример 6.2. Для данной задачи составить двойственную, решить ее графическим методом и, используя вторую теорему двойственности, найти решение исходной задачи:
, .
Решение. Составим двойственную задачу
Решим эту задачу графическим методом. На рис. 6 изображены область допустимых решений задачи, нормаль линий уровня, линии уровня и оптимальное решение задачи .
| , ; , ; ; |
Рис. 6
.
Подставим оптимальное решение в систему ограничений. Получим, что ограничения (1) и (4) выполняются как строгие неравенства:
Согласно второй теореме двойственности соответствующие координаты оптимального решения двойственной, т.е. исходной задачи, равны нулю: . Учитывая это, из системы ограничений исходной задачи получим
__________________
;
=7, =1; .
Ответ: 102 при .
Транспортная задача