1.6 对偶性及对偶单纯形法.ppt

2-4 对偶性及对偶单纯形法
一线性规划的对偶理论

(资源利用问题)
胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个,椅子销售价格30/个,生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时,油漆工2小时。生产一个椅子需要木工3小时,油漆工1小时。该厂每个月可用木工工时为120小时,油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大?
数学模型
max g = 50x1 + 30x2
. 4x1 + 3x2  120
2x1 + x2  50 ()
x1,x2  0
如果我们换一个角度,考虑另外一种经营问题。假如有一个企业家有一批等待加工的订单,有意利用该家具厂的木工和油漆工资源来加工他的产品。因此,他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他,又使自己付的租金最少?
假设 y1, y2 分别表示每个木工和油漆工工时的租金,则所付租金最小的目标函数可表示为:
min s = 120 y1 + 50 y2
目标函数中的系数 120,50 分别表示可供出租的木工和油漆工工时数。
得到另外一个数学模型:
min s = 120y1 + 50y2
. 4 y1 + 2y2  50
3 y1 + y2  30 ()
y1, y2  0
模型()和模型() 既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据,区别在于模型反映的实质内容是不同的。模型()是站在家具厂经营者立场追求销售收入最大,模型()是则站在家具厂对手的立场追求所付的租金最少。
如果模型()称为原问题,
则模型()称为对偶问题。
任何线性规划问题都有对偶问题,
而且都有相应的意义。
例2 .2 营养配餐问题
假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择,它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小?