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

Каждой исходной задаче соответствует двойственная ЗЛП.

Если в исходной задаче ищется , определяются значения n переменных x₁, x₂, …, x_n и используется m ограничений; то в двойственной задаче находятся , значения m переменных y₁, y₂, …, y_m и используется n ограничений.

Для условий типовой исходной задачи составим модель двойственной задачи. Для правильного перехода к двойственной задаче в исходной задаче на max все знаки неравенств должны иметь вид «£»:

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

1. Число переменных в двойственной задаче равно числу ограничений в исходной задаче, т.е. в нашем случае m = 4: y₁, y₂, y₃, y₄.

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

3. Знаки «£» в системе ограничений заменяются на противоположные «³».

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

5. На каждую переменную двойственной задачи накладывается условие неотрицательности.

Используя эти правила, запишем двойственную задачу

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

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

Таким образом, необходимо найти такой набор теневых цен (оценок) ресурсов , при котором общие затраты на сырье Z будут минимальными (min) при условии, что выручка от продажи сырья А, В, С, используемого при производстве единицы продукции I и II видов, будет не менее единичной прибыли (прибыли от реализации единицы продукции).

Искомыми переменными являются y₁, y₂, y₃ – теневые (внутренние) цены на сырье. Теневая цена выражает величину изменения целевой функции F (прибыли) при изменении имеющегося объема сырья данного вида (т.е. в исходной задаче – правой части неравенства) на единицу при условии, что все остальные переменные не изменяются. Теневая цена имеет и другие названия: условная, скрытая, неявная. Смысл этих названий в том, что это условные, ненастоящие цены, которые определяются непосредственно в результате решения задачи, поэтому их называют оценками.

Переменная y₄ также имеет неявный смысл и выражает величину изменения прибыли F при изменении на единицу правой части ограничения–неравенства x₁ + x₂ ≥ 10 ед. (общее количество производимой продукции должно быть не менее 10 единиц). Полученное значение переменной y₄ можно назвать оценкой снижения выручки от продажи сырья за счет отвлечения ресурсов для производства количества продукции, превышающего 10 единиц.

Найдем оптимальное решение двойственной задачи. Для этого составим соотношение между переменными исходной и двойственной задач и используем индексную F–строку последней табл. 4 (функцию F исходной задачи, выраженную через свободные переменные: ).

исходная задача
первоначальные	дополнительные
дополнительные	первоначальные
двойственная задача

 

Согласно правилу 4, компоненты оптимального решения двойственной задачи y_i^* равны абсолютным значениям коэффициентов Δ_j при соответствующих переменных x_j^* функции F исходной задачи, выраженной через свободные переменные ее оптимального решения.

Используя , отсюда запишем:

- первоначальные переменные:

y₁^* = Δ₃ = 0; y₂^* = Δ₄ = 2; y₃^* = Δ₅ = 1; y₄^* = Δ₆ = 0;

- дополнительные переменные:

y₅^* = Δ₁ = 0; y₆^* = Δ₂ = 0.

Оптимальное решение двойственной задачи: = (0, 2, 1, 0, 0, 0).

Минимальные общие затраты на ресурсы: = 54 y.е. = .

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

Первоначальные переменные исходной задачи – план производства (количество производимой продукции): x₁ = 9 ед. I вида, x₂ = 6 ед. II вида.

Дополнительные переменные исходной задачи x₃, x₄, x₅ – остатки сырья, x₆ – превышение над нижней производственной границей:

x₃ = 51 кг. Сырье А недоиспользовано на 51 кг.

x₄ = x₅ = 0. Ресурсы В и С использованы полностью, являются дефицитными.

x₆ = 6 ед. I и II видов. Превышение над нижней производственной границей составляет 5 единиц продукции обоих видов.

Первоначальные переменные двойственной задачи y₁, y₂, y₃ характеризуют дефицитность сырья и называются «теневыми» ценами единицы (1 кг) сырья. Если y_i > 0, то сырье недефицитное; если y_i = 0, то сырье дефицитное.

y₁ = 0 у.е. Сырье А недефицитное (x₃ = 51 кг).

y₂ = 2 у.е., y₃ = 1 у.е. Сырье видов В и С дефицитное (x₄ = x₅ = 0 кг).

Например, если увеличить запасы сырья В на 1 кг, то прибыль увеличится на 2 у.е., если же его запасы увеличить на 5 кг, то прибыль увеличится на 5·2=10 у.е.

Первоначальная переменная y₄ формально предполагает «скрытый» убыток (или доход). Фактически изменение нижней производственной границы «10» на величину max прибыли F_max не влияет, поэтому y₄ = 0 у.е.

Дополнительные переменные двойственной задачи y₅, y₆ характеризуют рентабельность производства, т.е. показывают превышение затрат на ресурсы над ценой реализации продукции. Если дополнительная переменная положительная, то производство нерентабельно (убыточно); если переменная равна нулю, тогда производство является рентабельным (безубыточным).

y₅ = y₆ = 0. Производство продукции и I, и II вида рентабельно (x₁ = 9, x₂ = 6).