文档介绍：运输问题(TP)
A2
A3
B2
A1
B3
B4
B1
s2=9
s3=4
d1=3
d2=2
d3=4
d4=5
s1=1
供应量
供应地
运价
需求量
需求地
8
7
3
2
4
7
5
1
2
4
9
6
例:
例:(产销平衡问题)
销地
产地
B1
B2
B3
B4
产量
A1
8
7
3
2
1
A2
4
7
5
1
9
A3
2
4
9
6
4
销量
3
2
4
5
14
X11
X12 X13 X14
X21 X22 X23 X24
X31 X32 X33 X34
运输问题的模型
销地
产地
B1
B2
B3
B4
产量
A1
8
7
3
2
1
A2
4
7
5
1
9
A3
2
4
9
6
4
销量
3
2
4
5
14
X11
X12 X13 X14
X21 X22 X23 X24
X31 X32 X33 X34
. X11+ X12 + X13 + X14 = 1 ,
X21+ X22 + X23 + X24 = 9 ,
X12+ X22 + X32 = 2
X13+ X23 + X33 = 4
X31+ X32 + X33 + X34 = 4 ,
X14+ X24 + X34 = 5
Xij≥0
X11+ X21 + X31 = 3
Z = 8X11+ 7X12 + 3X13 + 2X14 + …+4X32 + 9X33 + 6X34
min
数学模型的一般形式
已知资料如下:
单销
费量
产地
产
量
销量
单销
费量
产地
产
量
销量
当产销平衡时,
其模型如下:
TP模型可解决的问题
运输问题是一类重要的线性规划问题。解决的最典型问题是:要把一种商品从某些产地运到几个销地,各产地的供应量及各销地的需求量已知,且已知每一产地到每一销地的单位运价(单位收益),求满足各销地需求量、同时总运输成本最小(总收益最大)的运输方案。
同时,运输问题还用于解决资源分配、任务安排等实际问题。
How?
表上作业法
销地
产地
B1
B2
B3
B4
产量
A1
8
7
3
2
1
A2
4
7
5
1
9
A3
2
4
9
6
4
销量
3
2
4
5
14
5
×
×
×
×
×
×
(1)用“最小元素法”求初始调运方案
3
3
1
1
1
B1
B2
B3
B4
A1
1
A2
1
3
5
A3
3
1
初始调运方案
对应于TP问题模型,得初始基可行解
Z0= 3×1+ 7×1+ 5×3 +1×5 + 2×3+4×1=40
X11=0, X12 =0, X13 =1,X14 =5,
X21=0, X22 =1, X23 =3, X24=0,
X31 =3,X32 =1, X33 = 0,X34 =0。
特征:
1、平衡运输问题必有可行解,也必有最优解;
2、运输问题的基本可行解中应包括 m+n-1 个基变量。