图上作业法课件.ppt

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

距离组成的图形•发点用发点用““○””表示，发出货物的数量记在表示，发出货物的数量记在““○””之之内（单位：吨）内（单位：吨）•收地（销地）用收地（销地）用““□””表示，收取货物的数量记在表示，收取货物的数量记在““□””之内（单位：吨）之内（单位：吨）•两点之两点之间的的线路路长度度记在交通在交通线路的旁路的旁边1 1、交通图、交通图1 1、交通图、交通图2 2、流向图、流向图v流向图流向图: :v在交通图上表示物资流向的图被称为流向图在在交通图上表示物资流向的图被称为流向图在图中每个发点吨数全部运完，每个收点所需吨数图中每个发点吨数全部运完，每个收点所需吨数均已满足均已满足流向用箭头画在两点连线的右方流向用箭头画在两点连线的右方即：站在发点，看向收点，右手所在的一侧或（即：站在发点，看向收点，右手所在的一侧或从发点到收点，顺时针方向的一侧）从发点到收点，顺时针方向的一侧）2 2、流向图、流向图发点发点A到收点到收点B的的运输量，用括号运输量，用括号括起2 2、流向图、流向图v关于流向图的一些规定关于流向图的一些规定v箭头必须表示物资运输的方向箭头必须表示物资运输的方向v流量写在箭头的旁边，加小括号。

流量写在箭头的旁边，加小括号v流向不能直接跨越路线上的收点、发点、交叉点流向不能直接跨越路线上的收点、发点、交叉点v任何一段弧上最多只能显示一条流向！即同一段任何一段弧上最多只能显示一条流向！即同一段弧上的多条流向必须合并弧上的多条流向必须合并v除端点外，任何点都可以流进和流出除端点外，任何点都可以流进和流出2 2、流向图、流向图2 2、流向图、流向图v含有圈的流向图的补充规定含有圈的流向图的补充规定v顺时针方向的流向必须画在圈的内侧，称为内圈顺时针方向的流向必须画在圈的内侧，称为内圈流向流向v逆时针方向的流向必须画在圈的外侧，称为外圈逆时针方向的流向必须画在圈的外侧，称为外圈流向流向内圈流向、外圈流向举例内圈流向、外圈流向举例44（（4））26图：内圈流向图：内圈流向44（（4））26图：外圈流向图：外圈流向二、对流向图的检验二、对流向图的检验v在物资运输中，把某种物资从各发点调到各收点在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨的调运方案是很多的，但我们的目的是找出吨——公里数是最小的调运方案这就要注意在调运中公里数是最小的调运方案这就要注意在调运中不要发生对物流运输和迂回运输，因此，我们在不要发生对物流运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。

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

例例如某物资流向图如图所示如某物资流向图如图所示迂回运输的判断迂回运输的判断44（（4））26左图左图44（（4））26右图右图显然：左图为迂回运输显然：左图为迂回运输（（3 3）、正规（最优）流向图）、正规（最优）流向图v正规（最优）流向图正规（最优）流向图：一个最优的调运方：一个最优的调运方案，它的流向图必是无对流、无迂回的流案，它的流向图必是无对流、无迂回的流向图，称这种流向图为正规流向图向图，称这种流向图为正规流向图v物资调运的图上作业法就是寻找一个无对物资调运的图上作业法就是寻找一个无对流、无迂回的正规流向图流、无迂回的正规流向图v步骤如下：步骤如下：•作出一个无对流的初始可行方案；作出一个无对流的初始可行方案；•检验有无迂回检验有无迂回• 若无，结束；若无，结束；•က က否则，调整，直到最优否则，调整，直到最优三、图上作业法的求解过程三、图上作业法的求解过程v1 1、无圈（线状）的交通图、无圈（线状）的交通图v2 2、有圈的交通图、有圈的交通图v方法：方法：供需归邻站供需归邻站1 1、交通图无圈（现状）情形、交通图无圈（现状）情形v【【例例】】求最优调运方案求最优调运方案324786451A1A2B1B3B2A5A3A4B4案例分析案例分析v口诀口诀：：抓各端，各端供需归邻站抓各端，各端供需归邻站v即即：先满足端点的要求，逐步向中间逼近，直至：先满足端点的要求，逐步向中间逼近，直至收点与发点得到全部满足为止。

