模块三 物资调运问题的图上作业法

1、模块三 物资调运问题的图上作业法内容提要内容提要交通路线图和流向图的编制图上作业法的求解过程（重点）（重点）流向图的检验利用图上作业法解决车辆调度问题问题引入：问题引入：求下列问题的最优调运方案求下列问题的最优调运方案3.1 物资调运问题的图上作业法物资调运问题的图上作业法 所谓图上作业法图上作业法，就是利用生产地和消费地的地理分布，根据就近供应就近供应的原则，应用交通路线图交通路线图和货物产销平衡表货物产销平衡表，找出产销地之间吨公里数最小或总运费最低的运输路线（称为最优路线最优路线）.故图上作业法图上作业法只适合产销平衡的物资调运问题求最优调运方案。 1、交通路线图：、交通路线图：（也称为

2、网络图网络图）是反映产地与销地的交通路线及其距离的图。ACBGFDE1058979332524 交通路线图举例：ABHECI500006000030000200003000050000266239180393D80000F50000G50000115165317252349120 物资调运问题的交通路线图举例2一是有发点（产地）和收点（销地） ；二是有发点的发量及收点的收量；产地（发点）用“”表示，产量写在圆圈内销地（收点）用“”表示，销量写在方框内三是有连接收点、发点的交通线路以及与之相对应的线路长度或运价；距离或运价写在弧的旁边交通路线图交通路线图（网络图网络图）特征特征 ：如何绘制交通路

3、线图呢？如何绘制交通路线图呢？ 交通路线图的绘制：交通路线图的绘制： 第一步是先标出产地（发点）和销地（收点），产地第一步是先标出产地（发点）和销地（收点），产地“” 内填上该产地的产量（内填上该产地的产量（发量发量)；销地；销地“” 内填上该销地的内填上该销地的销量销量(收量收量)。 第二步画出连接这些点的交通路线，在每段路线旁注明该第二步画出连接这些点的交通路线，在每段路线旁注明该路线的长度或运价。路线的长度或运价。B155510AC201015201083097树状图（不成圈图）环型图（成圈图）2 、物资调运的流向图、物资调运的流向图（流向图）流向图） 在交通图上交通图上表示物资流向的图

4、被称为流向图称为流向图。流向图可以表示物资调运的方案。流向图可以表示物资调运的方案。 例：设发点A发量为10t ；收点B收量也是10t 。把A点的10t物资运到B点的交通流向图如下：(10)(10)(10)(10)思考：箭头方向代表什么？带箭头直线放置位置如何？直线思考：箭头方向代表什么？带箭头直线放置位置如何？直线右侧数字代表什么？一定加括号吗？右侧数字代表什么？一定加括号吗？物资调运流向图的一些规定：物资调运流向图的一些规定：1、箭头方向表示物资运输的方向（流向流向）；2、带箭头直线（流向流向）画在A到B前进方向的右侧右侧 ；3、运输物资的数量（流量流量）写在箭头线的旁边，加加小括号小括号

5、。4、流向不能直接跨越不能直接跨越路线上的收点、发点、交叉点5、同一段线路上的多条流向必须合并。即任何一段任何一段线路（弧）上最多只能显示一条流向！线路（弧）上最多只能显示一条流向！6、除端点外，任何点(产、销地产、销地)都可以流进和流出(10)(10)(10)(5)(5)(5)555510101010AABBCCDDEE图3-1 图3-2判断下列流向图正确与否？为什么？判断下列流向图正确与否？为什么？图图2 违背了违背了“流向不能直接跨越路线上的收点、发点、交叉点”1010(20)乙甲201010(20)乙甲判断下列流向图正确与否？为什么？判断下列流向图正确与否？为什么？101020乙甲1

6、1）2 2）3 3）4 4）20101020乙甲图图2） 违背了违背了“流向位置” 图图3 3） 违背了违背了“流量需加括号”图图4 4） 违背了违背了“流向位置” 及及“流量需加括号”3.2 利用流向图求解物资调运问题利用流向图求解物资调运问题 最优流向图最优流向图 总吨公里数最小的流向图 把每一条弧上的流量乘以相应的距离，再求和 怎样得到最优流向图？怎样得到最优流向图？ 作出第一个流向图 检验其是否最优？ 若是，结束； 否则，调整，直到最优。3.2 利用流向图求解物资调运问题利用流向图求解物资调运问题根据交通图成圈与否，图上作业法分为根据交通图成圈与否，图上作业法分为：3.2.1 3.2.

