Понятие двойственности. Построение двойственных задач

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

рассмотрим понятие двойственности на примере зада­чи оптимального использования сырья. Пусть на предпри­ятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья т видов в объемах b_i единиц (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 (малая теорема двойственности). Для су­ществования оптимального плана любой из пары двойст­венных задач необходимо и достаточно существование допустимого плана для каждой из них.