ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
рассмотрим понятие двойственности на примере задачи оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья т видов в объемах bi единиц (i = 1 ,…, m). Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск п видов неосновной продукции. Обозначим через аij норму расхода сырья i -го вида на единицу j- й (j = 1,…, п) продукции, сj – цена реализации единицы j -й продукции (реализация обеспечена). Неизвестные величины задачи: хj – объемы выпуска j- й продукции, обеспечивающие предприятию максимум выручки.
Математическая модель задачи:
(3.1)
Предположим далее, что с самого начала при изучении вопроса об использовании отходов основного производства на предприятии появилась возможность реализации их некоторой организации. Необходимо установить прикидочные оценки (цены) на эти отходы. Обозначим их . Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы предприятия и организации:
|
|
1) общую стоимость отходов сырья покупающая организация стремится минимизировать;
2) предприятие согласно уступить отходы только по таким ценам, при которых оно получит за них выручку, не меньшую той, что могло бы получить, организовав собственное производство.
Эти требования формализуются в виде следующей ЗЛП:
(3.2)
Переменные называются двойственными оценками или объективно обусловленными оценками. В зарубежной литературе их еще называют теневыми ценами.
Можно показать, что если в качестве прямой принять задачу (3.2) об определении оптимальных оценок на сырье, то двойственной к ней будет задача (3.1) об определении оптимального плана выпуска продукции.
Из моделей (3.1) и (3.2) непосредственно видно, что, имея математическую модель одной из этих задач, можно легко построить модель двойственной к ней задачи. Сопоставляя модели (3.1) и (3.2) пары двойственных задач, можно установить следующие взаимосвязи.
1. Если прямая задача на максимум, то двойственная к ней – на минимум, и наоборот.
2. Коэффициенты целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.
3. Свободные члены ограничений прямой задачи являются коэффициентами целевой функции двойственной.
4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.
5. Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа . Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .
|
|
6. Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной – числу переменных прямой.
7. Все переменные в обеих задачах неотрицательны.
Очевидно, что задача, двойственная двойственной, совпадает с исходной. Поэтому безразлично, какую задачу принять в качестве прямой, а какую – в качестве двойственной. Следует говорить о паре взаимно двойственных задач.
Рассмотрим пару двойственных ЗЛП (3.1) и (3.2).
Теорема 3.1. Для любых допустимых планов х = и
Y = прямой и двойственной ЗЛП справедливо неравенство z (x) f (y), т. е.
. (3.3)
Доказательство. Учитывая ограничения обеих ЗЛП, получаем
,
т. е. имеем неравенство (3.3), которое называется основным неравенством теории двойственности.
Экономическое содержание неравенства (3.3) состоит в том, что для любого допустимого плана производства х и любого допустимого вектора оценок ресурсов Y общая созданная стоимость не превосходит суммарной оценки ресурсов.
Теорема 3.2. (критерий оптимальности Канторовича). Если для некоторых допустимых планов х* и Y* пары двойственных задач выполняется равенство z (x*) = f (y*), то х* и Y* являются оптимальными планами соответствующих задач.
Доказательство. Согласно основному неравенству двойственности, для любого допустимого плана х прямой задачи и допустимого плана Y* двойственной справедливо неравенство z (x) f (y*). Но по условию
z (x*) = f (y*). Отсюда, в силу транзитивности отношений и =, получим z (x) z (x*). Так как х – произвольный план, то z (x*) = max Z, т.е. х* – оптимальный план прямой ЗЛП.
Аналогично доказывается, что план Y* является оптимальным для двойственной задачи.
Экономическое содержание теоремы 3.2 состоит в том, что план производства х и вектор оценок ресурсов Y являются оптимальными, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают.
Теорема 3.3 (малая теорема двойственности). Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существование допустимого плана для каждой из них.