图上作业法

,单击此处编辑母版标题样式,第二节 图上作业法,一、图上作业法的基本知识,1.,图上作业法的常用符号,2.,线形分类,二、交通图不含圈的图上作业法,三、交通图含圈的图上作业法,主题思路,一、运输路线图上作业法的的定义、适用范围,二、编制并解释交通图和流向图,三、内圈流向、外圈流向举例,四、不合理的现象（对流、迂回）,五、案例分析,六、技能训练解析,运输路线图上作业法,定义,：,图上作业法是在运输图上求解线性规划运输模 型的方法。它是在一张运输交通上通过一定步骤的规划和计算来完成物资调运,计划,的编制工作，以便使,物资,运行的总吨,公里数最小可使物资运费降低，并缩短了,运输时间,，所以，在一定条件下称这样的方案为最优方案。,适用范围：,在铁路、公路等交通部门经常使用这种方法决策最优运输问题。,交通图,反映发点（产地）与收地（销地）及交通线路及其距离组成的图形。,发点用“”表示，发出货物的数量记在“”之内（单位：吨）,收地（销地）用“”表示，收取货物的数量记在“”之内（单位：吨）,两点之间的线路长度记在交通线路的旁边。,10,5,9,9,7,8,A,D,E,G,F,B,C,5,3,2,2,3,4,含有圈的流向图的补充规定,顺时针方向的流向必须画在圈的内侧，称为内圈流向,逆时针方向的流向必须画在圈的外侧，称为外圈流向,4,4,（,4,）,2,6,图：,4-6,4,4,（,4,）,2,6,图：,4-7,内圈流向、外圈流向举例,顺时针方向的流向必须画在圈的内侧，称为内圈流向。如图：,4-6,逆时针方向的流向必须画在圈的外侧，称为外圈流向。如图：,4-7,20,10,10,(10),(20),乙,甲,图,4-4,图,4-5,20,10,10,(10),(10),乙,甲,(20),甲乙两地是一种对流现象。如果把流向图改成图,4-5,，就可以避免对流现象，从而可以节约运输量,20,10=200(,吨公里,),。,（,1,）对流：所谓对流就是在一段线路上有同一种物资出现相对,运输现象（往返运输）（同一段线路上，两各方向都有流向），如图,4-4,。,不合理的现象,2,：迂回,（,2,）,迂回,：,当收点与发点之间的运输线路有两条或两条以上时（即交通图成圈），如果运送的货物不是走最短线路，则称这种运输为迂回运输。,注：,当交通图成圈时，如果流向图中内圈流向的总长（简称,内圈长,）或外圈流向的总长（简称,外圈长,）,超过整个圈长的一半,就称为,迂回运输,。例如某物资流向图如图,4-6,、,4-7,所示。,4,4,（,4,）,2,6,图：,4-6,4,4,（,4,）,2,6,图：,4-7,显然：图,4-6,为迂回运输,迂回运输的判断,正规（最优）流向图,：,一个最优的调运方案，它的流向图必是无,对流、无迂回的流向图，称这种流向,为正规流向图。,物资调运的图上作业法就是寻找一个无对流、无迂回的正规流向图。,步骤如下：,作出一个无对流的初始可行方案；,检验有无迂回；,若无，结束；,否则，调整，直到最优。,（,一）任务内容,有某物资,7,万吨，由发运点,A1,、,A2,、,A3,发出，发量分别为,3,、,3,、,1,（万吨），运往收点,B1,、,B2,、,B3,，收收量分别为,2,、,3,、,1,（万吨），收发量平衡，交通路线如图,3-6,所示。问应如何调运，才能使总运输量最小。,（二）任务目标,掌握成圈与不成圈的图上作业法。,（三）任务准备,图上作业法的适用范围,案例分析,1,2,1,3,3,1,3,（,7,）,（,3,）,（,4,）,A1,（,5,）,B2,（,4,）,BI,A2,（,2,）,（,3,）,B4,A3,B3,注： 表示接收点，其中数字表示运入量。 表示发运点，其中数字表示发运量。,（ ）,中数字表示两地距离。,（,4,）,图,3-6,步骤一 去线破圈,作一个没有对流的流向图，用“去线破圈”的方法，去一线破一圈，有几个圈去掉几个线，把有圈的交通图化成不成圈的交通图。一般是先去掉最长的交通线，如去掉,A1B4,（,7km,），破,A1B1B2A3B4,圈。再去掉,A3B3,（,4km,），破,B2A2B3A4,圈，原来有圈的交通图，变成了不成圈的交通图，如图,3-7,所示。,然后从各个端点开始，在图上做一个没有对流的流向图。,1,2,1,3,3,1,3,（,7,）,（,3,）,（,4,）,A1,（,5,）,B2,（,4,）,BI,（,2,）,（,3,）,B4,A3,（,4,）,B3,A2,图,3-7,3,1,2,1,1,步骤二 检验有无迂回,对流向图中的各圈进行检查，看有无迂回。如果没有迂回，这个初始方案就是最优方案；如果其中某一圈又迂回，这个,方案就不是最优方案，需要改进。,圈,A1B1B2A3B4,：总长为（,5+4+4+3+7,）,=23km,半圈长为（,23/2,）,=11.5km,外圈流向总长为,：（,5+4+3,）,=12km,里圈流向总长为,0 km,因为外圈流向总长超过了全圈总长的,1/2,（,12km11.5km,）,可以断定。圈,A1B1B2A3B4,初始运输线路存在迂回现象，所对应的运输方案不是最优方案，因而需要整体优化。,再看看,B2A2B3A4,，其总长为,13km,，圈中内流向长为,3km,，外流向为,2km,都小于圈长的一半，因此此圈不必调整。,步骤三 重新去段破圈，调整流向。,初始方案中圈,A1B1B2A3B4,的里圈符合要求，外圈流向超过全圈总长的一半，故需缩小外圈。,对圈,A1B1B2A3B4,的调整方法是，在外圈的各流量中，减去外圈的最小流量,1,万吨，然后在内圈的各流量中加上,1,万吨，在此圈中，因无内流量，所以无处可加。另外，在无流量的线段上，新添上内圈流量,1,万吨，这样得出新的流量图。如图,3-8,所示,.,1,2,1,3,3,1,3,（,7,）,（,3,）,（,4,）,（,5,）,B2,（,4,）,BI,A2,（,2,）,（,3,）,B4,A3,B3,（,4,）,1,2,1,1,2,图,3-8,检验新运输线路图中的里外圈流向长，看是否超过全圈（封闭回路线）总长的,1/2.,新的流量图中，在,A1B1B2A3B4,圈内，内流长,4+7=11km,，外流长,5km,，都不超过新圈长（,23km,）的一半。在,B2A2B3A4,圈内，内流长为,3km,，外流长为,4+2=6km,，也都没有全圈（,13km,）的一半，因此，这个流向图没有迂回现象，是该问题的最优调运方案。此时，按调整后的新方案组织运输，总运输量为：,17+25+14+23+21=29(t.km),初始方案组织运输的运输量为：,35+14+32+21+31=30,（,t.km,）,由此可知，调整后的运输方案比初始运输方案节约运力为,1t.km.,技能训练,某企业由甲、乙、丙,3,个工厂，产品销往,A,、,B,、,C,、,D,、,E,、,F,、,G,、,H,八个地区。各工厂的位置、产量和各销售地区的位置、需求量如图,3-9,所示。请运用图上作业法确定最优运输线路图。,A,丙,（,74,）,A,A,E,A,H,A,G,A,F,A,C,A,D,A,B,乙,甲,（,78,）,-1500,（,41,）,（,55,）,+2900,（,57,）,-1300,（,32,）,+3200,-600,-900,（,132,）,-1000,+2000,（,57,）,-1000,-900,-900,（,75,）,（,45,）,（,74,）,（,109,）,图,3-9,解：步骤一 去线破圈,作一个没有对流的流向图，用,“,去线破圈,”,的方法，去一线破一圈，去掉甲乙（,109,），破甲乙,E,丙,GF,圈。再去掉甲,B,（,75,），破甲,BD,乙,E,丙,GF,圈，原来有圈的交通图，变成了不成圈的交通图，如图,3-10,所示。然后从各个端点开始，在图上做一个没有对流的流向图,A,丙,（,74,）,A,A,E,A,H,A,G,A,F,A,C,A,D,A,B,乙,甲,（,78,）,-1500,（,41,）,（,55,）,+2900,（,57,）,-1300,（,32,）,+3200,-600,-900,（,132,）,-1000,+2000,（,57,）,-1000,-900,-900,（,75,）,（,45,）,（,74,）,（,109,）,1000,1000,1500,1800,900,100,1400,600,900,图,3-10,步骤二 检验有无迂回,圈,BD,乙,E,丙,GF,：,总长为（,32+57+41+74+57+75+45+74,）,=455,半圈长为（,455/2,）,=227.5,外圈流向总长为,（,57+32+74+45+57,）,=265,里圈流向总长为,41,因为外圈流向总长超过了全圈总长的,1/2,可以断定。圈,BD,乙,E,丙,GF,初始运输线路存在迂回现象，所对应的运输方案不是最优方案，因而需要整体优化。,圈甲乙,E,丙,GF,：,总长为（,109+57+74+41+57+32,）,=370,半圈长为（,370/2,）,=185,外圈流向总长为（,57+32+57,）,=146,里圈流向总长为,41,圈乙,DB,甲：,总长为（,74+45+75+109,）,=303,半圈长为（,303/2,）,=151.5,外圈流向总长为（,74+45,）,=119,内圈流向总长为,0,圈甲乙,E,丙,GF,、圈乙,DB,甲的,外圈流向总长和内圈流向总长都小于其半圈长，所以不存在迂回现象。,步骤三 重新去段破圈，调整流向。,A,丙,（,74,）,A,A,E,A,H,A,G,A,F,A,C,A,D,A,B,乙,甲,（,78,）,-1500,（,41,）,（,55,）,+2900,（,57,）,-1300,（,32,）,+3200,-600,-900,（,132,）,-1000,+2000,（,57,）,-1000,-900,-900,（,75,）,（,45,）,（,74,）,（,109,）,1000,100,1500,900,800,500,1500,900,900,900,步骤四 再次检查有无迂回,圈,BD,乙,E,丙,GF,：,总长为（,32+57+41+74+57+75+45+74,）,=455,半圈长为（,455/2,）,=227.5,外圈流向总长为,（,57+74+57,）,=188,里圈流向总长为 （,32+41+74+75,）,=222,圈甲乙,E,丙,GF,：,总长为（,109+57+74+41+57+32,）,=370,半圈长为（,370/2,）,=185,外圈流向总长为（,57+57,）,=114,里圈流向总长为 （,32+41+41+74,）,=147,圈乙,DB,甲：,总长为（,74+45+75+109,）,=303,半圈长为（,303/2,）,=151.5,外圈流向总长为,74,内圈流向总长为,75,圈,BD,乙,E,丙,GF,、圈甲乙,E,丙,GF,、圈乙,DB,甲的,外圈流向总长和内圈流向总长都小于其半圈长，所以不存在迂回现象。,此时，按调整后的新方案组织运输，,总运输量为：,1500,78+800,32+500,57+900,55+1500,41+900,74+100,57+1000,132+900,75+900,74=620500,初始方案组织运输的运输量为：,1500,78+100,32+1400,57+900,55+600,41+1000,57+1000,132+900,45+1800,74=636800,由此可知,，调整后的运输方案比初始运输方案节约运力为,636800620500=16300,