运筹学第三章线性规划的对偶原理.ppt

《运筹学第三章线性规划的对偶原理.ppt》由会员分享，可在线阅读，更多相关《运筹学第三章线性规划的对偶原理.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章线性规划的对偶原理线性规划的对偶原理 单纯形法的矩阵描述单纯形法的矩阵描述A为为mn阶矩阵阶矩阵 RankRankA=m,取取B为可行基为可行基,N为非基，为非基，1求解步骤：求解步骤：232利润12kg40材料B16kg04材料A8台时 21设备台时限制 1 1 线性规划的对偶问题线性规划的对偶问题一、问题提出一、问题提出 例例11制定生产计划制定生产计划 M1 1:max:max z=2 2x1 1+3 3x2 2 1 1x1 1+2 2x2 2 8 8 4 4x1 1 1616 4 4x2 2 1212 x1 1，x2 2 0 0 3现在不再生产，将设备材料出租出让，确定租费

2、及转让费？现在不再生产，将设备材料出租出让，确定租费及转让费？设设y1 1为设备单位台时的租金，为设备单位台时的租金，y2 2,y3 3为材料为材料A A、B B转让附加费转让附加费(kgkg-1 1)目标函数，约束条件？目标函数，约束条件？则则M2 2为为M1 1的对偶问题，的对偶问题，反之亦然。反之亦然。M2 2:min:min w=8 8y1 1+1616y2 2+1212y3 3 y1 1+4 4y2 2 2 2 2 2y1 1 +4 4y3 3 3 3 y1 1,y2 2,y3 3 0 032利润12kg40材料B16kg04材料A8台时 21设备台时限制 4 一般的，原问题：一般的

3、，原问题：maxmax z=CX AX b X 0 0 对偶问题：对偶问题：minmin w=Yb YA C Y 0 0 比较：比较：maxmax z min min w 决策变量为决策变量为n个个 约束条件为约束条件为n个个 约束条件为约束条件为m个个 决策变量为决策变量为m个个 “”“”“”“”约束条件的限定向量约束条件的限定向量 目标函数的价值向量目标函数的价值向量 目标函数的价值向量目标函数的价值向量 约束条件的限定向量约束条件的限定向量 5二、二、对偶问题的化法对偶问题的化法 1 1、典型情况（对称形式）典型情况（对称形式）例例2 2 maxmax z=x1 1+2 2x2 2+x3

4、 3 2 2x1 1+x2 2 6 6 2 2x2 2+x3 3 8 8 x1 1,x2 2,x3 3 0 0对偶：对偶：minmin w=6=6y1 1+8 8y2 2 2 2y1 1 1 1 y1 1+2 2y2 2 2 2 y2 2 1 1 y1 1,y2 2 0 06 2 2、含等式的情况、含等式的情况 例例3max3max z=x1 1+2 2x2 2+4 4x3 3 2 2x1 1+x2 2+3 3x3 3=3 3 x1 1+2 2x2 2+5 5x3 3 4 4 x1 1,x2 2,x3 3 0 0对偶：对偶：minmin w=3 3y1 1-3-3y1 1”+4+4y2 2 2

5、 2y1 1-2-2y1 1”+y2 2 1 1 y1 1-y1 1”+2+2y2 2 2 2 3 3y1 1-3-3y1 1”+5+5y2 2 4 4 y1 1,y1 1”,y2 2 0 0令令y1 1=y1 1-y1 1”,”,则：则：minmin w=3 3y1 1+4+4y2 2 2 2y1 1+y2 2 1 1 y1 1+2+2y2 2 2 2 3 3y1 1+5+5y2 2 4 4 y2 2 0 0，y1 1自由变量自由变量一般，原问题第一般，原问题第i个约束取等式，对偶问题第个约束取等式，对偶问题第i个变量自由变量。个变量自由变量。2 2x1 1+x2 2+3 3x3 3 3 3

6、-2 2x1 1-x2 2-3 3x3 3-3-37 3 3、含、含“”的的maxmax问题问题 例例4max4max z=x1 1+2 2x2 2+4 4x3 3 2 2x1 1+x2 2+3 3x3 3 3 3 x1 1+2 2x2 2+5 5x3 3 4 4 x1 1,x2 2,x3 3 0 0对偶：对偶：minmin w=-3-3y1 1+4 4y2 2 -2 -2y1 1+y2 2 1 1 -y1 1+2 2y2 2 2 2 -3 -3y1 1+5 5y2 2 4 4 y1 1,y2 2 0 0令令y1 1=-y1 1，则：则：minmin w=3 3y1 1+4 4y2 2 2 2

