Для любой задачи ЛП можно сформулировать двойственную задачу, являющуюся "зеркальным отражением" исходной задачи, т.к. она использует те же параметры, а ее решение может быть получено одновременно с решением исходной задачи.
Прямая задача:
Сколько изделий и какой конструкции xj (j = 1, …, n) необходимо произвести, чтобы при заданных стоимостях cj (j = 1, …, n) единицы продукции и размерах имеющихся ресурсов bi (i = 1, …, m) максимизировать выпуск продукции в стоимостном выражении?
z = c1x1 + c2x2 + … + cnxn max
xj 0, j = 1, …, n
Двойственная задача:
Какие цены yi на единицу каждого из ресурсов нужно назначить при заданных количествах ресурсов bi и величинах стоимости продукции cj, чтобы продать ресурсы было бы не менее выгодно, чем производить продукцию?
f = b1y1 + b2y2 + … + bmym min
yi 0, i = 1, …, m,
Пары двойственных задач
А. Несимметричные
Прямая задача: Двойственная задача:
Б. Симметричные
Прямая задача: Двойственная задача:
Основные теоремы двойственности
Теорема 1 (основное неравенство двойственности).
Для любых допустимых планов X прямой и Y двойственной задач их целевые функции z(X) и f(Y) связаны между собой неравенствами:
при минимизации z(X) z(X) f(Y),
при максимизации z(X) z(X) f(Y),
и не существенно, какая задача прямая, а какая - двойственная.
Доказательство.
При максимизации z(X):
При минимизации z(X) необходимо записать задачи в соответствующем виде и доказать по аналогии с приведенным доказательством (самостоятельно!).
Теорема 2 (критерий оптимальности Канторовича).
Если на допустимых планах прямой и двойственной задач ЛП значения целевых функций совпадают, то эти планы являются оптимальными и наоборот, если планы прямой и двойственной задач оптимальны, то значения целевых функций на них совпадают.
Доказательство. (Докажем прямое утверждение)
Пусть X – допустимый план прямой задачи, а Y – допустимый план двойственной задачи и z(X) = f(Y).
Пусть X' – произвольный допустимый план прямой задачи. Тогда по основному неравенству двойственности
z(X') f(Y), т.е. z(X') f(Y) = z(X),
т.е. значение целевой функции прямой задачи в точке X является максимальным (т.к. это неравенство выполняется для любого допустимого плана).
Пусть Y' – произвольный допустимый план двойственной задачи. Тогда по основному неравенству двойственности
f(Y') z(X) = f(Y),
т.е. значение целевой функции двойственной задачи в точке Y является минимальным.
Теорема 3. Для существования оптимального решения как прямой, так и двойственной задачи ЛП необходимо и достаточно существования какого-либо допустимого плана для каждой из них.
Доказательство.
Необходимость. Оптимальные решения являются допустимыми по определению. Если существуют оптимальные планы, то с очевидностью существуют и допустимые.
Достаточность. Если Y – допустимый план двойственной задачи, то по основному неравенству двойственности для любого допустимого плана X' прямой задачи выполняется z(X') f(Y).
Т.о., последовательность значений целевой функции прямой задачи z(X1), z(X2), … на различных ее допустимых планах X1, X2, …, полученных симплекс-методом, является неубывающей и ограниченной сверху. Поэтому на допустимых планах X1, X2, … можно выбрать такой план X, для которого z(X') z(X) при любом X', что доказывает условие достаточности для максимума.
Теорема 4. Если прямая (двойственная) задача имеет оптимальное решение, то и двойственная (прямая) задача имеет оптимальное решение.
Теорема 5. Если прямая (двойственная) задача не имеет решения из-за неограниченности целевой функции на множестве допустимых решений, то система ограничений двойственной (прямой) задачи противоречива.
Теорема 6 (о дополняющей нежесткости)
Необходимым и достаточным условиями оптимальности допустимых планов прямой X и двойственной Y задач является выполнение условий дополняющей нежесткости
Использование двойственности при решении задач ЛП
Теория двойственности позволила усовершенствовать симплекс-метод и создать улучшенный (или исправленный) симплекс-метод, который позволяет получать сразу решение и исходной и двойственной задач. Поэтому можно выбирать, решать ли задачу в том виде, в котором она поставлена, или решать двойственную задачу. Так как объем вычислений в задаче ЛП связан скорее с количеством ограничений, чем с количеством переменных, то можно порекомендовать переходить к двойственной задаче в случае, когда ограничений больше, чем переменных.
Теория двойственности позволяет также проводить анализ устойчивости решения при изменении коэффициентов cj и bj, то есть определять границы изменения этих коэффициентов при изменении условий (например, стоимости, запасов ресурсов и т.п.), то есть заранее знать, изменится или нет оптимальное решение, нужен ли дополнительный анализ, понадобится ли еще раз принимать решение.
Теория двойственности создана Дж. Фон Нейманом и Л.В. Канторовичем.