Линейное программирование - двойное значение переменной переменной?

Question

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

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

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

Primal:

max z = 3*x1 + 5*x2 

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

     x1, x2 >= 0 

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

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

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

Целевая функция вашего двойного заключается в минимизации Стоимость/час 3 машин (ресурсов).

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

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

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

(Это иногда помогает думать о компании «арендой» машины M1, M2 и M3.) Если они собираются сдавать его в аренду, что самое большее, что они должны платить [$/час] для каждой машины и все еще производят x1 и x2 выгодно?

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

Переменные двойной проблемы y переменные часто называются «Теневые цены» ресурсов.

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

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