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

1、Duality TheoryDuality Theory 线性规划的对偶问题线性规划的对偶问题 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 对偶单纯形法对偶单纯形法第四章第四章 线性规划的对偶理论线性规划的对偶理论 灵敏度分析灵敏度分析 对偶问题的基本性质对偶问题的基本性质2022-9-291 线性规划的对偶问题线性规划的对偶问题Duality TheoryDuality Theory 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 对偶问题的基本性质对偶问题的基本性质第四章第四章 线性规划的对偶理论线性规划的对偶理论2022-9

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

3、种原料分别为1 1，1 1，0 0单位；生产单位；生产1 1吨乙产品，需耗用三吨乙产品，需耗用三种原料分别为种原料分别为1 1，2 2，1 1单位。每天原料供应的能力分别为单位。每天原料供应的能力分别为6 6，8 8，3 3单位。又单位。又知道每生产知道每生产1 1吨甲产品企业利润为吨甲产品企业利润为300300元，每生产元，每生产1 1吨乙产品企业利润为吨乙产品企业利润为400400元。元。2022-9-293例例1 1、应如何安排生产计划，使一天的总利润最大？、应如何安排生产计划，使一天的总利润最大？maxmax x x1 1 0,0,x x2 2 0 0s.t.s.t.x x1 1+x

4、x2 2 6 6z z=3=3x x1 1+4+4x x2 2 x x1 1+2+2x x2 2 8 8 x x2 2 3 3设设 x xj j 表示第表示第 j j 种产品每天的产量种产品每天的产量 假设该企业决策者决定不生产甲、乙产品，而是将厂假设该企业决策者决定不生产甲、乙产品，而是将厂里的现有资源外售。决策者应怎样制定每种资源的收费里的现有资源外售。决策者应怎样制定每种资源的收费标准才合理？标准才合理？2022-9-294例例1 1、应怎样制定收费标准才合理？、应怎样制定收费标准才合理？设设 y yj j 表示第表示第 j j 种原料的收费单价种原料的收费单价 分析问题：分析问题：1

5、1、出让每种资源的收入不能低于自己生产时的可获利润；、出让每种资源的收入不能低于自己生产时的可获利润；2 2、定价不能太高，要使对方能够接受。、定价不能太高，要使对方能够接受。把生产一吨甲产品所用的原料出让，所得净收入应不低于生产一吨甲把生产一吨甲产品所用的原料出让，所得净收入应不低于生产一吨甲产品的利润：产品的利润：乙产品同理：乙产品同理：123yy12324yyy 把企业所有原料出让的总收入：把企业所有原料出让的总收入：123683wyyy只能在满足只能在满足 所有产品的所有产品的利润的条件下利润的条件下,其总收入其总收入尽可能少尽可能少,才能成交才能成交.123min683wyyy121

6、23123 324,0yyyyyy yys.t.2022-9-295一、对偶问题的提出一、对偶问题的提出 任何一个求极大的线性规划问题都有一个求极小的线性任何一个求极大的线性规划问题都有一个求极小的线性规划问题与之对应，反之亦然规划问题与之对应，反之亦然.把其中一个叫原问题，则另一个就叫做它的对偶问题，把其中一个叫原问题，则另一个就叫做它的对偶问题，这一对互相联系的两个问题就称为一对对偶问题。这一对互相联系的两个问题就称为一对对偶问题。12max34zxx1212212 628 3,0 xxxxxx xs.t.LP1123min683wyyy12123123 324,0yyyyyy yys.t

7、.LP2原问题（原问题（P P）对偶问题（对偶问题（D D）2022-9-296二、原问题与对偶问题的对应关系二、原问题与对偶问题的对应关系12max34zxx1212212 628 3,0 xxxxxx xs.t.P123min683wyyy12123123 324,0yyyyyy yys.t.Dy yj j 表示对第表示对第 j j 种资源的估价种资源的估价321yyy矩阵形式：矩阵形式：12max(3 4)xzx12121161280130 xxxx s.t.123min6 8 3ywyy1231231 10312140yyyyyy s.t.max z=CX s.t.AX b X 0 m

