1
运筹学
北京理工大学
管理与经济学院
吴祈宗教授
2
1、绪 论
2、线 性 规 划
3、运 输 问 题
4、动 态 规 划
5、图与网络分析
6、排 队 论
7、教学日历
运 筹 学 —— 目录
说 明
本教学课件是与教材紧密配合
使用的，教材为：
,运筹学, 杨民助编著
西安交通大学出版社,2000年 6月
参考书：
,运筹学, 清华大学出版社
或其他的, 运筹学, 方面本科教材
的相关内容
下面所标注的页号，均为本
课程教材的页号。例如：
p123 表示第 123页
p31-34 表示从第 31页到第 34页
3
绪 论
运筹学（ Operational Research) 直译为“运作研究”
运筹学是运用科学的方法（如分析、试验、
量化等）来决定如何最佳地运营和设计各种系
统的一门学科。运筹学对经济管理系统中的人
力、物力、财力等资源进行统筹安排，为决策
者提供有依据的最优方案，以实现最有效的管
理。
? 运筹学有广泛应用 （可以自己找一些参考书看）
? 运筹学的产生和发展 （可以自己找一些参考书看）
4
运筹学解决问题的过程
1）提出问题：认清问题
2）寻求可行方案：建模、求解
3）确定评估目标及方案的标准或方法、途径
4）评估各个方案：解的检验、灵敏性分析等
5）选择最优方案：决策
6）方案实施：回到实践中
7）后评估：考察问题是否得到完满解决
1） 2） 3）：形成问题； 4） 5）分析问题：定性分
析与定量分析。构成决策。
5
运筹学的分支
? 线性规划
? 非线性规划
? 整数规划
? 动态规划
? 多目标规划
? 随机规划
? 模糊规划等
? 图与网络理论
? 存储论
? 排队论
? 决策论
? 对策论
? 排序与统筹方法
? 可靠性理论等
6
运筹学在工商管理中的应用
? 生产计划：生产作业的计划、日程表的编排、合理下
料、配料问题、物料管理等
? 库存管理：多种物资库存量的管理，库存方式、库存
量等
? 运输问题：确定最小成本的运输线路、物资的调拨、
运输工具的调度以及建厂地址的选择等
? 人事管理：对人员的需求和使用的预测，确定人员编
制、人员合理分配，建立人才评价体系等
? 市场营销：广告预算、媒介选择、定价、产品开发与
销售计划制定等
? 财务和会计：预测、贷款、成本分析、定价、证券管
理、现金管理等
*** 设备维修、更新，项目选择、评价，工程优化设计与管理等
7
运筹学方法使用情况 (美 1983)（ %）
0
10
20
30
40
50
60
70
í±
??
??
??
?ú
?￡
?a
í?
??
??
??
??
D?
1?
??
??
?ó
??
·
?
??
D?
1?
??
?ˉ
ì?
1?
??
??
°?
??
2ó °? ê1 ó? óD ê±ê1 ó? ?- ±￡ ê1 ó?
8
0
10
20
30
40
50
60
70
80
90
í±
??
??
??
?ú
?￡
?a
í?
??
??
??
??
D?
1?
??
??
?ó
??
·
?
??
D?
1?
??
?ˉ
ì?
1?
??
??
°?
??
2ó °? ê1 ó? óD ê±ê1 ó? ?- ±￡ ê1 ó?
运筹学方法在中国使用情况 (随机抽样 )（ %）
9
运筹学的推广应用前景
? 据美劳工局 1992年统计预测,
运筹学应用分析人员需求从 1990年到 2005
年的增长百分比预测为 73%,增长速度排到各项
职业的前三位,
结论,
? 运筹学在国内或国外的推广前景是非常广阔的
? 工商企业对运筹学应用和需求是很大的
? 在工商企业推广运筹学方面有大量的工作要做
10
? 学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程
中，应该多向自己提问，如一个方法的实质是什么，为什么这样做，怎
么做等。
? 自学时要掌握三个重要环节：
1、认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运
筹学教材都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助
你开阔思路，使学习深入。但是，把时间过多放在参考资料上，会导致思路分散，不利于
学好。
2、要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助你理解概念、理论
的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因此，做
题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整体，各节内容有内在联
系，只要学到一定程度，知识融会贯通起来，你做题的正确性自己就有判断。
3、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来该书所学内容。这
样，你才能够从较高的角度来看问题，更深刻的理解有关知识和内容。这就称作“把书读
薄”，若能够结合自己参考大量文献后的深入理解，把相关知识从更深入、广泛的角度进
行论述，则称之为“把书读厚”
? 在建数学模型时要结合实际应用，要学会用计算机软件解决问题 。
如何学习运筹学课程
返回目录
11
各章节的重点、难点
及注意事项
12
1,线 性 规 划
线性规划模型：
目标函数,Max z = 50 x1 + 100 x2
约束条件,s.t,x1 + x2 ≤ 300
2 x1 + x2 ≤ 400
x2 ≤ 250
x1,x2 ≥ 0
**看 p 7--9 例 1-1,1-2
例 1,某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时
及 A,B两种原材料的消耗以及资源的限制，如下表：
问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？
甲 乙 资源限制
设备 1 1 300 台时
原料 A 2 1 400 千克
原料 B 0 1 250 千克
单位产品获利 50 元 100 元
13
1,线 性 规 划 （续 1.1）
1,1 线性规划的概念
? 线性规划的组成, 目标函数 Max f 或 Min f
约束条件 s.t,(subject to) 满足于
决策变量 用符号来表示可控制的因素
? 一般形式 ( p10-- p 11)
目标函数,Max （ Min） z = c1 x1 + c2 x2 + … + c n xn
约束条件,s.t,a11 x1 + a12 x2 + … + a1n xn ≤ （ =,≥ ） b1
a21 x1 + a22 x2 + … + a2n xn ≤ （ =,≥ ） b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ （ =,≥ ） bm
x1, x2, …, xn ≥ 0
? 标准形式 ( p11-- p 15,例 1-3)
目标函数,Max z = c1 x1 + c2 x2 + … + c n xn
约束条件,s.t,a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1, x2, …, xn ≥ 0
**练习,p 68--70 习题 1 1-1,1-2
14
1,线 性 规 划 （续 1.2）
1,2 线性规划问题解的概念及性质
? 熟悉下列一些解的概念（ p15--16）
可行解、可行解集（可行域），最优解、最优值，基、基变量、非基变量，基本
解、基本可行解，可行基、最优基。
?图解方法及各有关概念的意义（ p16--20）
看：图解法步骤，例 1-4,1-5,1-6,1-7,1-8,1-9
下一页是一个图解法解题的一个例子，右图中的阴影部分为可行域。
? 单纯形法的理论基础（ p20--30）
1.2.3段要求看懂，了解如何直接通过对约束矩阵的分析求出基本可行解
1.2.4,1.2.5两段应注重结论的了解，如单纯形法思想和关于线性规划解的四个
定理，而对证明过程则可根据自己的数学基础来掌握：
基础很好，可要求掌握；否则，也可略去不看。
**习题,p70 习题 1 1-3,1-4
15
1,线 性 规 划 （续 1.2）
例 1.
目标函数：
Max z = 50 x1 + 100 x2
约束条件：
s.t,
x1 + x2 ≤ 300 (A)
2 x1 + x2 ≤ 400 (B)
x2 ≤ 250 (C)
x1 ≥ 0 (D)
x2 ≥ 0 (E)
得到最优解：
x1 = 50,x2 = 250
最优目标值 z = 27500
16
1,线 性 规 划 （续 1.3）
1,3 单纯形法
利用单纯形表的方法求解线性规
划 —— 重点 (p30--45 1.3.1,1.3.2,
1.3.3)
此项内容是本章的重点，学习中应
注意掌握表格单纯形法求解线性规划问
题的基本过程。要通过读懂教材内容以
及大量练习来掌握。
17
1,线 性 规 划 （续 1.3）
? 表格单纯形法 ( p40-- p 45)
? 考虑,bi > 0 i = 1,…,m
Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn ≤ b1
a21 x1 + a22 x2 + … + a2n xn ≤ b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ bm
x1, x2, …, xn ≥ 0
? 加入松弛变量：
Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2
…… ……
am1 x1 + am2 x2 + … + amn xn+ xn+m = bm
x1, x2, …, xn, xn+1, …, xn+m ≥ 0
18
显然,xj= 0 j = 1,…,n ; xn+i = bi i = 1,…,m 是基本可行解
对应的基是单位矩阵。
以下是初始单纯形表：
m m
其中,f = -∑ cn+i bi ?j = cj -∑ cn+i aij 为检验数 cn+i = 0 i= 1,…,m
i = 1 i = 1
an+i,i = 1,an+i,j = 0 ( j≠i ) i,j = 1,…,m
1,线 性 规 划 （续 1.3）
c
1 ?
c
n
c
n + 1 ?
c
n + m
C
B
X
B x
1 ?
x
n
x
n + 1 ?
x
n + m
θ
i
c
n + 1
x
n + 1
b
1
a
11 ?
a
1n
a
1 n + 1 ?
a
1 n + m θ 1
c
n + 2
x
n + 2
b
2
a
21 ?
a
2n
a
2 n + 1 ?
a
2 n + m θ 2
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
c
n + m
x
n + m
b
m
a
m1 ?
a
mn
a
m n + 1 ?
a
m n + m θ m
-z f σ
1
? σ
n
0 ? 0
19
1,线 性 规 划 （续 1.3单纯形法解题例）
50 100 0 0 0
C
B
X
B
x
1
x
2
x
3
x
4
x
5
θ
i
0 x
3
300 1 1 1 0 0 300
0 x
4
400 2 1 0 1 0 400
0 x
5
250 0 (1) 0 0 1 250
-z 0 50 100* 0 0 0
0 x
3
50 (1) 0 1 0 -1 50
0 x
4
150 2 0 0 1 -1 75
100 x
2
250 0 1 0 0 1
-z - 25 00 0 50* 0 0 0 - 10 0
50 x
1
50 1 0 1 0 -1
0 x
4
50 0 0 -2 1 1
100 x
2
250 0 1 0 0 1
-z - 27 50 0 0 0 - 50 0 - 50
例 1。化标准形式,Max z = 50 x1 + 100 x2
s.t,x1 + x2 + x3 = 300
2 x1 + x2 + x4 = 400
x2 + x5 = 250
x1,x2,x3,x4,x5 ≥ 0
最优解 x1 = 50 x2 = 250 x4 = 50（松弛标量，表示原料 A有 50个单位的剩余）
20
? 注意：单纯形法中，
1、每一步运算只能用矩阵初等行变换；
2、表中第 3列的数总应保持非负（ ≥ 0）；
3、当所有检验数均非正（ ≤ 0）时，得到最
优单纯形表。
1,线 性 规 划 （续 1.3）
21
1,线 性 规 划 （续 1.3）
? 一般情况的处理及注意事项的强调（ p45--55）
1.3.4段主要是讨论初始基本可行解不明显时，常用的方法。
要弄清它的原理，并通过例 1-14 ~ 例 1-17掌握这些方法，同
时进一步熟悉用单纯形法解题。
考虑一般问题,bi > 0 i = 1,…,m
Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1, x2, …, xn ≥ 0
22
1,线 性 规 划 （续 1.3）
? 大 M法,引入人工变量 xn+i ≥ 0 i = 1,…,m ; 充
分大正数 M 。 得到，
Max z = c1 x1 + c2 x2 + … + c n xn + M xn+1 + … + M x n+m
s.t,a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2
…… ……
am1 x1 + am2 x2 + … + amn xn + xn+m = bm
x1, x2, …, xn, xn+1, …, xn+m ≥ 0
显然,xj= 0 j=1,…,n ; xn+i = bi i =1,…,m 是基本可行解
对应的基是单位矩阵。
? 结论：若得到的最优解满足 xn+i = 0 i = 1,…,m 则是原
问题的最优解；否则，原问题无可行解。
23
1,线 性 规 划 （续 1.3）
? 两阶段法,引入人工变量 xn+i ≥ 0,i = 1,…,m ；构造，
Max z = - xn+1 - xn+2 - … - xn+m
s.t,a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2
…… ……
am1 x1 + am2 x2 + … + amn xn + xn+m = bm
x1, x2, …, xn, xn+1, …, xn+m ≥ 0
? 第一阶段求解上述问题：
显然,xj= 0 j=1,…,n ; xn+i = bi i =1,…,m 是基本可行解
对应的基是单位矩阵。
? 结论：若得到的最优解满足 xn+i = 0 i = 1,…,m 则是原问
题的基本可行解；否则，原问题无可行解。
? 得到原问题的基本可行解后，第二阶段求解原问题。
24
1,线 性 规 划 （续 1.3）例题
例：（ LP） Max z = 5 x1 + 2 x2 + 3 x3 - x4
s.t,x1 + 2 x2 + 3 x3 = 15
2 x1 + x2 + 5 x3 = 20
x1 + 2 x2 + 4 x3 + x4 = 26
x1,x2,x3,x4 ≥ 0
? 大 M法问题（ LP - M）
Max z = 5 x1 + 2 x2 + 3 x3 - x4 - M x5 - M x6
s.t,x1 + 2 x2 + 3 x3 + x5 = 15
2 x1 + x2 + 5 x3 + x6 = 20
x1 + 2 x2 + 4 x3 + x4 = 26
x1,x2,x3,x4,x5,x6 ≥ 0
? 两阶段法,第一阶段问题（ LP - 1）
Max z = - x5 - x6
s.t,x1 + 2 x2 + 3 x3 + x5 = 15
2 x1 + x2 + 5 x3 + x6 = 20
x1 + 2 x2 + 4 x3 + x4 = 26
x1,x2,x3,x4,x5,x6 ≥ 0
25
1,线 性 规 划 （续 1.3）大 M法例
5 2 3 -1 -M -M
C
B
X
B
x
1
x
2
x
3
x
4
x
5
x
6
θ
i
-M x
5
15 1 2 3 0 1 0 5
-M x
6
20 2 1 ( 5) 0 0 1 4
-1 x
4
26 1 2 4 1 0 0 6.5
-z 35M + 26 3M + 6 3M + 4 8M + 7 0 0 0
-M x
5
3 - 1/ 5 ( 7/ 5) 0 0 1 - 3/ 5 15/ 7
3 x
3
4 2/ 5 1/ 5 1 0 0 1/ 5 20
-1 x
4
10 - 3/ 5 6/ 5 0 1 0 - 4/ 5 25/ 3
-z 3M - 2 - M / 5+ 16/ 5 7/ 5M + 13/ 5 0 0 0 - 8/ 5M - 7/ 5
2 x
2
15/ 7 - 1/ 7 1 0 0 5/ 7 - 3/ 7
3 x
3
25/ 7 ( 3/ 7) 0 1 0 - 1/ 7 2/ 7 25/ 3
-1 x
4
52/ 7 - 3/ 7 0 0 1 - 6/ 7 - 2/ 7
-z - 53/ 7 25/ 7 0 0 0 - M - 13 / 7 - M - 2 / 7
2 x
2
10/ 3 0 1 1/ 3 0 2/ 3 - 1/ 3
5 x
1
25/ 3 1 0 7/ 3 0 - 1/ 3 2/ 3
-1 x
4
11 0 0 1 1 -1 0
-z - 1 12/ 3 0 0 - 25/ 3 0 - M - 2 / 3 - M + 8/ 3
?大 M法 （ LP - M）
?得到最优解,(25/3,10/3,0,11)T 最优目标值,112/3
26
1,线 性 规 划 （续 1.3）两阶段法例
0 0 0 0 -1 -1
C
B
X
B
x
1
x
2
x
3
x
4
x
5
x
6
θ
i
-1 x
5
15 1 2 3 0 1 0 5
-1 x
6
20 2 1 ( 5) 0 0 1 4
0 x
4
26 1 2 4 1 0 0 6.5
-z 35 3 3 8 0 0 0
-1 x
5
3 - 1/ 5 ( 7/ 5) 0 0 1 - 3/ 5 15/ 7
0 x
3
4 2/ 5 1/ 5 1 0 0 1/ 5 20
0 x
4
10 - 3/ 5 6/ 5 0 1 0 - 4/ 5 25/ 3
-z 3 - 1/ 5 7/ 5 0 0 0 - 8/ 5
0 x
2
15/ 7 - 1/ 7 1 0 0 5/ 7 - 3/ 7
0 x
3
25/ 7 3/ 7 0 1 0 - 1/ 7 2/ 7 25/ 3
0 x
4
52/ 7 - 3/ 7 0 0 1 - 6/ 7 - 2/ 7
-z 0 0 0 0 0 -1 -1
?第一阶段 （ LP - 1）
?得到原问题的基本可行解,(0,15/7,25/7,52/7)T
27
1,线 性 规 划 （续 1.3）两阶段法例
5 2 3 -1
C
B
X
B x 1 x 2 x 3 x 4 θ i
2 x
2
1 5 / 7 - 1 / 7 1 0 0
3 x
3
2 5 / 7 (3/ 7 ) 0 1 0 2 5 / 3
-1 x 4 5 2 / 7 - 3 / 7 0 0 1
-z - 5 3 / 7 2 5 / 7 0 0 0
2 x
2
1 0 / 3 0 1 1 / 3 0
5 x
1
2 5 / 3 1 0 7 / 3 0
-1 x
4
11 0 0 1 1
-z - 1 1 2 / 3 0 0 - 2 5 / 3 0
?第二阶段 把基本可行解填入表中
?得到原问题的最优解,(25/3,10/3,0,11)T
?最优目标值,112/3
28
1,线 性 规 划 （续 1.3）
1.3.5 矩阵描述 —— 此段为选读，有
困难者可不看。
1.3.6 段单纯形迭代过程中的几点注
意事项是对有关内容的强调和补充，要
认真学习、理解。
**习题,p70--71 习题 1 1-5,1-6
29
1,4 线性规划应用 —— 建模（ p55--68）
本节介绍了些线性规划应用的例子，这些例子从多个方面介绍建模对未来
是很有用的，应认真对待。
除了教材上的例子之外，还有许多其它应用：
* 合理利用线材问题：如何下料使用材最少
* 配料问题：在原料供应量的限制下如何获取最大利润
* 投资问题：从投资项目中选取方案，使投资回报最大
* 产品生产计划：合理利用人力、物力、财力等，使获利最大
* 劳动力安排：用最少的劳动力来满足工作的需要
* 运输问题：如何制定调运方案，使总运费最小
**下面是一些建模的例子，有兴趣者，可作为练习。这些例子有一定的难度，做
起来会有一些困难。
**习题,p72--73 习题 1 1-7,1-8,1-9,1-10
1,线 性 规 划 （续 1.4）
返回目录
30
例．某昼夜服务的公交线路每天各时间段内所需司机和乘务人
员数如下：
设司机和乘务人员分别在各时间段一开始时上班，并连续
工作八小时，问该公交线路怎样安排司机和乘务人员，既能
满足工作需要，又配备最少司机和乘务人员?
班次 时间 所需人数
1 6, 00 —— 10, 00 60
2 10, 00 —— 14, 00 70
3 14, 00 —— 18, 00 60
4 18, 00 —— 22, 00 50
5 22, —— 2, 00 20
6 2, 00 —— 6, 00 30
例：人力资源分配的问题
31
解：设 xi 表示第 i班次时开始上班的司机和乘务人
员数,这样我们建立如下的数学模型。
目标函数,Min x1 + x2 + x3 + x4 + x5 + x6
约束条件,s.t,x1 + x6 ≥ 60
x1 + x2 ≥ 70
x2 + x3 ≥ 60
x3 + x4 ≥ 50
x4 + x5 ≥ 20
x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0
例：人力资源分配的问题（续）
32
例,明兴公司生产甲、乙、丙三种产品，都需要经过铸
造、机加工和装配三个车间。甲、乙两种产品的铸件可以外
包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证
质量。数据如下表。问：公司为了获得最大利润，甲、乙、
丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本
公司铸造和由外包协作各应多少件？
甲 乙 丙 资源限制
铸造工时 ( 小时 / 件 ) 5 10 7 8000
机加工工时 ( 小时 / 件 ) 6 4 8 12000
装配工时 ( 小时 / 件 ) 3 2 2 10000
自产铸件成本 ( 元 / 件 ) 3 5 4
外协铸件成本 ( 元 / 件 ) 5 6 --
机加工成本 ( 元 / 件 ) 2 1 3
装配成本 ( 元 / 件 ) 3 2 2
产品售价 ( 元 / 件 ) 23 18 16
例：生产计划的问题
33
解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙
三种产品的件数,x4,x5 分别为由外协铸造再由本公司机加
工和装配的甲、乙两种产品的件数。
求 xi 的利润：利润 = 售价 - 各成本之和
可得到 xi（ i=1,2,3,4,5）的利润分别为 15,10,7,13,9元。
这样我们建立如下的数学模型。
目标函数,Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5
约束条件,s.t,5x1 + 10x2 + 7x3 ≤ 8000
6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000
3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000
x1,x2,x3,x4,x5 ≥ 0
例：生产计划的问题（续）
34
例,永久机械厂生产 Ⅰ, Ⅱ, Ⅲ 三种产品，均要经过 A,B 两
道工序加工。假设有两种规格的设备 A1,A2能完成 A 工序；
有三种规格的设备 B1,B2,B3能完成 B 工序。 Ⅰ 可在 A,B的
任何规格的设备上加工； Ⅱ 可在任意规格的 A设备上加工，
但对 B工序，只能在 B1设备上加工； Ⅲ 只能在 A2与 B2设备上加
工；数据如下表。问：为使该厂获得最大利润，应如何制定
产品加工方案？
产品单件工时
设备 Ⅰ Ⅱ Ⅲ
设备的
有效台时
满负荷时的
设备费用
A
1
5 10 6000 300
A
2
7 9 12 10000 321
B
1
6 8 4000 50
B
2
4 11 7000 783
B
3
7 4000 200
原料 （元 / 件） 0.25 0.35 0.50
售价 （元 / 件） 1.25 2.00 2.80
例：生产计划的问题（续）
35
解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工
的数量。
利润 = [（销售单价 - 原料单价） * 产品件数 ]之和 - （每台时的
设备费用 *设备实际使用的总台时数）之和。
这样我们建立如下的数学模型,
Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-
0.5x221-0.4475x122-1.2304x322-0.35x123
s.t,5x111 + 10x211 ≤ 6000 （ 设备 A1 ）
7x112 + 9x212 + 12x312 ≤ 10000 （ 设备 A2 ）
6x121 + 8x221 ≤ 4000 （ 设备 B1 ）
4x122 + 11x322 ≤ 7000 （ 设备 B2 ）
7x123 ≤ 4000 （ 设备 B3 ）
x111+ x112- x121- x122- x123 = 0 （ Ⅰ 产品在 A,B工序加工的数量相等）
x211+ x212- x221 = 0 （ Ⅱ 产品在 A,B工序加工的数量相等）
x312 - x322 = 0 （ Ⅲ 产品在 A,B工序加工的数量相等）
xijk ≥ 0,i = 1,2,3; j = 1,2; k = 1,2,3
例：生产计划的问题（续）
36
例、某工厂要做 100套钢架，每套用长为 2.9 m,2.1 m,1.5 m的
圆钢各一根。已知原料每根长 7.4 m，问：应如何下料，可
使所用原料最省？
解,设计下列 5 种下料方案
方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8
2, 9 m 1 2 0 1 0 1 0 0
2, 1 m 0 0 2 2 1 1 3 0
1, 5 m 3 1 2 0 3 1 0 4
合计 7, 4 7, 3 7, 2 7, 1 6, 6 6,5 6,3 6, 0
剩余料头 0 0, 1 0, 2 0, 3 0, 8 0, 9 1,1 1, 4
假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根
数。这样我们建立如下的数学模型。
目标函数,Min x1 + x2 + x3 + x4 + x5
约束条件,s.t,x1 + 2x2 + x4 ≥ 100
2x3 + 2x4 + x5 ≥ 100
3x1 + x2 + 2x3 + 3x5 ≥ 100
x1,x2,x3,x4,x5 ≥ 0
例：套裁下料问题
37
例 6．某工厂要用三种原料 1,2,3混合调配出三种不
同规格的产品甲、乙、丙，数据如下表。问：该厂
应如何安排生产，使利润收入为最大？
产品名称 规格要求 单价 （元 /kg ）
甲 原材料 1 不少于 50 %,原材料 2 不超过 25% 50
乙 原材料 1 不少于 25 %,原材料 2 不超过 50% 35
丙 不限 25
原材料名称 每天最多供应量 单价 （元 /kg ）
1 100 65
2 100 25
3 60 35
例：配料问题
38
例：配料问题（续）
解,设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含
量。这样我们建立数学模型时，要考虑：
对于甲,x11,x12,x13；
对于乙,x21,x22,x23；
对于丙,x31,x32,x33；
对于原料 1,x11,x21,x31；
对于原料 2,x12,x22,x32；
对于原料 3,x13,x23,x33；
目标函数,利润最大，利润 = 收入 - 原料支出
约束条件,规格要求 4 个；
供应量限制 3 个。
39
Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33
s.t,0.5 x11-0.5 x12 -0.5 x13 ≥ 0 （原材料 1不少于 50%）
-0.25x11+0.75x12 -0.25x13 ≤ 0 （原材料 2不超过 25%）
0.75x21-0.25x22 -0.25x23 ≥ 0 （原材料 1不少于 25%）
-0.5 x21+0.5 x22 -0.5 x23 ≤ 0 （原材料 2不超过 50%）
x11+ x21 + x31 ≤ 100 ( 供应量限制）
x12+ x22 + x32 ≤ 100 ( 供应量限制）
x13+ x23 + x33 ≤ 60 ( 供应量限制）
xij ≥ 0,i = 1,2,3; j = 1,2,3
例：配料问题（续）
40
例 8．某部门现有资金 200万元，今后五年内考虑给以下的项目投资。已知：项
目 A：从第一年到第五年每年年初都可投资，当年末能收回本利 110%；项目 B：从第
一年到第四年每年年初都可投资，次年末能收回本利 125%，但规定每年最大投资额
不能超过 30万元；项目 C：需在第三年年初投资，第五年末能收回本利 140%，但规
定最大投资额不能超过 80万元；项目 D：需在第二年年初投资，第五年末能收回本
利 155%，但规定最大投资额不能超过 100万元；
据测定每万元每次投资的风险指数如右表：
问：
a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最
大？
b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在 330万元
的基础上使得其投资总的风险系数为最小？
项目 风险指数 （次 /万元）
A 1
B 3
C 4
D 5, 5
解,1） 确定决策变量：连续投资问题
设 xij ( i = 1 - 5,j = 1,2,3,4)表示第 i 年初投资于 A(j=1),B(j=2),C(j=3)、
D(j=4)项目的金额。这样我们建立如下的决策变量：
A x11 x21 x31 x41 x51
B x12 x22 x32 x42
C x33
D x24
例：投资问题
41
2）约束条件：
第一年,A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200；
第二年,B次当年末才可收回投资故第二年年初的资金为 x11，于是 x21 + x22+ x24 = 1.1x11；
第三年：年初的资金为 x21+x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12；
第四年：年初的资金为 x31+x22，于是 x41 + x42 = 1.1x31+ 1.25x22；
第五年：年初的资金为 x41+x32，于是 x51 = 1.1x41+ 1.25x32；
B,C,D的投资限制,xi2 ≤ 30 ( I =1, 2,3,4 ),x33 ≤ 80, x24 ≤ 100
3）目标函数及模型：
a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24
s.t,x11+ x12 = 200
x21 + x22+ x24 = 1.1x11；
x31 + x32+ x33 = 1.1x21+ 1.25x12；
x41 + x42 = 1.1x31+ 1.25x22；
x51 = 1.1x41+ 1.25x32；
xi2 ≤ 30 ( I =1, 2,3,4 ),x33 ≤ 80, x24 ≤ 100
xij ≥ 0 ( i = 1, 2,3,4,5； j = 1,2,3,4）
b) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24
s.t,x11+ x12 = 200
x21 + x22+ x24 = 1.1x11；
x31 + x32+ x33 = 1.1x21+ 1.25x12；
x41 + x42 = 1.1x31+ 1.25x22；
x51 = 1.1x41+ 1.25x32；
xi2 ≤ 30 ( I =1, 2,3,4 ),x33 ≤ 80, x24 ≤ 100
1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330
xij ≥ 0 ( i = 1, 2,3,4,5； j = 1,2,3,4）
例：投资问题（续）
42
2、线性规划问题的进一步研究（ 2.1）
2,1 对偶原理
1、对偶问题,考虑前文例 1
若设备和原料都用于外协加工，工厂收取加工费。试问：
设备工时和原料 A,B 各如何收费才最有竞争力？
设 y1, y2, y3 分别为每设备工时、
原料 A,B每单位的收取费用
Max z = 50 x1 + 100 x2 Min f = 300 y1 + 400 y2 + 250 y3
s.t,x1 + x2 ≤ 300 s.t,y1 + 2 y2 + ≥ 50
2 x1 + x2 ≤ 400 （不少于甲产品的利润）
x2 ≤ 250 y1 + y2 + y3 ≥ 100
x1,x2 ≥ 0 y1,y2,y3 ≥ 0
43
2、对偶定义
? 对称形式,互为对偶
(LP) Max z = cT x ? (DP) Min f = bT y
s.t,Ax ≤ b s.t,AT y ≥ c
x ≥ 0 y ≥ 0
“Max -- ≤,,Min-- ≥”
? 一般形式：
若一个问题的某约束为等式，那么对应的对偶问题的
相应变量无非负限制；反之,若一个问题的某变量无非负
限制，那么对应的对偶问题的相应约束为等式。
2、线性规划问题的进一步研究（ 2.1）
44
3、对偶定理 （原问题与对偶问题解的关系）
考虑（ LP）和（ DP）
定理 2-1 （弱对偶定理）若 x,y 分别为（ LP）和（ DP）的可行
解，那么 cT x ≤ bT y 。
推论 若（ LP）可行，那么（ LP）无有限最优解的充分必要条
件是（ LD）无可行解。
定理 2-2 （最优性准则定理）若 x,y 分别为（ LP）和（ DP）的
可行解，且 cT x = bT y,那么 x,y分别为（ LP）和（ DP）的
最优解。
定理 2-3 （主对偶定理）若（ LP）和（ DP）均可行，那么
（ LP）和（ DP）均有最优解，且最优值相等。
以上定理、推论对任意形式的相应线性规划的对偶均有效
**习题,p 99 习题 2 2-1
2、线性规划问题的进一步研究（ 2.1）
45
4、影子价格 —— 是一个向量，它的分量表示最优目
标值随相应资源数量变化的变化率。
若 x*,y* 分别为（ LP）和（ DP）的最优解，
那么,cT x* = bT y* 。
根据 f = bT y* = b1y1* + b2y2* + ?? + bmym*
可知 ?f / ?bi = yi*
yi* 表示 bi 变化 1个单位对目标 f 产生的影响，称
yi* 为 bi的影子价格。
注意：若 B 是最优基,y* = (BT)-1 cB 为影子价格向量。
2、线性规划问题的进一步研究（ 2.1）
46
5、由最优单纯形表求对偶问题最优解
第 1章例 1。化标准形式,Max z = 50 x1 + 100 x2
s.t,x1 + x2 + x3 = 300, 2 x1 + x2 + x4 = 400
x2 + x5 = 250, x1,x2,x3,x4,x5 ≥ 0 I
O
B=(p1,p4,p2 )
(BT)-1 cB
B-1
最优解 x1 = 50 x2 = 250 x4 = 50（松弛标量，表示原料 A有 50个单位的
剩余） 影子价格 y1 = 50 y2 = 0 y3 = 50,B-1对应的检验数 (BT)-1 cB 。
2、线性规划问题的进一步研究（ 2.1）
50 100 0 0 0
C
B
X
B
x
1
x
2
x
3
x
4
x
5
θ
i
0 x
3
300 1 1 1 0 0 300
0 x
4
400 2 1 0 1 0 400
0 x
5
250 0 (1) 0 0 1 250
-z 0 50 100* 0 0 0
0 x
3
50 (1) 0 1 0 -1 50
0 x
4
150 2 0 0 1 -1 75
100 x
2
250 0 1 0 0 1
-z - 25 00 0 50* 0 0 0 - 10 0
50 x
1
50 1 0 1 0 -1
0 x
4
50 0 0 -2 1 1
100 x
2
250 0 1 0 0 1
-z - 27 50 0 0 0 - 50 0 - 50
47
2,2 对偶单纯形法
? 对偶单纯形法在什么情况下使用,
应用前提：有一个基，其对应的基本解满足
① 单纯形表的检验数行全部非正（对偶可
行）；
② 变量取值可有负数（非可行解）。
**注：通过矩阵行变换运算，使所有相应变
量取值均为非负数即得到最优单纯性表。
2、线性规划问题的进一步研究（ 2.2）
48
2、线性规划问题的进一步研究（ 2.2）
? 对偶单纯形法求解线性规划问题过程：
1、建立初始对偶单纯形表，对应一个基本解，所有
检验数均非正，转 2；
2、若 b’≥ 0,则得到最优解，停止；否则，若有 bk <
0 则选 k 行的基变量为出基变量，转 3；
3、若所有 akj’≥ 0 ( j = 1,2,…,n ),则原问题无可行解，
停止；否则，若有 akj’< 0 则选
? = min {?j’/ akj’┃ akj’< 0 } = ?r’/ akr’那么 r 为
进基变量，转 4；
4、以 akr’为转轴元，作矩阵行变换使其变为 1，该列
其他元变为 0，转 2。
49
例,求解线性规划问题：
Min f = 2 x1 + 3 x2 + 4 x3
S.t,x1 + 2x2 + x3 ≥ 3
2x1 - x2 + x3 ≥ 4
x1,x2,x3 ≥ 0
标准化：
Max Z = - 2x1 - 3x2 - 4x3
S.t,- x1 - 2x2 - x3 + x4 = - 3
- 2x1 + x2 - 3x3 + x5 = - 4
x1,x2,x3,x4,x5 ≥ 0
2、线性规划问题的进一步研究（ 2.2）
50
? 表格对偶单纯形法
**习题,p 100 习题 2 2-2,2-3
C
I
-2 -3 -4 0 0
C
B
X
B
b X
1
X
2
X
3
X
4
X
5
0 X
4
-3 -1 -2 -1 1 0
0 X
5
-4 [- 2] 1 -3 0 1
σ
j
-2 -3 -4 0 0
0 X
4
-1 0 [- 5/2 ] 1/2 1 -1/ 2
-2 X
1
2 1 -1/ 2 3/2 0 -1/ 2
σ
j
0 -4 -1 0 -1
-3 X
2
2/5 0 1 -1/ 5 -2/ 5 1/5
-2 X
1
11/
5
1 0 7/5 -1/ 5 -2/ 5
σ
j
0 0 -9/ 5 -8/ 5 -1/ 5
2、线性规划问题的进一步研究（ 2.2）
51
2.3 灵敏度分析
? 进一步理解最优单纯形表中各元素的含义
考虑问题 Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn ≤ b1
a21 x1 + a22 x2 + … + a2n xn ≤ b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ bm
x1, x2, …, xn ≥ 0
引入 m 个松弛变量后，通过计算得到最优单纯形表。应
-1 -1能够找到最优基 B的逆矩阵 B,以及 B N，检验数等。
2、线性规划问题的进一步研究（ 2.3）
52
2、线性规划问题的进一步研究（ 2.3）
c
1 ?
c
n
0 ? 0
C
B
X
B x
1 ?
x
n
x
n + 1 ?
x
n + m
θ
i
0 x
n + 1
b
1
a
11 ?
a
1n
1 ? 0 θ
1
0 x
n + 2
b
2
a
21 ?
a
2n
0 ? 0 θ
2
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
0 x
n + m
b
m
a
m1 ?
a
mn
0 ? 1 θ
m
-z f c
1
? c
n
0 ? 0
c
1 ?
c
n
c
n + 1 ?
c
n +m
C
B
X
B x
1 ?
x
n
x
n +1 ?
x
n +m
θ
i
c
i 1
x
i 1
b
1
a
11 ?
a
1n
a
1 n +1 ?
a
1 n +m θ 1
c
i 2
x
i 2
b
2
a
21 ?
a
2n
a
2 n +1 ?
a
2 n +m θ 2
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
C
i m
x
i m
b
m
a
m1 ?
a
mn
a
m n +1 ?
a
m n + m θ m
-z f σ
1
? σ
n
σ
n +1
? σ
n +m
最优单纯形表
B-1
(BT)-1cB
I
O
53
? 价值系数 C发生变化：
m
考虑检验数 ?j = cj -∑ cri arij j = 1,2,……,ni = 1
1、若 ck 是非基变量的系数：
设 ck 变化为 ck + ?ck ?k’= ck + ?ck -∑ cri arik = ?k+ ?ck
只要 ?k’≤ 0,即 ?ck ≤ - ?k, 则最优解不变；否则，将最优
单纯形表中的检验数 ?k 用 ?k’取代，继续单纯形法的表格计
算 。
例, Max Z = - 2x1 - 3x2 - 4x3
S.t,- x1 - 2x2 - x3 + x4 = - 3
- 2x1 + x2 - 3x3 + x5 = - 4
x1,x2,x3,x4,x5 ≥ 0
2、线性规划问题的进一步研究（ 2.3）
54
例：最优单纯形表
从表中看到 σ 3 = C3 +Δ C3 - （ C2 * a13 + C1* a23 ）
可得到 Δ C3 ≤ 9/5 时，原最优解不变。
2、线性规划问题的进一步研究（ 2.3）
C I -2 -3 -4 0 0
C B X B b X 1 X 2 X 3 X 4 X 5
-3 X 2 2/ 5 0 1 - 1/ 5 - 2/ 5 1/ 5
-2 X 1 11/ 5 1 0 7/ 5 - 1/ 5 - 2/ 5
σ j 0 0 - 9/ 5 - 8/ 5 - 1/ 5
C I -2 -3 -4 + Δ c
3
0 0
C B X B b X 1 X 2 X 3 X 4 X 5
-3 X 2 2/ 5 0 1 - 1/ 5 - 2/ 5 1/ 5
-2 X 1 11/5 1 0 7/ 5 - 1/ 5 - 2/ 5
σ j 0 0 - 9/ 5 + Δ c 3 - 8/ 5 - 1/ 5
55
2、若 cs 是基变量的系数,设 cs 变化为 cs + ?cs,那么
?j’= cj -∑ cri arij - ( cs + ?cs ) asj = ?j - ?cs asj,对所有非基变量
i ≠ s
只要对所有非基变量 ?j’≤ 0,即 ?j ≤ ?cs asj, 则最优
解不变；否则，将最优单纯形表中的检验数 ?j 用 ?j’取代，
继续单纯形法的表格计算 。
Max{?j / asj ?asj > 0 } ≤ ?cs ≤ Min{?j / asj ?asj < 0 }
例, Max Z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5
S.t,x1 + 2x2+ x3 = 8
4x1 + x4 =16
4x2 +x5 = 12
x1,x2,x3,x4,x5 ≥ 0
2、线性规划问题的进一步研究（ 2.3）
56
例、下表为最优单纯形表，考虑基变量系数 c2 发生变化
从表中看到 σ j = Cj - （ C1 * a1j + C5 * a5j + （ C2 +Δ C2 ） * a2j ） j = 3,4
可得到 -3 ≤ Δ C2 ≤ 1 时，原最优解不变。
C
i
2 3 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2 X
1
4 1 0 0 1/ 4 0
0 X
5
4 0 0 -2 1/ 2 1
3 X
2
2 0 1 1/ 2 - 1 / 8 0
σ
j 0 0 - 1.5 - 1 / 8 0
C
i
2 3+ Δ C 2 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2 X
1
4 1 0 0 1/ 4 0
0 X
5
4 0 0 -2 1/ 2 1
3+ Δ C
2 X 2 2 0 1 1/ 2 - 1 / 8 0
σ
j 0 0 - 1, 5 - Δ C 2 /2 - 1 / 8 + Δ C 2 /8 0
2、线性规划问题的进一步研究（ 2.3）
57
? 右端项 b 发生变化
设分量 br 变化为 br + ?br,根据第 1章的讨论，最优解
的基变量 xB = B-1b，那么只要保持 B-1(b + ?b) ≥ 0,则最优
基不变，即基变量保持，只有值的变化；否则，需要利用对
偶单纯形法继续计算。
对于问题 (LP) Max z = cT x
s.t,Ax ≤ b
x ≥ 0
最优单纯形表中含有
B-1 = （ aij ） i = 1,…,m ; j = n+1,…,n+m
那么，新的 xi = (B-1b)i + ?br air i = 1,…,m 。由此可得，最优
基不变的条件是
Max{-bi / air ?air > 0 } ≤ ?br ≤ Min{-bi / air ?air < 0 }
2、线性规划问题的进一步研究（ 2.3）
58
例、上例最优单纯形表如下
? 0 0.25 0 ?
这里 B-1 = ? -2 0.5 1 ? 各列分别对应 b1,b2,b3 的单一
?0.5 -0.125 0 ?
变化。因此，设 b1 增加 4，则 x1,x5,x2 分别变为：
4 + 0*4 = 4,4 + (-2)*4 = - 4 < 0,2 + 0.5*4 = 4
用对偶单纯形法进一步求解，可得：
x* = ( 4,3,2,0,0 )T f* = 17
2、线性规划问题的进一步研究（ 2.3）
C
i
2 3 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2 X
1
4 1 0 0 1/ 4 0
0 X
5
4 0 0 -2 1/ 2 1
3 X
2
2 0 1 1/ 2 - 1 / 8 0
σ
j 0 0 - 1.5 - 1 / 8 0
59
? 增加一个变量
增加变量 xn+1 则有相应的 pn+1, cn+1 。那么，计算出
B-1pn+1 ?n+1 = cn+1 -∑ cri ari n+1
填入最优单纯形表，若 ?n+1 ≤ 0 则最优解不变；否则，
进一步用单纯形法求解。
例、前例增加 x6,p6 = ( 2,6,3 )T, c6 = 5 。计算得到
2、线性规划问题的进一步研究（ 2.3）
C
i
2 3 0 0 0 5
C
B
X
B
b X
1
X
2
X
3
X
4
X
5
X
6
2 X
1
4 1 0 0 1/4 0 1.5
0 X
5
4 0 0 -2 1/2 1 [2]
3 X
2
2 0 1 1/2 -1/8 0 0.2 5
σ
j
0 0 -1.5 -1/8 0 1.2 5
用单纯形法进一步求解，可得,x* = ( 1,1.5,0,0,0,2 )T f* = 16.5
60
? 增加一个约束
增加约束一个之后，应把最优解带入新的约束，若满足
则最优解不变，否则填入最优单纯形表作为新的一行，引入
1个新的非负变量（原约束若是小于等于形式可引入非负松
弛变量，否则引入非负人工变量），并通过矩阵行变换把对
应基变量的元素变为 0，进一步用单纯形法或对偶单纯形法
求解。
例、前例增加 3x1+ 2x2≤15，原最优解不满足这个约束。于是
2、线性规划问题的进一步研究（ 2.3）
C
i
2 3 0 0 0 5
C
B
X
B
b X
1
X
2
X
3
X
4
X
5
X
6
2 X
1
4 1 0 0 1/4 0 0
0 X
5
4 0 0 -2 1/2 1 0
3 X
2
2 0 1 1/2 -1/8 0 0
0 X
6
-1 0 0 -1 -1/ 2 0 1
σ
j
0 0 -1.5 -1/8 0 0
61
? A中元素发生变化 （只讨论 N 中某一列变化情况）
与增加变量 xn+1 的情况类似，假设 pj 变化 。那么，重新
计算出 B-1pj ?j = cj -∑ cri ari j
填入最优单纯形表，若 ?j ≤ 0 则最优解不变；否则，进
一步用单纯形法求解。
2、线性规划问题的进一步研究（ 2.3）
改变生产工艺,P
1
= ( 2, 5, 2 )
T
,C
1
= 4,
C
i
4 3 0 0 0
C
B
X
B
b X
1
X
2
X
3
X
4
X
5 θ
2 X
1
4 1,25 0 0 1/4 0
0 X
5
4 0,5 0 -2 1/2 1
3 X
2
2 0,375 1 1/2 -1/ 8 0
σ
j
0,375 0 -1,5 -1/ 8 0
用初等行变换把 X
1 对应的列向量变换为
( 1, 0, 0 )
T
,……
可得最优解,x* = ( 3.2,0.8,0,0,2.4 )T f* = 15.2
62
2、线性规划问题的进一步研究（ 2.3）
2,3 灵敏度分析 (内容，为重点 )
2.3.1 Ci 发生变化
2.3.2 Bj发生变化
2.3.3 增加一个变量
2.3.4 增加一个约束
2.3.5 A中元素发生变化
**习题,p 100 习题 2 2-4
返回目录
63
3,1 运输问题模型与性质
? 运输模型
例,某公司从两个产地 A1,A2将物品运往三个销地
B1,B2,B3，各产地的产量、各销地的销量和各
产地运往个销地每件物品的运费如下表所示，问：
应如何调运可使总运输费用最小？
B
1
B
2
B
3 产量
A
1
6 4 6 200
A
2
6 5 5 300
销量 150 150 200
3、运 输 问 题（ 3.1）
64
解,产销平衡问题,总产量 = 总销量
设 xij 为从产地 Ai运往销地 Bj的运输量，得到下列运输量表：
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
s.t,x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
xij ≥ 0 ( i = 1, 2； j = 1,2,3）
3、运 输 问 题（ 3.1） B
1 B 2 B 3 产量
A 1 x 11 x 12 x 13 200
A 2 x 21 x 22 x 23 300
销量 150 150 200
65
? 系数矩阵
? 1 1 1 0 0 0 ?
? 0 0 0 1 1 1 ?
? 1 0 0 1 0 0 ?
? 0 1 0 0 1 0 ?
? 0 0 1 0 0 1 ?
特点：
1、共有 m+n行，分别表示产地和销地； mn列分别表示各变量；
2、每列只有两个 1，其余为 0，分别表示只有一个产地和一个
销地被使用；
3、运 输 问 题（ 3.1）
66
? 设 xij 为从产地 Ai运往销地 Bj的运输量，得到下列一般运输
量问题的模型：
m n
Min f = ? ? cij xiji=1 j=i
n
s.t,? xij = si i = 1,2,…,mj=1
m
? xij = dj j = 1,2,…,ni=1
xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n)
?一般运输模型,产销平衡
A1,A2,…, Am 表示某物资的 m个产地； B1,B2,…, Bn
表示某物质的 n个销地； si 表示产地 Ai的产量； dj 表示销地 Bj
的销量； cij 表示把物资为从产地 Ai运往销地 Bj的单位运价。
3、运 输 问 题（ 3.1续）
67
3、运 输 问 题（ 3.1续）
? 变化：
1）有时目标函数求最大，如求利润最大或
营业额最大等；
2）当某些运输线路上的能力有限制时，模
型中可直接加入（等式或不等式）约束；
3）产销不平衡时，可加入虚设的产地（产
大于销时）或销地（销大于产时）。
68
3、运 输 问 题（ 3.1续）
? 求解思路 是
基本可行解 最优否 结束
否
换基
? 运输问题基变量的特点
* 运输问题的基变量共有 m + n -1 个,A的秩为 m + n -1。
* 运输问题的 m + n -1 个变量构成基变量的充分必要条件是
不含闭回路。
要弄清下列概念,闭回路、闭回路的顶点。
69
3,2 运输问题的表上作业法 ——本章重点
1、初始基本可行解的确定：
（ 1）西北角法,从西北角（左上角）格开始，在格内的右下
角标上 允许取得 的最大数。然后按行（列）标下一格的数。
若某行（列）的产量（销量）已满足，则把该行（列）的其
他格划去。如此进行下去，直至得到一个基本可行解。
（ 2）最小元素法,从运价最小的格开始，在格内的右下角标
上 允许取得 的最大数。然后按运价从小到大顺序填数。若某
行（列）的产量（销量）已满足，则把该行（列）的其他格
划去。如此进行下去，直至得到一个基本可行解。
注,应用西北角法和最小元素法，每次填完数，都只划去一行
或一列，只有最后一个元例外（同时划去一行和一列）。当
填上一个数后行、列同时饱和时，也应任意划去一行（列）
在保留的列（行）任意没被划去的格内标一个 0。
3、运 输 问 题（ 3.2）
70
*
例：某食品公司下属的 A
1
,A
2
,A
3
, 3 个厂生产方便食品，
要运输到 B
1
,B
2
,B
3
,B
4
, 4 个销售点，数据如下：
B
1
B
2
B
3
B
4 产量 a i
A
1
3 11 3 10 7
A
2
1 9 2 8 4
A
3
7 4 10 5 9
销量 b
j
3 6 5 6 20 （产销平衡）
求最优运输方案。
3、运 输 问 题（ 3.2）
1,确定初始基本可行解,（ 1 ）西北角法
B
1
B
2
B
3
B
4 产量 a i
A
1
3
3
11
4
3 10 7
A
2
1 9
2
2
2
8 4
A
3
7 4 10
3
5
6
9
销量 b
j
3 6 5 6 20
71
*
3、运 输 问 题（ 3.2）
（ 2 ）最小元素法
B
1
B
2
B
3
B
4
产量 a
i
A
1
3 11 3
4
10
3
7
A
2
1
3
9 2
1
8 4
A
3
7 4
6
10 5
3
9
销量 b
j
3 6 5 6 20
注：除最后一个元素 （相当于同时删去一行一列）外，每填一个
数都只删去一行或一列。若当前的行、列同时满足，可在当前的
行 （或列）的一个格子标 0,同时删去当前的列 （或行）。
72
2、最优性检验：
因为求最小，当所有检验数均大于等于 0时为最优解
（ 1）位势法求检验数：
? 位势,设对应基变量 xij 的 m + n - 1 个 ij,存在 ui,
vj 满足 ui + vj = cij, i = 1,…,m ; j = 1,…,n, 称这
些 ui,vj 为该基本可行解对应的位势。
由于有 m + n 个变量（ ui,vj ）,m + n - 1 个
方程（基变量个数），故有一个自由变量，位势不
唯一。
? 利用位势求检验数：
?ij = cij - ui - vj i = 1,…,m ; j = 1,…,n
3、运 输 问 题（ 3.2）
73
? 前例，位势法求检验数：
step 1 从任意基变量对应的 cij 开始，任取 ui 或 vj,然后利用公
式 cij = ui + vj 依次找出 m + n 个 ui,vj ； 从 c14 = 10 开始
step 2 计算非基变量的检验数 ?ij = cij - ui - vj ； 填入圆圈内
3、运 输 问 题（ 3.2）
v
j
-3 4 -2 5
u
i
B
1
B
2
B
3
B
4 产量 a i
5 A
1
3
1
11
2
3
4
10
3
7
4 A
2
1
3
9
1
2
*1
8
-1
4
0 A
3
7
10
4
6
10
12
5
3
9
销量 b
j
3 6 5 6 20
74
3、主元变换：
（ 1）选负检验数中最小者 ?rk，那么 xrk 为主元，作
为进基变量； （上页图中 x24 ）
（ 2）以为 xrk 起点找一条闭回路，除 xrk 外其余顶点
必须为基变量格； （上页图中 蓝色回路）
（ 3）为闭回路的每一个顶点标号,xrk 为 1，沿一个
方向依次给各顶点标号；
（ 4）求 ?=min{xij?xij对应闭回路上的偶数标号格 }=
xpq那么确定 xpq为出基变量,?为调整量；
（ 5）对闭回路的各奇标号顶点 xij + ?，对各偶标号顶
点 xij - ?，特别 xpq - ? = 0，变为非基变量；
3、运 输 问 题（ 3.2）
重复 2,3步，直到所有检验数均非负，得到最优解。
75
主元变换,由前面得到 ? = 1，于是
3、运 输 问 题（ 3.2）
v
j
-2 4 -2 5
u
i
B
1
B
2
B
3
B
4 产量 a i
5 A
1
3
0
11
2
3
（ 4+1 ） 5
10
（ 3 -1 ） 2
7
3 A
2
1
3
9
2
2
( 1-1 ) 1
8
（ 0+1 ） 1
4
0 A
3
7
9
4
6
10
12
5
3
9
销量 b
j
3 6 5 6 20
?ij ≥ 0，得到最优解 x13 = 5,x14 = 2,x21 = 3,
x24 = 1,x32 = 6,x34 = 3,其余 xij = 0 ;
最优费用,f* = 3*5+10*2+1*3+8*1+4*6+5*3 = 85
**习题,p 123 习题 3 3-1,3-2
76
3,3 产销不平衡的运输问题
1、产量大于销量 例,某公司从两个产地 A1,A2将物品
运往三个销地 B1,B2,B3，各产地的产量、各销地的销量
和各产地运往个销地每件物品的运费如下表所示，问：应
如何调运可使总运输费用最小？
解,增加一个虚设的销地运输费用为 0
B 1 B 2 B 3 产量
A 1 6 4 6 3 00
A 2 6 5 5 300
销量 150 150 200
B 1 B 2 B 3 B 4 产量
A 1 6 4 6 0 3 00
A 2 6 5 5 0 300
销量 150 150 200 100
3、运 输 问 题（ 3.3）
77
2、销量大于产量
例,某公司从两个产地 A1,A2将物品运往三个销地 B1,B2、
B3，各产地的产量、各销地的销量和各产地运往个销地每件
物品的运费如下表所示，问：应如何调运可使总运输费用最
小？
解,增加一个虚设的产地运输费用为 0
3、运 输 问 题（ 3.3）
B 1 B 2 B 3 产量
A 1 6 4 6 200
A 2 6 5 5 300
销量 250 200 200
B 1 B 2 B 3 产量
A 1 6 4 6 2 00
A 2 6 5 5 300
A 3 0 0 0 150
销量 250 200 200
78
? 下面给出一些例题，可作为建模的练习：
例,石家庄北方研究院有一、二、三，三个区。每年分别需
要用煤 3000,1000,2000吨，由河北临城、山西盂县两处
煤矿负责供应，价格、质量相同。供应能力分别为 1500、
4000吨，运价如下表。由于需大于供，经院研究决定一区
供应量可减少 0--200吨，二区必须满足需求量，三区供应
量不少于 1700吨，试求总费用为最低的调运方案。
一区 二区 三区 产量
山西盂县 1,6 5 1,7 0 1,7 5 4000
河北临城 1,6 0 1,6 5 1,7 0 1500
需要量 3000 1000 2000
3、运 输 问 题（例题）
79
解：
根据题意，作出产销平衡与运价表：
取 M 代表一个很大的正数，其作用是强迫相应
的 x31,x33,x34取值为 0。
3、运 输 问 题（例题） 一区 一区 二区 三区 三区 产量
山西盂县 1,6 5 1,6 5 1,70 1,75 1,75 4000
河北临城 1,6 0 1,6 0 1,6 5 1,70 1,70 1500
假想生产点 M 0 M M 0 500
需要量 2800 200 1000 1700 300
80
例,设有 A,B,C三个化肥厂供应 1,2,3,4四个
地区的农用化肥。假设效果相同，有关数据如下
表。试求总费用为最低的化肥调拨方案。
1 2 3 4 产量
A 1 6 1 3 22 17 50
B 14 1 3 19 15 60
C 19 20 23 --- 50
最低需要量 30 70 0 10
最高需要量 50 70 30 不限
3、运 输 问 题（例题）
81
解,根据题意，作出产销平衡与运价表：
最低要求必须满足，因此把相应的虚设产地运费取为 M,
而最高要求与最低要求的差允许按需要安排，因此把相应的
虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适
当取的数据，根据产销平衡要求确定 D的产量为 50。
3、运 输 问 题（例题）
1 ’ 1, 2 3 4 ’ 4, 产量
A 1 6 1 6 1 3 22 17 17 50
B 14 14 1 3 19 15 15 60
C 19 19 20 23 M M 50
D M 0 M 0 M 0 50
销量 30 20 70 30 10 50
82
例,某厂按合同规定须于当年每个季度末分别提供 10,15、
25,20台同一规格的柴油机。已知该厂各季度的生产能力
及生产每台柴油机的成本如下表。如果生产出来的柴油机
当季不交货，每台每积压一个季度需储存、维护等费用
0.15万元。试求在完成合同的情况下，使该厂全年生产总
费用为最小的决策方案。
生产能力 （台） 单位成本 （万元）
一季度 25 1 0,8
二季度 35 1 1,1
三季度 30 1 1,0
四季度 10 1 1,3
3、运 输 问 题（例题）
83
解,设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那末应满足：
交货,x11 = 10 生产,x11 + x12 + x13 + x14 ≤ 25
x12 + x22 = 15 x22 + x23 + x24 ≤ 35
x13 + x23 + x33 = 25 x33 + x34 ≤ 30
x14 + x24 + x34 + x44 = 20 x44 ≤ 10
把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j
季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维
护等费用看作运费。可构造下列产销平衡问题：
目标函数,Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22
+11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44
3、运 输 问 题（例题） 第一季度 第二季度 第三季度 第四季度 D 产量
第一季度 10.80 1 0.95 11,1 0 11.2 0 25
第二季度 M 11.10 1 1.25 11.40 0 35
第三季度 M M 11.00 11.15 0 30
第四季度 M M M 11.30 0 10
销量 10 15 25 20 30
84
例,光明仪器厂生产电脑绣花机是以产定销的。已知 1至 6月份各月的
生产能力、合同销量和单台电脑绣花机平均生产费用见下表
已知上年末库存 103台绣花机，如果当月生产出来的机器当月
不交货，则需要运到分厂库房，每台增加运输成本 0.1万元,每台机
器每月的平均仓储费、维护费为 0.2万元。在 7--8月份销售淡季，全
厂停产 1个月，因此在 6月份完成销售合同后还要留出库存 80台。加
班生产机器每台增加成本 1万元。问应如何安排 1--6月份的生产，可
使总的生产费用（包括运输、仓储、维护）最少？
正常生产能力 （台） 加班生产能力 （台） 销量 （台） 单台费用 （万元）
1 月份 60 10 104 15
2 月份 50 10 75 14
3 月份 90 20 1 1 5 1 3, 5
4 月份 100 40 160 13
5 月份 100 40 103 13
6 月份 80 40 70 1 3, 5
3、运 输 问 题（例题）
85
解,这个生产存储问题可化为运输问题来做。考虑：
各月生产与交货分别视为产地和销地
1） 1--6月份合计生产能力（包括上年末储存量）
为 743台，销量为 707台。设一假想销地销量为 36；
2）上年末库存 103台，只有仓储费和运输费，把
它列为的 0行；
3） 6月份的需求除 70台销量外，还要 80台库存，
其需求应为 70+80=150台；
4） 1--6表示 1--6月份正常生产情况,1’--6’表示
1--6月份加班生产情况。
续下页 产销平衡与运价表：
3、运 输 问 题（例题）
86
**习题,p 124 习题 3 3-3,3-4
1 月 2 月 3 月 4 月 5 月 6 月 虚销地 正常产量 加班产量
0 0.3 0.5 0.7 0.9 1.1 1.3 0 103
1 15 15, 3 15, 5 15, 7 15, 9 16, 1 0 60
1 ’ 16 16, 3 16, 5 16, 7 6.9 17, 1 0 10
2 M 14 14, 3 14, 5 14, 7 14, 9 0 50
2 ’ M 15 15, 3 15, 5 15, 7 15, 9 0 10
3 M M 13, 5 13, 8 14, 0 14, 2 0 90
3 ’ M M 14, 5 14, 8 15, 0 15, 2 0 20
4 M M M 13, 0 13, 3 13, 5 0 100
4 ’ M M M 14, 0 14, 3 14, 5 0 40
5 M M M M 13, 0 13, 3 0 100
5 ’ M M M M 14, 0 14, 3 0 40
6 M M M M M 13, 5 0 80
6 ’ M M M M M 14, 5 0 40
销量 104 75 1 15 160 103 150 36
3、运 输 问 题（例题）
返回目录
87
4,1 动态规划概念与模型
? 多阶段决策过程特点
要点：阶段，状态，决策，状态转移方程,k-后部子
过程
4、动 态 规 划 (4.1)
88
? 动态规划模型
nopt R( u
1,…,u n ) = ? rk ( xk,uk ) k=1
s.t,xk+1 = Tk ( xk,uk )
xk ?Xk ； uk ? Uk k = 1,…,n
?,表示对 n阶段效应进行综合（常用 ? 或 ? ）；
opt,最优化（ Max 或 Min）
R( u1,…,u n )：目标函数（最优值函数）
xk+1 = Tk ( xk,uk ),状态转移方程
Xk,状态可能集合
Uk：决策允许集合
4、动 态 规 划 (4.1)
89
? 建模过程
① 确定阶段与阶段变量；
② 明确状态变量与状态可能集合；
③ 明确决策变量与决策允许集合；
④ 明确状态转移方程；
⑤ 确定阶段效应和目标。
4、动 态 规 划 (4.1)
90
4,2 动态规划求解
? 求解动态规划模型：
从起始状态 x1 开始，找最优策略、最优路线和
最优目标值。
? 最优性原理
最优策略具有的基本性质是：无论初始状态和
初始决策如何，对于前面决策所确定的某一状态而
言，余下的决策序列必构成最优策略。
最优策略的任何一子策略也是相应初始状态的
最优策略；每个最优策略只能由最优子策略构成。
4、动 态 规 划 (4.2)
91
? 贝尔曼函数：（ k - 子过程的最优目标函数 )
nf
k(xk) = opt ? ri ( xi,ui ) k=1,…,ni=k
? 动态规划求解问题的一般过程：
① 逆序地求出条件最优目标函数值集合和条件最优决
策集合：
fn+1(xn+1) = 0 (边界条件 )
fk(xk) = opt {rk ( xk,uk ) + fk+1(xk+1) }u
k = n,…,1
4、动 态 规 划 (4.2)
92
② 顺序地求最优决策序列：
初始状态唯一,R* = f1(x1),u1* (x1)=u1’(x1)
若不唯一,R* = opt{f1(x1) ?x1?X1} = f1(x1*)，
u1* (x1*)=u1’(x1*)
xk+1 = Tk ( xk,uk )
uk+1* (xk+1*) = uk+1’(xk+1*) k=1,…,n
最优策略,{u1*(x1*),u2*(x2*),…,u n* (xn*)}
最优路线,{x1*,x2*,…,xn*,xn+1*)
4、动 态 规 划 (4.2)
93
1、动态规划的四大要素、一个方程 —— 重点
① 状态变量及其可能集合 xk ?Xk
② 决策变量及其允许集合 uk ? Uk
③ 状态转移方程 xk+1 = Tk ( xk,uk )
④ 阶段效应 rk ( xk,uk )
⑤ 动态规划基本方程
fn+1(xn+1) = 0 (边界条件 )
fk(xk) = opt {rk ( xk,uk ) + fk+1(xk+1) }u
k = n,…,1
4、动 态 规 划 (4.2)
94
4,3 动态规划应用举例
例：一个线路网络图，从 A到 E要修建一条石油管道，必须 在
B,C,D处设立加压站。各边上的数为长度，现需要找一
条路使总长度最短。
4、动 态 规 划 (4.3)
95
解,可分成 4个阶段,A到 B,B到 C,C到 D,D到 E ；
每个阶段 k 的起点称为状态 S k ；
从 k 阶段的起点出发可以做一选择，即决定到下一阶
段的哪个节点，称为决策 X k ；
可见,S k+1 是由 S k 和 X k 所决定的。
那麽，从 A出发经过 4个阶段,A到 B,B到 C,C到 D,D
到 E，逐次作出决策，构成从 A到 E 的一条路线，记为 u 。
即，
u = S1 X1 S2 X2 S3 X3 S4 X4 S5 其中 S1 = A, S5 = E
记 d 为两个相邻节点之间的长度，如 d（ A,B 3） = 3 。
① 记 f k（ S k）为从 S k 到 E 的最短长度，称为从 S k 到 E
的距离。
那么,f 1（ A）是从 A到 E 的最短距离，即最优策略的值。
4、动 态 规 划 (4.3续 )
96
② 最短路问题的特点：如果从 A 到 E 的最优策
略经过某节点，那么这个策略的从该节点到 E
的一段，必定是该节点到 E的所有线路中 S k 最
短的一条，即这一段的长度为 f k（ S k）。
（ 1）逆序法：从 E到 A
（ 2）顺序法：对节点 S k,从 A到 S k 所有
线路中，最短的一条的长度记为 φ k（ S k），
例如 φ 1（ A） = 0,称为问题的边界条件。
4、动 态 规 划 (4.3续 )
动态规划文本
97
学习方法建议：
第一步 先看问题，充分理解问题的条件、情
况及求解目标；
第二步 结合前面讲到的理论和解题过程，考
虑如何着手进行求解该问题的工作。分析针
对该动态规划问题的“四大要素、一个方
程” ——这一步在开始时，会感到困难，但
是一定要下决心去思考，在思考过程中深入
理解前文讲到的概念和理论；
4、动 态 规 划 (4.3续 )
98
第三步 动手把求解思路整理出来，或者说，
把该问题作为习题独立的来做；
第四步 把自己的求解放到一边，看书中的求
解方法，要充分理解教材中的论述；
第五步 对照自己的求解，分析成败。
**习题,p175--177 4 -1,4 -2,4 -3,4 -6；
**练习,4 -4,4 -5,4 -7
4、动 态 规 划 (4.3续 )
返回目录
99
5,1 图的基本概念 —— 本节主要是概念
? 图 G（ V,E）：
V是顶点集合（ vi,i=1…6 ）
E是边的集合（ ej,j=1…9 ）
顶点数 p (G) = 6
边数 q (G) = 9
对于边 e3 =[ v1,v4 ],v1,v4是
e3的端点 e3 是 v1,v4的关联边
5、图 与 网 络 分 析（ 5.1）
?图的其他概念,
相邻点，相邻边，
环，多重边（平行边），
多重图，简单图
100
端点的次 d(v),点 v 作为边端点的次数；
奇点,d(v)=奇数； 偶点,d(v)=偶数；
悬挂点,d(v)=1； 悬挂边,与悬挂点连接的边，
孤立点,d(v)=0； 空图, E = ?，无边图 。
定理一,所有顶点次数之和等于所有边数
的 2倍。
定理二,在任一图中，奇点的个数必为偶
数。
5、图 与 网 络 分 析（ 5.1续）
101
? 图的连通性：
链,由两两相邻的点及其相关联的边构成的点边序列；如：
v0,e1,v1,e2,v2,e3,v3,…,vn-1,en,vn ；
v0,vn分别为链的 起点 和 终点
简单链,链中所含的边均不相同；
初等链,链中所含的点均不相同，也称 通路 ；
回路,若 v0 ≠ vn 分称该链为开链，否则称为 闭链 或 回路 ；
圈,出起点和终点外链中所含的点均不相同的闭链；
连通图, 图中任意两点之间均至少有一条通路，否则称作
不连通图。
5、图 与 网 络 分 析（ 5.1续）
102
? 子图 设 G1 = [ V1,E1 ],G2 = [ V2,E2 ]
子图定义,如果 V2 ? V1,E2 ? E1 称 G2 是 G1 的子图；
真子图,如果 V2 ? V1,E2 ? E1 称 G2 是 G1 的真子图；
部分图,如果 V2 = V1,E2 ? E1 称 G2 是 G1 的部分图；
导出子图,如果 V2 ? V1,E2 = {[ vi,vj ] ∣ vi,vj ? V2 }，称 G2
是 G1 中由 V2 导出 的导出子图。
5、图 与 网 络 分 析（ 5.1续）
103
? 有向图,关联边有方向
弧,有向图的边 a = ( u,v ),起点 u,终点 v；
路,若有从 u 到 v 不考虑方向的链，且各方向一致，
则称之为从 u 到 v 的 路；
初等路,各顶点都不相同的路；
初等回路,u = v 的初等路
连通图,若不考虑方向
是无向连通图
强连通图,任两点有路
5、图 与 网 络 分 析（ 5.1续）
104
? 树,无圈连通图；无圈图又称为树林，子连通图是树
定理,六种等价描述。 设：边数 q,顶点数 p,
1、无圈连通图；
2、边数 q = 顶点数 p - 1；
3、连通，且 q = p - 1；
4、无圈，但加一边则得到唯一的圈；
5、连通，但若去一边则图不连通；
6、每对顶点之间有且仅有一条链。
部分树,若一个图 G 的部分图 T 是树，则称 T 为部分树，
又称生成树
余树,G 中去掉 T 所有的边后得到的部分树称为 G 中 T 的
余树，余树不一定是树。
5、图 与 网 络 分 析（ 5.1续）
105
5、图 与 网 络 分 析（ 5.2）
5,2 网络最短路问题
网络,规定起点、中间点和终点的赋权图；
有向网络,网络中每个边都是有向边；
无向网络,网络中每个边都是无向边；
混合网络,网络中既有有向边，又有无向边；
网络最短路线问题,寻找网络中从起点 v1 到终
点 vn 的最短路线。
Min L(?) = ? lij ?为从 v1 到 vn 的通路；
lij??
其中,lij为从 vi 到 vj 的一步距离。
106
? 结合例题学习、掌握求最短路的狄克斯拉、海斯和
福德三个方法：
1、狄克斯拉方法：适用于满足所有权系数大于等
于 0（ lij≥0）的网络最短路问题，能求出起点 v1 到
所有其它点 vj 的最短距离；
2、海斯方法：基本思想是在最短路线上任意两点
间路线也是最短路线。利用 vi 到 vj 的一步距离求
出 vi 到 vj 的两步距离再求出 vi 到 vj 的四步距
离 …… 经有限次迭代可求出 vi 到 vj 的最短距离；
3、福德方法：适用于有负权系数，但无负回路的
有向或无向网络的最短路问题，能求出起点 v1 到所
有其它点 vj 的最短距离。
**习题,p218--219 习题 5 5-2
5、图 与 网 络 分 析（ 5.2续）
107
5,3 最短树问题（最小树问题）（ p198--201 ）
? 依据树的特点（即无圈和连通），按照最短的要求构造求最短
树的方法。
? 结合例题学习、掌握求最小树的破圈法和生长法两个方法：
1、破圈法
① 在网络图中寻找一个圈。若不存在圈，则已经得到最
短树或网络不存在最短树；
② 去掉该圈中权数最大的边；
反复重复 ① ② 两步，直到求出最短树。
2、生长法
从网络图中任意节点开始寻找与该节点关联的权数最小的
边，得到另一节点后，再从这个新节点开始寻找与该节点关联
的权数最小的另一边 …… 。注意寻找过程中，节点不得重复，
即在找最小权数边时不考虑已选过的边。反复进行，直到得到
最短树或证明网络不存在最短树。
**习题,p218--219 习题 5 5-1,5-3
5、图 与 网 络 分 析（ 5.3）
108
5,4 最大流问题（ p201--212）
? 网络最大流问题
* 在一定条件下，要求流过网络的物流、能量流或信息流等流量为最大的
问题。
* 规定,一个起点和一个终点；有向网络；各弧上有权表示允许的最大
流量；除起点和重点外，各节点流入量总和等于流出量总和。
? 最大流最小割定理（在理解割集和最小割集概念的基础上掌握此定理）
最大流最小割定理：流过网络的最大流量等于最小割集的容量。
? 结合例题学习、掌握求最大流的福德 —富克逊方法
在理解算法原理的基础上，掌握算法思想及过程。通过例题掌握此方法。
**习题,p219 习题 5 5-4
5、图 与 网 络 分 析（ 5.4）
109
5,5 最小费用 —— 最大流问题（ p212--218）
? 最小费用 ——最大流问题
本节讨论的问题是在 5.4节问题的基础上增加关于使费用最小的目标。
? 对偶法原理
先用 5.4节讨论的方法求出网络的最大流量，然后在原始的网络中用 5.2.4的福
德算法找出从起点 vs 到终点 vt 的最短路线 ——最短增广链，在该增广链上找出
最大调整量，并调整流量得到一个可行流，则此可行流的费用最小。如果此时
流量等于最大流量，那么它就是最小费用最大流；否则应继续调整。
? 结合例题学习、掌握求最小费用 ——最大流问题对偶法。
**习题,p 220 习题 5 5-5
5、图 与 网 络 分 析（ 5.5）
返回目录
110
6、排 队 论（ 6.1）
6,1 概述
?排队系统的特征,排队系统又称随机
服务系统
① 有请求服务的人或物； ② 有为顾
客服务的人或物； ③ 顾客到达时间与接
受服务时间是随机的 。
?结构：
排队的过程可表示为,排队系统
顾客到达 排队 服务机构服务 顾客离去
111
排队系统有三个组成部分
? 输入过程：
顾客总体数 （来源无限或有限）
顾客到来方式 （单个或成批）
顾客流的概率分布 （泊松流、定长、爱尔朗分布等）
? 服务规则：
损失制 （服务台满时顾客立即离去）
等待制 （先到先服务，后到先服务，随机服务，优先权）
混合制 （队长有限制，排队时间有限制）
? 服务机构：
服务台数量及布置形式 （单 /多服务台，串、并列或结合）
某一时刻接受服务的顾客数 （每服务台每次服务顾客数）
服务时间分布 （负指数、定长、爱尔朗分布等）
6、排 队 论（ 6.1续）
112
? 排队论研究的内容和目的 —— 提出排队论关
心的问题和需要计算的一些量
研究内容：
数量指标：队长、等待时间和逗留时间
的分布、忙期和闲期的分布、服务设备利用
率、顾客损失率等；
排队系统优化问题：系统最优设计问题
和动态控制问题。
研究目的,通过对排队系统中概率规律的研究，
使系统达到最优设计和最优控制，以最小费
用实现系统的最大效益。
6、排 队 论（ 6.1续）
113
6、排 队 论 （ 6.1续）
? 排队模型的分类及 排队系统的常用符号
肯道尔（ D.G.Kendall）分类,A / B / C / D / E
其中,A 顾客到达的分布；
B 服务时间的分布；
C 服务台数；
D 系统容量；
E 顾客源的个体数。
表示分布的符号,M----指数分布或泊松输入； D----
定长分布； Ek----k阶爱尔朗分布； GI----一般独立
随机分布； G----一般随机分布。
114
? 系统的运行指标 —— 提出一般常需要计算的一些量
最常用的量,单位时间顾客平均到达数 ?
单位时间平均服务顾客数 ?
（ 1）、系统中无顾客的概率 P0
（ 2）、系统中平均排队的顾客数 Lq
（ 3）、系统中的平均顾客数 Ls
（ 4）、系统中顾客平均的排队等待时间 Wq
（ 5）、系统中顾客的平均逗留时间 Ws
（ 6）、系统中恰好有 n 个顾客的概率 Pn
（ 7）,有效到达率 ?e
（ 8）、有效离去率 ? e
此外还有：忙、空的概率等 6 个量
6、排 队 论 （ 6.1续）
115
6.2 泊松输入 — 负指数服务的排队系统
? 对于泊松输入 - 负指数分布服务的排队系统
的一般决策过程：
① 根据已知条件绘制状态转移速度图
② 依据状态转移速度图写出各稳态概率之间
的关系
③ 求出 P0 及 Pn
④ 计算各项数量运行指标
⑤ 用系统运行指标构造目标函数，对系统进
行优化
6、排 队 论（ 6.2）
116
? 典型分布 —— 泊松分布及其性质，负指数分布
泊松分布 (平稳状态） ? > 0 为单位时间平均到
达的顾客数：
P { I = n } = ?n e-? / n! (n = 0,1,2,……)
负指数分布 ? 为平均服务率，即单位时间服
务的顾客数
P（服务时间 ≤ t ) = 1- e-? t t ≥0
? 系统状态概率分布及状态转移速度图 —— 基
本的概率分布推导
6、排 队 论（ 6.2）
117
? 系统的运行指标：
（ 1）、系统中顾客数的期望值 Ls
（ 2）、系统中排队等待顾客数的期望值 Lq
（ 3）、系统中顾客平均的排队等待时间 Wq
（ 4）、系统中顾客的平均逗留时间 Ws
（ 5）,有效到达率 ?e
6、排 队 论（ 6.2续）
118
6、排 队 论（ 6.2续）
（ 6）、系统中 Ls,Lq,Wq,Ws,?e 之间
的关系
Ls = ? n pn,Lq = ? ( n - c ) pn，
Ws = Ls / ?e,Wq = Lq / ?e，
Ws = Wq + 1 / ?,
?e = ? ?n pn = ? ? n pn,
Ls = Lq + ?e / ? 。
119
6、排 队 论 （ 6.3）
*在 6.1,6.2节的基础上，结合例题学习、掌握下列各系统有关问题的计算
6,3 M/M/1无限源系统（ p239--246 ）
? M/M/1/N系统,M/M/1等待制系统,M/M/l损失制系统，无限源模型特点
6,4 M/M/C无限源系统（ p246--253 ）
? M/M/C/N系统,M/M/C等待制系统,M/M/C损失制系统
6,5 客源有限的排队系统（ p253--258 ）
? M/M/1/m/m系统,M/M/C/m/m系统
6,6 排队系统应用举例（ p258--264 ）
? 本段的各例题要在充分理解的基础上学习，然后独立去完成课后练习作业。
6,7 本章小结（ p264 ）
? 学习本节内容，要认真体会第 6章的重点和难点。
? 小结也需要学习，自己应仿照此在总复习中作各章的小结。
**习题,p 265--266 习题 6 6-1,6-2,6-3,6-4,6-5,6-6,6-7,6-8
返回目录
120
教 学 日 历
周次 学习内容 课内学时 自学学时 作业 （ 教材 ）
1 绪论 2
1 线性规划
1 1,1 线性规划的概念 2 4 习题 1 1-1,1-2
1,1,1线性规划问题的导出
1,1,2线性胡划问题的概念和模型
1,1,3线性规划问题的标准型
1,1,4线性规划问题的标准化
2 1,2线性规划问题解的概念及性质 4 8 习题 1 1-3,1-4
1,2,1解的概念
1,2,2图解法 (解的几何表示 )
1,2,3基本可行解的几何意义
1,2,4线性规划求解思路 (单纯形法思想 )
1,2,5线性规划解的性质的证明
3 1,3单纯形法 6 12 习题 1 1-5,1-6
1,3,1单纯形法引例
1,3,2单纯形法的一般描述
121
周次 学习内容 课内学时 自学学时 作业（教材）
1,3,3表格单纯形法
1,3,4一般线性规划问题的处理
1,3,5单纯形法的矩阵描述
1,3,6单纯形迭代过程中的几点注意事项
4 1,4线性规划应用 6 12 习题 1 1-7,1-8
1,4,1线性规划建模 1-9
1,4,2生产计划问题
1,4,3合理下料问题
1,4,4合理配料问题
1,4,5运输问题
1,4,6最大流量问题
2 线性规划问题的进一步研究
5 2,1对偶原理 2 4 习题 2 2-1
2,1,1对偶线性规划问题的导出
2,1,2对偶问题的定义
2,1,3对偶定理
教 学 日 历（续）
122
周次 学习内容 课内学时 自学学时 作业（教材）
2,1,4对偶最优解的经济含义 ——影子价格
2,1,5由最优单纯形表求对偶问题最优解
5 2,2对偶单纯形法 2 4 习题 2 2-2,2-3
6 2,3灵敏度分析 4 8 习题 2 2-4
2,3,1价值系数 C发生改变
2,3,2右端常数 b发生改变
2,3,3增加一个变量
2,3,4增加一个约束
2,3,5 A中的元素发生改变
3 运输问题
7 3,1运输问题模型与性质 2 4 习题 3 3-1,3-2
3,1,1约束方程组的系数矩阵具有特殊的结构 （ 3.1,3.2两节
3,1,2运输问题的基变量共有 m+n-1个 的习题 ）
3,1,3 m+n-1个变量构成基变量的充要条件是不含闭回路
7 3,2运输问题的求解 (表上作业法 ) 2 4
3,2,1初始基本可行解的确定
教 学 日 历（续）
123
周次 学习内容 课内学时 自学学时 作业（教材）
3,2,2最优性检验
3,2,3主元变换
8 3,3产销不平衡的运输问题 2 4 习题 3 3-3,3-4
3,3,1产量大于销量的情况
3,3,2销量大于产量的情况
4 动态规划
8 4,1动态规划概念与模型 2 4
4,1,1引言
4,1,2多段决策过程
4,1,3动态规划模型
4,1,4动态规划建模
9 4,2动态规划求解 2 4
4,2,1解的概念
4,2,2最优性原理
4,2,3贝尔曼函数
4,2,4动态规划的基本方程
教 学 日 历（续）
124
周次 学习内容 课内学时 自学学时 作业（教材）
4,2,5动态规划方法基本原理
4,2,6动态规划问题求解的一般步骤
4,2,7动态规划四大要素、一个方程
9 4,3动态规划应用举例 10 15 习题 4 4-1,4-2
4,3,1工程路线问题 4-3,4-4
10 4,3,2资源分配问题 4-5,4-6
4,3,3串联系统可靠性问题 4-7
4,3,4生产 —库存问题
4,3,5二维背包问题
4,3,6设备更新问题
5．图与网络分析
11 5,1图的基本概念 2 4
5,1,1引言
5,1,2图的概念
5,1,3图的连通
5,1,4子图
5,1,5有向图
教 学 日 历（续）
125
周次 学习内容 课内学时 自学学时 作业（教材）
5,1,6树
11 5,2网络最短路线问题 4 8 习题 5 5-2,5-3
5,2,1引言
5,2,2最短路线问题的狄克斯拉法
5,2,3最短路线问题的海斯算法
5,2,4最短路线问题的福德算法
12 5,3最短树问题 2 4 习题 5 5-1
5,3,1引言
5,3,2破圈法
5,3,3生长法
12 5,4最大流问题 2 4 习题 5 5-4
5,4,1引言
5,4,2最大流最小割集定理
5,4,3福德 —富克逊算法
12 5,5最小费用 —最大流问题 2 4 习题 5 5-5
5,5,1引言
5,5,2对偶法原理和步骤
教 学 日 历（续）
126
周次 学习内容 课内学时 自学学时 作业（教材）
5,5,3对偶法示例
6 排队论
13 6,1概述 2 4
6,1,1引言
6,1,2排队系统的特征
6,1,3排队系统的结构
6,1,4排队论研究的内容和目的
6,1,5排队模型的分类
6,1,6排队系统的常用符号
13 6,2泊松输入 —负指数服务的系统 3 6
6,2,1典型分布
6,2,2系统状态概率分布
6,2,3状态转移速度图
6,2,4系统的运行指标
13 6,3 M/M/1无限源系统 2 4
6,3,1 M/M/1/N系统
教 学 日 历（续）
127
周次 学习内容 课内学时 自学学时 作业（教材）
6,3,2 M/M/1等待制系统
6,3,3 M/M/l损失制系统
6,3,4 M/M/1无限源模型特点
14 6,4 M/M/C无限源系统 2 4
6,4,1 M/M/C/N系统
6,4,2 M/M/C等待制系统
6,4,3 M/M/C损失制系统
14 6,5客源有限的排队系统 2 4
6,5,1 M/M/1/m/m系统
6,5,2 M/M/C/m/m系统
14 6,6排队系统应用举例 1 2 习题 6 6-1~6-8
（第 6章的习题可在充分理解概念的基础上集中练习）
6,7本章小结
教 学 日 历（续）
返回目录
运筹学
北京理工大学
管理与经济学院
吴祈宗教授
2
1、绪 论
2、线 性 规 划
3、运 输 问 题
4、动 态 规 划
5、图与网络分析
6、排 队 论
7、教学日历
运 筹 学 —— 目录
说 明
本教学课件是与教材紧密配合
使用的，教材为：
,运筹学, 杨民助编著
西安交通大学出版社,2000年 6月
参考书：
,运筹学, 清华大学出版社
或其他的, 运筹学, 方面本科教材
的相关内容
下面所标注的页号，均为本
课程教材的页号。例如：
p123 表示第 123页
p31-34 表示从第 31页到第 34页
3
绪 论
运筹学（ Operational Research) 直译为“运作研究”
运筹学是运用科学的方法（如分析、试验、
量化等）来决定如何最佳地运营和设计各种系
统的一门学科。运筹学对经济管理系统中的人
力、物力、财力等资源进行统筹安排，为决策
者提供有依据的最优方案，以实现最有效的管
理。
? 运筹学有广泛应用 （可以自己找一些参考书看）
? 运筹学的产生和发展 （可以自己找一些参考书看）
4
运筹学解决问题的过程
1）提出问题：认清问题
2）寻求可行方案：建模、求解
3）确定评估目标及方案的标准或方法、途径
4）评估各个方案：解的检验、灵敏性分析等
5）选择最优方案：决策
6）方案实施：回到实践中
7）后评估：考察问题是否得到完满解决
1） 2） 3）：形成问题； 4） 5）分析问题：定性分
析与定量分析。构成决策。
5
运筹学的分支
? 线性规划
? 非线性规划
? 整数规划
? 动态规划
? 多目标规划
? 随机规划
? 模糊规划等
? 图与网络理论
? 存储论
? 排队论
? 决策论
? 对策论
? 排序与统筹方法
? 可靠性理论等
6
运筹学在工商管理中的应用
? 生产计划：生产作业的计划、日程表的编排、合理下
料、配料问题、物料管理等
? 库存管理：多种物资库存量的管理，库存方式、库存
量等
? 运输问题：确定最小成本的运输线路、物资的调拨、
运输工具的调度以及建厂地址的选择等
? 人事管理：对人员的需求和使用的预测，确定人员编
制、人员合理分配，建立人才评价体系等
? 市场营销：广告预算、媒介选择、定价、产品开发与
销售计划制定等
? 财务和会计：预测、贷款、成本分析、定价、证券管
理、现金管理等
*** 设备维修、更新，项目选择、评价，工程优化设计与管理等
7
运筹学方法使用情况 (美 1983)（ %）
0
10
20
30
40
50
60
70
í±
??
??
??
?ú
?￡
?a
í?
??
??
??
??
D?
1?
??
??
?ó
??
·
?
??
D?
1?
??
?ˉ
ì?
1?
??
??
°?
??
2ó °? ê1 ó? óD ê±ê1 ó? ?- ±￡ ê1 ó?
8
0
10
20
30
40
50
60
70
80
90
í±
??
??
??
?ú
?￡
?a
í?
??
??
??
??
D?
1?
??
??
?ó
??
·
?
??
D?
1?
??
?ˉ
ì?
1?
??
??
°?
??
2ó °? ê1 ó? óD ê±ê1 ó? ?- ±￡ ê1 ó?
运筹学方法在中国使用情况 (随机抽样 )（ %）
9
运筹学的推广应用前景
? 据美劳工局 1992年统计预测,
运筹学应用分析人员需求从 1990年到 2005
年的增长百分比预测为 73%,增长速度排到各项
职业的前三位,
结论,
? 运筹学在国内或国外的推广前景是非常广阔的
? 工商企业对运筹学应用和需求是很大的
? 在工商企业推广运筹学方面有大量的工作要做
10
? 学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程
中，应该多向自己提问，如一个方法的实质是什么，为什么这样做，怎
么做等。
? 自学时要掌握三个重要环节：
1、认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运
筹学教材都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助
你开阔思路，使学习深入。但是，把时间过多放在参考资料上，会导致思路分散，不利于
学好。
2、要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助你理解概念、理论
的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因此，做
题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整体，各节内容有内在联
系，只要学到一定程度，知识融会贯通起来，你做题的正确性自己就有判断。
3、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来该书所学内容。这
样，你才能够从较高的角度来看问题，更深刻的理解有关知识和内容。这就称作“把书读
薄”，若能够结合自己参考大量文献后的深入理解，把相关知识从更深入、广泛的角度进
行论述，则称之为“把书读厚”
? 在建数学模型时要结合实际应用，要学会用计算机软件解决问题 。
如何学习运筹学课程
返回目录
11
各章节的重点、难点
及注意事项
12
1,线 性 规 划
线性规划模型：
目标函数,Max z = 50 x1 + 100 x2
约束条件,s.t,x1 + x2 ≤ 300
2 x1 + x2 ≤ 400
x2 ≤ 250
x1,x2 ≥ 0
**看 p 7--9 例 1-1,1-2
例 1,某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时
及 A,B两种原材料的消耗以及资源的限制，如下表：
问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？
甲 乙 资源限制
设备 1 1 300 台时
原料 A 2 1 400 千克
原料 B 0 1 250 千克
单位产品获利 50 元 100 元
13
1,线 性 规 划 （续 1.1）
1,1 线性规划的概念
? 线性规划的组成, 目标函数 Max f 或 Min f
约束条件 s.t,(subject to) 满足于
决策变量 用符号来表示可控制的因素
? 一般形式 ( p10-- p 11)
目标函数,Max （ Min） z = c1 x1 + c2 x2 + … + c n xn
约束条件,s.t,a11 x1 + a12 x2 + … + a1n xn ≤ （ =,≥ ） b1
a21 x1 + a22 x2 + … + a2n xn ≤ （ =,≥ ） b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ （ =,≥ ） bm
x1, x2, …, xn ≥ 0
? 标准形式 ( p11-- p 15,例 1-3)
目标函数,Max z = c1 x1 + c2 x2 + … + c n xn
约束条件,s.t,a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1, x2, …, xn ≥ 0
**练习,p 68--70 习题 1 1-1,1-2
14
1,线 性 规 划 （续 1.2）
1,2 线性规划问题解的概念及性质
? 熟悉下列一些解的概念（ p15--16）
可行解、可行解集（可行域），最优解、最优值，基、基变量、非基变量，基本
解、基本可行解，可行基、最优基。
?图解方法及各有关概念的意义（ p16--20）
看：图解法步骤，例 1-4,1-5,1-6,1-7,1-8,1-9
下一页是一个图解法解题的一个例子，右图中的阴影部分为可行域。
? 单纯形法的理论基础（ p20--30）
1.2.3段要求看懂，了解如何直接通过对约束矩阵的分析求出基本可行解
1.2.4,1.2.5两段应注重结论的了解，如单纯形法思想和关于线性规划解的四个
定理，而对证明过程则可根据自己的数学基础来掌握：
基础很好，可要求掌握；否则，也可略去不看。
**习题,p70 习题 1 1-3,1-4
15
1,线 性 规 划 （续 1.2）
例 1.
目标函数：
Max z = 50 x1 + 100 x2
约束条件：
s.t,
x1 + x2 ≤ 300 (A)
2 x1 + x2 ≤ 400 (B)
x2 ≤ 250 (C)
x1 ≥ 0 (D)
x2 ≥ 0 (E)
得到最优解：
x1 = 50,x2 = 250
最优目标值 z = 27500
16
1,线 性 规 划 （续 1.3）
1,3 单纯形法
利用单纯形表的方法求解线性规
划 —— 重点 (p30--45 1.3.1,1.3.2,
1.3.3)
此项内容是本章的重点，学习中应
注意掌握表格单纯形法求解线性规划问
题的基本过程。要通过读懂教材内容以
及大量练习来掌握。
17
1,线 性 规 划 （续 1.3）
? 表格单纯形法 ( p40-- p 45)
? 考虑,bi > 0 i = 1,…,m
Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn ≤ b1
a21 x1 + a22 x2 + … + a2n xn ≤ b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ bm
x1, x2, …, xn ≥ 0
? 加入松弛变量：
Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2
…… ……
am1 x1 + am2 x2 + … + amn xn+ xn+m = bm
x1, x2, …, xn, xn+1, …, xn+m ≥ 0
18
显然,xj= 0 j = 1,…,n ; xn+i = bi i = 1,…,m 是基本可行解
对应的基是单位矩阵。
以下是初始单纯形表：
m m
其中,f = -∑ cn+i bi ?j = cj -∑ cn+i aij 为检验数 cn+i = 0 i= 1,…,m
i = 1 i = 1
an+i,i = 1,an+i,j = 0 ( j≠i ) i,j = 1,…,m
1,线 性 规 划 （续 1.3）
c
1 ?
c
n
c
n + 1 ?
c
n + m
C
B
X
B x
1 ?
x
n
x
n + 1 ?
x
n + m
θ
i
c
n + 1
x
n + 1
b
1
a
11 ?
a
1n
a
1 n + 1 ?
a
1 n + m θ 1
c
n + 2
x
n + 2
b
2
a
21 ?
a
2n
a
2 n + 1 ?
a
2 n + m θ 2
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
c
n + m
x
n + m
b
m
a
m1 ?
a
mn
a
m n + 1 ?
a
m n + m θ m
-z f σ
1
? σ
n
0 ? 0
19
1,线 性 规 划 （续 1.3单纯形法解题例）
50 100 0 0 0
C
B
X
B
x
1
x
2
x
3
x
4
x
5
θ
i
0 x
3
300 1 1 1 0 0 300
0 x
4
400 2 1 0 1 0 400
0 x
5
250 0 (1) 0 0 1 250
-z 0 50 100* 0 0 0
0 x
3
50 (1) 0 1 0 -1 50
0 x
4
150 2 0 0 1 -1 75
100 x
2
250 0 1 0 0 1
-z - 25 00 0 50* 0 0 0 - 10 0
50 x
1
50 1 0 1 0 -1
0 x
4
50 0 0 -2 1 1
100 x
2
250 0 1 0 0 1
-z - 27 50 0 0 0 - 50 0 - 50
例 1。化标准形式,Max z = 50 x1 + 100 x2
s.t,x1 + x2 + x3 = 300
2 x1 + x2 + x4 = 400
x2 + x5 = 250
x1,x2,x3,x4,x5 ≥ 0
最优解 x1 = 50 x2 = 250 x4 = 50（松弛标量，表示原料 A有 50个单位的剩余）
20
? 注意：单纯形法中，
1、每一步运算只能用矩阵初等行变换；
2、表中第 3列的数总应保持非负（ ≥ 0）；
3、当所有检验数均非正（ ≤ 0）时，得到最
优单纯形表。
1,线 性 规 划 （续 1.3）
21
1,线 性 规 划 （续 1.3）
? 一般情况的处理及注意事项的强调（ p45--55）
1.3.4段主要是讨论初始基本可行解不明显时，常用的方法。
要弄清它的原理，并通过例 1-14 ~ 例 1-17掌握这些方法，同
时进一步熟悉用单纯形法解题。
考虑一般问题,bi > 0 i = 1,…,m
Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1, x2, …, xn ≥ 0
22
1,线 性 规 划 （续 1.3）
? 大 M法,引入人工变量 xn+i ≥ 0 i = 1,…,m ; 充
分大正数 M 。 得到，
Max z = c1 x1 + c2 x2 + … + c n xn + M xn+1 + … + M x n+m
s.t,a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2
…… ……
am1 x1 + am2 x2 + … + amn xn + xn+m = bm
x1, x2, …, xn, xn+1, …, xn+m ≥ 0
显然,xj= 0 j=1,…,n ; xn+i = bi i =1,…,m 是基本可行解
对应的基是单位矩阵。
? 结论：若得到的最优解满足 xn+i = 0 i = 1,…,m 则是原
问题的最优解；否则，原问题无可行解。
23
1,线 性 规 划 （续 1.3）
? 两阶段法,引入人工变量 xn+i ≥ 0,i = 1,…,m ；构造，
Max z = - xn+1 - xn+2 - … - xn+m
s.t,a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2
…… ……
am1 x1 + am2 x2 + … + amn xn + xn+m = bm
x1, x2, …, xn, xn+1, …, xn+m ≥ 0
? 第一阶段求解上述问题：
显然,xj= 0 j=1,…,n ; xn+i = bi i =1,…,m 是基本可行解
对应的基是单位矩阵。
? 结论：若得到的最优解满足 xn+i = 0 i = 1,…,m 则是原问
题的基本可行解；否则，原问题无可行解。
? 得到原问题的基本可行解后，第二阶段求解原问题。
24
1,线 性 规 划 （续 1.3）例题
例：（ LP） Max z = 5 x1 + 2 x2 + 3 x3 - x4
s.t,x1 + 2 x2 + 3 x3 = 15
2 x1 + x2 + 5 x3 = 20
x1 + 2 x2 + 4 x3 + x4 = 26
x1,x2,x3,x4 ≥ 0
? 大 M法问题（ LP - M）
Max z = 5 x1 + 2 x2 + 3 x3 - x4 - M x5 - M x6
s.t,x1 + 2 x2 + 3 x3 + x5 = 15
2 x1 + x2 + 5 x3 + x6 = 20
x1 + 2 x2 + 4 x3 + x4 = 26
x1,x2,x3,x4,x5,x6 ≥ 0
? 两阶段法,第一阶段问题（ LP - 1）
Max z = - x5 - x6
s.t,x1 + 2 x2 + 3 x3 + x5 = 15
2 x1 + x2 + 5 x3 + x6 = 20
x1 + 2 x2 + 4 x3 + x4 = 26
x1,x2,x3,x4,x5,x6 ≥ 0
25
1,线 性 规 划 （续 1.3）大 M法例
5 2 3 -1 -M -M
C
B
X
B
x
1
x
2
x
3
x
4
x
5
x
6
θ
i
-M x
5
15 1 2 3 0 1 0 5
-M x
6
20 2 1 ( 5) 0 0 1 4
-1 x
4
26 1 2 4 1 0 0 6.5
-z 35M + 26 3M + 6 3M + 4 8M + 7 0 0 0
-M x
5
3 - 1/ 5 ( 7/ 5) 0 0 1 - 3/ 5 15/ 7
3 x
3
4 2/ 5 1/ 5 1 0 0 1/ 5 20
-1 x
4
10 - 3/ 5 6/ 5 0 1 0 - 4/ 5 25/ 3
-z 3M - 2 - M / 5+ 16/ 5 7/ 5M + 13/ 5 0 0 0 - 8/ 5M - 7/ 5
2 x
2
15/ 7 - 1/ 7 1 0 0 5/ 7 - 3/ 7
3 x
3
25/ 7 ( 3/ 7) 0 1 0 - 1/ 7 2/ 7 25/ 3
-1 x
4
52/ 7 - 3/ 7 0 0 1 - 6/ 7 - 2/ 7
-z - 53/ 7 25/ 7 0 0 0 - M - 13 / 7 - M - 2 / 7
2 x
2
10/ 3 0 1 1/ 3 0 2/ 3 - 1/ 3
5 x
1
25/ 3 1 0 7/ 3 0 - 1/ 3 2/ 3
-1 x
4
11 0 0 1 1 -1 0
-z - 1 12/ 3 0 0 - 25/ 3 0 - M - 2 / 3 - M + 8/ 3
?大 M法 （ LP - M）
?得到最优解,(25/3,10/3,0,11)T 最优目标值,112/3
26
1,线 性 规 划 （续 1.3）两阶段法例
0 0 0 0 -1 -1
C
B
X
B
x
1
x
2
x
3
x
4
x
5
x
6
θ
i
-1 x
5
15 1 2 3 0 1 0 5
-1 x
6
20 2 1 ( 5) 0 0 1 4
0 x
4
26 1 2 4 1 0 0 6.5
-z 35 3 3 8 0 0 0
-1 x
5
3 - 1/ 5 ( 7/ 5) 0 0 1 - 3/ 5 15/ 7
0 x
3
4 2/ 5 1/ 5 1 0 0 1/ 5 20
0 x
4
10 - 3/ 5 6/ 5 0 1 0 - 4/ 5 25/ 3
-z 3 - 1/ 5 7/ 5 0 0 0 - 8/ 5
0 x
2
15/ 7 - 1/ 7 1 0 0 5/ 7 - 3/ 7
0 x
3
25/ 7 3/ 7 0 1 0 - 1/ 7 2/ 7 25/ 3
0 x
4
52/ 7 - 3/ 7 0 0 1 - 6/ 7 - 2/ 7
-z 0 0 0 0 0 -1 -1
?第一阶段 （ LP - 1）
?得到原问题的基本可行解,(0,15/7,25/7,52/7)T
27
1,线 性 规 划 （续 1.3）两阶段法例
5 2 3 -1
C
B
X
B x 1 x 2 x 3 x 4 θ i
2 x
2
1 5 / 7 - 1 / 7 1 0 0
3 x
3
2 5 / 7 (3/ 7 ) 0 1 0 2 5 / 3
-1 x 4 5 2 / 7 - 3 / 7 0 0 1
-z - 5 3 / 7 2 5 / 7 0 0 0
2 x
2
1 0 / 3 0 1 1 / 3 0
5 x
1
2 5 / 3 1 0 7 / 3 0
-1 x
4
11 0 0 1 1
-z - 1 1 2 / 3 0 0 - 2 5 / 3 0
?第二阶段 把基本可行解填入表中
?得到原问题的最优解,(25/3,10/3,0,11)T
?最优目标值,112/3
28
1,线 性 规 划 （续 1.3）
1.3.5 矩阵描述 —— 此段为选读，有
困难者可不看。
1.3.6 段单纯形迭代过程中的几点注
意事项是对有关内容的强调和补充，要
认真学习、理解。
**习题,p70--71 习题 1 1-5,1-6
29
1,4 线性规划应用 —— 建模（ p55--68）
本节介绍了些线性规划应用的例子，这些例子从多个方面介绍建模对未来
是很有用的，应认真对待。
除了教材上的例子之外，还有许多其它应用：
* 合理利用线材问题：如何下料使用材最少
* 配料问题：在原料供应量的限制下如何获取最大利润
* 投资问题：从投资项目中选取方案，使投资回报最大
* 产品生产计划：合理利用人力、物力、财力等，使获利最大
* 劳动力安排：用最少的劳动力来满足工作的需要
* 运输问题：如何制定调运方案，使总运费最小
**下面是一些建模的例子，有兴趣者，可作为练习。这些例子有一定的难度，做
起来会有一些困难。
**习题,p72--73 习题 1 1-7,1-8,1-9,1-10
1,线 性 规 划 （续 1.4）
返回目录
30
例．某昼夜服务的公交线路每天各时间段内所需司机和乘务人
员数如下：
设司机和乘务人员分别在各时间段一开始时上班，并连续
工作八小时，问该公交线路怎样安排司机和乘务人员，既能
满足工作需要，又配备最少司机和乘务人员?
班次 时间 所需人数
1 6, 00 —— 10, 00 60
2 10, 00 —— 14, 00 70
3 14, 00 —— 18, 00 60
4 18, 00 —— 22, 00 50
5 22, —— 2, 00 20
6 2, 00 —— 6, 00 30
例：人力资源分配的问题
31
解：设 xi 表示第 i班次时开始上班的司机和乘务人
员数,这样我们建立如下的数学模型。
目标函数,Min x1 + x2 + x3 + x4 + x5 + x6
约束条件,s.t,x1 + x6 ≥ 60
x1 + x2 ≥ 70
x2 + x3 ≥ 60
x3 + x4 ≥ 50
x4 + x5 ≥ 20
x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0
例：人力资源分配的问题（续）
32
例,明兴公司生产甲、乙、丙三种产品，都需要经过铸
造、机加工和装配三个车间。甲、乙两种产品的铸件可以外
包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证
质量。数据如下表。问：公司为了获得最大利润，甲、乙、
丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本
公司铸造和由外包协作各应多少件？
甲 乙 丙 资源限制
铸造工时 ( 小时 / 件 ) 5 10 7 8000
机加工工时 ( 小时 / 件 ) 6 4 8 12000
装配工时 ( 小时 / 件 ) 3 2 2 10000
自产铸件成本 ( 元 / 件 ) 3 5 4
外协铸件成本 ( 元 / 件 ) 5 6 --
机加工成本 ( 元 / 件 ) 2 1 3
装配成本 ( 元 / 件 ) 3 2 2
产品售价 ( 元 / 件 ) 23 18 16
例：生产计划的问题
33
解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙
三种产品的件数,x4,x5 分别为由外协铸造再由本公司机加
工和装配的甲、乙两种产品的件数。
求 xi 的利润：利润 = 售价 - 各成本之和
可得到 xi（ i=1,2,3,4,5）的利润分别为 15,10,7,13,9元。
这样我们建立如下的数学模型。
目标函数,Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5
约束条件,s.t,5x1 + 10x2 + 7x3 ≤ 8000
6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000
3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000
x1,x2,x3,x4,x5 ≥ 0
例：生产计划的问题（续）
34
例,永久机械厂生产 Ⅰ, Ⅱ, Ⅲ 三种产品，均要经过 A,B 两
道工序加工。假设有两种规格的设备 A1,A2能完成 A 工序；
有三种规格的设备 B1,B2,B3能完成 B 工序。 Ⅰ 可在 A,B的
任何规格的设备上加工； Ⅱ 可在任意规格的 A设备上加工，
但对 B工序，只能在 B1设备上加工； Ⅲ 只能在 A2与 B2设备上加
工；数据如下表。问：为使该厂获得最大利润，应如何制定
产品加工方案？
产品单件工时
设备 Ⅰ Ⅱ Ⅲ
设备的
有效台时
满负荷时的
设备费用
A
1
5 10 6000 300
A
2
7 9 12 10000 321
B
1
6 8 4000 50
B
2
4 11 7000 783
B
3
7 4000 200
原料 （元 / 件） 0.25 0.35 0.50
售价 （元 / 件） 1.25 2.00 2.80
例：生产计划的问题（续）
35
解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工
的数量。
利润 = [（销售单价 - 原料单价） * 产品件数 ]之和 - （每台时的
设备费用 *设备实际使用的总台时数）之和。
这样我们建立如下的数学模型,
Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-
0.5x221-0.4475x122-1.2304x322-0.35x123
s.t,5x111 + 10x211 ≤ 6000 （ 设备 A1 ）
7x112 + 9x212 + 12x312 ≤ 10000 （ 设备 A2 ）
6x121 + 8x221 ≤ 4000 （ 设备 B1 ）
4x122 + 11x322 ≤ 7000 （ 设备 B2 ）
7x123 ≤ 4000 （ 设备 B3 ）
x111+ x112- x121- x122- x123 = 0 （ Ⅰ 产品在 A,B工序加工的数量相等）
x211+ x212- x221 = 0 （ Ⅱ 产品在 A,B工序加工的数量相等）
x312 - x322 = 0 （ Ⅲ 产品在 A,B工序加工的数量相等）
xijk ≥ 0,i = 1,2,3; j = 1,2; k = 1,2,3
例：生产计划的问题（续）
36
例、某工厂要做 100套钢架，每套用长为 2.9 m,2.1 m,1.5 m的
圆钢各一根。已知原料每根长 7.4 m，问：应如何下料，可
使所用原料最省？
解,设计下列 5 种下料方案
方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8
2, 9 m 1 2 0 1 0 1 0 0
2, 1 m 0 0 2 2 1 1 3 0
1, 5 m 3 1 2 0 3 1 0 4
合计 7, 4 7, 3 7, 2 7, 1 6, 6 6,5 6,3 6, 0
剩余料头 0 0, 1 0, 2 0, 3 0, 8 0, 9 1,1 1, 4
假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根
数。这样我们建立如下的数学模型。
目标函数,Min x1 + x2 + x3 + x4 + x5
约束条件,s.t,x1 + 2x2 + x4 ≥ 100
2x3 + 2x4 + x5 ≥ 100
3x1 + x2 + 2x3 + 3x5 ≥ 100
x1,x2,x3,x4,x5 ≥ 0
例：套裁下料问题
37
例 6．某工厂要用三种原料 1,2,3混合调配出三种不
同规格的产品甲、乙、丙，数据如下表。问：该厂
应如何安排生产，使利润收入为最大？
产品名称 规格要求 单价 （元 /kg ）
甲 原材料 1 不少于 50 %,原材料 2 不超过 25% 50
乙 原材料 1 不少于 25 %,原材料 2 不超过 50% 35
丙 不限 25
原材料名称 每天最多供应量 单价 （元 /kg ）
1 100 65
2 100 25
3 60 35
例：配料问题
38
例：配料问题（续）
解,设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含
量。这样我们建立数学模型时，要考虑：
对于甲,x11,x12,x13；
对于乙,x21,x22,x23；
对于丙,x31,x32,x33；
对于原料 1,x11,x21,x31；
对于原料 2,x12,x22,x32；
对于原料 3,x13,x23,x33；
目标函数,利润最大，利润 = 收入 - 原料支出
约束条件,规格要求 4 个；
供应量限制 3 个。
39
Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33
s.t,0.5 x11-0.5 x12 -0.5 x13 ≥ 0 （原材料 1不少于 50%）
-0.25x11+0.75x12 -0.25x13 ≤ 0 （原材料 2不超过 25%）
0.75x21-0.25x22 -0.25x23 ≥ 0 （原材料 1不少于 25%）
-0.5 x21+0.5 x22 -0.5 x23 ≤ 0 （原材料 2不超过 50%）
x11+ x21 + x31 ≤ 100 ( 供应量限制）
x12+ x22 + x32 ≤ 100 ( 供应量限制）
x13+ x23 + x33 ≤ 60 ( 供应量限制）
xij ≥ 0,i = 1,2,3; j = 1,2,3
例：配料问题（续）
40
例 8．某部门现有资金 200万元，今后五年内考虑给以下的项目投资。已知：项
目 A：从第一年到第五年每年年初都可投资，当年末能收回本利 110%；项目 B：从第
一年到第四年每年年初都可投资，次年末能收回本利 125%，但规定每年最大投资额
不能超过 30万元；项目 C：需在第三年年初投资，第五年末能收回本利 140%，但规
定最大投资额不能超过 80万元；项目 D：需在第二年年初投资，第五年末能收回本
利 155%，但规定最大投资额不能超过 100万元；
据测定每万元每次投资的风险指数如右表：
问：
a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最
大？
b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在 330万元
的基础上使得其投资总的风险系数为最小？
项目 风险指数 （次 /万元）
A 1
B 3
C 4
D 5, 5
解,1） 确定决策变量：连续投资问题
设 xij ( i = 1 - 5,j = 1,2,3,4)表示第 i 年初投资于 A(j=1),B(j=2),C(j=3)、
D(j=4)项目的金额。这样我们建立如下的决策变量：
A x11 x21 x31 x41 x51
B x12 x22 x32 x42
C x33
D x24
例：投资问题
41
2）约束条件：
第一年,A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200；
第二年,B次当年末才可收回投资故第二年年初的资金为 x11，于是 x21 + x22+ x24 = 1.1x11；
第三年：年初的资金为 x21+x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12；
第四年：年初的资金为 x31+x22，于是 x41 + x42 = 1.1x31+ 1.25x22；
第五年：年初的资金为 x41+x32，于是 x51 = 1.1x41+ 1.25x32；
B,C,D的投资限制,xi2 ≤ 30 ( I =1, 2,3,4 ),x33 ≤ 80, x24 ≤ 100
3）目标函数及模型：
a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24
s.t,x11+ x12 = 200
x21 + x22+ x24 = 1.1x11；
x31 + x32+ x33 = 1.1x21+ 1.25x12；
x41 + x42 = 1.1x31+ 1.25x22；
x51 = 1.1x41+ 1.25x32；
xi2 ≤ 30 ( I =1, 2,3,4 ),x33 ≤ 80, x24 ≤ 100
xij ≥ 0 ( i = 1, 2,3,4,5； j = 1,2,3,4）
b) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24
s.t,x11+ x12 = 200
x21 + x22+ x24 = 1.1x11；
x31 + x32+ x33 = 1.1x21+ 1.25x12；
x41 + x42 = 1.1x31+ 1.25x22；
x51 = 1.1x41+ 1.25x32；
xi2 ≤ 30 ( I =1, 2,3,4 ),x33 ≤ 80, x24 ≤ 100
1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330
xij ≥ 0 ( i = 1, 2,3,4,5； j = 1,2,3,4）
例：投资问题（续）
42
2、线性规划问题的进一步研究（ 2.1）
2,1 对偶原理
1、对偶问题,考虑前文例 1
若设备和原料都用于外协加工，工厂收取加工费。试问：
设备工时和原料 A,B 各如何收费才最有竞争力？
设 y1, y2, y3 分别为每设备工时、
原料 A,B每单位的收取费用
Max z = 50 x1 + 100 x2 Min f = 300 y1 + 400 y2 + 250 y3
s.t,x1 + x2 ≤ 300 s.t,y1 + 2 y2 + ≥ 50
2 x1 + x2 ≤ 400 （不少于甲产品的利润）
x2 ≤ 250 y1 + y2 + y3 ≥ 100
x1,x2 ≥ 0 y1,y2,y3 ≥ 0
43
2、对偶定义
? 对称形式,互为对偶
(LP) Max z = cT x ? (DP) Min f = bT y
s.t,Ax ≤ b s.t,AT y ≥ c
x ≥ 0 y ≥ 0
“Max -- ≤,,Min-- ≥”
? 一般形式：
若一个问题的某约束为等式，那么对应的对偶问题的
相应变量无非负限制；反之,若一个问题的某变量无非负
限制，那么对应的对偶问题的相应约束为等式。
2、线性规划问题的进一步研究（ 2.1）
44
3、对偶定理 （原问题与对偶问题解的关系）
考虑（ LP）和（ DP）
定理 2-1 （弱对偶定理）若 x,y 分别为（ LP）和（ DP）的可行
解，那么 cT x ≤ bT y 。
推论 若（ LP）可行，那么（ LP）无有限最优解的充分必要条
件是（ LD）无可行解。
定理 2-2 （最优性准则定理）若 x,y 分别为（ LP）和（ DP）的
可行解，且 cT x = bT y,那么 x,y分别为（ LP）和（ DP）的
最优解。
定理 2-3 （主对偶定理）若（ LP）和（ DP）均可行，那么
（ LP）和（ DP）均有最优解，且最优值相等。
以上定理、推论对任意形式的相应线性规划的对偶均有效
**习题,p 99 习题 2 2-1
2、线性规划问题的进一步研究（ 2.1）
45
4、影子价格 —— 是一个向量，它的分量表示最优目
标值随相应资源数量变化的变化率。
若 x*,y* 分别为（ LP）和（ DP）的最优解，
那么,cT x* = bT y* 。
根据 f = bT y* = b1y1* + b2y2* + ?? + bmym*
可知 ?f / ?bi = yi*
yi* 表示 bi 变化 1个单位对目标 f 产生的影响，称
yi* 为 bi的影子价格。
注意：若 B 是最优基,y* = (BT)-1 cB 为影子价格向量。
2、线性规划问题的进一步研究（ 2.1）
46
5、由最优单纯形表求对偶问题最优解
第 1章例 1。化标准形式,Max z = 50 x1 + 100 x2
s.t,x1 + x2 + x3 = 300, 2 x1 + x2 + x4 = 400
x2 + x5 = 250, x1,x2,x3,x4,x5 ≥ 0 I
O
B=(p1,p4,p2 )
(BT)-1 cB
B-1
最优解 x1 = 50 x2 = 250 x4 = 50（松弛标量，表示原料 A有 50个单位的
剩余） 影子价格 y1 = 50 y2 = 0 y3 = 50,B-1对应的检验数 (BT)-1 cB 。
2、线性规划问题的进一步研究（ 2.1）
50 100 0 0 0
C
B
X
B
x
1
x
2
x
3
x
4
x
5
θ
i
0 x
3
300 1 1 1 0 0 300
0 x
4
400 2 1 0 1 0 400
0 x
5
250 0 (1) 0 0 1 250
-z 0 50 100* 0 0 0
0 x
3
50 (1) 0 1 0 -1 50
0 x
4
150 2 0 0 1 -1 75
100 x
2
250 0 1 0 0 1
-z - 25 00 0 50* 0 0 0 - 10 0
50 x
1
50 1 0 1 0 -1
0 x
4
50 0 0 -2 1 1
100 x
2
250 0 1 0 0 1
-z - 27 50 0 0 0 - 50 0 - 50
47
2,2 对偶单纯形法
? 对偶单纯形法在什么情况下使用,
应用前提：有一个基，其对应的基本解满足
① 单纯形表的检验数行全部非正（对偶可
行）；
② 变量取值可有负数（非可行解）。
**注：通过矩阵行变换运算，使所有相应变
量取值均为非负数即得到最优单纯性表。
2、线性规划问题的进一步研究（ 2.2）
48
2、线性规划问题的进一步研究（ 2.2）
? 对偶单纯形法求解线性规划问题过程：
1、建立初始对偶单纯形表，对应一个基本解，所有
检验数均非正，转 2；
2、若 b’≥ 0,则得到最优解，停止；否则，若有 bk <
0 则选 k 行的基变量为出基变量，转 3；
3、若所有 akj’≥ 0 ( j = 1,2,…,n ),则原问题无可行解，
停止；否则，若有 akj’< 0 则选
? = min {?j’/ akj’┃ akj’< 0 } = ?r’/ akr’那么 r 为
进基变量，转 4；
4、以 akr’为转轴元，作矩阵行变换使其变为 1，该列
其他元变为 0，转 2。
49
例,求解线性规划问题：
Min f = 2 x1 + 3 x2 + 4 x3
S.t,x1 + 2x2 + x3 ≥ 3
2x1 - x2 + x3 ≥ 4
x1,x2,x3 ≥ 0
标准化：
Max Z = - 2x1 - 3x2 - 4x3
S.t,- x1 - 2x2 - x3 + x4 = - 3
- 2x1 + x2 - 3x3 + x5 = - 4
x1,x2,x3,x4,x5 ≥ 0
2、线性规划问题的进一步研究（ 2.2）
50
? 表格对偶单纯形法
**习题,p 100 习题 2 2-2,2-3
C
I
-2 -3 -4 0 0
C
B
X
B
b X
1
X
2
X
3
X
4
X
5
0 X
4
-3 -1 -2 -1 1 0
0 X
5
-4 [- 2] 1 -3 0 1
σ
j
-2 -3 -4 0 0
0 X
4
-1 0 [- 5/2 ] 1/2 1 -1/ 2
-2 X
1
2 1 -1/ 2 3/2 0 -1/ 2
σ
j
0 -4 -1 0 -1
-3 X
2
2/5 0 1 -1/ 5 -2/ 5 1/5
-2 X
1
11/
5
1 0 7/5 -1/ 5 -2/ 5
σ
j
0 0 -9/ 5 -8/ 5 -1/ 5
2、线性规划问题的进一步研究（ 2.2）
51
2.3 灵敏度分析
? 进一步理解最优单纯形表中各元素的含义
考虑问题 Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn ≤ b1
a21 x1 + a22 x2 + … + a2n xn ≤ b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ bm
x1, x2, …, xn ≥ 0
引入 m 个松弛变量后，通过计算得到最优单纯形表。应
-1 -1能够找到最优基 B的逆矩阵 B,以及 B N，检验数等。
2、线性规划问题的进一步研究（ 2.3）
52
2、线性规划问题的进一步研究（ 2.3）
c
1 ?
c
n
0 ? 0
C
B
X
B x
1 ?
x
n
x
n + 1 ?
x
n + m
θ
i
0 x
n + 1
b
1
a
11 ?
a
1n
1 ? 0 θ
1
0 x
n + 2
b
2
a
21 ?
a
2n
0 ? 0 θ
2
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
0 x
n + m
b
m
a
m1 ?
a
mn
0 ? 1 θ
m
-z f c
1
? c
n
0 ? 0
c
1 ?
c
n
c
n + 1 ?
c
n +m
C
B
X
B x
1 ?
x
n
x
n +1 ?
x
n +m
θ
i
c
i 1
x
i 1
b
1
a
11 ?
a
1n
a
1 n +1 ?
a
1 n +m θ 1
c
i 2
x
i 2
b
2
a
21 ?
a
2n
a
2 n +1 ?
a
2 n +m θ 2
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
C
i m
x
i m
b
m
a
m1 ?
a
mn
a
m n +1 ?
a
m n + m θ m
-z f σ
1
? σ
n
σ
n +1
? σ
n +m
最优单纯形表
B-1
(BT)-1cB
I
O
53
? 价值系数 C发生变化：
m
考虑检验数 ?j = cj -∑ cri arij j = 1,2,……,ni = 1
1、若 ck 是非基变量的系数：
设 ck 变化为 ck + ?ck ?k’= ck + ?ck -∑ cri arik = ?k+ ?ck
只要 ?k’≤ 0,即 ?ck ≤ - ?k, 则最优解不变；否则，将最优
单纯形表中的检验数 ?k 用 ?k’取代，继续单纯形法的表格计
算 。
例, Max Z = - 2x1 - 3x2 - 4x3
S.t,- x1 - 2x2 - x3 + x4 = - 3
- 2x1 + x2 - 3x3 + x5 = - 4
x1,x2,x3,x4,x5 ≥ 0
2、线性规划问题的进一步研究（ 2.3）
54
例：最优单纯形表
从表中看到 σ 3 = C3 +Δ C3 - （ C2 * a13 + C1* a23 ）
可得到 Δ C3 ≤ 9/5 时，原最优解不变。
2、线性规划问题的进一步研究（ 2.3）
C I -2 -3 -4 0 0
C B X B b X 1 X 2 X 3 X 4 X 5
-3 X 2 2/ 5 0 1 - 1/ 5 - 2/ 5 1/ 5
-2 X 1 11/ 5 1 0 7/ 5 - 1/ 5 - 2/ 5
σ j 0 0 - 9/ 5 - 8/ 5 - 1/ 5
C I -2 -3 -4 + Δ c
3
0 0
C B X B b X 1 X 2 X 3 X 4 X 5
-3 X 2 2/ 5 0 1 - 1/ 5 - 2/ 5 1/ 5
-2 X 1 11/5 1 0 7/ 5 - 1/ 5 - 2/ 5
σ j 0 0 - 9/ 5 + Δ c 3 - 8/ 5 - 1/ 5
55
2、若 cs 是基变量的系数,设 cs 变化为 cs + ?cs,那么
?j’= cj -∑ cri arij - ( cs + ?cs ) asj = ?j - ?cs asj,对所有非基变量
i ≠ s
只要对所有非基变量 ?j’≤ 0,即 ?j ≤ ?cs asj, 则最优
解不变；否则，将最优单纯形表中的检验数 ?j 用 ?j’取代，
继续单纯形法的表格计算 。
Max{?j / asj ?asj > 0 } ≤ ?cs ≤ Min{?j / asj ?asj < 0 }
例, Max Z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5
S.t,x1 + 2x2+ x3 = 8
4x1 + x4 =16
4x2 +x5 = 12
x1,x2,x3,x4,x5 ≥ 0
2、线性规划问题的进一步研究（ 2.3）
56
例、下表为最优单纯形表，考虑基变量系数 c2 发生变化
从表中看到 σ j = Cj - （ C1 * a1j + C5 * a5j + （ C2 +Δ C2 ） * a2j ） j = 3,4
可得到 -3 ≤ Δ C2 ≤ 1 时，原最优解不变。
C
i
2 3 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2 X
1
4 1 0 0 1/ 4 0
0 X
5
4 0 0 -2 1/ 2 1
3 X
2
2 0 1 1/ 2 - 1 / 8 0
σ
j 0 0 - 1.5 - 1 / 8 0
C
i
2 3+ Δ C 2 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2 X
1
4 1 0 0 1/ 4 0
0 X
5
4 0 0 -2 1/ 2 1
3+ Δ C
2 X 2 2 0 1 1/ 2 - 1 / 8 0
σ
j 0 0 - 1, 5 - Δ C 2 /2 - 1 / 8 + Δ C 2 /8 0
2、线性规划问题的进一步研究（ 2.3）
57
? 右端项 b 发生变化
设分量 br 变化为 br + ?br,根据第 1章的讨论，最优解
的基变量 xB = B-1b，那么只要保持 B-1(b + ?b) ≥ 0,则最优
基不变，即基变量保持，只有值的变化；否则，需要利用对
偶单纯形法继续计算。
对于问题 (LP) Max z = cT x
s.t,Ax ≤ b
x ≥ 0
最优单纯形表中含有
B-1 = （ aij ） i = 1,…,m ; j = n+1,…,n+m
那么，新的 xi = (B-1b)i + ?br air i = 1,…,m 。由此可得，最优
基不变的条件是
Max{-bi / air ?air > 0 } ≤ ?br ≤ Min{-bi / air ?air < 0 }
2、线性规划问题的进一步研究（ 2.3）
58
例、上例最优单纯形表如下
? 0 0.25 0 ?
这里 B-1 = ? -2 0.5 1 ? 各列分别对应 b1,b2,b3 的单一
?0.5 -0.125 0 ?
变化。因此，设 b1 增加 4，则 x1,x5,x2 分别变为：
4 + 0*4 = 4,4 + (-2)*4 = - 4 < 0,2 + 0.5*4 = 4
用对偶单纯形法进一步求解，可得：
x* = ( 4,3,2,0,0 )T f* = 17
2、线性规划问题的进一步研究（ 2.3）
C
i
2 3 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2 X
1
4 1 0 0 1/ 4 0
0 X
5
4 0 0 -2 1/ 2 1
3 X
2
2 0 1 1/ 2 - 1 / 8 0
σ
j 0 0 - 1.5 - 1 / 8 0
59
? 增加一个变量
增加变量 xn+1 则有相应的 pn+1, cn+1 。那么，计算出
B-1pn+1 ?n+1 = cn+1 -∑ cri ari n+1
填入最优单纯形表，若 ?n+1 ≤ 0 则最优解不变；否则，
进一步用单纯形法求解。
例、前例增加 x6,p6 = ( 2,6,3 )T, c6 = 5 。计算得到
2、线性规划问题的进一步研究（ 2.3）
C
i
2 3 0 0 0 5
C
B
X
B
b X
1
X
2
X
3
X
4
X
5
X
6
2 X
1
4 1 0 0 1/4 0 1.5
0 X
5
4 0 0 -2 1/2 1 [2]
3 X
2
2 0 1 1/2 -1/8 0 0.2 5
σ
j
0 0 -1.5 -1/8 0 1.2 5
用单纯形法进一步求解，可得,x* = ( 1,1.5,0,0,0,2 )T f* = 16.5
60
? 增加一个约束
增加约束一个之后，应把最优解带入新的约束，若满足
则最优解不变，否则填入最优单纯形表作为新的一行，引入
1个新的非负变量（原约束若是小于等于形式可引入非负松
弛变量，否则引入非负人工变量），并通过矩阵行变换把对
应基变量的元素变为 0，进一步用单纯形法或对偶单纯形法
求解。
例、前例增加 3x1+ 2x2≤15，原最优解不满足这个约束。于是
2、线性规划问题的进一步研究（ 2.3）
C
i
2 3 0 0 0 5
C
B
X
B
b X
1
X
2
X
3
X
4
X
5
X
6
2 X
1
4 1 0 0 1/4 0 0
0 X
5
4 0 0 -2 1/2 1 0
3 X
2
2 0 1 1/2 -1/8 0 0
0 X
6
-1 0 0 -1 -1/ 2 0 1
σ
j
0 0 -1.5 -1/8 0 0
61
? A中元素发生变化 （只讨论 N 中某一列变化情况）
与增加变量 xn+1 的情况类似，假设 pj 变化 。那么，重新
计算出 B-1pj ?j = cj -∑ cri ari j
填入最优单纯形表，若 ?j ≤ 0 则最优解不变；否则，进
一步用单纯形法求解。
2、线性规划问题的进一步研究（ 2.3）
改变生产工艺,P
1
= ( 2, 5, 2 )
T
,C
1
= 4,
C
i
4 3 0 0 0
C
B
X
B
b X
1
X
2
X
3
X
4
X
5 θ
2 X
1
4 1,25 0 0 1/4 0
0 X
5
4 0,5 0 -2 1/2 1
3 X
2
2 0,375 1 1/2 -1/ 8 0
σ
j
0,375 0 -1,5 -1/ 8 0
用初等行变换把 X
1 对应的列向量变换为
( 1, 0, 0 )
T
,……
可得最优解,x* = ( 3.2,0.8,0,0,2.4 )T f* = 15.2
62
2、线性规划问题的进一步研究（ 2.3）
2,3 灵敏度分析 (内容，为重点 )
2.3.1 Ci 发生变化
2.3.2 Bj发生变化
2.3.3 增加一个变量
2.3.4 增加一个约束
2.3.5 A中元素发生变化
**习题,p 100 习题 2 2-4
返回目录
63
3,1 运输问题模型与性质
? 运输模型
例,某公司从两个产地 A1,A2将物品运往三个销地
B1,B2,B3，各产地的产量、各销地的销量和各
产地运往个销地每件物品的运费如下表所示，问：
应如何调运可使总运输费用最小？
B
1
B
2
B
3 产量
A
1
6 4 6 200
A
2
6 5 5 300
销量 150 150 200
3、运 输 问 题（ 3.1）
64
解,产销平衡问题,总产量 = 总销量
设 xij 为从产地 Ai运往销地 Bj的运输量，得到下列运输量表：
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
s.t,x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
xij ≥ 0 ( i = 1, 2； j = 1,2,3）
3、运 输 问 题（ 3.1） B
1 B 2 B 3 产量
A 1 x 11 x 12 x 13 200
A 2 x 21 x 22 x 23 300
销量 150 150 200
65
? 系数矩阵
? 1 1 1 0 0 0 ?
? 0 0 0 1 1 1 ?
? 1 0 0 1 0 0 ?
? 0 1 0 0 1 0 ?
? 0 0 1 0 0 1 ?
特点：
1、共有 m+n行，分别表示产地和销地； mn列分别表示各变量；
2、每列只有两个 1，其余为 0，分别表示只有一个产地和一个
销地被使用；
3、运 输 问 题（ 3.1）
66
? 设 xij 为从产地 Ai运往销地 Bj的运输量，得到下列一般运输
量问题的模型：
m n
Min f = ? ? cij xiji=1 j=i
n
s.t,? xij = si i = 1,2,…,mj=1
m
? xij = dj j = 1,2,…,ni=1
xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n)
?一般运输模型,产销平衡
A1,A2,…, Am 表示某物资的 m个产地； B1,B2,…, Bn
表示某物质的 n个销地； si 表示产地 Ai的产量； dj 表示销地 Bj
的销量； cij 表示把物资为从产地 Ai运往销地 Bj的单位运价。
3、运 输 问 题（ 3.1续）
67
3、运 输 问 题（ 3.1续）
? 变化：
1）有时目标函数求最大，如求利润最大或
营业额最大等；
2）当某些运输线路上的能力有限制时，模
型中可直接加入（等式或不等式）约束；
3）产销不平衡时，可加入虚设的产地（产
大于销时）或销地（销大于产时）。
68
3、运 输 问 题（ 3.1续）
? 求解思路 是
基本可行解 最优否 结束
否
换基
? 运输问题基变量的特点
* 运输问题的基变量共有 m + n -1 个,A的秩为 m + n -1。
* 运输问题的 m + n -1 个变量构成基变量的充分必要条件是
不含闭回路。
要弄清下列概念,闭回路、闭回路的顶点。
69
3,2 运输问题的表上作业法 ——本章重点
1、初始基本可行解的确定：
（ 1）西北角法,从西北角（左上角）格开始，在格内的右下
角标上 允许取得 的最大数。然后按行（列）标下一格的数。
若某行（列）的产量（销量）已满足，则把该行（列）的其
他格划去。如此进行下去，直至得到一个基本可行解。
（ 2）最小元素法,从运价最小的格开始，在格内的右下角标
上 允许取得 的最大数。然后按运价从小到大顺序填数。若某
行（列）的产量（销量）已满足，则把该行（列）的其他格
划去。如此进行下去，直至得到一个基本可行解。
注,应用西北角法和最小元素法，每次填完数，都只划去一行
或一列，只有最后一个元例外（同时划去一行和一列）。当
填上一个数后行、列同时饱和时，也应任意划去一行（列）
在保留的列（行）任意没被划去的格内标一个 0。
3、运 输 问 题（ 3.2）
70
*
例：某食品公司下属的 A
1
,A
2
,A
3
, 3 个厂生产方便食品，
要运输到 B
1
,B
2
,B
3
,B
4
, 4 个销售点，数据如下：
B
1
B
2
B
3
B
4 产量 a i
A
1
3 11 3 10 7
A
2
1 9 2 8 4
A
3
7 4 10 5 9
销量 b
j
3 6 5 6 20 （产销平衡）
求最优运输方案。
3、运 输 问 题（ 3.2）
1,确定初始基本可行解,（ 1 ）西北角法
B
1
B
2
B
3
B
4 产量 a i
A
1
3
3
11
4
3 10 7
A
2
1 9
2
2
2
8 4
A
3
7 4 10
3
5
6
9
销量 b
j
3 6 5 6 20
71
*
3、运 输 问 题（ 3.2）
（ 2 ）最小元素法
B
1
B
2
B
3
B
4
产量 a
i
A
1
3 11 3
4
10
3
7
A
2
1
3
9 2
1
8 4
A
3
7 4
6
10 5
3
9
销量 b
j
3 6 5 6 20
注：除最后一个元素 （相当于同时删去一行一列）外，每填一个
数都只删去一行或一列。若当前的行、列同时满足，可在当前的
行 （或列）的一个格子标 0,同时删去当前的列 （或行）。
72
2、最优性检验：
因为求最小，当所有检验数均大于等于 0时为最优解
（ 1）位势法求检验数：
? 位势,设对应基变量 xij 的 m + n - 1 个 ij,存在 ui,
vj 满足 ui + vj = cij, i = 1,…,m ; j = 1,…,n, 称这
些 ui,vj 为该基本可行解对应的位势。
由于有 m + n 个变量（ ui,vj ）,m + n - 1 个
方程（基变量个数），故有一个自由变量，位势不
唯一。
? 利用位势求检验数：
?ij = cij - ui - vj i = 1,…,m ; j = 1,…,n
3、运 输 问 题（ 3.2）
73
? 前例，位势法求检验数：
step 1 从任意基变量对应的 cij 开始，任取 ui 或 vj,然后利用公
式 cij = ui + vj 依次找出 m + n 个 ui,vj ； 从 c14 = 10 开始
step 2 计算非基变量的检验数 ?ij = cij - ui - vj ； 填入圆圈内
3、运 输 问 题（ 3.2）
v
j
-3 4 -2 5
u
i
B
1
B
2
B
3
B
4 产量 a i
5 A
1
3
1
11
2
3
4
10
3
7
4 A
2
1
3
9
1
2
*1
8
-1
4
0 A
3
7
10
4
6
10
12
5
3
9
销量 b
j
3 6 5 6 20
74
3、主元变换：
（ 1）选负检验数中最小者 ?rk，那么 xrk 为主元，作
为进基变量； （上页图中 x24 ）
（ 2）以为 xrk 起点找一条闭回路，除 xrk 外其余顶点
必须为基变量格； （上页图中 蓝色回路）
（ 3）为闭回路的每一个顶点标号,xrk 为 1，沿一个
方向依次给各顶点标号；
（ 4）求 ?=min{xij?xij对应闭回路上的偶数标号格 }=
xpq那么确定 xpq为出基变量,?为调整量；
（ 5）对闭回路的各奇标号顶点 xij + ?，对各偶标号顶
点 xij - ?，特别 xpq - ? = 0，变为非基变量；
3、运 输 问 题（ 3.2）
重复 2,3步，直到所有检验数均非负，得到最优解。
75
主元变换,由前面得到 ? = 1，于是
3、运 输 问 题（ 3.2）
v
j
-2 4 -2 5
u
i
B
1
B
2
B
3
B
4 产量 a i
5 A
1
3
0
11
2
3
（ 4+1 ） 5
10
（ 3 -1 ） 2
7
3 A
2
1
3
9
2
2
( 1-1 ) 1
8
（ 0+1 ） 1
4
0 A
3
7
9
4
6
10
12
5
3
9
销量 b
j
3 6 5 6 20
?ij ≥ 0，得到最优解 x13 = 5,x14 = 2,x21 = 3,
x24 = 1,x32 = 6,x34 = 3,其余 xij = 0 ;
最优费用,f* = 3*5+10*2+1*3+8*1+4*6+5*3 = 85
**习题,p 123 习题 3 3-1,3-2
76
3,3 产销不平衡的运输问题
1、产量大于销量 例,某公司从两个产地 A1,A2将物品
运往三个销地 B1,B2,B3，各产地的产量、各销地的销量
和各产地运往个销地每件物品的运费如下表所示，问：应
如何调运可使总运输费用最小？
解,增加一个虚设的销地运输费用为 0
B 1 B 2 B 3 产量
A 1 6 4 6 3 00
A 2 6 5 5 300
销量 150 150 200
B 1 B 2 B 3 B 4 产量
A 1 6 4 6 0 3 00
A 2 6 5 5 0 300
销量 150 150 200 100
3、运 输 问 题（ 3.3）
77
2、销量大于产量
例,某公司从两个产地 A1,A2将物品运往三个销地 B1,B2、
B3，各产地的产量、各销地的销量和各产地运往个销地每件
物品的运费如下表所示，问：应如何调运可使总运输费用最
小？
解,增加一个虚设的产地运输费用为 0
3、运 输 问 题（ 3.3）
B 1 B 2 B 3 产量
A 1 6 4 6 200
A 2 6 5 5 300
销量 250 200 200
B 1 B 2 B 3 产量
A 1 6 4 6 2 00
A 2 6 5 5 300
A 3 0 0 0 150
销量 250 200 200
78
? 下面给出一些例题，可作为建模的练习：
例,石家庄北方研究院有一、二、三，三个区。每年分别需
要用煤 3000,1000,2000吨，由河北临城、山西盂县两处
煤矿负责供应，价格、质量相同。供应能力分别为 1500、
4000吨，运价如下表。由于需大于供，经院研究决定一区
供应量可减少 0--200吨，二区必须满足需求量，三区供应
量不少于 1700吨，试求总费用为最低的调运方案。
一区 二区 三区 产量
山西盂县 1,6 5 1,7 0 1,7 5 4000
河北临城 1,6 0 1,6 5 1,7 0 1500
需要量 3000 1000 2000
3、运 输 问 题（例题）
79
解：
根据题意，作出产销平衡与运价表：
取 M 代表一个很大的正数，其作用是强迫相应
的 x31,x33,x34取值为 0。
3、运 输 问 题（例题） 一区 一区 二区 三区 三区 产量
山西盂县 1,6 5 1,6 5 1,70 1,75 1,75 4000
河北临城 1,6 0 1,6 0 1,6 5 1,70 1,70 1500
假想生产点 M 0 M M 0 500
需要量 2800 200 1000 1700 300
80
例,设有 A,B,C三个化肥厂供应 1,2,3,4四个
地区的农用化肥。假设效果相同，有关数据如下
表。试求总费用为最低的化肥调拨方案。
1 2 3 4 产量
A 1 6 1 3 22 17 50
B 14 1 3 19 15 60
C 19 20 23 --- 50
最低需要量 30 70 0 10
最高需要量 50 70 30 不限
3、运 输 问 题（例题）
81
解,根据题意，作出产销平衡与运价表：
最低要求必须满足，因此把相应的虚设产地运费取为 M,
而最高要求与最低要求的差允许按需要安排，因此把相应的
虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适
当取的数据，根据产销平衡要求确定 D的产量为 50。
3、运 输 问 题（例题）
1 ’ 1, 2 3 4 ’ 4, 产量
A 1 6 1 6 1 3 22 17 17 50
B 14 14 1 3 19 15 15 60
C 19 19 20 23 M M 50
D M 0 M 0 M 0 50
销量 30 20 70 30 10 50
82
例,某厂按合同规定须于当年每个季度末分别提供 10,15、
25,20台同一规格的柴油机。已知该厂各季度的生产能力
及生产每台柴油机的成本如下表。如果生产出来的柴油机
当季不交货，每台每积压一个季度需储存、维护等费用
0.15万元。试求在完成合同的情况下，使该厂全年生产总
费用为最小的决策方案。
生产能力 （台） 单位成本 （万元）
一季度 25 1 0,8
二季度 35 1 1,1
三季度 30 1 1,0
四季度 10 1 1,3
3、运 输 问 题（例题）
83
解,设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那末应满足：
交货,x11 = 10 生产,x11 + x12 + x13 + x14 ≤ 25
x12 + x22 = 15 x22 + x23 + x24 ≤ 35
x13 + x23 + x33 = 25 x33 + x34 ≤ 30
x14 + x24 + x34 + x44 = 20 x44 ≤ 10
把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j
季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维
护等费用看作运费。可构造下列产销平衡问题：
目标函数,Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22
+11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44
3、运 输 问 题（例题） 第一季度 第二季度 第三季度 第四季度 D 产量
第一季度 10.80 1 0.95 11,1 0 11.2 0 25
第二季度 M 11.10 1 1.25 11.40 0 35
第三季度 M M 11.00 11.15 0 30
第四季度 M M M 11.30 0 10
销量 10 15 25 20 30
84
例,光明仪器厂生产电脑绣花机是以产定销的。已知 1至 6月份各月的
生产能力、合同销量和单台电脑绣花机平均生产费用见下表
已知上年末库存 103台绣花机，如果当月生产出来的机器当月
不交货，则需要运到分厂库房，每台增加运输成本 0.1万元,每台机
器每月的平均仓储费、维护费为 0.2万元。在 7--8月份销售淡季，全
厂停产 1个月，因此在 6月份完成销售合同后还要留出库存 80台。加
班生产机器每台增加成本 1万元。问应如何安排 1--6月份的生产，可
使总的生产费用（包括运输、仓储、维护）最少？
正常生产能力 （台） 加班生产能力 （台） 销量 （台） 单台费用 （万元）
1 月份 60 10 104 15
2 月份 50 10 75 14
3 月份 90 20 1 1 5 1 3, 5
4 月份 100 40 160 13
5 月份 100 40 103 13
6 月份 80 40 70 1 3, 5
3、运 输 问 题（例题）
85
解,这个生产存储问题可化为运输问题来做。考虑：
各月生产与交货分别视为产地和销地
1） 1--6月份合计生产能力（包括上年末储存量）
为 743台，销量为 707台。设一假想销地销量为 36；
2）上年末库存 103台，只有仓储费和运输费，把
它列为的 0行；
3） 6月份的需求除 70台销量外，还要 80台库存，
其需求应为 70+80=150台；
4） 1--6表示 1--6月份正常生产情况,1’--6’表示
1--6月份加班生产情况。
续下页 产销平衡与运价表：
3、运 输 问 题（例题）
86
**习题,p 124 习题 3 3-3,3-4
1 月 2 月 3 月 4 月 5 月 6 月 虚销地 正常产量 加班产量
0 0.3 0.5 0.7 0.9 1.1 1.3 0 103
1 15 15, 3 15, 5 15, 7 15, 9 16, 1 0 60
1 ’ 16 16, 3 16, 5 16, 7 6.9 17, 1 0 10
2 M 14 14, 3 14, 5 14, 7 14, 9 0 50
2 ’ M 15 15, 3 15, 5 15, 7 15, 9 0 10
3 M M 13, 5 13, 8 14, 0 14, 2 0 90
3 ’ M M 14, 5 14, 8 15, 0 15, 2 0 20
4 M M M 13, 0 13, 3 13, 5 0 100
4 ’ M M M 14, 0 14, 3 14, 5 0 40
5 M M M M 13, 0 13, 3 0 100
5 ’ M M M M 14, 0 14, 3 0 40
6 M M M M M 13, 5 0 80
6 ’ M M M M M 14, 5 0 40
销量 104 75 1 15 160 103 150 36
3、运 输 问 题（例题）
返回目录
87
4,1 动态规划概念与模型
? 多阶段决策过程特点
要点：阶段，状态，决策，状态转移方程,k-后部子
过程
4、动 态 规 划 (4.1)
88
? 动态规划模型
nopt R( u
1,…,u n ) = ? rk ( xk,uk ) k=1
s.t,xk+1 = Tk ( xk,uk )
xk ?Xk ； uk ? Uk k = 1,…,n
?,表示对 n阶段效应进行综合（常用 ? 或 ? ）；
opt,最优化（ Max 或 Min）
R( u1,…,u n )：目标函数（最优值函数）
xk+1 = Tk ( xk,uk ),状态转移方程
Xk,状态可能集合
Uk：决策允许集合
4、动 态 规 划 (4.1)
89
? 建模过程
① 确定阶段与阶段变量；
② 明确状态变量与状态可能集合；
③ 明确决策变量与决策允许集合；
④ 明确状态转移方程；
⑤ 确定阶段效应和目标。
4、动 态 规 划 (4.1)
90
4,2 动态规划求解
? 求解动态规划模型：
从起始状态 x1 开始，找最优策略、最优路线和
最优目标值。
? 最优性原理
最优策略具有的基本性质是：无论初始状态和
初始决策如何，对于前面决策所确定的某一状态而
言，余下的决策序列必构成最优策略。
最优策略的任何一子策略也是相应初始状态的
最优策略；每个最优策略只能由最优子策略构成。
4、动 态 规 划 (4.2)
91
? 贝尔曼函数：（ k - 子过程的最优目标函数 )
nf
k(xk) = opt ? ri ( xi,ui ) k=1,…,ni=k
? 动态规划求解问题的一般过程：
① 逆序地求出条件最优目标函数值集合和条件最优决
策集合：
fn+1(xn+1) = 0 (边界条件 )
fk(xk) = opt {rk ( xk,uk ) + fk+1(xk+1) }u
k = n,…,1
4、动 态 规 划 (4.2)
92
② 顺序地求最优决策序列：
初始状态唯一,R* = f1(x1),u1* (x1)=u1’(x1)
若不唯一,R* = opt{f1(x1) ?x1?X1} = f1(x1*)，
u1* (x1*)=u1’(x1*)
xk+1 = Tk ( xk,uk )
uk+1* (xk+1*) = uk+1’(xk+1*) k=1,…,n
最优策略,{u1*(x1*),u2*(x2*),…,u n* (xn*)}
最优路线,{x1*,x2*,…,xn*,xn+1*)
4、动 态 规 划 (4.2)
93
1、动态规划的四大要素、一个方程 —— 重点
① 状态变量及其可能集合 xk ?Xk
② 决策变量及其允许集合 uk ? Uk
③ 状态转移方程 xk+1 = Tk ( xk,uk )
④ 阶段效应 rk ( xk,uk )
⑤ 动态规划基本方程
fn+1(xn+1) = 0 (边界条件 )
fk(xk) = opt {rk ( xk,uk ) + fk+1(xk+1) }u
k = n,…,1
4、动 态 规 划 (4.2)
94
4,3 动态规划应用举例
例：一个线路网络图，从 A到 E要修建一条石油管道，必须 在
B,C,D处设立加压站。各边上的数为长度，现需要找一
条路使总长度最短。
4、动 态 规 划 (4.3)
95
解,可分成 4个阶段,A到 B,B到 C,C到 D,D到 E ；
每个阶段 k 的起点称为状态 S k ；
从 k 阶段的起点出发可以做一选择，即决定到下一阶
段的哪个节点，称为决策 X k ；
可见,S k+1 是由 S k 和 X k 所决定的。
那麽，从 A出发经过 4个阶段,A到 B,B到 C,C到 D,D
到 E，逐次作出决策，构成从 A到 E 的一条路线，记为 u 。
即，
u = S1 X1 S2 X2 S3 X3 S4 X4 S5 其中 S1 = A, S5 = E
记 d 为两个相邻节点之间的长度，如 d（ A,B 3） = 3 。
① 记 f k（ S k）为从 S k 到 E 的最短长度，称为从 S k 到 E
的距离。
那么,f 1（ A）是从 A到 E 的最短距离，即最优策略的值。
4、动 态 规 划 (4.3续 )
96
② 最短路问题的特点：如果从 A 到 E 的最优策
略经过某节点，那么这个策略的从该节点到 E
的一段，必定是该节点到 E的所有线路中 S k 最
短的一条，即这一段的长度为 f k（ S k）。
（ 1）逆序法：从 E到 A
（ 2）顺序法：对节点 S k,从 A到 S k 所有
线路中，最短的一条的长度记为 φ k（ S k），
例如 φ 1（ A） = 0,称为问题的边界条件。
4、动 态 规 划 (4.3续 )
动态规划文本
97
学习方法建议：
第一步 先看问题，充分理解问题的条件、情
况及求解目标；
第二步 结合前面讲到的理论和解题过程，考
虑如何着手进行求解该问题的工作。分析针
对该动态规划问题的“四大要素、一个方
程” ——这一步在开始时，会感到困难，但
是一定要下决心去思考，在思考过程中深入
理解前文讲到的概念和理论；
4、动 态 规 划 (4.3续 )
98
第三步 动手把求解思路整理出来，或者说，
把该问题作为习题独立的来做；
第四步 把自己的求解放到一边，看书中的求
解方法，要充分理解教材中的论述；
第五步 对照自己的求解，分析成败。
**习题,p175--177 4 -1,4 -2,4 -3,4 -6；
**练习,4 -4,4 -5,4 -7
4、动 态 规 划 (4.3续 )
返回目录
99
5,1 图的基本概念 —— 本节主要是概念
? 图 G（ V,E）：
V是顶点集合（ vi,i=1…6 ）
E是边的集合（ ej,j=1…9 ）
顶点数 p (G) = 6
边数 q (G) = 9
对于边 e3 =[ v1,v4 ],v1,v4是
e3的端点 e3 是 v1,v4的关联边
5、图 与 网 络 分 析（ 5.1）
?图的其他概念,
相邻点，相邻边，
环，多重边（平行边），
多重图，简单图
100
端点的次 d(v),点 v 作为边端点的次数；
奇点,d(v)=奇数； 偶点,d(v)=偶数；
悬挂点,d(v)=1； 悬挂边,与悬挂点连接的边，
孤立点,d(v)=0； 空图, E = ?，无边图 。
定理一,所有顶点次数之和等于所有边数
的 2倍。
定理二,在任一图中，奇点的个数必为偶
数。
5、图 与 网 络 分 析（ 5.1续）
101
? 图的连通性：
链,由两两相邻的点及其相关联的边构成的点边序列；如：
v0,e1,v1,e2,v2,e3,v3,…,vn-1,en,vn ；
v0,vn分别为链的 起点 和 终点
简单链,链中所含的边均不相同；
初等链,链中所含的点均不相同，也称 通路 ；
回路,若 v0 ≠ vn 分称该链为开链，否则称为 闭链 或 回路 ；
圈,出起点和终点外链中所含的点均不相同的闭链；
连通图, 图中任意两点之间均至少有一条通路，否则称作
不连通图。
5、图 与 网 络 分 析（ 5.1续）
102
? 子图 设 G1 = [ V1,E1 ],G2 = [ V2,E2 ]
子图定义,如果 V2 ? V1,E2 ? E1 称 G2 是 G1 的子图；
真子图,如果 V2 ? V1,E2 ? E1 称 G2 是 G1 的真子图；
部分图,如果 V2 = V1,E2 ? E1 称 G2 是 G1 的部分图；
导出子图,如果 V2 ? V1,E2 = {[ vi,vj ] ∣ vi,vj ? V2 }，称 G2
是 G1 中由 V2 导出 的导出子图。
5、图 与 网 络 分 析（ 5.1续）
103
? 有向图,关联边有方向
弧,有向图的边 a = ( u,v ),起点 u,终点 v；
路,若有从 u 到 v 不考虑方向的链，且各方向一致，
则称之为从 u 到 v 的 路；
初等路,各顶点都不相同的路；
初等回路,u = v 的初等路
连通图,若不考虑方向
是无向连通图
强连通图,任两点有路
5、图 与 网 络 分 析（ 5.1续）
104
? 树,无圈连通图；无圈图又称为树林，子连通图是树
定理,六种等价描述。 设：边数 q,顶点数 p,
1、无圈连通图；
2、边数 q = 顶点数 p - 1；
3、连通，且 q = p - 1；
4、无圈，但加一边则得到唯一的圈；
5、连通，但若去一边则图不连通；
6、每对顶点之间有且仅有一条链。
部分树,若一个图 G 的部分图 T 是树，则称 T 为部分树，
又称生成树
余树,G 中去掉 T 所有的边后得到的部分树称为 G 中 T 的
余树，余树不一定是树。
5、图 与 网 络 分 析（ 5.1续）
105
5、图 与 网 络 分 析（ 5.2）
5,2 网络最短路问题
网络,规定起点、中间点和终点的赋权图；
有向网络,网络中每个边都是有向边；
无向网络,网络中每个边都是无向边；
混合网络,网络中既有有向边，又有无向边；
网络最短路线问题,寻找网络中从起点 v1 到终
点 vn 的最短路线。
Min L(?) = ? lij ?为从 v1 到 vn 的通路；
lij??
其中,lij为从 vi 到 vj 的一步距离。
106
? 结合例题学习、掌握求最短路的狄克斯拉、海斯和
福德三个方法：
1、狄克斯拉方法：适用于满足所有权系数大于等
于 0（ lij≥0）的网络最短路问题，能求出起点 v1 到
所有其它点 vj 的最短距离；
2、海斯方法：基本思想是在最短路线上任意两点
间路线也是最短路线。利用 vi 到 vj 的一步距离求
出 vi 到 vj 的两步距离再求出 vi 到 vj 的四步距
离 …… 经有限次迭代可求出 vi 到 vj 的最短距离；
3、福德方法：适用于有负权系数，但无负回路的
有向或无向网络的最短路问题，能求出起点 v1 到所
有其它点 vj 的最短距离。
**习题,p218--219 习题 5 5-2
5、图 与 网 络 分 析（ 5.2续）
107
5,3 最短树问题（最小树问题）（ p198--201 ）
? 依据树的特点（即无圈和连通），按照最短的要求构造求最短
树的方法。
? 结合例题学习、掌握求最小树的破圈法和生长法两个方法：
1、破圈法
① 在网络图中寻找一个圈。若不存在圈，则已经得到最
短树或网络不存在最短树；
② 去掉该圈中权数最大的边；
反复重复 ① ② 两步，直到求出最短树。
2、生长法
从网络图中任意节点开始寻找与该节点关联的权数最小的
边，得到另一节点后，再从这个新节点开始寻找与该节点关联
的权数最小的另一边 …… 。注意寻找过程中，节点不得重复，
即在找最小权数边时不考虑已选过的边。反复进行，直到得到
最短树或证明网络不存在最短树。
**习题,p218--219 习题 5 5-1,5-3
5、图 与 网 络 分 析（ 5.3）
108
5,4 最大流问题（ p201--212）
? 网络最大流问题
* 在一定条件下，要求流过网络的物流、能量流或信息流等流量为最大的
问题。
* 规定,一个起点和一个终点；有向网络；各弧上有权表示允许的最大
流量；除起点和重点外，各节点流入量总和等于流出量总和。
? 最大流最小割定理（在理解割集和最小割集概念的基础上掌握此定理）
最大流最小割定理：流过网络的最大流量等于最小割集的容量。
? 结合例题学习、掌握求最大流的福德 —富克逊方法
在理解算法原理的基础上，掌握算法思想及过程。通过例题掌握此方法。
**习题,p219 习题 5 5-4
5、图 与 网 络 分 析（ 5.4）
109
5,5 最小费用 —— 最大流问题（ p212--218）
? 最小费用 ——最大流问题
本节讨论的问题是在 5.4节问题的基础上增加关于使费用最小的目标。
? 对偶法原理
先用 5.4节讨论的方法求出网络的最大流量，然后在原始的网络中用 5.2.4的福
德算法找出从起点 vs 到终点 vt 的最短路线 ——最短增广链，在该增广链上找出
最大调整量，并调整流量得到一个可行流，则此可行流的费用最小。如果此时
流量等于最大流量，那么它就是最小费用最大流；否则应继续调整。
? 结合例题学习、掌握求最小费用 ——最大流问题对偶法。
**习题,p 220 习题 5 5-5
5、图 与 网 络 分 析（ 5.5）
返回目录
110
6、排 队 论（ 6.1）
6,1 概述
?排队系统的特征,排队系统又称随机
服务系统
① 有请求服务的人或物； ② 有为顾
客服务的人或物； ③ 顾客到达时间与接
受服务时间是随机的 。
?结构：
排队的过程可表示为,排队系统
顾客到达 排队 服务机构服务 顾客离去
111
排队系统有三个组成部分
? 输入过程：
顾客总体数 （来源无限或有限）
顾客到来方式 （单个或成批）
顾客流的概率分布 （泊松流、定长、爱尔朗分布等）
? 服务规则：
损失制 （服务台满时顾客立即离去）
等待制 （先到先服务，后到先服务，随机服务，优先权）
混合制 （队长有限制，排队时间有限制）
? 服务机构：
服务台数量及布置形式 （单 /多服务台，串、并列或结合）
某一时刻接受服务的顾客数 （每服务台每次服务顾客数）
服务时间分布 （负指数、定长、爱尔朗分布等）
6、排 队 论（ 6.1续）
112
? 排队论研究的内容和目的 —— 提出排队论关
心的问题和需要计算的一些量
研究内容：
数量指标：队长、等待时间和逗留时间
的分布、忙期和闲期的分布、服务设备利用
率、顾客损失率等；
排队系统优化问题：系统最优设计问题
和动态控制问题。
研究目的,通过对排队系统中概率规律的研究，
使系统达到最优设计和最优控制，以最小费
用实现系统的最大效益。
6、排 队 论（ 6.1续）
113
6、排 队 论 （ 6.1续）
? 排队模型的分类及 排队系统的常用符号
肯道尔（ D.G.Kendall）分类,A / B / C / D / E
其中,A 顾客到达的分布；
B 服务时间的分布；
C 服务台数；
D 系统容量；
E 顾客源的个体数。
表示分布的符号,M----指数分布或泊松输入； D----
定长分布； Ek----k阶爱尔朗分布； GI----一般独立
随机分布； G----一般随机分布。
114
? 系统的运行指标 —— 提出一般常需要计算的一些量
最常用的量,单位时间顾客平均到达数 ?
单位时间平均服务顾客数 ?
（ 1）、系统中无顾客的概率 P0
（ 2）、系统中平均排队的顾客数 Lq
（ 3）、系统中的平均顾客数 Ls
（ 4）、系统中顾客平均的排队等待时间 Wq
（ 5）、系统中顾客的平均逗留时间 Ws
（ 6）、系统中恰好有 n 个顾客的概率 Pn
（ 7）,有效到达率 ?e
（ 8）、有效离去率 ? e
此外还有：忙、空的概率等 6 个量
6、排 队 论 （ 6.1续）
115
6.2 泊松输入 — 负指数服务的排队系统
? 对于泊松输入 - 负指数分布服务的排队系统
的一般决策过程：
① 根据已知条件绘制状态转移速度图
② 依据状态转移速度图写出各稳态概率之间
的关系
③ 求出 P0 及 Pn
④ 计算各项数量运行指标
⑤ 用系统运行指标构造目标函数，对系统进
行优化
6、排 队 论（ 6.2）
116
? 典型分布 —— 泊松分布及其性质，负指数分布
泊松分布 (平稳状态） ? > 0 为单位时间平均到
达的顾客数：
P { I = n } = ?n e-? / n! (n = 0,1,2,……)
负指数分布 ? 为平均服务率，即单位时间服
务的顾客数
P（服务时间 ≤ t ) = 1- e-? t t ≥0
? 系统状态概率分布及状态转移速度图 —— 基
本的概率分布推导
6、排 队 论（ 6.2）
117
? 系统的运行指标：
（ 1）、系统中顾客数的期望值 Ls
（ 2）、系统中排队等待顾客数的期望值 Lq
（ 3）、系统中顾客平均的排队等待时间 Wq
（ 4）、系统中顾客的平均逗留时间 Ws
（ 5）,有效到达率 ?e
6、排 队 论（ 6.2续）
118
6、排 队 论（ 6.2续）
（ 6）、系统中 Ls,Lq,Wq,Ws,?e 之间
的关系
Ls = ? n pn,Lq = ? ( n - c ) pn，
Ws = Ls / ?e,Wq = Lq / ?e，
Ws = Wq + 1 / ?,
?e = ? ?n pn = ? ? n pn,
Ls = Lq + ?e / ? 。
119
6、排 队 论 （ 6.3）
*在 6.1,6.2节的基础上，结合例题学习、掌握下列各系统有关问题的计算
6,3 M/M/1无限源系统（ p239--246 ）
? M/M/1/N系统,M/M/1等待制系统,M/M/l损失制系统，无限源模型特点
6,4 M/M/C无限源系统（ p246--253 ）
? M/M/C/N系统,M/M/C等待制系统,M/M/C损失制系统
6,5 客源有限的排队系统（ p253--258 ）
? M/M/1/m/m系统,M/M/C/m/m系统
6,6 排队系统应用举例（ p258--264 ）
? 本段的各例题要在充分理解的基础上学习，然后独立去完成课后练习作业。
6,7 本章小结（ p264 ）
? 学习本节内容，要认真体会第 6章的重点和难点。
? 小结也需要学习，自己应仿照此在总复习中作各章的小结。
**习题,p 265--266 习题 6 6-1,6-2,6-3,6-4,6-5,6-6,6-7,6-8
返回目录
120
教 学 日 历
周次 学习内容 课内学时 自学学时 作业 （ 教材 ）
1 绪论 2
1 线性规划
1 1,1 线性规划的概念 2 4 习题 1 1-1,1-2
1,1,1线性规划问题的导出
1,1,2线性胡划问题的概念和模型
1,1,3线性规划问题的标准型
1,1,4线性规划问题的标准化
2 1,2线性规划问题解的概念及性质 4 8 习题 1 1-3,1-4
1,2,1解的概念
1,2,2图解法 (解的几何表示 )
1,2,3基本可行解的几何意义
1,2,4线性规划求解思路 (单纯形法思想 )
1,2,5线性规划解的性质的证明
3 1,3单纯形法 6 12 习题 1 1-5,1-6
1,3,1单纯形法引例
1,3,2单纯形法的一般描述
121
周次 学习内容 课内学时 自学学时 作业（教材）
1,3,3表格单纯形法
1,3,4一般线性规划问题的处理
1,3,5单纯形法的矩阵描述
1,3,6单纯形迭代过程中的几点注意事项
4 1,4线性规划应用 6 12 习题 1 1-7,1-8
1,4,1线性规划建模 1-9
1,4,2生产计划问题
1,4,3合理下料问题
1,4,4合理配料问题
1,4,5运输问题
1,4,6最大流量问题
2 线性规划问题的进一步研究
5 2,1对偶原理 2 4 习题 2 2-1
2,1,1对偶线性规划问题的导出
2,1,2对偶问题的定义
2,1,3对偶定理
教 学 日 历（续）
122
周次 学习内容 课内学时 自学学时 作业（教材）
2,1,4对偶最优解的经济含义 ——影子价格
2,1,5由最优单纯形表求对偶问题最优解
5 2,2对偶单纯形法 2 4 习题 2 2-2,2-3
6 2,3灵敏度分析 4 8 习题 2 2-4
2,3,1价值系数 C发生改变
2,3,2右端常数 b发生改变
2,3,3增加一个变量
2,3,4增加一个约束
2,3,5 A中的元素发生改变
3 运输问题
7 3,1运输问题模型与性质 2 4 习题 3 3-1,3-2
3,1,1约束方程组的系数矩阵具有特殊的结构 （ 3.1,3.2两节
3,1,2运输问题的基变量共有 m+n-1个 的习题 ）
3,1,3 m+n-1个变量构成基变量的充要条件是不含闭回路
7 3,2运输问题的求解 (表上作业法 ) 2 4
3,2,1初始基本可行解的确定
教 学 日 历（续）
123
周次 学习内容 课内学时 自学学时 作业（教材）
3,2,2最优性检验
3,2,3主元变换
8 3,3产销不平衡的运输问题 2 4 习题 3 3-3,3-4
3,3,1产量大于销量的情况
3,3,2销量大于产量的情况
4 动态规划
8 4,1动态规划概念与模型 2 4
4,1,1引言
4,1,2多段决策过程
4,1,3动态规划模型
4,1,4动态规划建模
9 4,2动态规划求解 2 4
4,2,1解的概念
4,2,2最优性原理
4,2,3贝尔曼函数
4,2,4动态规划的基本方程
教 学 日 历（续）
124
周次 学习内容 课内学时 自学学时 作业（教材）
4,2,5动态规划方法基本原理
4,2,6动态规划问题求解的一般步骤
4,2,7动态规划四大要素、一个方程
9 4,3动态规划应用举例 10 15 习题 4 4-1,4-2
4,3,1工程路线问题 4-3,4-4
10 4,3,2资源分配问题 4-5,4-6
4,3,3串联系统可靠性问题 4-7
4,3,4生产 —库存问题
4,3,5二维背包问题
4,3,6设备更新问题
5．图与网络分析
11 5,1图的基本概念 2 4
5,1,1引言
5,1,2图的概念
5,1,3图的连通
5,1,4子图
5,1,5有向图
教 学 日 历（续）
125
周次 学习内容 课内学时 自学学时 作业（教材）
5,1,6树
11 5,2网络最短路线问题 4 8 习题 5 5-2,5-3
5,2,1引言
5,2,2最短路线问题的狄克斯拉法
5,2,3最短路线问题的海斯算法
5,2,4最短路线问题的福德算法
12 5,3最短树问题 2 4 习题 5 5-1
5,3,1引言
5,3,2破圈法
5,3,3生长法
12 5,4最大流问题 2 4 习题 5 5-4
5,4,1引言
5,4,2最大流最小割集定理
5,4,3福德 —富克逊算法
12 5,5最小费用 —最大流问题 2 4 习题 5 5-5
5,5,1引言
5,5,2对偶法原理和步骤
教 学 日 历（续）
126
周次 学习内容 课内学时 自学学时 作业（教材）
5,5,3对偶法示例
6 排队论
13 6,1概述 2 4
6,1,1引言
6,1,2排队系统的特征
6,1,3排队系统的结构
6,1,4排队论研究的内容和目的
6,1,5排队模型的分类
6,1,6排队系统的常用符号
13 6,2泊松输入 —负指数服务的系统 3 6
6,2,1典型分布
6,2,2系统状态概率分布
6,2,3状态转移速度图
6,2,4系统的运行指标
13 6,3 M/M/1无限源系统 2 4
6,3,1 M/M/1/N系统
教 学 日 历（续）
127
周次 学习内容 课内学时 自学学时 作业（教材）
6,3,2 M/M/1等待制系统
6,3,3 M/M/l损失制系统
6,3,4 M/M/1无限源模型特点
14 6,4 M/M/C无限源系统 2 4
6,4,1 M/M/C/N系统
6,4,2 M/M/C等待制系统
6,4,3 M/M/C损失制系统
14 6,5客源有限的排队系统 2 4
6,5,1 M/M/1/m/m系统
6,5,2 M/M/C/m/m系统
14 6,6排队系统应用举例 1 2 习题 6 6-1~6-8
（第 6章的习题可在充分理解概念的基础上集中练习）
6,7本章小结
教 学 日 历（续）
返回目录
