Двойственность в задачах линейной оптимизации

Двойственная задача линейного программирования

Каждой задаче линейного программирования.

со смешанными ограничениями вида.

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

при ограничениях.

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

если прямая задача является задачей максимизации, то двойственная — минимизации и наоборот;

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

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

матрица ограничений двойственной задачи получается транспонированием матрицы ограничений прямой задачи;

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

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

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

Отсюда имеем оптимальный план двойственной задачи.

Если прямая задача решается на максимум:

Если прямая задача решается на минимум:

Рассмотрим пример.

Приведем задачу к каноническому виду.

Таблица I.

№ 1.

Здесь в условиях наших обозначений: (количество истинных переменных) и (количество дополнительных переменных = количеству ограничений задачи):

Заметим так же, что задача решается на максимум.

Таблица II.

№ 2.
			— 2.

Таблица III.

№ 3.
			;
			;

Оптимальный план двойственной задачи, судя по вектору, будет иметь вид.