Построение двойственной задачи

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

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

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

(2.5.1)

при ограничениях:

(2.5.2),

(2.5.3).

Чтобы сформулировать условия двойственной задачи, проведем симметричное структурное преобразование условий прямой задачи в соответствии со следующими правилами:

1) каждому ограничению прямой задачи соответствует переменная двойственной задачи;

2) каждой переменной прямой задачи соответствует ограничение двойственной задачи;

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

На примере задачи планирования товарооборота двойственная задача формулируется следующим образом:

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

Запишем математическую модель двойственной задачи.

Определить вектор , который удовлетворяет ограничениям

(2.5.4),

(2.5.5)

и обеспечивает минимальное значение целевой функции

(2.5.6).

Ограничения (2.5.4) показывают, что стоимость всех ресурсов, затраченных на продажу единицы j-группы товаров, должна быть не меньше дохода, получаемого при реализации единицы j-группы товаров, а общая стоимость всех ресурсов должна быть

минимизирована.

В целом двойственная задача по отношению к исходной составляется согласно следующим правилам.

1. Число переменных в двойственной задаче равно числу ограничений в прямой задаче.

2. Матрица коэффициентов системы ограничений двойственной задачи получается из матрицы коэффициентов системы ограничений прямой задачи путем транспонирования.

3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

4. Свободными членами системы ограничений двойственной задачи являются коэффициенты функции цели прямой задачи.

5. Двойственная задача решается на минимум, если целевая функция прямой задачи задается на максимум, и наоборот.

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

7. Если переменная прямой задачи , то j-е условие системы ограничений двойственной задачи является неравенством, если — любое число, то j-е условие двойственной задачи представляет собой уравнение.

8. Если i-е соотношение прямой задачи является неравенством, то соответствующая оценка i-го ресурса — переменная , если i-е соотношение представляет собой уравнение, то переменная двойственной задачи — любое число.

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

 

Теоремы двойственности

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

Если - оптимальный план прямой задачи, а — система оптимальных оценок ресурсов, то

(2.5.7),

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

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

(2.5.8),

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

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

,

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

(2.5.9).

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

Переменные прямой задачи (заголовок симплексной таблицы)
основные	дополнительные
Переменные двойственной задачи (их значения расположены в индексной строке оптимальной симплексной таблицы)
дополнительные	основные

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

 

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

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

(2.5.10).

 

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

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

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

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

Прямая задача

Двойственная задача

 

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

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

Оптимальный план товарооборота:

=(250; 5375; 0; 0; 0; 1875); F()= 27625 тыс. руб.

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

Из теоремы двойственности следует, что .

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

.

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

.

Как видно из плана III симплексной табл. 2.4.2, обратная матрица расположена в столбцах дополнительных переменных .

Тогда .

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

=(23,75; 12,5; 0; 0; 0; 5,75); Z()= 27625 тыс. руб.

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

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

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

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

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

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

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

F()= 27625 + = 27625 + 23,75=27648,75 тыс. руб.

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

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

F()= 27625 - 5,75 = 27619,25 тыс. руб.

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

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