文档介绍：E
2006/3
1
--第3章运输问题--
第三章运输问题
Transportation problem
2006/3
2
--第3章运输问题--
运输问题的典例和数学模型
一、典例:
某食品公司经营糖果业务,公司下设三个工厂A1、A2、A3,四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问:如何调运可使总费用最小?
生产量:A1——7吨, A2 —— 4吨, A3 —— 9吨
销售量:B1 —— 3吨,B2 —— 6吨,B3 —— 5吨,B4 —— 6吨
产地
单位运价
销地
B1 B2 B3 B4
A1
A2
A3
3 11 3 10
1 9 2 8
7 4 10 5
2006/3
3
--第3章运输问题--
调运示意图
A1
A2
A3
B1
B2
B3
B4
7吨
4吨
9吨
3吨
6吨
5吨
6吨
x11
x12
x13
x14
x21
x22
x23
x24
x31
x32
x33
x34
产地
销地
2006/3
4
--第3章运输问题--
二、建立模型
设 xij——第i产地到第j销地之间的调运量,则有
Min z =  cij· xij
3
4
i=1
j=1
x11+x12+x13+x14=7
x11+x21+x31=3
xij0,(i=1,2,┄,3;j=1,2,┄,4)
产量限制
销量限制
x21+x22+x23+x24=4
x31+x32+x33+x34=9
x12+x22+x32=6
x13+x23+x33=5
x14+x24+x34=6
2006/3
5
--第3章运输问题--
一般模型表示:
设有个m产地、n个销地,其中第i个产地的产量为ai,第j个销地的销量为bj,且ai=bj。若第i个产地到第j个销地每调运单位物资的运费为cij,则使总费用最少的调运模型为:
Min z =  cij· xij
n
i=1
j=1
m
2006/3
6
--第3章运输问题--
三、模型的特点
:mn个
:m+n个
最大独立方程数:m+n-1
:
Pij=
0····1···1···0
——第i个分量
——第m+j个分量
2006/3
7
--第3章运输问题--
x11 x12 ······ x1n x21 x22 ······ x2n ,············, xm1 xm2 ······ xmn
1 1 ······ 1 0 0 ······ 0 ············ 0 0 ······ 0
0 0 ······ 0 1 1 ······ 1 ············ 0 0 ······ 0
0 0 ······ 0 0 0 ······ 0 ············ 1 1 ······ 1
1 0 ······ 0 1 0 ······ 0 ············ 1 0 ······ 0
0 1 ······ 0 0 1 ······ 0 ············ 0 1 ······ 0
0 0 ······ 1 0 0 ······ 1 ············ 0 0 ······ 1
i=1
i=2
i=m
j=1
j=2
j=n
··&#183