线性规划 - 对偶单纯形法中变量的含义是什么？

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元/单位。这些产品是在三台机器M1-M3上生产的。要生产第一个产品，需要在M1上工作一小时，在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上工作1小时和在M3上工作3小时，我至少应该得到3个货币单位的报酬 - 在M2上工作2小时和在M3上工作2小时，我至少应该得到5个货币单位的报酬

但是，我就是无法理解变量y1和y2的含义。当我最终进行最小化时，对偶中的结果z与原始问题中相同（尽管原始问题增加了结果的下限，而对偶则降低了结果的上限），但对偶问题的目标函数包括什么？

- penelope

Answer 1

你的对偶优化函数的目标是最小化三台机器（资源）的成本/小时。

因此，对偶问题的目标函数（4*y1+12*y2+18*y3）可以解读为：

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

由于原问题是最大化生产利润，所以对偶问题可以被理解为最小化公司的生产成本。

（有时候将公司想象成“租用”M1，M2和M3这些机器可能会有所帮助。）如果他们要租用这些机器，每台机器他们应该支付多少美元/小时才能够盈利地制造出x1和x2？

对偶变量y1，y2和y3的含义是每小时拥有/租用成本。

对偶问题中的y变量通常被称为资源的“影子价格”。

由于你正在寻求理解对偶问题的见解：

1. 一个技巧是降低对偶的维度。（想象一下只有一台机器M1。）现在，制定对偶并尝试理解目标函数和约束条件。
2. 以“机会成本”的概念来思考可能会有所帮助。如果制造公司必须租用机器（资源），那么它应该支付多少美元/小时的价格？或者，如果还有许多其他（有利可图的）产品需要制造，机器将被分配到X1和X2而不是制造这些其他产品的成本/小时。
3. 请注意，并非所有的对偶问题都能够轻松“理解”。但是，通过查看原始问题中相应的变量，可以了解许多对偶约束条件。同样地，通过研究相应的原始问题约束条件，可以了解对偶变量的见解。

- Ram Narasimhan