Связь между решениями прямой и двойственной задач

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

(43)

при условиях

(44)

(45)

Двойственная задача: найти минимум функции

(46)

при условиях

(47)

Каждая из задач двойственной пары (43) – (45) и (46), (47) фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определениисимплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи.

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

Лемма 1. Если Х – некоторый план исходной задачи (43) – (45), a Y – произвольный план двойственной задачи (46), (47), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е.

Лемма 2. Если для некоторых планов X^* и Y^* задач (43) – (45) и (46), (47), то X^* – оптимальный план исходной задачи, а Y^* – оптимальный план двойственной задачи.

Теорема 8 (первая теорема двойственности). Если одна из задач двойственной пары (43) – (45) или (46), (47) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т. е.

Если же целевая функция одной задачи из двойственной пары неограничена (для исходной (43) – (45) – сверху, для двойственной (46), (47) – снизу), то другая задача вообще не имеет планов.

Теорема 9 (вторая теорема двойственности). План задачи (43) – (45) и план задачи (46), (47) являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство

Основные теоремы двойственности и их экономическое содержание

Теорема. Для любых допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т.е.
(2.29)
– основное неравенство теории двойственности.
Теорема (критерий оптимальности Канторовича).
Если для некоторых допустимых планов и пары двойственных задач выполняется неравенство , то и являются оптимальными планами соответствующих задач.
Теорема (малая теорема двойственности).
Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существование допустимого плана для каждой из них.
Теорема. Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций равны: . Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.
Экономическое содержание первой теоремы двойственности состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадение значений целевых функций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были оптимальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Двойственные оценки, обладают тем свойством, что они гарантируют рентабельность оптимального плана, т. е. равенство общей оценки продукции и ресурсов, и обусловливают убыточность всякого другого плана, отличного от оптимального. Двойственные оценки позволяют сопоставить и сбалансировать затраты и результаты системы.
Теорема (о дополняющей нежесткости)
Для того, чтобы планы и пары двойственных задач были оптимальны, необходимо и достаточно выполнение условий:
(2.30)
(2.31)
Условия (2.30), (2.31) называются условиями дополняющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.
Экономически это означает, что если по некоторому оптимальному плану производства расход i -го ресурса строго меньше его запаса , то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его i -я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а ресурс избыточный (используемый не полностью) имеет нулевую оценку.
Теорема (об оценках). Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи математического программирования, точнее
(2.32)