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

课程名称：《运筹学》第_4_讲次2.4单纯型法（2）授课题目本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，掌握单纯形法的基本思想，学会用单纯形求解线性规划的一般方法。[重点及难点]利用单纯形求解线性规划。内容[本讲课程的引入]前面我们学习了线性规划解的基本概念以及用图解法解线性规划的方法，我们知道图解法只适合解决只含有两个决策变量的线性规划，这就造成了很大局限性。为了帮助大家更好的解决问题，今天我给大家介绍一种新的求解线性规划的方法一一单纯形法[本讲课程的内容]一、复习首先，让我们回忆一下几个重要概念：可行解、可行域、基、基变量、非基变量、基本解？（学生回答，教师点拨）二、新授以上这些概念对于我们解线性规划来讲都是十分重要的。下面我先给大家介绍单纯形方法的基本思想（板书：1、单纯形方法的基本思想）从可行域的一个基本可行解(极点)出发，判别它是否已是最优解，如果不是，寻找下一个基本可行解，并使目标函数得到改进，如此选代下去，直到找到最优解或判定该问题无界为止。（可以简单板书）好，下面我们就通过例题学习一下单纯形方法的解题思路（板书：2、单纯形方法的解题思路）出示例题（板书）例2.13求解线性规划：max== 50xi +30x24xl +3x2≤120s.t.2x; +X2≤50X,X2≥0

课程名称：《运筹学》 第 4 讲次 授课题目 2.4 单纯型法（2） 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，掌握单纯形法的基本思想，学会用单纯形求解线性规 划的一般方法。 [重点及难点] 利用单纯形求解线性规划。 内 容 [本讲课程的引入] 前面我们学习了线性规划解的基本概念以及用图解法解线性规划的方法，我们知道 图解法只适合解决只含有两个决策变量的线性规划，这就造成了很大局限性。为了帮助 大家更好的解决问题，今天我给大家介绍一种新的求解线性规划的方法——单纯形法 [本讲课程的内容] 一、复习 首先，让我们回忆一下几个重要概念：可行解、可行域、基、基变量、非基变量、基本解？（学 生回答，教师点拨） 二、新授 以上这些概念对于我们解线性规划来讲都是十分重要的。下面我先给大家介绍单纯形方法的基本 思想（板书：1、单纯形方法的基本思想） 从可行域的一个基本可行解(极点)出发，判别它是否已是最优解，如果不是，寻找下一个基本可 行解，并使目标函数得到改进，如此迭代下去，直到找到最优解或判定该问题无界为止。 （可以简单板书）好，下面我们就通过例题学习一下单纯形方法的解题思路（板书：2、单纯形 方法的解题思路） 出示例题（板书） 例 2.13 求解线性规划： max z = 50x1 + 30x2 s.t. 4x1 + 3x2  120 2x1 + x2  50 x1, x2  0

内容解：将原问题转化为标准型模型：max==50x+30x24x1 +3x2 +x3= 120S.1.2x1+x2+x4=50X ,23x4≥ 0选x3，x4为基变量（为什么？）转换为典则形式（用非基变量表示基变量和目标函数的形式称为关于基的典则形式）max==50xi+30x2s.1. X3 =120 -4x -3 x2x4 = 50-2 xI-x2XX2≥0寻找初始可行解：令非基变量为零，得到：x(1)=(0,0,120,50)，2()=0最优性检验：该解是最优解吗？（提出检验的方法和标准）第一次换基选代选xI入基。得到下列不等式关系：X =120-4xI-3x2≥0X4 = 50-2x1-x2≥0简化为：120-4x≥050-2≥0选xi=min(120/4,50/2)=25，才使上述不等式成立，并迫使x4为零：因此需令x4出基。新的典则方程变为：4x1+x3=120-3x2=50-2 x1X2 -X4化简后：z(2)= 1250 + 5 X2 -25 X4Xj = 25 - 0.5 x2 - 0.5 x42 x4X3=20-X2 +

内 容 解：将原问题转化为标准型模型： max z = 50x1+ 30x2 s.t. 4x1 + 3x2 + x3 = 120 2x1 + x2 + x4 = 50 x1 , x2 , x3 , x4  0 选 x3 , x4 为基变量（为什么？） 转换为典则形式（用非基变量表示基变量和目标函数的形式称为关于基的典则形式） max z = 50 x1 + 30 x2 s.t. x3 = 120 - 4 x1 - 3 x2 x4 = 50 - 2 x1 - x2 x1 , x2 , x3 , x4  0 寻找初始可行解：令非基变量为零， 得到： x (1) = (0, 0, 120, 50) T， z (1) = 0 最优性检验 : 该解是最优解吗？（提出检验的方法和标准） 第一次换基迭代 选 x1入基。得到下列不等式关系: x3 = 120 - 4 x1 - 3 x2  0 x4 = 50 - 2 x1 - x2  0 简化为：120 - 4 x1  0 50 - 2 x1  0 选 x1= min(120/4, 50/2) = 25, 才使上述不等式成立，并迫使 x4为零； 因此需令 x4出基。 新的典则方程变为: 4 x1 + x3 = 120 - 3 x2 2 x1 = 50 - x2 - x4 化简后： z (2) = 1250 + 5 x2 - 25 x4 x1 = 25 - 0.5 x2 - 0.5 x4 x3 = 20 - x2 + 2 x4

