mathematical-optimization - 线性规划 - 双单纯形变量的含义？

Question

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

我了解解决双重问题的机制 - 我不需要帮助。我无法理解(即使在 Wikipedia 上阅读了它)是 的实际含义。 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 上工作两小时，在 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 处理生产利润最大化，因此 Dual 可以被认为是最小化公司的生产成本。

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

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

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

由于您正在寻找 洞察对偶数 的理解:

一个技巧是减少对偶的维度。 (假设只有一台机器 M1。)现在，制定对偶并尝试理解目标函数和约束。

从“机会成本”的角度思考会有所帮助。如果制造公司不得不租用机器(资源)，它应该支付多少价格/小时？或者，如果有许多其他(有利可图的)产品，将以每小时多少成本将机器分配给 X1 和 X2，而不是制造这些其他产品。

请注意，并非所有对偶都可以轻松“理解”。但是，您可以通过查看原始变量中的相应变量来了解许多双重约束。同样，您可以通过研究相应的原始约束来深入了解对偶变量。