8、in w=bTY s.t.ATY CT Y 02022-9-297(一一)对称型对偶问题对称型对偶问题其中其中 y yi i 0 0 （i i=1,2,=1,2,mm）称为）称为对偶变量对偶变量。变量均具有非负约束，且约束条件：当目标函数求极大时变量均具有非负约束，且约束条件：当目标函数求极大时均取均取“”号，当目标函数求极小时均取号，当目标函数求极小时均取“”号。号。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

9、+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 02022-9-298(二二)非对称型对偶问题非对称型对偶问题分析：分析：化为对称形式。化为对称形式。max x10,x20,x3无约束无约束s.t.a11x1+a12x2+a13x3 b1z=c1x1+c2x2+c3x3 a31x1+a32x2+a33x3 b3 a21x1+a22x2+a23x3=b2令令33

10、333(0,0)xxxxx22xx ，11 112 213 313 31a xa xa xa xb1233,0 x x x x1 12 23 33 3zc xc xc xc x21 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.2022-9-29913 12322323333a

11、 ya ya ya yc(二二)非对称型对偶问题非对称型对偶问题11 112 213 313 31a xa xa xa xb1233,0 x x x x1 12 23 33 3zc xc 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 121221231 31a ya ya ya yc1223,0y y y y 1 1222233wb yb

12、 yb yb y13 12322323333a ya ya ya yc12 12222223232a ya ya ya ycmins.t.对偶问题：对偶问题：2022-9-291012 12223232a ya ya yc12 12223232a ya ya yc(二二)非对称型对偶问题非对称型对偶问题13 12322323333a ya ya ya yc11 121221231 31a ya ya ya yc1223,0y y y y 1 1222233wb yb yb yb y13 12322323333a ya ya ya yc12 12222223232a ya ya ya ycmin

13、s.t.令令33yy222yy y-，13 12323333a ya ya yc11 121231 31a ya ya yc10y ，1 12233wb yb yb y13 12323333a ya ya ycmins.t.2y 无约束，30y 12 12223232a ya ya yc13 12323333a ya ya yc11 121231 31a ya ya yc10y ，1 12233wb yb yb ymins.t.2y 无约束，30y 13 12323333a ya ya yc2022-9-29113 3个个 =约束条件约束条件变变 量量(二二)非对称型对偶问题非对称型对偶问题1

14、2 12223232a ya ya yc13 12323333a ya ya yc11 121231 31a ya ya yc10y ，1 12233wb yb yb ymins.t.2y 无约束，30y 原问题原问题对偶问题对偶问题目标函数目标函数 maxmax目标函数目标函数 minmin目标函数的系数目标函数的系数约束条件右端常数约束条件右端常数约束条件右端常数约束条件右端常数目标函数的系数目标函数的系数3 3个个 =3 3个个 0 000无符号限制无符号限制约束条件约束条件变变 量量3 3个个 0 000无符号限制无符号限制321yyy原问题（对偶问题）原问题（对偶问题）对偶问题（原问

15、题）对偶问题（原问题）2022-9-29123 3个个 =约束条件约束条件变变 量量(一一)对称型对偶问题对称型对偶问题原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数 maxmax目标函数目标函数 minmin目标函数的系数目标函数的系数约束条件右端常数约束条件右端常数约束条件右端常数约束条件右端常数目标函数的系数目标函数的系数3 3个个 =3 3个个 0 000无符号限制无符号限制约束条件约束条件变变 量量3 3个个 0 000无符号限制无符号限制12max34zxx1212212 628 3,0 xxxxxx xs.t.123min683wyyy1

