运筹学教案

第 1 次课 2 学时

上次课复习： 本次课题（或教材章节题目）：绪论、第一章 线性规划与单纯形法 §1.1 线性规划的基本概念 教学要求： 掌握运筹学发展历史、主要分支及工作步骤；掌握线性规划一般形式特点及图解法。 重 点：运筹学的工作步骤、线性规划一般形式、图解法。 难 点：线性规划一般形式及特点、线性规划图解法。 教学手段及教具：多媒体教学。 讲授内容及时间分配： 一、运筹学简史 二、运筹学的主要分支 三、运筹学的工作步骤 第一章 线性规划与单纯形法 §1.1 线性规划的基本概念 §1.1.1线性规划的数学模型 §1.1.2图解法 课后作业 30分钟 10分钟 10分钟 20分钟 30分钟 P42 3、（1）、（3） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 1 页

南 京 工 业 大 学 教 案 用 纸

绪 论

运筹学（operations research）是用数学方法研究各类系统最优化问题的学科。运筹学通过建立系统的数学模型并求解，为决策者制定最优决策提供科学依据。

一、运筹学简史

二、运筹学的主要分支

1. 线性规划（Linear Programming） 2. 目标规划（Goal Programming） 3. 整数规划（Integer Programming）

4. 非线性规划（Nonlinear Programming） 5. 动态规划（Dynamic Programming）

6. 图论与网络分析（Graph Theory and Network Analysis） 7. 排队论（Queuing Theory） 8. 存贮论（Inventory Theory） 9. 对策论（Game Theory） 10. 决策论（Decision Theory） 三、运筹学的工作步骤 1. 提出和形成问题 2. 收集资料，确定参数 3. 建立模型

4. 模型求解和检验 5. 解的控制

第一章 线性规划与单纯形法 §1.1 线性规划的基本概念

§1.1.1线性规划的数学模型 特点：

（1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值； （2）变量的变化要受某些，这些条件用一些线性等式或不等式表示； （3）有一个需要优化的目标，它也是变量的线性函数。

具备以上三个特点的数学模型称为线性规划（Linear Programming，简记为LP），一般形式为：

max(min) zc1x1c2x2cnxna11x1a12x2a1nxn(,)b1axaxax(,)b2112222nn2   axaxax(,)bm22mnnmm11x1,x2,xn0采用求和符号Σ，可以简写为：

max(min) zcjxjj1n nax(,)b i1,2,,miijj j1x0 j1,2,,nj第 2 页

南 京 工 业 大 学 教 案 用 纸

§1.1.2图解法 1. 唯一最优 例4

max z2x15x2 x12x285x2x20 12 4x212 x1,x20

x2 5 x2=－2/5x1+z/5 4 Q4 3 2 1 0 l2 5x1+2x2=20 Q3 Q2 Q1 1 2 3 4 5 6 图1-1

l3 4x2=12 l1 x1+2x2=8 x1 2. 无穷多最优

3. 无界解（无最优解）

第 3 页

南 京 工 业 大 学 教 案 用 纸

第 2 次课 2 学时

上次课复习： 线性规划一般形式及特点； 线性规划图解法。 本次课题（或教材章节题目）：§1.2 线性规划的标准形式和解的性质 教学要求： 掌握线性规划的标准形式、基可行解的概念及LP解的性质 重 点：线性规划的标准形式、特点、基可行解的概念及LP解的性质 难 点：线性规划的标准形式、基可行解的概念。 教学手段及教具：多媒体教学。 讲授内容及时间分配： 上次课复习 §1.2.1 LP的标准形式 §1.2.2 LP的基可行解的概念 §1.2.3 LP解的性质 5分钟 30分钟 50分钟 15分钟 课后作业 P42 4、（1）、（2） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 4 页

南 京 工 业 大 学 教 案 用 纸

§1.2 线性规划的标准形式和解的性质

§1.2.1 LP的标准形式

max zcjxjj1n（1.4）

naxb i1,2,,m iijj j1x0 j1,2,,nj变换一般LP为标准形式的方法：

（1）如果原问题目标函数求极小值：min zn（1.5） （1.6）

cj1njxj

令z1=－z，转化为求max z1(cj1j)xj。

（2）若某个右端常数bi<0，则以－1乘该约束两端。

（3）若某约束为“≤”型的不等式约束，则在左端加上一个非负变量，称为松弛变量，使不等式化为等式；若某约束为“≥”型，则在左端减去一个非负变量，称为剩余变量，或者仍然称为松弛变量，使不等式转化为等式。

′′

（4）若某个xj的符号约束为xj≤0；那么令xj=－xj，则xj≥0；若某个xj无符号，则可令xj=xj′－xj″，其中xj′≥0，xj″≥0。

§1.2.2 LP的基可行解的概念

max zCXAXb X0

max zCXnPjxjb j1x,,x0n1设系数矩阵A的秩是m，即A的m个行向量是线性无关的。若B是A的m阶满秩子阵，称B为问题的一个基。设B=（Pj1，Pj2，…，Pjm），称对应的变量xj1，xj2，…，xjm为基变量，其它的变量称为非基变量。令非基变量等于0，从方程组可以唯一解出基变量的值，从而得到方程组的一个

解，称为基本解；如果它的各个分量非负，即它同时又是可行解，则称之为基可行解，对应的基称为可行基。

§1.2.3 LP解的性质 1. 凸集和极点

2.线性规划解的性质

定理1 线性规划的可行域R是凸集。

定理2 X是线性规划基可行解的充分必要条件是X是可行域的极点。

定理3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。

第 5 页

南 京 工 业 大 学 教 案 用 纸

第 3 次课 2 学时

上次课复习： 线性规划的标准形式、特点； 基可行解的概念。 本次课题（或教材章节题目）：§1.3 单纯形法 教学要求： 掌握单纯形法的解题思路、单纯形法要点和单纯形表 重 点：单纯形表；单纯形法则 难 点：初始单纯形表；换基迭代法则 教学手段及教具：多媒体教学。 讲授内容及时间分配： 上次课复习及作业 §1.3.1 单纯形法的解题思路 §1.3.2 单纯形法要点和单纯形表 P43 7、（1） 10分钟 40分钟 40分钟 10分钟 课后作业 P43 7、（2） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 6 页

南 京 工 业 大 学 教 案 用 纸

§1.3 单纯形法

§1.3.1 单纯形法的解题思路 由具体例题突出相关概念。

§1.3.2 单纯形法要点和单纯形表 1. 检验数的意义和计算公式

max zcjxj

j1nn a1jxjb1x1 jm1n a2jxjb2 x2 jm1   n xmamjxjbmjm1x1,x2,xn0m jcj2.单纯形表

表1-5 cj CB c1 c2 … cm XB b b1 b2 … bm caii1ij （1.19）

c1 c2 … cm cm+1 … ck … cn x1 x2 … xm xm+1 … xk … xn 1 0 … 0 a1m+1 … a1k … a1n 0 1 … 0 a2m+1 … a2k … a2n … … … … … … 0 0 … 1 amm+1 … amk … amn 0 0 … 0 cm1x1 x2 … xm σj caii1mim1 … ckcaii1mik … cncaii1min 3. 单纯形法的基本法则 法则1 最优性判定法则 法则2 换入变量确定法则

设kmaxjj0，则xk为换入变量。

j法则3 换出变量确定法则

minibibaik0l aikalk （1.21）

再强调一下，这个法则的目的是，保证下一个基本解的可行性，违背这一法则，下一个基本解一

定包含负分量，即不是可行解。

第 7 页

南 京 工 业 大 学 教 案 用 纸

法则4 换基迭代运算法则

max z2x15x2 8 x12x2x3 5x2x x4 20 12 4x2 x512 x1,x2,x3,x4,x50表1-6 cj CB 0 0 0 0 0 5 2 0 5 XB b 8 20 12 2 14 3 2 4 3 2 5 0 0 0 θ比 8/2 20/2 12/4 2/1 14/5 — x1 1 5 0 2 [1] 5 0 2 1 0 0 0 x2 2 2 [4] 5 0 0 1 0 0 0 1 0 x3 1 0 0 0 1 0 0 0 1 -5 0 -2 x4 0 1 0 0 0 1 0 0 0 1 0 0 x5 0 0 1 0 -1/2 -1/2 1/4 -5/4 -1/2 2 1/4 -1/4 x3 x4 x5 σj x3 x4 x2 σj x1 x4 x2 σj 最优解X*=（2，3，0，4，0）T，z*=2×2+5×3=19。

第 8 页

南 京 工 业 大 学 教 案 用 纸

第 4 次课 2 学时

上次课复习： 单纯形表； 单纯形法则； 讲解作业3、（3）与4、（1）存在问题。 本次课题（或教材章节题目）：§1.3 单纯形法 §1.3.3 关于单纯形法的补充说明 教学要求： 掌握无穷多最优解与唯一最优解的判别法则、无最优解（无界解）的判定法则； 掌握求min z 的情况。 重 点：单纯形判别法则 难 点：单纯形判别法则及证明；求min z 的情况。 教学手段及教具：多媒体教学。 讲授内容及时间分配： 上次课复习及作业 1. 无穷多最优解与唯一最优解的判别法则 2. 无最优解（无界解）的判定 3. 求min z 的情况 P43 7、（3） 课后作业 P43 7、（4） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 20分钟 30分钟 20分钟 15分钟 15分钟 参考资料 注：本页为每次课教案首页

第 9 页

南 京 工 业 大 学 教 案 用 纸

§1.3.3 关于单纯形法的补充说明

1. 无穷多最优解与唯一最优解的判别法则

若对某可行解X1，（1）所有检验数σj≤0，且有一个非基变量xk的检验数等于0，则问题有无穷多最优解；（2）所有非基变量的检验数σj<0，则问题有唯一最优解。

例13 讨论线性规划

max zx1x22x3x4x3 x41 x1  2x40x1x2 x,x,x,x01234的最优解的类型。

解 约束方程组已经是关于x3，x2的解出形式，直接列表求解： 表1-8 cj CB 2 1 1 1 XB b 1 0 1 1 1 1 2 -1 x1 [1] -1 0 1 0 0 x2 0 1 0 0 1 0 x3 1 0 0 1 1 0 x4 -1 2 -1 -1 1 -1 x3 x2 σj x1 x2 σj 2. 无最优解（无界解）的判定

若对基可行解X1，存在非基变量xk的检验数σk>0，但aik≤0，i=1，2，…，m即xk的系数列向量无正分量，则问题无最优解。

3.求min z 的情况 例14 求例2中的LP

min z2x12x23x3

x4 1020x140x2  20x3 x5810x1 x,x,x,x,x012345（1.22） （1.23）

的最优解。

表1-9

cj CB 2 3 2 3 XB b 1/4 2/5 1/2 3/20 2 2 3 0 0 x1 [1/2] 1/2 -1/2 1 0 0 x2 1 0 0 2 -1 1 x3 0 1 0 0 1 0 x4 -1/40 0 1/20 -1/20 1/40 1/40 x5 0 -1/20 3/20 0 -1/20 3/20 x2 x3 σj x1 x3 σj 第 10 页

南 京 工 业 大 学 教 案 用 纸

第 5 次课 2 学时

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

11 第 页

南 京 工 业 大 学 教 案 用 纸

§1.4 初始可行基的求法——人工变量法

§1.4.1 大M法

例15 求下列LP问题的最优解

max z3x1x2x3 x12x2x3114xx2x3 123 x312x1 x1,x2,x30解

max z13x1x2x3Mx6Mx7 11 x12x2x3x4 4xx2x x5x6 3 123 x3 x712x1 x1,,x70表1-10 cj CB 0 -M -M 0 -M -1 0 -1 -1 3 -1 -1 XB b 11 3 1 10 1 1 12 1 1 4 1 9 3 -1 -1 0 0 -M -M x1 1 -4 -2 3-6M 3 0 -2 1 [3] 0 -2 1 1 0 0 0 x2 -2 1 0 -1+M -2 [1] 0 -1+M 0 1 0 0 0 1 0 0 x3 1 2 [1] -1+3M 0 0 1 0 0 0 1 0 0 0 1 0 x4 1 0 0 0 1 0 0 0 1 0 0 0 1/3 0 2/3 -1/3 x5 0 -1 0 -M 0 -1 0 -M -2 -1 0 -1 -2/3 -1 -4/3 -1/3 x6 0 1 0 0 0 1 0 0 2 1 0 0 2/3 1 4/3 -M+1/3 x7 0 0 1 0 -1 -2 1 -3M+1 -5 -2 1 -3M+1 -5/3 -2 -7/3 -M+2/3 x4 x6 x7 σj x4 x6 x3 σj x4 x2 x3 σj x1 x2 x3 σj §1.4.2 两阶段法

两阶段法是另一种处理人工变量的方法。它的第一阶段是先解辅助问题

min wx6x7 11 x12x2x3x4 4xx2x x5x6 3 123 x3 x712x1 x1,,x70第 12 页

南 京 工 业 大 学 教 案 用 纸

表1-12

cj CB 0 1 1 0 1 0 0 0 0 XB b 11 3 1 10 1 1 12 1 1 0 0 0 0 0 1 1 x1 1 -4 -2 6 3 0 -2 0 3 0 -2 0 x2 -2 1 0 -1 -2 [1] 0 -1 0 1 0 0 x3 1 2 [1] -3 0 0 1 0 0 0 1 0 x4 1 0 0 0 1 0 0 0 1 0 0 0 x5 0 -1 0 1 0 -1 0 1 -2 -1 0 0 x6 0 1 0 0 0 1 0 0 2 1 0 1 x7 0 0 1 0 -1 -2 1 3 -5 -2 1 1 x4 x6 x7 σj x4 x6 x3 σj x4 x2 x3 σj 第二阶段: 表1-13

cj CB 0 -1 -1 3 -1 -1 XB b 12 1 1 4 1 9 3 -1 -1 0 0 x1 3 0 -2 1 1 0 0 0 x2 0 1 0 0 0 1 0 0 x3 0 0 1 0 0 0 1 0 x4 1 0 0 0 1/3 0 2/3 -1/3 x5 -2 -1 0 -1 -2/3 -1 -4/3 -1/3 x4 x2 x3 σj x1 x2 x3 σj

§1.4.3 关于退化解的说明

第 13 页

南 京 工 业 大 学 教 案 用 纸

第 6 次课 2 学时

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

第 14 页

南 京 工 业 大 学 教 案 用 纸

§1.5线性规划应用举例

例18 利用长度为7.4米的角钢，要做成三边长为2.9米，2.1米，1.5米的三角架100套。如何下料，才能使消耗的原料最少？

