单纯形法 (3)讲稿

1、关于单纯形法 (3)第一张，PPT共一百一十二页，创作于2022年6月一、问题的提出图解法只能解决二维的线性规划问题，那更多变量的问题怎么办？(jsj)通过代数算法搜寻最优解。单纯形法，就是这样的一种代数搜寻法。线性规划问题的解一般有无穷多个，如果不缩小搜寻范围，工作量太大！我们首先将最优解缩小在一个有限的范围。第二张，PPT共一百一十二页，创作于2022年6月一、问题的提出回顾图解法，我们知道：最优解必定在可行域的顶点上取得，而顶点的个数总是有限的。多维线性规划问题的可行域也存在有限个顶点。如果能够从一个顶点开始，通过某种方式向更优顶点转移，总会找到最优点。首先面临的问题：如何通过代数方法找

2、到第一个顶点？第三张，PPT共一百一十二页，创作于2022年6月一、问题的提出图解法中的例1.5模型为： Max z= 50 x1+100 x2 s.t. 1x1+1x2300 2x1+1 x2400 0 x1+1 x2250 x1 0， x2 0第四张，PPT共一百一十二页，创作于2022年6月一、问题的提出从其标准形的解向量开始研究： Max z= 50 x1+100 x2 s.t. 1x1+1x2+1x3+0 x4+0 x5300 2x1+1x2+0 x3+1x4+0 x5400 0 x1+1x2+0 x3+0 x4+1x5250 xj 0 (j=1,2,3,4,5)第五张，PPT共一百

3、一十二页，创作于2022年6月一、问题的提出顶点对应的解向量有何代数特征？O (0,0,300,400,250)A (0,250,50,150,0)B (50,250,0,50,0)C (100,200,0,0,50)D (200,0,100,0,50)答案：都有两个变量取值为0，且非负。X1X2O(0,0) A(0,250)B(50,250)C(100,200)D(200,0)第六张，PPT共一百一十二页，创作于2022年6月一、问题的提出既然顶点解向量中有两个变量取值为0，而标准形中又有三个约束方程，是否可以直接通过这种方式找顶点？如令x10，x20，则x3300，x4400，x5250可

4、得到解（0，0，300，400，250）第七张，PPT共一百一十二页，创作于2022年6月一、问题的提出又如：令x30，x50，由约束条件：x1+x2+x33002x1+x2+x4400 x2+x5250可得到解（50，250，0，50，0）第八张，PPT共一百一十二页，创作于2022年6月一、问题的提出若令x20，x50，会怎样？由约束方程可知：x1+x2+x3300 x1+x3300 2x1+x2+x4400 2x1+x4400 x2+x5250 0250？显然不能得到相应的解。第九张，PPT共一百一十二页，创作于2022年6月一、问题的提出为什么令x20，x50时不能得到解？因为其余三个

5、变量的系数列向量为该矩阵是非可逆矩阵，即去掉x2和x5后的三个约束方程线性相关，这种情况下得不到解。第十张，PPT共一百一十二页，创作于2022年6月一、问题的提出既然如此，如果我们在技术矩阵中取出三列，组成一个可逆阵，令其余两列对应的变量为零，则一定可以得到一个解。第十一张，PPT共一百一十二页，创作于2022年6月一、问题的提出如，取1、2、3列得到：此矩阵为可逆阵，故令x40，x50，一定可以得到一个解。对应的解为（75，250，-25，0，0）。第十二张，PPT共一百一十二页，创作于2022年6月一、问题的提出基的概念：已知A是约束条件的mn阶系数矩阵，其秩为m。设B是A矩阵中的一个非

6、奇异（可逆）的mm阶子矩阵，则称B为线性规划问题的一个基。B由A中的m个线性无关列向量组成。第十三张，PPT共一百一十二页，创作于2022年6月一、问题的提出一个基对应一组概念：非基变量基变量基向量非基向量对应基本解：（0，0，300，400，250）第十四张，PPT共一百一十二页，创作于2022年6月一、问题的提出(0,0,300,400,250)(0,300,0,100,-50)(0,400,-100,0,150)(0,250,50,150,0)(300,0,0,-200,-50)(200,0,100,0,50)不存在(100,200,0,0,50)(50,250,0,50,0)(75,2

7、50,-25,0,0)基本解是x3 ,x5p3 ,p5x1 ,x2 ,x4p1 ,p2 ,p4B2=(p1,p2 ,p4 )是x3 ,x4p3 ,p4x1 ,x2 ,x5p1 ,p2 ,p5B3=(p1 ,p2 ,p5) 是x1 ,x2p1 ,p2x3 ,x4 ,x5p3 ,p4 ,p5B10 =(p3,p4,p5)否x1 ,x3p1 ,p3x2 ,x4 ,x5p2 ,p4 ,p5B9=(p2,p4,p5)否x1 ,x4p1 ,p4x2 ,x3 ,x5p2 ,p3 ,p5B8=(p2 ,p3,p5)是x1 ,x5p1 ,p5x2 ,x3 ,x4p2 ,p3 ,p4B7=(p2 ,p3,p4)否