7、1 不成圈问题的图上作业法求物资调运问题不成圈问题的图上作业法求物资调运问题3.2.2 3.2.2 成圈问题的图上作业法求物资调运问题成圈问题的图上作业法求物资调运问题3.2.1 不成圈问题的图上作业法求物资调运问题不成圈问题的图上作业法求物资调运问题 交通线路图不成圈（树状交通路线）问题，是指交通图中没有任何回路出现，是树状的。即所有供应点（发点发点）和需求点（收点收点）之间不构成任何圈， 树状交通图问题的求解原则：树状交通图问题的求解原则：只要流向图中无对流出现就是最优流向图，即最优只要流向图中无对流出现就是最优流向图，即最优调运方案调运方案. . 思考：什么是对流？思考：什么是对流？流向

8、图中对流现象：流向图中对流现象： 所谓对流就是在一段线路上有同一种物资出现相对运输现象（往返运输）（同一段线路上，两个方向都有流向），如下图所示：201010(10)(20)乙甲 不成圈问题的图上作业法求解步骤：不成圈问题的图上作业法求解步骤：第一步：第一步：编制货物产销平衡表；第二步：第二步：在交通示意图上，从各端点各端点开始按“供需归邻供需归邻站法站法” 作流向图，逐步向中间逼近，直至收点与发点得到全部满足为止。第三步：第三步：检验其是否最优（是否存在对流是否存在对流）；第四步：第四步：没有对流，即为最优。没有对流，即为最优。把最佳调运路线的结果填入货物产销平衡表后得最佳调运方案；无圈流向

9、图是否最优判定定理：无圈流向图是否最优判定定理：只要无圈流向图中没有对流，就一定是最优的。 （有无对流）（有无对流）【例【例3.1】求不成圈问题的最优调运方案】求不成圈问题的最优调运方案v第一步：编制货物产销平衡表；第一步：编制货物产销平衡表；320表表3-1 货物产销平衡表货物产销平衡表 销地（收点）销地（收点）产地（发点）产地（发点） B1B1 B2 B2 B3B3 B4B4发货量发货量 A1A1100 A2A220 A3 A360 A4 A4140收货量收货量1402060100v口诀：口诀：抓各端，供需归邻站抓各端，供需归邻站v 即：从各端点开始，先满足各端点的要求，逐步向中间即：从各

10、端点开始，先满足各端点的要求，逐步向中间逼近，直至收点与发点得到全部满足为止。逼近，直至收点与发点得到全部满足为止。（2020）（100100）（4040）（2020）（4040）（100100）（120120）检查流向图中是否存在对流现象： 所谓所谓对流对流就是在一段线路上有同一种物资出现相就是在一段线路上有同一种物资出现相对运输现象（往返运输）（同一段线路上，两个对运输现象（往返运输）（同一段线路上，两个方向都有流向），如下图所示：方向都有流向），如下图所示：201010(10)(20)乙甲图 4-4经检验：初始方案中无对流现象，故方案为最优！经检验：初始方案中无对流现象，故方案为最优！第

11、四步：得到最优调运方案第四步：得到最优调运方案1 1 销地（收点）销地（收点）产地（发点）产地（发点） B1B1 B2 B2 B3B3 B4B4发货量发货量 A1A1100100 A2A22020 A3 A320202060 A4 A440100140收货量收货量1402060100表表3.2 货物最佳调运方案货物最佳调运方案第三步：得到最优调运方案第三步：得到最优调运方案2 2 销地（收点）销地（收点）产地（发点）产地（发点） B1B1 B2 B2 B3B3 B4B4发货量发货量 A1A1100100 A2A22020 A3 A3402060 A4 A440100140收货量收货量14020

12、60100表表3.2 货物最佳调运方案货物最佳调运方案说明：说明： 交通路线不成圈问题的图上作业法求得的最优调运交通路线不成圈问题的图上作业法求得的最优调运方案不一定是唯一的！不同的最佳调运方案的总成本方案不一定是唯一的！不同的最佳调运方案的总成本一定都是相同的。一定都是相同的。 因为上例中没考虑各地之间运输距离。 不成圈问题的图上作业法求解步骤：不成圈问题的图上作业法求解步骤：第一步：编制货物产销平衡表第一步：编制货物产销平衡表；第二步：在交通示意图上，从第二步：在交通示意图上，从各端点各端点开始开始按按“供需归邻供需归邻站法站法” 作流向图，逐步向中间逼近，直至收点与发点得作流向图，逐步向