表1-14

2.9米 2.1米 1.5米 合计长 余料长 变量编号 1 2 0 1 7.3 0.1 2 1 2 0 7.1 0.3 3 1 1 1 6.5 0.9 4 1 0 3 7.4 0 5 0 3 0 6.3 1.1 6 0 2 2 7.2 0.2 7 0 1 3 6.6 0.8 8 0 0 4 6 1.4 x2 x4 x6 min zx1x2x3x4x5x6x7x8

x1 x7 x3 （1.24） （1.25） （1.26）

x5 x8 x4 x6 100x12x2  2x32x4x5x63x7 100  3x5x6 4x81003x1x22x3 x1,,x80例19 某食品厂要用C，P，H三种原料混合加工成三种不同档次的产品A，B，C，已知三种产

品中原料含量，原料成本和每月用量，三种产品的加工费和单价等资料如表1-16所示。该厂应当每月生产三种产品多少公斤，才能使利润最大？试建立问题的线性规划模型。

表1-16 C P H 产品单价（元/kg） 产品加工费（元/kg） 解

A B D 每月原料（kg） 原料单价（元/kg） 3000 3000 2400 65 25 35 ≥50% ≥25% — ≤25% ≤50% ≤60% — — — 60 6 45 5 40 4 max z11x129x219x325x415x55x629x711x8x9x1x2x3 0 0x13x2x3  3x4x5x6 0 x4x5x6 0  3x72x83x90 x x4 x7 30001 x2 x5 x8 3000 x3 x6 x9 2400 xj0 j1,2,9

第 15 页

南 京 工 业 大 学 教 案 用 纸

第 7 次课 2 学时

上次课复习： 线性规划相关要点。 本次课题（或教材章节题目）：第二章 对偶理论与灵敏度分析§2.1 单纯形法的矩阵描述 教学要求： 掌握单纯形法的矩阵描述 重 点：单纯形法的矩阵描述 难 点：B-1的求法及作用 教学手段及教具：多媒体教学。 讲授内容及时间分配： §2.1 单纯形法的矩阵描述 p79 2、3 50分钟 50分钟 课后作业 P78 1、（1） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 16 页

南 京 工 业 大 学 教 案 用 纸

第二章 对偶理论与灵敏度分析

§2.1 单纯形法的矩阵描述

表2-1

cj 系数 0 基变量 XS σj … CB XB σj B1b －CB 解向量 b XB B CB I 0 CN XN N CN … B1N －0 XS I 0 B1 －CN－CBB1N －－CBB1 －其中XS=（xs1，xs2，xsm）T是松弛变量组成的列向量。从表2-1可以清楚地看到，以B为基的单

－

纯形表中的增广矩阵，是以B1左乘初始表的增广矩阵的结果；因此，在B为基的表中，与初始表单

－

位矩阵相同位置上即为B的逆矩阵B1。这是一个很有用的普遍规律。这一点还可以利用初等变换知识加以说明：初始表经过若干次行的初等变换转化为以B为基的单纯形表，在这个过程中，它把矩阵B变成为单位矩阵I，从而把单位矩阵I变成。

－

注：为加深对B1及各表达式的理解，课堂练习作业2、3

第 17 页

南 京 工 业 大 学 教 案 用 纸

第 8 次课 2 学时

上次课复习： 单纯形法的矩阵描述 本次课题（或教材章节题目）：§2.2 对偶问题的概念§2.3对偶问题的基本性质 教学要求： 掌握一般形式对偶问题的对应规律、理解并应用对偶定理 重 点： 一般形式对偶问题的对应规律、对偶定理 难 点：对偶定理 教学手段及教具：多媒体教学。 讲授内容及时间分配： §2.2.1对偶问题的提出 §2.2.2 一般形式的对偶问题 §2.3对偶问题的基本性质 20分钟 30分钟 50分钟 课后作业 P79 4、（1） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 18 页

南 京 工 业 大 学 教 案 用 纸

§2.2 对偶问题的概念

§2.2.1对偶问题的提出 原问题

max zCXAXb X0它的对偶问题

（2.11）

min wYbYAC Y0

（2.12）

注意：Y=（y1，y2，…，ym）是行向量。 表2-2

（1）决策变量 （2）目标函数 （3）约束条件 （4）系数矩阵 （5）右端向量 （6）价值向量 §2.2.2 一般形式的对偶问题 表2-3

A C b 原问题（对偶问题）max 约束条件系数矩阵 目标函数价值向量 约束条件右端常数向量 xj≥0 n个变量 m原问题 X≥0（n个） max z=CX AX≤b（m个） A b C 对偶问题 Y≥0（m个） min w=Yb YA≥C（n个） AT C b 对偶问题（原问题）min 约束条件系数矩阵的转置 约束条件右端常数向量 目标函数价值向量 xj≤0 xj无约束 aycijiji1maycijijn个技术约束 i1maijyicji1 yi ≥0 naijxjbij1nm个技术约束aijxjbi j1naijxjbij1§2.3对偶问题的基本性质 定理1 对偶问题的对偶是与原问题。

第 19 页

yi≤0 m个变量 yi无约束 南 京 工 业 大 学 教 案 用 纸

定理2（弱对偶定理） 设X(x1,x2,,xn)T与Y(y1,y2,,ym)分别是（2.9）与（2.10）的可行解，则CXYb。

定理3（最优性判定定理） 设X，Y分别为问题（2.3）与（2.4）的可行解，且CXYb，则两者均为最优解。

第 20 页

南 京 工 业 大 学 教 案 用 纸

第 9 次课 2 学时

上次课复习： 一般形式对偶问题的对应规律； 对偶定理 本次课题（或教材章节题目）：§2.4 影子价格§2.5 对偶单纯形法 教学要求： 掌握互补松弛定理、影子价格意义、对偶单纯形法 重 点： 互补松弛定理、影子价格意义、对偶单纯形法 难 点：互补松弛定理 教学手段及教具：多媒体教学。 讲授内容及时间分配： 互补松弛定理 §2.4 影子价格 §2.5 对偶单纯形法 30分钟 20分钟 50分钟 课后作业 P81 7、8、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 21 页

南 京 工 业 大 学 教 案 用 纸

定理4（强对偶定理） 如果原问题有最优解，那么对偶问题也有最优解；设前者的最优基为B，

－

则对偶最优解为Y*=CBB1，且两者最优值相等。

定理5（互补松弛定理） 设X与Y分别是问题（2.9）与（2.10）的可行解，那么它们都是最优解的充要条件是

(biaijxj)yi0， i=1，2，…，m

j1n （2.18）

且(ai1mijyicj)xj0， j=1，2，…，n

（2.19）

条件（2.18）与（2.19）也可以写为：

xsiyi0 i=1，2，…，m ysjxj0 j=1，2，…，n

z=w= Yb=

*

*

*

（2.20） （2.21）

§2.4 影子价格

mbyii1*i （2.26）

对bi求偏导数，得到：

z*yi* bi （2.27）

即第i种资源影子价格yi*是z*对资源数量bi的变化率，是第i种资源增加一个单位时，最大产值的改变量。

§2.5 对偶单纯形法

§2.5.2 对偶单纯形法的基本思路 由具体例题引出。

§2.5.2 对偶单纯形法的计算步骤 对于标准形式的线性规划：

（1）建立初始单纯形表，使得所有检验数σj≤0；

（2）检查b列元素，如果所有bi≥0，则已得到最优解，结束。否则转入下一步；

（3）确定换出变量：设minbibi0bl，第l方程原基变量为换出变量，第l行为主元行；

ijalj0k，xk为换入变量，第k列为主元列； （4）确定换入变量：设minjaljalk（5）以alk为主元作换基迭代运算，方法与单纯形法完全相同，得到新的单纯形表，返回步骤（2）。

例6 用对偶单纯形法解线性规划（2.30）

第 22 页

南 京 工 业 大 学 教 案 用 纸

min w15y124y25y36y2y3y4 2  5y12y2y3 y51y,y,y,y,y012345表2-5

ci CB 0 0 -24 0 -24 -5

XB b -2 -1 1/3 -1/3 1/4 1/2 -15 -24 -5 0 0 y1 0 -5 -15 0 -5 -15 -5/4 15/2 -15/2 y2 [-6] -2 -24 1 0 0 1 0 0 y3 -1 -1 -5 1/6 [-2/3] -1 0 1 0 y4 1 0 0 -1/6 -1/3 -4 -1/4 1/2 -7/2 y5 0 1 0 0 1 0 1/4 -3/2 -3/2 y4 y5 σj y2 y5 σj y2 y3 σj 第 23 页

南 京 工 业 大 学 教 案 用 纸

第 10 次课 2 学时

上次课复习： 影子价格意义 对偶单纯形法 本次课题（或教材章节题目）：§2.6 灵敏度分析 教学要求： 掌握灵敏度分析方法 重 点： cj、bi、aij的变化分析 难 点： aij、的变化分析 教学手段及教具：多媒体教学。 讲授内容及时间分配： §2.6.1 价值系数cj的变化分析 §2.6.2右端常数bi的变化分析 §2.6.3 增加一个新变量的分析 §2.6.4 增加新的约束条件的分析 §2.6.5* 其它变化情况的分析 15分钟 20分钟 15分钟 20分钟 30分钟 课后作业 P83 13、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 24 页

南 京 工 业 大 学 教 案 用 纸

§2.6 灵敏度分析

§2.6.1 价值系数cj的变化分析

例7 某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划

max z5x14x2x13x2902xx802 1x1 x245x1,x20已知最优表是表2-6

表2-6

cj CB 0 5 4 XB b 25 35 10 5 4 0 0 0

（2.33）

x1 0 1 0 0 x2 0 0 1 0 x3 1 0 0 0 x4 2 1 -1 -1 x5 -5 -1 2 -3 x3 x1 x2 σj 最优计划是两种产品分别生产35单位与10单位，最大产值z*=215单位。 （1）确定x2的系数c2的变化范围，使原最优解保持最优； （2）若c2=6，求新的最优计划。

解 （1）将上表中的x2的系数以c2代替，重新计算检验数，得到： σ4=0－5×1－c2×（-1）= c2－5 σ5=0－5×（-1）－c2×2=5－2c2

令σ4≤0，σ5≤0，解得5/2≤c2≤5，即当c2在区间[5/2，5]中变化时，最优解X*=（35，10，25，0，0）T*保持不变。

（2）当c2=6时，σ4=1>0，原最优解失去最优性，在表2-6中作适当变动后（修改c2的值，重新计算检验数），用单纯形法容易求得新的最优表如下：

表2-7 cj CB 0 5 6 0 5 6 XB b 25 35 10 25/2 45/2 45/2 5 6 0 0 0 x1 0 1 0 0 0 1 0 0 x2 0 0 1 0 0 0 1 0 x3 1 0 0 0 1/2 -1/2 1/2 -1/2 x4 [2] 1 -1 1 1 0 0 0 x5 -5 -1 2 -7 -5/2 3/2 -1/2 -9/2 x3 x1 x2 σj x4 x1 x2 σj 故新的最优解为x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，最优值z*=495/2，即随着产品Ⅱ的价格上升，其产量x2上升，而x1下降，总产值上升。

§2.6.2右端常数bi的变化分析

例8 对于例7中的线性规划（2.33）作下列分析： （1）b3在什么范围内变化，原最优基不变？ （2）若b3=55，求出新的最优解。

第 25 页

南 京 工 业 大 学 教 案 用 纸

解 原最优基为B=（P3，P1，P2），由表2-6可得：

2 -51 －1

1 1 B= 0 0 -1 290－

（1）由B180=

b32 -590250-5b31 0 1 180b80=≥0 30 -1 2b3802b3解得40≤b3≤50，即当b3∈[40，50]时，最优基B不变，最优解为：

*x3250-5b3*x1=80b3，x4*=x5*=0，z*=5×（80－b3）+4×（－80+2b3）=80+3b3 *x2802b3（2）当b3=55时，

250-5b32580b3=25，以它代替表2-6的b列，用对偶单纯形法继续求解。 802b303表2-8 cj CB 0 5 4 0 5 4 XB b -25 25 30 5 30 20 5 4 0 0 0 x1 0 1 0 0 0 1 0 0 x2 0 0 1 0 0 0 1 0 x3 1 0 0 0 -1/5 -1/5 2/5 -3/5 x4 2 1 -1 -1 -2/5 3/5 -1/5 -11/5 x5 [-5] -1 2 -3 1 0 0 0 x3 x1 x2 σj x5 x1 x2 σj §2.6.3 增加一个新变量的分析

例9 （续例7）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示，P6=

3/211/2。试问它的价值系数c6符合什么条件，才必须安排它的生产？设c6=3，新的最优生

T产计划是什么？

解 设新产品的产量为x6，把P6作为初始表的第6列，则在最终表中，它变换为：

2 -53/211 －1

1 11=1/2 P6=BP6=0 0 -1 21/201－

σ6=c6－CBB1P6 =c6－（0，5，4）1/2= c6－5/2

0第 26 页

南 京 工 业 大 学 教 案 用 纸

因此，只有当c6>5/2时，才必须安排新产品生产，否则，原最优计划不变。

当c6=3时，σ6=1/2，在原最终表中增加第六列，P6=B1P6，然后利用单纯形法继续求解。

－

表2-9

cj CB 0 5 4 3 5 4 XB b 25 35 10 25 45/2 10 5 4 0 0 0 3 x1 0 1 0 0 0 1 0 0 x2 0 0 1 0 0 0 1 0 x3 1 0 0 0 1 -1/2 0 -1/2 x4 2 1 -1 -1 2 0 -1 -2 x5 -5 -1 2 -3 -5 3/2 2 -1/2 x6 [1] 1/2 0 1/2 1 0 0 0 x3 x1 x2 σj x6 x1 x2 σj §2.6.4 增加新的约束条件的分析 例10 假设在例7中，还要考虑一个新的资源约束：4x1+2x2≤150

原最优解X*=（35，10，25，0，0）T不满足该约束，为了求得新的最优计划，在上式中引入松弛变量x6，化为：4x1+2x2+x6=150

表2-10 cj CB 0 5 4 0 表2-11 CB 0 5 4 0 0 5 4 0 0 5 4 0 cj XB b 25 35 10 150 25 35 10 -10 15 30 15 5 5 4 0 0 0 0 XB b 25 35 10 150 5 4 0 0 0 0 x1 0 1 0 4 0 x2 0 0 1 2 0 x3 1 0 0 0 0 x4 2 1 -1 0 -1 x5 -5 -1 2 0 -3 x6 0 0 0 1 0 x3 x1 x2 x6 σj x1 0 1 0 4 0 0 1 0 0 0 0 1 0 0 0 x2 0 0 1 2 0 0 0 1 0 0 0 0 1 0 0 第 27 页

