《运筹学》课程授课教案（讲稿）第6讲 单纯形法（4/4）

第_6_讲次课程名称：《运筹学》2.4单纯型法（4)授课题目本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，掌握一般线性规划求解的方法一一人工变量法。[重点及难点】人工变量法求解线性规划的基本思想。内容[本讲课程的引入]前面我们学习了求解线性规划的方法一一单纯形法，前提是该模型标准化之后能直接找到一个单位矩阵作基，如果没有单位矩阵怎么办呢？[本讲课程的内容]对所有约束条件是“≤”形式的不等式，可以利用化标准型的方法，在每个约束条件的左端加上一个松弛变量，从而得到一个初始可行基。对约束条件是“≥”形式的不等式或等式约束情况，可采用人造基方法。即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束则加上一个非负的人工变量，这样总能得到一个单位矩阵。因为人工变量是加入到原约束条件中的虚拟变量，要求将它们从基变量中逐个替换出来。若经过基的变换，基变量中不再含有非负的人工变量，这表示原问题有解。若在最终表中当所有i≤0而在其中还有某个人工变量，这表示无可行解。(一）大M法在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为此假定人工变量在目标函数中的系数为（-M）（M为任意大的正数），这样，目标函数要实现最大化时，必须把人工变量从基变量中换出，否则目标函数不可能实现最大化。举例用大M法求解：maxf=-2xl-3x22x1 +x2≤16s.t.xl +3x2≥20x+x2=10xl, x2≥0

课程名称：《运筹学》 第 6 讲次 授课题目 2.4 单纯型法（4） 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，掌握一般线性规划求解的方法——人工变量法。 [重点及难点] 人工变量法求解线性规划的基本思想。 内 容 [本讲课程的引入] 前面我们学习了求解线性规划的方法——单纯形法，前提是该模型标准化之后能直接找到一个单 位矩阵作基，如果没有单位矩阵怎么办呢？ [本讲课程的内容] 对所有约束条件是“≤”形式的不等式，可以利用化标准型的方法，在每个约束条件的左端加上 一个松弛变量，从而得到一个初始可行基。 对约束条件是“≥”形式的不等式或等式约束情况，可采用人造基方法。即对不等式约束减去一 个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束则加上一个非负的人工变量，这样 总能得到一个单位矩阵。 因为人工变量是加入到原约束条件中的虚拟变量，要求将它们从基变量中逐个替换出来。若经过 基的变换，基变量中不再含有非负的人工变量，这表示原问题有解。若在最终表中当所有σj ≤ 0 ， 而在其中还有某个人工变量，这表示无可行解。 （一） 大 M 法 在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为 此假定人工变量在目标函数中的系数为（-M）（M 为任意大的正数），这样，目标函数要实现最大化 时，必须把人工变量从基变量中换出，否则目标函数不可能实现最大化。 举例 用大 M 法求解： max f = -2x1 - 3x2 s.t. 2x1 + x2  16 x1 + 3x2  20 x1 + x2 = 10 x1, x2  0

内容00-2-3-m-m0BbX1X2X3X4XsX6CBXB00162101016x40201-10120/3(3)-mXs0010110110-mX602m00a4m-m5/301/31028/50X428/3-1/301/31-1/301/320-320/3X2001510/3(2/3)1/3-1/3-mX60202/3m1/3m0-4/3m0gj00-1/211/2-5/201X4501-3-1/201/2-1/2X2150-21/20Xi-1/23/225000-1/2a-m-m（二）两阶段法用电子计算机求解含人工变量的线性规划问题时，只能用很大的数代替M，这就可能造成计算上的错误。故介绍两阶段法求解线性规划问题。第一阶段：不考虑原问题是否存在基可行解：给原问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。然后用单纯形法求解，若得到最优解为0，则说明原问题存在基可行解，可以进行第二阶段计算。否则原问题无可行解，应停止计算。第二阶段：将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换成原问题目标函数的系数，作为第二阶段的初始表，用单纯形法求解。举例用两阶段法求解：maxf=-2x1 -3x2s.t.2xl +x2 ≤16x1 + 3x2≥20xl+x2=10xl,x2≥0

内 容 （二） 两阶段法 用电子计算机求解含人工变量的线性规划问题时，只能用很大的数代替 M，这就可能 造成计算上的错误。故介绍两阶段法求解线性规划问题。 第一阶段：不考虑原问题是否存在基可行解；给原问题加入人工变量，并构造仅含人 工变量的目标函数和要求实现最小化。然后用单纯形法求解，若得到最优解为 0，则说明 原问题存在基可行解，可以进行第二阶段计算。否则原问题无可行解，应停止计算。 第二阶段：将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换成 原问题目标函数的系数，作为第二阶段的初始表，用单纯形法求解。 举例 用两阶段法求解： max f = -2x1 - 3x2 s.t. 2x1 + x2  16 x1 + 3x2  20 x1 + x2 = 10 x1, x2  0 -2 -3 0 0 -m -m cB xB B -1b x1 x2 x3 x4 x5 x6  0 x4 16 2 1 0 1 0 0 16 -m x5 20 1 (3) -1 0 1 0 20/3 -m x6 10 1 1 0 0 0 1 10 σ j 2m 4m -m 0 0 0 0 x4 28/3 5/3 0 1/3 1 -1/3 0 28/5 -3 x2 20/3 1/3 1 -1/3 0 1/3 0 20 -m x6 10/3 (2/3) 0 1/3 0 -1/3 1 5 σ j 20 2/3m 0 1/3m 0 -4/3m 0 0 x4 1 0 0 -1/2 1 1/2 -5/2 -3 x2 5 0 1 -1/2 0 1/2 -1/2 -2 x1 5 1 0 1/2 0 -1/2 3/2 σ j 25 0 0 -1/2 0 -m -m

内容第一步：0000-1-1B'b0XiXBX2X3X4XsX6CB01621010016X401201(3)-10-120/3X510100011-110X624-100030gi28/55/31/31-1/30028/30X401/3101/302020/3-1/3X201/3015-110/3(2/3)-1/3X6010/32/301/30-4/3g1000-1/211/2 2-5/2x45001-1/201/2 -1/2X2510001/2-1/2 3/2X1000-10-1/2-1gi第二步-2-300CBXBB'beXiX2X3X4100X40-1/21-3501-1/20X25100-21/2xi00025-1/2gi练习：用两阶段法求解-3x1 +x2+x3min: 2=s.t.xl -2x2 +x3≤二1-4x1 +x2 + 2x3≥3-2x1+x3=1xl，x2，x3≥0（三）退化单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样

内 容 第一步： 第二步 练习： 用两阶段法求解: min: z = -3x1 + x2 + x3 s.t. x1 - 2x2 + x3  11 -4x1 + x2 + 2x3  3 -2x1 + x3 = 1 x1 , x2 , x3  0 （三） 退化 单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样 0 0 0 0 -1 -1 cB xB B -1b x1 x2 x3 x4 x5 x6  0 x4 16 2 1 0 1 0 0 16 -1 x5 20 1 (3) -1 0 1 0 20/3 -1 x6 10 1 1 0 0 0 1 10 σ j 30 2 4 -1 0 0 0 0 x4 28/3 5/3 0 1/3 1 -1/3 0 28/5 0 x2 20/3 1/3 1 -1/3 0 1/3 0 20 -1 x6 10/3 (2/3) 0 1/3 0 -1/3 1 5 σ j 10/3 2/3 0 1/3 0 -4/3 0 0 x4 1 0 0 -1/2 1 1/2 -5/2 0 x2 5 0 1 -1/2 0 1/2 -1/2 0 x1 5 1 0 1/2 0 -1/2 3/2 σ j 0 0 0 -1/2 0 -1 -1 -2 -3 0 0 CB xB B -1b x1 x2 x3 x4  0 x4 1 0 0 -1/2 1 -3 x2 5 0 1 -1/2 0 -2 x1 5 1 0 1/2 0 σ j 25 0 0 -1/2 0

内容在下一次选代中就有一个或几个基变量等于0，这就出现退化解。当出现退化时，进行多次选代，而基从B1，B2，又返回到B1，即出现了计算过程的循环，永达不到最优解。为解决此问题，1974年由勃兰特提出一种简便的规则，简称勃兰特规则：（1）选取j=cj一>0中下标最小的非基变量为换入变量。（2）当按规则计算存在两个或两个以上最小比值时，选取下标最小的基变量为换出变量。按勃兰特规则计算时，一般能避免出现循环。【本讲小结】今天我们学习了人工变量法，可以将那些标准化之后不能直接找到一个单位矩阵的线性规划通过引入人工变量的方法进一步求解。[本讲课程的作业】44页7.（1)

内 容 在下一次迭代中就有一个或几个基变量等于 0，这就出现退化解。当出现退化时，进行多 次迭代，而基从 B1 ，B2 ，.又返回到 B1 ，即出现了计算过程的循环，永达不到最优 解。为解决此问题，1974 年由勃兰特提出一种简便的规则，简称勃兰特规则： （1）选取σj = cj — zj ＞ 0 中下标最小的非基变量为换入变量。 （2）当按θ规则计算存在两个或两个以上最小比值时，选取下标最小的基变量为换 出变量。 按勃兰特规则计算时，一般能避免出现循环。 [本讲小结] 今天我们学习了人工变量法，可以将那些标准化之后不能直接找到一个单位矩阵的线 性规划通过引入人工变量的方法进一步求解。 [本讲课程的作业] 44 页 7.（1）