对偶问题及对偶单纯形法完整课件

《对偶问题及对偶单纯形法完整课件》由会员分享，可在线阅读，更多相关《对偶问题及对偶单纯形法完整课件（61页珍藏版）》请在装配图网上搜索。

1、第1页Duality Theory 线性规划的对偶问题线性规划的对偶问题 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 对偶单纯形法对偶单纯形法第四章第四章 线性规划的对偶理论线性规划的对偶理论 灵敏度分析灵敏度分析 对偶问题的基本性质对偶问题的基本性质第2页 线性规划的对偶问题线性规划的对偶问题Duality Theory 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 对偶问题的基本性质对偶问题的基本性质第四章第四章 线性规划的对偶理论线性规划的对偶理论第3页例如：例如：平面中矩形的面积与周长的关系平面中矩形的面积与周长的关系周

2、长一定面积最大的矩形是正方形周长一定面积最大的矩形是正方形 : 面积一定周长最短的矩形是正方形面积一定周长最短的矩形是正方形一、对偶问题的提出一、对偶问题的提出 对同一问题从不同角度考虑，有两种对立的描述。对同一问题从不同角度考虑，有两种对立的描述。例例1 1、应如何安排生产计划，使一天的总利润最大？、应如何安排生产计划，使一天的总利润最大？ 某企业生产甲、乙两种产品，要用某企业生产甲、乙两种产品，要用A、B、C三种不同的原料。每生产三种不同的原料。每生产1吨甲产品，需耗用三种原料分别为吨甲产品，需耗用三种原料分别为1，1，0单位；生产单位；生产1吨乙产品，需耗用三吨乙产品，需耗用三种原料分别

3、为种原料分别为1，2，1单位。每天原料供应的能力分别为单位。每天原料供应的能力分别为6，8，3单位。又知单位。又知道每生产道每生产1吨甲产品企业利润为吨甲产品企业利润为300元，每生产元，每生产1吨乙产品企业利润为吨乙产品企业利润为400元。元。第4页例例1 1、应如何安排生产计划，使一天的总利润最大？、应如何安排生产计划，使一天的总利润最大？max x1 0 , x2 0s.t. x1 + x2 6z = 3x1 + 4x2 x1 + 2x2 8 x2 3设设 xj 表示第表示第 j 种产品每天的产量种产品每天的产量 假设该企业决策者决定不生产甲、乙产品，而是将假设该企业决策者决定不生产甲、

4、乙产品，而是将厂里的现有资源外售。决策者应怎样制定每种资源的收厂里的现有资源外售。决策者应怎样制定每种资源的收费标准才合理？费标准才合理？第5页例例1 1、应怎样制定收费标准才合理？、应怎样制定收费标准才合理？设设 yj 表示第表示第 j 种原料的收费单价种原料的收费单价 分析问题：分析问题： 1 1、出让每种资源的收入不能低于自己生产时的可获利润；、出让每种资源的收入不能低于自己生产时的可获利润； 2 2、定价不能太高，要使对方能够接受。、定价不能太高，要使对方能够接受。 把生产一吨甲产品所用的原料出让，所得净收入应不低于生产一吨把生产一吨甲产品所用的原料出让，所得净收入应不低于生产一吨甲产

5、品的利润：甲产品的利润： 乙产品同理：乙产品同理：123yy12324yyy 把企业所有原料出让的总收入：把企业所有原料出让的总收入：123683wyyy只能在满足只能在满足所有产品的所有产品的利润的条件下利润的条件下, ,其总收入其总收入尽可能少尽可能少, ,才能成交才能成交. .123min683wyyy12123123 324,0yyyyyy yys.t.第6页一、对偶问题的提出一、对偶问题的提出 任何一个求极大的线性规划问题都有一个求极小的线性任何一个求极大的线性规划问题都有一个求极小的线性规划问题与之对应，反之亦然规划问题与之对应，反之亦然. 把其中一个叫原问题，则另一个就叫做它的对

