第二第二节 单纯形法形法Simplex Method一、一、单纯形法原理及步形法原理及步骤二、用向量矩二、用向量矩阵描画描画单纯形法原理形法原理三、三、单纯形表形表四、两四、两阶段法和大段法和大M法法五、退化和循五、退化和循环两阶段法和大两阶段法和大M M法法当不能经过转化规范方式使约束方程系数矩阵中出现单位矩阵时，此时可以经过添加人工变量的方法，人为地使系数矩阵中出现一个单位矩阵，以它作为初始可行基。例如: 设一线性规划问题的约束为人工变量法有两种方法：两阶段法和大M法。引进变量X4,X5基中不包含基中不包含单位矩位矩阵，因此无法直接，因此无法直接获得初始可行基。得初始可行基。两阶段法和大两阶段法和大M M法法X=(x1,x2,xn)T引进人工变量Xa=(xn+1,xn+2,xn+m)T根底可行解X=0,Xa=b非原问题的根底可行解两阶段法和大两阶段法和大M M法法 根本思想：根本思想：根本思想：根本思想： 人造解人造解人造解人造解 X0 X0 不是原不是原不是原不是原LPLP问题问题问题问题的根本可行解。的根本可行解。的根本可行解。的根本可行解。 但假但假但假但假设设设设能能能能经过单纯经过单纯经过单纯经过单纯形法的迭代步形法的迭代步形法的迭代步形法的迭代步骤骤骤骤，将，将，将，将虚虚虚虚拟拟拟拟 的人工的人工的人工的人工变变变变量都交量都交量都交量都交换换换换出去，都出去，都出去，都出去，都变为变为变为变为非基非基非基非基变变变变量量量量 即即即即 人工人工人工人工变变变变量量量量xn+1 = xn+2 = = xn+m = 0xn+1 = xn+2 = = xn+m = 0 ，那么那么那么那么X0X0的的的的 前前前前n n个分量就构成原个分量就构成原个分量就构成原个分量就构成原LPLP问题问题问题问题的一个根本可行的一个根本可行的一个根本可行的一个根本可行解。解。解。解。 反之，假反之，假反之，假反之，假设经过设经过设经过设经过迭代，不能把人工迭代，不能把人工迭代，不能把人工迭代，不能把人工变变变变量量量量都都都都变变变变 为为为为非基非基非基非基变变变变量，那么量，那么量，那么量，那么阐阐阐阐明原明原明原明原LPLP问题问题问题问题无可行解。无可行解。无可行解。无可行解。两阶段法和大两阶段法和大M M法法两两阶段法段法 阶段段 求解求解辅助助问题 构造辅助问题 (1)假设辅助问题的最优基B全部在A中，即Xa全部是非基变量min z=0，那么B为原问题的一个可行基。转阶段; (2)假设辅助问题的最优目的函数值min z0，那么至少有一个人工变量留在第一阶段问题最优解的基变量中，这时原问题无可行解。两阶段法和大两阶段法和大M M法法 阶阶段段 求解原求解原问题问题 以以阶阶段段的最的最优优基基B B作作为为原原问题问题的初始可行的初始可行基，求解原基，求解原问题问题，得到原，得到原问题问题的最的最优优基和最基和最优优解。解。例1 求解以下线性规划问题。两阶段法和大两阶段法和大M M法法引进松弛变量x3，x4，x50，得到添加人工变量x6，x70，构造辅助问题，并进入第一阶段求解。两阶段法和大两阶段法和大M M法法规范化并写出辅助问题的系数矩阵表：消去目的函数中基变量x6、x7的系数，得到初始单纯形表并进展单纯形变换：x2进基 X7离基Cj 0 0 0 0 0 1 1两阶段法和大两阶段法和大M M法法x1进基 X6离基第一阶段最优，z=0Cj 0 0 0 0 0 1 1- -两阶段法和大两阶段法和大M M法法在第一阶段最优单纯形表换入原问题的目的函数，去掉人工变量x6、x7以及相应的列，得到第二阶段的系数矩阵表：消去基变量x1、x2在目的函数中的系数，得到第二阶段问题的单纯形表：x4进基 X1离基Cj -1 2 0 0 0两阶段法和大两阶段法和大M M法法x3进基 X5离基问题的最优解为X=(x1,x2,x3,x4,x5)T=(0,3,1,2,0)T，max z=6 ，即min z=-6。Cj -1 2 0 0 0两阶段法和大两阶段法和大M M法法OABCD012123x1x2 第一阶段：在原问题的可行域外部进展基变换，第一阶段终了后进入可行域 第二阶段：从可行域内部的的一个极点B原问题的一个可行基开场，在可行域内部进展基变换基迭代道路基迭代道路两阶段法和大两阶段法和大M M法法 大大M法的根本步骤如下：法的根本步骤如下： 1引进松弛变量，使约束条件成为等式；引进松弛变量，使约束条件成为等式； 2假设约束条件的系数矩阵中不存在一个单位矩阵，假设约束条件的系数矩阵中不存在一个单位矩阵，那么引进人工变量；那么引进人工变量； 3在原目的函数中，加上人工变量，每个人工变量在原目的函数中，加上人工变量，每个人工变量的系数为一个充分大的正数的系数为一个充分大的正数M； 4用单纯形表求解以上问题，假设这个问题的最优用单纯形表求解以上问题，假设这个问题的最优解中有人工变量是基变量，那么原问题无可行解。假设最解中有人工变量是基变量，那么原问题无可行解。假设最优解中一切人工变量都离基，那么得到原问题的最优解。优解中一切人工变量都离基，那么得到原问题的最优解。两阶段法和大两阶段法和大M M法法例2 求解以下线性规划问题。引进松弛变量x4，x5并规范化两阶段法和大两阶段法和大M M法法引进人工变量x6，x70，在目的函数中添加人工变量列出系数矩阵表两阶段法和大两阶段法和大M M法法消去基变量x6、x7在目的函数中的系数x1进基 X6离基x3进基 X7离基Cj -2 -3 -1 0 0 -M -M两阶段法和大两阶段法和大M M法法已获得最优解，最优解为：x1，x2，x3，x4，x5，x6，x7(8，0，16，0，0，0，0)，max z=-32，即min z=32Cj -2 -3 -1 0 0 -M -M退化和循环退化和循环定定义2-6 设B是是线性性规划的一个可行基，划的一个可行基， XB=B-1b=(xB1,xB2,xBi,xBm)T 是是这个根底解中的基个根底解中的基变量。假量。假设其中至少有一个分量其中至少有一个分量xBi=0(i=1,2,m)，那么称此根底可行解是退化的。，那么称此根底可行解是退化的。 退化的构造对单纯形迭代会有不利的影响。当迭代进入一个退化极点时，能够出现以下情况： (1)进展进基、离基变换后，虽然改动了基，但没有改动极点，目的函数当然也不会改良。进展假设干次基变换后，才脱离退化极点，进入其他极点。这种情况会添加叠代次数，使单纯形法收敛的速度减慢。 (2)在非常特殊的情况下，退化会出现基的循环，一旦出现这样的情况，单纯形叠代将永远停留在同一极点上，因此无法求得最优解。退化和循环退化和循环 对此，Bland提出了一个防止循环的方法，在选择进基变量和离基变量时作了以下规定： 1在选择进基变量时，在一切检验数zj-cj0的非基变量中选取下标最小的进基； 2当有多个变量同时可作为离基变量时，选择下标最小的那个变量离基。这样就可以防止出现循环。 当然，用Bland的方法，由于选取进基变量时不再思索检验数zj-cj绝对值的大小，将会导致收敛速度的降低。需求掌握的知需求掌握的知识点：点：LP的规范方式LP的解的各种概念与方式单纯形法的原理单纯形法求解LP问题的步骤最终解的判别需求具需求具备的技的技艺：将LP问题转化为规范方式单纯形表格法求解LP问题第二节第二节 单纯形法单纯形法 总结总结下周见！