运筹学教学资料运筹学第3章第1节.pptx

学习要点:
1. 掌握运输问题的数学模型及其系数矩阵的特殊
结构。
2. 掌握表上作业法及其在产销平衡问题求解中的
应用。
3. 掌握产销不平衡运输问题的求解方法。
4. 了解应用LINGO求解运输问题的方法。
运输问题(The Transportation Problem, TP)是一类特殊而且极其典型的线性规划问题。
运输问题可用单纯形法来求解。由于运输问题数学模型具有特殊的结构,存在一种更简便的计算方法。
表上作业法——实质仍是单纯形法。
从运输问题的解决及表上作业法的理论解释,我们可更充分体会到单纯形法的魅力。
运输问题的数学模型
一、运输问题的数学模型
某公司从三个产地A1,A2,A3将物品运往四个销地B1,
B2,B3,B4, 各产地的产量、各销地的销量和各产
地运往各销地每件物品的运费如下表所示,问:应如
何调运可使总运输费用最小?
B1
B2
B3
B4
产量
A1
2
9
10
7
9
A2
1
3
4
2
5
A3
8
4
2
5
7
销量
3
8
4
6
运输问题的数学模型
解:本问题是产销平衡的,即总产量等于总销量:
9+5+7=3+8+4+6=21
令x i j 表示从A i到B j 的调运量,
B1
B2
B3
B4
产量
A1
x11
x12
x13
x14
9
A2
x21
x22
x23
x24
5
A3
x31
x32
x33
x34
7
销量
3
8
4
6
运输问题的数学模型
B1
B2
B3
B4
产量
A1
2
9
10
7
9
A2
1
3
4
2
5
A3
8
4
2
5
7
销量
3
8
4
6
满足产销平衡要求的调运方案把各个产地的产量都能调运完,保障供给,即
对于A3成立
对于A2成立
对于A1成立
满足产销平衡要求的调运方案要求各个销地的销量都能满足,即
对于B1成立
对于B2 成立
对于B3成立
对于B4成立
运输问题的数学模型
另外从Ai到Bj 运输物资的调运量不能为负,即
调运方案的总费用为
综合上述分析,得到本案例的数学模型
运输问题的数学模型
运输问题的数学模型
运输问题一般表述:
设某种物资有m个产地 A1,A2,…,Am ,
生产量分别为a1,a2,…,am ;
n个销地 B1,B2,…,Bn,销售量分别为b1,b2,…, bn ;
cij 表示 i 地往 j 地的单位运价。
在产销平衡条件下,求总运费最小的调运方案。
运输问题的数学模型
bn
…
b2
b1
销量
am
cmn
…
cm2
cm1
Am
…
…
…
…
…
…
a2
c2n
…
c22
c21
A2
a1
c1n
…
c12
c11
A1
产量
Bn
…
B2
B1
变化:
1)有时目标函数求最大。如求利润最大或营业额最大等;
2)当某些运输线路上的能力有限制时,在模型中直接加入约束条件(等式或不等式约束);
3)产销不平衡时,可加入假想的产地(销大于产时)或销地(产大于销时)。
bn
…
b2
b1
销量
am
cmn
…
cm2
cm1
Am
…
…
…
…
…
…
a2
c2n
…
c22
c21
A2
a1
c1n
…
c12
c11
A1
产量
Bn
…
B2
B1
运输问题的数学模型