图上作业法课件.ppt

1、图上作业法-本节课的主要内容本节课的主要内容v编制交通图和流向图编制交通图和流向图v对流向图的检验对流向图的检验v图上作业法的求解过程（重点）图上作业法的求解过程（重点）一、图上作业法图上作业法v在运输中，若使用同一种运输工具，则运费的在运输中，若使用同一种运输工具，则运费的计算往往仅与运送计算往往仅与运送物资的多少及里程物资的多少及里程有关。因有关。因此，在求最佳的运输方案时，用此，在求最佳的运输方案时，用吨公里吨公里作为度作为度量的标准比用运费作为度量标准更加方便、实量的标准比用运费作为度量标准更加方便、实用。用。v在求解最佳运输方案时，用吨公里作为度量单在求解最佳运输方案时，用吨公里作为

2、度量单位，还可以在已经画出的交通图上进行，操作位，还可以在已经画出的交通图上进行，操作起来较为简单、方便、直观、快捷。起来较为简单、方便、直观、快捷。v在铁路、公路等交通部门经常使用这种方法决在铁路、公路等交通部门经常使用这种方法决策最优运输问题，这种方法被称为策最优运输问题，这种方法被称为图上作业法图上作业法。二、编制交通图和流向图二、编制交通图和流向图 交通图交通图 反映发点（产地）与收地（销地）及交通线路及其反映发点（产地）与收地（销地）及交通线路及其距离组成的图形。距离组成的图形。发点用发点用“”表示表示，发出货物的数量记在，发出货物的数量记在“”之之内（单位：吨）内（单位：吨）收地（

3、销地）用收地（销地）用“”表示表示，收取货物的数量记在，收取货物的数量记在“”之内（单位：吨）之内（单位：吨）两点之间的线路长度记在交通线路的旁边两点之间的线路长度记在交通线路的旁边。1 1、交通图、交通图1 1、交通图、交通图2 2、流向图、流向图v流向图流向图:v在交通图上表示物资流向的图被称为流向图在交通图上表示物资流向的图被称为流向图。在。在图中每个发点吨数全部运完，每个收点所需吨数图中每个发点吨数全部运完，每个收点所需吨数均已满足。均已满足。2 2、流向图、流向图发点发点A到收点到收点B的的运输量，用括号运输量，用括号括起。括起。2 2、流向图、流向图v关于流向图的一些规定关于流向图

4、的一些规定v箭头必须表示物资运输的方向箭头必须表示物资运输的方向v流量写在箭头的旁边，加小括号。流量写在箭头的旁边，加小括号。v流向不能直接跨越路线上的收点、发点、交叉点流向不能直接跨越路线上的收点、发点、交叉点v任何一段弧上最多只能显示一条流向！即同一段任何一段弧上最多只能显示一条流向！即同一段弧上的多条流向必须合并。弧上的多条流向必须合并。v除端点外，任何点都可以流进和流出除端点外，任何点都可以流进和流出2 2、流向图、流向图2 2、流向图、流向图v含有圈的流向图的补充规定含有圈的流向图的补充规定v顺时针方向的流向必须画在圈的内侧，称为顺时针方向的流向必须画在圈的内侧，称为内圈内圈流向流向

5、v逆时针方向的流向必须画在圈的外侧，称为逆时针方向的流向必须画在圈的外侧，称为外圈外圈流向流向内圈流向、外圈流向举例内圈流向、外圈流向举例44（4）26图：图：4-644（4）26图：图：4-7二、对流向图的检验二、对流向图的检验v在物资运输中，把某种物资从各发点调到各收点在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出的调运方案是很多的，但我们的目的是找出吨吨公里数是最小的调运方案公里数是最小的调运方案。这就要注意在调运中。这就要注意在调运中不要发生不要发生对物流运输和迂回运输对物流运输和迂回运输，因此，我们在，因此，我们在制定流向图时，就要避免它的出现。制定

