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

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

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

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

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

Представим, что другое предприятие, производящее другие виды продукции по другим технологиям, но с использованием трех таких же видов ресурсов, которые имеются у нас, предлагает нам «уступить» имеющиеся у нас ресурсы по «договорным» ценам. Возникает вопрос: при каких предложенных ценах мы можем согласиться с таким предложением.

Технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С известны:

3 0 3 3 186

A = 2 3 1 1 B = 102 C =(38 12 28 21)

4 3 2 2 196

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

б) Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы затрат А, 3, 2 и 4 единиц 1-го, 2-го и 3-го видов ресурсов соответственно (элементы первого столбца матрицы).

В ценах у1, у2, у3 наши затраты на производство одной единицы первого вида продукции составят: 3у1 + 2у2 + 4у3, т.е. столько нам готово заплатить другое предприятие за все ресурсы, идущие на производство первого вида продукции. На рынке за единицу первого вида продукции мы получили бы прибыль в размере 38 денежных единиц.

Следовательно, мы можем согласиться с предложением «уступить» ресурсы, идущие на производство первого вида продукции, только в том случае, если нам заплатят не меньше 38 денежных единиц. Математически это можно выразить неравенством:

3у1 + 2у2 + 4у3 ≥ 38

Аналогичное условие «уступки» ресурсов мы поставим и по другим видам продукции:

3у2 + 3у3 ≥ 12

3у1 + у2 + 2у3 ≥ 28

3у1 + у2 + 2у3 ≥ 21

в) Выразим через введенные переменные у1, у2, у3 общую стоимость всех имеющихся ресурсов, которую нам должны заплатить:

F = 186у1 + 102у2 + 196у3 денежных единиц.

При поставленных нами условиях покупающее ресурсы предприятие будет искать такие значения у1, у2, у3, чтобы общая стоимость всех ресурсов была как можно меньше.

Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования:

Найти вектор двойственных оценок ресурсов: У (у1, у2, у3, у4),

минимизирующий общую оценку всех ресурсов F = 186у1 + 102у2 + 196у3 → min,

при условии, что по каждому виду продукции 3у1 + 2у2 + 4у3 ≥ 38

суммарная оценка всех ресурсов, затрачиваемых на 3у2 + 3у3 ≥ 12

производство единицы продукции, не меньше 3у1 + у2 + 2у3 ≥ 28

прибыли, получаемой от реализации единицы 3у1 + у2 + 2у3 ≥ 21

этой продукции,

причем оценки ресурсов не могут быть отрицательными у1 ≥ 0, у2 ≥ 0, у3 ≥ 0

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

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности (о дополняющей нежесткости), в соответствии с которой для того, чтобы Х (х1, х2, х3, х4) и У (у1, у2, у3) являлись оптимальным решением соответствующих задач двойственной пары, необходимо и достаточно выполнение условий

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

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

Поскольку оптимальная производственная программа Х*(х1*, х2*,х3*, х4*) нам известна (см. п. 1.4.): х1* = 36, х2* = 0, х3* = 26, х4* = 0, подставим значения известных нам переменных в уравнения:

ИЛИ

В первой группе уравнений второе уравнение у2( 98 - 102) = 0 означает, что при выполнении оптимальной производственной программы второй ресурс расходуется не полностью (98 единиц из 102), следовательно, двойственная оценка второго ресурса равна нулю: у2* = 0

Остальные (первый и третий) ресурсы расходуются полностью и являются дефицитными, следовательно, у1*, у3* > 0

Первое и третье уравнения второй группы означают, что поскольку продукции первого и третьего вида входят в оптимальную производственную программу (х1* = 36, х3* = 26), то суммарная двойственная оценка ресурсов, расходуемых на производство первого и третьего видов продукции соответственно, должна быть равна цене единицы этого вида продукции.

Получаем:

у2* = 0

3у1 + 2у2 + 4у3 = 38

3у1 + у2 + 2у3 = 28

Решаем полученную систему уравнений

Таким образом, двойственные оценки ресурсов у1* = 6, у2* = 0, у3* = 5

При этом общая оценка всех ресурсов равна

F*(min) = 186у1* + 102у2* + 196у3* = 186 * 6 + 196 * 5 = 1116 + 980 = 2096 денежных единиц.

Экономически смысл двойственных оценок ресурсов у1* = 6, у2* = 0, у3* = 5 показывает, что добавление одной единицы 1-го (2-го, 3-го) ресурса обеспечит прирост прибыли на 6 (0, 5) денежных единиц.

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

Оценка 1-ой технологии: ∆1 = 3у1*+ 2у2*+ 4у3*- 38

∆1= 3*6 + 2*0 + 4*5 – 38

∆1 = 0

Действительно, 1-ая технология применяется (производство продукции первого вида входит в оптимальную производственную программу).

Оценка 2-ой технологии: ∆2 = 3у2*+ 3у3*- 12

∆2= 3*0 + 3*5 – 12

∆2 = 3

Данная оценка показывает, что если произвести одну единицу продукции второго вида, то прибыль уменьшится на 3 денежные единицы, поэтому 2-ой вид продукции не входит в оптимальную производственную программу.

Оценка 3-ей технологии: ∆3 = 3у1*+ у2*+ 2у3*- 28

∆3= 3*6 + 0 + 2*5 – 28

∆3 = 0

3-я технология применяется.

Оценка 4-ой технологии: ∆4 = 3у1*+ у2*+ 2у3*- 21

∆4= 3*6 + 0 + 2*5 – 21

∆4 = 7

Если произвести одну единицу 4-го вида продукции, то прибыль уменьшится на 7 денежных единиц.

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