6、偶问题，把其中一个叫原问题，则另一个就叫做它的对偶问题，这一对互相联系的两个问题就称为一对对偶问题。这一对互相联系的两个问题就称为一对对偶问题。 12max34zxx1212212 628 3,0 xxxxxx xs.t.LP1123min683wyyy12123123 324,0yyyyyy yys.t.LP2原问题（原问题（P）对偶问题（对偶问题（D）第7页二、原问题与对偶问题的对应关系二、原问题与对偶问题的对应关系12max34zxx1212212 628 3,0 xxxxxx xs.t.P123min683wyyy12123123 324,0yyyyyy yys.t.Dyj 表示对第表

7、示对第 j 种资源的估价种资源的估价321yyy矩阵形式：矩阵形式：12max(3 4)xzx12121161280130 xxxx s.t.123min6 8 3ywyy1231231 10312140yyyyyy s.t. max z=CX s.t. AX b X 0 min w =bTY s.t. ATY CT Y 0第8页( (一一) )对称型对偶问题对称型对偶问题其中其中 yi 0 （i = 1,2,m）称为）称为对偶变量对偶变量。 变量均具有非负约束，且约束条件：当目标函数求极大时变量均具有非负约束，且约束条件：当目标函数求极大时均取均取“”号，当目标函数求极小时均取号，当目标函数

8、求极小时均取“”号。号。max z = c1x1 + c2x2 + + cnxns.t. a11x1 + a12x2 + + a1nxn b1 a21x1 + a22x2 + + a2nxn b2 (P) am1x1 + am2x2 + + amnxn bm 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. A

9、X b X 0 min w =bTY s.t. ATY CT Y 0第9页( (二二) )非对称型对偶问题非对称型对偶问题分析：分析：化为对称形式。化为对称形式。max x10, x20, x3无约束无约束s.t. a11x1 + a12x2 + a13x3 b1z = c1x1 + c2x2 + c3x3 a31x1 + a32x2 + a33x3 b3 a21x1 + a22x2 + a23x3 = b2令令33333 (0,0)xxxxx22xx ，11 112 213 313 31a xa xa xa xb1233,0 x x x x1 12 23 33 3zcxc xc xc x21

10、 122 223 323 32a xa xa xa xb31 132 233 333 33a xa xa xa xb31 132 233 333 33a xa xa xa xb21 122 223 323 32a xa xa xa xb21 122 223 323 32a xa xa xa xb21 122 223 323 32a xa xa xa xbmaxs.t.第10页13 12322323333a ya ya ya yc( (二二) )非对称型对偶问题非对称型对偶问题11 112 213 313 31a xa xa xa xb1233,0 x x x x1 12 23 33 3zcxc

11、 xc xc x31 132 233 333 33a xa xa xa xb21 122 223 323 32a xa xa xa xb21 122 223 323 32a xa xa xa xb21 122 223 323 32a xa xa xa xbmaxs.t.对偶变量对偶变量1y3y2y2y11 121 221 231 31a ya ya ya yc1223,0y y y y 1 1222233wb yb yb yb y13 12322323333a ya ya ya yc12 12222223232a ya ya ya ycmins.t.对偶问题：对偶问题：第11页12 12223

12、232a ya ya yc12 12223232a ya ya yc( (二二) )非对称型对偶问题非对称型对偶问题13 12322323333a ya ya ya yc11 121 221 231 31a ya ya ya yc1223,0y y y y 1 1222233wb yb yb yb y13 12322323333a ya ya ya yc12 12222223232a ya ya ya ycmins.t.令令33yy222yy y- ，13 12323333a ya ya yc11 121231 31a ya ya yc10y ，1 12233w byb yb y13 1232

13、3333a ya ya ycmins.t.2y 无约束，30y 12 12223232a ya ya yc13 12323333a ya ya yc11 121231 31a ya ya yc10y ，1 12233w byb yb ymins.t.2y 无约束，30y 13 12323333a ya ya yc第12页3个个=约束条件约束条件变变 量量( (二二) )非对称型对偶问题非对称型对偶问题12 12223232a ya ya yc13 12323333a ya ya yc11 121231 31a ya ya yc10y ，1 12233w byb yb ymins.t.2y 无约