x3 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 x4 2 1 -1 0 -1 2 1 -1 [-2] -1 0 0 0 1 0 x5 -5 -1 2 0 -3 -5 -1 2 0 -3 -5 -1 2 0 -3 x6 0 0 0 1 0 0 0 0 1 0 1 1/2 -1/2 -1/2 -1/2 x3 x1 x2 x6 σj x3 x1 x2 x6 σj x3 x1 x2 x4 σj 南 京 工 业 大 学 教 案 用 纸

§2.6.5* 其它变化情况的分析 1. cj和bi同时变化的情况

此时原最优表的b列和检验数行同时改变，可能造成原问题与对偶问题均非可行解（即b列有负分量，σ行有正检验数）。这时需要引入人工变量，使原问题转化为基可行解，再用大M法继续迭代计算。

2. 技术系数aij的变化

由于工艺条件的改变，造成了某个变量xj的系数向量Pj变化。若xj在原最优表中是非基变量，则该表只有第j列和σj变化，处理方式相对比较简单。如果xj是基变量，那么Pj包含在最优基B中，

－

B与B1都会改变，从而最优表的b列与σ行都有变化。若所得的表中，原问题与对偶问题中有一个为可行解，则可用单纯形法或对偶单纯形法继续求解。

3. 增加新的等式约束条件

设新约束为体方法是：

若

aj1nkjxj=bk （bk≥0），且原最优解X*不满足它，这时也需要利用人工变量求解。具

aj1nkjx*jnaj1kjxj+xa= bk

若

aj1nkjx*j> bk给左端减去人工变量xa，化为

naj1kjxj－xa= bk

以xa作为该方程的基变量，这样可以保证原问题有基可行解，从而可用大M法或两阶段法继续

求解。

第 28 页

南 京 工 业 大 学 教 案 用 纸

第 11 次课 2 学时

上次课复习： cj、bi、aij的变化分析 本次课题（或教材章节题目）：§2.7* 参数线性规划 教学要求： 掌握参数线性规划方法 重 点：参数规划的解法 难 点：b中含参数的解法 教学手段及教具：多媒体教学。 讲授内容及时间分配： （1）价值系数连续变化时分析 （2）右端常数连续变化时分析 P84 14、 20分钟 30分钟 50分钟 课后作业 P84 15、（1）、（2） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 29 页

南 京 工 业 大 学 教 案 用 纸

§2.7* 参数线性规划

（1）当价值系数连续变化时，参数线性规划的形式是

max z(CC)XAXb X0

其中C为原价值向量，C为变动向量，λ是连续变化的参数。 （2）当右端常数连续变化时，参数线性规划的形式是

max zCXAXbb X0其中b为原右端常数向量，b为变动向量，λ是参数。 参数线性规划的分析步骤：

（1）首先令λ=0，求得相应的最优单纯形表； （2）把λC或λb项反映到最优表中；

（3）当λ增大或减小时，观察检验数行或b列，确定目前最优解（或最优基）的适用范围，若λ的变动超出该范围，用单纯形法或对偶单纯形法求新的最优解；

（4）对于新的最优表，重复（3）的做法，直到把λ的变化范围讨论完毕。 例13 分析下列线性规划的最优解与参数λ的关系：

max z(2)x1(12)x25x215 6x2x242 1x1 x25x1,x20

解 （1）先取λ=0，求出最优解，并把λC反映到最优表中，得表2-16。 表2-16 cj CB 0 2+λ 1+2λ XB b 15/2 7/2 3/2 2+λ 1+2λ 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 1 0 0 0 x4 5/4 1/4 -1/4 -1/4+λ/4 x5 -15/2 -1/2 3/2 -1/2-5λ/2 x3 x1 x2 σj

-1/5≤λ≤1

（2）当λ>1时，表2-16中，σ4= -1/4+λ/4>0，应引入x4，用单纯形法迭代得到表2-17。

第 30 页

南 京 工 业 大 学 教 案 用 纸

表2-17

cj CB 0 2+λ 1+2λ XB b 6 2 3 2+λ 1+2λ 0 0 0

λ≥1

x1 0 1 0 0 x2 0 0 1 0 x3 4/5 -1/5 1/5 1/5-λ/5 x4 1 0 0 0 x5 -6 1 0 -2-λ x4 x1 x2 σj （3）在表2-16中，如果λ≤-1/5，σ5= -1/2－5λ/2>0，应引入x5，迭代后得到表2-18的第一表，由检验数行可知，它是最优表的λ的范围是-2≤λ≤-1/5；而当λ≤-2时，它的σ4>0，经迭代又得到第二表。

表2-18 cj 0 0 0 2+λ 1+2λ CB XB b x1 x2 x3 x4 x5 -2≤λ≤-1/5 0 15 0 5 1 0 0 x3 *z=8+4λ 4 1 1/3 0 [1/6] 0 2+λ x1 0 1 0 2/3 0 -1/6 1 x5 -1/3-λ0 0 0 σj 1/3+5λ/3 /6

0 15 0 5 1 0 0 x3 λ≤-2

0 24 6 2 0 1 0 x4 z*=0

0 5 1 1 0 0 1 x5

0 0 0 σj 2+λ 1+2λ

例14 某公司利用甲、乙两种原料生产A、B、C三种产品的最优计划问题，归结为下列线性规划：

max z60x140x222x32x13x23x316000 6x13x2x318000x,x,x0123

其中x1，x2，x3表示产品产量，目标函数z表示总产值（单位：元），技术约束表示原料，产量x1，x2与原料的单位为千克。现在假设公司准备拿出4万元资金补充原料以扩大生产，已知甲的市场价格为2元/kg，乙的价格为6元/kg，问两种原料各补充多少，效果最佳？最优计划是什么？

解 线性规划（2.35）的最优单纯形表如下（表2-19） 表2-19

cj CB 40 60 XB b 5000 500 60 40 22 0 0

（2.35）

x1 0 1 0 x2 1 0 0 x3 4/3 -1/2 -4/3 x4 1/2 -1/4 -5 x5 -1/6 1/4 -25/3 x2 x1 σj X*=（500，5000，0，0）T，z*=230000万元。

两种原料的影子价格分别为5元/kg，与25/3元/kg，高于市场价格，补充原料可以提高效益。 设两种原料甲、乙分别补充μ与λ千克，则有关系式：

第 31 页

南 京 工 业 大 学 教 案 用 纸

2μ+6λ=40000，从中解出μ=20000－3λ：

max z60x140x222x32x13x23x3360003  6x13x2x318000x,x,x0123

（2.28）

这是一个右端常数项包含变动参数λ的参数规划，λ的取值范围是0≤λ≤40000/6=20000/3。 要在这个区间中求出一个λ值，使得相应的最优计划的产值z*（λ）为最大。 首先要把右端常数的变化，反映到表2-19中，与灵敏度分析相仿，计算

11 36000326－~B1b== 1118000 44表2-20 cj CB 40 60 XB b 15000-5λ/3 -4500+λ 5150003用它代替表2-19的b列，得表2-20 4500 60 40 22 0 0 x1 0 1 0 x2 1 0 0 x3 4/3 -1/2 -4/3 x4 1/2 -1/4 -5 x5 -1/6 1/4 -25/3 x2 x1 σj 当15000-5λ/3≥0且-4500+λ≥0，即4500≤λ≤20000/3时，它是最优表，最优函数值z*=60（-4500+λ）+40（15000-5λ/3）=330000－20λ/3；z*（λ）在区间[4500，20000/3]中是λ的减函数。

当λ<4500时，表2-20中x1<0，利用对偶单纯形法，以a23=-1/2为主元迭代，可得新的最优表（表2-21）。

表2-21 cj CB 40 22 XB b 3000+λ 9000-2λ 60 40 22 0 0 x1 8/3 -2 -8/3 x2 1 0 0 x3 0 1 0 x4 -1/3 1/2 -13/3 x5 1/2 -1/2 -9 x2 x3 σj 0≤λ≤4500时，上表为最优表，相应最优目标函数值z*=318000－4λ，是λ的减函数。 综合上述结果，当λ=0，μ=20000kg时是最佳选择，相应的最优产量计划是x2*=3000kg，x3*=9000kg，最大产值z*=318000元。因此，4万元的补充投入，带来产值的增量是318000－230000=88000元，相当于利润增加4.8万元。

第 32 页

南 京 工 业 大 学 教 案 用 纸

第 12 次课 2 学时

上次课复习： 线性规划及对偶问题回顾： 数学模型 单纯形法 对偶理论 本次课题（或教材章节题目）：第三章 运输问题§3.1 运输问题及其数学模型§ 3.2 表上作业法 教学要求： 掌握运输问题数学模型、掌握最小元素法、西北角法、伏格尔法 重 点：运输问题数学模型、最小元素法、伏格尔法 难 点：伏格尔法 教学手段及教具：多媒体教学。 讲授内容及时间分配： §3.1 运输问题及其数学模型 § 3.2 表上作业法 § 3.2.1.初始基本可行解的确定 30分钟 70分钟 课后作业 P110 1、（1） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 33 页

南 京 工 业 大 学 教 案 用 纸

第三章 运输问题

§3.1 运输问题及其数学模型

运输问题的一般提法是：设某种物资有m个产地和n个销地。产地Ai的产量为

ai (i1,2,,m)；销地Bj的销量为bj (j1,2,,n)。从第i个产地Ai向第j个销地Bj运输每单

位物资的运价为Cij。这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。

表3—1 产销平衡表

销 地 产 地 A1A2 AmB1x11x21xm1B2x12x22xm2Bn x1nx2n xmn产量 a1a2 am销量 b1b2 bn 表3—2 单位运价表

销 地 产 地 B1c11B2c12c22cm2Bn c1nc2n cmnA1A2Am产销平衡的运输问题的数学模型为：

c21cm1minzcijxij

i1j1mnxj1mnijai (i1,2,,m)bj (j1,2,,n)

（3-1）

xi1ijxij≥ 0 (i1,2,,m;j1,2,,n)其中ai和bj满足

第 34 页

南 京 工 业 大 学 教 案 用 纸

mnabii1j1j （3-2）称为产销平衡条件。

将（3-1）的结构约束加以整理，可知其系数矩阵的结构比较松散，且特殊

x11x12x1nx21x22x2nxm1xm2xmn

1A111111111111111m行 1 n行 1该系数矩阵中对应于变量xij的系数向量中除第i个和第mj个为1以外，其余的都为零。

§ 3.2 表上作业法

§ 3.2.1.初始基本可行解的确定

（1）最小元素法

基本思想：优先满足单位运价最小的供销业务。首先找出运价最小的，并以最大限度满足其供销量为原则确定供销业务。然后，在余下的未确定的供销业务中找运价最小的，同样以最大限度满足其供销量为原则确定供销业务，同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。由于该方法基于优先满足单位运价最小的供销业务，故称为最小元素法。

（2）西北角法

西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销需求。按以上方法进行下去，最后可得到初始方案。

（3）伏格尔法 最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运价。伏格尔法考虑到，某产地的产品假如不能按最小运价就近供应，就考虑次小运价，这就有一个差额。差额越大，说明不能按最小运价调运时，运费增加越多。因而对差额最大的行或列，就应当采用最小运价调运。基于此思想，伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。

第 35 页

南 京 工 业 大 学 教 案 用 纸

第 13 次课 2 学时

上次课复习： 运输问题数学模型 最小元素法 西北角法 伏格尔法 本次课题（或教材章节题目）：§ 3.2.2 解的最优性检验§ 3.2.3．解的改进§ 3.2.4．表上作业法中需要说明的问题 教学要求： 掌握闭回路法、位势法 重 点：闭回路法、位势法 难 点：位势法 教学手段及教具：多媒体教学。 讲授内容及时间分配： §3.2.2 解的最优性检验 §3.2.3 解的改进 §3.2.4 表上作业法中需要说明的问题 §3.2.5 表上作业法小结 40分钟 30分钟 20分钟 10分钟 课后作业 P110 1、（2） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 36 页

南 京 工 业 大 学 教 案 用 纸

§ 3.2.2．解的最优性检验 （1）闭回路法

在单纯形法中，为了检验一个基本可行解是不是最优解，需要求出所有非基变量的检验数。在运输问题中，每个空格对应一个非基变量。

（2）位势法

对于一个调运方案的每列赋予一个值，称为列位势。记为：v1,v2,,vn，对于每行赋予一个值，称为行位势，记为u1,u2,,um。它们的值由下列方程组决定：

uivjcij

§ 3.2.3．解的改进

如果某一个调运方案的所有空格的检验数都不小于零，则该调运方案是最优方案。有负的检验数，说明该调运方案不是最优方案，进一步调整，还可以使总的运费减少。

调整方法：从检验数为负值的空格出发作闭回路（当出现两个或两个以上的检验数为负值时，取绝对值最大的）。

§ 3.2.4 表上作业法中需要说明的问题 （1）无穷多最优解 （2）退化

§ 3.2.5．表上作业法小结

第 37 页

南 京 工 业 大 学 教 案 用 纸

第 14 次课 2 学时

上次课复习： 闭回路法 位势法 本次课题（或教材章节题目）：§ 3.3 产销不平衡的运输问题§ 3.4 应用举例 教学要求： 掌握产量大于销量、销量大于产量的运输问题 重 点：产销平衡表的确定 难 点：运输问题的实际应用 教学手段及教具：多媒体教学。 讲授内容及时间分配： § 3.3.1 产量大于销量 § 3.3.2 销量大于产量 § 3.4 应用举例 30分钟 20分钟 50分钟 课后作业 P111 3、4、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 38 页

南 京 工 业 大 学 教 案 用 纸

§ 3.3 产销不平衡的运输问题

§ 3.3 1．产量大于销量 其数学模型为：minznmnci1j1ijxij

xj1mij  ai (i1,2,,m)bj (j1,2,,n)

xi1ijxij  0 (i1,2,,m; j1,2,,n)增加一个假想的销地Bn1，其销量为：bn1abii1j1mnj

相应运价ci,n10 (i1,2,,m)，上述不平衡问题转化为产销平衡的问题，数学模型为：

minzcijxiji1j1mn1n1xijai (i1,2,,m)j1 mxijbj (j1,2,,n1)i1xij  0 (i1,2,,m; j1,2,,n1)§ 3.3 2．销量大于产量

