运筹学讲稿第3次课2学时0上次课复习：线性规划的标准形式、特点；基可行解的概念。本次课题（或教材章节题目）：$1.3单纯形法0教学要求：掌握单纯形法的解题思路、单纯形法要点和单纯形表重点：单纯形表：单纯形法则难点：初始单纯形表：换基送代法则教学手段及教具：多媒体教学。讲授内容及时间分配：10分钟上次课复习及作业$1.3.1单纯形法的解题思路40分钟$1.3.2单纯形法要点和单纯形表40分钟0P437、(1)10分钟P437、(2)课后作业0《运筹学》钱颂迪主编清华大学出版社《运筹学教程》胡运权主编清华大学出版社参考资料《运筹学》牛映武主编西安交大出版社陶谦坎主编《运筹学应用案例》机械工业出版社注：本页为每次课教案首页第6页
运筹学讲稿 第 6 页 第 3 次课 2 学时 注：本页为每次课教案首页 上次课复习： 线性规划的标准形式、特点； 基可行解的概念。 本次课题（或教材章节题目）：§1.3 单纯形法 教学要求： 掌握单纯形法的解题思路、单纯形法要点和单纯形表 重 点：单纯形表；单纯形法则 难 点：初始单纯形表；换基迭代法则 教学手段及教具：多媒体教学。 讲授内容及时间分配： 上次课复习及作业 10 分钟 §1.3.1 单纯形法的解题思路 40 分钟 §1.3.2 单纯形法要点和单纯形表 40 分钟 P43 7、（1） 10 分钟 课后作业 P43 7、（2） 参考资料 《运筹学》 钱颂迪 主编 清华大学出版社 《运筹学教程》 胡运权 主编 清华大学出版社 《运筹学》 牛映武 主编 西安交大出版社 《运筹学应用案例》 陶谦坎 主编 机械工业出版社
运筹学讲稿$1.3单纯形法81.3.1单纯形法的解题思路由具体例题突出相关概念。$1.3.2单纯形法要点和单纯形表1.检验数的意义和计算公式HmaxC,xj=lxaij=m+I-Za2,x, = b2X2j=m+1Zamx,=bmx.+j=m+1X,X2x,≥0(1.19)o.caji=l2.单纯形表表 1-5..cj"*CmC1C2Cm+1CkCnb.....CBXBXi..XmXm+1XkXnX200bi1....lm+1...akainCIXib2010....C2X2a2m+1a2ka2n.....................bm001Xm...Amm+1amk...amnCm"m0000jc,aim+lCkZc,aikZc,aC.Cm+1L1=1i=li=l3.单纯形法的基本法则法则1最优性判定法则法则2换入变量确定法则设,=max(g,o,>0,则x为换入变量。I法则3换出变量确定法则b.b,ak0/=e=min(1.21)aikak再强调一下，这个法则的目的是，保证下一个基本解的可行性，违背这一法则，下一个基本解一定包含负分量，即不是可行解。第7页
运筹学讲稿 第 7 页 §1.3 单纯形法 §1.3.1 单纯形法的解题思路 由具体例题突出相关概念。 §1.3.2 单纯形法要点和单纯形表 1. 检验数的意义和计算公式 ∑= = n j j j z c x 1 max ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ + = + = + = ∑ ∑ ∑ = + = + = + , , 0 1 2 1 2 1 2 2 1 1 1 1 n m n j m m mj j n j m j j n j m j j x x x x a x b x a x b x a x b L LLLL ∑= = − m i j j iaij c c 1 σ （1.19） 2.单纯形表 表 1-5 cj c1 c2 . cm cm+1 . ck . cn CB XB b x1 x2 . xm xm+1 . xk . xn c1 c2 . cm x1 x2 . xm b1 b2 . bm 1 0 . 0 a1m+1 . a1k . a1n 0 1 . 0 a2m+1 . a2k . a2n . . . . . . 0 0 . 1 amm+1 . amk . amn σj 0 0 . 0 ∑= + − + m i m iaim c c 1 1 1 . ∑= − m i k iaik c c 1 . ∑= − m i n iain c c 1 3. 单纯形法的基本法则 法则 1 最优性判定法则 法则 2 换入变量确定法则 设 = max{ j j > 0} j σ k σ σ ，则 xk为换入变量。 法则 3 换出变量确定法则 lk l ik ik i i a b a a b = ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ θ = min > 0 （1.21） 再强调一下，这个法则的目的是，保证下一个基本解的可行性，违背这一法则，下一个基本解一 定包含负分量，即不是可行解
运筹学讲稿法则4换基选代运算法则z=2x, +5x2max2=8X +2x2 +X35x, +2x2= 20+ X44x2+x, =12[X1,X2,Xg,X4,X, ≥0表 1-625000cj0比CBXBbXiX2X3x4xs08211008/2X32052010020/2X40120001[4] 12/4xs2o5000200[1]0-1/22/1X31451000-1/214/5x45300101/4X2-20000-5/4221010-1/2X140-51200x45310001/4 X20j00-20-1/4最优解X=（(2,3，0，4，0)2=2X2+5X3=19。.第8页
运筹学讲稿 第 8 页 法则 4 换基迭代运算法则 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ + = + + = + + = = + , , , , 0 4 12 5 2 20 2 8 max 2 5 1 2 3 4 5 2 5 1 2 4 1 2 3 1 2 x x x x x x x x x x x x x z x x 表 1-6 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 θ比 0 0 0 x3 x4 x5 8 20 12 1 5 0 2 2 [4] 1 0 0 0 1 0 0 0 1 8/2 20/2 12/4 σj 2 5 0 0 0 0 0 5 x3 x4 x2 2 14 3 [1] 5 0 0 0 1 1 0 0 0 1 0 -1/2 -1/2 1/4 2/1 14/5 — σj 2 0 0 0 -5/4 2 0 5 x1 x4 x2 2 4 3 1 0 0 0 0 1 1 -5 0 0 1 0 -1/2 2 1/4 σj 0 0 -2 0 -1/4 最优解 X* =（2，3，0，4，0）T ，z * =2×2+5×3=19
运筹学讲稿第4次课2学时0上次课复习：单纯形表；单纯形法则；讲解作业3、（3）与4、（1）存在问题。本次课题（或教材章节题目）：$1.3单纯形法$1.3.3关于单纯形法的补充说明0教学要求：掌握无穷多最优解与唯一最优解的判别法则、无最优解（无界解）的判定法则；掌握求minz的情况。重点：单纯形判别法则难点：单纯形判别法则及证明；求minz的情况。教学手段及教具：多媒体教学。讲授内容及时间分配：20分钟上次课复习及作业1.无穷多最优解与唯一最优解的判别法则30分钟20分钟2.无最优解（无界解）的判定015分钟3.求minz的情况P437、(3)15分钟P437、(4)课后作业0《运筹学》主编钱颂迪清华大学出版社《运筹学教程》胡运权主编清华大学出版社参考资料《运筹学》牛映武主编西安交大出版社《运筹学应用案例》陶谦坎主编机械工业出版社注：本页为每次课教案首页第9页
运筹学讲稿 第 9 页 第 4 次课 2 学时 注：本页为每次课教案首页 上次课复习： 单纯形表； 单纯形法则； 讲解作业 3、（3）与 4、（1）存在问题。 本次课题（或教材章节题目）：§1.3 单纯形法 §1.3.3 关于单纯形法的补充说明 教学要求： 掌握无穷多最优解与唯一最优解的判别法则、无最优解（无界解）的判定法则； 掌握求 min z 的情况。 重 点：单纯形判别法则 难 点：单纯形判别法则及证明；求 min z 的情况。 教学手段及教具：多媒体教学。 讲授内容及时间分配： 上次课复习及作业 20 分钟 1. 无穷多最优解与唯一最优解的判别法则 30 分钟 2. 无最优解（无界解）的判定 20 分钟 3. 求 min z 的情况 15 分钟 P43 7、（3） 15 分钟 课后作业 P43 7、（4） 参考资料 《运筹学》 钱颂迪 主编 清华大学出版社 《运筹学教程》 胡运权 主编 清华大学出版社 《运筹学》 牛映武 主编 西安交大出版社 《运筹学应用案例》 陶谦坎 主编 机械工业出版社
运筹学讲稿$1.3.3关于单纯形法的补充说明1.无穷多最优解与唯一最优解的判别法则若对某可行解Xi，（1）所有检验数α，≤0，且有一个非基变量x的检验数等于0，则问题有无穷多最优解；（2）所有非基变量的检验数0<0，则问题有唯一最优解。例13讨论线性规划maxz= X +X2 +2x, -X4+X -X4=1xi+2x4=0-X,+X2[X,X2,X3,x4 ≥0的最优解的类型。解约束方程组已经是关于x3，x2的解出形式，直接列表求解：表1-8211-1CiCBXBbxiX2X3X421[1]01-1X31012-10X2000-19j0111-11X1110111X2000-1ai2.无最优解（无界解）的判定若对基可行解Xi，存在非基变量x的检验数>0，但ai≤0，i=1，2，，m即x的系数列向量无正分量，则问题无最优解。3.求minz的情况例14求例2中的LPminz=2x,+2x2+3x(1.22)[20x, +40x2=10-x4(1.23)10x+20x3-x=8[,x2,Xg,x4,x≥0的最优解。表 1-922300cjXBCBbxiX2X3X4Xs21/410-1/400[1/2]X232/51/2010-1/20X3-1/2003/20oi1/2021/2120-1/200Xi30-113/201/40-1/20X300111/403/20第10页
运筹学讲稿 第 10 页 §1.3.3 关于单纯形法的补充说明 1. 无穷多最优解与唯一最优解的判别法则 若对某可行解 X1，（1）所有检验数σj≤0，且有一个非基变量 xk的检验数等于 0，则问题有无穷 多最优解；（2）所有非基变量的检验数σj<0，则问题有唯一最优解。 例 13 讨论线性规划 ⎪ ⎩ ⎪ ⎨ ⎧ ≥ − + + = + − = = + + − , , , 0 2 0 1 max 2 1 2 3 4 1 2 4 1 3 4 1 2 3 4 x x x x x x x x x x z x x x x 的最优解的类型。 解 约束方程组已经是关于 x3，x2 的解出形式，直接列表求解： 表 1-8 cj 1 1 2 -1 CB XB b x1 x2 x3 x4 2 1 x3 x2 1 0 [1] -1 0 1 1 0 -1 2 σj 0 0 0 -1 1 1 x1 x2 1 1 1 0 0 1 1 1 -1 1 σj 0 0 0 -1 2. 无最优解（无界解）的判定 若对基可行解 X1，存在非基变量 xk的检验数σk>0，但 aik≤0，i=1，2，.，m 即 xk的系数列向 量无正分量，则问题无最优解。 3.求 min z 的情况 例 14 求例 2 中的 LP ⎪ ⎩ ⎪ ⎨ ⎧ ≥ + − = + − = = + + , , , , 0 10 20 8 20 40 10 min 2 2 3 1 2 3 4 5 1 3 5 1 2 4 1 2 3 x x x x x x x x x x x z x x x 的最优解。 表 1-9 cj 2 2 3 0 0 CB XB b x1 x2 x3 x4 x5 2 3 x2 x3 1/4 2/5 [1/2] 1/2 1 0 0 1 -1/40 0 0 -1/20 σj -1/2 0 0 1/20 3/20 2 3 x1 x3 1/2 3/20 1 0 2 -1 0 1 -1/20 1/40 0 -1/20 σj 0 1 0 1/40 3/20 （1.22） （1.23）