图上作业法

图上作业法本节课的主要内容编制交通图和流向图对流向图的检验图上作业法的求解过程（重点）一、图上作业法在运输中，若使用同一种运输工具，则运费的计算往往仅与运送物资的多少及里程有关。因此，在求最佳的运输方案时，用吨公里作为度量的标准比用运费作为度量标准更加方便、实用。在求解最佳运输方案时，用吨公里作为度量单位，还可以在已经画出的交通图上进行，操作起来较为简单、方便、直观、快捷。在铁路、公路等交通部门经常使用这种方法决策最优运输问题，这种方法被称为图上作业法。二、编制交通图和流向图•交通图•反映发点（产地）与收地（销地）及交通线路及其距离组成的图形。•发点用“○”表示，发出货物的数量记在“○”之内（单位：吨）•收地（销地）用“□”表示，收取货物的数量记在“□”之内（单位：吨）•两点之间的线路长度记在交通线路的旁边。1、交通图1、交通图2、流向图流向图:在交通图上表示物资流向的图被称为流向图。在图中每个发点吨数全部运完，每个收点所需吨数均已满足。流向用箭头画在两点连线的右方。（即：站在发点，看向收点，右手所在的一侧或从发点到收点，顺时针方向的一侧）2、流向图发点A到收点B的运输量，用括号括起。2、流向图关于流向图的一些规定箭头必须表示物资运输的方向流量写在箭头的旁边，加小括号。流向不能直接跨越路线上的收点、发点、交叉点任何一段弧上最多只能显示一条流向！即同一段弧上的多条流向必须合并。除端点外，任何点都可以流进和流出2、流向图2、流向图含有圈的流向图的补充规定顺时针方向的流向必须画在圈的内侧，称为内圈流向逆时针方向的流向必须画在圈的外侧，称为外圈流向内圈流向、外圈流向举例44（4）26图：内圈流向44（4）26图：外圈流向二、对流向图的检验在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨—公里数是最小的调运方案。这就要注意在调运中不要发生对物流运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。（1）不合理的现象1：对流（1）对流：所谓对流就是在一段线路上有同一种物资出现相对运输现象（往返运输）（同一段线路上，两各方向都有流向），如左图。甲乙两地是一种对流现象。如果把流向图改成右图，就可以避免对流现象，从而可以节约运输量20×10=200(吨公里)。201010(10)(20)乙甲左图右图201010(10)(10)乙甲(20)（2）不合理的现象2：迂回（2）迂回：当收点与发点之间的运输线路有两条或两条以上时（即交通图成圈），如果运送的货物不是走最短线路，则称这种运输为迂回运输。注：当交通图成圈时，如果流向图中内圈流向的总长（简称内圈长）或外圈流向的总长（简称外圈长）超过整个圈长的一半就称为迂回运输。例如某物资流向图如图所示。迂回运输的判断44（4）26左图44（4）26右图显然：左图为迂回运输（3）、正规（最优）流向图正规（最优）流向图：一个最优的调运方案，它的流向图必是无对流、无迂回的流向图，称这种流向图为正规流向图。物资调运的图上作业法就是寻找一个无对流、无迂回的正规流向图。步骤如下：•作出一个无对流的初始可行方案；•检验有无迂回•若无，结束；•􀁺否则，调整，直到最优。三、图上作业法的求解过程1、无圈（线状）的交通图2、有圈的交通图方法：供需归邻站1、交通图无圈（现状）情形【例】求最优调运方案324786451A1A2B1B3B2A5A3A4B4案例分析口诀：抓各端，各端供需归邻站即：先满足端点的要求，逐步向中间逼近，直至收点与发点得到全部满足为止。324786451A1A2B1B3B2A5A3A4B4（3）（4）（2）（3）（4）（7）（3）（10）练一练答案2、交通图有圈情形【例】求最优调运方案454786454A1A2B1B3B2B5A38B42273463它的原则可归纳为：流向划右方，对流不应当；里圈、外圈分别算，要求不过半圈长；如若超过半圈长，应甩运量最小段；反复求算最优方案。解题步骤：第一步：变有圈为无圈。方法：“丢边破圈”。即丢掉一条边，破去一个圈。注意：丢边时，往往是丢掉圈中长度最大的边。如图所示第一步：“丢边破圈”454786454A1A2B1B3B2B5A38B42273463第二步：在无圈的交通图上作流向图。原则：先外后内，先端点后中间点，要求每个边都有流向。当某条边无流向时，必须填上运输量为零的虚流向。第二步：作流向图454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（3）（2）（8）第三步：检查有无迂回。圈B5B4B3A2的圈长=4+4+5+8=21,内圈长=4+4+5=13（21/2），有迂回，所以流向图不是最优流向图。需要调整。第四步：对方案进行调整。方法：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边B5B4），并补上原来丢掉的边（边B5A2），得到新的交通图。在此交通图上做新的流向图。第四步：调整方案454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（1）（2）（6）第五步：对新方案进行检验。圈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）可验证：此方案中无迂回现象。即为最优方案。发收B1B2B3B4B5发货量A1347A24228A3145收货量44462练一练答案