7、y1 1+y2 2 1 1 y1 1+2 2y2 2 2 2 3 3y1 1+5 5y2 2 4 4 y1 1 0,0,y2 2 0 0-2-2x1 1-x2 2-3 3x3 3-3-38一般一般:max问题第问题第i个约束取个约束取“”，则，则min问题第问题第i个变量个变量 0 0 ；min问题第问题第i个约束取个约束取“”，则，则max问题第问题第i个变量个变量 0 0；原问题第原问题第i个约束取等式，对偶问题第个约束取等式，对偶问题第i个变量个变量 自由变量；自由变量；max问题第问题第j j个变量个变量 0 0,则则min问题第问题第j个约束取个约束取“”；min问题第问题第j个变量

8、个变量 0 0 ，则，则max问题第问题第j个约束取个约束取“”；原问题第原问题第j个变量自由变量，对偶问题第个变量自由变量，对偶问题第j个约束取等式。个约束取等式。9 例例5 min5 min z=2 2x1 1+3 3x2 2-5 5x3 3+x4 4 x1 1+x2 2-3 3x3 3 +x4 4 5 5 2 2x1 1 +2 2x3 3-x4 4 4 4 x2 2+x3 3+x4 4=6 6 x1 1 0,0,x2 2,x3 3 0,0,x4 4自由变量自由变量对偶：对偶：maxmax w=5 5y1 1+4 4y2 2+6 6y3 3 y1 1+2 2y2 2 2 2 y1 1 +y

9、3 3 3 3 -3 -3y1 1+2 2y2 2+y3 3 -5-5 y1 1-y2 2+y3 3=1 1 y1 1 0,0,y2 2 0,0,y3 3自由变量自由变量102 2 对偶问题的基本性质和基本定理对偶问题的基本性质和基本定理1 1、对称性定理、对称性定理 对偶问题的对偶为原问题对偶问题的对偶为原问题.原问题：原问题：maxmax z=CX AX b X 0 (1)0 (1)对偶问题：对偶问题：minmin w=Yb YA C Y 0 (2)0 (2)证：证：(2)(2)作变换：作变换：(2)(2)等价于：等价于：对偶对偶令令z=w,即为即为(1)(1)(2)(2)的对偶问题为的对

10、偶问题为(1)(1)。11证：证：推论：推论：(1)(1)max问题任一可行解的目标值为问题任一可行解的目标值为min问题目标值的一个下界；问题目标值的一个下界；(2)(2)min问题任一可行解的目标值为问题任一可行解的目标值为max问题目标值的一个上界。问题目标值的一个上界。123 3、无界性、无界性（性质（性质2 2的推论）的推论）若原问题若原问题(对偶问题对偶问题)为无界解，则对偶问题为无界解，则对偶问题(原问题原问题)为为无可行解。无可行解。注：该性质的逆不存在。若原注：该性质的逆不存在。若原(对偶对偶)问题为无可行解，问题为无可行解，对偶对偶(原问题原问题)问题或为无界解，或为无可行

11、解。问题或为无界解，或为无可行解。13 4 4、最优性最优性 设设X*，Y*分别为原问题和对偶问题可行解，分别为原问题和对偶问题可行解，当当CX*=Y*b时，时，X*，Y*分别为最优解。分别为最优解。证：证：X*为最优解为最优解Y*为最优解为最优解145 5、对偶定理、对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标若原问题有最优解，那么对偶问题也有最优解，且目标值相等。值相等。证：证：155 5、对偶定理、对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标若原问题有最优解，那么对偶问题也有最优解，且目标值相等。值相等。推论（单纯形乘子推论（单纯形乘子Y的定理）：的定理）：原

12、问题有一个对应于基原问题有一个对应于基B的最优解，则此时的的最优解，则此时的Y是对偶问题的一个最优解。是对偶问题的一个最优解。例：书例：书P2516对偶问题中，解的情况有：对偶问题中，解的情况有：1.都有有限最优解都有有限最优解2.都无可行解都无可行解3.一个有无界解，另一个无可行解一个有无界解，另一个无可行解176 6、松弛性、松弛性若若X*，Y*分别为原问题及对偶问题的可行解，分别为原问题及对偶问题的可行解，那么那么Ys*X*=0=0，Y*Xs*=0=0，当且仅当当且仅当X*，Y*分别为最优解。分别为最优解。证：证：将将b，C代入目标函数，代入目标函数，18 7 7、检验数与解的关系、检验