16、2123123 324,0yyyyyy yys.t.2 2个个2 2个个2022-9-2913二、原问题与对偶问题的对应关系二、原问题与对偶问题的对应关系2022-9-2914例例2 2、写出下述线性规划问题的对偶问题、写出下述线性规划问题的对偶问题解：解：设对偶变量为设对偶变量为123435xxxx12340,0,xx xx,无约束1234235zxxxxmaxs.t.1342 24xxx234 6xxx122 2yy10,y 123546wyyymins.t.123,y y y，则对偶问题为则对偶问题为20,y 3y 无约束13 3yy123325yyy123 1yyy2022-9-291

17、5例例3 3、写出下述线性规划问题的对偶问题、写出下述线性规划问题的对偶问题解：解：设对偶变量为设对偶变量为123435xxxx12340,0,xx xx,无约束1234235zxxxxmins.t.1342 24xxx234 6xxx122 2yy10,y 123546wyyymaxs.t.123,y y y，则对偶问题为则对偶问题为20,y 3y 无约束13 3yy123325yyy123 1yyy2022-9-2916练习、写出下述线性规划问题的对偶问题练习、写出下述线性规划问题的对偶问题1234235zxxxxmaxs.t.1234124123412344 32532 74234 60

18、,0,xxxxxxxxxxxxxxx无约束12343234zxxxxmins.t.123423412341234 2343 345237420,0,xxxxxxxxxxxxxxx,无约束2022-9-2917 对偶问题的基本性质对偶问题的基本性质Duality TheoryDuality Theory 线性规划的对偶问题线性规划的对偶问题 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析第二章第二章 线性规划的对偶理论线性规划的对偶理论2022-9-2918对偶问题的基本性质对偶问题的基本性质1.1.对称性对称性2.2.弱对偶性弱对偶性3.3

19、.无界性无界性4.4.最优性最优性7.7.原问题与对偶问题单纯形表间的性质原问题与对偶问题单纯形表间的性质5.5.互补松弛性互补松弛性6.6.强对偶性强对偶性2022-9-2919对偶问题的基本性质对偶问题的基本性质 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,mijijiia ycjnyim（）（）s.t.（D）2022-9-2920 对偶问题对偶问题1 1、对称性、对称性定理：对偶问题的对偶是原问题。定理：对偶问题

20、的对偶是原问题。对偶问题对偶问题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 02022-9-29212 2、弱对偶性、弱对偶性11nmjjiijic xb y定理：设定理：设 和和 分别是原问题（分别是原问题（P P）和其对偶问题（和其对偶问题（D D）的可行解，则恒有）的可行解，则恒有(1,)jxjn(1,)iy im111()nnmjjijijjjic xa yx 111()mmniiijjiiijb ya xy 11mnijjiija x y2022-9-29

21、222 2、弱对偶性、弱对偶性11nmjjiijic xb y定理：设定理：设 和和 分别是原问题（分别是原问题（P P）和其对偶问）和其对偶问题（题（D D）的可行解，则恒有）的可行解，则恒有(1,)jxjn(1,)iy im推论：原问题任一可行解的目标函数值是其对偶问题目标推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。是其原问题目标函数值的上界。2022-9-29233 3、无界性、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解，定理：在互为对偶的两

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

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

24、个问题或具有无界解或无可行解。2022-9-29253 3、无界性、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解，定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。则另一个问题无可行解。推论推论1 1：在互为对偶的两个问题中，若一个问题无可行解，：在互为对偶的两个问题中，若一个问题无可行解，则另一个问题或具有无界解或无可行解。则另一个问题或具有无界解或无可行解。推论推论2 2：在互为对偶的两个问题中，若一个问题有可行解，：在互为对偶的两个问题中，若一个问题有可行解，另一个问题无可行解，则可行的问题无界。另一个问题无可行解，则可行的问题无界。无界解无界解无可行

25、解无可行解无可行解无可行解无界解无界解对偶问题对偶问题原问题原问题2022-9-2926例例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)(0,0,0)T T 是原问题的一是原问题的一个可行解，故

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

