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

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

максимизировать

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

минимизировать

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

Условно назовем первую задачу исходной, а вторую двойственной (по отношению к первой). Рассмотрим это на примере.

Исходная задача:

максимизировать

Z= 6X₁+5X₂+3X₃→max, (8.101)

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

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

минимизировать

Z= 10Y₁+ 20У₂ →min, (8/103)

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

Образно говоря, двойственная задача - это на 90 градусов поверну­тая исходная задача:

1. j-й столбец, составленный из коэффициентов, фигурирующих в ог­раничениях исходной модели, совпадает сj-й строкой, составленной из коэффициентов, фигурирующих в ограничениях двойственной модели;

2. строка, составленная из коэффициентов в выражении для целе­вой функции, совпадает со столбцом, составленным из констант, фи­гурирующих в правых частях ограничений двойственной модели;

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

4. направление знаков неравенства в исходной модели противопо­ложно направлению знаков неравенства в двойственной модели. Требо­вание максимизации в исходной задаче заменено требованием миними­зации в двойственной задаче.

Теорема двойственности:

а) если исходная и двойственная ей задача имеют допустимые реше­ния, то: существует оптимальное решение X_j* (j= 1,2,..., п)исходной задачи; существует оптимальное решение Y_i*(i =1,2,..., т)двойственной задачи;

имеет место следующее соотношение:

б) если исходная (двойственная) задача допускает оптимальное ре­шение, для которого значение целевой функции ограничено, то соответ­ствующая ей двойственная (исходная) задача допускает оптимальное ре­шение при том же значении целевой функции.

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

Решение двойственной задачи

В качестве примера рассмотрим ранее решенную Задачу о распреде­лении ресурсов:

максимизировать Z= 4Х₁ +5Х₂ + 9Х₃+ 11Х₄→mах,

Двойственная задача будет формироваться следующим образом:

минимизировать Z= 15Y₁+ 120У₂+ 100Y₃→min, (8.108)

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

Оптимальные значения переменных двойственной задачи:

а) коэффициенты при свободных переменных в строке 0 на последней симплекс-итерации при решении задачи максимизации совпадают с оп­тимальными значениями переменных двойственной задачи;

б) коэффициент при X jв строке 0 на последней симплекс-итерации

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

Рассмотрим коэффициенты при трех свободных переменных в строке 0 на заключительной симплекс-итерации (см. формулу (8.87)). Со­гласно утверждению, приведенному выше, оптимальными значениями переменных двойственной задачи являются следующие:

Убедимся, что выполняются условия (8.105)

а также то, что значение целевой функции двойственной задачи совпада­ет со значением целевой функции исходной задачи

Решение (8.106) должно быть оптимальным, поскольку удовлетворя­ются все ограничения и, кроме того, значения целевых функций исход­ной и двойственной задач совпадают. Наконец, вычислим разность меж­ду левыми и правыми частями соотношений (8.107)

т. е. получаем значения коэффициентов при Х₂и Х₄в строке 0 сис­темы уравнений (К), что согласуется с отверждением, сформулирован­ным выше.

Таким образом, симплексный метод можно рассматривать как способ получения пробных решений двойственной задачи путем определения допустимых решений исходной задачи. Как только удается найти допус­тимое решение этих двух задач, процесс итерации заканчивается.

Продолжение анализа на чувствительность.

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

Обращаясь к примеру, рассмотренному выше, разберем уравнение

Если коэффициент при Х₂в выражении для целевой функции поло­жить равным 5 + δ, то в правой части соотношения (8.110) также будет стоять 5 + δ. Подставив в (8/110) оптимальные значения двойственной задачи (8.106), получим, (с учетом замены (5 + δ)):

Таким образом, решение двойственной задачи остается допустимым, если δ не превышает 3/7. Если же δ принимает значение, превышаю­щее значение 3/7, то это решение не является более допустимым и, сле­довательно, рассматриваемое решение исходной задачи не является более оптимальным.

В каких случаях в базис можно вводить новую переменную?Предпо­ложим, что в нашу задачу вводится дополнительная переменная, причем дополнения к строкам имеют следующий вид:

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

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

Значит при С₈≥14 переменную нужно включать в базис. Оптимальное значение каждой переменной двойственной задачи определяет положительное или отрицательное приращение значения целевой функции за счет единичного приращения (положительного или отрицательного) значения константы в правой части соответствующего ограничения при условии, что рассматриваемый базис остается допустимым.

Оптимальное значение переменных двойственной задачи называют скрытыми доходами. Почему в нашей задаче увеличение объема материала типа А не приводит к увеличению прибыли? Это объясняется тем, что запас материала типа А превышает имеющиеся в нем потребности, что видно из того обстоятельства, что свободная переменная Xg входит

в оптимальный базис. Увеличение заведомо избыточного ресурса не мо­жет увеличить прибыль.