文档介绍：第三章运输问题
第一节运输问题及其数学模型
第二节表上作业法
第三节产销不平衡的运输问题及其求解
第四节应用问题举例
前面两章, 我们讨论了一般LP问题的求解方法, 但在实际问题中, 往往碰到有些线性规划问题, 它们的约束方程组的系数矩阵具有特殊的结构, .
,钢铁,木材,粮食等物资,在全国有若干生产基地,根据已有的交通网,应如何制定调动方案,将这些物资运到各消费地点, 而总运费要最小.
第一节运输问题及其数学模型
一、运输问题的数学模型
设某种物品
有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.
问: 如何调运这些物品才能使总运费最小?
bn
…
b2
b1
销量
am
xmn
…
xm2
xm1
Am
…
….
xij
…
…
…
a2
x2n
….
x22
x21
A2
a1
x1n
….
x12
x11
A1
产量
Bn
…
B2
B1
销地
产地
运价表
c21
c22
c11
c12
c1n
c2n
cm1
cm2
cmn
cij
设xij(i=1,2,…,m, j=1,2,…,n)表示从Ai到Bj的运量
若运输问题(transportation problem)的总产量等于其总销量,即
则称该运输问题为产销平衡运输问题; 反之,称为产销不平衡运输问题
若xij表示从Ai到Bj的运量, 那么产销平衡问题的数学模型为
2
3
1
a2=27
a3=19
a1=14
供应量
供应地
运价
2
3
4
1
b1=22
b2=13
b3=12
b4=13
销售量
销售地
6
7
5
3
8
4
2
7
10
5
9
6
举例说明
运输问题网络图
供应地约束
销售地约束
运输问题线性规划模型
运输问题的表格表示
二、运输问题数学模型的特点
1、平衡运输问题有有限最优解
对于平衡运输问题, 若令其决策变量
则xij(i=1,2,…,m; j=1,2,…,n)是问题的一可行解; 并且运输问题必有最优解(目标函数有下界, 且不会趋于)
0<=xij<=min{ai, bj}
其中
2、运输问题约束条件的系数矩阵
m
行
n
行
其系数矩阵A有m+n行,