图上作业法专题.ppt

《图上作业法专题.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、图上作业法专题一、图上作业法在运输中，若使用同一种运输工具，则运费的计算往往仅与运送物资的多少及里程有关。因此，在求最佳的运输方案时，用吨公里作为度量的标准比用运费作为度量标准更加方便、实用。在求解最佳运输方案时，用吨公里作为度量单位，还可以在已经画出的交通图上进行，操作起来较为简单、方便、直观、快捷。在铁路、公路等交通部门经常使用这种方法决策最优运输问题，这种方法被称为图上作业法。二、编制交通图和流向图交通图反映发点（产地）与收地（销地）及交通线路及其距离组成的图形。发点用“○”表示，发出货物的数量记在“○

2、”之内（单位：吨）收地（销地）用“□”表示，收取货物的数量记在“□”之内（单位：吨）两点之间的线路长度记在交通线路的旁边。1、交通图1、交通图2、流向图流向图:在交通图上表示物资流向的图被称为流向图。在图中每个发点吨数全部运完，每个收点所需吨数均已满足。2、流向图发点A到收点B的运输量，用括号括起。2、流向图关于流向图的一些规定箭头必须表示物资运输的方向流量写在箭头的旁边，加小括号。流向不能直接跨越路线上的收点、发点、交叉点任何一段弧上最多只能显示一条流向！即同一段弧上的多条流向必须合并。除端点外，任何点都可

3、以流进和流出2、流向图2、流向图含有圈的流向图的补充规定顺时针方向的流向必须画在圈的内侧，称为内圈流向逆时针方向的流向必须画在圈的外侧，称为外圈流向内圈流向、外圈流向举例44（4）26图：4-644（4）26图：4-7二、对流向图的检验在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨—公里数是最小的调运方案。这就要注意在调运中不要发生对物流运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。（1）不合理的现象1：对流（1）对流：所谓对流就是在一段线路上有同一种物资出现

4、相对运输现象（往返运输）（同一段线路上，两各方向都有流向），如图4-4。甲乙两地是一种对流现象。如果把流向图改成图4-5，就可以避免对流现象，从而可以节约运输量20×10=200(吨公里)。201010(10)(20)乙甲图4-4图4-5201010(10)(10)乙甲(20)（2）不合理的现象2：迂回（2）迂回：当收点与发点之间的运输线路有两条或两条以上时（即交通图成圈），如果运送的货物不是走最短线路，则称这种运输为迂回运输。注：当交通图成圈时，如果流向图中内圈流向的总长（简称内圈长）或外圈流向的总长（简称

5、外圈长）超过整个圈长的一半就称为迂回运输。例如某物资流向图如图4-6、4-7所示。迂回运输的判断44（4）26图：4-644（4）26图：4-7显然：图4-6为迂回运输（3）、正规（最优）流向图正规（最优）流向图：一个最优的调运方案，它的流向图必是无对流、无迂回的流向图，称这种流向图为正规流向图。物资调运的图上作业法就是寻找一个无对流、无迂回的正规流向图。步骤如下：作出一个无对流的初始可行方案；检验有无迂回若无，结束；?否则，调整，直到最优。三、图上作业法的求解过程1、无圈的交通图2、有圈的交通图方法：供需归

6、邻站1、交通图无圈情形【例1】求最优调运方案324786451A1A2B1B3B2A5A3A4B4案例分析口诀：抓各端，各端供需归邻站即：先满足端点的要求，逐步向中间逼近，直至收点与发点得到全部满足为止。324786451A1A2B1B3B2A5A3A4B4（3）（4）（2）（3）（4）（7）（3）（10）图4-8练一练答案2、交通图有圈情形【例2】求最优调运方案454786454A1A2B1B3B2B5A38B42273463图4-9解题步骤：第一步：变有圈为无圈。方法：“丢边破圈”。即丢掉一条边，破去一个

7、圈。注意：丢边时，往往是丢掉圈中长度最大的边。如图所示第一步：“丢边破圈”454786454A1A2B1B3B2B5A38B42273463第二步：在无圈的交通图上作流向图。原则：先外后内，先端点后中间点，要求每个边都有流向。当某条边无流向时，必须填上运输量为零的虚流向。第二步：作流向图454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（3）（2）（8）图4-10第三步：补上丢掉的边，检查有无迂回。圈B5B4B3A2的圈长=4+4+5+8=21,内圈长=4+4+5=13

8、>21/2，有迂回，所以流向图不是最优流向图。需要调整。第四步：对方案进行调整。方法：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边B5B4），并补上原来丢掉的边（边B5A2），得到新的交通图。在此交通图上做新的流向图。第四步：调整方案454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（1）（2）（6）图4-11第五步：对新方案进行检验。圈B