《运筹学》胡运权清华版-2-02单纯形算法的矩阵表ppt课件

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

2、 XbBNSBXNXI 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

3、 XSXSb B N Icj- zj0 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 c1. cj. cn 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 例例 知初始表和最优表如下，请将表中空白处数知初始表和最优表如下，请

4、将表中空白处数字填上。字填上。cj2-11000CBXBbx1x2x3x4x5x60 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 x46031

5、11000 x5101-120100 x62011-1001cj-zj2-110000 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 x6

6、2011-1001cj-zj2-110000 x4100011-1-22x115101/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 2max212121221

8、xxxxxxxs.t.xxz0,y 125 26.32132132yyyyyyyts32152415minyyyw对对偶偶问问题题原原问问题题 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：迭代中：迭代中j

9、cBCBXjjzc4x1x2x3x5xb5x1x3x100060011B051006201011001AB-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

10、 -3/24y1y2y3y5y2y3y 基列基列 常数列常数列 15/2 7/2 3/2 0 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. 1. 两者的最优值一样两者的最优值一样 2. 2. 从任一个问题的最优表，可以从任一个问题的最优表，可以直接找到另一个问题的最优解，对直接找到另一个问题的最优解，对应关系应关系2/17 wz原问题决策变量原问题决策变量原问题松弛变量原问题松弛变量对偶问题剩余变量对偶问题剩余变量 对偶问题决策变量对偶问题决策变量例例2 2、用单纯形表求解、用单纯形表求解LPLP问题所得最优表如下，问题所得最优表如下，试直接写出对