运筹学胡运权清华版202单纯形算法的矩阵表示.ppt

《运筹学胡运权清华版202单纯形算法的矩阵表示.ppt》由会员分享，可在线阅读，更多相关《运筹学胡运权清华版202单纯形算法的矩阵表示.ppt（22页珍藏版）》请在第壹文秘上搜索。

1、单纯形法的矩阵描述C 0基系数基列常数列X XS0XSbA Icj-zjC 0初始单纯形表初始单纯形表线性规划问题：线性规划问题：max.0zCXAXbstX标准型：标准型：max0.,0SSSzCXXAXI XbstX X一、初始单纯形表一、初始单纯形表二、迭代后的单纯形表（二、迭代后的单纯形表（当前可行基当前可行基B）基列常数列X XSXB？cj-zj？则表结构则表结构分析：分析：初始表初始表迭代后任一表迭代后任一表初等行变换初等行变换初等初等行行变换变换左乘左乘一个适当矩阵一个适当矩阵S S？A、X、C可根据基可根据基B分块分块:AB NBNXXX:BNCCCSAXI XbBNSBXNX

2、I Xb 现求基现求基B所对应的基可行解与目标值：所对应的基可行解与目标值：111BNSXB NXB XB b左乘左乘B-1令非基变量令非基变量XN，XS01,0BXB b其它分量为基解基解1BBNNBzCXC XC XC B b目标值目标值基列常数列X XSXBB-1b？cj-zj-CBB-1b？迭代后表迭代后表基列常数列X XSXSbA Icj-zj0C 0对比初始表对比初始表B-1AB-1C-CBB-1A-CBB-1B-1第第1行行-CBB-1第第1行第行第2行行三、其他形式的初始表与迭代后单纯形表三、其他形式的初始表与迭代后单纯形表基列常数列 XB XN XSXSb B N Icj-z

3、j0 CB CN 0基列常数列 XB XN XSXBB-1b I B-1N B-1cj-zj-CBB-1b 0 CN-CBB-1N -CBB-1单纯形乘子单纯形乘子初始表初始表基列常数列 x1.xj.xn XSXSb P1.Pj.Pn Icj-zj0 0基列常数列 x1.xj.xn XS XBB-1b B-1 P1.B-1 Pj.B-1 Pn B-1 cj-zj-CBB-1b .cj-CBB-1Pj.迭代后单纯形表迭代后单纯形表检验数检验数j 例例 已知初始表和最优表如下，请将表中空白处已知初始表和最优表如下，请将表中空白处数字填上。数字填上。cj2-11000CBXBbx1x2x3x4x5x

4、60 x4603111000 x5101-120100 x62011-1001cj-zj2-110000 x41-1-22x101/21/2-1x20-1/21/2cj-zj .解：解：cj2-11000CBXBbx1x2x3x4x5x60 x4603111000 x5101-120100 x62011-1001cj-zj2-110000 x41-1-22x101/21/2-1x20-1/21/2cj-zj .B-1B=（P4，P1，P2）解：解：cj2-11000CBXBbx1x2x3x4x5x60 x4603111000 x5101-120100 x62011-1001cj-zj2-110

5、000 x41-1-22x101/21/2-1x20-1/21/2cj-zj .B-1B-1b?10155 解：解：cj2-11000CBXBbx1x2x3x4x5x60 x4603111000 x5101-120100 x62011-1001cj-zj2-110000 x4101-1-22x11501/21/2-1x250-1/21/2cj-zj .B-1B-1P3?11/2-3/2010001 解：解：cj2-11000CBXBbx1x2x3x4x5x60 x4603111000 x5101-120100 x62011-1001cj-zj2-110000 x4100011-1-22x115

6、101/201/21/2-1x2501-3/20-1/21/2cj-zj00-3/20-3/2-1/2 .四、最优表四、最优表基列常数列X XSXBB-1b B-1A B-1cj-zj-CBB-1b C-CBB-1A -CBB-1若若B是最优基，则下表是最优表是最优基，则下表是最优表根据最优性判定定理根据最优性判定定理1100BBCC B AC B110BBC B ACC B即：即：记记Y=CBB-1YYY是对偶问题的可行解，是对偶问题的可行解，目标值目标值w=Yb=CBB-1b=max z Y是一般型意义下对偶问题可行是一般型意义下对偶问题可行 解，仅由决策变量取值组成（解，仅由决策变量取值

7、组成（m维）维）结论结论：当采用单纯形法求得原问题的一个：当采用单纯形法求得原问题的一个最优解的时候，检验行上同时得到对偶问最优解的时候，检验行上同时得到对偶问题的一个可行解，且两者具有相同的目标题的一个可行解，且两者具有相同的目标值。利用对偶性质，可以证明这个对偶问值。利用对偶性质，可以证明这个对偶问题的解也为最优解。题的解也为最优解。例、以求解下面例、以求解下面LPLP问题以及它的对偶问题过程为问题以及它的对偶问题过程为例，验证前述结论例，验证前述结论0,5 2426 155 2max212121221xxxxxxxs.t.xxz0,y 125 26.32132132yyyyyyyts32

8、152415minyyyw对对偶偶问问题题原原问问题题 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 jcBCbBXjjzc表表1：初始表：初始表5x4x1x2x3x5x4x3x100010001B051006201011001AB-1原问题原问题 2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1/6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 表表2：迭代中：迭代中jcBCBXjjzc4x1x2x3x5xb5x1x3x100060011B051006201

9、011001AB-1原问题原问题 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 表表3：最优表：最优表jcBCBXjjzc4x1x2x3x5xb2x1x3x105062011B051006201011001AB-1原问题原问题 基列基列 常数列常数列 1/4 1/2-5/4 1 0 -1/4 1/415/2 0 1 1/2 -3/2cj-zj-15/2 0 0 -7/2 -3/24y1y2y3y5y2y3y 基列基列 常数列常数列 15/2 7/2 3/2 0

10、 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2cj-zj 0 0 0 -1/4 -1/24x1x2x3x5x2x1x3x对对偶偶问问题题最最优优表表原原问问题题最最优优表表对偶问题最优解对偶问题最优解 Y=（y1,y2,y3）=(0,1/4,1/2)松松 弛弛 变变 量量决策变量决策变量剩余变量剩余变量决决 策策 变变 量量原问题最优解原问题最优解 X=(x1,x2)T =(7/2,3/2)T 两个问题作一比较两个问题作一比较:1.两者的最优值相同两者的最优值相同2.从任一个问题的最优表，可以直接从任一个问题的最优表，可以直接找到另一个问题的最优解，对应关系找到另一个问题的最优解，对应关系2/17 wz原问题决策变量原问题决策变量原问题松弛变量原问题松弛变量对偶问题剩余变量对偶问题剩余变量 对偶问题决策变量对偶问题决策变量例例2 2、用单纯形表求解、用单纯形表求解LPLP问题所得最优表如下，问题所得最优表如下，试直接写出对偶问题最试直接写出对偶问题最优解。优解。12121212max2328416412,0zxxxxxxx xcjCB203XBx1x5x2b442 2 3 0 0 0 x1 x2 x3 x4 x5 1 0 0 0 0 0 -2 1 0 1 1/8 0（D）最优解（）最优解（3/2,1/8,0,0,0）