第五章 运输问题

第五章 运输问题
1
一. 物资调配问题
调运规划问题描述 设 某种要调运的物资，有一组供应点(产地或称发点)m个，一组需求 点(销地或称收点)n个，如果每个供应点的供应量及每个需求点的需求量 都已经确定，即第i个产地有ai 单位的物资发出，第j个需求点需要收进bj 单位的物资；并且从每—个产地到每一个销地的单位运价是已知的，假 定把单位物资从第i个产地调运到第j个销地去的单位运价为cij 。 调运规划问题也叫运输问题 物资调运规划的目的：
准检验数计算过程 空格（1，1）= u1+v1 = 2+0 = 2 （3，1）=u3+v1= -3+0 = -3 （1，2）=u1+v2= 2+7 = 9 （2，2）=u2+v2= 1+7 = 8 （3，3）=u3+v3= -3+1 = -2 （2，4）=u2+v4= 1+8 = 9
利用运价表与准检验数表求检验数
第3步：求检验数
检验数 Δxij = cij − (ui + v j )
准检验数表 运价表 B1 A1 A2 A3 3 1 7 B2 11 9 4 B3 3 2 10 B4 10 8 5 A1 A2 A3 B1 [2] 1 [-3] B2 [9] [8] 4 B3 3 2 [-2] B4 10 [9] 5
B3 3 2 10 500
B4 10 8 5 600
供应量(t) 700 400 900 2000
A1 A2 A3 需求量(t)
5
解：（1）列出物资调运平衡表和运价表
表5-2 供需平衡表 需 运价 供 A1 A2 A3 需求量(t) 300 600 500 600 表5-3 运价表 运价 料库 A1 A2
运价表 运价 料库 A1 A2 A3 工地 B1 3 1 7 B2 11 9 4 B3 3 2 10 B4 10 8 5
2
1
供需平衡表 需 运量 供 A1 A2 A3 需求量(t) 300 600 500 600 B1 B2 B3 B4 供应量(t) 700 300 100 400 900 2000
检验数表 “运价表” 减 “准检验数表”
A1 A2 A3 10 B1 1 B2 2 1 12 -1 B3 B4
检验结果：检 验数出现负 值，根据最优 方案判断准 则，该方案不 是最优方案。
3）调整调运方案
当判定一个初始调运方案不是最优调运方案时，就要在检验数出现负 值的该空格内进行调整。 如果检验数是负值的空格不只一个时，一般选择检验数为负值且绝对 值最大的空格作为具体的调整对象。
运价表 运价 料库 A1 A2 A3 工地 B1 3 1 7 B2 11 9 4 B3 3 2 10 B4 10 8 5
2 5
仿照前面的方 法，一直作下去， 就可得到如左图所 示的运价表和平衡 表。
此时，在运价表中 只有方格(1，4)处的 运价没有划掉，B4尚 有300t的需求，而A1 刚好还有300t的物资 可以供应，为了满足 供需平衡，所以最后 在平衡表上应有(1，4) ＝300。这样就得到表 5—6的初始调运方 案。
6
B1
B2
B3
B4
供应量(t) 700 400 900 2000
平衡表中填入的数 字表示供需点之间的 调运量； 空格表示双方不发 生调运关系
工地
B1 3 1 7
B2 11 9 4
B3 3 2 10
B4 10 8 5 平衡表和运价表是表上作业法 的基本资料和运算的依据。 表上作业法的实质就是利用运 价表在平衡表上进行求解。
调整后的调运方案
运量 供 A1 A2 A3 需求量(t) 300 300 1 600 4 600 500 需 B1 B2 B3 500 3 0 2 B4 200 10 100 8 300 5 600 供应量(t) 700 400 900 2000
调整后的检验数
B1 A1 A2 A3 9 2 B2 2 4 1 12 B3 B4
13
检验数：调运方案的每个空格所形成的闭回路上，作单位物资的运量
调整，总可以计算出相应的运费是增加还是减少。我们把所计算出来 的每条闭回路上调整单位运量而使运输费用发生变化的增减值，称其 为检验数。
如果检验数小于零，表示在该空格的闭回路上调整运量使运费减少； 如果检验数大于零，则表示在该空格的闭回路上调整运量会使运费增加。
A3
（2）编制初始调运方案
物资调运规划其总的目的是寻求一个运输费用最少的最优调运方案。 一般最优方案是由初始方案经过反复调整得到的。因此，编制出较好 的初始调运方案非常重要。 最好的调运方案是使运费最省的方案，因此可以用最小元素法来确定 初始调运方案。 所谓最小元素法，就是按运价表依次挑选运费少的供——需点尽量优 先安排供应的调运方法。
1
4
3
供需平衡表 需 运价 供 A1 A2 A3 需求量(t) 300 B1 B2 B3 400 300 600 600 500 100 300 600 B4 供应量(t) 700 400 900 2000
表5-6 初始调运方案
B1 B2 B3 B4
运量
价格
运量 供 A1 A2 A3
需
供应量(t)
Min S = ∑∑ cij ⋅ xij
i =1 j =1
m
n
约束条件
3
⎧n ⎪∑ xij = ai (i = 1,2,L , m) ⎪ j =1 ⎪m ⎪∑ xij = b j ( j = 1,2, L , n) s.t ⎨ i =1 n ⎪m ⎪∑ ai = ∑ b j ⎪ i =1 j =1 ⎪ x ≥ 0 (i = 1,2, L, m; j = 1,2, L , n) ⎩ ij
通过计算其检验数全部非负，此 方案为最优方案。
运输费用为： S＝3×500十10×200十8×100十 1×300十4×600十5×300 ＝8500(元) 该值小于初始调运方案的总运费。
B1 A1 A2 A3 300 600 B2 B3 400 100 B4 300 负 300
X13 400+100=500 X23 100-100=0
X14 300-100=200 X24 0+100=100
调整过程： （1）作出负值所在空格的闭回路，本例为空格x24，闭回路如上图所示。 （2）沿闭回路在各奇数次转角点中挑选运量的最小数值作为调整量。本例 是将x23方格的100作为调整量，将这个数填入空格x24内，同时调整该闭回路 中其他转角点上的运量，使各行、列保持原来的供需平衡．这样使得到一个 新的调运方案。
12
需 供 A1 A2 A3 需求量(t)
B1
B2
B3
B4
供应量(t)
400 300 600 300 600 500 100
300
700 400
300 600
900 2000
空格(1，1)： (1，1)—(1，3)—(2，3)—(2，1)一(1，1) 空格(3，1)： (3，I)—(2，1)—(2，3)—(1，3)一(1，4)—(3，4)—(3，1) 对所有的空格，都可以用同样的方法画出一条闭回。
7
运价表 工地 运价 料库 A1 A2 A3 B1 3 1 7 B2 11 9 4 B3 3 2 10 B4 10 8 5
1
供需平衡表 需 运量 供 A1 A2 A3 需求量(t) 300 600 500 600 B1 B2 B3 B4 供应量(t) 700 300 400 900 2000
首先，在运价表内 找出最小的运价，对本 例而言，方格(2，1)数 值是1，最小，这样，供 应点A2尽可能地满足B1工 地的需要，于是在平衡 表中有(2，1)＝300，即 在空格(2，1)中填入数 字300。 此时，由于工地B1已 经全部得到满足，不需 要其他仓库供应给它 了，运价表中的第一列 数字己不起作用，因此 将运价表第一列划去， 并标注符号①，
制订一个合理的调运方案； 确定m个产地与n个销地之间的供需联系和数量的最优搭配； 确定具体的运输路线，使总的运输费用最低。
2
1. 数学模型
设供应点为Ai，该供应点的供应量是ai，（i=1,2,…,m）； 设需求点为Bj，该需求点的需求量是bi，（j＝1,2,…,n）； cij为从第i个供应点到第j个需求点的单位运价； 由供应点Ai发往需求点Bj的物资调运量是xij单位。 假设m个供应点的总供应量等于n个需求点的总需求量，（这样，调运问题满 足供需平衡，称为平衡运输问题）。这时，由各供应点Ai调出的物资总量应等 于它的供应量ai(i=1,2,…,m)；而每一个需求点Bj调入的物资总量应等于它的 需求量bj(j=1,2,…,n)。 目标函数：
400 300 1 600 4 300 600 100
3 2
300 10
700 400
300 500 600
5
900 2000
需求量(t)
根据初始调运方案的运输量和单位运价，可以计算初始调运方案的运 输费用为： S=1*300+4*600+3*400+2*100+10*300+5*300=8600(元)
然后，在运价表未 划去的各行、列中，再 选取一个最小的运价， 本例，即(2，3)＝2最 小，让A2料库尽量供应 满足B3工地的需要。由 于A2库储量400t已供应 给B1工地300t了，所以 最多还能供给B3工地 100t。于是在平衡表 (2，3)空格填入100；相 应地由于仓库A2所储物 资已全部供应完毕，因 此，在运价表中与A2同 行的运价也不再起作 用，所以也将它们划 去，并标注符号②。
4
4. 表上作业法解题实例
例题1 某公司下属三个储存某种物资的仓库，供应四个工地的需要。三个仓库的 供应量和四个工地的需求量以及由各仓库到各工地调运单位物资的运价(元／吨) 由表5—1给出，试求运输费用最少的调运方案。