27、yy1221yy223y 2 1y21y 2022-9-29284 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因此因此*1111nnm

28、mjjjjiiiijjiic xc xb yb y2022-9-29295 5、互补松弛性、互补松弛性定理：设定理：设 和和 分别是原问题和其分别是原问题和其对偶问题的最优解，对偶问题的最优解，*(1,)jxjn*(1,)iyim*1nijjija xb若对偶变量若对偶变量 ，则原问题相应的约束条件，则原问题相应的约束条件*0iy若约束条件若约束条件 ，则相应的对偶变量，则相应的对偶变量*0iy*1nijjija xb2022-9-2930 皮肌炎是一种引起皮肤、肌肉、心、肺、肾等多脏器严重损害的，全身性疾病，而且不少患者同时伴有恶性肿瘤。它的1症状表现如下：1、早期皮肌炎患者，还往往伴有全身

29、不适症状，如-全身肌肉酸痛，软弱无力，上楼梯时感觉两腿费力；举手梳理头发时，举高手臂很吃力；抬头转头缓慢而费力。皮肌炎图片皮肌炎的症状表现5 5、互补松弛性、互补松弛性定理：设定理：设 和和 分别是原问题和其对偶问题的最分别是原问题和其对偶问题的最优解，优解，*(1,)jxjn*(1,)iyim*1nijjija xb若对偶变量若对偶变量 ，则原问题相应的约束条件，则原问题相应的约束条件*0iy若约束条件若约束条件 ，则相应的对偶变量，则相应的对偶变量*0iy*1nijjija xb*111()nnmjjijijjjic xa yx*111()mmniiijjiiijb ya xy*11nmj

30、jiijic xb y*111()mmniiijjiiijb ya xy*11()0mnijjiiija xby 2022-9-29325 5、互补松弛性、互补松弛性定理：设定理：设 和和 分别是原问题和其对偶问题的最分别是原问题和其对偶问题的最优解，优解，*(1,)jxjn*(1,)iyim*1nijjija xb若对偶变量若对偶变量 ，则原问题相应的约束条件，则原问题相应的约束条件*0iy若约束条件若约束条件 ，则相应的对偶变量，则相应的对偶变量*0iy*1nijjija xb*1nijjija xb若若 ，则，则*0iy若若 ，则，则*0iy*1nijjija xb*1mijijia y

31、c若若 ，则，则*0jx若若 ，则，则*0jx*1mijijia yc2022-9-2933例例2 2、利用互补松弛定理求最优解、利用互补松弛定理求最优解123123123 2102216 ,0 xxxxxxx x x12334zxxxmaxs.t.已知原问题的最优解是已知原问题的最优解是*(6,2,0)TX求对偶问题的最优解。求对偶问题的最优解。解：解：设对偶变量为设对偶变量为1223yy12,0y y 121016wyymins.t.12,y y则对偶问题为则对偶问题为12224yy12 1yy设对偶问题的最优解为设对偶问题的最优解为*12(,),TyyY因因*12,0,xx 由互补松弛性

32、知由互补松弛性知*1223yy*12224yy解方程组得解方程组得*121,1,yy故对偶问题的最优解为故对偶问题的最优解为*(1,1),TY*26.w2022-9-2934例例3 3、利用互补松弛定理求最优解、利用互补松弛定理求最优解已知原问题的最优解是已知原问题的最优解是12312312312323523 61 40,0,xxxxxxxxxxxx无约束12343zxxxmaxs.t.*(0,0,4)TX求对偶问题的最优解。求对偶问题的最优解。对偶变量为对偶变量为123231yyy1230,0,yyy无约束12324wyyymins.t.123,y y y则对偶问题为则对偶问题为1233 4

