线性规划 - 双重单纯变量意义？

Question

我刚学会了解决线性程序的单纯形法,我试图理解它的双重问题代表什么.

我理解解决双重问题的机制 - 我不需要帮助.我无法得到的(甚至在维基百科上阅读之后)是双变量中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台M1-M3机器生产.要生产第一种产品,需要在M1上工作一小时,在M3上工作3小时.要生产第二个,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上的一小时工作和M3上的3小时,我应该得到至少3个钱单位 - 在M2和2 上工作两个小时在M3上的小时,我应该得到至少5个钱单位

但是,我无法围绕y1和y2变量的含义进行思考.当我最终进行最小化时,z中的结果在原始中是相同的(尽管原始增加结果的下限而双重增加上限),但是双重问题的目标函数是什么？的？

Answer 1

Dual的Objective功能是最小化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可以被认为是最小化公司的生产成本.

(有时候会想到公司"租用"机器M1,M2和M3.)如果他们要租用它,他们应该为每台机器支付[$ /小时]的最多,并且仍然可以制造x1并且x2有利可图？

双变量的含义y1, y2, and y3是每小时拥有/租赁成本.

双重问题的y变量通常被称为资源的"影子价格".

因为您正在寻找对双重理解的洞察力:

1. 一个技巧是减少双重的维度.(想象一下,只有一台机器M1.)现在,制定对偶并尝试理解目标函数和约束.
2. 它有助于从"机会成本"的角度思考.如果制造公司不得不租用机器(资源),它应该支付多少价格/小时？或者,如果有许多其他(有利可图的)产品,将按什么成本/小时分配机器X1,X2而不是制造这些其他产品.
3. 请注意,并非所有对偶都可以轻松"理解".但是,通过查看原始对应的变量,您可以了解许多双重约束.同样,通过研究相应的原始约束,您可以深入了解双变量.