《运筹学胡运权清华版202单纯形算法的矩阵表ppt课件》由会员分享，可在线阅读，更多相关《运筹学胡运权清华版202单纯形算法的矩阵表ppt课件（22页珍藏版）》请在金锄头文库上搜索。
1、单纯形法的矩阵描画C 0基系数基列常数列X XS0XSbA Icj- zjC 0初始初始单纯形表形表线性规划问题：线性规划问题：规范型：规范型：一、初始单纯形表一、初始单纯形表二、迭代后的二、迭代后的单纯形表当前可行基形表当前可行基B 基列常数列X XSXB？ ？cj- zj？ ？那么表构造那么表构造分析：分析：初始表初始表迭代后任一表迭代后任一表初等行变换初等行变换初等行变换初等行变换左乘一个适当矩阵左乘一个适当矩阵S S？A、X、C可根据基可根据基B分块分块 现求基现求基B所对应的基可行解与目的值：所对应的基可行解与目的值：左乘左乘B-1令非基变量令非基变量XN，XS0基解基解目的值目的值
2、基列常数列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- 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
3、. 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 例例 知初始表和最优表如下，请将表中空白处数知初始表和最优表如下，请将表中空白处数字填上。字填上。cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x41-1-22x101/21/2-1x20-1/21/2cj-zj . 解：解：cj
4、2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x41-1-22x101/21/2-1x20-1/21/2cj-zj .B-1B=P4，P1，P2 解：解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x41-1-22x101/21/2-1x20-1/21/2cj-zj .B-1B-1b?10155 解：解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-12
5、0100x62011-1001cj-zj2-110000x4101-1-22x11501/21/2-1x250-1/21/2cj-zj .B-1B-1P3?11/2-3/2010001 解：解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x4100011-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 -C
6、BB-1假设假设B是最优基，那么下表是最优表是最优基，那么下表是最优表根据最优性断定定理根据最优性断定定理即：即：记记Y= CBB-1YYY是对偶问题的可行解，是对偶问题的可行解，目的值目的值w=Yb= CBB-1b=max z Y是普通型意是普通型意义义下下对对偶偶问题问题可行可行 解，解，仅仅由决策由决策变变量取量取值组值组成成 m维维 结论：当采用单纯形法求得原问题的一个结论：当采用单纯形法求得原问题的一个最优解的时候，检验行上同时得到对偶问最优解的时候，检验行上同时得到对偶问题的一个可行解，且两者具有一样的目的题的一个可行解，且两者具有一样的目的值。利用对偶性质，可以证明这个对偶问值。
7、利用对偶性质，可以证明这个对偶问题的解也为最优解。题的解也为最优解。例、以求解下面例、以求解下面LPLP问题以及它的对偶问题过程为问题以及它的对偶问题过程为例，验证前述结论例，验证前述结论对对偶偶问问题题原原问问题题 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 表表1：初始表：初始表B-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：迭代中：迭代中B-1原问题原问题 2 1 0 0
8、 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：最：最优表表B-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/2 基列基列 常数列常数列 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/2对对偶偶问问题题最最优优表表原原问问题题最最优优表表
9、对偶问题最优解对偶问题最优解 Y=y1, y2, y3 = (0, 1/4, 1/2)松松 弛弛 变变 量量决策变量决策变量剩余变量剩余变量决决 策策 变变 量量原问题最优解原问题最优解 X=(x1, x2)T =(7/2,3/2) T两个问题作一比较两个问题作一比较: :1. 1. 两者的最优值一样两者的最优值一样2. 2. 从任一个问题的最优表，可以从任一个问题的最优表，可以直接找到另一个问题的最优解，对直接找到另一个问题的最优解，对应关系应关系原问题决策变量原问题决策变量原问题松弛变量原问题松弛变量对偶问题剩余变量对偶问题剩余变量 对偶问题决策变量对偶问题决策变量例例2 2、用单纯形表求解、用单纯形表求解LPLP问题所得最优表如下，问题所得最优表如下，试直接写出对偶问题最试直接写出对偶问题最优解。优解。cj 2 3 0 0 0CBXBb x1 x2 x3 x4 x52x14 1 0 0 0 0x54 0 0 -2 1 3x22 0 1 1/8 0cjzj 0 0 -3/2 -1/8 0D最优解最优解3/2,1/8, 0,0,0
