Двойственные задачи линейного программирования

Каждой задаче ЛП можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой):

Прямая задача (ПЗ)

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

ДЗ по отношению к прямой составляют согласно правилам:

1) ЦФ ПЗ задаётся на max, тогда ЦФ ДЗ – на min, и наоборот;

2) матрица , составленная из коэффициентов в

системе ограничений ПЗ, и аналогичная матрица в ДЗ получаются друг из друга транспонированием;

3) число переменных в ДЗ (т) равно числу соотношений (ограничений) в ПЗ, а число ограничений ДЗ (п) – числу переменных в ПЗ;

4) коэффициенты при неизвестных в ЦФ ДЗ – свободные члены (b_i), а правые части в ограничениях ДЗ (c_j) – коэффициенты при неизвестных в ЦФ ПЗ;

5) если переменная x_j ПЗ может принимать только положительные значения (x_j ³ 0), то j-е условие ПЗ – условие неравенства вида «³». Если i-е соотношение в ПЗ – неравенство, то i-я переменная ДЗ z_i ³ 0.

 

Если ПЗ имеет решение, то и ДЗ тоже имеет решение, причём max(min) L₁ = min(max)L₂. Поэтому достаточно для отыскания оптимума решить одну какую-либо из задач двойственной пары, обычно решают ту, которая проще.

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

 

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

Свойство 1. max(min) L₁ = min(max)L₂

Исходя из первого свойства ДЗ, можно провести следующую интерпретацию двойственной задачи

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

Если ресурс в ПЗ используется не полностью, то соответствующая величина двойственной переменной (оценки) в ДЗ равна “0”, и, наоборот, если ресурс используется полностью, то его увеличение или уменьшение влияет на значение ЦФ в ПЗ.

Свойство 2.

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

	(а)
	(б)

 

Ограничение вида “а” говорит о том, что суммарная оценка всех используемых ресурсов на производство единицы продукции равна стоимость единицы продукции.

Ограничение вида “б” говорит о том, что двойственная оценка всех видов ресурсов на производство одной единицы продукции вида выше цены этой продукции. Значит, ее выпускать невыгодно.

Анализ соотношений “а” и “б” позволяет следующим образом проинтерпретировать взаимоотношение покупателя ресурса и организации, имеющей (производящей) данный ресурс. Покупатель стремится минимизировать стоимость ресурса, однако ее нельзя сделать меньше стоимости той продукции, которую собирается выпускать покупатель, т.к. в этом случае организации будет выгоднее самой наладить производство соответствующей продукции, а не продавать ресурсы.

Свойство 3.

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

,

— дополнительные двойственные переменные

Если основные переменные (переменные в ПЗ) равны нулю, то дополнительные двойственные переменные положительные значения и их величины показывают насколько уменьшится значение ЦФ в ПЗ при принудительном выпуске единицы продукции соответствующего вида.

Свойство 4.

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

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

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

 

Пример. Для производства изделий А, В, С используются три различных вида ресурсов. Каждый из видов ресурсов может быть использован в количестве соответственно не большем 180, 210, 244 ед. Известны затраты каждого из видов ресурсов на единицу продукции и цена единицы продукции каждого вида (табл.2.10).

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

Таблица 2.5.1.

Вид ресурса	Норма расхода ресурса (ед. изм.) на единицу продукции
А	В	С
Цена продукции

 

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

Решение.

ПЗ

ДЗ

Решение ПЗ даёт оптимальный план производства изделий А, В, С, а решение ДЗ – оптимальную систему оценок ресурсов, используемых для производства этих изделий:

Исходя из анализа оптимальных двойственных оценок можно сделать следующие выводы.

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

§ Более того, величина двойственной оценки показывает, на сколько возрастает максимальное значение ЦФ ПЗ при увеличении количество соответствующего ресурса на 1 ед. Так, увеличение количества ресурса первого вида на 1 ед. приведёт к тому, что появится возможность найти новый оптимальный план производства изделий, при которой общий доход возрастает на 5,75 д.е. и станет равным 1340+5,75=1345,75 д.е. Анализ полученных оптимальных значений новой ПЗ показывает, что это увеличение общего дохода достигается за счёт увеличения производства изделий В на 0,625 ед. и сокращения выпуска изделий С на 0,25 ед. Вследствие этого использование ресурса второго вида уменьшается на 0,125 ед.

Точно также увеличение на 1 ед.количества ресурсов третьего вида позволит перейти к новому оптимальному плану производства, при котором доход возрастает на 1,25 д.е. и составит 1340+1,25=1341,25 д.е., что достигается за счёт увеличения выпуска изделий С на 0,25 ед. и уменьшения выпуска В на 0,25 ед., причём объём используемого ресурса второго вида возрастает на 0,625 ед.

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