图上作业法专题.pptVIP

第四步：调整方案 4 5 4 7 8 6 4 5 4 A1 A2 B1 B3 B2 B5 A3 8 B4 2 2 7 3 4 6 3 （4） （8） （1） （5） （1） （2） （6） 图 4-11 第五步：对新方案进行检验。 圈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），得到新的交通图。在此交通图上做新的流向图。 第六步：调整方案 4 5 4 7 8 6 4 5 4 A1 A2 B1 B3 B2 B5 A3 8 B4 2 2 7 3 4 6 3 （3） （7） （1） （4） （2） （2） （6） 图 4-12 可验证：此方案中无迂回现象。即为最优方案。 发 收 B1 B2 B3 B4 B5 发货量 A1 3 4 7 A2 4 2 2 8 A3 1 4 5 收货量 4 4 4 6 2 练一练 答案 图上作业法 有某物资7t，由发出点A1,A2,A3发出，发量分别为3,3,1(t)，运往收点B1,B2,B3,B4，收量分别为2,3,1,1(t)，收发量平衡，交通图如下图，问应如何调动，才使t·km最小？ 【例1】 * （2）图上作业法 【例3】有某物资7t，由A1，A2，A3发出，发量分别为3，3，1（t），运往收点B1，B2，B3，B4，收量分别为2，3，1，1（t），收发量平衡，交通图如图4—1所示，问应如何调运，才使t·km最小。 。 4 3 1 2 1 3 3 1 7 3 5 4 3 2 4 * 3 1、破圈求初始解 1 2 1 3 3 1 7 3 5 4 3 2 4 3 1 2 1 1 4 ②检查有无迂回，方法水对流想图中的各圈进行检查，侃侃有无迂回。如果没有迂回，即该圈总长的一半均大于内流长和外流长，这个初始方案就是最优方案，如果其中某一圈有迂回，这个方案就不是最优方案，需要改进。 在图中，圈A1B1B2A3B4的总长为23km，外流长为5+4+3=12km，大于圈长的一半，因而需要调整。在看圈B2A2B3A3其总长为13km，圈中内流长为3km，外流长为2km，都小于圈长的一半，因此此圈不必调整。 * 对圈A1B1B2A3B4的调整方法是：在外圈的个流量中，减去外圈的最小流量1t；然后在内圈的个流量中加上1t，在此圈中，因无内流量，所以无处可加；另外，在无流量的线段上，新添上内圈流量1t，这样得出新的流量图。 方案调整 1 2 1 3 3 1 7 3 5 4 3 2 4 3 1 2 1 1 4 3 1 2 1 3 3 1 7 3 5 4 3 2 4 2 1 2 1 1 4 3 * 1 2 1 3 3 1 7 3 5 4 3 2 4 2 1 2 1 1 4 3 2 1 2 1 3 3 1 7 3 5 4 3 4 2 3 1 4 3 1 在圈B2A2B3A3中外圈长为4+3=7大于圈长的一半，调整为内圈加“1”外圈减“1” 此时两个圈都没有迂回是最优方案总的TKM 为： 7*1+2*5+1*4+3*2=27 方案调整 * 8 7 5 4 5 4 6 9 8 3 4 6 6 5 7 5 7 代表仓库 代表需求 * 最短路问题 ??? 2、分析还没有P标号的各点，比较T(j)和P(1)+l1j，l1j为V1到Vj的弧长。将Vj的新标号取较小者，即T(j)=min[T(j),P(1)+l1j]。如果[P(1)+l1j]T(j)，则用P(1)+l1j代替T(j)作为Vj点的新的T标号。 T(B)=min[T(B),P(A)+l12]=min[∞,0+3]=3T(C)=min[T(C),P(A)+ l13]=min[∞,0+4]=4 ??? 点V2的T标号的数最小，令P(2)=16。 1、将A标上P标号0，即P(1)=0，表示从A到A的距离为0。给其他点（B～F）标上T标号，即T(j)=∞，j=2,3,4,5,6。 F 5 A 0 E C D B 3 7 4 5 4 3 4 3 * ??? 3、以点B（刚得到标号的点）作为比较基础，重复上述过程，即比较T(j)与[P(2)+l2j]，j=3,4,5,6取较小的数作为Vj的新的T标号。 T(D)=3+5=8 T(C)=4 T(E)=3+7=10??? 比较T(D)、T(E)、 T(C)，其中T(C)为最小，将点C的T标号改为P标号：P(C)=4。