Page:1
QSC华东理工大学 工商经济学院 运筹学
Page:2
QSC华东理工大学 工商经济学院 运筹学经典运输问题销售商供应商
B o st o n C h i c a g o S t,L o u i s L e x i n g t o n
生产能力
( 吨 )
C l e v e l a n d 3 2 7 6 5,0 0 0
B e d f o r d 7 5 2 3 6,0 0 0
Y o r k 2 5 4 5 2,5 0 0
需求量 ( 吨 ) 6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
每吨运输成本 ( ＄ / 吨 )
Page:3
QSC华东理工大学 工商经济学院 运筹学网络表示供应商
1
Cleveland
2
Bedford
3
York
2
Chicago
1
Boston
3
St,Louis
4
Lexington
销售商
5,000
2,500
6,000
6,000
1,500
2,000
4,000
3
2
76
2
7 5
3
4
2 5
5
Page:4
QSC华东理工大学 工商经济学院 运筹学线性规划模型
Min Z= 3x 11 +2x 12 +7x 13 +6x 14 +7x 21 +5x 22 +2x 23 +3x 24 +2x 31 +5x 32 +4x 33 +5x 34
S,t,x11 +x 12 +x 13 +x 14 ≤ 5000
x21 +x 22 +x 23 +x 24 ≤ 6000
x31 +x 32 +x 33 +x 34 ≤ 2500
x11 +x 21 +x 31 = 6000
x11 +x 21 +x 31 = 4000
x11 +x 21 +x 31 = 2000
x11 +x 21 +x 31 = 1500
xij?0,
Page:5
QSC华东理工大学 工商经济学院 运筹学运输问题线性规划的一般形式
m
1i
n
1j
ijijc=zM in x
m,1,2,=i sx
n
1j
iij
n,1,2,=j dx
m
1i
jij
n,1,=jm;,1,2,=i 0,x ij
st,供应,
需求,
Page:6
QSC华东理工大学 工商经济学院 运筹学供求平衡问题的特征
d s
n
1j
j
m
1i
i
基变量的个数 =m+n-1
Page:7
QSC华东理工大学 工商经济学院 运筹学初始基本可行解的构造
Page:8
QSC华东理工大学 工商经济学院 运筹学西北角方法供应量
3 2 7 6
7 5 2 3
2 5 4 5
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 5,0 0 0
B e d fo r d 6,0 0 0
Y o r k 2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
5000
1000
0
1000
0
50004000
0
10001000 0
1000
1000
0
15001500
Page:9
QSC华东理工大学 工商经济学院 运筹学最小元素法供应量
3 2 7 6
7 5 2 3
2 5 4 5
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 5,0 0 0
B e d fo r d 6,0 0 0
Y o r k 2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
4000
0
1000
2500
2000 1500
3500
0
0
2500
2500 4000
0 0
2500
1000
Page:10
QSC华东理工大学 工商经济学院 运筹学运输问题的特殊解法
—— 闭回路方法检验数：非基变量增加一个单位引起的成本变化量
Page:11
QSC华东理工大学 工商经济学院 运筹学闭回路方法 ---例供应量
3 2 7 6
7 5 2 3
2 5 4 5
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 5,0 0 0
B e d fo r d 6,0 0 0
Y o r k 2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
Page:12
QSC华东理工大学 工商经济学院 运筹学初始基本可行解：
供应量
1000 4000
7 5 2 3
2500 2000 1500
2 5 4 5
2500
需求量 6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
Y o r k
6,0 0 0B e d fo r d
2,5 0 0
6 5,0 0 02 7C l e v e l a n d 3
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
基本可行解
Page:13
QSC华东理工大学 工商经济学院 运筹学检验数的计算：
供应量
1000 4000
+1 7 5 -1 2 3
2500 2000 1500
2 5 4 5
2500
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d -1 3 2 +1 7 6 5,0 0 0
Y o r k
6,0 0 0B e d fo r d
2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
9
闭回路检验数
Page:14
QSC华东理工大学 工商经济学院 运筹学初始基本可行解与检验数：
供应量
1000 4000
7 5 2 3
2500 2000 1500
2 5 4 5
2500
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 3 2 7 6 5,0 0 0
Y o r k
6,0 0 0B e d fo r d
2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
74
-1
9 7
7
基本可行解检验数
Page:15
QSC华东理工大学 工商经济学院 运筹学
1000 4000
-θ 7 +θ 5 2 3
2500 2000 1500
2 5 4 5
2500
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d +θ 3 -θ 62 7
Y o r k
B e d fo r d
-1
3500 1500
7 5 2 3
2500 2000 1500
2 5 4 5
2500
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 3 62 7
Y o r k
B e d fo r d
θ=2500
基本可行解的调整：
Page:16
QSC华东理工大学 工商经济学院 运筹学检验数的重新计算：
3500 1500
7 5 2 3
2500 2000 1500
2 5 4 5
2500
Y o r k
B e d fo r d
62 7C l e v e l a n d 3
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
8 6
64
1
6
检验数均大于 0，得最优解：
Page:17
QSC华东理工大学 工商经济学院 运筹学运输问题的特殊解法
—— 位势方法检验数：目标函数的系数减去对偶变量之和
Page:18
QSC华东理工大学 工商经济学院 运筹学
m
1i
n
1j
ijijc=zM in x
m,1,2,=i
sx
n
1j
iij
n,1,2,=j
dx
m
1i
jij
n,1,=jm;,1,2,=i 0,x ij
st,供应,
需求,
对偶变量 ui
对偶变量 vj
Page:19
QSC华东理工大学 工商经济学院 运筹学
m
1i
n
1j
jjii vdus=M a x w
n,1,2,j m;,1,2,=i
cv u ijji
n,1,=j m;,1,2,=i
v,u ji
无约束
st,对偶变量 xij
Page:20
QSC华东理工大学 工商经济学院 运筹学原问题检验数：
λij=cij-(ui+vj)
i=1,2,……m; j=1,2,……n
特别对于 m+n-1个基变量，有
λij=cij-(ui+vj)=0
Page:21
QSC华东理工大学 工商经济学院 运筹学位势法 ---例供应量
3 2 7 6
7 5 2 3
2 5 4 5
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 5,0 0 0
B e d fo r d 6,0 0 0
Y o r k 2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
Page:22
QSC华东理工大学 工商经济学院 运筹学初始基本可行解：
供应量
1000 4000
7 5 2 3
2500 2000 1500
2 5 4 5
2500
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 3 2 7 6 5,0 0 0
Y o r k
6,0 0 0B e d fo r d
2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1 5,0 0 0
基本可行解
Page:23
QSC华东理工大学 工商经济学院 运筹学位势计算：
1000 4000
7 5 2 3
2500 2000 1500
2 5 4 5
2500
u 1
u 2
u 3
v 1 v 2 v 3 v 4
Y o r k
B e d fo r d
62 7
C l e v e l a n d
3
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
3vu
2vu
2vu
7vu
2vu
3vu
42
32
13
12
21
11
1v
2;v
1;u
4;u
2;v
3;v
0;u
4
3
3
2
2
1
1
Page:24
QSC华东理工大学 工商经济学院 运筹学
1000 4000
7 5 2 3
2500 2000 1500
2 5 4 5
2500
Le x i n g to n
v
2
=2 v
3
=-2 v
4
=-1
B o s to n C h i c a g o S t,Lo u i s
3 2 7 6
B e d fo r d
u
1
=0
u
2
=4
u
3
=-1
v
1
=3
Y o r k
C l e v e l a n d
-1
9 7
4 7 7
检验数的计算：
Page:25
QSC华东理工大学 工商经济学院 运筹学退化问题的处理保证基变量的个数为 m+n-1
Page:26
QSC华东理工大学 工商经济学院 运筹学供应量
3 2 7 6
7 5 2 3
2 5 4 5
需求量 5,0 0 0 4,0 0 0 2,0 0 0 2,5 0 0
Y o r k 2,5 0 0
B e d fo r d 6,0 0 0
C l e v e l a n d 5,0 0 0
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
5000
0
0
Page:27
QSC华东理工大学 工商经济学院 运筹学非平衡问题的处理
----转换为平衡问题
Page:28
QSC华东理工大学 工商经济学院 运筹学销售商供应商
A B C D
生产能力
( 吨 )
甲 3 2 7 6 5,0 0 0
乙 7 5 2 3 6,0 0 0
丙 2 5 4 5 4,5 0 0
需求量 ( 吨 ) 6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
销售商供应商
A B C D
E
生产能力
( 吨 )
甲 3 2 7 6 0 5,0 0 0
乙 7 5 2 3 0 6,0 0 0
丙 2 5 4 5 0 4,5 0 0
需求量
( 吨 )
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0 2000
供过于求的处理
Page:29
QSC华东理工大学 工商经济学院 运筹学销售商供应商
A B C D
生产能力
( 吨 )
甲 3 2 7 6 5,0 0 0
乙 7 5 2 3 6,0 0 0
丙 2 5 4 5 2,5 0 0
需求量 ( 吨 ) 6,0 0 0 4,0 0 0 2,0 0 0 3,5 0 0
销售商供应商
A B C D
生产能力
( 吨 )
甲 3 2 7 6 5,0 0 0
乙 7 5 2 3 6,0 0 0
丙 2 5 4 5 2,5 0 0
丁 0 0 0 0 2000
需求量
( 吨 )
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
供不应求的处理
Page:30
QSC华东理工大学 工商经济学院 运筹学运输问题的推广
—— 转运问题
Page:31
QSC华东理工大学 工商经济学院 运筹学转运问题 ---例生产厂
1
Denver
2
Atlanta
6
Miami
5
Detroit
7
Dallas
8
New
Orleans
零售店
600
400
200
300
350
1503
2
3
6
4
3
1
1
6
2
5
4
3
Kansas
City
4
Louisville
6
4
批发部
Page:32
QSC华东理工大学 工商经济学院 运筹学
Min Z= 2x
13
+3x
14
+3x
23
+x
24
+2x
35
+6x
36
+3x
37
+6x
38
+4x
45
+4x
46
+6x
47
+5x
48
+4x
28
+x
78
S,t.
x
13
+x
14
≤ 600{
x
23
+x
24
+x
28
≤ 400
-x
13
-x
23
+x
35
+x
36
+x
37
+x
38
=0{
-x
14
-x
24
+x
45
+x
46
+x
47
+x
48
=0
x
35
+x
45
=200
x
36
+x
46
=150
x
37
+x
47
-x
78
=350{
x
38
+x
48
+x
28
+x
78
=300
x
ij
0 for all i,j
供应转运需求线性规划模型
Page:33
QSC华东理工大学 工商经济学院 运筹学转运问题分析与建模要点纯供应节点 —— 有供应量 Si，无需求量，无转运功能生产厂
1
Denver600
3
2
供应量
O u t ) ( A r c s
,iji Sx
Page:34
QSC华东理工大学 工商经济学院 运筹学纯需求节点 —— 无供应量，有需求量 dj，无转运功能
5
Detroit
零售店
200
需求量
2
4
I n ) ( A r c s
,jji dx
Page:35
QSC华东理工大学 工商经济学院 运筹学供应节点 —— 有供应量，无需求量，具有转运功能生产厂
1
Denver600
3
2
供应量
4
O u t ) ( A r c s I n ) ( A r c s
,,ijiji Sxx
Page:36
QSC华东理工大学 工商经济学院 运筹学需求节点 —— 无供应量，有需求量 dj，具有转运功能
7
Dallas 350
1
6
3 销售商需求量
O u t ) ( A r c s I n ) ( A r c s
,,jjiji dxx
Page:37
QSC华东理工大学 工商经济学院 运筹学纯转运节点 —— 无供应量，无需求量，仅具有转运功能
2
3
6
3
2
3
Kansas
City
6
批发部
O u t ) ( A r c s I n ) ( A r c s
,,0jiji xx
Page:38
QSC华东理工大学 工商经济学院 运筹学一般转运节点 —— 有供应量 Si，有需求量 di，又具有转运功能
2 6
3
3
Kansas
City
5
600 200
1 需求量供应量
O u t ) ( A r c s I n ) ( A r c s
,,iijiji dSxx
Page:39
QSC华东理工大学 工商经济学院 运筹学转运问题的应用 —— 生产与库存计划季度生产能力需求量单位生产成本单位库存费用
1 600 400 2 0,2 5
2 300 500 5 0,2 5
3 500 400 3 0,2 5
4 400 400 3 0,2 5
Page:40
QSC华东理工大学 工商经济学院 运筹学网络模型生产第一季度第二季度
600
300
2
3
5
第四季度第三季度500
400
需求第一季度第二季度
400
500
第四季度第三季度 400
400
3
0.25
0.25
0.25
生产能力 生产 需求量
QSC华东理工大学 工商经济学院 运筹学
Page:2
QSC华东理工大学 工商经济学院 运筹学经典运输问题销售商供应商
B o st o n C h i c a g o S t,L o u i s L e x i n g t o n
生产能力
( 吨 )
C l e v e l a n d 3 2 7 6 5,0 0 0
B e d f o r d 7 5 2 3 6,0 0 0
Y o r k 2 5 4 5 2,5 0 0
需求量 ( 吨 ) 6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
每吨运输成本 ( ＄ / 吨 )
Page:3
QSC华东理工大学 工商经济学院 运筹学网络表示供应商
1
Cleveland
2
Bedford
3
York
2
Chicago
1
Boston
3
St,Louis
4
Lexington
销售商
5,000
2,500
6,000
6,000
1,500
2,000
4,000
3
2
76
2
7 5
3
4
2 5
5
Page:4
QSC华东理工大学 工商经济学院 运筹学线性规划模型
Min Z= 3x 11 +2x 12 +7x 13 +6x 14 +7x 21 +5x 22 +2x 23 +3x 24 +2x 31 +5x 32 +4x 33 +5x 34
S,t,x11 +x 12 +x 13 +x 14 ≤ 5000
x21 +x 22 +x 23 +x 24 ≤ 6000
x31 +x 32 +x 33 +x 34 ≤ 2500
x11 +x 21 +x 31 = 6000
x11 +x 21 +x 31 = 4000
x11 +x 21 +x 31 = 2000
x11 +x 21 +x 31 = 1500
xij?0,
Page:5
QSC华东理工大学 工商经济学院 运筹学运输问题线性规划的一般形式
m
1i
n
1j
ijijc=zM in x
m,1,2,=i sx
n
1j
iij
n,1,2,=j dx
m
1i
jij
n,1,=jm;,1,2,=i 0,x ij
st,供应,
需求,
Page:6
QSC华东理工大学 工商经济学院 运筹学供求平衡问题的特征
d s
n
1j
j
m
1i
i
基变量的个数 =m+n-1
Page:7
QSC华东理工大学 工商经济学院 运筹学初始基本可行解的构造
Page:8
QSC华东理工大学 工商经济学院 运筹学西北角方法供应量
3 2 7 6
7 5 2 3
2 5 4 5
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 5,0 0 0
B e d fo r d 6,0 0 0
Y o r k 2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
5000
1000
0
1000
0
50004000
0
10001000 0
1000
1000
0
15001500
Page:9
QSC华东理工大学 工商经济学院 运筹学最小元素法供应量
3 2 7 6
7 5 2 3
2 5 4 5
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 5,0 0 0
B e d fo r d 6,0 0 0
Y o r k 2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
4000
0
1000
2500
2000 1500
3500
0
0
2500
2500 4000
0 0
2500
1000
Page:10
QSC华东理工大学 工商经济学院 运筹学运输问题的特殊解法
—— 闭回路方法检验数：非基变量增加一个单位引起的成本变化量
Page:11
QSC华东理工大学 工商经济学院 运筹学闭回路方法 ---例供应量
3 2 7 6
7 5 2 3
2 5 4 5
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 5,0 0 0
B e d fo r d 6,0 0 0
Y o r k 2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
Page:12
QSC华东理工大学 工商经济学院 运筹学初始基本可行解：
供应量
1000 4000
7 5 2 3
2500 2000 1500
2 5 4 5
2500
需求量 6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
Y o r k
6,0 0 0B e d fo r d
2,5 0 0
6 5,0 0 02 7C l e v e l a n d 3
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
基本可行解
Page:13
QSC华东理工大学 工商经济学院 运筹学检验数的计算：
供应量
1000 4000
+1 7 5 -1 2 3
2500 2000 1500
2 5 4 5
2500
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d -1 3 2 +1 7 6 5,0 0 0
Y o r k
6,0 0 0B e d fo r d
2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
9
闭回路检验数
Page:14
QSC华东理工大学 工商经济学院 运筹学初始基本可行解与检验数：
供应量
1000 4000
7 5 2 3
2500 2000 1500
2 5 4 5
2500
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 3 2 7 6 5,0 0 0
Y o r k
6,0 0 0B e d fo r d
2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
74
-1
9 7
7
基本可行解检验数
Page:15
QSC华东理工大学 工商经济学院 运筹学
1000 4000
-θ 7 +θ 5 2 3
2500 2000 1500
2 5 4 5
2500
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d +θ 3 -θ 62 7
Y o r k
B e d fo r d
-1
3500 1500
7 5 2 3
2500 2000 1500
2 5 4 5
2500
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 3 62 7
Y o r k
B e d fo r d
θ=2500
基本可行解的调整：
Page:16
QSC华东理工大学 工商经济学院 运筹学检验数的重新计算：
3500 1500
7 5 2 3
2500 2000 1500
2 5 4 5
2500
Y o r k
B e d fo r d
62 7C l e v e l a n d 3
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
8 6
64
1
6
检验数均大于 0，得最优解：
Page:17
QSC华东理工大学 工商经济学院 运筹学运输问题的特殊解法
—— 位势方法检验数：目标函数的系数减去对偶变量之和
Page:18
QSC华东理工大学 工商经济学院 运筹学
m
1i
n
1j
ijijc=zM in x
m,1,2,=i
sx
n
1j
iij
n,1,2,=j
dx
m
1i
jij
n,1,=jm;,1,2,=i 0,x ij
st,供应,
需求,
对偶变量 ui
对偶变量 vj
Page:19
QSC华东理工大学 工商经济学院 运筹学
m
1i
n
1j
jjii vdus=M a x w
n,1,2,j m;,1,2,=i
cv u ijji
n,1,=j m;,1,2,=i
v,u ji
无约束
st,对偶变量 xij
Page:20
QSC华东理工大学 工商经济学院 运筹学原问题检验数：
λij=cij-(ui+vj)
i=1,2,……m; j=1,2,……n
特别对于 m+n-1个基变量，有
λij=cij-(ui+vj)=0
Page:21
QSC华东理工大学 工商经济学院 运筹学位势法 ---例供应量
3 2 7 6
7 5 2 3
2 5 4 5
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 5,0 0 0
B e d fo r d 6,0 0 0
Y o r k 2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
Page:22
QSC华东理工大学 工商经济学院 运筹学初始基本可行解：
供应量
1000 4000
7 5 2 3
2500 2000 1500
2 5 4 5
2500
需求量
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
C l e v e l a n d 3 2 7 6 5,0 0 0
Y o r k
6,0 0 0B e d fo r d
2,5 0 0
6,0 0 0 4,0 0 0 2,0 0 0 1 5,0 0 0
基本可行解
Page:23
QSC华东理工大学 工商经济学院 运筹学位势计算：
1000 4000
7 5 2 3
2500 2000 1500
2 5 4 5
2500
u 1
u 2
u 3
v 1 v 2 v 3 v 4
Y o r k
B e d fo r d
62 7
C l e v e l a n d
3
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
3vu
2vu
2vu
7vu
2vu
3vu
42
32
13
12
21
11
1v
2;v
1;u
4;u
2;v
3;v
0;u
4
3
3
2
2
1
1
Page:24
QSC华东理工大学 工商经济学院 运筹学
1000 4000
7 5 2 3
2500 2000 1500
2 5 4 5
2500
Le x i n g to n
v
2
=2 v
3
=-2 v
4
=-1
B o s to n C h i c a g o S t,Lo u i s
3 2 7 6
B e d fo r d
u
1
=0
u
2
=4
u
3
=-1
v
1
=3
Y o r k
C l e v e l a n d
-1
9 7
4 7 7
检验数的计算：
Page:25
QSC华东理工大学 工商经济学院 运筹学退化问题的处理保证基变量的个数为 m+n-1
Page:26
QSC华东理工大学 工商经济学院 运筹学供应量
3 2 7 6
7 5 2 3
2 5 4 5
需求量 5,0 0 0 4,0 0 0 2,0 0 0 2,5 0 0
Y o r k 2,5 0 0
B e d fo r d 6,0 0 0
C l e v e l a n d 5,0 0 0
B o s to n C h i c a g o S t,Lo u i s Le x i n g to n
5000
0
0
Page:27
QSC华东理工大学 工商经济学院 运筹学非平衡问题的处理
----转换为平衡问题
Page:28
QSC华东理工大学 工商经济学院 运筹学销售商供应商
A B C D
生产能力
( 吨 )
甲 3 2 7 6 5,0 0 0
乙 7 5 2 3 6,0 0 0
丙 2 5 4 5 4,5 0 0
需求量 ( 吨 ) 6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
销售商供应商
A B C D
E
生产能力
( 吨 )
甲 3 2 7 6 0 5,0 0 0
乙 7 5 2 3 0 6,0 0 0
丙 2 5 4 5 0 4,5 0 0
需求量
( 吨 )
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0 2000
供过于求的处理
Page:29
QSC华东理工大学 工商经济学院 运筹学销售商供应商
A B C D
生产能力
( 吨 )
甲 3 2 7 6 5,0 0 0
乙 7 5 2 3 6,0 0 0
丙 2 5 4 5 2,5 0 0
需求量 ( 吨 ) 6,0 0 0 4,0 0 0 2,0 0 0 3,5 0 0
销售商供应商
A B C D
生产能力
( 吨 )
甲 3 2 7 6 5,0 0 0
乙 7 5 2 3 6,0 0 0
丙 2 5 4 5 2,5 0 0
丁 0 0 0 0 2000
需求量
( 吨 )
6,0 0 0 4,0 0 0 2,0 0 0 1,5 0 0
供不应求的处理
Page:30
QSC华东理工大学 工商经济学院 运筹学运输问题的推广
—— 转运问题
Page:31
QSC华东理工大学 工商经济学院 运筹学转运问题 ---例生产厂
1
Denver
2
Atlanta
6
Miami
5
Detroit
7
Dallas
8
New
Orleans
零售店
600
400
200
300
350
1503
2
3
6
4
3
1
1
6
2
5
4
3
Kansas
City
4
Louisville
6
4
批发部
Page:32
QSC华东理工大学 工商经济学院 运筹学
Min Z= 2x
13
+3x
14
+3x
23
+x
24
+2x
35
+6x
36
+3x
37
+6x
38
+4x
45
+4x
46
+6x
47
+5x
48
+4x
28
+x
78
S,t.
x
13
+x
14
≤ 600{
x
23
+x
24
+x
28
≤ 400
-x
13
-x
23
+x
35
+x
36
+x
37
+x
38
=0{
-x
14
-x
24
+x
45
+x
46
+x
47
+x
48
=0
x
35
+x
45
=200
x
36
+x
46
=150
x
37
+x
47
-x
78
=350{
x
38
+x
48
+x
28
+x
78
=300
x
ij
0 for all i,j
供应转运需求线性规划模型
Page:33
QSC华东理工大学 工商经济学院 运筹学转运问题分析与建模要点纯供应节点 —— 有供应量 Si，无需求量，无转运功能生产厂
1
Denver600
3
2
供应量
O u t ) ( A r c s
,iji Sx
Page:34
QSC华东理工大学 工商经济学院 运筹学纯需求节点 —— 无供应量，有需求量 dj，无转运功能
5
Detroit
零售店
200
需求量
2
4
I n ) ( A r c s
,jji dx
Page:35
QSC华东理工大学 工商经济学院 运筹学供应节点 —— 有供应量，无需求量，具有转运功能生产厂
1
Denver600
3
2
供应量
4
O u t ) ( A r c s I n ) ( A r c s
,,ijiji Sxx
Page:36
QSC华东理工大学 工商经济学院 运筹学需求节点 —— 无供应量，有需求量 dj，具有转运功能
7
Dallas 350
1
6
3 销售商需求量
O u t ) ( A r c s I n ) ( A r c s
,,jjiji dxx
Page:37
QSC华东理工大学 工商经济学院 运筹学纯转运节点 —— 无供应量，无需求量，仅具有转运功能
2
3
6
3
2
3
Kansas
City
6
批发部
O u t ) ( A r c s I n ) ( A r c s
,,0jiji xx
Page:38
QSC华东理工大学 工商经济学院 运筹学一般转运节点 —— 有供应量 Si，有需求量 di，又具有转运功能
2 6
3
3
Kansas
City
5
600 200
1 需求量供应量
O u t ) ( A r c s I n ) ( A r c s
,,iijiji dSxx
Page:39
QSC华东理工大学 工商经济学院 运筹学转运问题的应用 —— 生产与库存计划季度生产能力需求量单位生产成本单位库存费用
1 600 400 2 0,2 5
2 300 500 5 0,2 5
3 500 400 3 0,2 5
4 400 400 3 0,2 5
Page:40
QSC华东理工大学 工商经济学院 运筹学网络模型生产第一季度第二季度
600
300
2
3
5
第四季度第三季度500
400
需求第一季度第二季度
400
500
第四季度第三季度 400
400
3
0.25
0.25
0.25
生产能力 生产 需求量
