第五章 单纯形法

第五章 单纯形法一、问题的提出二、单纯形法的基本思路和原理三、单纯形法的表格形式四、人工变量法五、几种特殊情况一、问题的提出v 图解法只能解决二维的线性规划问题，那更多变量的问题怎么办？v 通过代数算法搜寻最优解。v 单纯形法，就是这样的一种代数搜寻法。v 线性规划问题的解一般有无穷多个，如果不缩小搜寻范围，工作量太大！v 我们首先将最优解缩小在一个有限的范围。一、问题的提出v 回顾图解法，我们知道：最优解必定在可行域的顶点上取得，而顶点的个数总是有限的。v 多维线性规划问题的可行域也存在有限个顶点。v 如果能够从一个顶点开始，通过某种方式向更优顶点转移，总会找到最优点。v 首先面临的问题：v 如何通过代数方法找到第一个顶点？一、问题的提出 图解法中的例 1.5模型为： Max z= 50x1+100 x2 s.t. 1x1+1x23002x1+1 x24000x1+1 x2250x1 0， x2 0一、问题的提出 从其标准形的解向量开始研究： Max z= 50x1+100 x2 s.t. 1x1+1x2+1x3+0x4+0x5 3002x1+1x2+0x3+1x4+0x5 4000x1+1x2+0x3+0x4+1x5 250xj 0 (j=1,2,3,4,5)一、问题的提出v 顶点对应的解向量有何代数特征？v O (0,0,300,400,250)v A (0,250,50,150,0)v B (50,250,0,50,0)v C (100,200,0,0,50)v D (200,0,100,0,50)v 答案：都有两个变量取值为 0，且非负。X1X2O(0,0) A(0,250) B(50,250)C(100,200)D(200,0)一、问题的提出v既然顶点解向量中有两个变量取值为 0，而标准形中又有三个约束方程，是否可以直接通过这种方式找顶点？ 如令 x1 0， x2 0，则 x3 300， x4 400， x5 250 可得到解（ 0， 0， 300， 400， 250）一、问题的提出 又如：令 x3 0， x5 0， 由约束条件： x1+x2+x3 300 2x1+x2+x4 400 x2+x5 250 可得到解（ 50， 250， 0， 50， 0）一、问题的提出 若令 x2 0， x5 0，会怎样？ 由约束方程可知： x1+x2+x3 300 x 1+x3 300 2x1+x2+x4 400 2x 1+x4 400 x2+x5 250 0 250？ 显然不能得到相应的解。一、问题的提出 为什么令 x2 0， x5 0时不能得到解？ 因为其余三个变量的系数列向量为 该矩阵是非可逆矩阵，即去掉 x2和 x5后的三个约束方程线性相关，这种情况下得不到解。一、问题的提出v 既然如此，如果我们在技术矩阵中取出三列，组成一个可逆阵，令其余两列对应的变量为零，则一定可以得到一个解。一、问题的提出v 如，取 1、 2、 3列得到：v 此矩阵为可逆阵，故令 x4 0， x5 0，一定可以得到一个解。v 对应的解为（ 75， 250， -25， 0， 0）。一、问题的提出 基的概念： 已知 A是约束条件的 mn阶系数矩阵，其秩为 m。 设 B是 A矩阵中的一个非奇异（可逆）的mm阶子矩阵，则称 B为线性规划问题的一个 基 。 B由 A中的 m个线性无关列向量组成。一、问题的提出 一个基对应一组概念：非基变量 基变量基向量非基向量对应基本解：（ 0， 0， 300， 400， 250）一、问题的提出(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,250,-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)否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)是否可行非基变量非基向量基变量基向量基一、问题的提出 基本解可能可行，也可能不可行。 满足非负约束条件的基本解叫 基本可行解 ，相应的基称为 可行基 。 否则为 非可行基 。一、问题的提出v A： (0,250,50,150,0)v B： (50,250,0,50,0)v C： (100,200,0,0,50)v D： (200,0,100,0,50)v O： (0,0,300,400,250)v E： (75,250,-25,0,0)v F： (0,300,0,100,-50)v G： (0,400,-100,0,150)v 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)一、问题的提出v线性规划解的集合关系：基本解最优解基本可行解可行解一、问题的提出v显然，将搜索范围控制在基本可行解内，将大大减少搜索工作量。v但是，即使取得一个基，得到的解还不一定可行。v如何才能保证取得一个可行基呢？一、问题的提出 总结： 1、可行域顶点对应的解必为基本可行解：有 n-m个变量取值为 0，满足非负条件。 2、一个基对应一组基本解，可能可行，也可能不可行； 3、最优解必定在基本可行解中；二、单纯形法的基本思路和原理单纯形法的基本思路： 首先找到一个顶点； 然后判断它是否最优； 如果不是，则通过更换顶点的方式找到更优的顶点； 直到找到最优顶点。二、单纯形法的基本思路和原理第一步：找到一个顶点 （初始基本可行解）二、单纯形法的基本思路和原理 思考： 1、令 n-m个变量为 0（非基变量）是否一定可以找到？ 答案：不一定。 如例中 x2 0， x5 0时不能得到解。 可行的办法：找到一个基。二、单纯形法的基本思路和原理 2、一个基是否一定对应可行域顶点？ 答案：不一定。必须是可行基。 一般来说，判断一个基是否是可行基，需要在求出其基本解后才能判断。二、单纯形法的基本思路和原理 3、那有没有办法在求出解之前保证我们取得的基为可行基？ 解决办法：保证 右端项非负 ，找到一个单位矩阵 ，必定是一个可行基。二、单纯形法的基本思路和原理 如范例系数阵：存在 3阶单位阵（初始可行基）右端项非负二、单纯形法的基本思路和原理 基本可行解为 （ 0， 0， 300， 400， 250） 此可行基称为 初始可行基 。 对应的解称为 初始基本可行解 。 初始基本可行解在上页矩阵中一目了然。二、单纯形法的基本思路和原理第二步：最优性检验二、单纯形法的基本思路和原理 对应于每一组基本解，目标函数都可以表示成非基变量的函数，称为