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

课程名称：《运筹学》第_5_讲次2.4单纯形法（3）授课题目本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，进一步熟悉单纯形法的基本思想，学会用单纯形表求解线性规划。[重点及难点】利用单纯形表求解线性规划。内容[本讲课程的引入]上一讲我们学习了单纯形法的推导，今天我们继续给大家介绍利用单纯形法求解线性规划。首先让我们回忆一下单纯形方法的基本思想和解题思路。[本讲课程的内容]一、 复习1、单纯形方法的基本思想从可行域的一个基本可行解(极点)出发，判别它是否已是最优解，如果不是，寻找下一个基本可行解，并使目标函数得到改进，如此选代下去，直到找到最优解或判定该问题无界为止。2、单纯形方法的解题思路出示上次讲授的例题（板书）例2.13求解线性规划：max z=50xi +30x2s.t.4x+3x2≤1202x +x2≤50X,X2≥0结合上次讲过的例题简单回忆单纯形法的解题思路将原间题转化为标准型模型；选则基变量；转换为典则形式（用非基变量表示基变量和目标函数的形式称为关于基的典则形式）；寻找初始可行解（令非基变量为零）；最优性检验；换基代；得到新的典则方程.三、新授大家不难看出利用单纯形法的上述推导过程来求解很是繁琐，为了便于计算，我们设计了一种计

课程名称：《运筹学》 第 5 讲次 授课题目 2.4 单纯形法（3） 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，进一步熟悉单纯形法的基本思想，学会用单纯形表求解线性规划。 [重点及难点] 利用单纯形表求解线性规划。 内 容 [本讲课程的引入] 上一讲我们学习了单纯形法的推导，今天我们继续给大家介绍利用单纯形法求解线性规划。首先， 让我们回忆一下单纯形方法的基本思想和解题思路。 [本讲课程的内容] 一、复习 1、单纯形方法的基本思想 从可行域的一个基本可行解(极点)出发，判别它是否已是最优解，如果不是，寻找下一个基本可 行解，并使目标函数得到改进，如此迭代下去，直到找到最优解或判定该问题无界为止。 2、单纯形方法的解题思路 出示上次讲授的例题（板书） 例 2.13 求解线性规划： max z = 50x1 + 30x2 s.t. 4x1 + 3x2  120 2x1 + x2  50 x1, x2  0 结合上次讲过的例题简单回忆单纯形法的解题思路： 将原问题转化为标准型模型；选则基变量；转换为典则形式（用非基变量表示基变量和目标函数 的形式称为关于基的典则形式）；寻找初始可行解（令非基变量为零）； 最优性检验 ；换基迭代；得 到新的典则方程. 三、新授 大家不难看出利用单纯形法的上述推导过程来求解很是繁琐，为了便于计算，我们设计了一种计

内容算表，称为单纯形表：CIC2cncj-oiB-"bCBX....xnXIX20iXB列中填入基变量；CB列中填入基变量的价值系数，它们是与基变量相对应的；B"b’列中填入约束方程右端的常数；cj列中填入价值系数（j=1，2，,n）0i列中的数字是在确定换入变量后，按规则计算后填入：最后一行称为检验数行，对应各非基变量x,的检验数是：mo,=cj - Zcdg（边介绍边板书）=1计算步骤：(1)找出初始可行基，确定初始基可行解，建立初始单纯形表。(2)检验各非基变量xj的检验数oj，若oj≤0；则已得倒最优解，可停止计算，否则转入下一步。（注：当某个非基变量的检验数j0时，线性规划问题有无穷多最优界。）(3)在oj>0，若有某个ok对应x的系数列向量Pk≤0，则此问题无界，停止计算。否则，转入下一步。(4)根据max（oj>0）=ok，确定x为换入变量，按e规则计算=min（bilaikaik>0)，可确定x为换出变量。转入下一步。(5）以a为主元素进行迭代（即用高斯消去法或称为旋转运算），把x所对应的列向量Pk变换为第1个元素为的1单位列向量，将X列中的x换为x，得到新的单纯形表。重复（2）一（5），直到终止。现用例1来说明上述计算步骤：例 1求解线性规划：（略）解：将原问题转化为标准型模型：max z=50x+30x

内 容 算表，称为单纯形表： cj→ c1 c2 . cn θi CB XB B -1 b x1 x2 . xn σj XB列中填入基变量； CB列中填入基变量的价值系数，它们是与基变量相对应的； B -1 b＇列中填入约束方程右端的常数； cj 列中填入价值系数（j = 1，2，.,n） θi 列中的数字是在确定换入变量后，按θ规则计算后填入； 最后一行称为检验数行，对应各非基变量 xj 的检验数是： σj = cj － ∑ciaij 计算步骤： （边介绍边板书） （1） 找出初始可行基，确定初始基可行解，建立初始单纯形表。 （2） 检验各非基变量 xj 的检验数σj ，若σj ≤ 0 ；则已得倒最优解，可停止 计算，否则转入下一步。 （注：当某个非基变量的检验数σj= 0 时，线性 规划问题有无穷多最优界。） （3） 在σj ＞ 0 ，若有某个σk 对应 xk的系数列向量 Pk ≤ 0 ，则此问题无界， 停止计算。否则，转入下一步。 （4） 根据 max（σj ＞ 0）=σk，确定 xk 为换入变量，按θ规则计算θ= min（bi/aik| aik ＞ 0） ， 可确定 xl 为换出变量。转入下一步。 （5） 以 alk为主元素进行迭代（即用高斯消去法或称为旋转运算），把 xk所对应的 列向量 PK 变换为第 l 个元素为的 1 单位列向量，将 XB列中的 xl换为 xk，得 到新的单纯形表。重复（2）—（5），直到终止。 现用例 1 来说明上述计算步骤： 例 1 求解线性规划：（略） 解：将原问题转化为标准型模型： max z = 50x1+ 30x2 m i=1

内容4xi +3x2+X3=120S.t.+x4=502x +x23:x20X1X2X3（120，50,0,0）T得到初始的基本可行解为：建初始单纯形表如下：300500citeB'b'CBXBX1X2x3X40120431030x310201x45025a300050经过一次选代得：503000ci-eb'CBXBX1X2X3X4020011-220X3255010.500.550XI005-25经过二次选代ci-5030000b'XBXICBX2X3X4011-23020x21150-0.51.550Xi000-25-5经二次迭代后，最后一行的所有检验数都已为负或零。这表示目标函数值已不可能再增大，于是得到：最优解为x*=(15,25,00），最优值为z*=1350练习：例2.14用单纯形法求解线性规划问题maxz=2x,-x,+x3x+x+x≤60XX2+2x≤10X+x2-≤20XX2,x≥0

内 容 s.t. 4x1 + 3x2 + x3 = 120 2x1 + x2 + x4 = 50 x1 , x2 , x3 , x4  0 得到初始的基本可行解为： （120，50，0，0）T 建初始单纯形表如下： cj→ 50 30 0 0 θ CB XB B -1 b＇ x1 x2 x3 x4 0 x3 120 4 3 1 0 30 0 x4 50 2 1 0 1 25 σj 50 30 0 0 经过一次迭代得： 经过二次迭代 经二次迭代后，最后一行的所有检验数都已为负或零。这表示目标函数值已不可能 再增大，于是得到： 最优解为 x* = (15, 25, 0, 0)T , 最优值为 z* = 1350 练习：例 2.14 用单纯形法求解线性规划问题 cj→ 50 30 0 0 θ CB XB b＇ x1 x2 x3 x4 0 x3 20 0 1 1 -2 20 50 x1 25 1 0.5 0 0.5 50 σj 0 5 0 -25 cj→ 50 30 0 0 θ CB XB b＇ x1 x2 x3 x4 30 x2 20 0 1 1 -2 50 x1 15 1 0 -0.5 1.5 σj 0 0 -5 -25 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

内容解：引入松弛变量x4、x5、X6.标准化得maxZ=2xj-x2+x3= 60S. t. 3 x + X2 + X+ x4=10X1-2+2x3+Xs+ x6 = 0X1+X2-X3X1, X2 , X3, X4, X5, X6, ≥0建初始单纯形表，进行迭代运算：2-108b’Xb100CBxix2XAX6X3Xs11000603120X4-120100[10*10X510201-100120X62*-11009j40-51-37.50300X402101-1201---XI0100[2]-305*-11X601*-30-2oj001-201001-1X4201510.50.500.5XI5010-1-1.50.5-0.5X200-1.50-1.5-0.5gj由最优单纯形表可知原线性规划的最优解为：15,5,0，10,0,0）(最优值为：z*=25。【本讲小结】今天我们给大家重点介绍了利用单纯形表求解线性规划的方法，让我们一起回过头来思考一下，有哪些地方是我们尤其要注意的？

内 容 解：引入松弛变量 x4、 x5、 x6，标准化得， max 2 1 2 3 Z  x  x  x s. t. 3 x1 + x2 + x3+ x4 = 60 x 1- x 2 +2 x 3 + x5 = 10 x 1+ x 2- x 3 + x6 = 0 x 1, x 2 , x 3, x4, x5, x6，≥0 建初始单纯形表，进行迭代运算： CB Xb b’ 2 -1 1 0 0 0 θ x1 x2 x3 x4 x5 x6 0 x4 60 3 1 1 1 0 0 20 0 x5 10 [1] -1 2 0 1 0 10* 0 x6 20 1 1 -1 0 0 1 20 σj 2* -1 1 0 0 0 0 x4 30 0 4 -5 1 -3 0 7.5 2 x1 10 1 -1 2 0 1 0 - 0 x6 10 0 [2] -3 0 -1 1 5* σj 0 1* -3 0 -2 0 0 x4 10 0 0 1 1 -1 -2 2 x1 15 1 0 0.5 0 0.5 0.5 -1 x2 5 0 1 -1.5 0 -0.5 0.5 σj 0 0 -1.5 0 -1.5 -0.5 由最优单纯形表可知原线性规划的最优解为： ( 15 , 5 , 0，10，0，0 )T 最优值为： z*=25。 [本讲小结] 今天我们给大家重点介绍了利用单纯形表求解线性规划的方法，让我们一起回过头来 思考一下，有哪些地方是我们尤其要注意的？

内容[本讲课程的作业】用单纯形表解下列线性规划问题max Z = 3xj +x2 +3x32xi +x2 +X3≤2X+2x2+3x≤52x +2x2 +X ≤6[X,X2,X≥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