图上作业法专题

一、图上作业法在运输中，若使用同一种运输工具，则运费的计算往往仅与运送物资的多少及里程有关。因此，在求最佳的运输方案时，用吨公里作为度量的标准比用运费作为度量标准更加方便、实用。在求解最佳运输方案时，用吨公里作为度量单位，还可以在已经画出的交通图上进行，操作起来较为简单、方便、直观、快捷。在铁路、公路等交通部门经常使用这种方法决策最优运输问题，这种方法被称为图上作业法。第一页，共53页。二、编制交通图和流向图交通图

反映发点（产地）与收地（销地）及交通线路及其距离组成的图形。发点用“○”表示，发出货物的数量记在“○”之内（单位：吨）收地（销地）用“□”表示，收取货物的数量记在“□”之内（单位：吨）两点之间的线路长度记在交通线路的旁边。第二页，共53页。1、交通图第三页，共53页。1、交通图第四页，共53页。2、流向图流向图:在交通图上表示物资流向的图被称为流向图。在图中每个发点吨数全部运完，每个收点所需吨数均已满足。第五页，共53页。2、流向图发点A到收点B的运输量，用括号括起。第六页，共53页。2、流向图关于流向图的一些规定箭头必须表示物资运输的方向流量写在箭头的旁边，加小括号。流向不能直接跨越路线上的收点、发点、交叉点任何一段弧上最多只能显示一条流向！即同一段弧上的多条流向必须合并。除端点外，任何点都可以流进和流出第七页，共53页。2、流向图第八页，共53页。2、流向图含有圈的流向图的补充规定顺时针方向的流向必须画在圈的内侧，称为内圈流向逆时针方向的流向必须画在圈的外侧，称为外圈流向第九页，共53页。内圈流向、外圈流向举例44（4）26图：4-644（4）26图：4-7第十页，共53页。二、对流向图的检验在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨—公里数是最小的调运方案。这就要注意在调运中不要发生对物流运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。第十一页，共53页。（1）不合理的现象1：对流（1）对流：所谓对流就是在一段线路上有同一种物资出现相对运输现象（往返运输）（同一段线路上，两各方向都有流向），如图4-4。甲乙两地是一种对流现象。如果把流向图改成图4-5，就可以避免对流现象，从而可以节约运输量20×10=200(吨公里)。第十二页，共53页。201010(10)(20)乙甲图4-4图4-5201010(10)(10)乙甲(20)第十三页，共53页。（2）不合理的现象2：迂回（2）迂回：当收点与发点之间的运输线路有两条或两条以上时（即交通图成圈），如果运送的货物不是走最短线路，则称这种运输为迂回运输。注：当交通图成圈时，如果流向图中内圈流向的总长（简称内圈长）或外圈流向的总长（简称外圈长）超过整个圈长的一半就称为迂回运输。例如某物资流向图如图4-6、4-7所示。第十四页，共53页。迂回运输的判断44（4）26图：4-644（4）26图：4-7显然：图4-6为迂回运输第十五页，共53页。（3）、正规（最优）流向图正规（最优）流向图：一个最优的调运方案，它的流向图必是无对流、无迂回的流向图，称这种流向图为正规流向图。物资调运的图上作业法就是寻找一个无对流、无迂回的正规流向图。步骤如下：作出一个无对流的初始可行方案；检验有无迂回若无，结束；否则，调整，直到最优。第十六页，共53页。三、图上作业法的求解过程1、无圈的交通图2、有圈的交通图方法：供需归邻站第十七页，共53页。1、交通图无圈情形【例1】求最优调运方案324786451A1A2B1B3B2A5A3A4B4第十八页，共53页。案例分析口诀：抓各端，各端供需归邻站即：先满足端点的要求，逐步向中间逼近，直至收点与发点得到全部满足为止。324786451A1A2B1B3B2A5A3A4B4（3）（4）（2）（3）（4）（7）（3）（10）图4-8第十九页，共53页。练一练第二十页，共53页。答案第二十一页，共53页。2、交通图有圈情形【例2】求最优调运方案454786454A1A2B1B3B2B5A38B42273463图4-9第二十二页，共53页。解题步骤：第一步：变有圈为无圈。方法：“丢边破圈”。即丢掉一条边，破去一个圈。注意：丢边时，往往是丢掉圈中长度最大的边。如图所示第二十三页，共53页。第一步：“丢边破圈”454786454A1A2B1B3B2B5A38B42273463第二十四页，共53页。第二步：在无圈的交通图上作流向图。原则：先外后内，先端点后中间点，要求每个边都有流向。当某条边无流向时，必须填上运输量为零的虚流向。第二十五页，共53页。第二步：作流向图454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（3）（2）（8）图4-10第二十六页，共53页。第三步：补上丢掉的边，检查有无迂回。圈B5B4B3A2的圈长=4+4+5+8=21,内圈长=4+4+5=13>21/2，有迂回，所以流向图不是最优流向图。需要调整。第二十七页，共53页。第四步：对方案进行调整。方法：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边B5B4），并补上原来丢掉的边（边B5A2），得到新的交通图。在此交通图上做新的流向图。第二十八页，共53页。第四步：调整方案454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（1）（2）（6）图4-11第二十九页，共53页。第五步：对新方案进行检验。圈B5B4B3A2的圈长=4+4+5+8=21,内圈长=4+5=9<21/2，外圈长=8<21/2.内圈、外圈的长度均不超过圈长的一半，所以该圈不存在迂回。圈A3B1B2A1B3B4的圈长=7+2+3+6+4+3=25,内圈长=2+3+6+3=14>25/2，有迂回，所以流向图不是最优流向图。需要调整。第三十页，共53页。第六步：对方案进行调整。方法：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边A1B3），并补上原来丢掉的边（边B1A3），得到新的交通图。在此交通图上做新的流向图。第三十一页，共53页。第六步：调整方案454786454A1A2B1B3B2B5A38B42273463（3）（7）（1）（4）（2）（2）（6）图4-12第三十二页，共53页。可验证：此方案中无迂回现象。即为最优方案。发收B1B2B3B4B5发货量A1347A24228A3145收货量44462第三十三页，共53页。练一练第三十四页，共53页。答案第三十五页，共53页。图上作业法有某物资7t，由发出点A1,A2,A3发出，发量分别为3,3,1(t)，运往收点B1,B2,B3,B4，收量分别为2,3,1,1(t)，收发量平衡，交通图如下图，问应如何调动，才使t·km最小？【例1】第三十六页，共53页。37（2）图上作业法【例3】有某物资7t，由A1，A2，A3发出，发量分别为3，3，1（t），运往收点B1，B2，B3，B4，收量分别为2，3，1，1（t），收发量平衡，交通图如图4—1所示，问应如何调运，才使t·km最小。。431213317354324第三十七页，共53页。3831、破圈求初始解1213317354324312114②检查有无迂回，方法水对流想图中的各圈进行检查，侃侃有无迂回。如果没有迂回，即该圈总长的一半均大于内流长和外流长，这个初始方案就是最优方案，如果其中某一圈有迂回，这个方案就不是最优方案，需要改进。在图中，圈A1B1B2A3B4的总长为23km，外流长为5+4+3=12km，大于圈长的一半，因而需要调整。在看圈B2A2B3A3其总长为13km，圈中内流长为3km，外流长为2km，都小于圈长的一半，因此此圈不必调整。第三十八页，共53页。39对圈A1B1B2A3B4的调整方法是：在外圈的个流量中，减去外圈的最小流量1t；然后在内圈的个流量中加上1t，在此圈中，因无内流量，所以无处可加；另外，在无流量的线段上，新添上内圈流量1t，这样得出新的流量图。方案调整1213317354324312114312133173543242121143第三十九页，共53页。40121331735432421211432121331735434231431在圈B2A2B3A3中外圈长为4+3=7大于圈长的一半，调整为内圈加“1”外圈减“1”此时两个圈都没有迂回是最优方案总的TKM为：7*1+2*5+1*4+3*2=27方案调整第四十页，共53页。4187545469834665757代表仓库代表需求第四十一页，共53页。42最短路问题

