文档介绍：运输问题
运输问题及其数学模型
表上作业法
最小元素法
位势法
闭回路法
产销不平衡的运输问题
应用举例
运输问题及其模型
例某公司经销一种产品,它下设三个工厂、四个销售部。三个工厂的日产量分别为:A1—7吨,A2—4吨,A3—9吨;各销售部的日销量分别为:B1—3吨,B2—6吨,B3—5吨,B4—6吨。各厂到各销售部的单位产品的运价如右表。问该公司应如何调运产品,才能完成运输任务而使运费最省。
用线性规划法处理此问题。设由产地i到销地j的运量为xij,模型为:
min z= 3x11+11x12+3x13+10x14
+x21 +9x22 +2x23 +8x24
+7x31 +4x32+10x33+5x34
x11+x12+x13+x14=7
x21+x22+x23+x24=4
x31+x32+x33+x34=9
x11+x21+x31=3
x12+x22+x32=6
x13+x23+x33=5
x14+x24+x34=6
xij≥0 (i=1,2,3; j=1,2,3,4)
运输问题一般用表上作业法求解,需建立表格模型:
单位运价表
产销平衡表
表上作业法
表上作业法的步骤类似于单纯形法:
(1)给出初始调运方案。
(2)检验方案是否最优,若是最优解,则停止计算;否则转下一步。
(3)调整调运方案,得新的方案。
(4)重复(2),(3)直到求出最优方案。
给出初始调运方案最常用的方法
——最小元素法
表上作业法要求,调运方案的数字格必须为m+n-1个,且有数字格不构成闭回路。一般,用最小元素法给出的方案符合这一要求。
3
1
4
6
3
3
最小元素法中的退化情况
3
6
0
5
4
2
出现退化时,要在同时被划去的行列中任选一个空格填0,此格作为有数字格。
位势表
1
0
2
1
9
-4
8
(2)
(9)
(8)
(9)
(-3)
(-2)
检验数表
若所有检验数非负则是最优解
最优性检验的方法——位势法
(1)从一个检验数为负数且最小的空格出发,和其它数字格构成闭回路。可证,此闭回路存在且唯一。
(2)在闭回路上进行运量调整,使选定空格处的运量尽可能地增加。
(3)运量调整后,必然使某个数字格变成零。把一个变成零的数字格抹去,得新的调运方案。
方案调整的方法闭回路法
位势表
1
0
2
1
9
-4
8
(2)
(9)
(8)
(9)
(-3)
(-2)
检验数表
有检验数为负,不是最优解。
表上作业法举例
位势表
1
0
1
2
8
-3
7
(3)
(9)
(7)
(1)
(-2)
(-2)
检验数表
表上作业法举例(续)
检验数都非负,得最优解。