8、x2 ,x3p2 ,p3x1 ,x4 ,x5p1 ,p4 ,p5B6=(p1 ,p4 ,p5)是x2 ,x4p2 ,p4x1 ,x3 ,x5p1 ,p3 ,p5B5=(p1 ,p3 ,p5)x2 ,x5p2 ,p5x1 ,x3 ,x4p1 ,p3 ,p4B4=(p1 ,p3 ,p4) 否x4 ,x5p4 ,p5x1 ,x2 ,x3p1 ,p2 ,p3B1=(p1 ,p2 ,p3)是否可行非基变量非基向量基变量基向量基第十五张，PPT共一百一十二页，创作于2022年6月一、问题的提出基本解可能可行，也可能不可行。满足非负约束条件的基本解叫基本可行解，相应的基称为可行基。否则为非可行基。第十六张，

9、PPT共一百一十二页，创作于2022年6月一、问题的提出A：(0,250,50,150,0)B：(50,250,0,50,0)C：(100,200,0,0,50)D：(200,0,100,0,50)O：(0,0,300,400,250)E：(75,250,-25,0,0)F：(0,300,0,100,-50)G：(0,400,-100,0,150)H：(300,0,0,-200,-50)X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,0)G(0,400)E(75,250)F(0,300)H(300,0)第十七张，PPT共一百一十二页，创作于2022年6月一

10、、问题的提出线性规划解的集合关系：基本解最优解基本可行解可行解第十八张，PPT共一百一十二页，创作于2022年6月一、问题的提出显然，将搜索范围控制在基本可行解内，将大大减少搜索工作量。但是，即使取得一个基，得到的解还不一定可行。如何才能保证取得一个可行基呢？第十九张，PPT共一百一十二页，创作于2022年6月一、问题的提出总结：1、可行域顶点对应的解必为基本可行解：有n-m个变量取值为0，满足非负条件。2、一个基对应一组基本解，可能可行，也可能不可行；3、最优解必定在基本可行解中；第二十张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理单纯形法的基本思路：首先找到一个

11、顶点；然后判断它是否最优；如果不是，则通过更换顶点的方式找到更优的顶点；直到找到最优顶点。第二十一张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理第一步：找到一个顶点 （初始基本可行解）第二十二张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理思考：1、令n-m个变量为0（非基变量）是否一定可以找到？答案：不一定。如例中x20，x50时不能得到解。可行的办法：找到一个基。第二十三张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理2、一个基是否一定对应可行域顶点？答案：不一定。必须是可行基。一般来说，判断一个基是否是可行基

12、，需要在求出其基本解后才能判断。第二十四张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理3、那有没有办法在求出解之前保证我们取得的基为可行基？解决办法：保证右端项非负，找到一个单位矩阵，必定是一个可行基。第二十五张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理如范例系数阵：存在3阶单位阵（初始可行基）右端项非负第二十六张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理基本可行解为（0，0，300，400，250）此可行基称为初始可行基。对应的解称为初始基本可行解。初始基本可行解在上页矩阵中一目了然。第二十七张，PPT共

13、一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理第二步：最优性检验第二十八张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理对应于每一组基本解，目标函数都可以表示成非基变量的函数，称为典式。如：初始基本可行解（0，0，300，400，250）其非基变量为x1，x2目标函数为Max z= 50 x1+100 x2第二十九张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理典式Z= 50 x1+100 x2如果x1增加1，Z会怎样？答案：Z增加50。如果x2的值增加1，Z会怎样？答案：Z增加100。第三十张，PPT共一百一十二页，创作于2

14、022年6月二、单纯形法的基本思路和原理x1，x2的取值是否有增加的可能？分析：该解中非基变量 x1，x2的取值为0，其值完全有可能增加。说明此时目标函数值还有增加的可能，没有达到最优。第三十一张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理再如：基本解（50，250，0，50，0）其非基变量为x3，x5由约束方程可得：x150-x3+x5 x2250 -x5目标函数为Max z= 50 x1+100 x2 27500-50 x3-50 x5第三十二张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理典式Z= 27500-50 x3-50 x5如果x3增加1，Z会怎样？答案：Z减少50。如果x5的值增加1，Z会怎样？答案：Z减少50 。可见要使Z增加，只有使x3和x5减少。第三十三张，PPT共一百一十二页，创作于2022年6月二、单纯形法的基本思路和原理x3，x5的取值是否有减少的可能？分析：该解中非基变量 x1，x2的取值为0，其值不可能再减少。所以Z值不可能再增加。说明此基本解对应的目标函数值已经达到最优。第三十四张，PPT共一百一十二页，创作于20