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

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

Теперь представим себе, что знакомый предприниматель П, занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у₁ рублей за каждую единицу первого ресурса, у₂ руб – второго, у₃ руб – третьего. Возникает вопрос: при каких ценах у₁, у₂, у₃ мы можем согласиться с предложением П.

В еличины у₁, у₂, у₃ принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.

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

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 2 единицы ресурса первого вида, 4 единицы ресурса второго вида и 2 единицы третьего (элементы первого столбца матрицы). В ценах у₁, у₂, у₃ наши затраты составят 2у₁ + 4у₂ + 2у₃, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы продукции первого вида. На рынке за единицу первой продукции мы получили бы прибыль 36 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше 2у₁ + 4у₂ + 2у₃  36.

Аналогично, для трех оставшихся видов продукции:

3у₁ + 2у₂ + 8у₃32

4у₁ + 7у₃10

у₁ + 2у₂ 13

Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить 103у₁ + 148у₂ + 158у₃ рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у₁, у₂, у₃, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.

Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок у(у₁, y₂, y₃) минимизирующий общую оценку всех ресурсов f = 103у₁ + 148у₂ + 158у₃ (1)

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

2у₁ + 4у₂ + 2у₃  36

3у₁ + 2у₂ + 8у₃32 (2)

4у₁ + 7у₃10

у₁ + 2у₂ 13

причем оценки ресурсов не могут быть отрицательными y₁ 0, y₂ 0, y₃ 0. (3)

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений (х₁, х₂, х₃, х₄) и (y₁, y₂, y₃) пары двойственных задач необходимо и достаточно выполнение условий

x ₁ (2у₁ + 4у₂ + 2у₃ - 36) = 0 y₁ (2x₁ +3x₂ + 4x₃ + x₄ - 103) = 0

x ₂ (3у₁ + 2у₂ + 8у₃ - 32) = 0 y₂ (4x₁ +2x₂ + 2x₄ - 148) = 0

x ₃ (4у₁ + 7у₃- 10) = 0 y₃ (2x₁ +8x₂ + 7x₃ - 158) = 0 .

x ₄ (у₁ + 2у₂ - 13) = 0

Ранее было найдено, что в решении исходной задачи х₁>0, x₂>0. Поэтому

2y₁ + 4y₂ + 2y₃ - 36 = 0

3y₁ + 2y₂ + 8y₃ - 32 = 0

Если же учесть, что первый ресурс был избыточным и, согласно той же теореме двойственности, ее двойственная оценка равна нулю у₁=0,

то приходим к системе уравнений

4y₂ + 2y₃ - 36 = 0

2y₂ + 8y₃ - 32 = 0

откуда следует у₂=8, у₃=2.

Таким образом, получили двойственные оценки ресурсов у₁=0; у₂=8; у₃=2, (4)

причем общая оценка всех ресурсов равна 1500.

Заметим, что решение (4) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка третьего ресурса у₃=2 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли в 2 единицы.