14、束，30y 原问题原问题对偶问题对偶问题目标函数目标函数 maxmax目标函数目标函数 minmin目标函数的系数目标函数的系数约束条件右端常数约束条件右端常数约束条件右端常数约束条件右端常数目标函数的系数目标函数的系数3个个=3个个00无符号限制无符号限制约束条件约束条件变变 量量3个个00无符号限制无符号限制321yyy原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）第13页3个个=约束条件约束条件变变 量量( (一一) )对称型对偶问题对称型对偶问题原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数 maxmax目标函数目标函

15、数 minmin目标函数的系数目标函数的系数约束条件右端常数约束条件右端常数约束条件右端常数约束条件右端常数目标函数的系数目标函数的系数3个个=3个个00无符号限制无符号限制约束条件约束条件变变 量量3个个00无符号限制无符号限制12max34zxx1212212 628 3,0 xxxxxx xs.t.123min683wyyy12123123 324,0yyyyyy yys.t.2个个2个个第14页二、原问题与对偶问题的对应关系二、原问题与对偶问题的对应关系第15页例例2 2、写出下述线性规划问题的对偶问题、写出下述线性规划问题的对偶问题解：解：设对偶变量为设对偶变量为123435xxxx

16、12340,0,xx xx,无约束1234235zxxxxmaxs.t.1342 24xxx234 6xxx122 2yy10,y 123546wyyymins.t.123,y y y，则对偶问题为则对偶问题为20,y 3y 无约束13 3yy123325yyy123 1yyy第16页例例3 3、写出下述线性规划问题的对偶问题、写出下述线性规划问题的对偶问题解：解：设对偶变量为设对偶变量为123435xxxx12340,0,xx xx,无约束1234235zxxxxmins.t.1342 24xxx234 6xxx122 2yy10,y 123546wyyymaxs.t.123,y y y，则

17、对偶问题为则对偶问题为20,y 3y 无约束13 3yy123325yyy123 1yyy第17页练习、写出下述线性规划问题的对偶问题练习、写出下述线性规划问题的对偶问题1234235zxxxxmaxs.t.1234124123412344 32532 74234 60,0,xxxxxxxxxxxxxxx无约束12343234zxxxxmins.t.123423412341234 2343 345237420,0,xxxxxxxxxxxxxxx ,无约束第18页 对偶问题的基本性质对偶问题的基本性质Duality Theory 线性规划的对偶问题线性规划的对偶问题 对偶问题的经济解释对偶问题的

18、经济解释影子价格影子价格 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析第二章第二章 线性规划的对偶理论线性规划的对偶理论第19页对偶问题的基本性质对偶问题的基本性质对称性对称性弱对偶性弱对偶性无界性无界性最优性最优性原问题与对偶问题单纯形表间的性质原问题与对偶问题单纯形表间的性质互补松弛性互补松弛性强对偶性强对偶性第20页对偶问题的基本性质对偶问题的基本性质 max z=CX s.t. AX b X 0 min w =bTY s.t. ATY CT Y 0njjjxcz1max1 1,0 1,nijjijja xbimxjn（）（）s.t.（P）1minmiiiwby1 1,0 1,miji

19、jiia ycjnyim（）（）s.t.（D）第21页 对偶问题对偶问题1、对称性、对称性定理：对偶问题的对偶是原问题。定理：对偶问题的对偶是原问题。对偶问题对偶问题max z = CXs.t. AX b X 0max w = bTYs.t. ATY CTY 0 min w = bTYs.t. ATY CT Y 0min z = CXs.t. AX b X 0第22页2、弱对偶性、弱对偶性11nmjjiijic xb y定理：设定理：设 和和 分别是原问题（分别是原问题（P P）和其对偶问题（和其对偶问题（D D）的可行解，则恒有）的可行解，则恒有(1, )jxjn(1,)iy im111()

20、nnmjjijijjjic xa yx 111()mmniiijjiiijb ya xy 11mnijjiija x y第23页2、弱对偶性、弱对偶性11nmjjiijic xb y定理：设定理：设 和和 分别是原问题（分别是原问题（P P）和其对偶问题（和其对偶问题（D D）的可行解，则恒有）的可行解，则恒有(1, )jxjn(1,)iy im推论：原问题任一可行解的目标函数值是其对偶问题目标推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。是其原问题目标函数值的上

