4.3_图上作业法合编.ppt

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