第5章 高效运 输问题a.ppt

文档介绍：1
第五章运输问题
运输问题的数学模型
初始基可行解的确定
最优性检验与基可行解的改进
其他运输问题
2
§ 运输问题的数学模型及其特征
●有m个产地A1, A2, …, Am生产某种物资,另有n个销地B1, B2, …, Bm 需要该类物资;
●令a1, a2, …, am表示各产地产量, b1, b2, …, bn表示各销地的销量, 若ai=bj ,则称产销平衡;
●设xij表示产地 i 运往销地 j 的物资量,cij表示对应的单位运费。
3
如何调运,使总的运输费用最小?
供需平衡表
bn
…
b2
b1
销量
Bn
B2
B1
需方
供方
Am
A2
A1
am
a2
a1
产量
cmn
cm2
cm1
c2n
c22
c21
c1n
c12
c11
…
…
…
…
4
销
产
B1
B2
…
Bn
产量
A1
c11 x11
c12 x12
…
c1n x1n
a1
A2
c21 x21
c22 x22
…
c2n x2n
a2
┇
┇
┇
┇
┇
┇
Am
cm1 xm1
cm2 xm2
…
cmn xmn
am
销量
b1
b1
…
bn
平衡表、运价表合二为一
5
(1) 运输问题数学模型
xij ——供应节点i至需求节点j的运输量;
aij ——供应节点i的可供应量,i=1,2, …,m;
bij ——需求节点j的需求量,j=1,2,…,n;
cij ——供应节点i至需求节点j的单位运输成本。
6
根据运输问题中总供应量与总需求量的关系可将运输问题分为两类:
平衡型运输问题和不平衡型运输问题。
平衡型运输问题:
不平衡型运输问题:
对于不平衡型运输问题通常通过设立虚拟供应节点或虚拟需求节点将其转化为平衡型运输问题求解。
(2) 运输问题的分类
7
产销平衡运输问题的数学模型:
Ai的产品全
部供应出去
Bj的需求全部得到满足
8
平衡型运输问题的数学模型
模型包含
变量:m×n个
约束方程:m+n个
秩:r(A)=m+n-1
m 行
n 行
稀疏矩阵
9
产大于销运输问题的数学模型:
Ai的产品没有全部供应出去
Bj的需求全部得到满足
10
销大于产运输问题的数学模型:
Ai的产品全
部供应出去
Bj的需求没有全部得到满足
以下主要讨论产销平衡运输问题的数学模型