线性规划的对偶理论与灵敏度分析.ppt

《线性规划的对偶理论与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性规划的对偶理论与灵敏度分析主要内容：了解影子价格的含义。理解线性规划的对偶问题及其性质。深刻理解对偶单纯形法；灵敏度分析的方法和步骤。教学重点与难点：对偶单纯形法；灵敏度分析的方法和步骤。13.1线性规划的对偶问题一、引例例3．1生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才

2、能使每月的销售收入最大？2数学模型maxg=50x1+30x2s.t.4x1+3x2120(3.1)2x1+x250x1,x203如果我们换一个角度，考虑另外一种经营问题。假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？4假设y1,y2分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为：mins=120y1+50y2目标函数中的系数120，50分

3、别表示可供出租的木工和油漆工工时数。5该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益：4y1+2y2503y1+y230y1,y206得到另外一个数学模型：mins=120y1+50y2s.t.4y1+2y250(3.2)3y1+y230y1,y207模型(3.1)和模型(3.2)既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型(3.1)是站在家具厂经营者立场追求销售收入最大，模型(3.2)

4、则是站在家具厂对手的立场追求所付的租金最少。8如果模型(3.1)称为原问题，则模型(3.2)称为对偶问题。任何线性规划问题都有对偶问题，而且都有相应的意义。9例3.2营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？10各种食物的营养成分表11解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minS=14x1+6x2+3x3+2x4s.t.1000x1

5、+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，x3，x40(3.3)12该问题的对偶问题：maxg=3000y1+55y2+800y3s.t.1000y1+50y2+400y314800y1+60y2+200y36900y1+20y2+300y33200y1+10y2+500y32y1，y2，y30(3.4)13该问题的对偶问题(3.4)经济意义可解释为：市场上有一厂商生产三种可代替食品中的热量、蛋白质和钙的营养素，该厂商希

6、望它的产品既有市场竞争力，又能带来最大利润，因此需要构造一个模型来研究定价问题。以上模型的变量为各营养素单位营养量的价格，目标函数反映厂商利润最大的目标，约束条件反映市场的竞争条件，即：用于购买与某种食品营养价值相同的营养素的价格应小于该食品的市场价格。14二、对偶规则原问题一般模型：对偶问题一般模型：maxZ=CXminω=YbAX≤bYA≥CX≥0Y≥015对偶规则原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的技术系数矩阵转置后

7、为对偶问题系数矩阵原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反16原问题对偶问题目标函数maxmin目标函数约束条件m个≤≥=变量n个≥≤无约束价值系数约束条件的右端项变量符号n个≥≤无约束约束条件m个≥≤=约束条件的右端项价值系数.17例3.3写出下列线性规划问题的对偶问题minZ=3x1+2x2-6x3+x52x1+x2-4x3+x4+3x5≥7x1+2x3-x4≤4-x1+3x2-x4+x5=-2x1，x2，x3≥0;x4≤0;x5无限制18maxω=7y1+4y2-2y32y1+y2-y3≤3y1+3y3≤2-4y1+

8、2y2≤-6y1-y2-y3≥03y1+y3=1y1≥0，y2≤0y3无约束19例3.4：写出下列线性规划问题的对偶问题maxS=10x1+x2+2x