图上作业法
目录 |
图上作业法在运输图上求解线性规划运输模型的方法。它是在一张运输交通上通过一定步骤的规划和计算来完成物资调运计划的编制工作，以便使物资运行的总吨—公里数最小可使物资运费降低，并缩短了运输时间，所以，在一定条件下称这样的方案为最优方案。
图上作业法的步骤[1]
制定一个物资调运方案时：
1、首先要编制物资平衡表（如下图所示）。
图1：物资平衡表
在编制物资平衡表时需要做3件事。
(1)出需要调出物资的地点（即发点）及发量。
(2)出需要调进物资的地点（即收点）及收量。
(3)求：总发量=总收量。
2、第二步，根据物资平衡表和收点，发点间的相互位置绘制交通图。所谓交通图就是表明收点和发点间的相互位置以及联结这些点之间的交通线路的简要地图。在交通图上，用圆圈“〇”表示发点，将该发点的发量填入圆圈“〇”内。用方框“□”表示收点，将该收点的收量填入方框“□”内。两点间的距离，记在交通线路的旁边。
3、第三步，交通图绘制好后，即可在其上面进行物资调运，找出初始调运方案(初始基可行解)，作物资调运流向图。
我们用箭头“→”表示物资调运的方向即称流向，并规定：流向“→”必须画在沿着线路前进的右侧。把运送物资的数量记在流向“→”的旁边并加括号（ ），以区别于两点之间的距离数。
另一方面，为了保持图面的整洁，流向量最好不要通过收，发点以及交叉路口，如图1中，(a)，(b)是正确的。
图上作业法的注意事项[1]
在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨—公里数是最小的调运方案。这就要注意在调运中不要发生对流运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。
（1）对流：所谓对流就是在一段线路上有同一种物资往返运输（同一段线路上，两各方向都有流向），如下图。
图2
图3
将某种物资10吨从A1运往B2，同时又有同样的物资10吨同时从A2运往B1，于是在A1A2之间就出现了对流现象.如果把流向图改成图3，即将A1的10吨运往B1，而将A2的10吨运往B2，就避免了A1A2的对流，从而可以节约运输量
(吨公里)。
（2）迂回：当交通图成圈时，如果流向图中内圈流向的总长（简称内圈长）或外圈流向的总长（简称外圈长）超过整个圈长的一半就称为迂回运输。例如某物资流向图如下图4所示。
图4
图5
显然，它是一个迂回运输流向图，它的内圈长6大于整个圈长的一半5。如果把它改成图5，就避免了迂回现象，可节约运输量
（吨公里） 理论上可以证明，一个物资调运方案中，如果没有对流和迂回运输，则该方案就是最优调运方案。即运输量最小的方案。
从以上讨论可以看到，图上作业法的实质就是在一张交通图上寻找没有对流和迂回的最优流向图。
为了贯彻以上原则，则须采用逐步逼近法，即我们可以先设法作一个流向图，然后来检查它是不是最优的，如果是的话，问题就解决了;如果不是，就把这个流向图稍微变化一下，这样的变化称为调整。调整后的新流向图所花费的吨公里比原流向图的要少一些。然后再检查新流向图是不是最优的，如果仍旧不是，就再进行调整，一直到找到最优流向图为止。
物资运输的交通图总共分为两类：
一类是不成圈的交通图；
另一类是成圈交通图。