13、数与解的关系 原问题附加变量最优检验数的值为对偶问题的最优解。原问题附加变量最优检验数的值为对偶问题的最优解。分析：分析：minmin z=CX+0 0Xs=(C 0)(0)(X Xs)T AX-Xs=b X,Xs 0 0 max max w=Yb+YS0 0 YA+Ys=C Y,Ys 0 0 检验数：检验数：=(C 0)-0)-CBB-1-1(A-I)=(C-CBB-1-1A CBB-1-1)=(c s)c=C-CBB-1-1A X对应的检验数对应的检验数 s=CBB-1-1 Xs对应的检验数对应的检验数 例：书例：书P254=2=2，5=3=319求对偶问题的最优解求对偶问题的最优解:1.

14、单纯形乘子单纯形乘子Y的定理的定理2.松弛性松弛性3.检验数与解的关系检验数与解的关系20 例例66已知：已知：minmin w w=20y20y1 1+20y20y2 2 的最优解为的最优解为y y1 1*=1.2,y=1.2,y2 2*=0.2=0.2-y ys1s1 y y1 1+2y2y2 2 1 1 试用松弛性求对试用松弛性求对偶偶-y ys2s2 2y 2y1 1+y y2 2 2 2 问题的最优解。问题的最优解。-y ys3s3 2y 2y1 1+3y3y2 2 3 3 -y ys4s4 3y 3y1 1+2y2y2 2 4 4 y y1 1,y,y2 2 0 0 解：对偶问题解

15、：对偶问题 maxmax z z=x x1 1+2x2x2 2+3x3x3 3+4x4x4 4 x x1 1+2x2x2 2+2x2x3 3+3x3x4 4 20 20 +x xs1s1 2x 2x1 1+x x2 2+3x3x3 3+2x2x4 4 20 20 +x xs2s2 x x1 1,x,x2 2,x,x3 3,x,x4 4 0 0 y y1 1*x xs1s1*=0 y0 y2 2*x xs2s2*=0 0 y ys1s1*x x1 1*=0 y0 ys2s2*x x2 2*=0 y0 ys3s3*x x3 3*=0 y0 ys4s4*x x4 4*=0 021 y y1 1*=1

16、.2,y=1.2,y2 2*0.20.2 0 x0 xs1s1*=x xs2s2*=0 0 由由 y y1 1*+2y2y2 2*=1.61.6 1 1 yys1s1*0 x0 x1 1*=0 0 由由 2 2y y1 1*+y y2 2*=2.62.6 2 yys2s2*0 x0 x2 2*=0 0 由由 2 2y y1 1*+3y3y2 2*=3=右边右边 yys3s3*=0 x0 x3 3*待定待定 由由 3 3y y1 1*+2y2y2 2*=4 4=右边右边 y ys4s4*=0 x0 x4 4*待定待定 有有 2 2x x3 3*+3x3x4 4*=2020 3x 3x3 3*+2

17、x2x4 4*=2020 x x3 3*=4 4 x x4 4*=4 4 最优解：最优解：x x1 1*=0 x0 x2 2*=0 x0 x3 3*=4 x4 x4 4*=4 4 x xs1s1*=0 x0 xs2s2*=0 0 最大值：最大值：z z*=2828=w w*y y1 1*=1.2,y=1.2,y2 2*=0.2=0.2 y ys1s1*x x1 1*=0 y=0 ys2s2*x x2 2*=0 =0 y ys3s3*x x3 3*=0 y=0 ys4s4*x x4 4*=0 =0 y y1 1*x xs1s1*=0 y=0 y2 2*x xs2s2*=0 =0 y y1 1+2

18、y2y2 2-y ys1s1*=1 1 2y2y1 1+y y2 2-y ys2s2*=2 2 2y2y1 1+3y3y2 2-y ys3s3*=3 =3 3y3y1 1+2y2y2 2-y ys4s4*=4 4 x x1 1+2x2x2 2+2x2x3 3+3x3x4 4+x xs1s1=20202x2x1 1+x x2 2+3x3x3 3+2x2x4 4+x xs2s2=2020228 8、对偶问题的经济含义、对偶问题的经济含义影子价格影子价格 最优情况：最优情况：z z*=w w*=b b1 1y y1 1*+b bi iy yi i*+b bm my ym m*x2x1Q Q2 2 例