2、分析还没有P标号的各点，比较T(j)和P(1)+l1j，l1j为V1到Vj的弧长。将Vj的新标号取较小者，即T(j)=min[T(j),P(1)+l1j]。如果[P(1)+l1j]<T(j)，则用P(1)+l1j代替T(j)作为Vj点的新的T标号。

T(B)=min[T(B),P(A)+l12]=min[∞,0+3]=3

T(C)=min[T(C),P(A)+l13]=min[∞,0+4]=4

点V2的T标号的数最小，令P(2)=16。

1、将A标上P标号0，即P(1)=0，表示从A到A的距离为0。给其他点（B～F）标上T标号，即T(j)=∞，j=2,3,4,5,6。F5A0ECDB37454343第四十二页，共53页。43

3、以点B（刚得到标号的点）作为比较基础，重复上述过程，即比较T(j)与[P(2)+l2j]，j=3,4,5,6取较小的数作为Vj的新的T标号。

T(D)=3+5=8T(C)=4

T(E)=3+7=10

比较T(D)、T(E)、T(C)，其中T(C)为最小，将点C的T标号改为P标号：P(C)=4。

A03FECDB374543445第四十三页，共53页。44同理T(D)=4+4=8比较T（D），T（E）其中T（D）最小，令P（D）=8A03FECDB3745434485第四十四页，共53页。45T（E）=3+8=11T（F）=8+4=12T（E）=3+7=10其中T（E）=10最小令P（E）=10A03FECDB374543448105第四十五页，共53页。46T（F）=10+5=15T（F）=12其中T（F）=12最小，则令P（F）=12最短路为12A-B-D-FA-C-D-FA03FECDB37454344810125第四十六页，共53页。3131213A1B2A2B3A3B4B174432435第四十七页，共53页。在上图的基础上做一个无对流的流向图。注意：与表上作业法类似，表上作业法要求有调运量的格子数应该是收点数+发点数-1。图上作业法要求在流向图上的箭头数（有调运量的边数）也应为收点数+发点数-1。这一要求也可以等价地表述为：在去线破圈后得到的不成圈的交通图上，要求每边都应该有流向。3131213A1B2A2B3A3B4B1443235(3)(1)(2)(1)(1)第四十八页，共53页。因此，某一边无流向时，必须在这一边上添上调运量为0的虚流向，和其它流向同样对待。按照这一要求，应在A3边上添上虚流向。于是，再补上去掉的边，得下图：3131213A1B2A2B3A3B4B144323