接上一节,继续我们的线性规划。
对偶问题(LP Duality)
对偶问题的提出——宅男示例升级版
考虑这样一个问题,一个宅男需要在家里宅一星期(7天),他只喜欢吃乐事薯片和香飘飘奶茶。他的女朋友是一个营养师,可以使用能量、蛋白质这些原材料制作出薯片和奶茶,是的,就这么神奇。所以,这个女生需要先去购买材料才能制作出食物。
假设这个女生从一个原材料公司购买所需要的原材料,这个原材料公司该如何给能量、蛋白质定价来获得最大的收益?
还要补充一下:
- 这个女生从天猫搜索了一下薯片和奶茶的价位。她希望购买原材料所花费的钱不大于网上的报价(要不然还不如网购呢)
- 这个女生要根据中国营养学会的推荐(每天需要摄入能量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 --