13、中间逼近，直至收点与发点得到全部满足为止。到全部满足为止。第三步：检验其是否最优第三步：检验其是否最优（是否存在对流）（是否存在对流）；第四步：第四步：没有对流，即为最优。没有对流，即为最优。把最佳调运路线的结果填把最佳调运路线的结果填入货物产销平衡表；入货物产销平衡表；练一练练一练 现有现有A A、B B、D D货物货物2424吨运往吨运往E E、F F、G G地，它们的发量、收量以及交通如地，它们的发量、收量以及交通如下图所示问应如何安排调运计划，才能使运输量（吨公里）最小。下图所示问应如何安排调运计划，才能使运输量（吨公里）最小。C C为为中转站。中转站。 答案答案一是有发点（产地）和收

14、点（销地） ；二是有发点的发量及收点的收量；产地（发点）用“”表示，产量写在圆圈内销地（收点）用“”表示，销量写在方框内三是有连接收点、发点的交通线路以及与之相对应的线路长度或运价；距离或运价写在弧的旁边交通路线图（网络图）交通路线图（网络图）特征特征 ：物资调运流向图的一些规定：物资调运流向图的一些规定：1、箭头方向表示物资运输的方向（流向流向）；2、带箭头直线（流向流向）画在A到B前进方向的右侧右侧 ；3、运输物资的数量（流量流量）写在箭头线的旁边，加加小括号小括号。4、流向不能直接跨越不能直接跨越路线上的收点、发点、交叉点5、同一段线路上的多条流向必须合并。即任何一段任何一段线路（弧）上

15、最多只能显示一条流向！线路（弧）上最多只能显示一条流向！6、除端点外，任何点(产、销地产、销地)都可以流进和流出根据交通图成圈与否，图上作业法分为根据交通图成圈与否，图上作业法分为：3.2.1 3.2.1 不成圈问题的图上作业法求物资调运问题不成圈问题的图上作业法求物资调运问题3.2.2 3.2.2 成圈问题的图上作业法求物资调运问题成圈问题的图上作业法求物资调运问题 不成圈问题的图上作业法求解步骤：不成圈问题的图上作业法求解步骤：第一步：编制货物产销平衡表；第一步：编制货物产销平衡表；第二步：在交通示意图上，从第二步：在交通示意图上，从各端点各端点开始按开始按“供需归邻站法供需归邻站法” 作

16、流向图，逐步向中间逼近，直至收点与发点得到全部满作流向图，逐步向中间逼近，直至收点与发点得到全部满足为止。足为止。第三步：检验其是否最优（第三步：检验其是否最优（是否存在对流是否存在对流）；）；第四步：第四步：没有对流，即为最优。没有对流，即为最优。把最佳调运路线的结果填入货把最佳调运路线的结果填入货物产销平衡表后得最佳调运方案；物产销平衡表后得最佳调运方案；无圈流向图是否最优判定定理：无圈流向图是否最优判定定理：只要无圈流向图中没有对流，就一定是最优的。 （有无对流）（有无对流）v试求下列交通图的最优调运方案试求下列交通图的最优调运方案324786451A1A2B1B3B2A5A3A4B4从

17、各端点开始满足各端点的要求，按从各端点开始满足各端点的要求，按“供需归供需归邻站邻站”逐步向中间逼近。逐步向中间逼近。v口诀：口诀：抓各端，供需归邻站抓各端，供需归邻站v即：先满足端点的要求，逐步向中间逼近，直至即：先满足端点的要求，逐步向中间逼近，直至收点与发点得到全部满足为止。收点与发点得到全部满足为止。324786451A1A2B1B3B2A5A3A4B4（3）（4）（2）（3）（4）（7）（3）（10）思考：对下面交通图求最优调运方案？454786454A1A2B1B3B2B5A38B422734633.3.1物资调运成圈问题的图上作业法求解物资调运成圈问题的图上作业法求解 交通线路图

