文档介绍：第四章之二 运输问题
§1 运输问题及其数学模型
§2 运输问题的表上作业法
§3 运输问题的进一步讨论
§4 运输问题的应用
例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?
一、运输问题的提出
§1 运输问题及其数学模型
解: 产销平衡问题: 总产量= 总销量
设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表:
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
. x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
xij ≥ 0 ( i = 1、2;j = 1、2、3)
一般运输模型
单一品种的物质的运输调度问题,其典型情况是:设某物品有m个产地A1,A2,…,Am,各产地的产量分别为a1, a2, …, am; n个销地B1, B2, …, Bn,各销地的销量分别为b1, b2, …, bn. 假定从产地Ai(i=1,2, …,m)向销地Bj(j=1, 2, …, n) 运输单位物质的运价为cij, 问怎样调运这些物品才能使得总运费最小?
运输问题的表示——网络图
A1
A2
Am
产地
B1
B2
Bn
销地
a1
a2
am
b1
b2
bn
c11
c12
c1n
c21
c22
c2n
cm1
cm2
cmn
若则称该问题为平衡运输问题,否则称为非平衡运输问题。
运输问题的数学模型
平衡问题的数学模型为
各产地运出的物资数量等于其产量
各销地接受的物资数量等于其销量
其中
运输问题的表示—表格表示
这个表常称为运输表
二、运输问题数学模型的特点
运输问题一定存在最优解
实际上
是平衡运输问题的一个可行解。此外由于目标函数有下界,因此平衡运输问题存在最优解。
运输问题系数矩阵的特点
m
n
上述矩阵的列向量具有形式
第i个
第(m+j)个
因此运输问题约束条件系数矩阵的元素只能是0或1,对应变量xij列除了第i个与第(m+j)个分量为1外,其它分量均为零