系统工程与运筹学基础
（运筹学部分）
目 录
第一章 线性规划
第二章 对偶
第三章 整数规划
第四章 运输问题
第五章 网络优化
第六章 动态规划
第一章 线性规划
线性规划模型
线性规划的图解
可行域的性质
线性规划的基本概念
基础解、基础可行解
单纯形表
线性规划的矩阵表示
线性规划模型
线性规划模型的结构
目标函数 ：max，min
约束条件：≥,=,≤
变量符号：：≥0, unr, ≤0
线性规划的标准形式
目标函数：min
约束条件 ：=
变量符号 ：≥0
线性规划的图解
max z=x1+3x2
. x1+ x2≤6
-x1+2x2≤8
x1 ≥0, x2≥0 可行域
目标函数等值线
最优解
6
4
-8
6
0
x1
x2
可行域的性质
●线性规划的可行域是凸集
●线性规划的最优解在极点上
凸集 凸集 不是凸集
极点
线性规划的基本概念
●线性规划的基矩阵、基变量、非基变量
=
=
目标函数
约
束
条
件
行列式≠0
基矩阵
右边常数
基变量x1、x2、x3，非基变量x4、x5、x6
基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，
0）
是基础可行解，表示可行域的一个极点。
目标函数值为：z=20
基变量x1、x2、x4，非基变量x3、x5、x6
基础解为
（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）
是基础可行解，表示可行域的一个极点。
目标函数值为：z=18
基变量x1、x2、x5，非基变量x3、x4、x6
基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，
0）
是基础解，但不是可行解，不是一个极点。
基变量x1、x2、x6，非基变量x3、x4、x5
基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，
4）
是基础可行解，表示可行域的一个极点。
目标函数值为：z=18
基变量x2、x3、x4，非基变量x1、x5、x6
基础解为
（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，
0）
是基础解，但不是可行解。
基变量x1、x2、x3，非基变量x4、x5、x6
基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）
是基础可行解，表示可行域的一个极点。
目标函数值为：z=15
基变量x1、x2、x3，非基变量x4、x5、x6
基础解为
（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）
是基础解但不是可行解。
=
目标函数
约
束
条
件
基矩阵
右边常数
进基变量、离基变量、基变换
=
基变量
=
进基变量
离基变量
目标函数
约
束
条
件
右边常数=
=
目标函数
约
束
条
件
新的基矩阵
右边常数=
=
进基变量
离基变量
目标函数
约
束
条
件
基矩阵
=
=
目标函数
约
束
条
件
新的基矩阵
右边常数=
基础解、基础可行解
max z=x1+3x2 D
. x1+ x2+x3 =6 B
-x1+2x2 +x4 =8 x4=0 C x3=0
x1, x2,x3,x4≥0 x1=0
E O x2=0 A
几何概念 代数概念
约束直线 满足一个等式约束的解
约束半平面 满足一个不等式约束的解
约束半平面的交集：
凸多边形
满足一组不等式约束的解
约束直线的交点 基础解
可行域的极点 基础可行解
目标函数等值线：
一组平行线
目标函数值等于一个常
数的解
单纯形表
求解线性规划问题
写成标准化形式
写出单纯形表
25/1
36/2
0 -3 -2 0 -2 -72
0
1
1/2 0 1 -1/2 7/1/2
1
x5
1/2 1 0 1/2 18/1/20
7
18
1
1/2
1/2x2
0
x6离基，x2进基，
x5离基，x1进基，
0 -4 -2 -2 -1 -86
0
1
1 0 2 -1
1
x1
0 1 -1 10
14
11
0
1
0x2
0
得到最优解，最优解为：
（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0）
min z’=-86，max z=86
线性规划的矩阵表示
=
=
=
=
=
CBTB-1aj-cj=zj-cj 称为非基变量的检验数（Reduced Cost）
B-1aj=Yj， B-1b= ，CBTB-1b=z0
第二章 对偶线性规划
对偶的定义
对偶问题的性质
原始对偶关系
目标函数值之间的关系
最优解之间的关系—互补松弛关系
最优解的Kuhn-Tucher条件
对偶可行基对偶单纯形法
对偶的经济解释
DUAL
一、对偶的定义
原始问题
min z=CTX
. AX≥b
X ≥0
对偶问题
max y=bTW
. ATW≤C
W ≥0
≥
min
bA
CT
CAT
bT
≤
max
m
n
m
n
二、对偶问题的性质
1、对偶的对偶就是原始问题
max z’=-CTX
. -AX≤-b
X ≥0
min y=-bTW
. -ATW≥-C
W ≥0
max y=bTW
. ATW≤C
W ≥0
min z=CTX
. AX≥b
X
≥0
对偶的定义
对偶的定义
min z=CTX
. AX≤b
X
≥0
max y=bTW
. ATW≤C
W ≤0
2、其他形式问题的对偶
min z=CTX
. AX≥b
X
≥0
max y=bTW
. ATW≤C
W ≥0
min z=CTX
. AX=b
X
≥0
max y=bTW
. ATW≤C
W ：unr
三、原始对偶关系
1、可行解的目标函数值之间的关系
设XF、WF分别是原始问题和对偶问题的可行解
z=CTXF ≥WTAXF ≥WTb=y
2、最优解的目标函数值之间的关系
设Xo、Wo分别是原始问题和对偶问题的最优解
z=CTXo=WoTAXo=WoTb=y
3、原始问题和对偶问题最优解之间的互补松弛关系
min z=CTX
. AX-XS=b
X, XS≥0
max y=bTW
. ATW+WS=C
W, WS≥0
min z=CTX
. AX≥b
X ≥0
max y=bTW
. ATW≤C
W≥0对偶
引进松弛变量 引进松弛变量
XTWS=0 WTXS=0
互补松弛关系
X，Xs W，Ws
min z=CTX
. AX-XS=b
X, XS
≥0
max y=bTW
. ATW+WS=C
W, WS ≥0
XTWS=0
WTXS=0
m n
=
W WS
AT I Cn
=A
XS
-
I
b
n m
m
X
原始问题和对偶问题变量、松弛变量的维数
w1 wi wm wm+1 wm+j wn+m
x1 xj xn xn+1 xn+i xn+m
对偶问题的变量 对偶问题的松弛变量
原始问题的变量 原始问题的松弛变量
xjwm+j=0 wixn+i=0 (i=1,2,…,m; j=1,2,…,n)
在一对变量中，其中一个大于0，另一个一定等于0
Kuhn-Tucher 条件
3、原始问题和对偶问题最优解的充分必要条件
(1)原始可行条件（PFC）
AX-XS=b
X, XS ≥0
(2)对偶可行条件（DFC）
ATW+WS=C
W, WS ≥0
(3)互补松弛条件
（CSC）
XTWS=0
WTXS=0
四、对偶单纯形法
1、用单纯形表求解原始问题的四种形式
min z=CTX
. AX≥b
X ≥0
min z=CTX
. AX ≤ b
X ≥0
max z=CTX
. AX ≥ b
X ≥0
max z=CTX
. AX ≤ b
X ≥0
（2）
（3） （4）
（1）
单纯形表和对偶(1)
min z=CTX
. AX-XS=b
X, XS≥0
max y=bTW
. ATW+WS=C
W, WS≥0
min z=CTX
. AX≥b
X ≥0
max y=bTW
. ATW≤C
W≥0
对偶问题原始问题
引进松弛变量引进松弛变量
min z=CTX
. AX-XS=b
X, XS≥0
max y=bTW
. ATW+WS=C
W, WS≥0
WT=CBTB-1
WST=CT-WTA
min z=CTX
. AX+XS=b
X, XS≥0
max y=bTW
. ATW+WS=C
W ≤0, WS≥0
min z=CTX
. AX ≤ b
X ≥0
max y=bTW
. ATW≤C
W ≤ 0
单纯形表和对偶(2)
对偶问题原始问题
引进松弛变量引进松弛变量
min z=CTX
. AX+XS=b
X, XS≥0
max y=bTW
. ATW+WS=C
W ≤0, WS≥0
WT=CBTB-1
WST=CT-WTA
max z=CTX
. AX-XS=b
X, XS≥0
max y=bTW
. ATW-WS=C
W ≤0, WS≥0
max z=CTX
. AX ≥ b
X ≥0
min y=bTW
. ATW ≥ C
W ≤ 0
单纯形表和对偶(3)
对偶问题原始问题
引进松弛变量引进松弛变量
max z=CTX
. AX-XS=b
X, XS≥0
min y=bTW
. ATW-WS=C
W ≤0, WS≥0
WT=CBTB-1
WST=WTA- CT
max z=CTX
. AX+XS=b
X, XS≥0
max y=bTW
. ATW-WS=C
W, WS≥0
max z=CTX
. AX ≤ b
X ≥0
min y=bTW
. ATW ≥ C
W ≥ 0
单纯形表和对偶(4)
对偶问题原始问题
引进松弛变量引进松弛变量
max z=CTX
. AX+XS=b
X, XS≥0
min y=bTW
. ATW-WS=C
W, WS≥0
WT=CBTB-1
WST=WTA- CT
2、对偶单纯形法（初始解原始不可行的问题）
已获得最优解：
（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35
对偶问题的最优解为：
（w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35
3、初始解原始、对偶都不可行的问题
解法1：先解决原始可行性
在得到原始可行解时同时得到对偶可行解，已获得最优解：
（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17
对偶问题的最优解为：
（w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17
解法2：先解决对偶可行性
已得到对偶可行解，再用对偶单纯形法求解
得到原始可行解，已获得最优解：
（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17
对偶问题的最优解为：
（w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17
五、对偶的经济解释
1、原始问题是利润最大化的生产计划问题
单位产品的利润（元/件）
产品产量（件）
总利润（元）
资源限量（吨）单位产品消耗的资源（吨/件） 剩余的资源（吨）
消耗的资源（吨）
2、对偶问题
资源限量（吨）
资源价格（元/吨）
总利润（元）
对偶问题是资源定价问题，对偶问题的最优解w1、w2、...、
wm称为m种资源的影子价格（Shadow Price）
原始和对偶问题都取得最优解时，最大利润 max z=min y
3、资源影子价格的性质
■影子价格越大，说明这种资源越是相对紧缺
■影子价格越小，说明这种资源相对不紧缺
■如果最优生产计划下某种资源有剩余，这种资源的影子
价格一定等于0
w1
w2
wm
4、产品的机会成本
机会成本
表示减少一件产品所节省的资源可以增加的利润
增加单位资源可以增加的利润
减少一件产品可以节省的资源
机会成本 利润差额成本
5、产品的差额成本（Reduced Cost）
差额成本=机会成本 - 利润
5、互补松弛关系的经济解释
在利润最大化的生产计划中
（1）边际利润大于0的资源没有剩余
（2）有剩余的资源边际利润等于0
（3）安排生产的产品机会成本等于利润
（4）机会成本大于利润的产品不安排生产
第四章 运输问题
运输问题的表示
网络图、线性规划模型、运输表
初始基础可行解
西北角法、最小元素法
非基变量的检验数
闭回路法、对偶变量法
确定进基变量，调整运量，确定离基
变量
2
3
2
1
3
4
1
运输问题网络图
s2=27
s3=19
d1=22
d2=13
d3=12
d4=13
s1=14
供
应
量
供应地 运价
需
求
量
需求地
6
7
5
3
8
4
2
7
5
9
10
6
运输问题线性规划模型
供
应
地
约
束
需
求
地
约
束
运输问题的表格表示
初始基础可行解—西北角法
8 13
13
14
6
6
初始基础可行解—最小元素法（1）
最小元素法（2）
最小元素法（3）
最小元素法（4）
最小元素法（5）
最小元素法（6）
-5
非基变量xij的检验数zij-cij—闭回路法(1)
z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5
-5
闭回路法(2)
z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5
-5
-5
闭回路法(3)
z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7
-7-5
-5
闭回路法(4)
z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9
-9
-5 -7
-5
闭回路法(5)
z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11
+11
-5 -7
-9
-5
闭回路法(6)
z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3
+3
-5 -7
-9
+11
非基变量xij的检验数zij-cij—对偶变量法(1)
v4=0
对偶变量法(2)
u3+v4=c34 u3=6
对偶变量法(3)
u3+v3=c33 v3=4
对偶变量法(4)
u2+v3=c23 u2=-2
对偶变量法(5)
u2+v2=c22 v2=6
对偶变量法(6)
u2+v1=c21 v1=10
对偶变量法(7)
u1+v1=c11 u1=-4
对偶变量法(8)
z12-c12=u1+v2-c12=(-4)+6-7=-5
-5
对偶变量法(9)
z13-c13=u1+v3-c13=(-4)+4-5=-5
-5-5
对偶变量法(10)
z14-c14=u1+v4-c14=(-4)+0-3=-7
-7-5 -5
对偶变量法(11)
z24-c24=u2+v4-c24=(-2)+0-7=-9
-9
-5 -5 -7
对偶变量法(12)
z31-c31=u3+v1-c31=6+10-5=11
11
-5 -5 -7
-9
对偶变量法(13)
z32-c32=u3+v2-c32=6+6-9=+3
+3
-5 -5 -7
-9
11
选择进基变量,确定离基变量
x31进基, min{x21,x33}=min{8,6}=6, x33离基
+3
-5 -5 -7
-9
11
调整运量,重新计算检验数,确定进基、离基变量
x14进基, min{x11,x34}=min{14,13}=13, x34离基
-11
-5 -5 +4
+2
-8
调整运量, 重新计算检验数
所有zij-cij<0,得到最优解。
Min z=6×1+3 ×13+8 ×2+4 ×13+2 ×12+5 ×19=142
-11
-5 -5
-4-8
-2
第五章 网络优化
网络的基本概念
网络最小费用流问题
网络最大流问题
最短路径问题
网络的基本概念
■节点与（有向）边
每一条边和两个节点关联，一条边
可以用两个节点的标号表示（i，
j）
ji
■路径（Path）
前后相继并且方向相同的边序列
P={(1,2),(2,3),(3,4)}
4
2
3
1
4
2
3
1
■网络由节点和边组成
■回路（Circuit）
起点和终点重合的路径称为回路
μ={(1,2),(2,4),(4,1)}
回路中各条边方向相同
4
2
3
1
■链（Chain）
前后相继并且方向不一定相同的边
序列称为链
C={(1,2),(3,2),(3,4)}
4
2
3
1
■连通图
任意两个节点之间至少有一条
链的图称为连通图
2
4
3
51
■圈(Cycle)
起点和终点重合的链称为圈
ρ ={(1,2),(2,4),(3,4),(1,3)}
圈中各条边方向不一定相同
4
2
3
1
■树(Tree)
无圈的连通图称为树
树中只与一条边关联的节点称
为悬挂节点
树的性质
任何树至少有一个悬挂节点
2
4
3
51
2
4
3
51
2
4
3
51
■如果树的节点个数为m，则
边的个数为m-1
■树中任意两个节点之间只有
唯一的一条链
■在树的任意两个不相邻的节
点之间增加一条边，则形成唯
一的圈
网络的生成树
■由网络的所有节点（m个）和
网络的m-1条边组成的树称为网
络的生成树，网络中不属于生成
树的边称为生成树的弦
4
2
3
1
4
2
3
1
4
2
3
1
4
2
3
1
4
2
3
1
4
2
3
1
4
2
3
1
网络的生成树的变换
4
2
3
1
■网络的一个生成树，增加一
条弦，形成唯一的圈，去掉生
成树的一条边，得到一个新的
网络的生成树
4
2
3
1
4
2
3
1 4
2
3
1
生成树2 生成树3生成树1
//
//
网络的生成树和线性规划的关系
■网络的一个生成树对应于线性规划的一个基
■生成树上的边对应于线性规划的基变量
■生成树的弦对应于线性规划的非基变量
■生成树的变换对应于线性规划单纯形法的进
基和离基变换
网络最小费用流问题
b2=-2 b4=3
b3=5 b5=-6
b6=-5b1=5
c24=5
c46=1
c13=3
c35=2
c56=4
c34=4
c12=6
2
3
4
5
61
需求节点
供应节点
cij 单位流量的费用
初始基础可行解—生成树
b6=-5
b2=-2 b4=3
b3=5 b5=-6
b1=5
x13=3
x46=3
x35=8
x56=2
x12=2
2
3
4
5
61
确定非基变量x24和x34
b2=-2
b6=-5
b3=5 b5=-6
b1=5
c24=5
c46=1
c13=3
c35=2
c56=4
c34=4
c12=6
2
3
4
5
61
b4=3
求x24的检验数z24-c24 闭回路法
z24 -c24 =(-c46+c56+c35+c13-c12)-c24=(-1+4+2+3-6)-5=-3
b2=-2 b4=3
b3=5 b5=-6
b6=-5b1=5
c24=5
c46=1
c13=3
c35=2
c56=4
c12=6
2
3
4
5
61
求x34的检验数z34 -c34 闭回路法
z34 -c34 =(-c46+c56+c35)-c34=(-1+4+2)-4=+1，x34进基
b2=-2 b4=3
b3=5 b5=-6
b6=-5b1=5
c46=1
c13=3
c35=2
c56=4
c34=4
c12=6
2
3
4
5
61
变量x34进基，确定离基变量
min{x56,x35}=min{2,8}=2, x56离基，调整流量，进行基变换
b2=-2 b4=3
b3=5 b5=-6
b6=-5b1=5
x46=3
x13=3
x35=8
x56=2
x34=0
x12=2
2
3
4
5
61
确定非基变量x24和x56
b2=-2 b4=3
b3=5 b5=-6
b6=-5b1=5
x46=5
x13=3
x35=6
x34=2
x12=2
2
3
4
5
61
计算x24和x56的检验数z24 -c24 、z56-
c56
z24 -c24 =(c34+c13-c12)-c24=(4+3-6)-5= -4
z56 -c56 =(c46+c34-c35)-c56=(1+4-2)-4= -1，获得最优解
b2=-2 b4=3
b3=5 b5=-6
b6=-5b1=5
c24=5
c46=1
c13=3
c35=2
c56=4
c34=4
c12=6
2
3
4
5
61
最优解
最优解的目标函数值为：min
z=62+33+42+26+15=46
b2=-2 b4=3
b3=5 b5=-6
b6=-5b1=5
x46=5
x13=3
x35=6
x34=2
x12=2
2
3
4
5
61
网络最大流问题
2
3
5
4
6
71
ff
u25=6
u42=2 u45=4
u23=3
u13=7 u34=4 u46=3
u36=1
u65=7
u57=9
u67=8
u12=8
边的容量和流量
容量uij，流量xij
可行流
满足以下条件的流称为可行流：
1、每一个节点流量平衡
2、0≤xij ≤uij
边的容量和流量、可行流
21
xij=5
uij=5
21
xij=3
uij=5
饱和边、不饱和边、流量的间隙
（1，2）是饱和的
2、如果xij<uij，边从i到j的方向是不饱和的；
（1，2）是不饱和的
间隙为12=u12-x12=5-3=2
1、如果xij=uij，边从i到j的方向是饱和的；
21
xij=0
uij=5
21
xij=5
uij=5
3、如果xij=0，边从j到i的方向是饱和的；
（2，1）是饱和的
如果xij>0，边从j到i的方向是不饱和的；
（2，1）是不饱和的
间隙为12=x12=5
给出一个初始的可行流xij=0
2
3
5
4
6
71
f=0f=0
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=0
x=0
x=0x=0
x=0
x=0
x=0
x=0
x=0
x=0
x=0
x=0
找到所有的不饱和边，以及各边可以
调整流量的方向
2
3
5
4
6
71
f=0f=0
u=6
u=2 u=4
u=3
u=7
u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=0
x=0
x=0
x=0
x=0
x=0
x=0
x=0
x=0
x=0
x=0
x=0
找到一条从1到7的不饱和链
链的间隙为： = min{8,3,1,8}=1
调整链的流量：xij’=xij+
2
3
5
4
6
71
f=0f=0
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=0
x=0
x=0x=0
x=0
x=0
x=0
x=0
x=0
x=0
x=0
=3
=1
=8
=8
x=0
调整流量，f=1。继续求出网络的不饱
和边
2
3
5
4
6
71
f=1f=1
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=0
x=0
x=0x=0
x=0
x=0
x=0
x=0
x=1
x=1
x=1
x=1
求出一条从1到7的不饱和链
2
3
5
4
6
71
f=1f=1
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=0
x=0
x=0x=0
x=0
x=0
x=0
x=0
x=1
x=1
x=1
x=1
=1
=6
=9
=7
=min {7,1,6,9}=1, 调整流量 xij’=xij+1, f’=f+1=2
调整流量，继续求出网络的不饱和边
2
3
5
4
6
71
f=2f=2
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=1
x=0
x=0x=1
x=0
x=0
x=0
x=1
x=1
x=1
x=1
x=0
求出一条从1到7的不饱和链
2
3
5
4
6
71
f=2f=2
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=1
x=0
x=0x=1
x=0
x=0
x=0
x=1
x=1
x=1
x=1
x=0
=5
=8
=7
=min {7,5,8}=5, 调整流量 xij’=xij+5, f’=f+5=2+5=7
调整流量，继续求出网络的不饱和边
2
3
5
4
6
71
f=7f=7
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=6
x=0
x=0x=1
x=0
x=0
x=0
x=6
x=1
x=1
x=6
x=0
2
3
5
4
6
71
f=7f=7
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=6
x=0
x=0x=1
x=0
x=0
x=0
x=6
x=1
x=1
x=6
x=0
求出一条从1到7的不饱和链
=min {6,7,4,3}=3, 调整流量 xij’=xij+3, f’=f+3=7+3=10
=4
=4
=3
=6
调整流量，继续求出网络的不饱和边
2
3
5
4
6
71
f=10f=10
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=6
x=0
x=3x=4
x=3
x=0
x=0
x=9
x=1
x=1
x=6
x=0
求出一条从1到7的不饱和链
2
3
5
4
6
71
f=10
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=6
x=0
x=3x=4
x=3
x=0
x=0
x=9
x=1
x=1
x=6
x=0
f=10
=1
=3
=7=3
=min {3,1,3,7}=1, 调整流量 xij’=xij+1, f’=f+1=10+1=11
调整流量，继续求出网络的不饱和边
2
3
5
4
6
71
f=11f=11
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=6
x=0
x=4x=5
x=3
x=1
x=0
x=9
x=2
x=1
x=6
x=0
已找不到一条从1到7的不饱和链，从1开始可以
到达的节点为1，2，3
已求得最大流
2
3
5
4
6
71
f=11
u=6
u=2 u=4
u=3
u=7 u=4 u=3
u=1
u=7
u=9
u=8
u=8
x=6
x=0
x=4x=5
x=3
x=1
x=0
x=9
x=2
x=1
x=6
x=0
f=11
最大流f=11，最小割集为（2,5）（3,4）（3,5）
u25+u34+u35=6+4+1=11
最短路径问题
2 3
7
1
8
4 5
6
6
1
3
4
10
5 2
7
5 9
3 4
6
8
2
求从1到8的最短路径
2 3
7
1
8
4 5
6
6
1
3
4
10
5 2
7
5 9
3 4
6
8
2
X={1}, w1=0
min {c12,c14,c16}=min {0+2,0+1,0+3}=min {2,1,3}=1
X={1,4}, w4=1
w1=0
w1=0
2 3
7
1
8
4 5
6
6
1
3
4
10
5 2
7
5 9
3 4
6
8
2
X={1,4}
min {c12,c16,c42,c47}=min {0+2,0+3,1+10,1+2}=min {2,3,11,3}=2
X={1,2,4}, w2=2
w1=0
w4=1
w2=2
2 3
7
1
8
4 5
6
6
1
3
4
10
5 2
7
5 9
3 4
6
8
2
X={1,2,4}
min {c13,c23,c25,c47}=min {0+3,2+6,2+5,1+2}=min {3,8,7,3}=3
X={1,2,4,6}, w6=3
w2=2
w4=1
w1=0
w6=3
2 3
7
1
8
4 5
6
6
1
3
4
10
5 2
7
5 9
3 4
6
8
2
X={1,2,4,6}
min {c23,c25,c47,c67}=min {2+6,2+5,1+2,3+4}=min {8,7,3,7}=3
X={1,2,4,6,7}, w7=3
w2=2
w4=1
w1=0
w6=3 w7=3
2 3
7
1
8
4 5
6
6
1
3
4
10
5 2
7
5 9
3 4
6
8
2
X={1,2,4,6,7}
min {c23,c25,c75,c78}=min {2+6,2+5,3+3,3+8}=min {8,7,6,11}=6
X={1,2,4,5,6,7}, w5=6
w2=2
w4=1
w1=0
w6=3 w7=3
w5=6
2 3
7
1
8
4 5
6
6
1
3
4
10
5 2
7
5 9
3 4
6
8
2
X={1,2,4,6,7}
min {c23,c53,c58,c78}=min {2+6,6+9,6+4,3+8}=min {8,15,10,11}=8
X={1,2,3,4,5,6,7}, w3=8
w2=2
w4=1
w1=0
w6=3 w7=3
w5=6
w3=8
2 3
7
1
8
4 5
6
6
1
3
4
10
5 2
7
5 9
3 4
6
8
2
X={1,2,3,4,6,7}
min {c38,c58,c78}=min {8+6,6+4,3+7}=min {14,10,11}=10
X={1,2,3,4,5,6,7,8}, w8=10
w2=2
w4=1
w1=0
w6=3 w7=3
w5=6
w3=8
w8=10
2 3
7
1
8
4 5
6
6
1
3
4
10
5 2
7
5 9
3 4
6
8
2
X={1,2,3,4,6,7,8}
1到10的最短路径为{1，4，7，5，8}，长度为10。
w2=2
w4=1
w1=0
w6=3 w7=3
w5=6
w3=8
w8=10
第六章 动态规划
最短路径问题
资源分配问题
背包问题
机器负荷分配问题
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
一、最短路径问题
求从A到E的最短路径
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f5(E)=0
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D1)=5
f5(E)=0
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f4(D1)=5
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f3(C1)=8
f4(D1)=5
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0f3(C2)=7
f4(D1)=5
f3(C1)=8
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f3(C1)=8
f3(C2)=7
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B1)=20
f3(C2)=7
f3(C1)=8
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B2)=14 f3(C2)=7
f3(C1)=8f2(B1)=21
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B3)=19
f3(C2)=7
f3(C1)=8f2(B1)=21
f2(B2)=14
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B3)=19
f3(C2)=7
f3(C1)=8
f1(A)=19 f2(B2)=14
f2(B1)=21
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B3)=19
f3(C2)=7
f3(C1)=8
f1(A)=19 f2(B2)=14
f2(B1)=21
状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态
A （ A，B2） B2
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B3)=19
f3(C2)=7
f3(C1)=8
f1(A)=19 f2(B2)=14
f2(B1)=21
状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态
A （ A，B2） B2 （B2，C1） C1
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B3)=19
f3(C2)=7
f3(C1)=8
f1(A)=19 f2(B2)=14
f2(B1)=21
状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态
A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
EC2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B3)=19
f3(C2)=7
f3(C1)=8
f1(A)=19 f2(B2)=14
f2(B1)=21
状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态
A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E
从A到E的最短路径为19，路线为A→B 2→C1 →D1 →E
2、资源分配问题
4万元资金，如何分配给A、B、C三个项目，使总效益最大
4万元
2万元
1万元
0万元
4万元
2万元
1万元
0万元
4万元
2万元
1万元
0万元
4万元
x1 A项目 x2 B项目 x3 C项目 x4
3万元 3万元 3万元
0
f