18、成圈问题是指交通路线示意图中有些路线构成回路的情况。 在一个在一个没有对流的没有对流的流向图中，对逐个圈检查是否有流向图中，对逐个圈检查是否有迂回！迂回！如果每一个圈上的内圈流向（如果每一个圈上的内圈流向（流向在圈内流向在圈内）和外圈流向（）和外圈流向（流向流向在圈外在圈外）的总长度都不超过圈长的一半，这个流向图就是最优）的总长度都不超过圈长的一半，这个流向图就是最优的；的；(有无迂回有无迂回) 如果图中没有圈，只要没有对流，就一定是最优的。如果图中没有圈，只要没有对流，就一定是最优的。（有无对流）（有无对流）定理：定理： 判断有圈流向图是否最优基本定理判断有圈流向图是否最优基本定理流向图中不

19、合理的现象：迂回流向图中不合理的现象：迂回迂回迂回：如果流向图中某一个圈的内圈流向总长（简称内圈长）或者外圈流向总长（简称外圈长）超过整个圈长的一半，就称为迂回运输迂回运输。外圈长为外圈长为 1642 392 ，内圈长为内圈长为1 6782 有圈流向图的补充规定有圈流向图的补充规定 顺时针顺时针方向的流向必须画在圈的方向的流向必须画在圈的内侧内侧，称为内，称为内圈流向圈流向 逆时针逆时针方向的流向必须画在圈的方向的流向必须画在圈的外侧外侧，称为外，称为外圈流向圈流向3.3.1 成圈问题图上作业法的求解步骤：成圈问题图上作业法的求解步骤： 第一步：丢边破圈。第一步：丢边破圈。 方法：方法：“丢边

20、破圈丢边破圈”。即从流向图中任取一圈，丢掉一条边，破去一个圈。再从剩下的图中取圈，丢边破圈，直到图中无圈为止。 注意注意1 1：丢边时，是丢掉圈中长度最大的边。：丢边时，是丢掉圈中长度最大的边。 第二步：在无圈的交通图上作流向图。第二步：在无圈的交通图上作流向图。 原则：按按“供需归邻站供需归邻站”，先端点后中间点做流向图。，先端点后中间点做流向图。当某条边无流向时，必须填上运输量为零的虚流向。 第三步：补上丢掉的边，对逐个圈检查有无迂回。第三步：补上丢掉的边，对逐个圈检查有无迂回。 第四步：若有迂回，调整有迂回的圈使之最优。第四步：若有迂回，调整有迂回的圈使之最优。例例3.2 设某集团公司有

21、3个配送中心，要为该公司所属的5个超市补充库存，各配送中心和超市的位置如下图，图中的数字表示相应点之间的里程，各配送中心供应量和各超市的需求量也在图中标出. 试确定最佳调运方案.454786454A1A2B1B3B2B5A38B42273463解： 第一步：变有圈为无圈。第一步：变有圈为无圈。 方法：方法：“丢边破圈丢边破圈”。在流向图中任取一圈，丢掉一条边，破去一个圈。再从剩下的图中取圈，丢边破圈，直到图中无圈。 注意：注意：丢边时，往往是丢掉圈中长度最大的边。如图所示454786454A1A2B1B3B2B5A38B42273463 第二步：在无圈的交通图上作流向图。第二步：在无圈的交通图

22、上作流向图。 原则：原则：按按“供需归邻站供需归邻站”，先端点后中间点，先端点后中间点，要求每个边都有流向。当某条边无流向时，必须填上运输量为零的虚流向。454786454A1A2B1B3B2B5A38B42273463（4）（8） （1）（5）（3）（2）（8）454786454A1A2B1B3B2B5A38B42273463（4）（5）（8） （1）（3）（8）454786454A1A2B1B3B2B5A38B42273463（4）（5） 第三步：补上丢掉的边，在第三步：补上丢掉的边，在无流向的边上填上运输无流向的边上填上运输量为零的虚流向，对逐个圈量为零的虚流向，对逐个圈检查有无迂回。检

23、查有无迂回。 圈B5B4B3A2的圈长=4+4+5+8=21, 内圈长= 4+4+5=1321/2，有迂回！ 所以流向图不是最优流向图。需要调整。 第四步：对方案进行调整。第四步：对方案进行调整。 方法：方法：将流向图中有迂回的圈调整为无迂回的将流向图中有迂回的圈调整为无迂回的 目的是：目的是：将一个不是最优的流向图逐步调整为最将一个不是最优的流向图逐步调整为最优的流向图；优的流向图；（1）外调整法：）外调整法： 流向图的调整（方案的调整）方法：流向图的调整（方案的调整）方法：适用于：不合格圈适用于：不合格圈内圈流向内圈流向的总长度的总长度超过圈长的一半超过圈长的一半时。时。找出这个圈的内圈流

