Линейное программирование - значения двойных симплексных переменных?

Question

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

Я понимаю механизм решения двойной задачи - мне не нужна помощь стот.Чего я не могу получить (даже после прочтения об этом в Wikipedia ), так это фактических значений переменных y в двойственном .

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

Первичное:

max z = 3*x1 +  5*x2

subject to:
          x1          <=  4
                2*x2  <= 12
        3*x1 +  2*x2  <= 18

        x1, x2 >= 0

В основной задаче x1 и x2 - это количество продуктов A и B , которые должны быть произведены, 3 и 5 - это их отпускные цены соответственно.Продукция выпускается на 3 станках М1-М3 .Для производства первого продукта требуется час работы на M1 и 3 часа на M3 .Для изготовления второго необходимо два часа работы на M2 и M3 .Машины M1, M2, M3 могут работать максимум 4, 12 и 18 часов соответственно.Наконец, я не могу произвести отрицательное количество какого-либо из продуктов.

Теперь я поставил двойную задачу:

min z = 4*y1 + 12*y2 + 18*y3

subject to:
          y1         +  3*y3 >= 3
                  y2 +  2*y3 >= 5

          y1, y2, y3 >= 0 

Теперь единственное, что я могу понять, эточто ограничения означают: - за час работы на M1 и 3 часа на M3 , мне должны заплатить не менее 3 денежных единиц - за два часа работы на M2 и 2 часа на M3 , мне должны заплатить как минимум 5 денежных единиц

Но я просто не могу понять, что означает y1 и y2 переменные.Когда я наконец выполняю минимизацию, результат в z такой же в первичном (хотя первичный в увеличении нижней границы результата, в то время как двойное - в уменьшении верхней границы), но что делает цельФункция двойной задачи состоит из?

Answer 1

Цель вашего Dual - минимизировать стоимость / час для 3 машин (ресурсов) .

Таким образом, целевая функция Dual (4*y1 + 12*y2+ 18*y3) может быть прочитана как:

Minimize 4*(cost/hour of Machine1) + 12*(cost/hour of M2) + 18*(cost/hr of M3)

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

(Иногда это помогает думать о компании "сдающей в аренду" машины М1, М2 и М3 .) Если они собираются арендовать ее, что самое большее, что они стоит ли платить [$ / час] за каждую машину и при этом производить x1 и x2 с прибылью?

Значение ваших двойных переменных y1, y2, and y3 - почасовые расходы на владение / аренду.

Переменные двойной проблемы y часто называют "теневыми ценами" ресурсов.

Поскольку вы ищете понимание понимания дуалов :

1. Один трюк - уменьшить размерность дуала. (Представьте, что была только одна Машина M1 .) Теперь сформулируйте двойственное и попытайтесь понять целевую функцию и ограничения.
2. Это помогает думать в терминах «альтернативных издержек». Если производственная фирма должна была арендовать машины (ресурсы), какую цену / час она должна заплатить? В качестве альтернативы, если было много других (прибыльных) продуктов, по какой цене / час машины будут выделены на X1 и X2 вместо производства этих других продуктов.
3. Обратите внимание, что не все дуалы можно легко понять. Однако вы можете получить представление о многих двойственных ограничениях, взглянув на соответствующую переменную в основном. Точно так же вы можете получить представление о двойной переменной, изучив соответствующее основное ограничение.