33、yyy123563yyy设对偶问题的最优解为设对偶问题的最优解为*123(,),TyyyY将将 代入原问题约束条件得代入原问题约束条件得*X解：解：*123*123*1232352023 6241 44xxxxxxxxx 由互补松弛性知由互补松弛性知*120,yy又又*123563yyy故对偶问题的最优解为故对偶问题的最优解为*(0,0,3),TY*12.w得得*33,y 2022-9-2935例例4 4、利用互补松弛定理求最优解、利用互补松弛定理求最优解已知其对偶问题的最优解是已知其对偶问题的最优解是1234512345 23423 30,1,2,5jxxxxxxxxxxxj12345235

34、23zxxxxxmins.t.*4 3(,)5 5TY求原问题的最优解。求原问题的最优解。对偶问题为对偶问题为设原问题的最优解为设原问题的最优解为*,X解：解：1243wyymins.t.121212121212 22 (1)3 (2)235 (3)2 (4)(5)3 3 ,0yyyyyyyyyyyy将将 代入原问题约束条件得：代入原问题约束条件得：*Y(2)(2)、(3)(3)、(4)(4)为严格不等式为严格不等式由互补松弛性知由互补松弛性知*2340,xxx又因又因*12,0,yy 由互补松弛性知由互补松弛性知*12345*12345 23423 3xxxxxxxxxx得得*151,xx故

35、原问题最优解为故原问题最优解为*(1,0,0,0,1),TX*5.z2022-9-29366 6、强对偶性、强对偶性（对偶定理）（对偶定理）定理：若原问题有最优解，则其对偶问题也一定具有最优定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。解，且目标函数的最优值相等。11max0nmjjsijizc xx1 1,0,0 1,nijjsiijjsia xxbimxxjn（）（）s.t.用单纯形法求原问题的最优解：用单纯形法求原问题的最优解：2022-9-2937jc BC基bjjcz11max0nmjjsijizc xx1 1,0,0 1,nijjsiijjsia x

36、xbimxxjn（）（）s.t.1ckcnc0000001sxslxsmx1blbmb1xkxnx1sxslxsmx10000101011a1 la1ma1kalkamka1nalnamna1ckcnc0001m1mjjjjiijjjiczccacBC P2022-9-2938jc BC基bjjcz1ckcnc0000001sxslxsmx1blbmb1xkxnx1sxslxsmx10000101011a1 la1ma1kalkamka1nalnamna1ckcnc0001m非基变量非基变量基变量基变量X Xs sX XI IA Ajjcz0 0C C基变量基变量 基变量基变量 基可基可 系数

37、系数 行解行解 0 0 X Xs s b bX XB B X XN NB NB NC CB B C CN N2022-9-2939 X XB B I I 0 0C CB B C CN NB NB NX XB B X XN N单纯形法计算的矩阵描述单纯形法计算的矩阵描述非基变量非基变量基变量基变量X Xs sI Ijjcz0 0基变量基变量 基变量基变量 基可基可 系数系数 行解行解 0 0 X Xs s b b基变量基变量非基变量非基变量X XB Bjjcz基变量基变量 基变量基变量 基可基可 系数系数 行解行解 C CN NC CB BB B-1-1N N B B-1-1N BN B-1-1

38、X XN N X Xs sB B-1-1b bC CB B进行初等进行初等行变换行变换C CB BB B-1-1 若若C CN NC CB BB B-1-1N N 00C CB BB B-1-1 00 最优解最优解X X*=B B-1-1b bB B-1-1存在存在2022-9-29406 6、强对偶性、强对偶性（对偶定理）（对偶定理）min w=bTY s.t.ATY CT Y 0 若若C CN NC CB BB B-1-1N N 00C CB BB B-1-1 00 最优解最优解X X*=B B-1-1b b令令Y YT T=C=CB BB B-1-1，则有，则有C CN NY YT T

