6. Двойственность в линейном программировании

Понятие двойственности является одним из важнейших в теории ЛП. С каждой задачей ЛП связывается другая вполне определенная задача, которая называется двойственной к исходной (прямой) задаче.

Двойственной к стандартной задаче (14) – (16) называется задача ЛП от m переменных вида

(31)

(32)

(33)

Связь между условиями прямой задачи (14) – (16) и двойственной (31) – (33) показана схематически в таблице 5:

Таблица 5

Ограничения и целевая функция прямой задачи «записаны» в строках таблицы 5, ограничения и целевая функция двойственной задачи «читаются» по столбцам.

Пример 15. Записать условие задачи, двойственной к стандартной задаче из примера 11.

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

Двойственную задачу примера 15 можно привести к стандартному виду, затем записать условие двойственной к ней и снова привести к стандартному виду. Проверьте, что результатом таких преобразований будет исходная (прямая) задача. Нетрудно понять, что и в общем случае задача, двойственная к двойственной совпадает с исходной.

В теории ЛП доказаны следующие утверждения (теоремы двойственности), устанавливающие связи между свойствами задач двойственной пары.

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

Теорема 2. Для того, чтобы допустимые планы

пары двойственных задач (14) – (16) и (31) – (33) были их оптимальными планами, необходимо и достаточно, чтобы они удовлетворяли системе уравнений

Теорема 1 – центральный результат всей теории ЛП. Теорема 2 позволяет найти оптимальный план одной из задач двойственной пары по оптимальному плану другой.

Пример 16. Решить задачу ЛП

,

Решение. Запишем условие двойственной задачи

Эту задачу можно решить графически (проделайте самостоятельно), в результате получим По теореме 1 исходная (прямая) задача также имеет оптимальный план Чтобы найти подставим

в систему уравнений из теоремы 2:

Второе и третье уравнения представляют собой тождества 0 = 0.

Для определения даже не обязательно подставлять эти числа в выражение для целевой функции F, так как из теоремы 1 следует (проверьте подстановкой).

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

Пример 17. Приведем обе задачи двойственной пары из предыдущего примера к канонической форме. В прямой задаче заменим и введем балансовые переменные в двойственной задаче введем балансовые переменные

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

Примем за базисные переменные в прямой задаче (тогда свободные) и переменные в двойственной задаче (тогда свободные). Каждая базисная переменная , содержатся в определенном ограничении одной из задач двойственной пары; этому ограничению соответствует определенная свободная переменная другой задачи.

Запишем симплексные таблицы обеих задач, в которых переменные

приняты за базисные:

В таблицах рядом с каждой переменной записана в скобках соответствующая переменная двойственной задачи; добавлены также символы в правых верхних углах. Благодаря этим дополнениям любое из равенств канонических форм обеих задач можно «прочитать» как в строке одной из таблиц, так и в столбце другой (во втором случае надо использовать переменные, записанные в скобках). Например, первая строка и первый столбец являются записями эквивалентных равенств и

в последней строке и последнем столбце тоже записаны эквивалентные равенства и Связь таблиц аналогична связи двух транспонированных относительно друг друга матриц: обозначения строк в переходят в обозначения столбцов числа 1,-1,-3,-4 первой строки переходят в числа -1, 1, 3, -4 первого столбца и т.д.

Таблица допустима (числа 6, 9, 5 неотрицательны), ее можно принять за начальную для решения двойственной задачи симплекс-методом. По инструкциям симплекс-метода находим разрешающий элемент 3 таблицы В таблице примем за разрешающий соответствующий элемент (-3) и выполним симплексные преобразования таблиц В результате получим новые таблицы

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

Допустимая таблица удовлетворяет условию оптимальности (числа 1/2, 5/2 положительны).Ей соответствует единственный оптимальный опорный план двойственной задачи : (свободные в ), . Учитывая «транспонированность» и соответствие между переменными взаимодвойственных задач, по таблице можно найти и оптимальный опорный план () прямой задачи. Переменные записанные в скобках в левом столбце будут свободными в следовательно Переменные записанные в скобках в верхней строке будут базисными в следовательно (см. строку ). Очевидно, что Аналогично оба оптимальных плана можно найти по таблице

Связь между симплексными таблицами прямой и двойственной задач, которая использовалась в примере 17, является основой нового способа решения задач ЛП, получившего название двойственного симплекс-метода. В этом методе начальная и все следующие таблицы удовлетворяют условию оптимальности вместо требования допустимости в обычном симплекс-методе. Заключительная таблица дает оптимальный план или позволяет сделать вывод об отсутствии допустимых (и тем более оптимальных) планов. Правила выбора разрешающего элемента в текущей симплексной таблице получаются из соответствующих правил обычного симплекс-метода для двойственной задачи с учетом связей между таблицами двойственной пары.