对偶问题（LP Duality）

对偶问题的提出——宅男示例升级版

考虑这样一个问题，一个宅男需要在家里宅一星期（7天），他只喜欢吃乐事薯片和香飘飘奶茶。他的女朋友是一个营养师，可以使用能量、蛋白质这些原材料制作出薯片和奶茶，是的，就这么神奇。所以，这个女生需要先去购买材料才能制作出食物。

假设这个女生从一个原材料公司购买所需要的原材料，这个原材料公司该如何给能量、蛋白质定价来获得最大的收益？

还要补充一下：

1. 这个女生从天猫搜索了一下薯片和奶茶的价位。她希望购买原材料所花费的钱不大于网上的报价（要不然还不如网购呢）
2. 这个女生要根据中国营养学会的推荐（每天需要摄入能量2400KJ，蛋白质75g）给男朋友制作可以满足七天营养需求的食物（可以求出一星期需要摄入能量16800KJ，蛋白质525g）

直接引用上一节使用的图，如下。

对于这个问题，很容易给出线性规划模型（公式），如下。

$$max \text{ } 16800y_1+525y_2$$

$$668y_1+1.5y_2 \leq 6.8$$

$$883y_1+1.2y_2 \leq 2.7$$

$$y_1 \geq 0, y_2 \geq 0$$

可以使用图解法解决，如下图。

可以得出，y1=0，y2=2.25。也就是能量定价为0元，蛋白质定价为2.25元。所以，原材料公司收益：16800_0+525_2.25=1181.25元。

回到上一节的“宅男”问题，求解出购买零食花费的最少的钱为1181.25元。

惊奇的发现，这两个问题的结果是一样的。

对偶问题

可以使用以上的这些公式把原问题转换为对偶问题，当然，也可以把对偶问题转换为原问题。

这里说对偶主要是后面要用到对偶单纯形法。对偶单纯法有什么好处呢？

若保持对偶问题的解是基可行解，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也就得到了最优解。这种方法的优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。

所以，总结来说，单纯形法可以来解决符合标准形式的线性规划问题，对偶单纯形法可以弥补单纯形法的一些缺陷，同样可以帮助我们更好的解决线性规划问题。这是我的理解。

对偶之所以有这些好处，主要在于对偶问题的优良性质，如下图。

-- EOF --