收点与发点得到全部满足为止324786451A1A2B1B3B2A5A3A4B4（（3））（（4））（（2））（（3））（（4））（（7））（（3））（（10））练一练练一练答案答案2 2、交通图有圈情形、交通图有圈情形v【【例例】】求最优调运方案求最优调运方案454786454A1A2B1B3B2B5A38B42273463v它的原则可归纳为：v流向划右方，对流不应当；里圈、外圈分别算，要求不过半圈长；如若超过半圈长，应甩运量最小段；反复求算最优方案解题步骤：解题步骤：v第一步：变有圈为无圈第一步：变有圈为无圈v方法：方法：““丢边破圈丢边破圈””即丢掉一条边，破即丢掉一条边，破去一个圈去一个圈v注意注意：：丢边时，往往是丢掉圈中长度最大丢边时，往往是丢掉圈中长度最大的边的边如图所示如图所示第一步：第一步： “ “丢边破圈丢边破圈””454786454A1A2B1B3B2B5A38B42273463v第二步：在无圈的交通图上作流向图第二步：在无圈的交通图上作流向图v原则：原则：先外后内，先端点后中间点，要求先外后内，先端点后中间点，要求每个边都有流向当某条边无流向时，必每个边都有流向。

当某条边无流向时，必须填上运输量为零的虚流向须填上运输量为零的虚流向第二步：作流向图第二步：作流向图454786454A1A2B1B3B2B5A38B42273463（（4））（（8）） （（1））（（5））（（3））（（2））（（8））v第三步：检查有无迂回第三步：检查有无迂回v圈圈B B5 5B B4 4B B3 3A A2 2的圈长的圈长=4+4+5+8=21,=4+4+5+8=21,内圈长内圈长= = 4+4+5=13>4+4+5=13>（（21/221/2），有迂回，所以流向图不是），有迂回，所以流向图不是最优流向图需要调整最优流向图需要调整v第四步：对方案进行调整第四步：对方案进行调整v方法方法：找出：找出有迂回圈的流量最小的边有迂回圈的流量最小的边（去掉的边（去掉的边除外），除外），改此边为丢掉的边改此边为丢掉的边（边（边B B5 5B B4 4），并），并补上补上原来丢掉的边原来丢掉的边（边（边B B5 5A A2 2），），得到新的交通图得到新的交通图在此交通图上做新的流向图此交通图上做新的流向图第四步：调整方案第四步：调整方案454786454A1A2B1B3B2B5A38B42273463（（4））（（8）） （（1））（（5））（（1））（（2））（（6））v第五步：对新方案进行检验。

第五步：对新方案进行检验v圈圈B B5 5B B4 4B B3 3A A2 2的圈长的圈长=4+4+5+8=21,=4+4+5+8=21,内圈长内圈长= = 4+5=9<21/24+5=9<21/2，外圈长，外圈长= 8<21/2.= 8<21/2.内圈、外圈的长内圈、外圈的长度均不超过圈长的一半，所以该圈不存在迂回度均不超过圈长的一半，所以该圈不存在迂回v圈圈A A3 3B B1 1B B2 2A A1 1B B3 3B B4 4的圈长的圈长=7+2+3+6+4+3=25,=7+2+3+6+4+3=25,内圈长内圈长= = 2+3+6+3=14>25/22+3+6+3=14>25/2，有迂回，所以流向图不是最，有迂回，所以流向图不是最优流向图需要调整优流向图需要调整v第六步：对方案进行调整第六步：对方案进行调整v方法方法：找出有迂回圈的流量最小的边（去掉的边：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边除外），改此边为丢掉的边（边A A1 1B B3 3），并补上），并补上原来丢掉的边（边原来丢掉的边（边B B1 1A A3 3），得到新的交通图在），得到新的交通图。

在此交通图上做新的流向图直到所有圈的内圈长此交通图上做新的流向图直到所有圈的内圈长小于二分之一圈长，外圈长小于二分之一圈长，小于二分之一圈长，外圈长小于二分之一圈长，得到最优方案得到最优方案第六步：调整方案第六步：调整方案454786454A1A2B1B3B2B5A38B42273463（（3））（（7））（（1））（（4））（（2））（（2））（（6））v可验证：此方案中无迂回现象即为最优方案可验证：此方案中无迂回现象即为最优方案发发收收B1B1B2B2B3B3B4B4B5B5发货量发货量A1A13 34 47 7A2A24 42 22 28 8A3A31 14 45 5收货量收货量4 44 44 46 62 2练一练练一练答案答案。