Теоремы двойственности. 
Экономико-математические методы и модели в коммерческой деятельности

Каждая из пары двойственных задач может быть решена самостоятельно. Однако при определении оптимального плана прямой задачи находится их решение двойственно.

ЕслиХ* = (xj, х, …, х*) — оптимальный план прямой задачи, a Y* = (г/j, г/2> •••> Ут) ~ система оптимальных оценок ресурсов, то.

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

Оптимальный план можно записать в матричном виде.

где А ¹ — обратная матрица к матрице, составленной из компонент-векторов, вошедших в оптимальный план.

Подставим выражение оптимального плана в уравнение (2.11).

где С§ — матрица коэффициентов базисных переменных, вошедших в оптимальный план.

Тогда оптимальный план двойственной задачи равен.

Таким образом, если найти оптимальный план прямой задачи, используя выражение (2.13), можно получить оптимальный план двойственной задачи. Поскольку в системе уравнений прямой задачи среди векторов Aj (j = 1, п + т) имеются т единичных, то матрица А ¹ расположена в первых т строках оптимальной симплексной таблицы в столбцах единичных векторов. Тогда нет необходимости определять оптимальный план двойственной задачи умножением С₅ на А~ поскольку компоненты этого плана совпадают с соответствующими элементами индексной (т — 1)-й строки столбцов единичных векторов.

Установим соответствие между переменными прямой и двойственной задач в симплексной таблице.

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

Для оптимальных планов X* и Y* пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений.

Вторая теорема двойственности, математически записанная системой уравнений (2.14), может быть интерпретирована следующим образом. Если в оптимальном плане некоторый.

п

г-й ресурс использован не полностью, т. е. если X < b_v то.

* о '⁼¹

соответствующая оценка /-го ресурса //, = 0.

Таким образом, положительную двойственную оценку у * имеют лишь те виды ресурсов, которые полностью использу;

п

ются в оптимальном плане, т. е. когда 2 я"*/ = Ь,.

М

Вторая часть уравнений системы (2.14) свидетельствует о том, что продаже в оптимальном плане подлежат только те виды товаров х* > 0, для которых оценка затраченных на их реализацию ресурсов равна доходу от их продажи, т. е. если.

т

X йуУ* = с_у Нецелесообразно продавать те виды товаров, для.

*⁼1 т

которых 2 (1уУ*^> Су В этом случае в оптимальном плане объ;

f-i.

ем реализации данного товара xj = 0.

Пример 2.10. Составим двойственную задачу к прямой задаче планирования товарооборота, которая решена симплексным методом в п. 2.3.2.

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

Решение прямой задачи получено симплексным методом. Оптимальный план товарооборота.

Используя последнюю итерацию прямой задачи (план III симплексной табл. 2.6), найдем оптимальный план двойственной задачи.

Из теоремы двойственности следует, что У * = С§/4^-1.

Составим матрицу А из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу А ¹ каким-либо методом, например через алгебраические дополнения, получим.

Как очевидно из плана III симплексной табл. 2.6, обратная матрица Л^-1 расположена в столбцах дополнительных переменных дг₄, х& х& Тогда.

Оптимальный план двойственной задачи равен.

У* = (23,75; 12,5; 0; 0; 0; 5,75); Z (Y*) = 27 625.

Подставим оптимальный план прямой задачи в систему ограниченной математической модели планирования товарооборота:

Первое и второе ограничения прямой задачи выполняются как равенства. Это означает, что ресурсы первого и второго видов полностью используются в оптимальном плане, являются дефицитными и их оценки согласно второй теореме двойственности отличны от нуля (у* > 0, у2 > 0). Третье ограничение выполняется как строгое неравенство, т. е. ресурс третьего вида израсходован не полностью, остаток его в оптимальном плане х<$ = 1875. Значит, ресурс третьего вида не является дефицитным, и его оценка в оптимальном плане г/з = 0.

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

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим.

Первое и второе ограничения двойственной задачи выполняются как равенства. Это означает, что двойственные оценки ресурсов, используемых для реализации единицы товаров первой и второй групп, равны в точности доходам. Поэтому продавать эти виды товаров экономически целесообразно, а их реализация предусмотрена оптимальным планом прямой задачи (х* > 0,.Г2* > 0). Третье ограничение двойственной задачи выполняется как строгое неравенство. Это означает, что двойственная оценка, используемая при реализации единицы товара третьей группы, выше дохода от его продажи. Следовательно, продавать товары третьей группы невыгодно, и действительно, в оптимальном плане прямой задачи = 0.

Величина двойственной оценки показывает, насколько возрастает значение целевой функции при увеличении дефицитного ресурса на единицу. Например, увеличение рабочего времени на 1 чел.-ч приведет к получению нового оптимального плана, в котором прибыль возрастает на 23,75 и станет равной.

При этом коэффициенты оптимальной симплексной табл. 2.6 столбца^, коэффициенты структурных сдвигов к_с показывают, что указанное увеличение прибыли достигается за счет увеличения реализации второй группы товара на величину 6,25 ед., уменьшения объема продажи первой группы товара на величину 2,5 ед. и уменьшения остатка ресурса третьего вида на 62,5 м².

В то же время ввод в продажу невыгодной группы товаров уменьшает размер дохода. Если xl = 1, то.

При этом коэффициенты структурных сдвигов оптимальной симплексной табл. 2.6 столбца х$ показывают, что указанное уменьшение дохода происходит за счет уменьшения объема продажи выгодного товара второй группы на величину 2,25 ед., увеличения продажи первой группы товара на 0,5 ед. и уменьшения остатка ресурсов третьего вида на 1,25 м².

Таким образом, двойственные оценки связаны с оптимальным планом прямой задачи. Всякое изменение исходных данных прямой задачи оказывает влияние на ее оптимальный план и систему двойственных оценок. В свою очередь двойственные оценки служат инструментом анализа и принятия правильных решений в условиях меняющихся коммерческих ситуаций.