21、界。第24页3、无界性、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解，定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。则另一个问题无可行解。原问题有可行解但目标函数值无界原问题有可行解但目标函数值无界对偶问题无可行解对偶问题无可行解对偶问题有可行解但目标函数值无界对偶问题有可行解但目标函数值无界原问题无可行解原问题无可行解推论：原问题任一可行解的目标函数值是其对偶问题目标推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。是其原问题

22、目标函数值的上界。第25页3、无界性、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解，定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。则另一个问题无可行解。原问题有无界解原问题有无界解对偶问题无可行解对偶问题无可行解推论：原问题任一可行解的目标函数值是其对偶问题目标推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。是其原问题目标函数值的上界。可能是无可行解可能是无可行解推论推论1 1：在互为对偶的两个问题中，若一个问题无可行解，：在

23、互为对偶的两个问题中，若一个问题无可行解，则另一个问题或具有无界解或无可行解。则另一个问题或具有无界解或无可行解。第26页3、无界性、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解，定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。则另一个问题无可行解。推论推论1 1：在互为对偶的两个问题中，若一个问题无可行解，：在互为对偶的两个问题中，若一个问题无可行解，则另一个问题或具有无界解或无可行解。则另一个问题或具有无界解或无可行解。推论推论2 2：在互为对偶的两个问题中，若一个问题有可行解，：在互为对偶的两个问题中，若一个问题有可行解，另一个问题无可行解，则可行的

24、问题无界。另一个问题无可行解，则可行的问题无界。无界解无界解无可行解无可行解无可行解无可行解无界解无界解对偶问题对偶问题原问题原问题第27页例例1 1、利用对偶理论证明问题无界（无最优解）、利用对偶理论证明问题无界（无最优解）解：解：设对偶变量为设对偶变量为1231231233221,0 xxxxxxx x x122zxxmaxs.t.12321yy12,0y y 122wyymins.t.12,y y则对偶问题为则对偶问题为12 2yy12 0yy由由 知，知，12,0y y 第一个约束第一个约束可知对偶问题无可知对偶问题无条件不成立，条件不成立，可行解。可行解。易知易知(0, 0, 0)T

25、 是原问题的一是原问题的一个可行解，故原问题可行。个可行解，故原问题可行。由无界性定理可知，原问题由无界性定理可知，原问题有无界解，即无最优解。有无界解，即无最优解。对偶问题对偶问题不可行不可行原问题无界原问题无界或不可行或不可行无界无界 不可行不可行第28页练习、证明下列线性规划问题无最优解练习、证明下列线性规划问题无最优解13123123 423,0 xxxxxx x x123zxxxmins.t.12 1yy12,0y y 1243wyymaxs.t.12yy2 1y1221yy 对偶问题对偶问题原问题的一个可行解：原问题的一个可行解：4,0,0T5,1,0T对偶问题不可行：对偶问题不可

26、行：找矛盾找矛盾12 1yy1221yy223y 2 1y21y 第29页4、最优性、最优性11nmjjiijic xb y定理：设定理：设 和和 分别是原问题（分别是原问题（P P）和其对偶问题（和其对偶问题（D D）的可行解，且有）的可行解，且有 (1, )jxjn (1,)iy im则则 和和 分别是原问题（分别是原问题（P P）和其对）和其对偶问题（偶问题（D D）的最优解。）的最优解。 (1, )jxjn (1,)iy im*11nnjjjjjjc xc x设设 和和 分别是分别是P和和D的的最优解：最优解：*(1, )jxjn*(1,)iyim*11mmiiiiiib yb y因此

27、因此*1111nnmmjjjjiiiijjiic xc xb yb y第30页5、互补松弛性、互补松弛性定理：设定理：设 和和 分别是原问题和其分别是原问题和其对偶问题的最优解，对偶问题的最优解，*(1, )jxjn*(1,)iyim*1nijjija xb若对偶变量若对偶变量 ，则原问题相应的约束条件，则原问题相应的约束条件*0iy若约束条件若约束条件 ，则相应的对偶变量，则相应的对偶变量*0iy*1nijjija xb第31页5、互补松弛性、互补松弛性定理：设定理：设 和和 分别是原问题和其分别是原问题和其对偶问题的最优解，对偶问题的最优解，*(1, )jxjn*(1,)iyim*1nij

