与清华大学运筹学-教材相应的授课文档第二章ppt课件

1、1 1 单纯形法的矩阵描述单纯形法的矩阵描述 设设max z = CXmax z = CX AX = b AX = b X 0 X 0 A A为为m mn n阶矩阵阶矩阵 RankA=m , RankA=m ,取取B B为可行基为可行基, N, N为非基，为非基， NBNBCCCNBAXXX , ,0, maxNBNBNNBBXXbNXBXXCXCzbBCbBNBIBN111- 1 0 0 :矩阵单纯形表0zXCXCbNXBXNNBBNBbBCzXNBCCXbBNXBBXBBNBNBNB11111)(0bBCzXXbBNXBIXBNNBNB1110bBCzXXbBNXBIXBNNBNB1110

2、NBCCbBCzbBXXBNNBBN111 , , 0 得令.,0 !出则最优解直接由上式求若能找到最优为最优基的使注BBNbBCzbBXB11 0 目标函数基可行解求解步骤：.42 .,. 4. ,)()(0)()()(min ,)(0)(max . 3., 0. 2,. 111111111步直到求出结果重复的求出此得到新的出基行对应的则若入基则若基变换否则转下一步则得最优解若求取可行基BBBxlPBbBPBPBbBxNBCCBBllklikikiikkNjNjBNN32利润12kg40材料B16kg04材料A8台时 21设备台时限制 2 2 对偶问题的提出对偶问题的提出 eg.1 eg.1

3、制定生产计划制定生产计划 M1: max z = 2x1 + 3x2 M1: max z = 2x1 + 3x2 1x1 + 2x2 8 1x1 + 2x2 8 4x1 16 4x1 16 4x2 12 4x2 12 x1 x1，x2 0 x2 0 现在出租，设y1为设备单位台时的租金 y2,y3为材料A、B转让附加费(kg-1) 则M2为M1的对偶问题，反之亦然。M2: min w = 8y1 + 16y2 + 12y3 y1 + 4y2 2 2y1 + 4y3 3 y1,y2,y3 032利润12kg40材料B16kg04材料A8台时 21设备台时限制 0,124 16 482 32max

4、 212121211xxxxxxxxzM 一般的，原问题：max z = CX AX b X 0 对偶问题：min w = Yb YA C Y 0 比较： max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个 “” “”3 3 对偶问题的化法对偶问题的化法 1 1、典型情况、典型情况 eg.2max z = x1 + 2x2 + x3 eg.2max z = x1 + 2x2 + x3 2x1 + x2 6 2x1 + x2 6 2x2 + x3 8 2x2 + x3 8 x1,x2,x3 0 x1,x2,x3 0对偶：min w = 6y1 + 8y2 2y

5、1 1 y1 + 2y2 2 y2 1 y1,y2 0 2、含等式的情况 eg.3max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0对偶：min w = 3y1-3y1”+4y2 2y1-2y1”+ y2 1 y1- y1”+2y2 2 3y1-3y1”+5y2 4 y1,y1”,y2 0令y1=y1-y1”,那么： min w = 3y1+4y2 2y1 + y2 1 y1 +2y2 2 3y1 +5y2 4 y2 0，y1无约束普通，原问题第i个约束取等式，对偶问题第i个变量无约束。 2x1 + x2

6、+ 3x3 3-2x1 - x2 - 3x3 -3 3、含“”的max问题 eg.4max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0对偶：min w = -3y1 + 4y2 -2y1 + y2 1 -y1 + 2y2 2 -3y1 + 5y2 4 y1,y2 0令y1 = -y1，那么： min w = 3y1 + 4y2 2y1 + y2 1 y1 + 2y2 2 3y1 + 5y2 4 y1 0,y2 0-2x1 - x2 - 3x3 -3普通: max问题第i个约束取“”，则min问题第i个变量 0

7、； min问题第i个约束取“”，则max问题第i个变量 0 ； 原问题第i个约束取等式，对偶问题第i个变量 无约束； max问题第j个变量 0 ,则min问题第j个约束取“” ； min问题第j个变量 0 ，则max问题第j个约束取“” ； 原问题第j个变量无约束，对偶问题第j个约束取等式。 eg.5min z = 2x1 + 3x2 - 5x3 + x4 eg.5min z = 2x1 + 3x2 - 5x3 + x4 x1 + x2 - 3x3 + x4 5 x1 + x2 - 3x3 + x4 5 2x1 + 2x3 - x4 4 2x1 + 2x3 - x4 4 x2 + x3 + x

8、4 = 6 x2 + x3 + x4 = 6 x1 0,x2,x3 0,x4 x1 0,x2,x3 0,x4无约束无约束对偶：max w = 5y1 + 4y2 + 6y3 y1 + y2 2 y1 + y3 3 -3y1 + 2y2 + y3 -5 y1 - y2 + y3 = 1 y1 0,y2 0,y3无约束 4 4 对偶问题的性质对偶问题的性质 1、对称性 对偶问题的对偶为原问题.0 )max(0;,min)max(YCYAYbwYCYACYAYbww即0)min(XbAXCXw0 , ,min 0 , ,maxYCYAYbwXbAXCXz0)min(XbAXCXw证毕令0 max m

9、axmax)min(XbAXCXzwzCXwww.,:的可行解分别为原问题和对问题设证明YXXCXAYCAYCYAbYXAYbXAbAX证毕bYXCbYXAYXC bYXCYX ,. 2则存在为对偶问题的可行解为原问题的可行解设弱对偶性推论：(1) max问题任一可解的目标值为min问题目标值的一个下界；(2) min问题任一可解的目标值为max问题目标值的一个上界。3、无界性 若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。 4、最优性 设X*，Y*分别为原问题和对偶问题可行解，当 C

10、X*=Y*b时， X*，Y*分别为最优解。证毕为最优解即为最优解即由弱对偶性题的任一可行解分别为原问题和对偶问设证明 * )2( ) 1 (.,:*YbYbYbYCXbYXCXXCCXbYXCYX 5、对偶定理 若原问题有最优解，那么对偶问题也有最优解， 且目标值相等。*11*1*1*1*11*0)(:, 0.:wbYbBCbBCCCXzbBXbBCbYwYBCYCAYCABCABCCXBNBBBBB则其目标值为因原问题最优解则为对偶问题的可行解若其中全部检验数可表示为则其对应的基矩阵存在为原问题的最优解设证明Y*为对偶问题的最优解，且原问题和对偶问题的目标值相等。证毕6、松弛性 若X*，Y*

11、分别为原问题及对偶问题的可行解， 那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为 最优解。证明：0,0max:SSSXXbXAXXCXz设原问题为0,0min:SSSYYCYYAYYbw设对偶问题为0,0maxSSSXXbXAXXCXz0,0minSSSYYCYYAYYbwXYYAXXYYACXzSS)(SSYXYAXXAXYYbw)(将b,C分别代入目标函数：;,0, 0,*为最优解时当为可行解若YXzwXYXYYXSS证毕必有则分别为最优解若另一方面0 , 0,*SSXYXYzwYXTSmSSSTnxxxXxxxX) () (*2*1*2*1* ) ( ) ( *2*1*2*

12、1*snSSSmyyyYyyyY 其中：用分量表示： mixynjxySiijSj, 2 , 1 , 0;, 2 , 1 , 0* 7、检验数与解的关系 (1)原问题非最优检验数的负值为对偶问题的一个基解。 (2)原问题最优检验数的负值为对偶问题的最优解。 分析：max z = CX + 0Xs = (C 0)(X Xs)T AX + Xs = b X,Xs 0 min w = Yb + YS0 YA - Ys = C Y,Ys 0 检验数： = (C 0)- CBB-1(A I) = (C- CBB-1A - CBB-1) = (c s) c = C - CBB-1A X对应的检验数 s =

13、 - CBB-1 Xs对应的检验数 eg.6eg.6知：知：min w = 20y1 + 20y2 min w = 20y1 + 20y2 的最优解为的最优解为y1y1* *=1.2,y2=1.2,y2* *=0.2=0.2-ys1 y1 + 2y2 1 -ys1 y1 + 2y2 1 试用松弛性求对试用松弛性求对偶偶-ys2 2y1 + y2 2 -ys2 2y1 + y2 2 问题的最优解。问题的最优解。 -ys3 2y1 + 3y2 3 -ys3 2y1 + 3y2 3 -ys4 3y1 + 2y2 4 -ys4 3y1 + 2y2 4 y1,y2 0 y1,y2 0 解：对偶问题 ma

14、x z = x1 + 2x2 + 3x3 + 4x4 x1 + 2x2 + 2x3 + 3x4 20 +xs1 2x1 + x2 + 3x3 + 2x4 20 +xs2 x1,x2,x3,x4 0 y1*xs1* = 0 y2*xs2* = 0 ys1*x1* = 0 ys2*x2* = 0 ys3*x3* = 0 ys4*x4* = 0 y1*=1.2,y2*0.2 0 xs1* = xs2* = 0 由 y1* + 2y2* = 1.6 1 ys1* 0 x1* = 0 由 2y1* + y2* = 2.6 2 ys2* 0 x2* = 0 由 2y1* + 3y2* = 3 =右边 ys

15、3* = 0 x3*待定 由 3y1* + 2y2* = 4 =右边 ys4* = 0 x4*待定 有 2x3* + 3x4* = 20 3x3* + 2x4* = 20 x3* = 4 x4* = 4 最优解：最优解：x1x1* * = 0 x2 = 0 x2* * = 0 x3 = 0 x3* * = 4 x4 = 4 x4* * = 4 = 4 xs1 xs1* * = 0 xs2 = 0 xs2* * = 0 = 0 最大值：最大值：z z* * = 28 = w = 28 = w* *5 5 对偶问题的经济含义对偶问题的经济含义影子价格影子价格 最优情况：最优情况：z z* * =

16、w = w* * = b1y1 = b1y1* * + + biyi + + biyi* * + + bmym+ + bmym* *的影子价格为称i*i*ibzbyyi*x2x1Q2 eg.7max z = 2x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 0b1： 8 9 Q2(4，2.5) z* = 15.5 z* = z*- z* = 3/2 = y1*b2：16 17 Q2”(4.25，1.875) z*” = 14.125 z* = z*”- z* = 1/8 = y2*b3：12 13 z* = 0 = y3*Q2Q2”6 6 对偶单纯形法对偶单纯形

17、法 单纯形法：由单纯形法：由 XB = B-1b 0 XB = B-1b 0，使，使j 0j 0，j = j = 1,m1,m对偶单纯形法：由对偶单纯形法：由j 0(j= 1,n)j 0(j= 1,n)，使，使XB = B-1b XB = B-1b 0 0 步骤：步骤：(1)(1)保持保持j 0j 0，j= 1,nj= 1,n，确定，确定XBXB，建立计，建立计算表格；算表格； (2)判别XB = B-1b 0是否成立？ 若成立，XB为最优基变量； 若不成立，转(3)； (4)消元运算，得到新的XB。(3)基变换 出基变量， 出基；，则若lliiixmibbb, 10min入基变量， 入基。则

18、若kaljajxalkkljj0min反复2）-（4步，求出结果。 eg.8用对偶单纯形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 0解：max z = -2x1 - 3x2 - 4x3 + 0 x4 + 0 x5 - x1 - 2x2 - x3 + x4 = -1 -2x1 + x2 - 3x3 + x5 = -4 x1,x2,x3,x4,x5 0-2-3-400CBXBbx1x2x3x4X50 x4-10 x5-4出出出x4,x5 0 最优最优解：最优解：x1x1* * = 2 = 2，x2x2

19、* * = 0 = 0，x3x3* * = 0 = 0，x4x4* * = 1 = 1，x5x5* * = 0 = 0目标值：目标值：w w* * = -z = -z* * = 4 = 47 7 灵敏度分析灵敏度分析njpBCcABCCNBCCjBjjBBNN, 2 , 1, 0 0 0 :111 或或最优性条件分析 变化对最优解的影响。j ,ijiacb0 :1bBXB可行性条件的变化资源ib 1 . 7TiTmiiiibbbbbbbbbbbb)0b 0 0() ( 21 bBbBbbBbBXB1111)(.,0 11这里用到可行性条件保持问题的最优性不变的变化范围求出由ibbBbB例1 已

20、知下述问题的最优解及最优单纯形表,0,124 164 82 00032max54321524132154321xxxxxxxxxxxxxxxxxz., ) 12使最优基不变的变化范围求 b. 4 )21时的最优解求b最优单纯形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/40014200032bBXBC5x4x3x2x1x1x5x2x14 Z)4 0 0 2 4(,*TX此时22216 1) :bbb解08/12/112/1204/101B2441216808/12/112/1204/101*bBXB由最优单纯形表得:)(012bbBb221118/12/14

21、/12440008/12/112/1204/10244)(bbbBbBbbB0008/22/44/4222bbb08/202/404/4222bbb.1682最优基不变bTTbb)0 0 4()0 0 ( )214 44 28024400408/12/112/1204/10244)(111bBbBbbB不可行!用对偶单纯形法计算-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/2000-1/81/2102+2311/2-2004-8x5001/40014+0 x12ix5x4x3x2x1bXBCB00032x23/4-2)(17 :

22、 . 0, 0, 2, 3, 4 :*5*4*3*2*1元目标值最优解zxxxxx的变化价值系数jc 2 . 7.01分两种情况讨论进行分析根据最优性条件NBCCBNN的变化非基变量价值系数kc. 1kBkkpBCc1:原检验数/ :kkkkkccccc变化kkkBkkkcpBCcc1/., 0 :/此时最优解不变令kkkkkcc例2 求例1 c4的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x204c8/1)8/1(8/1444c由解:. 8/1 4时最优解不变即c的变化基变量价

23、值系数rc. 2NBCCBNN1 原BBBCCC 若NBCNBCNBCCNBCCCBNBBNBBNN1111/ )( 则分析:)0 0 0( ) ( :21 rBmrBcCccccC其中.变化影响所有可见jrc方法:.0 1/的变化范围求出令rBNNcNBC例3 求例1 c2的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2解:0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2) 0 0( ),

24、3 0 2(2cCCBB 1/8)- (-3/2) (43N ) (/4/3/n44414/433313/3pcpBcpcpBcBBBB02232/120)c 0 0(232233/3cpcB08818/12/14/1)c 0 0(812244/4cpcB1322cc. 13 2时最优解不变即c的变化技术系数jia 3 . 7kBkkpBCc1 原T1k k k 0) a 0( ) ( , lkkTmklkkkkkklllpaaappppaaaa若分析:.k 的变化讨论非基变量技术系数lalklkakBkBkkkBkKpBCpBCcppBCc111 )( 则TlkmlkkBkapBC)00)(11 0lklkka令., 最优解不变时当lkkla例4 求例1 a24的变化范围,使最优解不变.解:242424241, 1aaaa) (0) 1/8 2/3( 3) 0 2(32111BBCB24242448181aa08181 244a令. , 1 24此时最优解不变a 例5 在例1的基础上，企业要增加一个新产品,每件产品需2个台时，原材料A 6kg，原材料B 3kg，利润 5元/件，问如何安排各产品的产量，使利润最大？解：0,1234 1664 822 532max3213231321321xxxxxxxxxxxxxz532利