IV. ДВОЙСТВЕННЫЕ ЗАДАЧИ

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

I. При построении двойственной задачи следует проверить, выполняются ли для исходной задачи такие требования:

1) во всех ограничениях свободные члены расположены в правой части равенства (неравенства), а члены с неизвестными – в левой;

2) все ограничения неравенств исходной задачи должны быть записаны так, чтобы знаки неравенств в них были направлены в одну и ту же сторону, для этого достаточно отдельные неравенства умножить на (-1);

3) общий знак неравенства системы ограничений связывается с оптимизацией формы таким образом: если max, то ; если min, то .

 

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

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

2) каждой неизвестной x_j исходной задачи соответствует ограничение двойственной. Эти ограничения строят таким образом: умножают коэффициенты a_ij, которые стоят при x_j, на соответствующие двойственные неизвестные , результаты умножения добавляем и ставим в левую часть ограничений, а в правую – коэффициент при x_j в оптимизирующей форме c_j;

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

 

III. Для оптимизированной форме двойственной задачи должны удовлетворяться условия:

1) форма z^* двойственной задачи оптимизируется в противоположном значении (если z(max), то z^*(min), и – наоборот);

2) коэффициентами при двойственных неизвестных в форме z^* являются соответствующие свободные члены системы ограничений исходной задачи. Свободный член c₀ формы z переносится без изменений в форму z^*.

 

Пример 12. Построить двойственную задачу к следующей задачи линейного программирования:

Решение. Прежде чем построить двойственную задачу к исходной, надо заменить знак второго ограничения на (для этого умножим его на (-1)) и в первом неравенстве сгруппируем члены:

Согласно ограничениям исходной задачи возьмем двойственные неизвестные y₁, y₂, y₃ и строим двойственную задачу:

Пример 13. Построить двойственную задачу к задаче линейного программирования с ограничениями в виде равенств.

Решение. Задача линейного программирования с ограничениями в виде равенств имеет вид:

 

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

 

Методику нахождения оптимального решения двойственной задачи, если исходная задача решена симплекс-методом, рассмотрим на таком примере:

(max) z₀=3x₁+2x₂;

Двойственная задача

Решение исходной задачи симплекс-методом приведено в таблицах 1 – 3. Оптимальный план двойственной задачи находим на основании строки последней итерации (таблица 3). При этом двойственная неизвестная y₁ соответствует базисной неизвестной первого ограничения x₃, неизвестная y₂ – второго ограничения x₄. Учитывая это, получаем такой оптимальный план двойственной задачи:

.