此题的做法可以用图论或排队论来做,我们巧妙的发现,仓库并没有设置存储上限,所以本题又可转成路径最短问题,而产量总和又恰等于需求总和。
所以先画出路线图(由于100比其他运费额高出两个数量级,即运送100倍的物资才能抵消,所以路线图不考虑100的情况,即使考虑,其结果也是相同的)如图
分析:
(1)从图中可以看出4的供给只有Z,所以首先使z存储5个单位
(2)3的路径中到仓库的最小路径有z-3,y-3都是7,先不考虑,可以作为后面的调节工厂供应的砝码;同理2的最短路径也是有两个y-2,z-2都是6.
(3)对一的供应x-1为最小,所以使x存储3个单位
(4)到z仓库的路径只有b-z,所以使b供应出5个单位给z,剩余3个单位
(5)到x仓库的路径最小为a-x,所以令a供应3个单位给x,剩余6个单位
(6)对于2,3而言,从y,z供应是无异性的,所以只需使a,b剩余单位以最小路径供应到y或z,就行了,得到a-y(6个单位),b-y(3个单位)
那么整体的运输如下:(出发地-目的地(运输单位))
a-x(3),a-y(6),b-y(3),b-z(5) x-1(3),y-2(5),y-3(4),z-4(5)
总运费:(1×3+2×6+1×3+2×5)+(5×3+6×5+7×4+4×5)=121