表上作业法与图上作业法教程文件.ppt
表上作业法与图上作业法 工地料库ABCDE供应量(t)甲32353100乙33134300丙78422600丁54778800需求量(t)250300350400500180030002000400010002000250503000000v运费=2100+1300+2400+2200+5250+4200+750+8300=6500 工地料库AV1=3BV2=2CV3=5DV4=6EV5=6甲U1=032353乙U2=-433134丙U3=-478422丁U4=254778300200400100200250503000-2-1-345128103-1 工地料库AV1=0BV2=-1CV3=2DV4=3EV5=3甲U1=032353乙U2=-133134丙U3=-178422丁U4=5547783002004001003002505020033124312883-1 工地料库AV1=1BV2=0CV3=3DV4=3EV5=3甲U1=032353乙U2=-233134丙U3=-178422丁U4=45477830040020010030025050200222220453791v运费=3100+1300+2400+2200+5250+4300+750+7200=6000课后作业 销地 产地B1B2B3B4产量A1A2A3359637267648657075销量50455560210图上作业法图上作业法v有某物资7t，由发出点A1,A2,A3发出，发量分别为3,3,1(t)，运往收点B1,B2,B3,B4，收量分别为2,3,1,1(t)，收发量平衡，交通图如下图，问应如何调动，才使tkm最小？3131213A1B2A2B3A3B4B174432435v(1)选用“去线破圈”的方法把有圈的交通图化为无圈的交通图，再做一个无对流的流向图。“去线破圈”的方法，去一线破一圈，有几个圈去掉几条线。对某一个圈，可任意去一边，于是就破掉了一圈，这样去一边，破一圈，直至无图，即可把一个有圈的交通图，化成一个无圈的交通图。v一般是先去掉长度最长的交通线，比如，去掉A1B4(7km)，破A1B1B2A3B4圈，再去掉A3B3(4km)，破B2A2B3A3圈。这样原来的有圈交通图，便成了一个无圈的交通图。v在上图的基础上做一个无对流的流向图。注意：与表上作业法类似，表上注意：与表上作业法类似，表上作业法要求有调运量的格子数应作业法要求有调运量的格子数应该是收点数该是收点数+发点数发点数-1。图上作。图上作业法要求在流向图上的箭头数（业法要求在流向图上的箭头数（有调运量的边数）也应为收点数有调运量的边数）也应为收点数+发点数发点数-1。这一要求也可以等。这一要求也可以等价地表述为：在去线破圈后得到价地表述为：在去线破圈后得到的不成圈的交通图上，要求每边的不成圈的交通图上，要求每边都应该有流向。都应该有流向。3131213A1B2A2B3A3B4B1443235(3)(1)(2)(1)(1)v因此，某一边无流向时，必须在这一边上添上调运量为0的虚流向，和其它流向同样对待。按照这一要求，应在A3边上添上虚流向。于是，再补上去掉的边，得下图：3131213A1B2A2B3A3B4B1443235(3)(1)(2)(1)(1)(0)v(2)检查有无迂回方法：对流向图中只有一边没有流向的各圈进行检查。如果没有迂回，即已到最优调运方案。如果有迂回，则需要进行调整。首先分别计算线路的首先分别计算线路的全圈长、内圈长全圈长、内圈长和和外圈长外圈长（圈（圈长即指里程数），如果长即指里程数），如果内圈长和外圈长都分别小于内圈长和外圈长都分别小于全圈长的一半，全圈长的一半，则该方案即为最优方案；否则，即则该方案即为最优方案；否则，即为非最优方案，需要对其进行调整为非最优方案，需要对其进行调整A1B1B2A3B4外圈长5+4+312，大于全圈长23的1/2v(3)调整方案:方法：在有迂回的外圈各流量中减去一个最小调运量，在内圈（含无调运量的边）（含无调运量的边）各流量上加上这一最小调运量。圈A1B1B2A3B4中的最小流量为，在外圈上减去该最小调运量后，有两条边同时为，需在有两条边同时为，需在任意一边上记上任意一边上记上0运量运量，于是，得到调整后的调运方案。如图3131213A1B2A2B3A3B4B1443235(2)(0)(2)(1)(1)7（1）经检查圈经检查圈B2A2B3A3不构成迂回运输，所以所得到的不构成迂回运输，所以所得到的方案已是最优方案。方案已是最优方案。最优调运方案的总运输量为最优调运方案的总运输量为Z=25+23+12+14+17 =29tkm此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢
