华北理工大学：《运筹学》课程授课教案（讲稿，共八章）

运筹学讲稿第5次课2学时0上次课复习：单纯形判别法则求minz所对应的情况。本次课题（或教材章节题目）：$1.4初始可行基的求法一人工变量法0教学要求：掌握大M法、两阶段法重点：大M法、两阶段法：各目标函数及价值系数难点：大M法中价值系数的符号：两阶段法的送代方法教学手段及教具：多媒体教学。讲授内容及时间分配：$1.4.1大M法35分钟35分钟$1.4.2两阶段法81.4.3关于退化解的说明10分钟0P44,1120分钟P438、(1)(3)课后作业0《运筹学》钱颂迪主编清华大学出版社《运筹学教程》胡运权主编清华大学出版社参考资料《运筹学》牛映武主编西安交大出版社《运筹学应用案例》陶谦坎主编机械工业出版社注：本页为每次课教案首页第11页

运筹学讲稿 第 11 页 第 5 次课 2 学时 注：本页为每次课教案首页 上次课复习： 单纯形判别法则 求 min z 所对应的情况。 本次课题（或教材章节题目）：§1.4 初始可行基的求法——人工变量法 教学要求：掌握大 M 法、两阶段法 重 点：大 M 法、两阶段法；各目标函数及价值系数 难 点：大 M 法中价值系数的符号；两阶段法的迭代方法 教学手段及教具：多媒体教学。 讲授内容及时间分配： §1.4.1 大 M 法 35 分钟 §1.4.2 两阶段法 35 分钟 §1.4.3 关于退化解的说明 10 分钟 P44 11 20 分钟 课后作业 P43 8、（1）（3） 参考资料 《运筹学》 钱颂迪 主编 清华大学出版社 《运筹学教程》 胡运权 主编 清华大学出版社 《运筹学》 牛映武 主编 西安交大出版社 《运筹学应用案例》 陶谦坎 主编 机械工业出版社

运筹学讲稿$1.4初始可行基的求法一人工变量法$1.4.1大M法例15求下列LP问题的最优解maxz=3x,-x2 -x3X -2x2 +x ≤11-4x +x2 +2x, ≥3-2x+x, =1[,X2,X,≥0解z, = 3x, -X2 -X3 - Mx。-Mx7max=11X-2x2+X+X4=3- 4x, + X2 +2x3Xs+x6-2x+ X7 = 1+x.-[x,",x≥0表1-103-100ci-1-M-MCBXBbXiX2x3X6X4XsX711-20001110X43120-110-M-4X610000-M-2[1]1X7003-6M0-M0-1+M-1+3M3-20001010-1x4-M10[1] 00-11-2X61-21000-101X310a-1+M00-M-3M+12012[3]00-2-51x4-110100-11-2X2100-1-21001X3011000-10-3M+134001/32/3-5/31-2/3X1I-110100-11-2X29001-12/3-4/34/3-7/3X30000j-1/3-1/3-M+1/3-M+2/3$1.4.2两阶段法两阶段法是另一种处理人工变量的方法。它的第一阶段是先解辅助问题min w=X+x=11X, -2x, +Xs +x46=3-4x, +X2 +2x3-Xs +X6-2x,+ x, = 1+ x3[x,",x ≥0第12页

运筹学讲稿 第 12 页 §1.4 初始可行基的求法——人工变量法 §1.4.1 大 M 法 例 15 求下列 LP 问题的最优解 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ − + = − + + ≥ − + ≤ = − − , , 0 2 1 4 2 3 2 11 max 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x z x x x 解 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ − + + = − + + − + = − + + = = − − − − , , 0 2 1 4 2 3 2 11 max 3 1 7 1 3 7 1 2 3 5 6 1 2 3 4 1 1 2 3 6 7 x x x x x x x x x x x x x x z x x x Mx Mx L 表 1-10 cj 3 -1 -1 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 0 -M -M x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 [1] 1 0 0 0 -1 0 0 1 0 0 0 1 σj 3-6M -1+M -1+3M 0 -M 0 0 0 -M -1 x4 x6 x3 10 1 1 3 0 -2 -2 [1] 0 0 0 1 1 0 0 0 -1 0 0 1 0 -1 -2 1 σj 1 -1+M 0 0 -M 0 -3M+1 0 -1 -1 x4 x2 x3 12 1 1 [3] 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 2 1 0 -5 -2 1 σj 1 0 0 0 -1 0 -3M+1 3 -1 -1 x1 x2 x3 4 1 9 1 0 0 0 1 0 0 0 1 1/3 0 2/3 -2/3 -1 -4/3 2/3 1 4/3 -5/3 -2 -7/3 σj 0 0 0 -1/3 -1/3 -M+1/3 -M+2/3 §1.4.2 两阶段法 两阶段法是另一种处理人工变量的方法。它的第一阶段是先解辅助问题 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ − + + = − + + − + = − + + = = + , , 0 2 1 4 2 3 2 11 min 1 7 1 3 7 1 2 3 5 6 1 2 3 4 6 7 x x x x x x x x x x x x x x w x x L

运筹学讲稿表1-12000001Ci1XBbCBX2XsXiX3X4X6X70-211110001X4131210-40-1X611-200001[1]X7-1-300a61003-2010100-1x41101-20[1]0-1X601-2010001X30-100103oj2012301-2-50x41010100-1-2X201-2010001X30000011aj第二阶段：表1-133-100-1cibCBXBX2XiX3X4Xs0123001-2X41000-11-1X211000-2-1X31000ai-1300411/3 -2/3Xi10100-1-1X290012/3-4/3-1X3000-1/3oj-1/3$1.4.3关于退化解的说明第13页

运筹学讲稿 第 13 页 表 1-12 cj 0 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 x7 0 1 1 x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 [1] 1 0 0 0 -1 0 0 1 0 0 0 1 σj 6 -1 -3 0 1 0 0 0 1 0 x4 x6 x3 10 1 1 3 0 -2 -2 [1] 0 0 0 1 1 0 0 0 -1 0 0 1 0 -1 -2 1 σj 0 -1 0 0 1 0 3 0 0 0 x4 x2 x3 12 1 1 3 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 2 1 0 -5 -2 1 σj 0 0 0 0 0 1 1 第二阶段: 表 1-13 cj 3 -1 -1 0 0 CB XB b x1 x2 x3 x4 x5 0 -1 -1 x4 x2 x3 12 1 1 3 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 σj 1 0 0 0 -1 3 -1 -1 x1 x2 x3 4 1 9 1 0 0 0 1 0 0 0 1 1/3 0 2/3 -2/3 -1 -4/3 σj 0 0 0 -1/3 -1/3 §1.4.3 关于退化解的说明

运筹学讲稿第6次课2学时0上次课复习：大M法；两阶段法本次课题（或教材章节题目）：S1.5线性规划应用举例0教学要求：掌握建模方法重点：各类实际问题如下料问题、混配问题、零件装配问题等的建模方法。难点：实际问题线性规划模型的建立。教学手段及教具：多媒体教学。讲授内容及时间分配：下料问题20分钟混配问题30分钟零件装配问题20分钟0实际应用举例30分钟P412、(2)(3)课后作业0《运筹学》钱颂迪主编清华大学出版社《运筹学教程》胡运权主编清华大学出版社参考资料《运筹学》牛映武主编西安交大出版社《运筹学应用案例》陶谦坎主编机械工业出版社注：本页为每次课教案首页第14页

运筹学讲稿 第 14 页 第 6 次课 2 学时 注：本页为每次课教案首页 上次课复习： 大 M 法； 两阶段法 本次课题（或教材章节题目）：§1.5 线性规划应用举例 教学要求：掌握建模方法 重 点：各类实际问题如下料问题、混配问题、零件装配问题等的建模方法。 难 点：实际问题线性规划模型的建立。 教学手段及教具：多媒体教学。 讲授内容及时间分配： 下料问题 20 分钟 混配问题 30 分钟 零件装配问题 20 分钟 实际应用举例 30 分钟 课后作业 P41 2、（2）（3） 参考资料 《运筹学》 钱颂迪 主编 清华大学出版社 《运筹学教程》 胡运权 主编 清华大学出版社 《运筹学》 牛映武 主编 西安交大出版社 《运筹学应用案例》 陶谦坎 主编 机械工业出版社

运筹学讲稿$1.5线性规划应用举例例18利用长度为7.4米的角钢，要做成三边长为2.9米，2.1米，1.5米的三角架100套。如何下料，才能使消耗的原料最少？表1-14234578162.9米2111000002103212.1米0132310041.5米合计长7.37.16.57.46.37.26.660余料长0.10.30.91.10.20.81.4变量编号X2x4X6X7X3XsXiXgminz=X, +X2 +Xg +X4 +x,+X+X, +Xg=100x, +2x2+ X4+ X6(1.24)=100(1.25)2xg+2x4+xs+X+3x+ 4xg =1003xi + X2 +2x3+ 3xs + X6(1.26)X,",xg≥0例19某食品厂要用C，P，H三种原料混合加工成三种不同档次的产品A，B，C，已知三种产品中原料含量限制，原料成本和每月限制用量，三种产品的加工费和单价等资料如表1-16所示。该厂应当每月生产三种产品多少公斤，才能使利润最大？试建立问题的线性规划模型。表1-16BD每月原料限制（kg）原料单价（元/kg）A65c3000≥50%≥25%P25≤25%3000≤50%≤60%H3524004540产品单价（元/kg）60654产品加工费（元/kg）解z=11x, +29x,+19x,-25x4+15xs+5x-29x,+11xg+xgmax≤0x+x,+x≤0X,+3x2X3≤0 3x4 +Xs +X6≤0-x +X, -X-3x +2xg-3x,≤0≤3000+ X7Xi+ X4≤3000+ X5+ XgX2+x,≤2400X3+X6x≥0j=1,2....9第15页

运筹学讲稿 第 15 页 §1.5 线性规划应用举例 例 18 利用长度为 7.4 米的角钢，要做成三边长为 2.9 米，2.1 米，1.5 米的三角架 100 套。如何 下料，才能使消耗的原料最少？ 表 1-14 1 2 3 4 5 6 7 8 2.9 米 2.1 米 1.5 米 2 0 1 1 2 0 1 1 1 1 0 3 0 3 0 0 2 2 0 1 3 0 0 4 合计长 余料长 7.3 0.1 7.1 0.3 6.5 0.9 7.4 0 6.3 1.1 7.2 0.2 6.6 0.8 6 1.4 变量编号 x2 x4 x6 x1 x7 x3 x5 x8 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ + + + + + = + + + + = + + + = = + + + + + + + , , 0 3 2 3 4 100 2 2 3 100 2 100 min 1 8 1 2 3 5 6 8 3 4 5 6 7 1 2 4 6 1 2 3 4 5 6 7 8 x x x x x x x x x x x x x x x x x z x x x x x x x x L 例 19 某食品厂要用 C，P，H 三种原料混合加工成三种不同档次的产品 A，B，C，已知三种产 品中原料含量限制，原料成本和每月限制用量，三种产品的加工费和单价等资料如表 1-16 所示。该 厂应当每月生产三种产品多少公斤，才能使利润最大？试建立问题的线性规划模型。 表 1-16 A B D 每月原料限制（kg） 原料单价（元/kg） C P H ≥50% ≤25% — ≥25% ≤50% — — ≤60% — 3000 3000 2400 65 25 35 产品单价（元/kg） 60 45 40 产品加工费（元/kg） 6 5 4 解 ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ = + + ≤ + + ≤ + + ≤ − + − ≤ − + − ≤ − + + ≤ − + − ≤ − + + ≤ = − + + − + + − + + 0 1,2, 9 2400 3000 3000 3 2 3 0 0 3 0 3 0 0 max 11 29 19 25 15 5 29 11 3 6 9 2 5 8 1 4 7 7 8 9 4 5 6 4 5 6 1 2 3 1 2 3 1 2 3 4 5 6 7 8 9 x j L x x x x x x x x x x x x x x x x x x x x x x x x z x x x x x x x x x j （1.24） （1.25） （1.26）