28、jija xb若对偶变量若对偶变量 ，则原问题相应的约束条件，则原问题相应的约束条件*0iy若约束条件若约束条件 ，则相应的对偶变量，则相应的对偶变量*0iy*1nijjija xb*111()nnmjjijijjjic xa yx *111()mmniiijjiiijb ya xy *11nmjjiijic xb y*111()mmniiijjiiijb ya xy *11()0mnijjiiija xb y 第32页5、互补松弛性、互补松弛性定理：设定理：设 和和 分别是原问题和其分别是原问题和其对偶问题的最优解，对偶问题的最优解，*(1, )jxjn*(1,)iyim*1nijjija

29、xb若对偶变量若对偶变量 ，则原问题相应的约束条件，则原问题相应的约束条件*0iy若约束条件若约束条件 ，则相应的对偶变量，则相应的对偶变量*0iy*1nijjija xb*1nijjija xb若若 ，则，则*0iy若若 ，则，则*0iy*1nijjija xb*1mijijia yc若若 ，则，则*0jx若若 ，则，则*0jx*1mijijia yc第33页例例2 2、利用互补松弛定理求最优解、利用互补松弛定理求最优解123123123 2102216 ,0 xxxxxxx x x12334zxxxmaxs.t.已知原问题的最优解是已知原问题的最优解是*(6,2,0)TX求对偶问题的最优解

30、。求对偶问题的最优解。解：解：设对偶变量为设对偶变量为1223yy12,0y y 121016wyymins.t.12,y y则对偶问题为则对偶问题为12224yy12 1yy设对偶问题的最优解为设对偶问题的最优解为*12(,) ,TyyY因因*12,0,xx 由互补松弛性知由互补松弛性知*1223yy*12224yy解方程组得解方程组得*121,1,yy故对偶问题的最优解为故对偶问题的最优解为*(1,1) ,TY*26.w第34页例例3 3、利用互补松弛定理求最优解、利用互补松弛定理求最优解已知原问题的最优解是已知原问题的最优解是12312312312323523 61 40,0,xxxxx

31、xxxxxxx无约束12343zxxxmaxs.t.*(0,0,4)TX求对偶问题的最优解。求对偶问题的最优解。对偶变量为对偶变量为123231yyy1230,0,yyy无约束12324wyyymins.t.123,y y y则对偶问题为则对偶问题为1233 4yyy123563yyy设对偶问题的最优解为设对偶问题的最优解为*123(,) ,TyyyY将将 代入原问题约束条件得代入原问题约束条件得*X解：解：*123*123*1232352023 6241 44xxxxxxxxx 由互补松弛性知由互补松弛性知*120,yy又又*123563yyy故对偶问题的最优解为故对偶问题的最优解为*(0,

32、0,3) ,TY*12.w得得*33,y 第35页例例4 4、利用互补松弛定理求最优解、利用互补松弛定理求最优解已知其对偶问题的最优解是已知其对偶问题的最优解是1234512345 23423 30,1,2,5jxxxxxxxxxxxj1234523523zxxxxxmins.t.*4 3( , )5 5TY求原问题的最优解。求原问题的最优解。对偶问题为对偶问题为设原问题的最优解为设原问题的最优解为*,X解：解：1243wyymins.t.121212121212 22 (1) 3 (2)235 (3) 2 (4) (5)3 3 ,0yyyyyyyyyyyy将将 代入原问题约束条件得：代入原问

33、题约束条件得：*Y(2)、(3)、(4)为严格不等式为严格不等式由互补松弛性知由互补松弛性知*2340,xxx又因又因*12,0,yy 由互补松弛性知由互补松弛性知*12345*12345 23423 3xxxxxxxxxx得得*151,xx故原问题最优解为故原问题最优解为*(1,0,0,0,1) ,TX*5.z第36页6、强对偶性、强对偶性（对偶定理）（对偶定理）定理：若原问题有最优解，则其对偶问题也一定具有最优定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。解，且目标函数的最优值相等。11max0nmjjsijizc xx1 1,0,0 1,nijjsiijj

