图上作业法专题

图上作业法专题一、图上作业法在运输中，若使用同一种运输工具，则运费的计算往往仅与运送物资的多少及里程有关。因此，在求最佳的运输方案时，用吨公里作为度量的标准比用运费作为度量标准更加方便、实用。在求解最佳运输方案时，用吨公里作为度量单位，还可以在已经画出的交通图上进行，操作起来较为简单、方便、直观、快捷。在铁路、公路等交通部门经常使用这种方法决策最优运输问题，这种方法被称为图上作业法。二、编制交通图和流向图•交通图•反映发点（产地）与收地（销地）及交通线路及其距离组成的图形。•发点用“○”表示，发出货物的数量记在“○”之内（单位：吨）•收地（销地）用“□”表示，收取货物的数量记在“□”之内（单位：吨）•两点之间的线路长度记在交通线路的旁边。1、交通图1、交通图2、流向图流向图:在交通图上表示物资流向的图被称为流向图。在图中每个发点吨数全部运完，每个收点所需吨数均已满足。2、流向图发点A到收点B的运输量，用括号括起。2、流向图关于流向图的一些规定箭头必须表示物资运输的方向流量写在箭头的旁边，加小括号。流向不能直接跨越路线上的收点、发点、交叉点任何一段弧上最多只能显示一条流向！即同一段弧上的多条流向必须合并。除端点外，任何点都可以流进和流出2、流向图2、流向图含有圈的流向图的补充规定顺时针方向的流向必须画在圈的内侧，称为内圈流向逆时针方向的流向必须画在圈的外侧，称为外圈流向内圈流向、外圈流向举例44（4）26图：4-644（4）26图：4-7二、对流向图的检验在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨—公里数是最小的调运方案。这就要注意在调运中不要发生对物流运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。（1）不合理的现象1：对流（1）对流：所谓对流就是在一段线路上有同一种物资出现相对运输现象（往返运输）（同一段线路上，两各方向都有流向），如图4-4。甲乙两地是一种对流现象。如果把流向图改成图4-5，就可以避免对流现象，从而可以节约运输量20×10=200(吨公里)。201010(10)(20)乙甲图4-4图4-5201010(10)(10)乙甲(20)（2）不合理的现象2：迂回（2）迂回：当收点与发点之间的运输线路有两条或两条以上时（即交通图成圈），如果运送的货物不是走最短线路，则称这种运输为迂回运输。注：当交通图成圈时，如果流向图中内圈流向的总长（简称内圈长）或外圈流向的总长（简称外圈长）超过整个圈长的一半就称为迂回运输。例如某物资流向图如图4-6、4-7所示。迂回运输的判断44（4）26图：4-644（4）26图：4-7显然：图4-6为迂回运输（3）、正规（最优）流向图正规（最优）流向图：一个最优的调运方案，它的流向图必是无对流、无迂回的流向图，称这种流向图为正规流向图。物资调运的图上作业法就是寻找一个无对流、无迂回的正规流向图。步骤如下：•作出一个无对流的初始可行方案；•检验有无迂回•若无，结束；•􀁺否则，调整，直到最优。三、图上作业法的求解过程1、无圈的交通图2、有圈的交通图方法：供需归邻站1、交通图无圈情形【例1】求最优调运方案324786451A1A2B1B3B2A5A3A4B4案例分析口诀：抓各端，各端供需归邻站即：先满足端点的要求，逐步向中间逼近，直至收点与发点得到全部满足为止。324786451A1A2B1B3B2A5A3A4B4（3）（4）（2）（3）（4）（7）（3）（10）图4-8练一练答案2、交通图有圈情形【例2】求最优调运方案454786454A1A2B1B3B2B5A38B42273463图4-9解题步骤：第一步：变有圈为无圈。方法：“丢边破圈”。即丢掉一条边，破去一个圈。注意：丢边时，往往是丢掉圈中长度最大的边。如图所示第一步：“丢边破圈”454786454A1A2B1B3B2B5A38B42273463第二步：在无圈的交通图上作流向图。原则：先外后内，先端点后中间点，要求每个边都有流向。当某条边无流向时，必须填上运输量为零的虚流向。第二步：作流向图454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（3）（2）（8）图4-10第三步：补上丢掉的边，检查有无迂回。圈B5B4B3A2的圈长=4+4+5+8=21,内圈长=4+4+5=1321/2，有迂回，所以流向图不是最优流向图。需要调整。第四步：对方案进行调整。方法：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边B5B4），并补上原来丢掉的边（边B5A2），得到新的交通图。在此交通图上做新的流向图。第四步：调整方案454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（1）（2）（6）图4-11第五步：对新方案进行检验。圈B5B4B3A2的圈长=4+4+5+8=21,内圈长=4+5=921/2，外圈长=821/2.内圈、外圈的长度均不超过圈长的一半，所以该圈不存在迂回。圈A3B1B2A1B3B4的圈长=7+2+3+6+4+3=25,内圈长=2+3+6+3=1425/2，有迂回，所以流向图不是最优流向图。需要调整。第六步：对方案进行调整。方法：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边A1B3），并补上原来丢掉的边（边B1A3），得到新的交通图。在此交通图上做新的流向图。第六步：调整方案454786454A1A2B1B3B2B5A38B42273463（3）（7）（1）（4）（2）（2）（6）图4-12可验证：此方案中无迂回现象。即为最优方案。发收B1B2B3B4B5发货量A1347A24228A3145收货量44462练一练答案图上作业法有某物资7t，由发出点A1,A2,A3发出，发量分别为3,3,1(t)，运往收点B1,B2,B3,B4，收量分别为2,3,1,1(t)，收发量平衡，交通图如下图，问应如何调动，才使t·km最小？【例1】38（2）图上作业法【例3】有某物资7t，由A1，A2，A3发出，发量分别为3，3，1（t），运往收点B1，B2，B3，B4，收量分别为2，3，1，1（t），收发量平衡，交通图如图4—1所示，问应如何调运，才使t·km最小。。4312133173543243931、破圈求初始解1213317354324312114②检查有无迂回，方法水对流想图中的各圈进行检查，侃侃有无迂回。如果没有迂回，即该圈总长的一半均大于内流长和外流长，这个初始方案就是最优方案，如果其中某一圈有迂回，这个方案就不是最优方案，需要改进。在图中，圈A1B1B2A3B4的总长为23km，外流长为5+4+3=12km，大于圈长的一半，因而需要调整。在看圈B2A2B3A3其总长为13km，圈中内流长为3km，外流长为2km，都小于圈长的一半，因此此圈不必调整。40对圈A1B1B2A3B4的调整方法是：在外圈的个流量中，减去外圈的最小流量1t；然后在内圈的个流量中加上1t，在此圈中，因无内流量，所以无处可加；另外，在无流量的线段上，新添上内圈流量1t，这样得出新的流量图。方案调整121331735432431211431213317354324212114341121331735432421211432121331735434231431在圈B2A2B3A3中外圈长为4+3=7大于圈长的一半，调整为内圈加“1”外圈减“1”此时两个圈都没有迂回是最优方案总的TKM为：7*1+2*5+1*4+3*2=27方案调整4287545469834665757代表仓库代表需求43最短路问题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]=3T(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。F5A0ECDB37454343443、以点B（刚得到标号的点）作为比较基础，重复上述过程，即比较T(j)与[P(2)+l2j]，j=3,4,5,6取较小的数作为Vj的新的T标号。T(D)=3+5=8T(C)=4T(E)=3+7=10比较T(D)、T(E)、T(C)，其中T(C)为最小，将点C的T标号改为P标号：P(C)=4。A03FECDB37454344545同理T(D)=4+4=8比较T（D），T（E）其中T（D）最小，令P（D）=8A03FECDB374543448546T（E）=3+8=11T（F）=8+4=12T（E）=3+7=10其中T（E）=10最小令P（E）=10A03FECDB37454344810547T（F）=10+5=15T（F）=12其中T（F）=12最小，则令P（F）=12最短路为12A-B-D-FA-C-D-FA03FECDB374543448101253131213A1B2A2B3A3B4B174432435在上图的基础上做一个无对流的流向图。注意：与表上作业法类似，表上作业法要求有调运量的格子数应该是收点数+发点数-1。图上作业法要求在流向图上的箭头数（有调运量的边数）也应为收点数+发点数-1。这一要求也可以等价地表述为：在去线破圈后得到的不成圈的交通图上，要求每边都应该有流向。3131213A1B2A2B3A3B4B1443235(3)(1)(2)(1)(1)因此，某一边无流向时，必须在这一边上添上调运量为0的虚流向，和其它流向同样对待。按照这一要求，应在A3边上添上虚流向。于是，再补上去掉的边，得下图：3131213A1B2A2B3A3B4B1443235(3)(1)(2)(1)(1)(0)(2)检查有无迂回方法：对流向图中只有一边没有流向的各圈进行检查。如果没有迂回，即已到最优调运方案。如果有迂回，则需要进行调整。首先分别计算线路的全圈长、内圈长和外圈长（圈长即指里程数），如果内圈长和外圈长都分别小于全圈长的一半，则该方案即为最优方案；否则，即为非最优方案，需要对其进行调整A1B1B2A3B4外圈长5+4+3＝12，大于全圈长23的1/2(3)调整方案:方法：在有迂回的外圈各流量中减去一个最小调运量，在内圈（含无调运量的边）各流量上加上这一最小调运量。圈A1B1B2A3B4中的最小流量为，在外圈上减去该最小调运量后，有两条边同时为，需在任意一边上记上0运量，于是，得到调整后的调运方案。如图3131213A1B2A2B3A3B4B1443235(2)(0)(2)(1)(1)7（1）经检查圈B2A2B3A3不构成迂回运输，所以所得到的方案已是最优方案。最优调运方案的总运输量为Z=2×5+2×3+1×2+1×4+1×7=29t·km