图上作业法完整版

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

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

3、用收地（销地）用“”表示，收取货物的数量记在表示，收取货物的数量记在“”之内（单位：吨）之内（单位：吨） 两点之间的线路长度记在交通线路的旁边。两点之间的线路长度记在交通线路的旁边。1 1、交通图、交通图1 1、交通图、交通图2 2、流向图、流向图v流向图流向图: :v在交通图上表示物资流向的图被称为流向图。在在交通图上表示物资流向的图被称为流向图。在图中每个发点吨数全部运完，每个收点所需吨数图中每个发点吨数全部运完，每个收点所需吨数均已满足。均已满足。流向用箭头画在两点连线的右方。流向用箭头画在两点连线的右方。（即：站在发点，看向收点，右手所在的一侧或（即：站在发点，看向收点，右手所在的一侧

4、或从发点到收点，顺时针方向的一侧）从发点到收点，顺时针方向的一侧）2 2、流向图、流向图发点发点A到收点到收点B的的运输量，用括号运输量，用括号括起。括起。2 2、流向图、流向图v关于流向图的一些规定关于流向图的一些规定v箭头必须表示物资运输的方向箭头必须表示物资运输的方向v流量写在箭头的旁边，加小括号。流量写在箭头的旁边，加小括号。v流向不能直接跨越路线上的收点、发点、交叉点流向不能直接跨越路线上的收点、发点、交叉点v任何一段弧上最多只能显示一条流向！即同一段任何一段弧上最多只能显示一条流向！即同一段弧上的多条流向必须合并。弧上的多条流向必须合并。v除端点外，任何点都可以流进和流出除端点外，

5、任何点都可以流进和流出v含有圈的流向图的补充规定含有圈的流向图的补充规定v顺时针方向的流向必须画在圈的内侧，称为内圈顺时针方向的流向必须画在圈的内侧，称为内圈流向流向v逆时针方向的流向必须画在圈的外侧，称为外圈逆时针方向的流向必须画在圈的外侧，称为外圈流向流向内圈流向、外圈流向举例内圈流向、外圈流向举例44（4）26图：内圈流向图：内圈流向44（4）26图：外圈流向图：外圈流向二、对流向图的检验二、对流向图的检验v在物资运输中，把某种物资从各发点调到各收点在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨的调运方案是很多的，但我们的目的是找出吨公里数是最小的调运

6、方案。这就要注意在调运中公里数是最小的调运方案。这就要注意在调运中不要发生对物流运输和迂回运输，因此，我们在不要发生对物流运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。制定流向图时，就要避免它的出现。（1 1）不合理的现象）不合理的现象1 1：对流：对流v（1 1）对流：所谓对流就是在一段线路上有同一）对流：所谓对流就是在一段线路上有同一种物资出现相对运输现象（往返运输）（同一段种物资出现相对运输现象（往返运输）（同一段线路上，两各方向都有流向），如左图。线路上，两各方向都有流向），如左图。v甲乙两地是一种对流现象。如果把流向图改成右甲乙两地是一种对流现象。如果把流向图改成右图，

7、就可以避免对流现象，从而可以节约运输量图，就可以避免对流现象，从而可以节约运输量202010=200(10=200(吨公里吨公里) )。201010(10)(20)乙甲左图 右图201010(10)(10)乙甲(20)（2 2）不合理的现象）不合理的现象2 2：迂回：迂回v（2 2）迂回迂回：当收点与发点之间的运输线路有两当收点与发点之间的运输线路有两条或两条以上时（即交通图成圈），如果运送的条或两条以上时（即交通图成圈），如果运送的货物不是走最短线路，则称这种运输为迂回运输。货物不是走最短线路，则称这种运输为迂回运输。v注：注：当交通图成圈时，如果流向图中内圈流向的当交通图成圈时，如果流向图

8、中内圈流向的总长（简称总长（简称内圈长内圈长）或外圈流向的总长（简称）或外圈流向的总长（简称外外圈长圈长）超过整个圈长的一半超过整个圈长的一半就称为就称为迂回运输迂回运输。例。例如某物资流向图如图所示。如某物资流向图如图所示。迂回运输的判断迂回运输的判断44（4）26左图左图44（4）26右图右图显然：左图为迂回运输显然：左图为迂回运输（3 3）、正规（最优）流向图）、正规（最优）流向图v正规（最优）流向图正规（最优）流向图：一个最优的调运方：一个最优的调运方案，它的流向图必是无对流、无迂回的流案，它的流向图必是无对流、无迂回的流向图，称这种流向图为正规流向图。向图，称这种流向图为正规流向图。

9、v物资调运的图上作业法就是寻找一个无对物资调运的图上作业法就是寻找一个无对流、无迂回的正规流向图。流、无迂回的正规流向图。v步骤如下：步骤如下： 作出一个无对流的初始可行方案；作出一个无对流的初始可行方案； 检验有无迂回检验有无迂回 若无，结束；若无，结束；否则，调整，直到最优。否则，调整，直到最优。三、图上作业法的求解过程三、图上作业法的求解过程v1 1、无圈（线状）的交通图、无圈（线状）的交通图v2 2、有圈的交通图、有圈的交通图v方法：方法：供需归邻站供需归邻站v【例例】求最优调运方案求最优调运方案324786451A1A2B1B3B2A5A3A4B4v口诀口诀：抓各端，各端供需归邻站抓

10、各端，各端供需归邻站v即即：先满足端点的要求，逐步向中间逼近，直至：先满足端点的要求，逐步向中间逼近，直至收点与发点得到全部满足为止。收点与发点得到全部满足为止。324786451A1A2B1B3B2A5A3A4B4（3）（4）（2）（3）（4）（7）（3）（10）练一练练一练答案答案v【例例】求最优调运方案求最优调运方案454786454A1A2B1B3B2B5A38B42273463v它的原则可归纳为：v流向划右方，对流不应当；里圈、外圈分别算，要求不过半圈长；如若超过半圈长，应甩运量最小段；反复求算最优方案。v第一步：变有圈为无圈。第一步：变有圈为无圈。v方法：方法：“丢边破圈丢边破圈”

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

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

13、 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=921/24+5=921/2，外圈长，外圈长= 821/2.= 825/22+3+6+3=1425/2，有迂回，所以流向图不是最，有迂回，所以流向图不是最优流向图。需要调整。优流向图。需要调整。v第六步：对方案进行调整。第六步：对方案进行调整。v方法方法：找出有迂回圈的流量最小的边（去掉的边：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边除外），改此边为丢掉的边（边A A1 1B B3 3），并补上），并补上原来丢掉的边（边原来丢掉的边（边B B1 1A A3 3），得到新的交通图。在），得到新的交通图。在此交通图上做新的流向图。直到所有圈的内圈长此交通图上做新的流向图。直到所有圈的内圈长小于二分之一圈长，外圈长小于二分之一圈长，小于二分之一圈长，外圈长小于二分之一