文档介绍：1
第四章运输问题
运输问题与有关概念
运输问题的求解—表上作业法
运输问题应用—建模
本章内容重点
2
问题的提出
一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地,在每个产地的供应量与每个销地的需求量已知,并知道各地之间的运输单价的前提下,如何确定一个使得总的运输费用最小的方案。
3
:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?
4
解: 产销平衡问题:
总产量= 总销量
设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表:
5
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)
6
1 1 1 0 0 0
0 0 0 1 1 1
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
系数矩阵
7
模型系数矩阵特征
+n行,分别表示各产地和销地;mn列,分别表示各决策变量;
1,其余为 0,分别表示只有一个产地和一个销地被使用。
8
一般运输问题的线性规划模型及求解思路
一般运输问题的提法:
假设 A1, A2,…,Am 表示某物资的m个产地;B1,B2,…,Bn 表示某物资的n个销地;si表示产地 Ai 的产量;dj 表示销地 Bj 的销量;cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价(表4-3)。如果
s1 + s2 + …+ sm = d1 + d2 + …+ dn
则称该运输问题为产销平衡问题;否则,称产销不平衡。首先讨论产销平衡问题。
9
表4-3 运输问题数据表
销地
产地
B1 B2 … Bn
产量
A1
A2
┇
Am
c11 c12 … c1n
c21 c22 … c2n
┇┇┇┇
cm1 cm2 … cmn
s1
s2
┇
sm
销量
d1 d2 … dn
设 xij 为从产地 Ai 运往销地 Bj 的运输量,根据这个运输问题的要求,可以建立运输变量表(表 4-4)。
10
表4-4 运输问题变量表
销地
产地
B1 B2 … Bn
产量
A1
A2
┇
Am
x11 x12 … x1n
x21 x22 … x2n
┇┇┇┇
xm1 xm2 … xmn
s1
s2
┇
sm
销量
d1 d2 … dn