线性规划-对偶单纯形变量的含义？

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 上工作 1 小时，在 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上工作两个小时，在M3上工作2小时，我应该得到至少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 处理生产利润最大化，<双重可以被认为是最小化公司的生产成本。

（有时，考虑一下公司“租赁”机器M1、M2和M3会有所帮助。）如果他们要租用机器，他们最多应该租多少台机器？为每台机器支付 [美元/小时] 并仍然可以盈利地生产 x1 和 x2？

双变量 y1、y2 和 y3 的含义是每小时的拥有/租赁成本。

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

由于您正在寻求深入理解对偶：

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