39、N N 00，Y Y 0 0因因C CB BY YT TB B=0=0，故故C CY YT T A A 00，即即A AT T Y Y C CT T，说明说明Y Y是是D D的可行解的可行解 max z=CX s.t.AX b X 0此时目标函数值此时目标函数值w=bw=bT TY=YY=YT Tb=Cb=CB BB B-1-1b b原问题的最优值原问题的最优值 z z=CB=CB-1-1b=Cb=CB BB B-1-1b b由最优性定理知，由最优性定理知，Y Y是是D D的最优解。的最优解。定理：若原问题有最优解，则其对偶问题也一定具有最优定理：若原问题有最优解，则其对偶问题也一定具有最优解

40、，且目标函数的最优值相等。解，且目标函数的最优值相等。2022-9-29416 6、强对偶性、强对偶性（对偶定理）（对偶定理）推论：若一对对偶问题都有可行解，则它们都有最优解，推论：若一对对偶问题都有可行解，则它们都有最优解，且目标函数的最优值必相等。且目标函数的最优值必相等。定理：若原问题有最优解，则其对偶问题也一定具有最优定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。解，且目标函数的最优值相等。互为对偶的两个问题，只会出现以下三种关系：互为对偶的两个问题，只会出现以下三种关系：都有最优解，且最优值相等都有最优解，且最优值相等 一个有无界解，另一个无可行解；一

41、个有无界解，另一个无可行解；两个都无可行解。两个都无可行解。*11nmjjiijizc xb yw2022-9-2942判断下列说法是否正确，为什么？判断下列说法是否正确，为什么？1 1、如果线性规划问题存在可行解，则其对偶问题也一定、如果线性规划问题存在可行解，则其对偶问题也一定存在可行解。存在可行解。2 2、如果线性规划问题的对偶问题无可行解，则原问题也、如果线性规划问题的对偶问题无可行解，则原问题也一定无可行解。一定无可行解。3 3、如果线性规划问题的原问题和对偶问题都具有可行解，、如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划一定具有有限最优解。则该线性规划一定具有有限最

42、优解。2022-9-2943对偶问题的基本性质对偶问题的基本性质一个问题一个问题maxmax另一问题另一问题minmin应用应用有最优解有最优解有最优解有最优解强对偶性强对偶性无界解无界解（有可行解）（有可行解）无可行解无可行解无界性无界性（证无最优解）（证无最优解）无可行解无可行解无界解无界解（有可行解）（有可行解）已知最优解已知最优解求最优解求最优解互补松弛性互补松弛性2022-9-29447 7、原问题与对偶问题单纯形表间的性质？、原问题与对偶问题单纯形表间的性质？X XB B I I 0 0C CB B C CN NB NB NX XB B X XN N非基变量非基变量基变量基变量X

43、Xs sI Ijjcz0 0基变量基变量 基变量基变量 基可基可 系数系数 行解行解 0 0 X Xs s b b基变量基变量非基变量非基变量X XB Bjjcz基变量基变量 基变量基变量 基可基可 系数系数 行解行解 C CN NC CB BB B-1-1N N B B-1-1N BN B-1-1X XN N X Xs sB B-1-1b bC CB BY YT T=C=CB BB B-1-1C CB BB B-1-1 2022-9-2945Duality TheoryDuality Theory 线性规划的对偶问题线性规划的对偶问题 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 对

44、偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 对偶问题的基本性质对偶问题的基本性质第二章第二章 线性规划的对偶理论线性规划的对偶理论2022-9-2946 第一步：找到一个满足最优检验的初始第一步：找到一个满足最优检验的初始基本解；基本解；第二步：检验当前解是否可行。若可行第二步：检验当前解是否可行。若可行，已得到最优，否则转入下一步。，已得到最优，否则转入下一步。第三步：选择第三步：选择b b最小一行的变量作为换出最小一行的变量作为换出变量变量 第四步：换入变量第四步：换入变量mincmincj j-z-zj j/a/aij ij(负数和零负数和零不参与比较不参与比较)第五步：迭代运算，到第

