文档介绍:运筹学讲义
运输问题(2)
3/12/2018
1
Opertional Research
运输问题的进一步讨论
产销不平衡的运输问题
运输问题的特殊情形-无运输通路
目标函数极大化问题
运输问题的应用
3/12/2018
2
Opertional Research
运输问题的一般提法
产地Ai产量为ai,i=1,…,m。销地Bj销量为bj,j=1,…,n。 Ai到Bj的单位运费为cij。用xij表示产地i到销地j的预算量。在产销平衡条件下,数学模型为:
3/12/2018
3
Opertional Research
解决问题的思路:产销不平衡→产销平衡
产销不平衡的运输问题
供大于求时
3/12/2018
4
Opertional Research
0
0
0
2
9
4
1
5
3
8
3
1
7
10
2
B5
6
B4
4
B3
3
B2
7
A3
5
A2
2
销量
7
A1
产量
B1
销地
产地
4
3
4
2
3
2
1
4
3/12/2018
5
Opertional Research
产销不平衡的运输问题
供小于求
3/12/2018
6
Opertional Research
无运输通路
若A2到B3无运输路径,则
在最优解中,x23=0
若目标函数为min,可令c23=M
3/12/2018
7
Opertional Research
1、最大元素法
目标函数极大化问题
3/12/2018
8
Opertional Research
练习题
销地
产地
B1 B2 B3 B4 B5
产量
A1
A2
A3
A4
5 7 3 4 4
6 8 6 9 7
3 5 7 2 5
8 4 5 7 3
700
500
800
1000
需求量
420 490 510 530 550
已知某运输问题的单位收益表如下:
1、求出最佳运输方案;
2、若A4产地因仓库容量限制,1000单位货物必须全部运出去,则应如何确定最佳运输方案。
3/12/2018
9
Opertional Research
10 (1) 20 (11)
(7) (9) 20
(2) 14 16 18
c22
+c22
+1
+11
→
10+C22 (1+C22) 20+C22 (11+C22)
(13) (1+C22) (10) 21
(13) 25 27 29
C22-3 (0) 10+C22 (0)
(0) (0) (0) 10-C22
(0) 24-C22 17 18-C22
→
C22-3≥0
10+C22≥0
10-C22≥0
24-C22≥0
18-C22≥0
→
3≤C22≤10
(1) p114
3/12/2018
10
Opertional Research