运筹学演示课件目 录第一章 线性规划第二章 对偶第三章 整数规划第四章 运输问题第五章 网络优化第六章 动态规划第七章 排 队 论第一章 线性规划线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解、基础可行解单纯形表线性规划的矩阵表示线性规划模型线性规划模型的结构目标函数,max,min
约束条件,≥,=,≤
变量符号：,≥0,unr,≤0
线性规划的标准形式目标函数,min
约束条件,=
变量符号,≥0
unr,0)(X
b),(AX.t.s
XCzm a x ( m in ) T
0X
bAX.t.s
XCzm in T
线性规划的图解
max z=x1+3x2
s.t,x1+ x2≤6
-x1+2x2≤8
x1 ≥0,x2≥0 可行域目标函数等值线最优解
6
4
-8
6
0
x1
x2
可行域的性质
● 线性规划的可行域是凸集
● 线性规划的最优解在极点上凸集 凸集 不是凸集极点线性规划的基本概念
● 线性规划的 基矩阵,基变量,非基变量
=
=
目标函数约束条件行列式 ≠0
基矩阵右边常数
m ax z= 2x 1 +3 x 2 +x 3
s,t,x 1 +3 x 2 +x 3? 15
2x 1 +3 x 2 -x 3? 18
x 1 -x 2 +x 3? 3
x 1,x 2,x 3? 0
m in z’ = -2x 1 -3x 2 -x 3
st x 1 +3x 2 +x 3 +x 4 =15
2x 1 +3x 2 -x 3 +x 5 =18
x 1 -x 2 +x 3 +x 6 =3
x 1,x 2,x 3,x 4,x 5,x 6? 0
x 1 +3 x 2 +x 3 =1 5
2x 1 +3 x 2 -x 3 =1 8
x 1 -x 2 +x 3 =3
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基础解为（ x1,x2,x3,x4,x5,x6） =（ 5,3,1,0,0,0）
是基础可行解，表示可行域的一个极点。
目标函数值为,z=20
x 1 +3x 2 +x 4 =15
2x 1 +3x 2 =18
x 1 -x 2 =3
基变量 x1,x2,x4,非基变量 x3,x5,x6
基础解为
（ x1,x2,x3,x4,x5,x6） =（ 27/5,12/5,0,2/5,0,0）
是基础可行解，表示可行域的一个极点。
目标函数值为,z=18
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
x 1 +3x 2 =15
2x 1 +3x 2 +x 5 =18
x 1 -x 2 =3
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
基变量 x1,x2,x5,非基变量 x3,x4,x6
基础解为（ x1,x2,x3,x4,x5,x6） =（ 6,3,0,0,-3,0）
是基础解，但不是可行解，不是一个极点。
x 1 +3x 2 =15
2x 1 +3x 2 =18
x 1 -x 2 +x 6 =3
基变量 x1,x2,x6,非基变量 x3,x4,x5
基础解为（ x1,x2,x3,x4,x5,x6） =（ 3,4,0,0,0,4）
是基础可行解，表示可行域的一个极点。
目标函数值为,z=18
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 +x 4 =1 5
3x 2 -x 3 =1 8
-x 2 +x 3 =3
基变量 x2,x3,x4,非基变量 x1,x5,x6
基础解为
（ x1,x2,x3,x4,x5,x6） =（ 0,21/2,27/2,-30,0,0）
是基础解，但不是可行解。
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 =1 5
3x 2 -x 3 +x 5 =1 8
-x 2 +x 3 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基础解为（ x1,x2,x3,x4,x5,x6） =（ 0,3,6,0,15,0）
是基础可行解，表示可行域的一个极点。
目标函数值为,z=15
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 =15
3x 2 -x 3 =18
-x 2 +x 3 +x 6 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基础解为
（ x1,x2,x3,x4,x5,x6） =（ 0,11/2,-3/2,0,0,10）
是基础解但不是可行解。
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
=
目标函数约束条件基矩阵右边常数进基变量、离基变量、基变换
=
基变量
=
进基变量离基变量目标函数约束条件右边常数=
=
目标函数约束条件新的基矩阵右边常数=
=
进基变量离基变量目标函数约束条件基矩阵
=
=
目标函数约束条件新的基矩阵右边常数=
基础解、基础可行解
max z=x1+3x2 D
s.t,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
O A B C D E
基变量 x 3 x 4 x 1 x 4 x 1 x 2 x 2 x 3 x 2 x 4 x 1 x 3
非基变量 x 1 x 2 x 2 x 3 x 3 x 4 x 1 x 4 x 1 x 3 x 2 x 4
x j < 0 -- -- -- -- x 4 x 1
基础可行解 是 是 是 是 否 否几何概念 代数概念约束直线 满足一个等式约束的解约束半平面 满足一个不等式约束的解约束半平面的交集：
凸多边形满足一组不等式约束的解约束直线的交点 基础解可行域的极点 基础可行解目标函数等值线：
一组平行线目标函数值等于一个常数的解单纯形表
m ax z= 3x 1 + 4x 2 -x 3 + 2x 4
s,t,x 1 +x 2 +x 3 +x 4 ≦ 25
x 1 + 2x 2 +x 3 + 2x 4 ≦ 36
x 1 x 2 x 3 x 4 ≧ 0
m in z ' = - 3x 1 - 4 x 2 +x 3 - 2 x 4
s,t,x 1 +x 2 +x 3 +x 4 +x 5 = 25
x 1 + 2 x 2 +x 3 + 2 x 4 +x 6 = 3 6
x 1 x 2 x 3 x 4 x 5 x 6 ≧ 0
求解线性规划问题写成标准化形式
z' x 1 x 2 x 3 x 4 x 5 x 6 R H S
z' 1 3 4 -1 2 0 0 0
0 1 1 1 1 1 0 25
0 1 2 1 2 0 1 36
写出单纯形表
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进基，
z' x 1 x 2 x 3 x 4 x 5 x 6 R H S
z' 1 3 4 -1 2 0 0 0
x 5 0 1 1 1 1 1 0 25
x 6 0 1 2 1 2 0 1 36
z' x 1 x 2 x 3 x 4 x 5 x 6 R H S
z' 1 1 0 -3 -2 0 -2 - 7 2
x 5 0 1 / 2 0 1 / 2 0 1 - 1 / 2 7
x 2 0 1 / 2 1 1 / 2 1 0 1 / 2 18
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
m ax z= 2x 1 +3x 2 +x 3
st x 1 +3x 2 +x 3? 15
2x 1 +3x 2 -x 3? 18
x 1 -x 2 +x 3? 3
x 1,x 2,x 3? 0
m in z’ = -2x 1 -3x 2 -x 3
st x 1 +3x 2 +x 3 +x 4 =15
2x 1 +3x 2 -x 3 +x 5 =18
x 1 -x 2 +x 3 +x 6 =3
x 1,x 2,x 3,x 4,x 5,x 6? 0
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 2 3 1 0 0 0 0
x 4 0 1 3 1 1 0 0 15 1 5 /3
x 5 0 2 3 -1 0 1 0 18 1 8 /3
x 6 0 1 -1 1 0 0 1 3 -
m in z’ = -2x 1 -3x 2 -x 3
st x 1 +3x 2 +x 3 +x 4 =15
2x 1 +3x 2 -x 3 +x 5 =18
x 1 -x 2 +x 3 +x 6 =3
x 1,x 2,x 3,x 4,x 5,x 6? 0
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 2 3 1 0 0 0 0
x 4 0 1 [ 3 ] 1 1 0 0 15 1 5 /3
x 5 0 2 3 -1 0 1 0 18 1 8 /3
x 6 0 1 -1 1 0 0 1 3 -
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 1 0 0 -1 0 0 - 1 5
x 2 0 1 /3 1 1 /3 1 /3 0 0 5 5 /1 /3
x 5 0 [ 1 ] 0 -2 -1 1 0 3 3 /1
x 6 0 4 /3 0 4 /3 1 /3 0 1 8 8 /4 /3
z’ x 1 x 2 x 3 x 4 x 5 x 6 RHS
z’ 1 0 0 2 0 -1 0 -18
x 2 0 0 1 1 2/3 -1/3 0 4 4/1
x 1 0 1 0 -2 -1 1 0 3 --
x 6 0 0 0 [ 4] 5/3 -4/3 1 4 4/4
z’ x 1 x 2 x 3 x 4 x 5 x 6 RHS
z’ 1 0 0 2 0 -1 0 -18
x 2 0 0 1 1 2/3 -1/3 0 4 4/1
x 1 0 1 0 -2 -1 1 0 3 --
x 6 0 0 0 [ 4] 5/3 -4/3 1 4 4/4
x 3 进基,x 6 离基
z’ x 1 x 2 x 3 x 4 x 5 x 6 RH S
z’ 1 0 0 0 -5/6 -1/3 -1/2 -20
x 2 0 0 1 0 1/4 0 -1/4 3
x 1 0 1 0 0 -1/6 1/3 1/2 5
x 3 0 0 0 1 5/12 -1/3 1/4 1
最优解,( x 1,x 2,x 3,x 4,x 5 x 6 )=(5,3,1,0,0,0),m ax z =20
线性规划的矩阵表示
=
=
=
=
=
z X B X N RHS
z 1 -C B
T
-C N
T
0
X B 0 I B
-1
N B
-1
b
z X RHS
z 1 -C T 0
0 A b
z X B X N RHS
z 1 -C B
T
-C N
T
0
0 B N b
z X
B
X
N
R HS
z 1 0
T
C
B
T
B
-1
N- C
N
T
C
B
T
B
-1
b
X
B
0 I B
-1
N B
-1
b
z X
B
… x
j
… RHS
z 1 -C
B
T
… - c
j
… 0
0 B … a
j
… b
z X
B
… x
j
… RHS
z 1 0
T
… C
B
T
B
-1
a
j
-c
j
… C
B
T
B
-1
b
0 I … B
-1
a
j
… B
-1
b
CBTB-1aj-cj=zj-cj 称为非基变量的检验数（ Reduced Cost）
B-1aj=Yj,B-1b=,CBTB-1b=z0b
z X
B
… x
j
… RHS
z 1 0
T
… z
j
-c
j
… z
0
X
B
0 I … Y
j
… b
z X
B
… x
j
… RHS
z 1 0
T
… C
B
T
B
-1
a
j
-c
j
… C
B
T
B
-1
b
0 I … B
-1
a
j
… B
-1
b
第二章 对偶线性规划对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的关系 — 互补松弛关系最优解的 Kuhn-Tucher条件对偶可行基对偶单纯形法对偶的经济解释
DUAL
一、对偶的定义原始问题
min z=CTX
s.t,AX≥b
X ≥0
对偶问题
max y=bTW
s.t,ATW≤C
W ≥0
≥
min
bA
CT
CAT
bT
≤
max
m
n
m
n
二、对偶问题的性质
1、对偶的对偶就是原始问题
max z’=-CTX
s.t,-AX≤-b
X ≥0
min y=-bTW
s.t,-ATW≥-C
W ≥0
max y=bTW
s.t,ATW≤C
W ≥0
min z=CTX
s.t,AX≥b
X ≥0
对偶的定义对偶的定义
min z=CTX
s.t,AX≤b
X ≥0
max y=bTW
s.t,ATW≤C
W ≤0
2、其他形式问题的对偶
min z=CTX
s.t,AX≥b
X ≥0
max y=bTW
s.t,ATW≤C
W ≥0
min z=CTX
s.t,AX=b
X ≥0
max y=bTW
s.t,ATW≤C
W,unr
三、原始对偶关系
1、可行解的目标函数值之间的关系设 XF,WF分别是原始问题和对偶问题的可行解
z=CTXF ≥WTAXF ≥WTb=y
2,最优解的目标函数值之间的关系设 Xo,Wo分别是原始问题和对偶问题的最优解
z=CTXo=WoTAXo=WoTb=y
3、原始问题和对偶问题最优解之间的互补松弛关系
min z=CTX
s.t,AX-XS=b
X,XS≥0
max y=bTW
s.t,ATW+WS=C
W,WS≥0
min z=CTX
s.t,AX≥b
X ≥0
max y=bTW
s.t,ATW≤C
W≥0对偶引进松弛变量 引进松弛变量
XTWS=0 WTXS=0
互补松弛关系
X,Xs W,Ws
min z=CTX
s.t,AX-XS=b
X,XS ≥0
max y=bTW
s.t,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
s.t,AX≥b
X ≥0
min z=CTX
s.t,AX ≤ b
X ≥0
max z=CTX
s.t,AX ≥ b
X ≥0
max z=CTX
s.t,AX ≤ b
X ≥0
（ 2）
（ 3） （ 4）
（ 1）
单纯形表和对偶 (1)
min z=CTX
s.t,AX-XS=b
X,XS≥0
max y=bTW
s.t,ATW+WS=C
W,WS≥0
min z=CTX
s.t,AX≥b
X ≥0
max y=bTW
s.t,ATW≤C
W≥0
对偶问题原始问题引进松弛变量引进松弛变量
z X X S RH S
1 -W S
T
-W
T
C B
T
B
-1
b
0 B
-1
A -B
-1
B
-1
b
z X X S RH S
1 -C
T
0
T
0
0 A -I b
min z=CTX
s.t,AX-XS=b
X,XS≥0
max y=bTW
s.t,ATW+WS=C
W,WS≥0
z X X S RH S
1 C B
T
B
-1
A- C
T
-C B
T
B
-1
C B
T
B
-1
b
0 B
-1
A -B
-1
B
-1
b
WT=CBTB-1
WST=CT-WTA
min z=CTX
s.t,AX+XS=b
X,XS≥0
max y=bTW
s.t,ATW+WS=C
W ≤0,WS≥0
min z=CTX
s.t,AX ≤ b
X ≥0
max y=bTW
s.t,ATW≤C
W ≤ 0
单纯形表和对偶 (2)
对偶问题原始问题引进松弛变量引进松弛变量
z X X S RH S
1 -W S
T
W
T
C B
T
B
-1
b
0 B
-1
A B
-1
B
-1
b
z X X S RH S
1 -C
T
0
T
0
0 A I b
min z=CTX
s.t,AX+XS=b
X,XS≥0
max y=bTW
s.t,ATW+WS=C
W ≤0,WS≥0
z X X S RH S
1 C B
T
B
-1
A- C
T
C B
T
B
-1
C B
T
B
-1
b
0 B
-1
A B
-1
B
-1
b
WT=CBTB-1
WST=CT-WTA
max z=CTX
s.t,AX-XS=b
X,XS≥0
max y=bTW
s.t,ATW-WS=C
W ≤0,WS≥0
max z=CTX
s.t,AX ≥ b
X ≥0
min y=bTW
s.t,ATW ≥ C
W ≤ 0
单纯形表和对偶 (3)
对偶问题原始问题引进松弛变量引进松弛变量
z X X S RH S
1 W S
T
-W
T
C B
T
B
-1
b
0 B
-1
A -B
-1
B
-1
b
z X X S RH S
1 -C
T
0
T
0
0 A -I b
max z=CTX
s.t,AX-XS=b
X,XS≥0
min y=bTW
s.t,ATW-WS=C
W ≤0,WS≥0
z X X S RH S
1 C B
T
B
-1
A- C
T
-C B
T
B
-1
C B
T
B
-1
b
0 B
-1
A -B
-1
B
-1
b
WT=CBTB-1
WST=WTA- CT
max z=CTX
s.t,AX+XS=b
X,XS≥0
max y=bTW
s.t,ATW-WS=C
W,WS≥0
max z=CTX
s.t,AX ≤ b
X ≥0
min y=bTW
s.t,ATW ≥ C
W ≥ 0
单纯形表和对偶 (4)
对偶问题原始问题引进松弛变量引进松弛变量
z X X S RH S
1 W S
T
W
T
C B
T
B
-1
b
0 B
-1
A B
-1
B
-1
b
z X X S RH S
1 -C
T
0
T
0
0 A I b
max z=CTX
s.t,AX+XS=b
X,XS≥0
min y=bTW
s.t,ATW-WS=C
W,WS≥0
z X X S RH S
1 C B
T
B
-1
A- C
T
C B
T
B
-1
C B
T
B
-1
b
0 B
-1
A B
-1
B
-1
b
WT=CBTB-1
WST=WTA- CT
2、对偶单纯形法（初始解原始不可行的问题）
0xxx
2xx2x
5xx3x2
4xxx.t.s
xx2x3zm i n
321
321
321
321
321
0xxxxxx
2xxx2x
5xxx3x2
4xxxx.t.s
xx2x3zm i n
654321
6321
5321
4321
321
0xxxxxx
2xxx2x2
5xxx3x2
4xxxx.t.s
xx2x3zm i n
654321
6321
5321
4321
321
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 -3 -2 -1 0 0 0 0
x
4
0 1 -1 1 1 0 0 4
x
5
0 2 -3 1 0 1 0 -5
x
6
0 -2 2 -1 0 0 1 -2
-3/ -2 -1/ -1
z x
1
x
2
x
3
x
4
x
5
x
6
R HS
z 1 -1 0 0 0 -4 -5 30
x
4
0 -1 0 0 1 1 2 -5
x
2
0 0 1 0 0 -1 -1 7
x
3
0 2 0 1 0 -2 -3 16
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 -1 -4 0 0 0 -1 2
x
4
0 -1 1 0 1 0 1 2
x
5
0 0 -1 0 0 1 1 -7
x
3
0 2 -2 1 0 0 -1 2
z x
1
x
2
x
3
x
4
x
5
x
6
R HS
z 1 0 0 0 -1 -5 -7 35
x
1
0 1 0 0 -1 -1 -2 5
x
2
0 0 1 0 0 -1 -1 7
x
3
0 0 0 1 2 0 1 6
已获得最优解：
（ 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、初始解原始、对偶都不可行的问题
0xxx
2xx2x
5xx3x2
4xxx.t.s
x2x2x3zm i n
321
321
321
321
321
0xxxxxx
2xxx2x
5xxx3x2
4xxxx.t.s
x2x2x3zm i n
654321
6321
5321
4321
321
0xxxxxx
2xxx2x2
5xxx3x2
4xxxx.t.s
x2x2x3zm i n
654321
6321
5321
4321
321
z x
1
x
2
x
3
x
4
x
5
x
6
R HS
z 1 -3 -2 2 0 0 0 0
x
4
0 1 -1 1 1 0 0 4
x
5
0 2 -3 1 0 1 0 -5
x
6
0 -2 2 -1 0 0 1 -2
解法 1：先解决原始可行性
z x
1
x
2
x
3
x
4
x
5
x
6
RH S
z 1 -7 0 0 0 2 4 -18
x
4
0 -1 0 0 1 1 2 -5
x
2
0 0 1 0 0 -1 -1 7
x
3
0 2 0 1 0 -2 -3 16
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 -7 2 0 0 0 2 -4
x
4
0 -1 1 0 1 0 1 2
x
5
0 0 -1 0 0 1 -7
x
3
0 2 -2 1 0 -1 2
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 0 0 0 -7 -5 -10 17
x
1
0 1 0 0 -1 -1 -2 5
x
2
0 0 1 0 0 -1 -1 7
x
3
0 0 0 1 2 0 1 6
在得到原始可行解时同时得到对偶可行解，已获得最优解：
（ 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
z x
1
x
2
x
3
x
4
x
5
x
6
RH S
z 1 -3 -2 2 0 0 0 0
x
4
0 1 -1 1 1 0 0 4
x
5
0 2 -3 1 0 1 0 -5
x
6
0 -2 2 -1 0 0 1 -2
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 -5 0 0 -2 0 0 -8
x
3
0 1 -1 1 1 0 0 4
x
5
0 1 -2 0 -1 1 0 -9
x
6
0 -1 1 0 1 0 1 2
解法 2：先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解
z x
1
x
2
x
3
x
4
x
5
x
6
R HS
z 1 0 0 0 -7 -5 -10 17
x
3
0 0 0 1 2 0 1 6
x
2
0 0 1 0 0 -1 -1 7
x
1
0 1 0 0 -1 -1 -2 5
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 -5 0 0 -2 0 0 -8
x
3
0 1/2 0 1 3/2 -1/2 0 17/ 2
x
2
0 -1/2 1 0 1/2 -1/2 0 9/2
x
6
0 -1/2 0 0 1/2 1/2 1 -5/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,原始问题是利润最大化的生产计划问题
0xxxxxx
bxxaxaxa
bxxaxaxa
bxxaxaxa.t.s
xcxcxczm a x
mn2n1nn21
mmnnmn22m11m
22nnn2222121
11nnn1212111
222211
单位产品的利润（ 元 /件）
产品产量（件）
总利润（元）
资源限量（吨）单位产品消耗的资源（吨 /件） 剩余的资源（ 吨）
消耗的资源（吨）
2,对偶问题
0wwwwww
cwwawawa
cwwawawa
cwwawawa.t.s
wbwbwbym i n
nm2m1mm21
nnmmmn2n21n1
22mm2m222112
11mm1m221111
mm2211
资源限量（吨）
资源价格（元 /吨）
总利润（元）
对偶问题是资源定价问题，对偶问题的最优解 w1,w2,...、
wm称为 m种资源的 影子价格（ Shadow Price）
原始和对偶问题都取得最优解时,最大利润 max z=min y
3,资源影子价格的性质
■ 影子价格越大，说明这种资源越是相对紧缺
■ 影子价格越小，说明这种资源相对不紧缺
■ 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于 0
种资源的边际利润第种资源的增量第最大利润的增量 iibzw
i
o
o
i
mmii2211 wbwbwbwbyz
mmiii2211 wbw)bb(wbwbzz
ii wbz
w1
w2
wm
4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润
mmjiij2j21j1 wawawawa
增加单位资源可以增加的利润减少一件产品可以节省的资源
0xxxx
bxaxaxaxa
bxaxaxaxa
bxaxaxaxas,t,
xcxcxcxczm a x
nj21
mnmnjmj2m21m1
2n2nj2j222121
1n1nj1j212111
nnjj2211
机会成本 利润差额成本
0wwwwww
cwwawawa
cwwawawa
cwwawawa.t.s
wbwbwbym i n
nm2m1mm21
nnmmmn2n21n1
22mm2m222112
11mm1m221111
mm2211
5、产品的差额成本（ Reduced Cost）
差额成本 =机会成本 - 利润
jjTjmjmj22j11jm caWc)awawaw(w
5、互补松弛关系的经济解释
0x0w
0w0x
0wx
0w0x
0x0w
0xw
jjm
jmj
jmj
iin
ini
ini
在利润最大化的生产计划中
（ 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
供应量供应地 运价需求量需求地
67
53
84
27
59
10
6
运输问题线性规划模型
0xxxxxxxxxxxx
13xxx
12xxx
13xxx
22xxx
19xxxx
27xxxx
14xxxxs,t,
x6x10x9x5x7x2x4x8x3x5x7x6zm i n
343332312423222114131211
342414
332313
322212
312111
34333231
24232221
14131211
343332312423222114131211
供应地约束需求地约束运输问题的表格表示
1 2 3 4
6 7 5 3
1
x
11
x
12
x
13
x
14
14
8 4 2 7
2
x
21
x
22
x
23
x
24
27
5 9 10 6
3
x
31
x
32
x
33
x
34
19
22 13 12 13
初始基础可行解 — 西北角法
1 2 3 4
6 7 5 3
1
14
8 4 2 7
2
27
5 9 10 6
3
19
22 13 12 13
8 13
13
14
6
6
1 2 3 4
6 7 5 3
1 14
8 4 2 7
2
12
27 15
5 9 10 6
3 19
22 13 12 13
0
初始基础可行解 — 最小元素法（ 1）
最小元素法（ 2）
1 2 3 4
6 7 5 3
1
13
14 1
8 4 2 7
2
12
27 15
5 9 10 6
3 19
22 13 12 13
0 0
最小元素法（ 3）
1 2 3 4
6 7 5 3
1
13
14 1
8 4 2 7
2
13 12
27 2
5 9 10 6
3 19
22 13 12 13
0 0 0
最小元素法（ 4）
1 2 3 4
6 7 5 3
1
13
14 1
8 4 2 7
2
13 12
27 2
5 9 10 6
3
19
19 0
22 13 12 13
3 0 0 0
最小元素法（ 5）
1 2 3 4
6 7 5 3
1
1 13
14 0
8 4 2 7
2
13 12
27 2
5 9 10 6
3
19
19 0
22 13 12 13
2 0 0 0
最小元素法（ 6）
1 2 3 4
6 7 5 3
1
1 13
14 0
8 4 2 7
2
2 13 12
27 0
5 9 10 6
3
19
19 0
22 13 12 13
0 0 0 0
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
非基变量 xij的检验数 zij-cij— 闭回路法 (1)
z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
闭回路法 (2)
z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5
-5
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
闭回路法 (3)
z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7
-7-5
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
闭回路法 (4)
z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9
-9
-5 -7
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
闭回路法 (5)
z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11
+11
-5 -7
-9
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
闭回路法 (6)
z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3
+3
-5 -7
-9
+11
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
5 9 10 6
3
6
13
u
3
v
1
v
2
v
3
v
4
=0
非基变量 xij的检验数 zij-cij— 对偶变量法 (1)
v4=0
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
5 9 10 6
3
6
13
u
3
=6
v
1
v
2
v
3
v
4
=0
对偶变量法 (2)
u3+v4=c34 u3=6
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
5 9 10 6
3
6
13
u
3
=6
v
1
v
2
v
3
=4 v
4
=0
对偶变量法 (3)
u3+v3=c33 v3=4
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
v
2
v
3
=4 v
4
=0
对偶变量法 (4)
u2+v3=c23 u2=-2
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
v
2
=6 v
3
=4 v
4
=0
对偶变量法 (5)
u2+v2=c22 v2=6
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (6)
u2+v1=c21 v1=10
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (7)
u1+v1=c11 u1=-4
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (8)
z12-c12=u1+v2-c12=(-4)+6-7=-5
-5
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (9)
z13-c13=u1+v3-c13=(-4)+4-5=-5
-5-5
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (10)
z14-c14=u1+v4-c14=(-4)+0-3=-7
-7-5 -5
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (11)
z24-c24=u2+v4-c24=(-2)+0-7=-9
-9
-5 -5 -7
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (12)
z31-c31=u3+v1-c31=6+10-5=11
11
-5 -5 -7
-9
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (13)
z32-c32=u3+v2-c32=6+6-9=+3
+3
-5 -5 -7
-9
11
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
选择进基变量,确定离基变量
x31进基,min{x21,x33}=min{8,6}=6,x33离基
+3
-5 -5 -7
-9
11
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
2 13 12
27
5 9 10 6
3
6
13
19
22 13 12 13
调整运量,重新计算检验数,确定进基、离基变量
x14进基,min{x11,x34}=min{14,13}=13,x34离基
-11
-5 -5 +4
+2
-8
1 2 3 4
6 7 5 3
1
1 13
14
8 4 2 7
2
2 13 12
27
5 9 10 6
3
19
19
22 13 12 13
调整运量,重新计算检验数所有 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=6?2+3?3+4?2+2?6+1?5=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
505)E(f)ED(d)D(f 5114
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
202)E(f)ED(d)D(f 5224
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
11
2421
1411
13
DC8
11
8
m i n
29
53
m i n
)D(f)D,C(
)D(f)D,C(
m i n)C(f
最优决策
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
22
2422
1412
23
DC7
7
11
m i n
25
56
m i n
)D(f)D,C(
)D(f)D,C(
m i n)C(f
最优决策
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
23
2423
1413
33
DC12
12
13
m i n
210
58
m i n
)D(f)D,C(
)D(f)D,C(
m i n)C(f
最优决策
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
11
3331
2321
1311
12
CB
20
22
21
20
m i n
1210
714
812
m i n
)C(f)C,B(
)C(f)C,B(
)C(f)C,B(
m i n)B(f
最优决策
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
12
3332
2322
1312
22
CB
14
16
17
14
m i n
124
710
86
m i n
)C(f)C,B(
)C(f)C,B(
)C(f)C,B(
m i n)B(f
最优决策
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
23
3333
2323
1313
32
CB
19
23
19
21
m i n
1211
712
813
m i n
)C(f)C,B(
)C(f)C,B(
)C(f)C,B(
m i n)B(f
最优决策
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
323
222
121
1
BA
19
20
19
23
m i n
191
145
212
m i n
)B(f)B,A(
)B(f)B,A(
)B(f)B,A(
m i n)A(f
最优决策
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→C 1 →D 1 →E
2、资源分配问题项目投入资金
A B C
1 万元 15 万吨 13 万吨 11 万吨
2 万元 28 万吨 29 万吨 30 万吨
3 万元 40 万吨 43 万吨 45 万吨
4 万元 51 万吨 55 万吨 58 万吨
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
约束条件,≥,=,≤
变量符号：,≥0,unr,≤0
线性规划的标准形式目标函数,min
约束条件,=
变量符号,≥0
unr,0)(X
b),(AX.t.s
XCzm a x ( m in ) T
0X
bAX.t.s
XCzm in T
线性规划的图解
max z=x1+3x2
s.t,x1+ x2≤6
-x1+2x2≤8
x1 ≥0,x2≥0 可行域目标函数等值线最优解
6
4
-8
6
0
x1
x2
可行域的性质
● 线性规划的可行域是凸集
● 线性规划的最优解在极点上凸集 凸集 不是凸集极点线性规划的基本概念
● 线性规划的 基矩阵,基变量,非基变量
=
=
目标函数约束条件行列式 ≠0
基矩阵右边常数
m ax z= 2x 1 +3 x 2 +x 3
s,t,x 1 +3 x 2 +x 3? 15
2x 1 +3 x 2 -x 3? 18
x 1 -x 2 +x 3? 3
x 1,x 2,x 3? 0
m in z’ = -2x 1 -3x 2 -x 3
st x 1 +3x 2 +x 3 +x 4 =15
2x 1 +3x 2 -x 3 +x 5 =18
x 1 -x 2 +x 3 +x 6 =3
x 1,x 2,x 3,x 4,x 5,x 6? 0
x 1 +3 x 2 +x 3 =1 5
2x 1 +3 x 2 -x 3 =1 8
x 1 -x 2 +x 3 =3
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基础解为（ x1,x2,x3,x4,x5,x6） =（ 5,3,1,0,0,0）
是基础可行解，表示可行域的一个极点。
目标函数值为,z=20
x 1 +3x 2 +x 4 =15
2x 1 +3x 2 =18
x 1 -x 2 =3
基变量 x1,x2,x4,非基变量 x3,x5,x6
基础解为
（ x1,x2,x3,x4,x5,x6） =（ 27/5,12/5,0,2/5,0,0）
是基础可行解，表示可行域的一个极点。
目标函数值为,z=18
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
x 1 +3x 2 =15
2x 1 +3x 2 +x 5 =18
x 1 -x 2 =3
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
基变量 x1,x2,x5,非基变量 x3,x4,x6
基础解为（ x1,x2,x3,x4,x5,x6） =（ 6,3,0,0,-3,0）
是基础解，但不是可行解，不是一个极点。
x 1 +3x 2 =15
2x 1 +3x 2 =18
x 1 -x 2 +x 6 =3
基变量 x1,x2,x6,非基变量 x3,x4,x5
基础解为（ x1,x2,x3,x4,x5,x6） =（ 3,4,0,0,0,4）
是基础可行解，表示可行域的一个极点。
目标函数值为,z=18
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 +x 4 =1 5
3x 2 -x 3 =1 8
-x 2 +x 3 =3
基变量 x2,x3,x4,非基变量 x1,x5,x6
基础解为
（ x1,x2,x3,x4,x5,x6） =（ 0,21/2,27/2,-30,0,0）
是基础解，但不是可行解。
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 =1 5
3x 2 -x 3 +x 5 =1 8
-x 2 +x 3 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基础解为（ x1,x2,x3,x4,x5,x6） =（ 0,3,6,0,15,0）
是基础可行解，表示可行域的一个极点。
目标函数值为,z=15
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
3x 2 +x 3 =15
3x 2 -x 3 =18
-x 2 +x 3 +x 6 =3
基变量 x1,x2,x3,非基变量 x4,x5,x6
基础解为
（ x1,x2,x3,x4,x5,x6） =（ 0,11/2,-3/2,0,0,10）
是基础解但不是可行解。
x 1 +3 x 2 +x 3 +x 4 =1 5
2x 1 +3 x 2 -x 3 +x 5 =1 8
x 1 -x 2 +x 3 +x 6 =3
=
目标函数约束条件基矩阵右边常数进基变量、离基变量、基变换
=
基变量
=
进基变量离基变量目标函数约束条件右边常数=
=
目标函数约束条件新的基矩阵右边常数=
=
进基变量离基变量目标函数约束条件基矩阵
=
=
目标函数约束条件新的基矩阵右边常数=
基础解、基础可行解
max z=x1+3x2 D
s.t,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
O A B C D E
基变量 x 3 x 4 x 1 x 4 x 1 x 2 x 2 x 3 x 2 x 4 x 1 x 3
非基变量 x 1 x 2 x 2 x 3 x 3 x 4 x 1 x 4 x 1 x 3 x 2 x 4
x j < 0 -- -- -- -- x 4 x 1
基础可行解 是 是 是 是 否 否几何概念 代数概念约束直线 满足一个等式约束的解约束半平面 满足一个不等式约束的解约束半平面的交集：
凸多边形满足一组不等式约束的解约束直线的交点 基础解可行域的极点 基础可行解目标函数等值线：
一组平行线目标函数值等于一个常数的解单纯形表
m ax z= 3x 1 + 4x 2 -x 3 + 2x 4
s,t,x 1 +x 2 +x 3 +x 4 ≦ 25
x 1 + 2x 2 +x 3 + 2x 4 ≦ 36
x 1 x 2 x 3 x 4 ≧ 0
m in z ' = - 3x 1 - 4 x 2 +x 3 - 2 x 4
s,t,x 1 +x 2 +x 3 +x 4 +x 5 = 25
x 1 + 2 x 2 +x 3 + 2 x 4 +x 6 = 3 6
x 1 x 2 x 3 x 4 x 5 x 6 ≧ 0
求解线性规划问题写成标准化形式
z' x 1 x 2 x 3 x 4 x 5 x 6 R H S
z' 1 3 4 -1 2 0 0 0
0 1 1 1 1 1 0 25
0 1 2 1 2 0 1 36
写出单纯形表
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进基，
z' x 1 x 2 x 3 x 4 x 5 x 6 R H S
z' 1 3 4 -1 2 0 0 0
x 5 0 1 1 1 1 1 0 25
x 6 0 1 2 1 2 0 1 36
z' x 1 x 2 x 3 x 4 x 5 x 6 R H S
z' 1 1 0 -3 -2 0 -2 - 7 2
x 5 0 1 / 2 0 1 / 2 0 1 - 1 / 2 7
x 2 0 1 / 2 1 1 / 2 1 0 1 / 2 18
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
m ax z= 2x 1 +3x 2 +x 3
st x 1 +3x 2 +x 3? 15
2x 1 +3x 2 -x 3? 18
x 1 -x 2 +x 3? 3
x 1,x 2,x 3? 0
m in z’ = -2x 1 -3x 2 -x 3
st x 1 +3x 2 +x 3 +x 4 =15
2x 1 +3x 2 -x 3 +x 5 =18
x 1 -x 2 +x 3 +x 6 =3
x 1,x 2,x 3,x 4,x 5,x 6? 0
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 2 3 1 0 0 0 0
x 4 0 1 3 1 1 0 0 15 1 5 /3
x 5 0 2 3 -1 0 1 0 18 1 8 /3
x 6 0 1 -1 1 0 0 1 3 -
m in z’ = -2x 1 -3x 2 -x 3
st x 1 +3x 2 +x 3 +x 4 =15
2x 1 +3x 2 -x 3 +x 5 =18
x 1 -x 2 +x 3 +x 6 =3
x 1,x 2,x 3,x 4,x 5,x 6? 0
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 2 3 1 0 0 0 0
x 4 0 1 [ 3 ] 1 1 0 0 15 1 5 /3
x 5 0 2 3 -1 0 1 0 18 1 8 /3
x 6 0 1 -1 1 0 0 1 3 -
z’ x 1 x 2 x 3 x 4 x 5 x 6 R H S
z’ 1 1 0 0 -1 0 0 - 1 5
x 2 0 1 /3 1 1 /3 1 /3 0 0 5 5 /1 /3
x 5 0 [ 1 ] 0 -2 -1 1 0 3 3 /1
x 6 0 4 /3 0 4 /3 1 /3 0 1 8 8 /4 /3
z’ x 1 x 2 x 3 x 4 x 5 x 6 RHS
z’ 1 0 0 2 0 -1 0 -18
x 2 0 0 1 1 2/3 -1/3 0 4 4/1
x 1 0 1 0 -2 -1 1 0 3 --
x 6 0 0 0 [ 4] 5/3 -4/3 1 4 4/4
z’ x 1 x 2 x 3 x 4 x 5 x 6 RHS
z’ 1 0 0 2 0 -1 0 -18
x 2 0 0 1 1 2/3 -1/3 0 4 4/1
x 1 0 1 0 -2 -1 1 0 3 --
x 6 0 0 0 [ 4] 5/3 -4/3 1 4 4/4
x 3 进基,x 6 离基
z’ x 1 x 2 x 3 x 4 x 5 x 6 RH S
z’ 1 0 0 0 -5/6 -1/3 -1/2 -20
x 2 0 0 1 0 1/4 0 -1/4 3
x 1 0 1 0 0 -1/6 1/3 1/2 5
x 3 0 0 0 1 5/12 -1/3 1/4 1
最优解,( x 1,x 2,x 3,x 4,x 5 x 6 )=(5,3,1,0,0,0),m ax z =20
线性规划的矩阵表示
=
=
=
=
=
z X B X N RHS
z 1 -C B
T
-C N
T
0
X B 0 I B
-1
N B
-1
b
z X RHS
z 1 -C T 0
0 A b
z X B X N RHS
z 1 -C B
T
-C N
T
0
0 B N b
z X
B
X
N
R HS
z 1 0
T
C
B
T
B
-1
N- C
N
T
C
B
T
B
-1
b
X
B
0 I B
-1
N B
-1
b
z X
B
… x
j
… RHS
z 1 -C
B
T
… - c
j
… 0
0 B … a
j
… b
z X
B
… x
j
… RHS
z 1 0
T
… C
B
T
B
-1
a
j
-c
j
… C
B
T
B
-1
b
0 I … B
-1
a
j
… B
-1
b
CBTB-1aj-cj=zj-cj 称为非基变量的检验数（ Reduced Cost）
B-1aj=Yj,B-1b=,CBTB-1b=z0b
z X
B
… x
j
… RHS
z 1 0
T
… z
j
-c
j
… z
0
X
B
0 I … Y
j
… b
z X
B
… x
j
… RHS
z 1 0
T
… C
B
T
B
-1
a
j
-c
j
… C
B
T
B
-1
b
0 I … B
-1
a
j
… B
-1
b
第二章 对偶线性规划对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的关系 — 互补松弛关系最优解的 Kuhn-Tucher条件对偶可行基对偶单纯形法对偶的经济解释
DUAL
一、对偶的定义原始问题
min z=CTX
s.t,AX≥b
X ≥0
对偶问题
max y=bTW
s.t,ATW≤C
W ≥0
≥
min
bA
CT
CAT
bT
≤
max
m
n
m
n
二、对偶问题的性质
1、对偶的对偶就是原始问题
max z’=-CTX
s.t,-AX≤-b
X ≥0
min y=-bTW
s.t,-ATW≥-C
W ≥0
max y=bTW
s.t,ATW≤C
W ≥0
min z=CTX
s.t,AX≥b
X ≥0
对偶的定义对偶的定义
min z=CTX
s.t,AX≤b
X ≥0
max y=bTW
s.t,ATW≤C
W ≤0
2、其他形式问题的对偶
min z=CTX
s.t,AX≥b
X ≥0
max y=bTW
s.t,ATW≤C
W ≥0
min z=CTX
s.t,AX=b
X ≥0
max y=bTW
s.t,ATW≤C
W,unr
三、原始对偶关系
1、可行解的目标函数值之间的关系设 XF,WF分别是原始问题和对偶问题的可行解
z=CTXF ≥WTAXF ≥WTb=y
2,最优解的目标函数值之间的关系设 Xo,Wo分别是原始问题和对偶问题的最优解
z=CTXo=WoTAXo=WoTb=y
3、原始问题和对偶问题最优解之间的互补松弛关系
min z=CTX
s.t,AX-XS=b
X,XS≥0
max y=bTW
s.t,ATW+WS=C
W,WS≥0
min z=CTX
s.t,AX≥b
X ≥0
max y=bTW
s.t,ATW≤C
W≥0对偶引进松弛变量 引进松弛变量
XTWS=0 WTXS=0
互补松弛关系
X,Xs W,Ws
min z=CTX
s.t,AX-XS=b
X,XS ≥0
max y=bTW
s.t,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
s.t,AX≥b
X ≥0
min z=CTX
s.t,AX ≤ b
X ≥0
max z=CTX
s.t,AX ≥ b
X ≥0
max z=CTX
s.t,AX ≤ b
X ≥0
（ 2）
（ 3） （ 4）
（ 1）
单纯形表和对偶 (1)
min z=CTX
s.t,AX-XS=b
X,XS≥0
max y=bTW
s.t,ATW+WS=C
W,WS≥0
min z=CTX
s.t,AX≥b
X ≥0
max y=bTW
s.t,ATW≤C
W≥0
对偶问题原始问题引进松弛变量引进松弛变量
z X X S RH S
1 -W S
T
-W
T
C B
T
B
-1
b
0 B
-1
A -B
-1
B
-1
b
z X X S RH S
1 -C
T
0
T
0
0 A -I b
min z=CTX
s.t,AX-XS=b
X,XS≥0
max y=bTW
s.t,ATW+WS=C
W,WS≥0
z X X S RH S
1 C B
T
B
-1
A- C
T
-C B
T
B
-1
C B
T
B
-1
b
0 B
-1
A -B
-1
B
-1
b
WT=CBTB-1
WST=CT-WTA
min z=CTX
s.t,AX+XS=b
X,XS≥0
max y=bTW
s.t,ATW+WS=C
W ≤0,WS≥0
min z=CTX
s.t,AX ≤ b
X ≥0
max y=bTW
s.t,ATW≤C
W ≤ 0
单纯形表和对偶 (2)
对偶问题原始问题引进松弛变量引进松弛变量
z X X S RH S
1 -W S
T
W
T
C B
T
B
-1
b
0 B
-1
A B
-1
B
-1
b
z X X S RH S
1 -C
T
0
T
0
0 A I b
min z=CTX
s.t,AX+XS=b
X,XS≥0
max y=bTW
s.t,ATW+WS=C
W ≤0,WS≥0
z X X S RH S
1 C B
T
B
-1
A- C
T
C B
T
B
-1
C B
T
B
-1
b
0 B
-1
A B
-1
B
-1
b
WT=CBTB-1
WST=CT-WTA
max z=CTX
s.t,AX-XS=b
X,XS≥0
max y=bTW
s.t,ATW-WS=C
W ≤0,WS≥0
max z=CTX
s.t,AX ≥ b
X ≥0
min y=bTW
s.t,ATW ≥ C
W ≤ 0
单纯形表和对偶 (3)
对偶问题原始问题引进松弛变量引进松弛变量
z X X S RH S
1 W S
T
-W
T
C B
T
B
-1
b
0 B
-1
A -B
-1
B
-1
b
z X X S RH S
1 -C
T
0
T
0
0 A -I b
max z=CTX
s.t,AX-XS=b
X,XS≥0
min y=bTW
s.t,ATW-WS=C
W ≤0,WS≥0
z X X S RH S
1 C B
T
B
-1
A- C
T
-C B
T
B
-1
C B
T
B
-1
b
0 B
-1
A -B
-1
B
-1
b
WT=CBTB-1
WST=WTA- CT
max z=CTX
s.t,AX+XS=b
X,XS≥0
max y=bTW
s.t,ATW-WS=C
W,WS≥0
max z=CTX
s.t,AX ≤ b
X ≥0
min y=bTW
s.t,ATW ≥ C
W ≥ 0
单纯形表和对偶 (4)
对偶问题原始问题引进松弛变量引进松弛变量
z X X S RH S
1 W S
T
W
T
C B
T
B
-1
b
0 B
-1
A B
-1
B
-1
b
z X X S RH S
1 -C
T
0
T
0
0 A I b
max z=CTX
s.t,AX+XS=b
X,XS≥0
min y=bTW
s.t,ATW-WS=C
W,WS≥0
z X X S RH S
1 C B
T
B
-1
A- C
T
C B
T
B
-1
C B
T
B
-1
b
0 B
-1
A B
-1
B
-1
b
WT=CBTB-1
WST=WTA- CT
2、对偶单纯形法（初始解原始不可行的问题）
0xxx
2xx2x
5xx3x2
4xxx.t.s
xx2x3zm i n
321
321
321
321
321
0xxxxxx
2xxx2x
5xxx3x2
4xxxx.t.s
xx2x3zm i n
654321
6321
5321
4321
321
0xxxxxx
2xxx2x2
5xxx3x2
4xxxx.t.s
xx2x3zm i n
654321
6321
5321
4321
321
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 -3 -2 -1 0 0 0 0
x
4
0 1 -1 1 1 0 0 4
x
5
0 2 -3 1 0 1 0 -5
x
6
0 -2 2 -1 0 0 1 -2
-3/ -2 -1/ -1
z x
1
x
2
x
3
x
4
x
5
x
6
R HS
z 1 -1 0 0 0 -4 -5 30
x
4
0 -1 0 0 1 1 2 -5
x
2
0 0 1 0 0 -1 -1 7
x
3
0 2 0 1 0 -2 -3 16
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 -1 -4 0 0 0 -1 2
x
4
0 -1 1 0 1 0 1 2
x
5
0 0 -1 0 0 1 1 -7
x
3
0 2 -2 1 0 0 -1 2
z x
1
x
2
x
3
x
4
x
5
x
6
R HS
z 1 0 0 0 -1 -5 -7 35
x
1
0 1 0 0 -1 -1 -2 5
x
2
0 0 1 0 0 -1 -1 7
x
3
0 0 0 1 2 0 1 6
已获得最优解：
（ 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、初始解原始、对偶都不可行的问题
0xxx
2xx2x
5xx3x2
4xxx.t.s
x2x2x3zm i n
321
321
321
321
321
0xxxxxx
2xxx2x
5xxx3x2
4xxxx.t.s
x2x2x3zm i n
654321
6321
5321
4321
321
0xxxxxx
2xxx2x2
5xxx3x2
4xxxx.t.s
x2x2x3zm i n
654321
6321
5321
4321
321
z x
1
x
2
x
3
x
4
x
5
x
6
R HS
z 1 -3 -2 2 0 0 0 0
x
4
0 1 -1 1 1 0 0 4
x
5
0 2 -3 1 0 1 0 -5
x
6
0 -2 2 -1 0 0 1 -2
解法 1：先解决原始可行性
z x
1
x
2
x
3
x
4
x
5
x
6
RH S
z 1 -7 0 0 0 2 4 -18
x
4
0 -1 0 0 1 1 2 -5
x
2
0 0 1 0 0 -1 -1 7
x
3
0 2 0 1 0 -2 -3 16
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 -7 2 0 0 0 2 -4
x
4
0 -1 1 0 1 0 1 2
x
5
0 0 -1 0 0 1 -7
x
3
0 2 -2 1 0 -1 2
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 0 0 0 -7 -5 -10 17
x
1
0 1 0 0 -1 -1 -2 5
x
2
0 0 1 0 0 -1 -1 7
x
3
0 0 0 1 2 0 1 6
在得到原始可行解时同时得到对偶可行解，已获得最优解：
（ 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
z x
1
x
2
x
3
x
4
x
5
x
6
RH S
z 1 -3 -2 2 0 0 0 0
x
4
0 1 -1 1 1 0 0 4
x
5
0 2 -3 1 0 1 0 -5
x
6
0 -2 2 -1 0 0 1 -2
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 -5 0 0 -2 0 0 -8
x
3
0 1 -1 1 1 0 0 4
x
5
0 1 -2 0 -1 1 0 -9
x
6
0 -1 1 0 1 0 1 2
解法 2：先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解
z x
1
x
2
x
3
x
4
x
5
x
6
R HS
z 1 0 0 0 -7 -5 -10 17
x
3
0 0 0 1 2 0 1 6
x
2
0 0 1 0 0 -1 -1 7
x
1
0 1 0 0 -1 -1 -2 5
z x
1
x
2
x
3
x
4
x
5
x
6
RHS
z 1 -5 0 0 -2 0 0 -8
x
3
0 1/2 0 1 3/2 -1/2 0 17/ 2
x
2
0 -1/2 1 0 1/2 -1/2 0 9/2
x
6
0 -1/2 0 0 1/2 1/2 1 -5/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,原始问题是利润最大化的生产计划问题
0xxxxxx
bxxaxaxa
bxxaxaxa
bxxaxaxa.t.s
xcxcxczm a x
mn2n1nn21
mmnnmn22m11m
22nnn2222121
11nnn1212111
222211
单位产品的利润（ 元 /件）
产品产量（件）
总利润（元）
资源限量（吨）单位产品消耗的资源（吨 /件） 剩余的资源（ 吨）
消耗的资源（吨）
2,对偶问题
0wwwwww
cwwawawa
cwwawawa
cwwawawa.t.s
wbwbwbym i n
nm2m1mm21
nnmmmn2n21n1
22mm2m222112
11mm1m221111
mm2211
资源限量（吨）
资源价格（元 /吨）
总利润（元）
对偶问题是资源定价问题，对偶问题的最优解 w1,w2,...、
wm称为 m种资源的 影子价格（ Shadow Price）
原始和对偶问题都取得最优解时,最大利润 max z=min y
3,资源影子价格的性质
■ 影子价格越大，说明这种资源越是相对紧缺
■ 影子价格越小，说明这种资源相对不紧缺
■ 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于 0
种资源的边际利润第种资源的增量第最大利润的增量 iibzw
i
o
o
i
mmii2211 wbwbwbwbyz
mmiii2211 wbw)bb(wbwbzz
ii wbz
w1
w2
wm
4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润
mmjiij2j21j1 wawawawa
增加单位资源可以增加的利润减少一件产品可以节省的资源
0xxxx
bxaxaxaxa
bxaxaxaxa
bxaxaxaxas,t,
xcxcxcxczm a x
nj21
mnmnjmj2m21m1
2n2nj2j222121
1n1nj1j212111
nnjj2211
机会成本 利润差额成本
0wwwwww
cwwawawa
cwwawawa
cwwawawa.t.s
wbwbwbym i n
nm2m1mm21
nnmmmn2n21n1
22mm2m222112
11mm1m221111
mm2211
5、产品的差额成本（ Reduced Cost）
差额成本 =机会成本 - 利润
jjTjmjmj22j11jm caWc)awawaw(w
5、互补松弛关系的经济解释
0x0w
0w0x
0wx
0w0x
0x0w
0xw
jjm
jmj
jmj
iin
ini
ini
在利润最大化的生产计划中
（ 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
供应量供应地 运价需求量需求地
67
53
84
27
59
10
6
运输问题线性规划模型
0xxxxxxxxxxxx
13xxx
12xxx
13xxx
22xxx
19xxxx
27xxxx
14xxxxs,t,
x6x10x9x5x7x2x4x8x3x5x7x6zm i n
343332312423222114131211
342414
332313
322212
312111
34333231
24232221
14131211
343332312423222114131211
供应地约束需求地约束运输问题的表格表示
1 2 3 4
6 7 5 3
1
x
11
x
12
x
13
x
14
14
8 4 2 7
2
x
21
x
22
x
23
x
24
27
5 9 10 6
3
x
31
x
32
x
33
x
34
19
22 13 12 13
初始基础可行解 — 西北角法
1 2 3 4
6 7 5 3
1
14
8 4 2 7
2
27
5 9 10 6
3
19
22 13 12 13
8 13
13
14
6
6
1 2 3 4
6 7 5 3
1 14
8 4 2 7
2
12
27 15
5 9 10 6
3 19
22 13 12 13
0
初始基础可行解 — 最小元素法（ 1）
最小元素法（ 2）
1 2 3 4
6 7 5 3
1
13
14 1
8 4 2 7
2
12
27 15
5 9 10 6
3 19
22 13 12 13
0 0
最小元素法（ 3）
1 2 3 4
6 7 5 3
1
13
14 1
8 4 2 7
2
13 12
27 2
5 9 10 6
3 19
22 13 12 13
0 0 0
最小元素法（ 4）
1 2 3 4
6 7 5 3
1
13
14 1
8 4 2 7
2
13 12
27 2
5 9 10 6
3
19
19 0
22 13 12 13
3 0 0 0
最小元素法（ 5）
1 2 3 4
6 7 5 3
1
1 13
14 0
8 4 2 7
2
13 12
27 2
5 9 10 6
3
19
19 0
22 13 12 13
2 0 0 0
最小元素法（ 6）
1 2 3 4
6 7 5 3
1
1 13
14 0
8 4 2 7
2
2 13 12
27 0
5 9 10 6
3
19
19 0
22 13 12 13
0 0 0 0
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
非基变量 xij的检验数 zij-cij— 闭回路法 (1)
z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
闭回路法 (2)
z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5
-5
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
闭回路法 (3)
z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7
-7-5
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
闭回路法 (4)
z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9
-9
-5 -7
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
闭回路法 (5)
z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11
+11
-5 -7
-9
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
8 13 6
27
5 9 10 6
3
6
13
19
22 13 12 13
-5
闭回路法 (6)
z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3
+3
-5 -7
-9
+11
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
5 9 10 6
3
6
13
u
3
v
1
v
2
v
3
v
4
=0
非基变量 xij的检验数 zij-cij— 对偶变量法 (1)
v4=0
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
5 9 10 6
3
6
13
u
3
=6
v
1
v
2
v
3
v
4
=0
对偶变量法 (2)
u3+v4=c34 u3=6
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
5 9 10 6
3
6
13
u
3
=6
v
1
v
2
v
3
=4 v
4
=0
对偶变量法 (3)
u3+v3=c33 v3=4
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
v
2
v
3
=4 v
4
=0
对偶变量法 (4)
u2+v3=c23 u2=-2
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
v
2
=6 v
3
=4 v
4
=0
对偶变量法 (5)
u2+v2=c22 v2=6
1 2 3 4
6 7 5 3
1
14
u
1
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (6)
u2+v1=c21 v1=10
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (7)
u1+v1=c11 u1=-4
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (8)
z12-c12=u1+v2-c12=(-4)+6-7=-5
-5
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (9)
z13-c13=u1+v3-c13=(-4)+4-5=-5
-5-5
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (10)
z14-c14=u1+v4-c14=(-4)+0-3=-7
-7-5 -5
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (11)
z24-c24=u2+v4-c24=(-2)+0-7=-9
-9
-5 -5 -7
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (12)
z31-c31=u3+v1-c31=6+10-5=11
11
-5 -5 -7
-9
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
对偶变量法 (13)
z32-c32=u3+v2-c32=6+6-9=+3
+3
-5 -5 -7
-9
11
1 2 3 4
6 7 5 3
1
14
u
1
=-4
8 4 2 7
2
8 13 6
u
2
=-2
5 9 10 6
3
6
13
u
3
=6
v
1
=10 v
2
=6 v
3
=4 v
4
=0
选择进基变量,确定离基变量
x31进基,min{x21,x33}=min{8,6}=6,x33离基
+3
-5 -5 -7
-9
11
1 2 3 4
6 7 5 3
1
14
14
8 4 2 7
2
2 13 12
27
5 9 10 6
3
6
13
19
22 13 12 13
调整运量,重新计算检验数,确定进基、离基变量
x14进基,min{x11,x34}=min{14,13}=13,x34离基
-11
-5 -5 +4
+2
-8
1 2 3 4
6 7 5 3
1
1 13
14
8 4 2 7
2
2 13 12
27
5 9 10 6
3
19
19
22 13 12 13
调整运量,重新计算检验数所有 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=6?2+3?3+4?2+2?6+1?5=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
505)E(f)ED(d)D(f 5114
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
202)E(f)ED(d)D(f 5224
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
11
2421
1411
13
DC8
11
8
m i n
29
53
m i n
)D(f)D,C(
)D(f)D,C(
m i n)C(f
最优决策
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
22
2422
1412
23
DC7
7
11
m i n
25
56
m i n
)D(f)D,C(
)D(f)D,C(
m i n)C(f
最优决策
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
23
2423
1413
33
DC12
12
13
m i n
210
58
m i n
)D(f)D,C(
)D(f)D,C(
m i n)C(f
最优决策
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
11
3331
2321
1311
12
CB
20
22
21
20
m i n
1210
714
812
m i n
)C(f)C,B(
)C(f)C,B(
)C(f)C,B(
m i n)B(f
最优决策
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
12
3332
2322
1312
22
CB
14
16
17
14
m i n
124
710
86
m i n
)C(f)C,B(
)C(f)C,B(
)C(f)C,B(
m i n)B(f
最优决策
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
23
3333
2323
1313
32
CB
19
23
19
21
m i n
1211
712
813
m i n
)C(f)C,B(
)C(f)C,B(
)C(f)C,B(
m i n)B(f
最优决策
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
323
222
121
1
BA
19
20
19
23
m i n
191
145
212
m i n
)B(f)B,A(
)B(f)B,A(
)B(f)B,A(
m i n)A(f
最优决策
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→C 1 →D 1 →E
2、资源分配问题项目投入资金
A B C
1 万元 15 万吨 13 万吨 11 万吨
2 万元 28 万吨 29 万吨 30 万吨
3 万元 40 万吨 43 万吨 45 万吨
4 万元 51 万吨 55 万吨 58 万吨
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
