第四章 高效运输问题42562 8793.ppt

文档介绍：第四章运输问题
运输问题及其数学模型
用表上作业法求解运输问题
运输问题的进一步讨论
应用问题举例
第一节运输问题及其数学模型
●有m个产地生产某种物资,有n个地区需要该类物资
●令a1, a2, …, am表示各产地产量, b1, b2, …, bn表示各销地的销量,ai=bj 称为产销平衡
●设xij表示产地 i 运往销地 j 的物资量,cij表示对应的单位运费。
一、运输问题的一般数学模型
如何建立供需搭配,使总的运输费用最小?
供需平衡表
bn
…
b2
b1
需求量
Bn
B2
B1
需方
供方
Am
A2
A1
am
a2
a1
供应量
cmn
cm2
cm1
c2n
c22
c21
c1n
c12
c11
…
…
…
…
数学模型:
设从Ai到Bj的物资运量为xij ,
产销平衡运输问题的数学模型。
Ai的产品全
部供应出去
Bj的需求全部得到满足
平衡表、运价表合二为一
二、运输问题数学模型的特点

若令其变量
其中

则()就是运输问题的一个可行解;另一方面,运输问题的目标函数有下界,目标函数值不会趋于由此可知,运输问题必存在有限最优解。
m×n

其系数列向量的结构是:
3. 运输问题有mn个决策变量,m+n 个约束条件。由于产销平衡条件,只有m+n–1个相互独立,因此,运输问题的基变量只有m+n–1 个。每个变量的系数列向量中有两个1、其它元素均为0。
4. 所有结构约束条件都是等式约束。
ui‚vj无约束(i=1,2, …,m;j=1,2, …,n)
设ui,vj为对偶变量,对偶问题模型为
ui
vj
m个
n个
三、运输问题的对偶规划
例
,B2和B3,其间的距离(或单位运价)如表小方格中的数据所示。各仓库的存量和使用地的需用量也都示于表中,试建立使总运输量(或总运费)最小的运输问题数学模型。