内容第二个基本可行解(25,0,20,0)，z(2)=1250第二次换基选代选x2入基。得到下列不等式关系：XI=25 - 0.5 x2 -0.5x4≥0X3 = 20 -X2+2x4≥0简化为：25-0.5x2≥020 -X2≥0选x2=min(25/0.5,20/1)=20时才能使不等式成立，并使x3为零，令x3出基。换基后的典则形式变为：z(3)=1350 -5 x3-15 x4x = 15 + 0.5 x3 - 1.5 x4x2=20 -x3+24第三个解为(15,20,0,0)，z(3)=1350;此时，目标函数表达式中非基变量的系数都为负，目标函数无法继续改进。所以，该线性规划的最优解为：（15,20,0,0)T最优值为：z(3)=1350小结：在推导过程中有几个非常关键的环节请大家一定要注意！（1）判断解的最优性的时候我们采取了什么方法？(2)在目标函数的典式中非基变量前面的系数，我们称之为检验数，只要检验数非负，则表明目标函数还有改进的余地，需要换基选代(3）换基的过程中如何选择进基变量和出基变量？（最大和最小θ原则）(4）判断线性规划有最优解的根据是什么？（所有的检验数都为非正）思考：（可以展开讨论）(1）在oj>0，若有某个ok对应x的系数列向量Pk≤0，则此问题的结论如何？（无界，停止计算）(2)在最后的结论中，当某个非基变量的检验数0时，线性规划问题最优解又如何呢？

内 容 第二个基本可行解 (25, 0, 20, 0) T , z (2)=1250 第二次换基迭代 选 x2入基。得到下列不等式关系: x1 = 25 - 0.5 x2 - 0.5x4  0 x3 = 20 - x2 + 2x4  0 简化为： 25 - 0.5 x2  0 20 - x2  0 选 x2 = min(25/0.5, 20/1) = 20 时才能使不等式成立，并使 x3为零， 令 x3 出基。 换基后的典则形式变为： z (3) = 1350 - 5 x3- 15 x4 x1 = 15 + 0.5 x3 - 1.5 x4 x2 = 20 - x3 + 2 x4 第三个解为(15, 20, 0, 0) T，z (3) = 1350； 此时，目标函数表达式中非基变量的系数都为负，目标函数无法继续改进。 所以，该线性规划的最优解为：(15, 20, 0, 0) T 最优值为： z (3) = 1350 小结：在推导过程中有几个非常关键的环节请大家一定要注意！ （1） 判断解的最优性的时候我们采取了什么方法？ （2） 在目标函数的典式中非基变量前面的系数，我们称之为检验数，只要检验数 非负，则表明目标函数还有改进的余地，需要换基迭代； （3） 换基的过程中如何选择进基变量和出基变量？（最大σ和最小θ原则） （4） 判断线性规划有最优解的根据是什么？（所有的检验数都为非正） 思考：（可以展开讨论） （1） 在σj ＞ 0 ，若有某个σk 对应 xk的系数列向量 Pk ≤ 0 ，则此问题的结 论如何？ （无界，停止计算） （2） 在最后的结论中，当某个非基变量的检验数σj= 0 时，线性规划问题最优解 又如何呢？

内容（有无穷多最优解）练习：用单纯形法求解线性规划问题maxz=2x -x,+x33x+X2+≤60X-2+2x≤10X + X2 -X ≤20X1,X2, X ≥0[本讲小结】今天我们给大家重点介绍了利用单纯形法求解线性规划的基本思想和方法，希望大家课下要很好的复习，争取熟练掌握其解题方法。[本讲课程的作业]用单纯形法解下列线性规划问题maxZ =3xj +X2 +3x32x+X2+X≤2X+2x2+3x3≤52xi +2x2 +x3≤6(X,X2,≥0

内 容 （有无穷多最优解） 练习： 用单纯形法求解线性规划问题 [本讲小结] 今天我们给大家重点介绍了利用单纯形法求解线性规划的基本思想和方法，希望大家 课下要很好的复习，争取熟练掌握其解题方法。 [本讲课程的作业] 用单纯形法解下列线性规划问题                  , , 0 2 2 6 2 3 5 2 2 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x max 3 1 2 3 3 Z  x  x  x max 2x1 x2 x3 z                     , , 0 20 2 10 3 60 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x