34、sia xxbimxxjn（）（）s.t.用单纯形法求原问题的最优解：用单纯形法求原问题的最优解：第37页jc BC基bmjjcz11max0nmjjsijizc xx1 1,0,0 1,nijjsiijjsia xxbimxxjn（）（）s.t.1ckcnc00000nc1sx1csmx1blbmb1xkxnx1sxslxsmx10000101011a1 la1ma1kalkamka1nalnamnakcib*iy0001slx01mjjjjiijjjiczccacBC P第38页jc BC基bmjjcz1ckcnc00000nc1sx1csmx1blbmb1xkxnx1sxslxsmx10

35、000101011a1 la1ma1kalkamka1nalnamnakcib*iy0001slx0非基变量非基变量基变量基变量XsXIAjjcz0C基变量基变量 基变量基变量 基可基可 系数系数 行解行解 0 Xs bXB XNB NCB CN第39页 XB I 0CB CNB NXB XN单纯形法计算的矩阵描述单纯形法计算的矩阵描述非基变量非基变量基变量基变量XsIjjcz0基变量基变量 基变量基变量 基可基可 系数系数 行解行解 0 Xs b基变量基变量非基变量非基变量XBjjcz基变量基变量 基变量基变量 基可基可 系数系数 行解行解 CNCBB-1N B-1N B-1XN XsB-1

36、bCB进行初等进行初等行变换行变换CBB-1 若若CNCBB-1N 0CBB-1 0 最优解最优解X*= B-1bB-1存在存在第40页6、强对偶性、强对偶性（对偶定理）（对偶定理） min w =bTY s.t. ATY CT Y 0 若若CNCBB-1N 0CBB-1 0 最优解最优解X*= B-1b令令YT= CBB-1，则有，则有CNYT N 0， Y 0因因CBYTB = 0，故故 CYT A 0，即即AT Y CT ，说明说明Y是是D的可行解的可行解 max z=CX s.t. AX b X 0此时目标函数值此时目标函数值w =bTY=YTb= CBB-1b原问题的最优值原问题的最

37、优值 z= CB-1b= CBB-1b由最优性定理知，由最优性定理知，Y是是D的最优解。的最优解。定理：若原问题有最优解，则其对偶问题也一定具有最优定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。解，且目标函数的最优值相等。第41页6、强对偶性、强对偶性（对偶定理）（对偶定理）推论：若一对对偶问题都有可行解，则它们都有最优解，推论：若一对对偶问题都有可行解，则它们都有最优解，且目标函数的最优值必相等。且目标函数的最优值必相等。定理：若原问题有最优解，则其对偶问题也一定具有最优定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。解，且目标函

38、数的最优值相等。 互为对偶的两个问题，只会出现以下三种关系：互为对偶的两个问题，只会出现以下三种关系： 都有最优解，且最优值相等都有最优解，且最优值相等 一个有无界解，另一个无可行解；一个有无界解，另一个无可行解； 两个都无可行解。两个都无可行解。*11nmjjiijizc xb yw第42页判断下列说法是否正确，为什么？判断下列说法是否正确，为什么？1 1、如果线性规划问题存在可行解，则其对偶问题也一定、如果线性规划问题存在可行解，则其对偶问题也一定存在可行解。存在可行解。2 2、如果线性规划问题的对偶问题无可行解，则原问题也、如果线性规划问题的对偶问题无可行解，则原问题也一定无可行解。一定

39、无可行解。3 3、如果线性规划问题的原问题和对偶问题都具有可行解，、如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划一定具有有限最优解。则该线性规划一定具有有限最优解。第43页对偶问题的基本性质对偶问题的基本性质一个问题一个问题maxmax另一问题另一问题minmin应用应用有最优解有最优解有最优解有最优解强对偶性强对偶性无界解无界解（有可行解）（有可行解）无可行解无可行解无界性无界性（证无最优解）（证无最优解）无可行解无可行解无界解无界解（有可行解）（有可行解）已知最优解已知最优解求最优解求最优解互补松弛性互补松弛性第44页7、原问题与对偶问题单纯形表间的性质？、原问题与对偶问题

