《第五章单纯形法》-精选·课件.ppt

第五章 单纯形法 一、问题的提出 二、单纯形法的基本思路和原理 三、单纯形法的表格形式 四、人工变量法 五、几种特殊情况 一、问题的提出 图解法只能解决二维的线性规划问题，那更多变量的问题怎么办？ 通过代数算法搜寻最优解。 单纯形法，就是这样的一种代数搜寻法。 线性规划问题的解一般有无穷多个，如果不缩小搜寻范围，工作量太大！ 我们首先将最优解缩小在一个有限的范围。 一、问题的提出 回顾图解法，我们知道：最优解必定在可行域的顶点上取得，而顶点的个数总是有限的。 多维线性规划问题的可行域也存在有限个顶点。 如果能够从一个顶点开始，通过某种方式向更优顶点转移，总会找到最优点。 首先面临的问题： 如何通过代数方法找到第一个顶点？ 一、问题的提出 图解法中的例1.5模型为： Max z= 50x1+100 x2  s.t. 1·x1+1·x2≤300 2·x1+1 ·x2≤400 0·x1+1 ·x2≤250 x1 ≥0， x2 ≥0 一、问题的提出 从其标准形的解向量开始研究： Max z= 50x1+100 x2  s.t. 1·x1+1·x2+1·x3+0·x4+0·x5＝300 2·x1+1·x2+0·x3+1·x4+0·x5＝400 0·x1+1·x2+0·x3+0·x4+1·x5＝250 xj ≥0 (j=1,2,3,4,5) 一、问题的提出 顶点对应的解向量有何代数特征？ 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，且非负。 一、问题的提出 既然顶点解向量中有两个变量取值为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 → x1+x3＝300 2x1+x2+x4＝400 → 2x1+x4＝400 x2+x5＝250 → 0＝250？ 显然不能得到相应的解。 一、问题的提出 为什么令x2＝0，x5＝0时不能得到解？ 因为其余三个变量的系数列向量为 该矩阵是非可逆矩阵，即去掉x2和x5后的三个约束方程线性相关，这种情况下得不到解。 一、问题的提出 既然如此，如果我们在技术矩阵中取出三列，组成一个可逆阵，令其余两列对应的变量为零，则一定可以得到一个解。 一、问题的提出 如，取1、2、3列得到： 此矩阵为可逆阵，故令x4＝0，x5＝0，一定可以得到一个解。 对应的解为（75，250，-25，0，0）。 一、问题的提出 基的概念： 已知A是约束条件的m×n阶系数矩阵，其秩为m。 设B是A矩阵中的一个非奇异（可逆）的m×m阶子矩阵，则称B为线性规划问题的一个基。 B由A中的m个线性无关列向量组成。 一、问题的提出 一个基对应一组概念： 一、问题的提出 一、问题的提出 基本解可能可行，也可能不可行。 满足非负约束条件的基本解叫基本可行解，相应的基称为可行基。 否则为非可行基。 一、问题的提出 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) 一、问题的提出 线性规划解的集合关系： 一、问题的提出 显然，将有哪些信誉好的足球投注网站范围控制在基本可行解内，将大大减少有哪些信誉好的足球投注网站工作量。 但是，即使取得一个基，得到的解还不一定可行。 如何才能保证取得一个可行基呢？ 一、问题的提出 总结： 1、可行域顶点对应的解必为基本可行解：有n-m个变量取值为0，满足非负条件。 2、一个基对应一组基本解，可能可行，也可能不可行； 3、最优解必定在基本可