3.2 Теоремы двойственности в линейном программировании

Основные утверждения о взаимно двойственных задачах содержатся в следующих теоремах.

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

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

Вторая теорема двойственности. Для того, чтобы два допустимых решения иУ=(у1, у2, …, уm)пары двойственных задач были оптимальными необходимо и достаточно, чтобы они удовлетворяли так называемым «условиям дополняющей нежесткости»:

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

Третья теорема двойственности (теорема об оценках). Значения переменныхуi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов ограничений исходной задачи на экстремальное значение ее целевой функции Zmax, т.е.

3.3 Экономическая интерпретация двойственных задач

В разделе 3.1 приведен один из возможных вариантов экономической интерпретации двойственных задач. В случае рассмотрения задачи планирования работы предприятия, производящего nвидов продукции с использованиемm видов ресурсов, решением исходной задачи является план производства , а решением двойственной задачи – совокупность цен (двойственных оценок) ресурсовУ=(у1, у2, …, уm),соответствующих этому плану.

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

Согласно третьей теореме двойственности оценки ресурсовУ=(у1, у2, …, уm)выступают как мера влияния объемов ресурсов на величину максимума товарной продукции (Zmax). Они показывают: на сколько увеличится значение целевой функции при приращении данного ресурса наединицу. Следовательно, еслиi-й ресурс увеличится на единиц, то целевая функция соответственно возрастет на ден. ед. Однако надо помнить, что это справедливо только для таких приращений ресурса, которые не вызовут изменение базиса исходной задачи.

Чтобы определить предел увеличения ресурса, не приводящий к изменению базиса в оптимальной симплекс-таблице, рассматривают коэффициенты таблицы, принадлежащие столбцу соответствующей ресурсу дополнительной переменной. Эти коэффициенты показывают на сколько увеличатся (если коэффициент больше 0), и на сколько уменьшатся (если коэффициент меньше 0) значения базисных переменных, если в задачу вводится дополнительная единица ресурса. Предел увеличения ресурса находится из условия неотрицательности новых значений базисных переменных. Поэтому его вычисляют как минимум модуля отношений значений базисных переменных к отрицательным коэффициентам столбца дополнительной переменной. Например, для ресурса с индексом jпредел увеличения равен

Пример расчета предела увеличения ресурса для задачи 2.1 приведен в разделе 2.2. В этой задаче при увеличении ресурса 2, не превышающем 6000 ед., справедлива его оценка y2, являющаяся решением двойственной задачи.

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

Из второй теоремы двойственностиследует, что если оценкауiединицы ресурса положительна, то при оптимальном плане производства этот ресурс используется полностью, т.е. является по определению дефицитным, ауiназываетсястепенью дефицитности. Если же ресурс используется не полностью, то его оценка равна0. Аналогично, еслиj-япродукция используется в производстве, т.е. , то она в оптимальных двойственных оценках неубыточна (рентабельна), если же она убыточна (нерентабельна), то в производстве не используется ( ). Двойственная оценкауjтакой продукции называетсястепенью нерентабельности.

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

Решение двойственной задачи получается в последней симплексной таблице исходной задачи (3.1)-(3.3), в (М+1)-й строке.

Если в качестве исходной задачи служит модель (3.4)-(3.6), то решение двойственной к ней (3.1)-(3.3) получается умножением на (-1) соответствующих элементов (М+1)-й строки последней симплекс-таблицы задачи (3.4)-(3.6).

Для того чтобы правильно выписать из симплекс-таблицы решение двойственной задачи, необходимо установить соответствие переменных прямой и двойственной задач, исходя из их канонической формы:

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

– дополнительным переменным исходной соответствуют основные переменные двойственной модели.

Значения основных переменных двойственной задачи расположены в столбцах дополнительных переменных (М+1)-й строки симплекс-таблицы прямой задачи, а значения дополнительных переменных – в столбцах основных переменных той же строки.