第5章 单纯形法 引例new.pptVIP免费

一、问题的提出图解法只能解决二维的线性规划问题，那更多变量的问题怎么办？通过代数算法搜寻最优解。单纯形法，就是这样的一种代数搜寻法。线性规划问题的解一般有无穷多个，如果不缩小搜寻范围，工作量太大！我们首先将最优解缩小在一个有限的范围。一、问题的提出回顾图解法，我们知道：最优解必定在可行域的顶点上取得，而顶点的个数总是有限的。多维线性规划问题的可行域也存在有限个顶点。如果能够从一个顶点开始，通过某种方式向更优顶点转移，总会找到最优点。首先面临的问题：如何通过代数方法找到第一个顶点？一、问题的提出图解法中的例1.5模型为：Maxz=50x1+100x2s.t.1·x1+1·x2≤3002·x1+1·x2≤4000·x1+1·x2≤250x1≥0，x2≥0一、问题的提出从其标准形的解向量开始研究：Maxz=50x1+100x2s.t.1·x1+1·x2+1·x3+0·x4+0·x5＝3002·x1+1·x2+0·x3+1·x4+0·x5＝4000·x1+1·x2+0·x3+0·x4+1·x5＝250xj≥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，且非负。X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,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时不能得到解？因为其余三个变量的系数列向量为110201000该矩阵是非可逆矩阵，即去掉x2和x5后的三个约束方程线性相关，这种情况下得不到解。一、问题的提出既然如此，如果我们在技术矩阵中取出三列，组成一个可逆阵，令其余两列对应的变量为零，则一定可以得到一个解。一、问题的提出如，取1、2、3列得到：111210010此矩阵为可逆阵，故令x4＝0，x5＝0，一定可以得到一个解。对应的解为（75，250，-25，0，0）。一、问题的提出基的概念：已知A是约束条件的m×n阶系数...