运筹学-对偶理论与灵敏度分析.ppt

《运筹学-对偶理论与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学-对偶理论与灵敏度分析.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6讲 对偶理论与灵敏度分析I6.1对偶问题的提出6.2 原问题与对偶问题的对应关系6.1 对偶问题的提出引例：引例：某某企企业业生生产产甲甲、乙乙两两种种产产品品，要要用用A、B、C三三种种不不同同的的原原料料。每每生生产产1吨吨甲甲产产品品，需需耗耗用用三三种种原原料料分分别别为为1，1，0单单位位；生生产产1吨吨乙乙产产品品，需需耗耗用用三三种种原原料料分分别别为为1，2，1单单位位。每每天天原原料料供供应应的的能能力力分分别别为为6，8，3单单位位。又又知知道道每每生生产产1吨吨甲甲产产品品企企业业利利润润为为300元元，每每生生产产1吨吨乙乙产产品品企企业业利润为利润为400元。问：

2、该企业应如何安排生产，使其每天的利润最大。元。问：该企业应如何安排生产，使其每天的利润最大。2设：该企业每天应生产甲产品设：该企业每天应生产甲产品x1吨，乙产品吨，乙产品x2吨吨max x1 0,x2 0s.t.x1+x2 6z=3x1+4x2 x1+2x2 8 x2 33 假假设设该该企企业业决决策策者者现现决决定定不不生生产产甲甲、乙乙产产品品，而而是是将将厂厂里里的的现现有有资资源源外外售售。购购买买方方应应以以什什么么样样的的价价格格来来采采购购每种资源每种资源呢呢？分析问题：分析问题：1.1.购买方给出的价格应该使该企业能够接受；购买方给出的价格应该使该企业能够接受；2.2.购买方应

3、尽可能使自己付出的成本最小。购买方应尽可能使自己付出的成本最小。4以以y1,y2,y3分别表示分别表示A,B,C三种原料的采购价格，三种原料的采购价格，为了能使该企业能够接受，应满足：为了能使该企业能够接受，应满足：把把生生产产1 1吨吨甲甲产产品品所所用用的的原原料料出出让让，所所得得净净收收入入应应不不低低于于生生产产1 1吨吨甲产品获得的利润：甲产品获得的利润：乙产品同理：乙产品同理：采购方付出的总成本：采购方付出的总成本：5所以，这三种原料的价格决策可表示为下列线性规划问题：s.t.6s.t.LP1s.t.LP2生产安排问题资源定价问题一对对偶问题76.2 原问题与对偶问题的对应关系o

4、对偶问题的定义原问题原问题(LP)对偶问题对偶问题(DP)n个决策变量，个决策变量，m个约束条件个约束条件m个决策变量，个决策变量，n个约束条件个约束条件价值系数价值系数C资源常数资源常数b价值系数价值系数bT资源常数资源常数CT系数矩阵系数矩阵A系数矩阵系数矩阵AT8原问题原问题(LP)对偶问题对偶问题(DP)矩阵形式：9s.t.Ps.t.Dyj 表示对第表示对第 j 种资源的定价种资源的定价矩阵形式：矩阵形式：s.t.s.t.max z=CX s.t.AX b X 0 min w=bTY s.t.ATY CT Y 010练习：写出下列问题的对偶问题练习：写出下列问题的对偶问题max Z=4

5、x1+7x2s.t.3x1+5x26x1+2x28x1,x20(P)minW=6y1+8y2s.t.3y1+y245y1+2y27y1,y20(D)11(一一)对称型对偶问题对称型对偶问题其中其中 yi 0（i=1,2,m）称为称为对偶变量对偶变量。变变量量均均具具有有非非负负约约束束，且且约约束束条条件件：当当目目标标函函数数求求极极大大时时均取均取“”号，当目标函数求极小时均取号，当目标函数求极小时均取“”号。号。max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 (P)am1x1+am2x2+amnxn bm

6、 xj 0（j=1,2,n）min w=b1 y1+b2 y2+bm yms.t.a11y1+a21 y2+am1ym c1 a12y1+a22y2 +am2 ym c2 (D)a1ny1+a2ny2+amnym cn yi 0（i=1,2,m）max z=CX s.t.AX b X 0 min w=bTY s.t.ATY CT Y 012(二二)非对称型对偶问题非对称型对偶问题分析：分析：化为对称形式。化为对称形式。max x10,x20,x3无约束无约束s.t.a11x1+a12x2+a13x3 b1z=c1x1+c2x2+c3x3 a31x1+a32x2+a33x3 b3 a21x1+a

7、22x2+a23x3=b2令令maxs.t.13maxs.t.对偶变量对偶变量mins.t.对偶问题：对偶问题：14mins.t.令令mins.t.mins.t.153个个=约约束束条条件件变变 量量mins.t.原问题原问题对偶问题对偶问题目标函数目标函数 maxmax目标函数目标函数 minmin目标函数的系数目标函数的系数约束条件右端常数约束条件右端常数约束条件右端常数约束条件右端常数目标函数的系数目标函数的系数3个个=3个个00无符号限制无符号限制约约束束条条件件变变 量量3个个00无符号限制无符号限制原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）16原问题与对偶问题的对应关系17例6.1：写出下列线性规划问题的对偶问题解：解：设对偶变量为设对偶变量为maxs.t.mins.t.则对偶问题为则对偶问题为18例6.2：写出下列线性规划问题的对偶问题解：解：设对偶变量为设对偶变量为mins.t.maxs.t.则对偶问题为则对偶问题为19练习练习：写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题maxs.t.mins.t.20