文档介绍：主讲人:卫斌
制作:魏永牛
天水师范学院数理与信息科学学院数学系
2004年5月
线性规划的运输问题
在处理产、供、销的经济活动中,会经常遇到物资调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、化肥、木材等物资要由若干个产地调运到若干个销售地。问题是,怎样制定合理的调用方案才能使总运输费用最少?本章将专门讨论这类特殊形式的线性规划问题。
导
言
第五章运输问题
例某食品公司经销的主要商品之一是糖果,它下面设有三个加工厂。某个的产量分别为A1—7t, A2—4t, A3—9t该公司把这些糖果分别运往四个地区的门市部销售,各地区每天的销售量为: B1—3t, B2—6t, B3—5t, B4—6t 。已知从各个加工厂到各销售部门每吨的运价见下表:
运输问题的数学模型
3
10
4
7
A3
8
2
9
1
A2
10
3
11
3
A1
B4
B3
B2
B1
门市部
加工厂
单位:元/t
问:该食品公司应如何调运,在满足各部门销售的情况下,使总的运费支出为最少?
产销平衡的运输问题
无论全国或一个地区,在各种生产或生活物资调运中都可以提出入上述问题类似的例子。
现在把问题概括一下,在线性规划中我们研究这样一类运输问题:
运输问题的数学模型
产销平衡的运输问题
设有某种物资要从m个产地(或称发点)Ai(i=1,2,…,m)运往n个销地(或称收点)Bj(j=1,2,…n) ,Ai的产量为ai,Bj的销量为bj,把Ai运到Bj的单位运价设为cij,问怎样编制调运方案才能使总运费最少?
假设从Ai运到Bj的物资数量为xij,总运费为S,总产量=总销量。那么这个运输问题的数学模型是:
运输问题的数学模型
产销平衡的运输问题
产销平衡的运输问题
运输问题的数学模型
运输问题的数学模型是:
产销平衡表
产量ai
产地
销地
销量bi
1 2 … n
1
2
m
b1 b2 … bn
a1
a2
am
x11 x12 … x1n
x21 x22 … x2n
xm1 xm2 … xmn
产地
销地
1 2 … n
1
2
m
c11 c12 … c1n
c21 c22 … c2n
cm1 cm2 … cmn
单位运价表
产销平衡的运输问题
运输问题的数学模型
运输问题的数学模型是:
C=(c11,c12,…,c1n,c21,c22,c2n,…,cm1,cm2,…cmn)
B=(a1,a2,…,am,b1,b2,…bn)T
X =(x11,x12,…,x1n,x21,x22,x2n,…,xm1,xm2,…xmn)T
运输问题的数学模型
其矩阵形式为
产销平衡的运输问题
(1)产量大于销量的情形
运输问题的数学模型
产销不平衡运输问题的转化
其运输问题的数学模型是
由于总量大于总销量,所以多余物资应储存在产地。社某产地Ai的多余存储量为xi,n+1,于是运输问题的约束条件方程组为:
则
运输问题的数学模型
产销不平衡运输问题的转化