其数学模型为：

minzcijxij

i1j1mnxj1mnijai (i1,2,,m)  bj (j1,2,,n)

xi1ijxij  0 (i1,2,,m;j1,2,,n)这时，可增加一个假想的产地Am1，其产量为：

am1bjai

j1i1nm由于假想的产地Am1实际上并不存在，相应的运费为cm1,j0 (j1,2,,n)。上述不平衡问

第 39 页

南 京 工 业 大 学 教 案 用 纸

题转化为平衡的问题，它的数学模型为：

minzcijxiji1j1m1nnxijai (i1,2,,m,m1)j1 m1xijbj (j1,2,,n)i1xij  0 (i1,2,,m,m1;j1,2,,n)§ 3.4 应用举例

例5 某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表3-24所示。如果生产出来的柴油机当季不交

4

货的，每台每积压一个季度需储存、维护等费用0.15×10元。要求在完成合同的情况下做出使该厂全年生产（包括储存、维护）费用最小的决策。

表 3—24 季度 Ⅰ Ⅱ Ⅲ Ⅳ 生产能力/台 25 35 30 10 单位成本/10元 10.8 11.1 11.0 11.3 4解 设xij为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足

10x11 xx 151222 25x13x23x33 x14x24x34x4420x11x12x13x1425 x22x23x2435  x33x3430  x4410 第i季度生产j季度交货的每台柴油机实际成本应该是该季度单位成本加上储存、维护等费用。表3—25

j i Ⅰ Ⅱ Ⅲ Ⅳ Ⅰ 10.8 Ⅱ 10.95 11.10 Ⅲ 11.10 11.25 11.00 Ⅳ 11.25 11.40 11.25 11.30 设用ai表示该厂第i季度的生产能力，bj表示第j季度的合同供应量，则问题可写成

第 40 页

南 京 工 业 大 学 教 案 用 纸

minzcijxiji1j444xijai (i1,2,3,4) j14xijbj (j1,2,3,4)i1xij  0 (i,j1,2,3,4)应注意，在该问题中，当i>j时应使xij=0。为了实现这一要求，在上面模型中，令对应的

cijM,M为一个充分大的正数。此外，再加上一个假想的需求D，就可以把这个问题变成产销平

衡的运输模型，其产销平衡表和单位运价表（合在一起）如表3-26所示。

表 3—26 销地 产地 Ⅰ Ⅱ Ⅲ Ⅳ 销量 Ⅰ 10.8 Ⅱ 10.95 11.10 Ⅲ 11.10 11.25 11.00 Ⅳ 11.25 11.40 11.25 11.30 20 D 0 0 0 0 30 产量 25 35 30 10 M M M 10 M M 15 M 25 第 41 页

南 京 工 业 大 学 教 案 用 纸

第 15 次课 2 学时

上次课复习： 产销平衡表的确定 本次课题（或教材章节题目）：运输问题的灵敏度分析及应用研究 教学要求： 掌握运输问题的灵敏度分析 重 点： 运输问题的灵敏度分析 难 点：运输问题的灵敏度分析 教学手段及教具：多媒体教学。 讲授内容及时间分配： 运输问题的灵敏度分析 运输问题应用研究 50分钟 50分钟 课后作业 P112 5、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 42 页

南 京 工 业 大 学 教 案 用 纸

补充：已知运输问题的产销平衡表、单位运价表及最优调运方案分别如表所示。产销平衡表及最 B1 B2 优调运方案B3 B4 产量

A1 5 10 15

A2 0 10 15 25

A3 5 5

销量 5 15 15 10

单位运价表

B1 B2 B3 B4

A1 10 1 20 11

A2 12 7 9 20

A3 2 14 16 18

1、从A2－B2的单位运价c22在什么范围变化时，上述最优调运方案不变？

2、A2－B4的单位运价c24变为何值时，有无穷多最优调运方案，除上述最优方案外，至少再写出两个。

3≤ c22≤ 10

c24=17

第 43 页

南 京 工 业 大 学 教 案 用 纸

本章小结

运输问题模型是一种特殊的线性规划，由于其约束条件特别简单，因此它有更简单的解法——表上作业法。本章教学重点内容有：

1. 运输问题的数学模型及其特点；

2. 确定初始调运方案的最小元素法和伏格尔法； 3. 检验数的意义、计算方法和格式； 4. 方案调整的方法；

5. 把不平衡运输问题转化为标准模型的方法。

第 44 页

南 京 工 业 大 学 教 案 用 纸

第 16 次课 2 学时

上次课复习： 运输问题主要内容回顾： 产销平衡运输问题 产销不平衡运输问题 本次课题（或教材章节题目）：第四章 目标规划§ 4.1目标规划问题与数学模型§ 4.2 目标规划 的图解法 教学要求： 掌握目标规划问题的数学模型、图解法 重 点：目标规划基本概念；图解法 难 点：图解法 教学手段及教具：多媒体教学。 讲授内容及时间分配： §4.1目标规划问题与数学模型 §4.1.1 目标规划问题的提出 §4.1.2 目标规划的数学模型 §4.2 目标规划的图解法 20分钟 40分钟 40分钟 课后作业 P131 1、3、（2） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 45 页

南 京 工 业 大 学 教 案 用 纸

第四章 目标规划

§ 4.1目标规划问题与数学模型

§ 4.1.1 目标规划问题的提出 § 4.1.2 目标规划的数学模型

在用目标规划描述该问题前，首先介绍目标规划的一系列基本概念。 （1）偏差变量

（2）绝对约束和目标约束 （3）优先因子和权系数 （4）目标规划的目标函数

目标规划的一般数学模型为：

minzpl(wlkdkwlkdk)

l1k1LKncxddkkgk,k1,,Kkjjj1nax(,)b,i1,,m iijjj1xj0,j1,,ndk,dk0,k1,,K§ 4.2 目标规划的图解法

（1）先考虑硬约束与决策变量的非负约束，同一般线性规划作图法。

（2）作目标约束，此时，先让didi0（与作绝对约束时类似）。然后标出di及di的增

加方向（实际上是目标值减少与增加的方向）。 B 11 8x110x256④ d1 F

E G C D x1x20②  d1 5.5 0 A 2x1x211,① d3 H d2 d3 d2 x12x210③ 图4——1 第 46 页

南 京 工 业 大 学 教 案 用 纸

（3）按优先级的次序，逐级让目标规划的目标函数（准则函数或达成函数）中极小化偏差变量取零，从而逐步缩小可行域，最后找出问题的解。

例3 某厂装配黑白与彩色两种电视机，每装配一台电视机，需占用装配线1小时，装配线每周开动40小时，预计市场每周彩电销量为24台，每台可获利80元，黑白电视机销量为30台，每台可获利40元，该厂的目标是：

第1优先级：充分利用装配线每周开动40小时。

第2优先级：允许装配线加班，但每周加班时间不超过10小时。

第3优先级：装配电视机数量尽量满足市场需要，但因彩电利润高，彩电权因子取2。 建立目标规划模型，并计算两种电视机的产量应为多大？

解 设x1,x2分别为彩电及黑白电视机产量，

准则函数（目标函数）为

minzp1d1p2d2p3(2d3d4) (4.2.2)

则目标约束为

x1x2d1d140x1x2d2d250①② ③

(4.2.1)

x1 d3d324 x2d4d430④x1,x2,di,di0 (i1,2,3,4)

C D G H d4 x230④ x2 F E d4 d3 x1x250② B O d3 d2 x124③ d1 A x1 x1x240① 图 4-2 (E)(E)0,d30,d44。 24,x226，此时d10,d2本题满意解为E点：x1

第 47 页

南 京 工 业 大 学 教 案 用 纸

第 17 次课 2 学时

上次课复习： 目标规划基本概念； 图解法 本次课题（或教材章节题目）：§4.3 解目标规划的单纯形法 §4.4 目标规划的灵敏度分析 教学要求： 掌握目标规划的单纯形法、掌握目标规划的灵敏度分析方法 重 点：目标规划单纯形法、灵敏度分析 难 点：灵敏度分析 教学手段及教具：多媒体教学。 讲授内容及时间分配： § 4.3 解目标规划的单纯形法 § 4.4 目标规划的灵敏度分析 50分钟 50分钟 课后作业 P132 4、（2）；5 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 48 页

南 京 工 业 大 学 教 案 用 纸

§ 4.3 解目标规划的单纯形法

解目标规划问题的单纯形法的计算步骤：

（1）建立初始单纯形表，在表中将检验数行按优先因子个数从高到低分别列成K行，置k=1； （2）检查K行中是否存在负数，且对应的前k-1行的系数是零。若有取其中最小者对应的变量为换入变量，转（3）。否则转（5）。

（3）按最小比值规则确定换出变量，当存在两个和两个以上相同最小比值时，选取具有较高优先级别的变量为换出变量。

（4）按单纯形法进行基变换运算，建立新的计算表，返回（2）。

（5）当k=K时，计算结束。表中的解即为满意解。否则置k=k+1，返回到（2）。

§ 4.4 目标规划的灵敏度分析

例5 已知目标规划问题

minP1d1,P2d2,P3(5d33d4),P4d1

x12x2d1d1 6 d2d2 9x12x2  d3d3 4 x12x2  x dd2244x1,x2,di,,di0 i1,2,3,4

目标函数分别变为：

（i）minP1d1,P2d2,P3d1,P4(5d33d4)

（ii）minP1d1,P2d2,P3(W1d3W2d4),P4d1 (W1,W20)

解 目标函数的变化仅影响原解的最优性，即各变量的检验数。因此，应当先考察检验数的变化，然后再作适当的处理。

表4—6

cj 0 0 p1 d1 0 -1 0 0 1 0 0 1 p4 d1 0 1 0 0 0 0 0 0 0 p2 d2 -1/2 -1 1/4 -1/4 0 1 -3 1 5p3 d3 1/2 0 1/4 -1/4 0 0 17/4 0 0 3p3 d4 0 0 1 0 0 0 0 0 0 CB XB b 13/2 3 x1 1 0 0 0 0 0 0 0 x2 0 0 0 1 0 0 0 0 d2 1/2 1 -1/4 1/4 0 0 3/4 -1 d3 -1/2 0 -1/4 1/4 0 0 3/4 0 d4 0 0 -1 0 0 0 3 0 0p43p30 x1d1d4 3/4 5/4 P1 P2 P3 P4 x2cjzj 1．当目标函数变（i），就是要了解交换第三和第四优先级目标对原解的影响。此时，单纯形表变为表4—7

第 49 页

南 京 工 业 大 学 教 案 用 纸

表4—7

cj 0 0 p1 d1 0 -1 0 0 1 0 1 0 p3 0 p2 d2 -1/2 -1 1/4 -1/4 0 1 1 -3/4 5p4 d3 1/2 0 1/4 -1/4 0 0 0 17/4 0 3p4 d4 0 0 1 0 0 0 0 0 0 CB XB b 13/2 3 x1 1 0 0 0 0 0 0 0 x2 0 0 0 1 0 0 0 0 d1 0 1 0 0 0 0 0 0 d2 1/2 1 -1/4 1/4 0 0 -1 3/4 d3 -1/2 0 -1/4 1/4 0 0 0 3/4 d4 0 0 -1 0 0 0 0 3 0p33p40 x1d1d4 3/4 5/4 P1 P2 P3 P4 x2cjzj 表4—8

cj 0 0 p1 d1 1/2 -1 -1/4 1/4 1 0 0 3/4 p3 0 p2 d2 0 -1 0 0 0 1 0 0 5p4 d3 1/2 0 1/4 -1/4 0 0 0 17/4 0 3p4 d4 0 0 1 0 0 0 0 0 0 CB XB b 5 3 x1 1 0 0 0 0 0 0 0 x2 0 0 0 1 0 0 0 0 d1 -1/2 1 1/4 -1/4 0 0 1 -3/4 d2 0 1 0 0 0 0 0 0 d3 -1/2 0 -1/4 1/4 0 0 0 3/4 d4 0 0 -1 0 0 0 0 3 003p40 x1d2d4 3/2 1/2 P1 P2 P3 P4 x2cjzj 2．当目标函数变（ii），就是要了解第三优先级中两目标权系数取值对原解的影响。

表4—9

cj 0 0 p1 d1 0 -1 0 0 1 0 0 1 p3 0 p2 d2 -1/2 -1 1/4 -1/4 W1P3 d3 1/2 0 1/4 -1/4 0 W2P3 d4 0 0 1 0 0 0 0 0 0 CB XB b 13/2 3 x1 1 0 0 0 0 0 0 0 x2 0 0 0 1 0 0 0 0 d1 0 1 0 0 0 0 0 0 d2 1/2 1 -1/4 1/4 d3 -1/2 0 -1/4 1/4 d4 0 0 -1 0 0 0 W2 0 0P4W2P30cjzj x1d1d4 3/4 5/4 P1 P2 P3 P4 x20 0 0 0 0 1 0 0 W2/4 -W2/4 W1-W2/4 W2/4 -1 1 0 0 第 50 页

南 京 工 业 大 学 教 案 用 纸

第 18 次课 2 学时

上次课复习： 目标规划单纯形法、 灵敏度分析 本次课题（或教材章节题目）：§ 4.5 目标规划应用举例 教学要求： 掌握目标规划数学模型的建立 重 点：目标规划数学模型的建立 难 点：数学模型中目标函数的确定 教学手段及教具：多媒体教学。 讲授内容及时间分配： § 4.5 目标规划应用举例 运输问题目标规划 生产问题目标规划 50分钟 50分钟 课后作业 P132 6 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 51 页

南 京 工 业 大 学 教 案 用 纸

§ 4.5 目标规划应用举例

例6 某电子公司生产录音机和收音机两种产品，它们均需经过两个工厂加工，每一台录音机在第一个工厂加工2小时，然后送到第二个工厂装配试验2.5小时才变为成品；每一台收音机需在第一个工厂加工4小时，在第二个工厂装配试验1.5小时才变为成品。录音机与收音机每台厂内的每月储存成本分别为8元和15元。第一个工厂有12部制造机器，每部每天工作8小时，每月正常工作天数为25天，第二个工厂有7部装配试验设备，每部每天工作16小时，每月正常工作天数仍为25天。每台机器每小时的运转成本是：第一个工厂为18元，第二个工厂为15元。每台录音机的销售利润为20元，收音机为23元。依市场预测，下月录音机与收音机的销售量估计分别为1500台和1000台。 该公司确定下列次序为目标优先次序：

P1：厂内的储存成本不超过23000元。 P2：录音机销售量必须完成1500台。