24、量中的最小值（称为找出这个圈的内圈流量中的最小值（称为调整量调整量），然后），然后所有的外圈流量都加上这个调整量，所有的内圈流量都减去所有的外圈流量都加上这个调整量，所有的内圈流量都减去这个调整量。无流量的边添上外圈流向和流量。这个调整量。无流量的边添上外圈流向和流量。适用于：适用于：不合格圈的不合格圈的外圈流向外圈流向的总长度的总长度超过圈长的一半时超过圈长的一半时找出这个圈中外圈流量中的最小值（找出这个圈中外圈流量中的最小值（调整量调整量），然后每个），然后每个外圈流量都减去这个调整量，每个内圈流量都加上这个调整外圈流量都减去这个调整量，每个内圈流量都加上这个调整量。无流量的边添上内圈流向

25、和流量。量。无流量的边添上内圈流向和流量。（2）内调整法：）内调整法：最优方案即是：所有圈的内、外圈的总长度同时小于圈长的一半！最优方案即是：所有圈的内、外圈的总长度同时小于圈长的一半！ 即所有的圈不存在迂回。即所有的圈不存在迂回。 第四步：对方案进行调整。第四步：对方案进行调整。 方法方法：由于圈B5B4B3A2的内圈长=4+4+5=1321/2。故采用“外外调整法调整法”：找出有迂回圈的内圈流量最小值（2 2），每个内圈内圈流量都减少减少2，外圈外圈流量都增加增加2 2，并在无流量的边B5A2上增加外圈流向和流量2 2，得到新的交通流向图。454786454A1A2B1B3B2B5A38B

26、42273463（4）（8）（1）（5）（2）（1）（6） 第五步：对新方案进行检验。第五步：对新方案进行检验。 圈B5B4B3A2的圈长=4+4+5+8=21,内圈长= 4+5=921/2，外圈长= 825/2，有迂回，所以流向图不是最优流向图。故需要调整。使用外调整法 第六步：对方案进行调整。第六步：对方案进行调整。 方法：找出有迂回圈的内圈流量中最小的流量（1 1），），内圈流量都减少1，外圈流量都增加1 1，并在无流量的（边B1A3）上增加外圈流向和流量1 1，并在无流量的边B1A3上增加外圈流向和流量1 1，得到新的交通流向图如下：454786454A1A2B1B3B2B5A38B4

27、2273463（3）（7）（1）（4）（2）（2）（6）图图 3.4 第七步：对新方案进行检验。第七步：对新方案进行检验。 圈A3B1B2A1B3B4的圈长=7+2+3+6+4+3=25,内圈长= 3+3+2=825/2，外圈长=4+7 装货装货量）则是空车的发点，其发量等于（卸下的货物量）则是空车的发点，其发量等于（卸下的货物- -装货量的差装货量的差额）；如果（卸货量额）；如果（卸货量 装货量）则它是空车的收点，其收量等于装货量）则它是空车的收点，其收量等于（装货量（装货量- -卸货量的差）；卸货量的差）；分析：分析：例如：某地要装货例如：某地要装货80t80t，卸货，卸货50t50t，则

28、在把，则在把50t50t货物卸下后，汽车货物卸下后，汽车就可以顺便带走就可以顺便带走50t50t货物，这样，只要再给该地货物，这样，只要再给该地30t30t空车就可以空车就可以了。所以，此点是空车的收点，收量为了。所以，此点是空车的收点，收量为30t30t。反之，某地要装。反之，某地要装货货50t50t，卸货，卸货80t80t，则在把，则在把80t80t货物卸下后，顺便装货物卸下后，顺便装50t50t货物带走，货物带走，这样，此点就发出了这样，此点就发出了30t30t的空车。于是，该点为空车的发点，的空车。于是，该点为空车的发点，发量为发量为30t30t。 故此：车辆调度问题可以化归物资调运问题，这里调运的物资故此：车辆调度问题可以化归物资调运问题，这里调运的物资是空车。可见，解决车辆调度问题仍然可以用图上作业法。是空车。可见，解决车辆调度问题仍