OR3 1
OPERATIONS RESEARCH
运筹学 Ⅲ
—— 如何把事情做得最好郝英奇
OR3 2
第六章 整数规划本章要求
理解整数规划的含义
掌握分枝定界法的思想和方法
掌握 0-1变量的含义和用法
掌握指派问题的算法
微机求解
OR3 3
6.1 整数规划问题的提出
决策问题中经常有整数要求，如人数、
件数、机器台数、货物箱数 …… 如何解决？四舍五入不行，枚举法太慢
问题分类,纯整数规划,混合整数规划、
0-1整数规划
专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法
OR3 4
问题举例
某集装箱运输公司，箱型标准体积 24m3，重量
13T,现有两种货物可以装运，甲货物体积 5m3、
重量 2T、每件利润 2000元；乙货物体积 4m3、
重量 5T、每件利润 1000元，如何装运获利最多？
maxZ=2000x1+1000x2
5x1+4x2≤24
2x1+5x2 ≤13
x1.x2 ≥0且为整数
解此 LP问题，得,X1=4.8,X2=0
显然不是可行解
OR3 5
整数规划图解法
x2
x11 2 3 4 5 6 7
2
3
1 B
A
OR3 6
图解法的启示
A（ 4.8,0）点是 LP问题的可行解，不是 IP问题的可行解,B（ 4,1）才是 IP的最优解
纯整数规划的可行解就是可行域中的整数点
非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化
IP问题的最优解不优于 LP问题的最优解
OR3 7
6.2 分枝定界法
思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解
例 1,maxZ=2000x1+1000x2
5x1+4x2≤24
2x1+5x2 ≤13
x1.x2 ≥0且为整数解：先不考虑整数要求，解相应的 LP问题，得：
x1=4.8 x2=0 Z=9600 不是可行解
Z=9600是 IP问题的上界，记为,Z=9600
OR3 8
分枝定界法（续）
X1=4.8不符合要求，切掉 4— 5之间的可行域，
可行域变成两块，即原有约束条件再分别附加约束条件 x1 ≤4和 x1 ≥5
原问题分解为两个
maxZ=2000x1+1000x2 maxZ=2000x1+1000x2
5x1+4x2≤24 5x1+4x2≤24
2x1+5x2 ≤13 ( IP1 ) 2x1+5x2 ≤13 (IP2)
x1 ≤4 x1 ≥5
x1.x2 ≥0且为整数 x1.x2 ≥0且为整数
OR3 9
分枝定界法（续）
不考虑整数要求，解相应 LP问题。
解 IP1得,x1=4,x2=1 z=9000
解 IP2得：无可行解此时可以断定 IP问题的下界为 9000，记为 Z=9000
由于目前的分枝末梢最大值是 9000，故
IP问题的上界便是 9000。由于 Z=Z，此时已得 IP问题的最优解，即
x1=4,x2=1,Z=9000
OR3 10
分枝定界法的解题步骤
1、不考虑整数约束，解相应 LP问题
2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步
3、任取一个非整数变量 xi=bi，构造两个新的约束条件,xi ≤[bi],xi ≥ [bi]+1,分别加入到上一个 LP问题，形成两个新的分枝问题。
4、不考虑整数要求，解分枝问题。若整数解的 Z值 >所有分枝末梢的 Z值，则得最优解。否则,取 Z值最大的非整数解，
继续分解,Go to 3 （例题 2讲解）
OR3 11
6.3 0— 1规划问题
某些特殊问题，只做是非选择，故变量设置简化为 0或 1,1代表选择,0代表不选择。
例 4,600万元投资 5个项目，求利润最大的方案？
项目 投资额 项目收益 约束条件
210 160中选 1项
300 210之中选 1项
150 60 选?必先选?
130 80
260 180
OR3 12
求解 0— 1规划的隐枚举法
例 4解：
0 当项目未被选中
1 当项目被选中
max Z=160x1+210x2+60x3+80x4+180x5
210x1+300x2+150x3+130x4+260x5 ≤600?
X1+x2+x3=1?
X3+x4=1?
x5 ≤ x1?
Xj=0或 1 j=1,2,…,5
增加过滤条件,160x1+210x2+60x3+80x4+180x5 ≥ 240?
建模：设 xj=
OR3 13
用隐枚举法解例 4：
(x1,x2,x3,x4,x5） Z值
（ 1,0,0,1,0） 240
（ 1,1,1,1,1）? X
（ 1,1,1,1,0）? X
（ 1,1,1,0,1）? X
（ 1,1,1,0,0）? X
（ 1,1,0,1,1）? X
（ 1,1,0,1,0）? X
（ 1,1,0,0,1）? X
（ 1,1,0,0,0） X
（ 1,0,1,1,1）? X
（ 1,0,1,1,0） X
（ 1,0,0,1,1） 420
………,.
OR3 14
6.4 指派问题
例 8 甲乙丙丁四个人,A,B,D四项任务，不同的人做不同的工作效率不同，
如何指派不同的人去做不同的工作使效率最高？
任务人 时间 A B C D
甲乙丙丁
4 10 7 5
2 7 6 3
3 3 4 4
4 6 6 3
数模,
minZ=ΣΣcijxij
Σxij=1 i=1,…,n
Σxij=1 j=1,…,n
Xij=0或 1
OR3 15
指派问题解法 — 匈牙利法
解：类似运输问题的最小元素法
第一步 造 0—— 各行各列减其最小元素
4 10 7 5 -4 0 6 3 1? 6 2 1?
Cij= 2 7 6 3 -2? 0 5 4 1? 0 5 3 1?
3 3 4 4 -3 0 0 1 1 0? 0 1
4 6 6 3 -3 1 3 3 0 1 3 2?
-1?
第二步 圈 0—— 寻找不同行不同列的 0元素，
圈之。 所在行和列其它 0元素划掉
第三步 打?—— 无?的行打?，打?行上 0列打
,打?列上?行打?，打?行上 0列打? …
OR3 16
指派问题解法 — 匈牙利法（续）
第四步 划线 —— 无?行、打?列划线
第五步 造 0—— 直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的 0元素,Go to 2
0 6 2 1 -1? 5 1 0? 0 4? 0
Cij= 0 5 3 1 -1? 0 4 2 0 3 1 0
0 0 0 1 1? 0 1 2? 0 2
1 3 2 0 2 3 2 2 2 1?
+1
最优解,x13=1,x21=1,x32=1,x44=1 Z=15
OR3 17
相关问题：
非标准型的转化
（ 1） maxZ= ΣΣcijxij?minZ’= ΣΣ(-cij)xij
minZ’’= ΣΣ(M-cij)xij= ΣΣbijxij
M是足够大的常数,新问题的最优解就是原问题的最优解
（ 2）整数规划的计算机求解
OR3 18
整数规划习题课
P222—— 6.11
A B C B D
1 1
2 1
3 1
4 1
5 1
OR3 19
第七章 动态规划（略）
OR3 20
第八章 图与网络分析
引论 哥尼斯堡七桥问题
A
B
DC
A
B
C D
简捷表示事物之间的本质联系，归纳事物之间的一般规律
OR3 21
引论 图的用处
A,B,C,D,E 某公司的五支球队进行循环赛 组织机构设置图
A
B C
D E
总公司 分公司 工厂或办事处
OR3 22
8.1 图的基本概念
图是由 点 和 线 构成的。
点的集合 V表示,V={vi}
不带箭头的连线叫做 边 (edge)，边的集合记为 E= { ej },一条边可以用两点
[ vi,vj ]表示,ej= [ vi,vj ].
带箭头的连线叫做 弧 (arc),弧的集合记为
A,A= { ak },一条弧也是用两点表示，
ak= [ vi,vj ],弧有方向,vi为始点,vj为终点
OR3 23
图的基本概念 (续 )
由点和边组成的图叫做 无向图,记为 G=（ V,E）
由点和弧组成的图叫做 有向图,记为 D=（ V,A）
例 1.
v1 v2
v3v4
v1
v2
v3
v4
v5
v6
v7
e1
e2
e3 e4e5
e6
e7
a1
a2
a8
a4a
3
a5
a6 a9
a7
a10
a11
无向图：点集、边集 有向图：点集、弧集
OR3 24
图的基本概念 (续 )
以点 u为端点的边的条数，叫做点 u的 次次为 1的点叫做 悬挂点 ；次为 0的点叫做孤立点 ；次为奇数则称 奇点 ；次为偶数则称 偶点。
点弧交替序列称为 链 ；闭合的链称为 圈
首尾相接的链称为 路 ；闭合的路称 回路
任意两点之间都有边相连，称为 连通图
OR3 25
8.2 树
无圈的连通图称之为 树
赋权无向图 G=（ V,E）的最小基干称为最小支撑树
赋权有向图 D=（ V,A）,从始点到终点的权值最小的路称为 最短路
OR3 26
8.3 最短路问题
例 6 某交通网络如下图，求 v1到 v8的最短路线
解：用双标号法
v1
v2
v4
v3
v5
v6
v7
v863
1
2
2
1
6
10
4
3
10
4
4
6
v1
V2(v3,5)
V3(v1,3)
V4(v1,1)
V5(v2,6)
V6(v5,10)
V7(v5,9)
V8(v5,12)6
3
1
2
2
1
6
10
4 10
4
3
6
4
V2(v1,6）
OR3 27
8.4 最大流问题
引例：如下输水网络，南水北调工程，
从 vs到 vt送水，弧旁数字前者为管道容量，
后者为现行流量，如何调整输水最多？
vs vt
v2
v1
v4
v3
(3,3)
(5,1)
(1,1)
(4,3)
(1,1)
(2,2)
(3,0)
(2,1)
(5,3)
OR3 28
最大流问题的相关概念
网络：给定了弧的容量 C（ vi,vj）的有向图 D=
（ V,A,C）叫做一个 网络 。
可行流：各点流入量 =流出量，且 vs的流出量
=vt的流入量，这样的流称之为 可行流
截集：分离始点 vs和终点 vt的弧的集合，叫做截集
截量：截集的容量叫做 截量
增广链：一条从到的链，前向弧上可增加，后向弧上可减少，则称此链为 增广链
OR3 29
求最大流的方法
方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。
寻找增广链的标号法：先给 vs标号（ 0，
+∞）,而后依次审查各条弧（ vi,vj）：对前向弧，饱和否？不饱和，给 vj点标号
（ vi,l(vj));对后向弧，可否减少？可，给
vj标号（ -vi,l(vj) ）,直到给 vt标上号，就得到了增广链。
OR3 30
解水网最大流问题
.
vs
V2
(0,+∞)
V1
(3,3)
(5,1)
(1,1)
(4,3)
(1,1)
(2,2)
(3,0)
(5,3)
(2,1)
V4
V3
Vt
(vs,4)
(-v1,1)
(-v2,1)
(v3,1)
(v2,1)
OR3 31
此题最大流图
沿增广链进行调整，前向弧增加 l(vj)，后向弧减少 l(vj)
vs
V2
V1 V3
V4
Vt
(3,3)
(5,2)
(4,3)
(1,0) (1,0)
(2,2)
(3,0)
(5,3)
(2,2)
(0,+∞)
(vs,3)
OR3 32
习题,p312－ 8.4，求最大流
给出任意可行流
找到一条增广链
调整可行流 注,’ ＝ 1,#＝ 1,$＝ 2，
*=1
vs
v1 v2
v3
v4 v5
vt
（ 4,3） ’
（ 10,4） $*
（ 3,2） #
（ 1,1）
（ 3,2） ’
（ 3,2） *
（ 4,2） $
（ 5,3） #*
（ 4,3） ’ （ 2,
2
）
（ 7,6） ’
（ 8,3） #$*
(0,+∞)
(vs,3)
OR3 33
第九章 网络计划
9.1基本概念
～是用网络分析的方法编制的计划
杜邦公司 — 关键路线法 CPM 确定型
美国海军武器局 — 计划评审技术 PERT
网络图（有向赋权图）的构成
结点，也称事项，一道工序的开始或结束
工序（弧），相对独立的活动，消耗资源
虚工序，只表示衔接关系，不消耗资源
工序时间（权），完成工序的时间消耗
OR3 34
9.2.网络规则
1、避免循环、不留缺口
2、一一对应：一道工序用两个事项表示
3,从左向右依次展开例,工 序 A B C D E F G H I
紧前工序 -- -- A B B C,D C,D E,F G
工序时间 4 6 6 7 5 9 7 4 8
A,4
B,6
C,6
D,7
E,5
G,7
F,9
H,4
I,8
OR3 35
9.3 关键路线法－－ CPM
9.3.1时间参数运算 什么是关键路线？
1、作业时间 t（ i,j），经验数据、统计数据
2、事项最早时间 TE(j)＝ max{TE(i)+ t（ i,j） }
到齐上课，最后到者决定最早开课时间
3、事项最迟时间 TL(i)＝ min{TL(j)- t（ i,j） }
保证 12点吃饭，路最远者决定最迟下课时间
4、工序最早可能开工时间
TES(i,j)＝ TE(i) = max{TES(h,i)+ t（ h,i ） }
5、工序最早可能完工时间
TEF(i,j)＝ TES(i,j)+ t（ i,j）
h
i
j
OR3 36
.6、工序最迟必须开工时间
TLS（ i,j)＝ TL(j)－ t（ i,j)＝ min{TLs(j,k)- t（ i,j） }
7、工序最迟必须完工时间
TLF（ i,j)＝ TL(j)＝ TLS（ i,j)+ t（ i,j)
8、工序总时差：在不影响其紧后工序 最迟必须开工时间的前提下，本工序可以推迟的时间
R（ i,j）＝ TLS(i,j)－ TES(i,j) ＝ TLF(i,j)－ TEF(i,j)
＝ min{TLS(j,k) } – TEF（ i,j）
9、工序单时差：在不影响其紧后工序 最早可能开工时间的前提下，本工序可以推迟的时间
r （ i,j）＝ min{TES(j,k) } – TEF（ i,j）
K
k
k
OR3 37
9.3.2时间参数图解
.
解上例：
计算事项
时间参数
TES TLS TEF TLF
TES TLS TEF TLS
r(i,j)
R（ i,j）
A4
B6
C6 G7
D7
E5
F9
H4
I 8
0 0
4 7
6
13
22
20
28 28
20
24
13
6
关键路线：由总时差为零的工序构成
B D G I
t（ i,j)
t（ j,k)
OR3 38
.
解上例 计算工序时间参数工序 i j t(i,j) ES EF LS LF R r
A 4 0 4 3 7 3 0
B 6 0 6 0 6 0 0
C 6 4 10 7 13 3 3
D 7 6 13 6 13 0 0
E 5 6 11 19 24 13 11
F 9 13 22 15 24 2 0
G 7 13 20 13 20 0 0
H 4 22 26 24 28 2 2
I 8 20 28 20 28 0 0
OR3 39
9.4计划评审技术－－ PERT
PERT的产生关键路线法中，工序时间是确定值，而对研究性的工序来说,t（ i,j）是随机的。 1958年美国海军武器局研制北极星导弹时提出，重点在于计划的评审。
PERT的时间估计 采用三种时间估计法 a－最乐观时间,b－最悲观时间,m－最可能时间，
则工序期望时间 te＝
方差 δe2＝（ ） 2
a+4m+b
6b－ a
6
OR3 40
PERT的计算方法
网络图的绘制与关键路线法相同
参数计算与关键路线法体系不同工程期望工期 TE ＝ ∑ tek
期望工期方差 δ2＝ ∑ δek2
计划工期 TK－－业主要求的工期预期完工概率,?＝ 查正态分布表一定概率的完工期 TK＝ TE + δ?
TK－ TE
δ
OR3 41
PERT应用举例
P346例 6 关键工序,C D F/G I J
期望工期：
TE＝ 10.50+10.17+20.33+5.17+12.83＝ 59
δ12＝ 1.36+0.25+4.00+0.25+14.69＝ 20.55
δ22＝ 1.36+0.25+1.00+0.25+14.69＝ 17.55
完工概率,?1＝（ 60-59）20.55＝ 0.22
查表得 P（?1）＝ 58.7％
2＝（ 60-59）17.55＝ 0.244
查表得 P（?2）＝ 59.5
若要有 90％的把握，计划工期应定多长
TK＝ TE + δ?＝ 59+4.53?1.29＝ 64.84
OR3 42
9.5 网络优化
CPM与 PERT主要目标是控制工期
网络优化在上述基础上，寻求时间更短、资源更省、成本更低的方案
9.5.1时间－资源优化 （资源的均衡配置）
原则：关键优先、利用时差 P331例题 4
方法：绘制资源负荷图，排定关键工序，游移非关键工序
60 80 110 135
d20天 g30天 k25天
58人
H15天 39人
42人 26人F18天 22人
OR3 43
9.5.2 时间－费用优化
时间和费用双目标优化，一般来讲二者是矛盾的。
通过仔细分析，寻找既省时又省钱的方案，即最低成本日程。
费用：直接费用和间接费用
直接费用：建造工程本身所需材料、人工
间接费用：工程所需管理费用、设备租金
c
t
间接费用总费用直接费用赶工：直接费用增加，间接费用减少。间接费用是常量直接费用简化为常量处理。
则：
赶工直接费用率＝ 费用差时间差
OR3 44
例题 5 P337
资料,P325图 9-8，关键工序 A,D,G,K,L
P337表 9-7提供赶工费用资料。
赶工选择关键工序才有意义；赶工费用率不高于间接费用率才有价值；赶工时间既取决于极限工期，又取决于次长路线。
A 60
B 45
C 10
D 20
E 40
G 30 K 25
F 18
H 15
L 35
首选 K赶工 10天再选 G赶工 10天已赶工 20天，此时出现两条关键路线
OR3 45
第十章 决策论
10.1决策的分类
按层次分：战略决策，战术决策
按频率分：程序性决策，非程序性决策
按状态信息分：确定型决策，不确定型决策，风险型决策
决策的三要素：方案、状态、损益矩阵
决策的程序
OR3 46
10.2不确定型决策
悲观准则
乐观准则
折衷准则
等可能准则
后悔值准则
OR3 47
10.3风险型决策
10.3.1决策准则例 1：
1,最大可能准则 取 A 3方案，收益 30
2,期望值准则 取 A 1方案，收益 34
EMV（ Expected Maximum Value）＝?P(θj)aij
θ1
0.2
θ2
0.5
θ3
0.2
θ4
0.1
E（ Ai）
A1
A2
A3
-20
-10
15
20
20
30
40
38
30
60
50
30
34
32
28.5
j
OR3 48
.
3,期望值与标准差准则
σ（ Ai)＝P（ θj ） ﹝a ij- E（ Ai） ﹞ 2
σ（ A1）＝ 22,σ（ A2）＝ 17,σ（ A3）＝ 4.5
设常数 K代表风险厌恶因子，则期望值与标准差的综合值为,ED(Ai)＝ E(Ai)－ Kσ（ Ai)
设 K=1，则
ED(A1)＝ 34－ 22＝ 12
ED(A2)＝ 32－ 17＝ 15
ED(A3)＝ 28.5－ 4.5＝ 24
OR3 49
.
4、生存风险度决策法生存风险度＝最大损失 /致命损失例 2：某企业有 200万元资产，火灾概率
0.0001，保险费每年 500元。
按照期望值法决策：
2000000× 0.0001＝ 200?500
按照生存风险度法决策：
投保：风险度＝ 500× 20/200万元＝ 0.5％
不投保：风险度＝ 200万元 /200万元＝ 100％
OR3 50
10.3.2 决策树法
把决策问题结构化
例 3.某研究所可投标一项 70万元的新产品开发项目。若投标，预研费用 2万元，
中标概率 60％，若中标用老工艺花费 28
万元，成功概率 80％，用新工艺花费 18
万元，成功概率 50％，研制失败赔偿 15
万元，投标还是不投标？中标后用什么工艺？
OR3 51
..
解：
计算：
状态节点? 70× 0.8+（ -15） × 0.2＝ 53
状态节点? 70× 0.5+（ -15） × 0.5＝ 27.5
决策节点 max{53-28,27.5-18}＝ 25
状态节点?25× 0.6+0× 0.4＝ 15
状态节点?0× 1＝ 0
决策节点 max{15,0}＝ 15 投标，中标用老工艺
1
2
34
5
6
不投标投标中标不中老工艺新工艺成功失败成功失败
70
-15
70
-15
0
03
1
53
27.5
0.8
0.2
0.5
0.5
0.6
0.4
25 -28
-1815
-213
肯定不中标 1
OR3 52
10.3.3 贝叶斯决策
1、完全信息价值 EVPI
Expected Value in perfect Information是指决策人为获取完全准确的信息，所能支付的信息费的上限。
θ1
0.1
θ2
0.2
θ3
0.5
θ4
0.2
E（ Ai）
A1
A2
A3
-20
-10
15
20
20
30
40
38
30
60
50
30
34
32
28.5
EVPI＝?P(θj)max{aij}－ EMV＝
0.1× 15+0.2× 30+0.5× 40+0.2× 60－ 34＝ 5.5j
OR3 53
2、先验概率和后验概率
完全信息无法取得，人们只能根据资料和经验对状态信息做出估计，这就是先验概率。
根据新的信息，对先验概率进行修正，
得到的便是后验概率。
设 P(θj)是状态 θj出现的概率，即先验概率,Si为补充信息事件组，则
P(Si)＝? P(θj)?P（ Si/θj）
P（ Si/θj）? P(θj)
P(Si)
j
P（ θj/Si）＝
OR3 54
3、贝叶斯决策应用举例
某公司拟投资一家电项目，预计市场状态和利润如下表
投资前可向市场调查机构咨询，
结果有好、中、
差三种，咨询机构信誉表如下，
若咨询费用 0.5
万元，如何决策？
状态 θj 好 θ1 中 θ2 差 θ3
概率 P(θj) 0.45 0.30 0.25
利润 15 8 -10
P（ Si/θj） θ
1 θ1 θ1
好 S1
中 S2
差 S3
0.75 0.15 0.10
0.15 0.70 0.15
0.10 0.15 0.75
OR3 55
解：
首先，画决策树
1
2
3
4
7
6
5
8
9
10
不咨询咨询 -0.5
6.65 投资不投资好 0.45
中 0.30
差 0.25
好 0.4075
中 0.3150
差 0.2775
投资不投资好 0.8282
中 0.1104
差 0.0613
投资不投资投资不投资好 0.2143
中 0.6667
差 0.1190
好 0.1622
中 0.1622
差 0.6757
15
8
-10
0
15
8
-10
15
8
-10
15
8
-10
0
0
0
6.65
12.69
12.69
7.36
7.36
0
-3.03
7.49
6.99
OR3 56
.
计算后验概率，填在图上并计算、决策
P(θ1) P(θ2) P(θ3)
P(S1)＝ 0.4075
P(S2)＝ 0.3150
P(S3)＝ 0.2775
0.75 0.15 0.10
0.15 0.70 0.15
0.10 0.15 0.75
P（ θj/Si） θj θj θj
S1
S2
S3
0.8282 0.1104 0.0613
0.2143 0.6667 0.1190
0.1622 0.1622 0.6757
OR3 57
10.4 效用理论
OR3 58
10.5 层次分析法
OPERATIONS RESEARCH
运筹学 Ⅲ
—— 如何把事情做得最好郝英奇
OR3 2
第六章 整数规划本章要求
理解整数规划的含义
掌握分枝定界法的思想和方法
掌握 0-1变量的含义和用法
掌握指派问题的算法
微机求解
OR3 3
6.1 整数规划问题的提出
决策问题中经常有整数要求，如人数、
件数、机器台数、货物箱数 …… 如何解决？四舍五入不行，枚举法太慢
问题分类,纯整数规划,混合整数规划、
0-1整数规划
专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法
OR3 4
问题举例
某集装箱运输公司，箱型标准体积 24m3，重量
13T,现有两种货物可以装运，甲货物体积 5m3、
重量 2T、每件利润 2000元；乙货物体积 4m3、
重量 5T、每件利润 1000元，如何装运获利最多？
maxZ=2000x1+1000x2
5x1+4x2≤24
2x1+5x2 ≤13
x1.x2 ≥0且为整数
解此 LP问题，得,X1=4.8,X2=0
显然不是可行解
OR3 5
整数规划图解法
x2
x11 2 3 4 5 6 7
2
3
1 B
A
OR3 6
图解法的启示
A（ 4.8,0）点是 LP问题的可行解，不是 IP问题的可行解,B（ 4,1）才是 IP的最优解
纯整数规划的可行解就是可行域中的整数点
非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化
IP问题的最优解不优于 LP问题的最优解
OR3 7
6.2 分枝定界法
思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解
例 1,maxZ=2000x1+1000x2
5x1+4x2≤24
2x1+5x2 ≤13
x1.x2 ≥0且为整数解：先不考虑整数要求，解相应的 LP问题，得：
x1=4.8 x2=0 Z=9600 不是可行解
Z=9600是 IP问题的上界，记为,Z=9600
OR3 8
分枝定界法（续）
X1=4.8不符合要求，切掉 4— 5之间的可行域，
可行域变成两块，即原有约束条件再分别附加约束条件 x1 ≤4和 x1 ≥5
原问题分解为两个
maxZ=2000x1+1000x2 maxZ=2000x1+1000x2
5x1+4x2≤24 5x1+4x2≤24
2x1+5x2 ≤13 ( IP1 ) 2x1+5x2 ≤13 (IP2)
x1 ≤4 x1 ≥5
x1.x2 ≥0且为整数 x1.x2 ≥0且为整数
OR3 9
分枝定界法（续）
不考虑整数要求，解相应 LP问题。
解 IP1得,x1=4,x2=1 z=9000
解 IP2得：无可行解此时可以断定 IP问题的下界为 9000，记为 Z=9000
由于目前的分枝末梢最大值是 9000，故
IP问题的上界便是 9000。由于 Z=Z，此时已得 IP问题的最优解，即
x1=4,x2=1,Z=9000
OR3 10
分枝定界法的解题步骤
1、不考虑整数约束，解相应 LP问题
2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步
3、任取一个非整数变量 xi=bi，构造两个新的约束条件,xi ≤[bi],xi ≥ [bi]+1,分别加入到上一个 LP问题，形成两个新的分枝问题。
4、不考虑整数要求，解分枝问题。若整数解的 Z值 >所有分枝末梢的 Z值，则得最优解。否则,取 Z值最大的非整数解，
继续分解,Go to 3 （例题 2讲解）
OR3 11
6.3 0— 1规划问题
某些特殊问题，只做是非选择，故变量设置简化为 0或 1,1代表选择,0代表不选择。
例 4,600万元投资 5个项目，求利润最大的方案？
项目 投资额 项目收益 约束条件
210 160中选 1项
300 210之中选 1项
150 60 选?必先选?
130 80
260 180
OR3 12
求解 0— 1规划的隐枚举法
例 4解：
0 当项目未被选中
1 当项目被选中
max Z=160x1+210x2+60x3+80x4+180x5
210x1+300x2+150x3+130x4+260x5 ≤600?
X1+x2+x3=1?
X3+x4=1?
x5 ≤ x1?
Xj=0或 1 j=1,2,…,5
增加过滤条件,160x1+210x2+60x3+80x4+180x5 ≥ 240?
建模：设 xj=
OR3 13
用隐枚举法解例 4：
(x1,x2,x3,x4,x5） Z值
（ 1,0,0,1,0） 240
（ 1,1,1,1,1）? X
（ 1,1,1,1,0）? X
（ 1,1,1,0,1）? X
（ 1,1,1,0,0）? X
（ 1,1,0,1,1）? X
（ 1,1,0,1,0）? X
（ 1,1,0,0,1）? X
（ 1,1,0,0,0） X
（ 1,0,1,1,1）? X
（ 1,0,1,1,0） X
（ 1,0,0,1,1） 420
………,.
OR3 14
6.4 指派问题
例 8 甲乙丙丁四个人,A,B,D四项任务，不同的人做不同的工作效率不同，
如何指派不同的人去做不同的工作使效率最高？
任务人 时间 A B C D
甲乙丙丁
4 10 7 5
2 7 6 3
3 3 4 4
4 6 6 3
数模,
minZ=ΣΣcijxij
Σxij=1 i=1,…,n
Σxij=1 j=1,…,n
Xij=0或 1
OR3 15
指派问题解法 — 匈牙利法
解：类似运输问题的最小元素法
第一步 造 0—— 各行各列减其最小元素
4 10 7 5 -4 0 6 3 1? 6 2 1?
Cij= 2 7 6 3 -2? 0 5 4 1? 0 5 3 1?
3 3 4 4 -3 0 0 1 1 0? 0 1
4 6 6 3 -3 1 3 3 0 1 3 2?
-1?
第二步 圈 0—— 寻找不同行不同列的 0元素，
圈之。 所在行和列其它 0元素划掉
第三步 打?—— 无?的行打?，打?行上 0列打
,打?列上?行打?，打?行上 0列打? …
OR3 16
指派问题解法 — 匈牙利法（续）
第四步 划线 —— 无?行、打?列划线
第五步 造 0—— 直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的 0元素,Go to 2
0 6 2 1 -1? 5 1 0? 0 4? 0
Cij= 0 5 3 1 -1? 0 4 2 0 3 1 0
0 0 0 1 1? 0 1 2? 0 2
1 3 2 0 2 3 2 2 2 1?
+1
最优解,x13=1,x21=1,x32=1,x44=1 Z=15
OR3 17
相关问题：
非标准型的转化
（ 1） maxZ= ΣΣcijxij?minZ’= ΣΣ(-cij)xij
minZ’’= ΣΣ(M-cij)xij= ΣΣbijxij
M是足够大的常数,新问题的最优解就是原问题的最优解
（ 2）整数规划的计算机求解
OR3 18
整数规划习题课
P222—— 6.11
A B C B D
1 1
2 1
3 1
4 1
5 1
OR3 19
第七章 动态规划（略）
OR3 20
第八章 图与网络分析
引论 哥尼斯堡七桥问题
A
B
DC
A
B
C D
简捷表示事物之间的本质联系，归纳事物之间的一般规律
OR3 21
引论 图的用处
A,B,C,D,E 某公司的五支球队进行循环赛 组织机构设置图
A
B C
D E
总公司 分公司 工厂或办事处
OR3 22
8.1 图的基本概念
图是由 点 和 线 构成的。
点的集合 V表示,V={vi}
不带箭头的连线叫做 边 (edge)，边的集合记为 E= { ej },一条边可以用两点
[ vi,vj ]表示,ej= [ vi,vj ].
带箭头的连线叫做 弧 (arc),弧的集合记为
A,A= { ak },一条弧也是用两点表示，
ak= [ vi,vj ],弧有方向,vi为始点,vj为终点
OR3 23
图的基本概念 (续 )
由点和边组成的图叫做 无向图,记为 G=（ V,E）
由点和弧组成的图叫做 有向图,记为 D=（ V,A）
例 1.
v1 v2
v3v4
v1
v2
v3
v4
v5
v6
v7
e1
e2
e3 e4e5
e6
e7
a1
a2
a8
a4a
3
a5
a6 a9
a7
a10
a11
无向图：点集、边集 有向图：点集、弧集
OR3 24
图的基本概念 (续 )
以点 u为端点的边的条数，叫做点 u的 次次为 1的点叫做 悬挂点 ；次为 0的点叫做孤立点 ；次为奇数则称 奇点 ；次为偶数则称 偶点。
点弧交替序列称为 链 ；闭合的链称为 圈
首尾相接的链称为 路 ；闭合的路称 回路
任意两点之间都有边相连，称为 连通图
OR3 25
8.2 树
无圈的连通图称之为 树
赋权无向图 G=（ V,E）的最小基干称为最小支撑树
赋权有向图 D=（ V,A）,从始点到终点的权值最小的路称为 最短路
OR3 26
8.3 最短路问题
例 6 某交通网络如下图，求 v1到 v8的最短路线
解：用双标号法
v1
v2
v4
v3
v5
v6
v7
v863
1
2
2
1
6
10
4
3
10
4
4
6
v1
V2(v3,5)
V3(v1,3)
V4(v1,1)
V5(v2,6)
V6(v5,10)
V7(v5,9)
V8(v5,12)6
3
1
2
2
1
6
10
4 10
4
3
6
4
V2(v1,6）
OR3 27
8.4 最大流问题
引例：如下输水网络，南水北调工程，
从 vs到 vt送水，弧旁数字前者为管道容量，
后者为现行流量，如何调整输水最多？
vs vt
v2
v1
v4
v3
(3,3)
(5,1)
(1,1)
(4,3)
(1,1)
(2,2)
(3,0)
(2,1)
(5,3)
OR3 28
最大流问题的相关概念
网络：给定了弧的容量 C（ vi,vj）的有向图 D=
（ V,A,C）叫做一个 网络 。
可行流：各点流入量 =流出量，且 vs的流出量
=vt的流入量，这样的流称之为 可行流
截集：分离始点 vs和终点 vt的弧的集合，叫做截集
截量：截集的容量叫做 截量
增广链：一条从到的链，前向弧上可增加，后向弧上可减少，则称此链为 增广链
OR3 29
求最大流的方法
方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。
寻找增广链的标号法：先给 vs标号（ 0，
+∞）,而后依次审查各条弧（ vi,vj）：对前向弧，饱和否？不饱和，给 vj点标号
（ vi,l(vj));对后向弧，可否减少？可，给
vj标号（ -vi,l(vj) ）,直到给 vt标上号，就得到了增广链。
OR3 30
解水网最大流问题
.
vs
V2
(0,+∞)
V1
(3,3)
(5,1)
(1,1)
(4,3)
(1,1)
(2,2)
(3,0)
(5,3)
(2,1)
V4
V3
Vt
(vs,4)
(-v1,1)
(-v2,1)
(v3,1)
(v2,1)
OR3 31
此题最大流图
沿增广链进行调整，前向弧增加 l(vj)，后向弧减少 l(vj)
vs
V2
V1 V3
V4
Vt
(3,3)
(5,2)
(4,3)
(1,0) (1,0)
(2,2)
(3,0)
(5,3)
(2,2)
(0,+∞)
(vs,3)
OR3 32
习题,p312－ 8.4，求最大流
给出任意可行流
找到一条增广链
调整可行流 注,’ ＝ 1,#＝ 1,$＝ 2，
*=1
vs
v1 v2
v3
v4 v5
vt
（ 4,3） ’
（ 10,4） $*
（ 3,2） #
（ 1,1）
（ 3,2） ’
（ 3,2） *
（ 4,2） $
（ 5,3） #*
（ 4,3） ’ （ 2,
2
）
（ 7,6） ’
（ 8,3） #$*
(0,+∞)
(vs,3)
OR3 33
第九章 网络计划
9.1基本概念
～是用网络分析的方法编制的计划
杜邦公司 — 关键路线法 CPM 确定型
美国海军武器局 — 计划评审技术 PERT
网络图（有向赋权图）的构成
结点，也称事项，一道工序的开始或结束
工序（弧），相对独立的活动，消耗资源
虚工序，只表示衔接关系，不消耗资源
工序时间（权），完成工序的时间消耗
OR3 34
9.2.网络规则
1、避免循环、不留缺口
2、一一对应：一道工序用两个事项表示
3,从左向右依次展开例,工 序 A B C D E F G H I
紧前工序 -- -- A B B C,D C,D E,F G
工序时间 4 6 6 7 5 9 7 4 8
A,4
B,6
C,6
D,7
E,5
G,7
F,9
H,4
I,8
OR3 35
9.3 关键路线法－－ CPM
9.3.1时间参数运算 什么是关键路线？
1、作业时间 t（ i,j），经验数据、统计数据
2、事项最早时间 TE(j)＝ max{TE(i)+ t（ i,j） }
到齐上课，最后到者决定最早开课时间
3、事项最迟时间 TL(i)＝ min{TL(j)- t（ i,j） }
保证 12点吃饭，路最远者决定最迟下课时间
4、工序最早可能开工时间
TES(i,j)＝ TE(i) = max{TES(h,i)+ t（ h,i ） }
5、工序最早可能完工时间
TEF(i,j)＝ TES(i,j)+ t（ i,j）
h
i
j
OR3 36
.6、工序最迟必须开工时间
TLS（ i,j)＝ TL(j)－ t（ i,j)＝ min{TLs(j,k)- t（ i,j） }
7、工序最迟必须完工时间
TLF（ i,j)＝ TL(j)＝ TLS（ i,j)+ t（ i,j)
8、工序总时差：在不影响其紧后工序 最迟必须开工时间的前提下，本工序可以推迟的时间
R（ i,j）＝ TLS(i,j)－ TES(i,j) ＝ TLF(i,j)－ TEF(i,j)
＝ min{TLS(j,k) } – TEF（ i,j）
9、工序单时差：在不影响其紧后工序 最早可能开工时间的前提下，本工序可以推迟的时间
r （ i,j）＝ min{TES(j,k) } – TEF（ i,j）
K
k
k
OR3 37
9.3.2时间参数图解
.
解上例：
计算事项
时间参数
TES TLS TEF TLF
TES TLS TEF TLS
r(i,j)
R（ i,j）
A4
B6
C6 G7
D7
E5
F9
H4
I 8
0 0
4 7
6
13
22
20
28 28
20
24
13
6
关键路线：由总时差为零的工序构成
B D G I
t（ i,j)
t（ j,k)
OR3 38
.
解上例 计算工序时间参数工序 i j t(i,j) ES EF LS LF R r
A 4 0 4 3 7 3 0
B 6 0 6 0 6 0 0
C 6 4 10 7 13 3 3
D 7 6 13 6 13 0 0
E 5 6 11 19 24 13 11
F 9 13 22 15 24 2 0
G 7 13 20 13 20 0 0
H 4 22 26 24 28 2 2
I 8 20 28 20 28 0 0
OR3 39
9.4计划评审技术－－ PERT
PERT的产生关键路线法中，工序时间是确定值，而对研究性的工序来说,t（ i,j）是随机的。 1958年美国海军武器局研制北极星导弹时提出，重点在于计划的评审。
PERT的时间估计 采用三种时间估计法 a－最乐观时间,b－最悲观时间,m－最可能时间，
则工序期望时间 te＝
方差 δe2＝（ ） 2
a+4m+b
6b－ a
6
OR3 40
PERT的计算方法
网络图的绘制与关键路线法相同
参数计算与关键路线法体系不同工程期望工期 TE ＝ ∑ tek
期望工期方差 δ2＝ ∑ δek2
计划工期 TK－－业主要求的工期预期完工概率,?＝ 查正态分布表一定概率的完工期 TK＝ TE + δ?
TK－ TE
δ
OR3 41
PERT应用举例
P346例 6 关键工序,C D F/G I J
期望工期：
TE＝ 10.50+10.17+20.33+5.17+12.83＝ 59
δ12＝ 1.36+0.25+4.00+0.25+14.69＝ 20.55
δ22＝ 1.36+0.25+1.00+0.25+14.69＝ 17.55
完工概率,?1＝（ 60-59）20.55＝ 0.22
查表得 P（?1）＝ 58.7％
2＝（ 60-59）17.55＝ 0.244
查表得 P（?2）＝ 59.5
若要有 90％的把握，计划工期应定多长
TK＝ TE + δ?＝ 59+4.53?1.29＝ 64.84
OR3 42
9.5 网络优化
CPM与 PERT主要目标是控制工期
网络优化在上述基础上，寻求时间更短、资源更省、成本更低的方案
9.5.1时间－资源优化 （资源的均衡配置）
原则：关键优先、利用时差 P331例题 4
方法：绘制资源负荷图，排定关键工序，游移非关键工序
60 80 110 135
d20天 g30天 k25天
58人
H15天 39人
42人 26人F18天 22人
OR3 43
9.5.2 时间－费用优化
时间和费用双目标优化，一般来讲二者是矛盾的。
通过仔细分析，寻找既省时又省钱的方案，即最低成本日程。
费用：直接费用和间接费用
直接费用：建造工程本身所需材料、人工
间接费用：工程所需管理费用、设备租金
c
t
间接费用总费用直接费用赶工：直接费用增加，间接费用减少。间接费用是常量直接费用简化为常量处理。
则：
赶工直接费用率＝ 费用差时间差
OR3 44
例题 5 P337
资料,P325图 9-8，关键工序 A,D,G,K,L
P337表 9-7提供赶工费用资料。
赶工选择关键工序才有意义；赶工费用率不高于间接费用率才有价值；赶工时间既取决于极限工期，又取决于次长路线。
A 60
B 45
C 10
D 20
E 40
G 30 K 25
F 18
H 15
L 35
首选 K赶工 10天再选 G赶工 10天已赶工 20天，此时出现两条关键路线
OR3 45
第十章 决策论
10.1决策的分类
按层次分：战略决策，战术决策
按频率分：程序性决策，非程序性决策
按状态信息分：确定型决策，不确定型决策，风险型决策
决策的三要素：方案、状态、损益矩阵
决策的程序
OR3 46
10.2不确定型决策
悲观准则
乐观准则
折衷准则
等可能准则
后悔值准则
OR3 47
10.3风险型决策
10.3.1决策准则例 1：
1,最大可能准则 取 A 3方案，收益 30
2,期望值准则 取 A 1方案，收益 34
EMV（ Expected Maximum Value）＝?P(θj)aij
θ1
0.2
θ2
0.5
θ3
0.2
θ4
0.1
E（ Ai）
A1
A2
A3
-20
-10
15
20
20
30
40
38
30
60
50
30
34
32
28.5
j
OR3 48
.
3,期望值与标准差准则
σ（ Ai)＝P（ θj ） ﹝a ij- E（ Ai） ﹞ 2
σ（ A1）＝ 22,σ（ A2）＝ 17,σ（ A3）＝ 4.5
设常数 K代表风险厌恶因子，则期望值与标准差的综合值为,ED(Ai)＝ E(Ai)－ Kσ（ Ai)
设 K=1，则
ED(A1)＝ 34－ 22＝ 12
ED(A2)＝ 32－ 17＝ 15
ED(A3)＝ 28.5－ 4.5＝ 24
OR3 49
.
4、生存风险度决策法生存风险度＝最大损失 /致命损失例 2：某企业有 200万元资产，火灾概率
0.0001，保险费每年 500元。
按照期望值法决策：
2000000× 0.0001＝ 200?500
按照生存风险度法决策：
投保：风险度＝ 500× 20/200万元＝ 0.5％
不投保：风险度＝ 200万元 /200万元＝ 100％
OR3 50
10.3.2 决策树法
把决策问题结构化
例 3.某研究所可投标一项 70万元的新产品开发项目。若投标，预研费用 2万元，
中标概率 60％，若中标用老工艺花费 28
万元，成功概率 80％，用新工艺花费 18
万元，成功概率 50％，研制失败赔偿 15
万元，投标还是不投标？中标后用什么工艺？
OR3 51
..
解：
计算：
状态节点? 70× 0.8+（ -15） × 0.2＝ 53
状态节点? 70× 0.5+（ -15） × 0.5＝ 27.5
决策节点 max{53-28,27.5-18}＝ 25
状态节点?25× 0.6+0× 0.4＝ 15
状态节点?0× 1＝ 0
决策节点 max{15,0}＝ 15 投标，中标用老工艺
1
2
34
5
6
不投标投标中标不中老工艺新工艺成功失败成功失败
70
-15
70
-15
0
03
1
53
27.5
0.8
0.2
0.5
0.5
0.6
0.4
25 -28
-1815
-213
肯定不中标 1
OR3 52
10.3.3 贝叶斯决策
1、完全信息价值 EVPI
Expected Value in perfect Information是指决策人为获取完全准确的信息，所能支付的信息费的上限。
θ1
0.1
θ2
0.2
θ3
0.5
θ4
0.2
E（ Ai）
A1
A2
A3
-20
-10
15
20
20
30
40
38
30
60
50
30
34
32
28.5
EVPI＝?P(θj)max{aij}－ EMV＝
0.1× 15+0.2× 30+0.5× 40+0.2× 60－ 34＝ 5.5j
OR3 53
2、先验概率和后验概率
完全信息无法取得，人们只能根据资料和经验对状态信息做出估计，这就是先验概率。
根据新的信息，对先验概率进行修正，
得到的便是后验概率。
设 P(θj)是状态 θj出现的概率，即先验概率,Si为补充信息事件组，则
P(Si)＝? P(θj)?P（ Si/θj）
P（ Si/θj）? P(θj)
P(Si)
j
P（ θj/Si）＝
OR3 54
3、贝叶斯决策应用举例
某公司拟投资一家电项目，预计市场状态和利润如下表
投资前可向市场调查机构咨询，
结果有好、中、
差三种，咨询机构信誉表如下，
若咨询费用 0.5
万元，如何决策？
状态 θj 好 θ1 中 θ2 差 θ3
概率 P(θj) 0.45 0.30 0.25
利润 15 8 -10
P（ Si/θj） θ
1 θ1 θ1
好 S1
中 S2
差 S3
0.75 0.15 0.10
0.15 0.70 0.15
0.10 0.15 0.75
OR3 55
解：
首先，画决策树
1
2
3
4
7
6
5
8
9
10
不咨询咨询 -0.5
6.65 投资不投资好 0.45
中 0.30
差 0.25
好 0.4075
中 0.3150
差 0.2775
投资不投资好 0.8282
中 0.1104
差 0.0613
投资不投资投资不投资好 0.2143
中 0.6667
差 0.1190
好 0.1622
中 0.1622
差 0.6757
15
8
-10
0
15
8
-10
15
8
-10
15
8
-10
0
0
0
6.65
12.69
12.69
7.36
7.36
0
-3.03
7.49
6.99
OR3 56
.
计算后验概率，填在图上并计算、决策
P(θ1) P(θ2) P(θ3)
P(S1)＝ 0.4075
P(S2)＝ 0.3150
P(S3)＝ 0.2775
0.75 0.15 0.10
0.15 0.70 0.15
0.10 0.15 0.75
P（ θj/Si） θj θj θj
S1
S2
S3
0.8282 0.1104 0.0613
0.2143 0.6667 0.1190
0.1622 0.1622 0.6757
OR3 57
10.4 效用理论
OR3 58
10.5 层次分析法
