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

содержание

Теорема 3.4. Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функ­ций равны: z(x*) = f(y*). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.

Рассмотрим пару симметричных двой­ственных задач (3.1) и (3.2). Вводя дополнительные переменные х_n+1, ..., х_n+m в прямую зада­чу и y_m+1, ..., у_т+п в двойственную, приводим модели задач к канони­ческому виду.

Теперь между переменными двойственных задач можно установить соответствие, сопоставляя свободным перемен­ным одной задачи базисные переменные другой, и на­оборот:

Экономическое содержание первой теоремы двойствен­ности состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продук­ции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммар­ной оценкой ресурсов. Совпадение значений целевых функций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были опти­мальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Двойст­венные оценки обладают тем свойством, что они гаранти­руют рентабельность оптимального плана, т. е. равенство общей оценки продукции и ресурсов, и обусловливают убыточность всякого другого плана, отличного от опти­мального. Двойственные оценки позволяют сопоставить и сбалансировать затраты и результаты системы.

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

Теорема 3.5 (о дополняющей нежесткости). Для того чтобы планы х* и Y* пары двойственных задач были опти­мальными, необходимо и достаточно выполнение условий:

, (3.4)

. (3.5)

Доказательство. Необходимость. Пусть х* и Y* - оптимальные планы двойственных ЗЛП (3.1) и (3.2). Согласно теореме 2.4, для этих планов значения целевых функций совпадают: z(x*) = f(y*), т.е.

. (3.6)

Предположим, что для оптимального плана х* ограничения задачи (3.1) обращаются в точные равенства, т.е.

. (3.7)

Подставив в выражение (3.6) b_i из равенства (3.7), получим

,

откуда

.

Отсюда следует условие (3.4), поскольку и . Условия (3.5) доказываются аналогично.

Достаточность. Пусть для некоторых допустимых пла­нов х* и Y* выполняются условия (3.4). Докажем их оптимальность. Просуммировав равенства (3.4) по всем j от 1 до п и выполнив преобразования, противоположные предыдущим, получим выражение (3.6). Согласно крите­рию Канторовича, планы х* и Y* являются оптималь­ными.

Условия (3.4), (3.5) называются условиями допол­няющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обра­щается в строгое неравенство, то соответствующая компо­нента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента опти­мального плана одной из задач положительна, то соответ­ствующее ограничение в двойственной задаче ее опти­мальным планом должно обращаться в строгое равенство.

Экономически это означает, что если по некоторому оптимальному плану х* производства расход i-го ресурса строго меньше его запаса, то в оптимальном плане соответствующая двойственная оценка единицы это­го ресурса равна нулю. Если же в некотором оптимальном плане оценок его
i-я компонента строго больше нуля, то в оптимальном плане производства расход соответствую­щего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положитель­ную оценку, а ресурс избыточный (используемый не полно­стью) имеет нулевую оценку.

Рассмотрим задачу определения оптимального плана выпуска продукции. Предположим, что запасы ресурсов могут изменяться. Возникает вопрос: как эти изменения сказываются на экстремальном значении выручки предприятия? На этот вопрос отвечает следую­щая теорема (без доказательства).

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

. (3.8)

Перейдем к выяснению экономического содержания третьей теоремы двойственности. Для этого в равенстве (3.8) дифференциалы заменим приращениями. Получим . При имеем . Отсюда следует, что ве­личина двойственной оценки численно равна изменению целевой функции при изменении соответствующего сво­бодного члена ограничений на единицу. В прикладных задачах двойственные оценки у_i* называют скрытыми, теневыми ценами или маргинальными оценками ресурсов.