数学建模运输问题.ppt

运输问题模型 Transportation

门市部
加工厂
B1
B2
B3
B4
A1
3
11
3
10
A2
1
9
2
8
A3
7
4
10
5
公司把这些糖果分别运往四个地区的门市部销售,
各地区每天的销售量分别为:
B1—3吨,B2—6吨,B3—5吨,B4—6吨。
A1—7 吨,A2—4吨,A3—9吨。
某食品公司主要经营糖果。
它下面设有三个加工厂,
每天的糖果生产量分别为:
已知从每个加工厂到各销售门市部每吨糖果的运价如上表所示,
该食品公司应如何调运,在满足各门市部销售需要的情况下,
使总的运费支出为最少。

在线性规划中研究这样一类问题:
有某种物资需要调运,这种物资的计量单位可以是重量,
包装单位或其他。
已知:
有m 个地点可以供应该种物资(统称产地,用 i =1,…,m 表示);
有 n 个地点需要该种物资(统称销地,用 j =1,…,n 表示)。
n 个销地的需要量(统称销量)为b1 , b2, …, bn(统写为 b j )。
从第 i 个产地到第 j 个销地的单位物资运价为c i j 。
又知
m 个产地的可供量(统称产量)为a1 , a2, …, am(统写为a i );
上面这些数据通常用产销平衡表和单位运价表来表示。
销地
产地
1
2
…
n
产量
1
2
.
.
.
m
a1
a2
.
.
.
am
销量
b1
b2
…
bn
销地
产地
1 2 … n
1
2
.
.
.
m
c11 c12 … c1n
c21 c22 … c2n
. . .
. . .
. . .
cm1 cm2 … cmn
产销平衡表
单位运价表
有时候把两个表写在一起:
销地
产地
1 2 … n
1
2
.
.
.
m
c11 c12 … c1n
c21 c22 … c2n
. . .
. . .
. . .
cm1 cm2 … cmn
销地
产地
1
2
…
n
产量
1
2
.
.
.
m
a1
a2
.
.
.
am
销量
b1
b2
…
bn
销地
产地
1 2 … n
产量
1
2
.
.
.
m
c11 c12 … c1n
c21 c22 … c2n
. . .
. . .
. . .
cm1 cm2 … cmn
a1
a2
.
.
.
am
销量
b1 b2 … bn

设 xij 代表从第 i 个产地调运给
第 j 个销地的物资数量。
在产销平衡的条件下,要求解
运输问题使总的运费支出最小,
则有如下的运输问题数学模型:
销地
产地
1 2 … n
产量
1
2
.
.
.
m
x11 x12 … x1n
x21 x22 … x2n
. . .
. . .
. . .
xm1 xm2 … xmn
a1
a2
.
.
.
am
销量
b1 b2 … bn
销地
产地
1 2 … n
产量
1
2
.
.
.
m
c11 c12 … c1n
c21 c22 … c2n
. . .
. . .
. . .
cm1 cm2 … cmn
a1
a2
.
.
.
am
销量
b1 b2 … bn
如果用单纯形法求解,
先要在每个约束条件左端加上一个人工变量,
因此即使象食品公司调运糖果这样简单的数学问题,
变量数就有 3×4+3+4=19个之多,计算起来非常繁杂。
运输问题的数学模型结构比较特殊,
它的约束条件变量的系数矩阵具有如下的形式:
运输问题的数学模型包含
m×n个变量,
(m+n)个约束条件。
说明:
产销不平衡的运输问题

1)数学模型
销地
产地
1 2 … n
产量
1
2
.
.
.
m
x11 x12 … x1n
x21 x22 … x2n
. . .
. . .
. . .
xm1 xm2 … xmn
a1
a2
.
.
.
am
销量
b1 b2 … bn
.
产大于销时,增加一个假想的销地 j = n+1(库存),
2)求解方法: 转化为产销平衡问题
该销地的总需求量为
而在单位运价表中从各产地到假想销地的单位运价为
就转化为一个产销平衡的运输问题。
具体做法如下:
销地
产地
1 2 … n
产量
1
2
.
.
.
m
c11 c12 … c1n
c21 c22 … c2n
. . .
. . .
. . .
cm1 cm2 … cmn
a1
a2
.
.
.
am
销量
b1 b2 … bn
n+1
0
0
.
.
.