19、例7max7max z z=2x2x1 1+3x3x2 2 x x1 1+2x2x2 2 8 8 4x 4x1 1 1616 4x4x2 2 1212 x x1 1,x,x2 2 0 0b b1 1：8 9 Q 8 9 Q2 2(4(4，2.5)z2.5)z*=15.515.5 z z*=z z*-z z*=3/23/2=y y1 1*b b2 2：16 17 Q16 17 Q2 2”(4.25(4.25，1.875)z1.875)z*”*”=14.12514.125 z z*=z z*”*”-z z*=1/81/8=y y2 2*b b3 3：12 13 12 13 z z*=0 0=y y

20、3 3*Q Q2 2Q Q2 2”Q2（4，2）z=14条件条件3未满足，再增加未满足，再增加b，不会带来，不会带来z的增加，的增加，故该资源价值为故该资源价值为0.23 3 3 对偶单纯形法对偶单纯形法 单纯形法：由单纯形法：由 XB=B-1-1b 0 0，使使j 0 0，j=1,1,m 对偶单纯形法：由对偶单纯形法：由j 0(0(j=1,1,n)，使，使XB=B-1-1b 0 0 相同点：都用于求解原问题相同点：都用于求解原问题 对对偶偶单单纯纯形形法法：从从一一个个原原始始不不可可行行而而对对偶偶可可行行的的基基出出发发，进进行行基基变变换换，每每次次基基变变换换时时都都保保持持基基的的

21、对对偶偶可可行行性性，一一旦旦获获得得一个原始可行基，则该基必定是最优基。一个原始可行基，则该基必定是最优基。步步骤骤：(1)(1)保保持持j 0 0，j=1,1,n，确确定定XB，建建立立计计算算表表格；格；(2)(2)判别判别XB=B-1-1b 0 0是否成立？是否成立？若成立，若成立，XB为最优基变量；为最优基变量；若不成立，转若不成立，转(3)(3)；24(4)(4)取主变换，得到新的取主变换，得到新的XB。(3)(3)基变换基变换 换出变量，换出变量，换入变量（最大负比值规则），换入变量（最大负比值规则），重复（重复（2 2）-（4 4）步，求出结果。）步，求出结果。25 例例88用

22、对偶单纯形法求解用对偶单纯形法求解 minmin w w=2x2x1 1+3x3x2 2+4x4x3 3 x x1 1+2x2x2 2+x x3 3 1 1 2x 2x1 1-x x2 2+3x3x3 3 4 4 x x1 1,x,x2 2,x,x3 3 0 0 minmin w w=2x2x1 1+3x3x2 2+4x4x3 3+0 x0 x4 4+0 x0 x5 5 x x1 1+2x2x2 2+x x3 3-x x4 4 1 1 2x 2x1 1-x x2 2+3x3x3 3 x x5 5 4 4 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5 0 026 minm

23、in w w=2x2x1 1+3x3x2 2+4x4x3 3+0 x0 x4 4+0 x0 x5 5 -x -x1 1-2x2x2 2-x x3 3+x+x4 4 -1 1 -2x 2x1 1+x+x2 2-3x3x3 3+x+x5 5 -4 4 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5 0 027234000 x1 x2 x3 x4 x5b0 x4-1-2-110-10 x5-21-301-4234000*-4-2.52-0.50.501011.54-0.5x1-0.51 x402001128初始检验数中有负数？对偶不可行初始检验数中有负数？对偶不可行1、构造扩充

24、问题、构造扩充问题 增加一个变量和一个约束条件增加一个变量和一个约束条件2、求基本解（初始对偶可行）、求基本解（初始对偶可行）检验数中最小的负数检验数中最小的负数 换入变量换入变量 新增变量为换出变量新增变量为换出变量 取主变换后全部检验数非负取主变换后全部检验数非负 3、用对偶单纯形法求解扩充问题、用对偶单纯形法求解扩充问题扩充问题无可行解，则原问题无可行解扩充问题无可行解，则原问题无可行解扩充问题有最优解，则原问题有可行解，扩充问题有最优解，则原问题有可行解，且如扩充问题的目标函数值与且如扩充问题的目标函数值与M无关，则无关，则为原问题最优解。为原问题最优解。29例例：标准型：标准型：扩充

25、问题：扩充问题：30-2200000 x1 x2 x3 x4 x5x6b0 x4-1-4-1100-80 x512201060 x6 111001M-2200000*2M-36-M100001141x10M-8 x40-200220 x51 1 1 0 0 1 M01-131作业P81 1.12(1)32 4 4 灵敏度分析灵敏度分析分析分析 变化对最优解的影响变化对最优解的影响。1、保持原最优基的变化范围；、保持原最优基的变化范围；2、原最优基不再最优时，求新的最优解的最简便方法、原最优基不再最优时，求新的最优解的最简便方法3334例例1 已知下述问题的最优解及最优单纯形表已知下述问题的最优

26、解及最优单纯形表,35最优单纯形表如下最优单纯形表如下:1401/83/2000-1/81/2102-311/2-2004001/40014-2 0000-3-236由最优由最优单纯形表得单纯形表得:1401/83/2000-1/81/2102-311/2-2004001/40014-2 000-3-23738不可行不可行!用对偶单纯形法计算用对偶单纯形法计算39-1401/83/2000-1/81/2102-311/2-2004001/40014-2 0000-3-2420440173/41/20001/400103-31/21/41002001/40014-2 0000-3-24142例例

27、2 求例求例1 c4的变化范围的变化范围,使最优解不变使最优解不变.解解:1401/83/2000-1/81/2102-311/2-2004001/40014-2000-3-243分析分析:44方法方法:例例3 求例求例1 c2的变化范围的变化范围,使最优解不使最优解不变变.01/83/200 0-1/81/2102-311/2-2004x5001/40014x1-2x5x4x3x2x1bXBCB000-3-2x245解解:01/83/200 0-1/81/2102-311/2-2004x5001/40014x1-2x5x4x3x2x1bXBCB000-3-2x24647改变改变C，求新的最优

28、解，求新的最优解?只需修改最终表上的只需修改最终表上的C及检验数，得到新的迭代表，及检验数，得到新的迭代表，继续求解。继续求解。例例3 c2=1,求新的最优解求新的最优解.01/83/200 0-1/81/2102-311/2-2004x5001/40014x1-2x5x4x3x2x1bXBCB000-3-2x2-2-211/4c2=-3，若若 c2=4？最优解不变最优解不变.0 0 -1/2 5/8 011继续用单纯形法求解继续用单纯形法求解.48分析分析:4950例例4 求例求例1 a24的变化范围的变化范围,使最优解不变使最优解不变.解解:x4为非基变量，故只影响为非基变量，故只影响x4

29、的检验数。的检验数。51基变量约束系数的变化基变量约束系数的变化会导致问题变得相当复杂，所以重新计算。会导致问题变得相当复杂，所以重新计算。52四、增加一个新变量四、增加一个新变量 例例5 在例在例1的基础上，企业要增加一个的基础上，企业要增加一个新产品新产品,每件产品需每件产品需2个台时，原材料个台时，原材料A 6kg，原材料原材料B 3kg，利润利润 5元元/件，问如何安排各产件，问如何安排各产品的产量，使利润最大？品的产量，使利润最大？解：解：532利润12340料B16604料A8221设备b53表明生产新品有利表明生产新品有利。54-5/401/83/200 1/40-1/81/21

30、02-3211/2-2004x503/201/40014x1-2x5x4x3x2x1XBCB-5000-3-2x2x3b55-5/401/83/200 1/40-1/81/2102-3211/2-2004x503/201/40014x1-2x5x4x3x2x1bXBCB-5000-3-2x28/34/28 ix321405/87/161/400 0-1/8-3/163/4103/2-311/21/4-10020-3/4-1/83/2011x1-2x5x4x3x2x1bXBCB-5000-3-2x2x3x3-533/256五、增加一个新的约束条件五、增加一个新的约束条件1、原最优解满足新约束，则

31、最优解不变。、原最优解满足新约束，则最优解不变。2、若不满足，则需求新的最优解。、若不满足，则需求新的最优解。例例:原问题：原问题：加条件：加条件：5719M-3M-232002112120123201011018b0MM00834需求新解，新条件变为需求新解，新条件变为原最优表：原最优表：（0，1，2）不满足新条件）不满足新条件0000000000312058190M-3M-232002110202002010121201232001011018b00MM0083459201M-3M-4340001/21/2010100142-1101001033/21/200001008b00MM0083460作业P81 1.1361小结小结1 1、对偶问题及其化法、对偶问题及其化法原问题决策变量决定对偶问题约束条件关系原问题决策变量决定对偶问题约束条件关系原问题约束条件决定对偶问题决策变量取值方向。原问题约束条件决定对偶问题决策变量取值方向。622 2、检验数的计算方法、检验数的计算方法633 3、对偶问题的性质、对偶问题的性质4 4、对偶单纯形法、对偶单纯形法弱对偶性弱对偶性无界性无界性最优性最优性松弛性松弛性检验数与对偶问题的解检验数与对偶问题的解645 5、灵敏度分析、灵敏度分析65(4)(4)增加一个新变量增加一个新变量(5)(5)增加一个约束增加一个约束66