第三章2 单纯形法1.ppt

第二节 单纯形法 本节主要介绍单纯形法的计算步骤及线性规划解的讨论方面的内容 第二节 单纯形法 二、基本过程及主要方法 1．如何寻找初始基本可行解X（0）。 初始基本可行解就是迭代开始时的基本可行解。既然是基本可行解，必须和一个基本矩阵相对应，这个基本矩阵就是系数列向量组成的满秩矩阵（参看文献（3）中矩阵部分的内容），但对由m个系数列向量组成的矩阵判断是否满秩本身就是一件很不容易的事情，即使满秩了对应的解也不一定是可行解。参看课本16页例题的最后一部分。 以上分析说明，必须寻找一种简便而又合理的方法。下面就结合课本上的例题（为了便于大家验证计算结果）谈一谈寻找方法。 第二节 单纯形法 第二节 单纯形法 由可行解的概念，它还是可行的，所以就是基本可行解。 把初始可行解代入两个约束方程中，等式成立。由解析数学知识可知，以该解为坐标的点必然是以两个约束方程为解析式的图形的公共交点（顶点）。还可以这样理解，以这两个约束方程联立求得的解为坐标的点，必然是以两个约束方程为解析式的图形的公共交点（顶点）。这一点对理解单纯形法的基本过程尤为重要。 其实，所有由“≤”约束构成的线性规划问题模型一旦化成标准型，所有松弛变量对应的系数列向量必然构成一个满秩的基本矩阵（是单位矩阵）。 第二节 单纯形法 以松弛变量为基变量，求得的基本解也一定是基本可行解（因为标准型中等式约束右端的系数是大于或等于零的）。 对由“≥”型约束构成的线性规划模型，其基本矩阵的选取较为复杂。因为将“≥”型约束化为等式约束时，在原不等式的左边减去了一个多余变量，由于多余变量的系数为-1，虽然能构成基本矩阵，求出基本解，但不能得到可行解。下面结合例题讲述。 第二节 单纯形法 例题： max Z = - 6x1 - 4x2 2x1 + x2 ≥2 3x1 +4x2 ≥5 xj ≥ 0 j=1，2 分析； 对两个“≥”型约束，分别引入多余变量x3 、x4化为标准型如下。 第二节 单纯形法（1） max Z = - 6x1 - 4x2 2x1 + x2 –x3 =2 3x1 +4x2 -x4 =5 xj ≥ 0 j=1，2 由x3 、x4的系数列向量构成的矩阵仍然是一满秩矩阵，因而可以作为基本矩阵，但求出的基本解为：（x1，x2，x3，x4）=（0，0，-2，-5） 非基变量 基变量 基本解中有小于零的分量，所以不是可行解。看来，要想采用和“≤”型约束一致的方法寻求初始基本可行解是行不通的，必须寻求其它方法。 第二节 单纯形法（2） 通过上面的分析可以发现，得出的基本解之所以不可行，主要由于x3 、x4的系数为“-1”，那么能不能构造出一个系数为0或1的基本矩阵呢？答案是肯定的，但必须引入人工变量。 过程如下： 给约束1、2 分别引入人工变量x5，x6，（x5，x6≥0）并加在约束方程的左端。注意：在一个等式两端同时加上一个变量是合理的，但只在一端加上一个变量就是不合理的，这种行为必须受到惩罚，直到加上的变量成为零，这种做法才是合理的。 第二节 单纯形法 为此还要引入惩罚因子M，M是一个非常大的正数，用它和人工变量一起对目标函数进行修整，M的作用就是强制人工变量为零，一旦不为零该问题就没有最优解，关于这一点后面还有论述。这样上面的模型就变为： 第二节 单纯形法 第二节 单纯形法 第二节 单纯形法 第二节 单纯形法 （2）用下面的例子说明另一种方法。 如有一个约束条件方程是2X1+3X2-4X3=5,这可以用以下两个约束条件方程来代替： 2X1+3X2-4X3≤5 2X1+3X2-4X3≥5 在这两个方程中，可分别加进松弛变量或减多余变量加入人工变量，再求初始基本可行解，但是有些复杂，一般希望用第一种方法，也可用第四章的对偶单纯形法直接求解。 第二节 单纯形法 第二节 单纯形法 解：设各生产甲、乙、丙三种产品x1 、x2 、x3个单位，建立模型如下： max Z =4x1 +x2 +5x3 6x1 +3x2 +5x3 ≤45 3x1 +4x2 +5x3 ≤30 xj≥0，i=1，2，3 用单纯形法求解，先引入松弛变量x4 、x5化为标准型如下： 第二节 单纯形法 第二节 单纯形法