吉林大学远程教育 运筹学课件1.4.ppt

运 筹 学 主 讲 教 师 李 时 第一章 线性规划与单纯形法 §4 单纯形法 单纯形法的基本思想是：从可行域的一个基可行解（一个顶点）出发，判断该解是否为最优解，如果不是最优解就转移到另一个较好的基可行解，如果目标函数达到最优，则已得到最优解，否则继续转移到其他较好的基可行解。由于基可行解（顶点）数目有限，所以在一般情况下经过有限次迭代后就一定能求出最优解。 例8 计算下列线性规划 maxZ=3x1-x2-x3 x1-2x2 + x3≤11 -4x1+ x2 +2X3≥3  -2x1 + x3 =1 x1,x2 ,x3 ≥0 解 加入松弛变量及人工变量得 maxZ=3x1-x2-x3-Mx6-Mx7  x1-2x2 + x3+x4 =11 -4x1+ x2 +2X3 -x5+x6 =3  -2x1 + x3 +x7=1 x1,x2 ,x3 , x4 , x5 , x6,x7≥0   取（P4, P6,P7）= 为初始基B，列出初始单纯形表，并计算如下：  * * 4.1确定初始基可行解 对于线性规划问题 maxZ= CX （L） AX=b X≥0 我们首先介绍求初始基可行解的方法。 1.直接观察法 若给定问题标准化后（且b≥0）系数矩阵A中存在m个线性无关的单位列向量，则以这m个单位列向量构成的单位子矩阵作为初始基B，则XB=B-1b =b≥0，其余xj =0是基可行解。 例5 求例1问题的初始基可行解 maxZ=6x1+4x2 2x1+3x2≤100 4x1+2x2≤120 x1,x2≥0 2.大M法（人工变量法） 若给定问题标准化后(b≥0)系数矩阵中不存在m个线性无关的单位列向量,则在某些约束的左端加一个非负变xn+i量(人工变量),使得变化后的系数矩阵中恰有m个线性无关的单位列向量,并且在目标函数中减去这些人工变量与M的乘积(M是相当大正数).对于变化后的问题,取这m个单位列向量构成的单位子矩阵为初始基,该基对应的解一定是基可行解. 例6 求下面问题的初始基可行解 maxZ=3x1-x2- x3 x1-2x2+ x3≤11 -4x1+ x2 +2x3 ≥3 -2x1 + x3 = 1 x1,x2, x3≥0 显然,对任意形式的线性规划问题都可以用这种增加人工变量的方法“凑出”一个单位子矩阵作为初始可行基. 按这种方法变化得到的线性规划与原线性规划有如下关系: ⑴原问题的任一基可行解都是变化后的问题的基可行解. ⑵若变化后问题的最优解中不含有非零的人工变量,则该解就是原问题的最优解. ⑶若变化后问题的最优解中含有非零的人工变量,则原问题无可行解. 4.2 最优性检验 设线性规划（L）的可行基B=（P1,P2,…,Pm） 记A=（B，N），C=（CB，CN），X=（XB，XN)T 用B-1左乘约束方程组的两端，得 即 将 得 记 即有