45、二步。第五步：迭代运算，到第二步。对偶单纯形法对偶单纯形法2022-9-2947对偶单纯形法j,0102641212120632153214321对一切jxxxxxxxxxxxxx Max z=-6xMax z=-6x1 1-3x-3x2 2-2x-2x3 3例：例：2022-9-2948cj-6-3-2000cBxBbx1x2x3x4x5x60 x4-20-1-1-11000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001zj000000cj-zj-6-3-2000对偶单纯形法找到一个满足最优检验的初始基本解找到一个满足最优检验的初始基本解检验当前解不可行，选择检验当

46、前解不可行，选择b b最小一行的变量作为换出变量；最小一行的变量作为换出变量；换入变量换入变量mincmincj j-z-zj j/a/aij ij 2022-9-2949cj-6-3-2000cBxBbx1x2x3x4x5x6-2x320111-1000 x5-1-1/4-1/40-1/4100 x610100-101zj-2-2-2200cj-zj-4-10-200对偶单纯形法检验当前解不可行，选择检验当前解不可行，选择b b最小一行的变量作为换出变量；最小一行的变量作为换出变量；换入变量换入变量mincmincj j-z-zj j/a/aij ij 2022-9-2950cj-6-3-2

47、000cBxBbx1x2x3x4x5x6-2 x3 16001-240-3 x2 41101-400 x6 10-100-101zj-3-3-2140cj-zj-300-1-40对偶单纯形法2022-9-2951 对偶问题的经济解释对偶问题的经济解释影子价格影子价格Duality TheoryDuality Theory 线性规划的对偶问题线性规划的对偶问题 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 对偶问题的基本性质对偶问题的基本性质第二章第二章 线性规划的对偶理论线性规划的对偶理论2022-9-2952 b bi i 代表第代表第i i种资源的拥有量；种资源的拥有量；y yi i*代

48、代表在资源最优利用条件下对第表在资源最优利用条件下对第i i种资种资源的单位估价。这种估价不是资源源的单位估价。这种估价不是资源的市场价格，而是根据资源在生产的市场价格，而是根据资源在生产中作出的贡献而作的估价。中作出的贡献而作的估价。一、影子价格的概念一、影子价格的概念设设 x xj j 表示第表示第 j j 种产品每天的产量种产品每天的产量设设 y yj j 表示第表示第 j j 种原料的收费单价种原料的收费单价 由对偶定理知当由对偶定理知当P P问题求得问题求得最优解最优解X X*时，时，D D问题也得到最问题也得到最优解优解Y Y*，且有，且有*11nmjjiijizc xb yw影子

49、价格影子价格2022-9-2953若若 ，则，则*0iy*1nijjija xb*1nijjija xb若若 ，则，则*0iy当某个右端常数当某个右端常数bi bi+1时时一、影子价格的概念一、影子价格的概念*1miiizb y由由 得得*iizyb说明说明 的值相当于在资源得到最优的值相当于在资源得到最优利用的生产条件下，利用的生产条件下，每增加一个每增加一个单位时目标函数单位时目标函数z的增量的增量*iyib*11iimmzb yb yb y*11(1)iimmzb ybyb y*11iimmib yb yb yy*izy边际价格边际价格说明若某资源说明若某资源 未被充分利用，未被充分利用

50、，则该种资源的影子价格为则该种资源的影子价格为0 0；ib若某资源的影子价格不为若某资源的影子价格不为0 0，则说，则说明已有资源在已消耗完毕。明已有资源在已消耗完毕。2022-9-2954二、在经营管理中的应用二、在经营管理中的应用1x2x3x4x5xjc BC基bjjcz340340001x2x5x42110001021111100100210y y1 1*=2=2y y2 2*=1=1y y3 3*=0=0Y Y*T T=C=CB BB B-1-1C CB BB B-1-1 2022-9-2955二、在经营管理中的应用二、在经营管理中的应用y y1 1*=2=2y y2 2*=1=1y