P3：第一、二工厂的生产设备应全力运转，避免有空闲时间。两厂运转成本当作它们间的权系数。

P4：第一个工厂的超时作业时间全月份不宜超过30小时。 P5：收音机销售量必须完成1000台。

P6：两个工厂的超时工作时间总应予，其的比率依各厂每小时运转成本为准。

试建立这个问题的目标规划模型。

解 设x1x2分别表示次月份录音机与收音机的产量。di,di分别为第i个目标的负、正偏差变量。

（1）第一、二工厂设备运转时间约束：

第一个工厂设备总能力：8×12×25=2400小时 第二个工厂设备总能力：16×7×25=2800小时 于是

2x14x2d1d124002.5x11.5x2dd2800（2）厂内储存成本约束：

22

8x115x2d3d323000

（3）销售目标约束：

x1d4d41500x2dd1000（4）第一个工厂超时作业之约束：

d1d11d1130

55

注意：这里对偏差变量d1引进它的偏差变量，且用d11,d11分别表示它的负、正偏差变量。 （5）达成函数为：

第 52 页

南 京 工 业 大 学 教 案 用 纸

minfp1d3p2d4p3(6d15d2)p4d11p5d5p6(6d15d2)

达成函数中p3和p6级目标的权系数是取第一、第二两工厂每小时运转成本比率18：15=6：5。 综合上述分析，即得这个问题的目标规划模型如下：

minfp1d3p2d4p3(6d15d2)p4d11p5d5p6(6d15d2)

约束条件：

2x14x2d1d124002.5x11.5x2d2d228008x115x2d3d323000x1d4d41500

x2d5d51000d1d11d1130x1,x2,di,di0 i1,2,,5,11

本章小结

目标规划能够适应更复杂的实际问题建模和求解的需要。本章重点掌握下列内容： 1. 正确理解偏差变量，优先因子、目标约束等基本概念；

2. 目标规划建模的方法与步骤，尤其是适当构成目标约束和正确建立目标函数的方法；

3. 目标规划的单纯形法，它与普通单纯形法的共同点和区别（从单纯形表的构成、检验数的写法、迭代运算的各个环节等方面对两者进行分析比较）。

第 53 页

南 京 工 业 大 学 教 案 用 纸

第 19 次课 2 学时

上次课复习： 目标规划主要内容回顾： 数学模型 图解法 灵敏度分析 本次课题（或教材章节题目）：第五章 整数规划 第一节 整数规划问题的提出及其特点 第二节 分支定界法 教学要求： 掌握整数规划数学模型的特点、分支定界法 重 点：整数规划数学模型；分枝定界法 难 点：分枝定界法 教学手段及教具：多媒体教学。 讲授内容及时间分配： 第一节 整数规划问题的提出及其特点 1.1整数规划问题的提出 1.2解的特点 第二节 分支定界法 35分钟 15分钟 50分钟 课后作业 P158 1；4、（2） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 页

南 京 工 业 大 学 教 案 用 纸

第五章 整数规划

本章学习过程中注意掌握：分枝定界法、割平面法、0-1规划解法、指派问题解法

第一节 整数规划问题的提出及其特点

1.1 整数规划问题的提出

例1 某公司拟建设A、B两种类型的生产基地若干个，两种类型的生产基地每个占地面积，所需经费，建成后生产能力及现有资源情况如表5-1所示。问A、B类型基地各建设多少个，可使总生产能力最大？

表5-1

占地（m2） 费用（万元） 生产能力（百件/年） A 2000 5 20 B 5000 4 10 资源 13000 24 解 设A、B两种类型基地各建设x1, x2个，则其模型为：

maxz20x110x2

2x15x213 5x14x224x0,x0且为整数121.2 解的特点

图5-1

第二节 分支定界法

例1 求解下面整数规划

maxz3x12x2

(P0)

2x1x29 2x13x214x0,x0且为整数值21解：

图5-2

第 55 页

(P1)

x1=3.25

x2=2.5

z(0)=14.75(P2)

x1=3.5 x2=2

z(1)=14.5 (P3)

(P4)

x1=2.5 x2=3

z(2)=13.5 x1=3 x2=2

z(3)=13 x1=4 x2=1

z(4)=14 ×

图5–3

* 南 京 工 业 大 学 教 案 用 纸

从以上解题过程可得用分枝定界法求解整数规划(最大化)问题的步骤为：

（1）先求解整数规划的松弛问题，若其无最优解，这时IP也无最优解，停止求解；若其有最优解，且符合整数条件，则此整数最优解即为相应IP的最优解，停止求解；若其是非整数最优解，记其目标函数值为z’，转下一步。

（2）定界，用观察法找IP的一个整数可行解，求得其目标函数值，并记作z, 以z*表示IP的最优值, 这时有: z≤z*≤z’

(3) 对z’问题分支，在z’问题的最优解中任选一个不符合整数条件的变量xj，其值为bj，以[bj]表示不大于bj的最大整数，构造两个约束条件

xj≤[bj]，和xj≥[bj]+1

将这两个约束条件分别加到z所代表的问题，构成两个新的线性规划分支，求解它们。

（4）比较、定界与剪枝，新分支中（包括未剪掉且未分的分支）的最大最优值作为IP新的上界’z，可得到的最大整数最优解的目标函数值作为IP新的下界z，若IP新的上下界相等，则此新上（下）界即为IP的最优值，对应的解为最优解，停止计算；否则对无最优解的分支、最优目标函数小于z的分枝予以剪枝，以后不再考虑，转（3）。

‘

第 56 页

南 京 工 业 大 学 教 案 用 纸

第 20 次课 2 学时

上次课复习： 整数规划数学模型 分支定界法 本次课题（或教材章节题目）：第三节 割平面法 第四节 0-1规划 教学要求： 掌握割平面法、0-1规划数学模型的建立及解法 重 点：割平面法；0-1规划 难 点： 0-1规划数学模型的建立 教学手段及教具：多媒体教学。 讲授内容及时间分配： 第三节 割平面法 第四节 0-1规划 50分钟 50分钟 课后作业 P159 5、（1）；6、（1） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 57 页

南 京 工 业 大 学 教 案 用 纸

第三节 割平面法

割平面法(Cutting Plane Approach)适用于求解纯整数规划的情形。 例1考虑纯整数规划问题

maxzx1x2

2x1x26 4x15x220x0,x0且为整数21解 先不考虑整数条件，求得其松弛问题的最优单纯形表为表5-4。

表5-4 Cj 1 1 0 0 CB XB b x1 x2 x3 x4 0 5/3 1 0 5/6 －1/6 x1 0 8/3 0 1 1/3 －2/3 x2 0 0 σj －1/6 －1/6 521158x1+ x3－ x4＝x2 － x3 + x4=

6363 3 3 将系数和常数都分解成整数和非负真分数之和

511522x1+ x3+（－１+ ）x4＝１ +x2 + (–1+)x3 + x4 =2 +

663 3 33

解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。

21x2 – x3 –2 = － （x3 + x4 ）

33因为所有变量均取整数，所以式子左端必为整数，右端则也为整数，且右端括号项为正数，则右端应为非正数，即

211－ x3 － x4≤0 （5.1） 333移项并引入松弛变量s1后得

211－ x3 － x4 + s1＝－ （5.2）

333将此约束条件加到表5-4，得表5-5，继续求解如下。

表5-5

Cj 1 1 0 0 0 CB XB b s1 x1 x2 x3 x4 5/6 0 5/3 1 0 0 －1/6 x3 0 8/3 0 1 1/3 0 －2/3 x4 0 s1 0 0 1 －2/3 [－1/3] －1/3 0 0 0 σj －1/6 －1/6 0 1 0 1 0 0 －1 x1 1 4 0 1 0 1 －2 x2 0 2 0 0 1 1 －3 x3 0 0 0 0 σj －1/2

第 58 页

南 京 工 业 大 学 教 案 用 纸

割平面法的求解步骤归纳为： 对于整数规划IP

max z=

cj1nnjxj

xjbi i=1,2,…,m

aj1ijxj ≥0, 且为整数， j=1,2,…,n

设其中aij和bi皆为整数（若不为整数时，可乘上一个倍数化为整数）。先求其松弛问题最优解，令xj是最优解中为分数值的一个基变量，在松弛问题的最优单纯形表中，得

xiaikxkbi (5.3)

k这里xk为非基变量, 将bi和aik都分解成整数部分N与非负真分数f之和，即

bi = Ni+fi, 0将上二式代入（5.3）式，得

xiNikxkNififikxk

kk上式由左边看为整数，右边也应为整数，又因为0fifikxk0 （5.4）

k加入松弛变量，将（5.4）添加到上一步最优单纯形表中，继续求解，直到得到整数最优解。

第四节 0-1规划

4.1问题的提出

例1项目选择问题。 现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和c（jj=1，2，…，n）。此外，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和4中至少选择一个；第三，项目5，6和7中恰好选择两个。应当怎样投资项目，才能使总预期收益最大？

解 每一个投资项目都有被选择和不被选择两种可能，为此令

1当选中第j个项目时 xj0当未选中第j个项目时这样，问题可表示为

第 59 页

南 京 工 业 大 学 教 案 用 纸

max z =

ncj1jxj

