11

我刚刚学习了求解线性程序的单纯形法，我试图理解它的对偶问题代表什么。

我了解解决双重问题的机制——我不需要帮助。我无法得到（即使在Wikipedia上阅读过它）是dual 中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和 2上工作两个小时在M3上几个小时，我应该得到至少 5 个货币单位的报酬

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

4

1 回答 1

12

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

（有时考虑公司“租用”机器M1、M2 和 M3会有所帮助。）如果他们要租用机器，他们应该为每台机器支付 [$/小时] 的最高费用是多少，并且仍然可以制造x1并x2盈利?

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

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

由于您正在寻找了解对偶的洞察力：

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