算法导论自学笔记(6-2)

接上一节,继续我们的线性规划。

对偶问题(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 --