40、单纯形表间的性质？ XB I 0CB CNB NXB XN非基变量非基变量基变量基变量XsIjjcz0基变量基变量 基变量基变量 基可基可 系数系数 行解行解 0 Xs b基变量基变量非基变量非基变量XBjjcz基变量基变量 基变量基变量 基可基可 系数系数 行解行解 CNCBB-1N B-1N B-1XN XsB-1bCBYT= CBB-1CBB-1 第45页Duality Theory 线性规划的对偶问题线性规划的对偶问题 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 对偶问题的基本性质对偶问题的基本性质第二章第二章 线性规划的对偶理

41、论线性规划的对偶理论第46页 第一步：找到一个满足最优检验的初始第一步：找到一个满足最优检验的初始基本解；基本解； 第二步：检验当前解是否可行。若可行第二步：检验当前解是否可行。若可行，已得到最优，否则转入下一步。，已得到最优，否则转入下一步。 第三步：选择第三步：选择b最小一行的变量作为换出最小一行的变量作为换出变量变量 第四步：换入变量第四步：换入变量mincj-zj/aij(负数和零负数和零不参与比较不参与比较) 第五步：迭代运算，到第二步。第五步：迭代运算，到第二步。对偶单纯形法对偶单纯形法第47页对偶单纯形法NoImage Max z=-6x1-3x2-2x3例：例：第48页cj-6

42、-3-2000cBxBbx1x2x3x4x5x60 x4-20-1-1-11000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001zj000000cj-zj-6-3-2000对偶单纯形法找到一个满足最优检验的初始基本解找到一个满足最优检验的初始基本解检验当前解不可行，选择检验当前解不可行，选择b最小一行的变量作为换出变量；最小一行的变量作为换出变量；换入变量换入变量mincj-zj/aij第49页cj-6-3-2000cBxBbx1x2x3x4x5x6-2x320111-1000 x5-1-1/4-1/40-1/4100 x610100-101zj-2-2-2200cj

43、-zj-4-10-200对偶单纯形法检验当前解不可行，选择检验当前解不可行，选择b最小一行的变量作为换出变量；最小一行的变量作为换出变量；换入变量换入变量mincj-zj/aij第50页cj-6-3-2000cBxBbx1x2x3x4x5x6-2 x3 16001-240-3 x2 41101-400 x6 10-100-101zj-3-3-2140cj-zj-300-1-40对偶单纯形法第51页 对偶问题的经济解释对偶问题的经济解释影子价格影子价格Duality Theory 线性规划的对偶问题线性规划的对偶问题 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 对偶问题的基本性质对偶问题的基

44、本性质第二章第二章 线性规划的对偶理论线性规划的对偶理论第52页 bi 代表第代表第i种资源的拥有量；种资源的拥有量；yi*代代表在资源最优利用条件下对第表在资源最优利用条件下对第i种资种资源的单位估价。这种估价不是资源源的单位估价。这种估价不是资源的市场价格，而是根据资源在生产的市场价格，而是根据资源在生产中作出的贡献而作的估价。中作出的贡献而作的估价。 一、影子价格的概念一、影子价格的概念设设 xj 表示第表示第 j 种产品每天的产量种产品每天的产量设设 yj 表示第表示第 j 种原料的收费单价种原料的收费单价 由对偶定理知当由对偶定理知当P问题求得问题求得最优解最优解X*时，时，D问题也

45、得到最问题也得到最优解优解Y*，且有，且有*11nmjjiijizc xb yw影子价格影子价格第53页若若 ，则，则*0iy*1nijjija xb*1nijjija xb若若 ，则，则*0iy当某个右端常数当某个右端常数bi bi+1时时一、影子价格的概念一、影子价格的概念*1miiizb y由由 得得*iizyb说明说明 的值相当于在资源得到最优的值相当于在资源得到最优利用的生产条件下，利用的生产条件下， 每增加一个每增加一个单位时目标函数单位时目标函数z的增量的增量* * *1 1ii m mz b yb yb y * *izy*11(1)iimmzb ybyb y*1 1iimmib

46、 yb yb yy3x4边际价格边际价格说明若某资源说明若某资源 未被充分利用，未被充分利用，则该种资源的影子价格为则该种资源的影子价格为0 0；* *izy若某资源的影子价格不为若某资源的影子价格不为0 0，则说，则说明已有资源在已消耗完毕。明已有资源在已消耗完毕。第54页二、在经营管理中的应用二、在经营管理中的应用1x4x5x32xjc BC( 4 ,0 ,0 )bjjczm210( 4 ,4 ,0 )110111 1002x04201x45x1000101 21 0110213102y1* = 2y2* = 1y3* = 0Y*T= CBB-1CBB-1 第55页二、在经营管理中的应用二