najxjBj1x2x1 x3x41xxx2675xj0或1(j1，2，3，n）在这一问题中，所有变量只有两个取值，0或1，即0-1变量，或叫二进制变量(binary variable)，或叫逻辑变量（logical variable）这样的问题称为0-1规划问题。 解0—1型整数规划的隐枚举法：

例5 maxz5x14x23x3

x13x22x35①②2x17x23x352x2x32  ③ 5x3x2x7④231xj0或1j=1,2,35x14x23x34 ◎

表5–7

点 满 足 条 件 ？ （x1，x2，x3） （0，0，0） （0，0，1） （0，1，0） （0，1，1） （1，0，0） （1，0，1） （1，1，0） （1，1，1）

◎ × × √ √ √ √ √ ① √ √ √ √ × ② √ × √ √ ③ × √ √ ④ √ √ 满足所有条件？ z值 4 8 9 × × √ × √ √ × 第 60 页

南 京 工 业 大 学 教 案 用 纸

第 21 次课 2 学时

上次课复习： 割平面法 0-1规划 本次课题（或教材章节题目）：第五节 指派问题 教学要求： 掌握指派问题的解法 重 点：匈牙利解法；人、事数不等的指派问题；最大化的指派问题 难 点：匈牙利解法 教学手段及教具：多媒体教学。 讲授内容及时间分配： 5.1 问题的提出 5.2求解指派问题的匈牙利法 5.3一般的指派问题 20分钟 30分钟 50分钟 课后作业 P160 7、9、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 61 页

南 京 工 业 大 学 教 案 用 纸

第五节 指派问题

5.1 问题的提出

指派问题的标准形式为：

Min z =

icijxij

jixij = 1， j = 1，2 … n xij= 1， I = 1，2 … n xij = 1 或 0

j5.2求解指派问题的匈牙利法 5.2.1 指派问题最优解的性质 5.2.2 匈牙利法

第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即 (1) 从（cij）的每行元素都减去该行的最小元素；

(2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。

第二步：进行试指派，以寻求最优解。

在(bij)中找尽可能多的0元素，若能找出n个0元素，就以这n个0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找0元素，常用的步骤为：

(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。然后划去◎所在列(行)的其它0元素，记作；这表示这列所代表的任务已指派完，不必再考虑别人了。

(2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎所在行的0元素，记作． (3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。

(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。

（5）若◎元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m第三步：作最少的直线覆盖所有0元素。 (1)对没有◎的行打√号；

(2)对已打√号的行中所有含Ø元素的列打√号； (3)再对打有√号的列中含◎元素的行打√号；

(4)重复(2)，(3)直到得不出新的打√号的行，列为止； (5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数l。l应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若l＝m第四步：变换矩阵(bij)以增加0元素。

在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。

5.3一般的指派问题

5.3.1 极大化问题的求解

第 62 页

南 京 工 业 大 学 教 案 用 纸

对极大化问题

max z =

icijxij

j可令bij = M－cij，M是足够大的常数（选cij中最大元素为M即可）这时系数矩阵可变换为（bij）, bij≥0符合匈牙利法，而

z’=

ibijxij =

ji（M－cij）xij

j所以max z相当于min z’ =

bijxij, ij5.3.2人数和事数不等的指派问题 = nM －

cijxij

ij= nM － z

bij）最小解即为原问题（cij）最大解。

第 63 页

（

南 京 工 业 大 学 教 案 用 纸

第 22 次课 2 学时

上次课复习： 整数规划复习： 分支定界法 割平面法 指派问题 本次课题（或教材章节题目）：第七章 动态规划§7.1 多阶段决策问题§7.2 动态规划的基本概念和基本原理 教学要求： 掌握动态规划的基本概念和基本原理 重 点：动态规划基本概念、标号法 难 点：动态规划基本概念 教学手段及教具：多媒体教学。 讲授内容及时间分配： 第七章 动态规划 §7.1 多阶段决策问题 §7.2 动态规划的基本概念和基本原理 §7.2.1动态规划的基本概念 §7.2.2动态规划的基本思想与基本原理 20分钟 40分钟 40分钟 课后作业 P232 1、（1）、（2） 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 页

南 京 工 业 大 学 教 案 用 纸

第七章 动态规划

本章要求准确熟练地掌握动态规划的基本概念，特别是状态变量、决策变量、状态转移方程、指标函数和动态规划基本方程等，了解最优性原理，掌握动态规划的逆序解法并能够应用于典型问题的求解。

§7.1 多阶段决策问题

例7-1 最短路问题

如图7-1所示，要从A地到E地铺设管线，中间需要经过三个中间站，两点之间的连线上的数字表示距离，问应该选择什么路线，使总距离最短？

C1 2 5 5 B1 4 D1 3 6 2 C2 3 7 1 6 E A B2 5 2 5 3 3 D2 C3 2 1 B3 2 C4 7 图7-1

§7.2 动态规划的基本概念和基本原理

§7.2.1动态规划的基本概念 1.阶段（stage） 2.状态（state） 3.决策（decision） 4.策略（policy）

5.状态转移方程（state transfer equation） 6.指标函数和最优指标函数 §7.2.2动态规划的基本思想与基本原理 动态规划的基本思想概括归结如下：

1. 将多阶段决策问题按照空间或时间顺序划分成相互联系的阶段，即把一个大问题分解成一族同类型的子问题，选取恰当的状态变量和决策变量，写出状态转移方程，定义最优指标函数，写出递推关系式和边界条件。

2. 从边界条件开始，由后向前逐段递推寻找最优，在每一个阶段的计算中都要用到前一阶段的最优结果，依次进行，求得最后一个子问题的最优解就是整个问题的最优解。

3. 在多阶段决策过程中，确定阶段k的最优决策时，不是只考虑本阶段最优，而是要考虑本阶段及其所有后部子过程的整体最优，也就是说，它是把当前效益和未来效益结合起来考虑的一种方法。

R. Bellman等人在深入研究多阶段决策问题的基础上，提出了著名的最优性原理：“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策略也是最优的。这一原理是动态规划方法的核心，根据最优原理可以将一个多阶段决策过程化为若干个单阶段决策过程，当然这种转化要满足两个基本条件，这就是前文所述的指标函数的可分离性和状态变量的无后效性。

第 65 页

南 京 工 业 大 学 教 案 用 纸

第 23 次课 2 学时

上次课复习： 动态规划的基本概念 标号法 本次课题（或教材章节题目）：§7.3 动态规划模型及求解方法 教学要求： 掌握动态规划模型的建立及求解方法 重 点：动态规划建模方法及求解方法 难 点：动态规划模型的建立 教学手段及教具：多媒体教学。 讲授内容及时间分配： §7.3 动态规划模型及求解方法 §7.3.1动态规划的数学模型 §7.3.2动态规划的求解方法 30分钟 70分钟 课后作业 P233 2、（1）、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 66 页

南 京 工 业 大 学 教 案 用 纸

§7.3 动态规划模型及求解方法

§7.3.1动态规划的数学模型 1. 动态规划的基本方程

f(s)opt[vk(sk,uk)fk1(sk1)] kn,n1,,1 (7.2a)kkukDk(sk)  (7.2b)fn1(sn1)0或1 2. 建立动态规划模型的步骤

建立动态规划数学模型，一般有如下步骤： （1）划分阶段

划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。

（2）正确选择状态变量sk

选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。

（3）确定决策变量uk及允许决策集合Dk（sk）

通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。

（4）确定状态转移方程

根据k阶段状态变量sk和决策变量uk（sk）写出k+1阶段状态变量sk+1，即sk+1=Tk（sk，uk），状态转移方程应当具有递推关系。

（5）确定阶段指标函数和最优指标函数，建立动态规划基本方程

阶段指标函数vk（sk，uk）是指第k阶段的收益，最优指标函数fk（sk）是指从第k阶段状态sk出发到第n阶段末所获得收益的最优值，最后写出动态规划基本方程。

以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。

§7.3.2动态规划的求解方法

逆序解法是求解动态规划问题的一般常用方法，即由k=n递推至k=1得到问题的最优解。

一般地，如果阶段指标函数vk（sk，uk）是线性函数或凸函数时，最优指标函数fk（sk）的表达式比较容易得到，但是当vk（sk，uk）不具备上述特性时，最优指标函数fk（sk）的表达式不易得到，就需要采用数值法，即对连续变量进行离散化处理，再分散求解。

例如静态规划模型

max zg1(x1)g2(x2)gn(xn)x1x2xna xj0 j1,2,,n其动态规划基本方程为：

[gk(xk)fk1(sk1)] kn,n1,,1fk(sk)xkmaxDk(sk) fn1(sn1)0状态转移方程为sk+1=sk－xk s1=a

状态变量sk及决策变量xk都是连续变量，对其进行离散化处理，具体做法是：

第 67 页

南 京 工 业 大 学 教 案 用 纸

1. 对区间[0，a]进行分割，分割数m=

a，其中Δ是分割后的小区间的长度，其大小可以根据所求解问题要求的精度及计算机运算能力而定，分割点为0，Δ，2Δ，…，mΔ= a。

2. 规定状态变量sk及决策变量xk仅在离散点0，Δ，2Δ，…，mΔ处取值，最优指标函数fk（sk）也定义在这些离散点上。动态规划基本方程可以写为：

[gk(p)fk1(skp)] kn,n1,,1fk(sk)pmax0,1,2,q 其中sk=qΔ，xk=pΔ。 fn1(sn1)03. 由后向前逐段递推，直至求出整个过程最优解。

需要指出的是当连续变量离散化处理以后，由于状态变量和决策变量只在给定的离散点上取值，故有可能漏掉最优解，因此需要慎重选择参数m与Δ。

第 68 页

南 京 工 业 大 学 教 案 用 纸

第 24 次课 2 学时

上次课复习： 动态规划建模方法及求解方法 本次课题（或教材章节题目）：§7.4 动态规划的应用举例§7.4.1资源分配问题 教学要求： 掌握资源分配问题模型及求解方法 重 点：资源分配问题模型及求解方法 难 点：资源分配问题的求解方法 教学手段及教具：多媒体教学。 讲授内容及时间分配： §7.4.1资源分配问题 作业3、利润最大化问题 50分钟 50分钟 课后作业 P234 4、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 69 页

南 京 工 业 大 学 教 案 用 纸

§7.4 动态规划的应用举例

动态规划应用十分广泛，通过具体实例展示它在管理领域的应用，并进一步阐述动态规划方法。 §7.4.1资源分配问题

资源分配问题就是将一定数量的一种或若干种资源（原材料、资金、设备等）合理分配给若干使用者，使得资源分配后总结果最优。一种资源的分配问题称为一维资源分配问题，两种资源的分配问题称为二维资源分配问题。

假设有一种资源，数量为a，将其分配给n个使用者，分配给第i个使用者数量xi时，相应的收益为gi（xi），问如何分配使得总收入最大？这就是一维资源分配问题，该问题的数学模型为：

max zg1(x1)g2(x2)gn(xn)x1x2xna i1,2,,nxi0

（7.3）

解 式（7.3）是一个静态规划问题，应用动态规划方法求解时人为赋予时间概念，将其看作是一

个多阶段决策问题。

按变量个数划分阶段，k=1，2，…，n；

设决策变量uk=xk，表示分配给第k个使用者的资源数量；

设状态变量为sk，表示分配给第k个至第n个使用者的总资源数量； 状态转移方程：sk+1=sk－xk，其中s1=a； 允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝

阶段指标函数：vk（sk，uk）=gk（xk）表示分配给第k个使用者数量xk时的收益；

最优指标函数fk（sk）表示以数量sk的资源分配给第k个至第n个使用者所得到的最大收益，则动态规划基本方程为：

[gk(xk)fk1(sk1)] kn,,1fk(sk)0maxxksk fn1(sn1)0由后向前逐段递推，f1（a）即为所求问题的最大收益。

第 70 页

南 京 工 业 大 学 教 案 用 纸

第 25 次课 2 学时

上次课复习： 资源分配问题模型及求解方法 本次课题（或教材章节题目）：机器负荷问题、生产-库存问题 教学要求： 掌握机器负荷问题、生产-库存问题模型及求解方法 重 点：机器负荷问题、生产-库存问题模型及求解方法 难 点：机器负荷问题、生产-库存问题模型的建立 教学手段及教具：多媒体教学。 讲授内容及时间分配： 机器负荷问题 生产—库存问题 50分钟 50分钟 课后作业 P234 5、6、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 71 页

南 京 工 业 大 学 教 案 用 纸

例7-7 机器负荷问题

某工厂有100台机器，拟分四期使用，每一期都可在高、低两种不同负荷下进行生产。若把x台机器投入高负荷下进行生产，则在本期结束时将有1/3的机器损坏报废；余下的机器全部投入低负荷下进行生产，则在期末有1/10的机器报废。如果高负荷下生产时每台机器可获利润为10，低负荷下生产时每台机器可获利润为7，问怎样分配机器使四期的总利润最大？

解 将问题按周期分为4个阶段，k=1，2，3，4；

状态变量sk表示第k阶段初完好的机器数，s1=100，0≤sk≤100；

决策变量xk表示第k阶段投入高负荷下生产的机器数，

则sk－xk表示第k阶段投入低负荷下生产的机器数； 允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝ 状态转移方程：sk+1=Tk（sk，xk），即第k+1阶段初拥有的完好机器数sk+1为：

29xk(skxk)； 310阶段指标函数：vk（sk，xk）=10xk+7（sk－xk）表示第k阶段所获得的利润；

sk1最优指标函数fk（sk）表示从第k阶段初完好机器数为sk至第四阶段的最大利润，动态规划基本方程为：

[vk(sk,xk)fk1(sk1)] k4,3,2,1fk(sk)0maxxksk f5(s5)0§7.4.2生产计划问题

例7-8 （生产—库存问题）

某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。

解 以每个时期作为一个阶段，该问题分为4个阶段，k=1，2，3，4； 决策变量xk表示第k阶段生产的产品数； 状态变量sk表示第k阶段初的库存量；

以dk表示第k阶段的需求，则状态转移方程：

sk+1=sk+xk－dk k=4，3，2，1 由于期初及期末库存为0，所以s1=0，s5=0； 允许决策集合Dk（sk）的确定：

当sk≥dk时，xk可以为0，当sk去本期的库存量，

djk4jsk，所以xk的上限为min（djsk，6），故有：Dk（sk）=｛xk| max

jk4（0，dk－sk）≤xk≤min（

djk4jsk，6）｝

阶段指标函数rk（sk，xk）表示第k期的生产费用与存贮费用之和：

xk00.5sk rk(sk,xk)

3x0.5s x1,2,3,4,5,6kkk第 72 页

南 京 工 业 大 学 教 案 用 纸

最优指标函数fk（sk）表示第k期库存为sk到第4期末的生产与存贮最低费用，动态规划基本方程为：

min[rk(sk,xk)fk1(sk1)] k4,3,2,1fk(sk)xkDk(sk) f5(s5)0

第 73 页

南 京 工 业 大 学 教 案 用 纸

第 26 次课 2 学时

上次课复习： 机器负荷问题模型及求解方法、 生产-库存问题模型及求解方法 本次课题（或教材章节题目）：库存-销售问题、背包问题、复合系统工作可靠性问题模型及求解 教学要求： 掌握库存-销售问题、背包问题、复合系统工作可靠性问题模型及求解方法 重 点：库存-销售问题、背包问题、复合系统工作可靠性问题模型及求解方法 难 点：库存-销售问题、背包问题、复合系统工作可靠性问题模型的建立 教学手段及教具：多媒体教学。 讲授内容及时间分配： 库存-销售问题 背包问题 复合系统工作可靠性问题 40分钟 30分钟 30分钟 课后作业 P235 8、9、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 74 页

南 京 工 业 大 学 教 案 用 纸

例7-9 （库存—销售问题）

设某公司计划在1至4月份从事某种商品经营。已知仓库最多可存储600件这种商品，已知1月初存货200件，根据预测知1至4月份各月的单位购货成本及销售价格如表7-13所示，每月只能销售本月初的库存，当月进货供以后各月销售，问如何安排进货量和销售量，使该公司四个月获得利润最大（假设四月底库存为零）。

表7-13

月份 1 2 3 4 购货成本C 40 38 40 42 销售价格P 45 42 39 44 解 按月份划分阶段，k=1，2，3，4；

状态变量sk表示第k月初的库存量，s1=200，s5=0； 决策变量 xk表示第k月售出的货物数量，

yk表示第k月购进的货物数量；

状态转移方程：sk+1=sk+yk－xk；

允许决策集合：0≤xk≤sk，0≤yk≤600－（sk－xk）；

阶段指标函数为：pkxk－ckyk表示k月份的利润，其中pk为第k月份的单位销售价格，ck为第k月份的单位购货成本；

最优指标函数fk（sk）表示第k月初库存为sk时从第k月至第4月末的最大利润，则动态规划基本方程为：

max[pkxkckykfk1(sk1)] k4,3,2,1fk(sk)0xksk0yk600(skxk) f5(s5)0§7.4.3背包问题

有人携带背包上山，其可携带物品的重量限度为a公斤，现有n种物品可供选择，设第i种物品的单件重量为ai公斤，其在上山过程中的价值是携带数量xi的函数ci（xi），问应如何安排携带各种物品的数量，使总价值最大。这就是背包问题，类似的货物装载问题，下料问题都等同于背包问题。

背包问题的数学模型为：

max zc1(x1)c2(x2)cn(xn)a1x1a2x2anxna xi0且为整数(i1,2,,n)下面用动态规划方法求解：

按照装入物品的种类划分阶段，k=1，2，…，n； 状态变量sk表示装入第k种至第n种物品的总重量； 决策变量xk表示装入第k种物品的件数； 状态转移方程为： sk+1=sk－akxk 允许决策集合为：

sDk(sk)xk0xk[k],xk为整数

ak第 75 页

南 京 工 业 大 学 教 案 用 纸

其中[sks]表示不超过k的最大整数；

akak阶段指标函数ck（xk）表示第k阶段装入第k种商品xk件时的价值；

最优指标函数fk（sk）表示第k阶段装入物品总重量为sk时的最大价值，动态规划基本方程为：

kn,n1,,1fk(sk)maxs[ck(xk)fk1(sk1)] kxk0,1,,[] akf(s)0n1n1§7.4.4复合系统工作可靠性问题

某个机器工作系统由n个部件串联而成，其中只要有一个部件失效，则整个系统不能正常工作，因此为了提高系统工作的可靠性，在设计时，每个主要部件上都装有备用元件，一旦某个主要部件失效，备用元件会自动投入系统工作，显然备用元件越多，系统工作可靠性越大，但是备用元件越多，系统的成本、重量、体积相应增大，工作精度降低，因此在上述条件下，应选择合理的备用元件数，使整个系统的工作可靠性最大。

设第i（i=1，2，…，n）个部件上装有ui个备用元件，正常工作的概率为pi（ui），则整个系统正常工作的可靠性为Pp(u)，装第i个部件的费用为c，重量为w，要求总费用不超过c，总重

iinii

i1量不超过w，则静态规划数学模型为：

maxPpi(ui)i1nnciuici1 nwiuiwi1ui0且为整数i1,2,,n下面用动态规划方法求解。

按部件个数划分阶段，k=1，2，…，n； 决策变量uk表示部件k上的备用元件数；

状态变量xk表示从第k个到第n个部件的总费用， yk表示从第k个到第n个部件的总重量； 状态转移方程为： xk+1=xk－ckuk yk+1=yk－wkuk 允许决策集合为：

xyDk(xk,yk)uk0ukmin([k],[k]),且uk为整数

ckwk阶段指标函数为pk（uk），表示第k个部件的正常工作概率；

最优指标函数fk（xk，yk）表示由状态xk，yk出发，从部件k到部件n的系统工作最大可靠性，

第 76 页

南 京 工 业 大 学 教 案 用 纸

则动态规划基本方程为：

[pk(uk)fk1(xk1,yk1)] kn,n1,,1fk(xk,yk)ukmaxDk(xk,yk) fn1(xn1,yn1)1f1（c，w）即为整个系统工作的最大可靠性。

本章小结

一般来讲，任何多阶段决策问题只要满足无后效性，且整个过程具有递推性，这样的多阶段决策问题都可以用动态规划方法来处理。运用动态规划解决实际问题易于确定全局最优解，能得到一族最优解。但是动态规划方法也存在不足之处，一是没有统一的标准模型可供使用，建模时需要根据问题性质及数学特点加以解决，这就需要灵活的技巧及大量的实践；二是应用局限性，动态规划模型中的状态变量必须满足无后效性，而许多实际问题往往不能满足这一条件；三是存在“维数障碍”，即当变量个数（维数）太大时，问题虽然可以用动态规划方法来描述，但由于计算机内存容量的而难以求解，一般地超过三维（含三维）的问题通常不采用动态规划方法来求解。

第 77 页

南 京 工 业 大 学 教 案 用 纸

第 27 次课 2 学时

上次课复习： 动态规划回顾： 数学模型特点 求解方法特点 本次课题（或教材章节题目）：第八章 图与网络分析 §8.1 图与网络的基本知识 §8.2 树 教学要求： 掌握图与网络的基本概念、树的概念和性质 重 点：图的基本概念、树的概念和性质 难 点：树的概念和性质 教学手段及教具：多媒体教学。 讲授内容及时间分配： §8.1 图与网络的基本知识 § 8.2 树 50分钟 50分钟 课后作业 P265 9、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 78 页

南 京 工 业 大 学 教 案 用 纸

第八章 图与网络分析

通过对本章的学习，正确理解图的基本概念与基本定理，掌握用图形与矩阵表示图的方法，理解树与最小支撑数的概念及求最小树的算法。理解欧拉图与最优投递路线问题的解法。熟练掌握赋权的最短通路问题及其Dijkstra算法，会用逐次逼近法求解带有负权的最短路问题。理解最大流问题，掌握求最大流的标号算法。会求网络系统的最大流和最小费用最大流。

§8.1 图与网络的基本知识

§8.1.1 图与网络的基本概念

定义1 一个图是由点集Vvj和V中元素的无序对的一个集合E{ek}所构成的二元组，记为G=(V，E)，其中V中的元素vj叫做顶点，V表示图G 的点集合；E中的元素ek叫做边，E表示图G的边集合。

一条边的两个端点是相同的,那么称为这条边是环。

如果两个端点之间有两条以上的边，那么称为它们为多重边。

定义2 一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。

定义3 每一对顶点间都有边相连的无向简单图称为完全图。有n个顶点的无向完全图记作Kn。 有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。 定义4 以点v为端点的边的个数称为点v的度，记作d(v)。

度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。

定理1 所有顶点度数之和等于所有边数的2倍。 定理2 在任一图中，奇点的个数必为偶数。

定义5 有向图中，以vi为始点的边数称为点vi的出次，用d(vi)表示；以vi为终点的边数称为点vi的入次，用d(vi)表示；vi点的出次和入次之和就是该点的次。

定义6 设 G1=（V1 , E1），G2 =（V2 ,E2）如果 V2 V1 , E2 E1称 G2 是G1 的子图；如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图或支撑子图。

在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作v1 ，一个称为终点（或收点），记作vn ，其余的点称为中间点。对每一条弧

(vi,vj)A，对应一个数wij，称为弧上的“权”。通常把这种赋权的图称为网络。

§8.1.2 连通图

定义7 由两两相邻的点及其相关联的边构成的点边序列称为链。如：v0，e1，v1，e2，v2，e3，v3,…,vn-1, en，vn，记作（v0，v1，v2，v3,…,vn-1，vn），其链长为n，其中v0，vn分别称为链的起点和终点。若链中所含的边均不相同，则称此链为简单链；所含的点均不相同的链称为初等链，也称通路。

第 79 页

南 京 工 业 大 学 教 案 用 纸

定义8 无向图G中，连接v0 与vn的一条链，若 v0 ≠ vn 则称该链为开链，否则称为闭链或回路或圈；如果在一个圈中所含的边均不相同，称此圈为简单圈；除起点和终点外链中所含的点均不相同的圈，叫做初等圈。

定义9 图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。 §8.1.3 图的矩阵表示

定义11 对于赋权图G=（V，E），其中边(vi,vj)有权wij，构造矩阵A(aij)nn，其中：

wijaij0(vi,vj)E(vi,vj)E

称矩阵A为网络G的权矩阵。

定义12 设图G=（V，E）中顶点的个数为n，构造一个矩阵A(aij)nn，其中：

1aij0(vi,vj)E(vi,vj)E

称矩阵A为网络G的邻接矩阵。

§ 8.2 树

§ 8.2.1 树的概念和性质

定义13 一个连通的无圈的无向图叫做树。树中次为1的点称为树叶，次大于1的点称为分支点。作为树T的定义，下列定义是等价的：（1）T是一个树。（设其顶点数为n ，边数为 m ）

（2）T无圈，且mn1。 （3）T连通，且mn1。

（4）T无圈，但在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。 （5）T中任意两个顶点之间有且仅有一条链。 （6）T连通，但去掉T的任一条边，T就不连通。 § 8.2.2 图的生成树

定义14 设图K(V,E1)是图G=(V , E )的支撑子图，如果图K(V,E1)是一个树,那么称K 是G 的一个生成树（支撑树），或简称为图G的树

定理4 一个图G有生成树的充要条件是G 是连通图。 § 8.2.3 最小生成树问题

定义15 如果图K(V,E1)是图G的一个生成树，那么称E1上所有边的权的和为生成树T 的权，记作S(T)。如果图G的生成树T*的权S(T*)，在G 的所有生成树T中的权最小，即

S(T*)minS(T)，那么称T*是G的最小生成树。

T*定理5 用Kruskal算法得到的子图T(e1,e2,,en1)是一棵最小树。

第 80 页

南 京 工 业 大 学 教 案 用 纸

第 28 次课 2 学时

上次课复习： 图与网络的基本概念 树的概念和性质 本次课题（或教材章节题目）：§ 8.3 最短路问题 教学要求： 掌握最短路问题的算法 重 点：狄克斯屈拉(Dijkstra)算法 难 点：狄克斯屈拉(Dijkstra)算法 教学手段及教具：多媒体教学。 讲授内容及时间分配： 最短路问题解法思路 狄克斯屈拉(Dijkstra)算法及实例 20分钟 80分钟 课后作业 P266 12、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 81 页

南 京 工 业 大 学 教 案 用 纸

§ 8.3 最短路问题

最短路的一般提法为：设G(V,E)为连通图，图中各边(vi,vj)有权lij（lij表示vi,vj之间没有边），vs,vt为图中任意两点，求一条路，使它为从vs到vt的所有路中总权最短。即：

L()最小。

(vi,vj)lij

§ 8.3.1 狄克斯屈拉(Dijkstra)算法

Dijkstra算法，是Dijkstra在1959年提出来的。目前公认，在所有的权wij ≥0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。

Dijkstra算法的基本思想是：从vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的标号。它或者表示从vs到该点的最短路权叫做P 标号，为永久性标号（permanent label）。或者表示从vs 到该点最短路权的上界，叫做T 标号，为试探性标号（tentative label）。算法的每一步是去修改T标号，把某一个具有T 标号的点改变为具有P 标号的点，使图D中具有P 标号的顶点多一个。这样，对于有n个顶点的图，至多经过n1步，就可求出从始点vs 到各点vj 及终点vt的最短路。

算法步骤：

1.给始点vs以P标号P(vs)0，这表示从vs到 vs的最短距离为0，其余节点均给T标号，

P(vi)(i2,3,,n)。

（2）设节点vi为刚得到P标号的点，考虑点vj，其中(vi,vj)E，且vj为T标号。对vj的T标号进行如下修改： T(vj)min[T(vj),P(vi)lij]。

（3）比较所有具有T标号的节点，把最小者改为P标号，即： P(vk)min[T(vi)] 当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。

第 82 页

南 京 工 业 大 学 教 案 用 纸

第 29 次课 2 学时

上次课复习： 狄克斯屈拉(Dijkstra)算法 本次课题（或教材章节题目）：§ 8.3 最短路问题 教学要求： 掌握最短路问题的逐次逼近算法、掌握最短路问题的应用 重 点：逐次逼近算法 难 点：逐次逼近算法 教学手段及教具：多媒体教学。 讲授内容及时间分配： 逐次逼近算法 最短路问题应用实例 60分钟 40分钟 课后作业 P266 13、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 83 页

南 京 工 业 大 学 教 案 用 纸

§8.3.2 逐次逼近法

Dijkstra算法只能计算非负权的情况，本算法可用于网络中带有负权的边时，求某指定点v1到网络中任意点的最短距离。 算法的基本思路与步骤：

首先设任一点vi到任一点vj都有一条弧，如果在图G中，(vi,vj)A，则添加弧(vi,vj)，并令lij。

显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi，再沿弧(vi,vj)到vj。则v1到

vi的这条路必然也是v1到vi的最短路。否则，从v1到vj的这条路将不是最短的。于是，设P1j表示

从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：

P1jmin{P1ilij}

i利用如下的递推公式：

开始时，令 P1(j1)l1j即用v1到vj的直接距离做初始解。

从第二步起，使用递推公式：

(j1,2,,n)

P1(jk)min[P1(ik1)lij]i（k2,3,,n）

求P1j，当进行到第t步，若出现

(t)(t1)P1jP1j(t)(k) （j1,2,,n）则停止计算，P即为v1到各点的最短路长。 1j（j1,2,,n）最短路的应用：

例8.9 某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表8—2所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。

这个问题可以转化为图的问题，考虑六个节点v1、v2、v3、v4、v5、v6，其中vi (i = 1 , 2 , 3 , 4 , 5 ) 表示在第i年初要购置新设备。节点v6是虚设点，表示第五年的年底才购置新设备。再从点vi (i = 1 , 2 , 3 , 4 , 5 )引出指向vi+1，vi+2，…，v6的弧，弧（vi , vj）表示第i年年初购进的新设备一直使用到第

第 84 页

南 京 工 业 大 学 教 案 用 纸

j年（(j = 2 , 3 , 4 , 5，6)的年初。弧（vi , vj）上所赋的权为第i年的购置费加上从第i年初使用到第j年初的维修费用的总和。这样，我们得到一个赋权的有向图,于是，问题就变为用最短路问题来求解。

表8——2 计划期内费用表 年份 购置费 使用年数 维修费

1 18 0—1 5 2 20 1—2 7 3 21 2—3 12 4 23 3—4 18 5 24 4—5 25 30 v1 23 v2 42 v3 25 60 85 35 v5 45 26 32 44 v4 28 33 62 29 v6 第 85 页

南 京 工 业 大 学 教 案 用 纸

第 30 次课 2 学时

上次课复习： 逐次逼近算法 本次课题（或教材章节题目）：§8.4 最大流问题 教学要求： 掌握最大流问题的求解方法 重 点：基本概念、截集、标号法 难 点：截集、标号法 教学手段及教具：多媒体教学。 讲授内容及时间分配： §8.4.1 基本概念 §8.4.2 Fold—Fulkerson定理 §8.4.3 求最大流的标号法 30分钟 20分钟 50分钟 课后作业 P266 14、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 86 页

南 京 工 业 大 学 教 案 用 纸

§8.4 最大流问题

8.4.1 基本概念

定义19 设一个赋权有向图D=（V, A）,在V中指定一个发点vs和一个收点vt ,其它的点叫做中间点。对于D中的每一个弧（vi , vj）∈A ,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，A，C）。

网络D上的流，是指定义在弧集合E上的一个函数ff(vi,vj){fij}，其中f(vi ,vj) =fi j 叫做弧(vi，vj)上的流量。

称满足下列条件的流f为可行流：

（1）容量条件：对于每一个弧（vi ,vj）∈E，有 0 ≤ fij ≤ cij 。 （2）平衡条件：对于发点vs，有

对于收点vt ，有

对于中间点，有

(vi,vj)E(vt,vj)E(vs,vj)Efsj(vj,vs)EfjsW

ftj(vj,vt)EfjtW

fij(vj,vi)Efji0

设流f ={fij}是网络D上的一个可行流。我们把D中 fij＝cij 的弧叫做饱和弧，fij＜cij 的弧叫

做非饱和弧。fij＞0 的弧为非零流弧，fij＝0 的弧叫做零流弧。

定义20 容量网络G =（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合S,S，使vsS,vtS，则所有始点属于S，而终点属于S的弧的集合，称为由S决定的截集，记作

(S,S)。截集(S,S)中所有弧的容量之和，称为这个截集的容量，记为C(S,S)。

由于V的分解方法不同，所以截集就不相同，对应的截集的容量也不相同，其中容量最小的称为最小截集。

§8.4.2 ( Fold—Fulkerson )定理

定义21 容量网络G，若为网络中从vs到vt 的一条链，给定向为从vs到vt ，上的边凡与方向相同的称为前向边，凡与方向相反的称为后向边，其集合分别用和表示，f 是一个可行流，如果满足：

0fijcij 0fijcij(vi,vj)(vi,vj)

则称为从vs到vt 的（关于f 的）一条可增广链。

(S,S)为任一截集，定理6 设f为网络G =（V，E，C）的任一可行流，流量为W，则有WC(S,S)。

第 87 页

南 京 工 业 大 学 教 案 用 纸

*由定理可知，如果网络上的一个可行流f和网络中的一个截集(S*,S*)，满足条件

WC(S*,S*)，那么f * 一定是D上的最大流，而(S*,S*)一定是G的最小截集。

定理7（Fold—Fulkerson定理） 在任何网络中，从vs到vt的最大流的流量等于最小截集的容量。

推论 可行流f 是最大流的充分必要条件是不存在从vs到vt 的（关于f 的）一条可增广链。 §8.4.3 求最大流的标号法

标号法是从网络中的一个可行流f 出发（如果D中没有可行流 f，可以令f 是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。

一、标号过程：

1. 给发点vs 标号（0，+∞）。

2. 取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理：

（1）如果边(vj,vi)E，且fji0，那么给vj 标号(vi,j)，其中：jmin(fji,i) （2）如果边(vi,vj)E，且fjicij，那么给vj 标号(vi,j)，其中：

jmin(cijfij,i)。

3. 重复步骤（2），直到vt被标号或标号过程无法进行下去，则标号法结束。

若vt被标号，则存在一条可增广链，转调整过程（第二步）；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。 二、调整过程

设

是一条从vs到vt的可增广链，的前向边和后向边分别用和表示。设

1min{cijfij(vi,vj)}，2min{fij(vi,vj)}，

如果上没有后向弧，则令2，取min(1,2)

fij1．令 fijfijfij(vi,vj)(vi,vj) (vi,vj)2．去掉所有标号，回到第一步，对可行流重新标号。

第 88 页

南 京 工 业 大 学 教 案 用 纸

第 31 次课 2 学时

上次课复习： 最大流问题的概念 最大流问题的解法 截集的概念 本次课题（或教材章节题目）：§8.5 最小费用流问题 教学要求： 掌握最小费用流问题的概念、求解方法 重 点：基本概念、最小费用流问题的求解方法 难 点：最小费用流问题的求解方法 教学手段及教具：多媒体教学。 讲授内容及时间分配： 最小费用流问题的基本概念 最小费用流问题求解方法 25分钟 75分钟 课后作业 P268 15、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 页

南 京 工 业 大 学 教 案 用 纸

§8.5 最小费用流问题

定义23 已知网络G =（V，A，C，d），f是G上的一个可行流，为一条（关于f的）从vs到vt的可增广链，d(f)dijdij称为链的费用。

若* 是从vs到vt的可增广链中费用最小的链，则称* 是最小费用可增广链。

结论：如果可行流 f在流量为W(f )的所有可行流中的费用最小，并且*是关于f 的所有增广链中的费用最小的增广链，那么沿增广链*调整可行流f，得到的新可行流f *也是流量为W(f*)的所有可行流中的最小费用流。依次类推，当f * 是最大流时，就是所要求的最小费用流。

算法的基本思路为：

先找一个流量为W(f法将f再对f(0)(0))的最小费用流f的流量为W(f(0)，然后寻找从vs到vt的可增广链，用最大流的方

(1)调整到f(1)，使f(1)(0))，且保证f是在W(f(0))下最小的费用流，

(1)重复上述步骤。

因为dij0，显然，零流f ={0}是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f(0)={0}开始。下面的问题是：如果已知f 是流量为W(f)的最小费用流，如何寻找关于f 的

最小费用增广链？

对此，重新构造一个赋权有向图L(f)，其顶点是原网络G的顶点，而将G中的每一条边 ( vi , vj )变成两个相反方向的边（vi， vj）和(vj , vi)，并且定义图中边的权lij为：

1.当边(vi,vj)E，令

dij当fijcijlij

当fijcij（其中的含义为：这条边已经饱和，不管付出多大代价，也不能再增大流量，权为的边可从

网络中去掉。）

2.当边(vj,vi)为原来网络G中边（vi， vj）的反向边，令

dij当fij0lji

当fij0其中的含义为：此边流量已经减少到0，不能再减少，权为的边可从网络中去掉。

这样，在网络G中寻找关于f 的最小费用可增广链就等价于在L(f )中寻求从vs 到vt 的最短路。

其算法步骤为：

（1）取零流为初始可行流 ，f (0) ={0}。 （2）一般地，如果在第K1步得到最小费用流f(K1)，则构造图 L( f (k-1) )。

第 90 页

南 京 工 业 大 学 教 案 用 纸

（3）在图L(f (k-1))中，寻求从vs到vt的最短路。若不存在最短路，则f(K1)就是最小费用最大

流，停止计算；否则转（4）。

－

（4）如果存在最短路，则在可行流f (k1)的图中得到与此最短路相对应的可增广链，在可增广链上，对f(K1)进行调整，调整量为：

minmin(cijfi(jk1)),min(fi(jk1))

f(k1)ij令f(k)(k1)ijfijf(k1)ij

(vi,vj)(v(k)i,vj)则得到新可行流f。对f(k)重复上面的步骤，返回步骤（2）。(vi,vj)第 91 页

南 京 工 业 大 学 教 案 用 纸

第 32 次课 2 学时

上次课复习： 最小费用流问题的概念 最小费用流问题的求解方法 本次课题（或教材章节题目）：§8.6中国邮递员问题 补充习题 教学要求： 掌握中国邮递员问题的解法 重 点：奇偶图上作业法 难 点：奇偶图上作业法 教学手段及教具：多媒体教学。 讲授内容及时间分配： 欧拉回路与道路 奇偶图上作业法 补充习题 15分钟 35分钟 50分钟 课后作业 P268 16、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 92 页

南 京 工 业 大 学 教 案 用 纸

§8.6中国邮递员问题

问题的提出：一个邮递员从邮局出发，要走遍他所负责的每条街道去送信，问应当如何选择适当的路线，可使所走的总路程最短。

§8.5.1 欧拉回路与道路

定义24 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。

具有欧拉回路的图称为欧拉图。

定理8 一个多重连通图G是欧拉图的充分必要条件是G中无奇点。

定理9 一个多重连通有向图G是欧拉图的充分必要条件是它每个顶点的出次等于入次。 §8.5.2 奇偶图上作业法 计算步骤如下：

（1）找出图G中的所有的奇顶点（必有偶数个，如无奇点，则已是欧拉图，找出欧拉回路即可），所以如果一个连通图有奇点，就可以把它们两两配成对，而每对奇点之间必有一条通路（图是连通的），我们把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点。

（2）如果边e(u,v)上的重复边多于一条，则可从e的重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点。

（3）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则进行调整：将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）。

通常用来判别最优路线的判别标准为：

判定标准1: 在最优邮递路线上，图中的每一条边至多有一条重复边。

判定标准2 : 在最优邮递路线上，图中每一个圈的重复边的总权小于或者等于该圈总权的一半。 一个最优邮递路线一定满足判定标准1和判定标准2。反之，不难证明，一个邮递路线如果满足判定标准1和判定标准2，那么它一定是最优邮递路线 。

以上的过程可以表述为：先分奇偶点，奇点对对连，连线不重叠，重叠需改变，圈上连线长，不得过半圈。

本章小结

本章共分六节内容。第一节介绍了关于图的各种定义，这是本章的重点内容，只有弄清第一节的概念，才是学好后面五节的关键。同时还要正确理解本章所介绍的图与一般的几何图形、工程制图区别。第二节中主要介绍了树的有关概念和应用。第三节介绍了最短路问题及求解最短路的Dijkstra算法和逐次逼近法，用来解决不同条件下的最短路问题。在第四节中介绍了求最大流问题的标号算法。而如何在考虑流量的同时，考虑到流量的费用，就是第五节介绍的求最小费用流的问题。第六节在介绍欧拉圈和欧拉道路的基础上，给出了中国邮递员问题的解法。而学会如何把一些实际问题与图联系起来并用图描述，然后用我们介绍的方法把问题优化，是我们学习本章的真正目的。

第 93 页

南 京 工 业 大 学 教 案 用 纸

第 33 次课 2 学时

上次课复习： 图与网络分析主要内容回顾： 最短路问题 最大流问题 中国邮递员问题 本次课题（或教材章节题目）：第九章 网络计划§9.1 网络图§9. 2 关键路线与时间参数 教学要求： 掌握网络图的绘制、关键路线与时间参数的求解方法 重 点：关键路线与时间参数的求解方法 难 点：关键路线的求解方法 教学手段及教具：多媒体教学。 讲授内容及时间分配： §9.1 网络图 §9.1.1 画网络图的规则 §9.1.2 绘制网络图 §9.1.3 网络图分类 §9.2 关键路线与时间参数 §9.2.1 路与关键路线 §9.2.2 时间参数 15分钟 30分钟 5分钟 10分钟 40分钟 课后作业 P306 7、8、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 94 页

南 京 工 业 大 学 教 案 用 纸

第九章 网络计划

通过对本章内容的学习，掌握绘制网络图的规律和方法，对一些简单的实际问题，通过对问题的分析，会绘制网络图；熟练掌握网络图中各种参数的计算，并会求关键路线；掌握最优方案的调整方法。了解实施计划管理的过程，了解图解评审法的适用范围及解题方法。

§9.1 网络图

网络图是有向图，由带箭头的线和节点组成。箭线表示工序（或工作、活动），节点表示某项或某几项活动的开始或结束的事项（事件），每个节点有一个唯一的节点号。活动完成需要的时间写在箭杆上。

§9.1 .1 画网络图的规则 1．方向、时序和编号 2．紧前工序与紧后工序 画网络图应注意以下规则：

（1）网络只能有一个总始点（总开工事项）和一个总终点（总完工事项），即在计划网络图中，除始点和终点外，其它各节点的前后都必须有箭线连接，不可中断，不可出现缺口。

（2）网络图为有向图，且不能有回路，否则将造成逻辑上的错误，使回路上的活动永远到达不了终点。

（3）两个节点之间不能有两条或两条以上的工序。 （4）应正确表示活动之间的前行后继关系。 （5）注意虚工序的应用。 （6）注意使用平行工序。

（7）交叉作业：两件或两件以上的工序交叉进行，称为交叉作业。 §9.1.2 绘制网络图

一般绘制网络图分为三步： 1.任务的分解 2.绘制网络图 3.节点编号

§9.1.3 网络图分类

（1）肯定型与非肯定型网络图 （2）总网络图和多级网络图

§9. 2 关键路线与时间参数

§9.2.1 路与关键路线

在网络图中，从始点开始，按照各道工序的顺序，连续不断地到达终点的一条通路称为路。 完成各道工序所需时间最长的路为关键路线。关键路线上的工序称为关键工序。 §9.2.2 时间参数 一、工序时间t(i,j)

完成工序（i,j）所需的时间称为工序时间，具体确定工序时间有两种方法：

1．在具备工时定额或劳动量定额的条件下，根据这些定额资料确定工序时间。

2．如果是新活动，无统计资料可查，可以请有经验的工程技术人员用类比方法，通过主观估计，用三种时间估计法确定工序时间，得到完成时间的期望值。

估计的三种时间是：

（1）最乐观时间：即在顺利情况下，完成工序的最短时间，用符号a 表示； （2）最保守时间：即在不顺利情况下，完成工序的最长时间，用符号b 表示；

第 95 页

南 京 工 业 大 学 教 案 用 纸

（3）最可能时间：即在正常情况下，完成工序的时间，用符号m 表示。 利用三个时间，每道工序的期望工时可估计为：ta4mb 6ba其方差为：

62sai4mibibai2道工序，则工程完工时间就可以认为是一个以TE为均值。以i66i1i1s2在一项工程中，工程完工时间等于各道关键工序的平均工序时间之和。若在关键路线上有很多2为方差的正态分布。

二、事项时间参数 （1）事项的最早时间

tE(1)0t(j)max[t(i)t(i,j)]EiE

将计算的各个事项的最早时间，写在各个事项的规定位置，并用□号括起来。

（2）事项的最迟时间

tL(n)tE(n)(总工期)t(i)min{t(j)t(i,j)}

LjL将计算出来的各个事项的最迟时间，写在各个事项的指定位置，并用△括起来。

三、工序的时间参数

（1）工序的最早可能开工时间与工序的最早可能完工时间

（2）工序的最迟必须开工时间与工序的最迟必须完工时间

tES(1,j)0tES(i,j)tE(i)tEF(i,j)tE(i)t(i,j)tLF(i,n)tL(n)(总完工期)tLF(i,j)tL(j)tLS(i,j)tLF(i,j)t(i,j)}

四、时差

（1）工序的总时差

R(i,j)tLF(i,j)tEF(i,j)tLS(i,j)tES(i,j)

即：总时差 = 最迟开工时间 - 最早开工时间 = 最迟完工时间 - 最早完工时间 （2）工序的单时差

r(i,j)tES(j,k)tEF(i,j)

即单时差等于其紧后工序的最早开工时间与本工序的最早完工时间之差。在网络图中总时差为零的工序称为关键工序，由关键工序组成的从始点到终点的路线称为关键路线。

第 96 页

南 京 工 业 大 学 教 案 用 纸

第 34 次课 2 学时

上次课复习： 网络图的绘制 关键路线与时间参数的计算 本次课题（或教材章节题目）：§9.3 网络计划的优化 教学要求： 掌握网络计划的优化的内容及方法 重 点：有限资源的合理分配、最低成本日程的确定 难 点：计算最低成本日程 教学手段及教具：多媒体教学。 讲授内容及时间分配： §9.3 网络计划的优化 一、缩短工程进度 二、有限资源的合理分配 三、最低成本日程 10分钟 40分钟 50分钟 课后作业 P309 14、 《运筹学》 《运筹学教程》 《运筹学》 《运筹学应用案例》 钱颂迪 胡运权 牛映武 陶谦坎 主编 主编 主编 主编 清华大学出版社 清华大学出版社 西安交大出版社 机械工业出版社 参考资料 注：本页为每次课教案首页

第 97 页

南 京 工 业 大 学 教 案 用 纸

§9.3 网络计划的优化

所谓网络计划的优化是指通过对网络作进一步的改善和调整，寻找并行作业机会、合理利用作业时差、合理分配资源以达到缩短工期，节约资源，减低成本的目的，求得最佳效果。

一、缩短工程进度

在现有资源允许的条件下，缩短工程进度的主要途径有：

1. 采取适当的技术措施，组织力量对关键工序进行攻关，压缩关键工序的工序时间。 2.改变工序：在工艺流程允许的条件下，把关键路线上串联的关键工序改为平行工序或交叉工序，合理调配工程技术人员，缩短工期。

3. 利用时差：由于非关键工序都有时差，所以这些工序在开工时间上，具体工时上都有一定的弹性。因此从非关键工序上抽调部分人力、物力到关键工序上，缩短关键工序的时间。

二、有限资源的合理分配

（1）当资源受到时，在保证不推迟或尽量少推迟工程完工时间的前提下，合理安排与充分利用有限资源。

（2）根据工程计划的要求，进一步安排与落实有限资源，以保证工程计划的实施。

（3）在考虑最大节省和充分利用有限资源的前提下，可以适当调整工程计划的完工时间。 三、最低成本日程

项目或任务的成本一般可以分成两类：

1.直接费用：如完成各项工作直接所需人力、资源、设备等费用。 2.间接费用：如管理人员的工资、办公费、采购费用、设备租金等。

费

用

总成本

直接费用

间接费用

工序时间 最低成本日程

图9—22

通过计算网络计划的不同完工期相应的总费用，以求得成本最低的日程安排就是“最低成本日程”，又称“工期——成本优化”。

工序（i,j）从正常工时每缩短一个单位时间所需增加的费用称为成本斜率（成本变动率），用cij表示。

cij

mijMijDijdij

第 98 页