运筹学09-高效运 输问题1.ppt

文档介绍：第9讲运输问题
School of Business
ECUST
本讲提纲
一、运输问题及其数学模型
二、运输问题的求解——表上作业法
三、运输问题的进一步讨论
School of Business
ECUST
一、运输问题及其数学模型
供应商
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
7
6
2
7
5
3
4
2
5
5
x11
x21
x31
x12
x22
x32
x13
x23
x33
x14
x24
x34
xij - 从 i 地到 j 地的运输量
应如何安排运输方案,使得总运费最低?
School of Business
ECUST
x11
x12
x13
x14
x21
x22
x23
x24
x31
x32
x33
x34
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.
x
11
+x
12
+x
13
+x
14
==
5000
x
21
+x
22
+x
23
+x
24
=
6000
x
31
+x
32
+x
33
+x
34
=
2500
x
11
+x
21
+x
31
= 6000
x
12
+x
22
+x
32
= 4000
x
13
+x
23
+x
33
= 2000
x
14
+x
24
+x
34
= 1500
x
ij
³
0
,
School of Business
ECUST
在该例中,有3个出发地,4个目的地,未知数(决策变量)个数为3x4=12个;约束方程个数为3+4=7个:3个产地的产量约束和4个需求地的需求量约束。
一般地,运输问题可以描述为:
设某种物品有:
m个产地:
产量:
n个销地:
销量:
从产地到销地的单位运价是。
求总运费最小的调度方案。
School of Business
ECUST
A1
A2
Am
︰
︰
B1
B2
Bn
︰
︰
a1
a2
am
︰
︰
b1
b2
bn
︰
︰
供应量
需求地
供应地
需求量
运价cij
运量xij
School of Business
ECUST
单位运价表
运量表
School of Business
ECUST
运输表(运价,运量)
销量
产
量
销地
产地
产销平衡条件下
School of Business
ECUST
运输问题的数学模型
从Ai运出的物资总量应等于Ai的产量ai
运到Bj的物资总量应该等于Bj的销量bj
School of Business
ECUST
产销平衡运输问题的特点与性质
(1) 所有的约束条件均为等式
(2) 总产量=总销量:
约束方程组共包含m×n个变量,(m+n)个约束方程
约束方程组
r (A) = m+n-1
基变量的个数为
m+n-1个