47、、在经营管理中的应用y1* = 2y2* = 1y3* = 0若原料若原料A A增加增加1 1单位，该厂按最优计划安排生产可多获利单位，该厂按最优计划安排生产可多获利200200元；元；若原料若原料B B增加增加1 1单位，可多获利单位，可多获利100100元元; ;原料原料C C本已剩余，再增加不会带来收益。本已剩余，再增加不会带来收益。1 1、指示企业内部挖潜的方向、指示企业内部挖潜的方向影子价格能说明增加哪种资源对增加经济效益最有利影子价格能说明增加哪种资源对增加经济效益最有利 第56页二、在经营管理中的应用二、在经营管理中的应用y1* = 2y2* = 1y3* = 02 2、在企业经

48、营决策中的作用、在企业经营决策中的作用当某种资源的影子价当某种资源的影子价格高于市场价格时：格高于市场价格时：当某种资源的影子价当某种资源的影子价格低于市场价格时：格低于市场价格时： 企业经营决策者可通过把本企业资源的影子价格与当时企业经营决策者可通过把本企业资源的影子价格与当时的市场价格进行比较，决定资源的买卖，以获取较大利润。的市场价格进行比较，决定资源的买卖，以获取较大利润。买进买进卖出卖出特别是影子价特别是影子价格为零时格为零时 第57页二、在经营管理中的应用二、在经营管理中的应用y1* = 2y2* = 1y3* = 03 3、在新产品开发决策中的应用、在新产品开发决策中的应用 利用

49、影子价格，通过分析新产品使用资源的经济效果，利用影子价格，通过分析新产品使用资源的经济效果，以决定新产品是否应该投产。以决定新产品是否应该投产。 假设该企业计划生产一类新产品，单件消耗三种原料的数假设该企业计划生产一类新产品，单件消耗三种原料的数量为（量为（2,3,22,3,2），则新产品的单位利润必须大于），则新产品的单位利润必须大于 2 22 + 12 + 13 + 03 + 02 = 72 = 7（百元）（百元）才能增加公司的收益，否则生产是不合算的。才能增加公司的收益，否则生产是不合算的。 第58页二、在经营管理中的应用二、在经营管理中的应用y1* = 2y2* = 1y3* = 04

50、 4、分析现有产品价格变动对资源紧缺情况的影响、分析现有产品价格变动对资源紧缺情况的影响 若甲产品提价，单位利润增至若甲产品提价，单位利润增至4 4，则影子价格改变，由，则影子价格改变，由Y*T= CBB-11说明如果甲产品提价的话，资源说明如果甲产品提价的话，资源A将变得更紧俏将变得更紧俏. . 第59页二、在经营管理中的应用二、在经营管理中的应用y1* = 2y2* = 1y3* = 05 5、分析工艺改变后对资源节约的收益、分析工艺改变后对资源节约的收益 若企业革新技术，改进工艺过程后使资源若企业革新技术，改进工艺过程后使资源A能节约能节约2%2%，则，则带来的经济收益每天将是带来的经济

51、收益每天将是 2 26 62% = 0.242% = 0.24（百元）（百元）第60页二、在经营管理中的应用二、在经营管理中的应用y1* = 2y2* = 1y3* = 0注意注意: :1 1、以上分析都是在最优基不变的条件下进行的、以上分析都是在最优基不变的条件下进行的2 2、应对影子价格有更为广义的理解、应对影子价格有更为广义的理解 若增加产量若增加产量约束约束 x1+ x2 40：产量不超过市场需求量产量不超过市场需求量若若y4*较大，则说明扩大销路能比增加资源带来更大的经济效益较大，则说明扩大销路能比增加资源带来更大的经济效益 Y*T= CBB-1第61页Duality Theory 线性规划的对偶问题线性规划的对偶问题 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 对偶问题的基本性质对偶问题的基本性质第二章第二章 线性规划的对偶理论线性规划的对偶理论