6、流向图时，就要避免它的出现。（1 1）不合理的现象）不合理的现象1 1：对流：对流v（1 1）对流：所谓对流就是在一段线路上有同一）对流：所谓对流就是在一段线路上有同一种物资出现相对运输现象（往返运输）（同一段种物资出现相对运输现象（往返运输）（同一段线路上，两各方向都有流向），如图线路上，两各方向都有流向），如图4-44-4。v甲乙两地是一种对流现象。如果把流向图改成图甲乙两地是一种对流现象。如果把流向图改成图4-54-5，就可以避免对流现象，从而可以节约运输，就可以避免对流现象，从而可以节约运输量量202010=200(10=200(吨公里吨公里)。201010(10)(20)乙甲图 4-

7、4图 4-5201010(10)(10)乙甲(20)（2 2）不合理的现象）不合理的现象2 2：迂回：迂回v（2 2）迂回迂回：当收点与发点之间的运输线路有两当收点与发点之间的运输线路有两条或两条以上时（即交通图成圈），如果运送的条或两条以上时（即交通图成圈），如果运送的货物货物不是走最短线路不是走最短线路，则称这种运输为迂回运输。，则称这种运输为迂回运输。v注：注：当交通图成圈时，如果流向图中内圈流向的当交通图成圈时，如果流向图中内圈流向的总长（简称总长（简称内圈长内圈长）或外圈流向的总长（简称）或外圈流向的总长（简称外外圈长圈长）超过整个圈长的一半超过整个圈长的一半就称为就称为迂回运输迂回

8、运输。例。例如某物资流向图如图如某物资流向图如图4-64-6、4-74-7所示。所示。迂回运输的判断迂回运输的判断44（4）26图：图：4-644（4）26图：图：4-7显然：图显然：图4-6为迂回运输为迂回运输（3 3）、正规（最优）流向图）、正规（最优）流向图v正规（最优）流向图正规（最优）流向图：一个最优的调运方：一个最优的调运方案，它的流向图必是无对流、无迂回的流案，它的流向图必是无对流、无迂回的流向图，称这种流向图为正规流向图。向图，称这种流向图为正规流向图。v物资调运的图上作业法就是寻找一个无对物资调运的图上作业法就是寻找一个无对流、无迂回的正规流向图。流、无迂回的正规流向图。v步

9、骤如下：步骤如下：作出一个无对流的初始可行方案；作出一个无对流的初始可行方案；检验有无迂回检验有无迂回 若无，结束；若无，结束；否则，调整，直到最优。否则，调整，直到最优。三、图上作业法的求解过程三、图上作业法的求解过程v1 1、无圈的交通图、无圈的交通图v2 2、有圈的交通图、有圈的交通图v方法：方法：供需归邻站供需归邻站1 1、交通图无圈情形、交通图无圈情形v【例例4-44-4】求最优调运方案求最优调运方案324786451A1A2B1B3B2A5A3A4B4案例分析案例分析v口诀口诀：抓各端，各端供需归邻站抓各端，各端供需归邻站v即即：先满足端点的要求，逐步向中间逼近，直至：先满足端点的

10、要求，逐步向中间逼近，直至收点与发点得到全部满足为止。收点与发点得到全部满足为止。324786451A1A2B1B3B2A5A3A4B4（3）（4）（2）（3）（4）（7）（3）（10）图图 4-8练一练练一练答案答案2 2、交通图有圈情形、交通图有圈情形v【例例4-54-5】求最优调运方案求最优调运方案454786454A1A2B1B3B2B5A38B42273463图图 4-9解题步骤：解题步骤：v第一步：变有圈为无圈。第一步：变有圈为无圈。v方法：方法：“丢边破圈丢边破圈”。即丢掉一条边，破即丢掉一条边，破去一个圈。去一个圈。v注意注意：丢边时，往往是丢掉圈中长度最大：丢边时，往往是丢掉

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

12、。第三步：补上丢掉的边，检查有无迂回。v圈圈B B5 5B B4 4B B3 3A A2 2的圈长的圈长=4+4+5+8=21,=4+4+5+8=21,内圈长内圈长=4+4+5=1321/24+4+5=1321/2，有迂回，所以流向图不是最优，有迂回，所以流向图不是最优流向图。需要调整。流向图。需要调整。v第四步：对方案进行调整。第四步：对方案进行调整。v方法方法：找出有迂回圈的流量最小的边（去掉的边：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边除外），改此边为丢掉的边（边B B5 5B B4 4），并补上），并补上原来丢掉的边（边原来丢掉的边（边B B5 5A A2 2）

13、，得到新的交通图。在），得到新的交通图。在此交通图上做新的流向图。此交通图上做新的流向图。第四步：调整方案第四步：调整方案454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（1）（2）（6）图图 4-11v第五步：对新方案进行检验。第五步：对新方案进行检验。v圈圈B B5 5B B4 4B B3 3A A2 2的圈长的圈长=4+4+5+8=21,=4+4+5+8=21,内圈长内圈长=4+5=921/24+5=921/2，外圈长，外圈长=821/2.=825/22+3+6+3=1425/2，有迂回，所以流向图不是最，有迂回，所以流向图不是最优流向图。需要调

14、整。优流向图。需要调整。v第六步：对方案进行调整。第六步：对方案进行调整。v方法方法：找出有迂回圈的流量最小的边（去掉的边：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边除外），改此边为丢掉的边（边A A1 1B B3 3），并补上），并补上原来丢掉的边（边原来丢掉的边（边B B1 1A A3 3），得到新的交通图。在），得到新的交通图。在此交通图上做新的流向图。此交通图上做新的流向图。第六步：调整方案第六步：调整方案454786454A1A2B1B3B2B5A38B42273463（3）（7）（1）（4）（2）（2）（6）图图 4-12v 可验证：此方案中无迂回现象。即为最优方案。可验证：此方案中无迂回现象。即为最优方案。发发收收B1B1B2B2B3B3B4B4B5B5发货量发货量A1A13 34 47 7A2A24 42 22 28 8A3A31 14 45 5收货量收货量4 44 44 46 62 2练一练练一练答案答案-