Question

下图中有四个仓库（用○表示）和五个工厂（用△表示），四个仓库中存放着五个工厂需要的同一种物资，○内数字表示该仓库可调出物资的数量（单位：吨），△内数字表示该工厂需调入物资的数量（单位：吨），两地之间连线上的数字表示两地间的距离（单位：千米）．已知每吨千米运费5元，请设计一个调运方案，使总运费最少？

Answer 1

分析：为解决这类问题，我们先介绍流向图的概念．在物资调运问题中，如果要将a吨物资从A地调往B地，那么从A沿路线右边向B画一箭头，并标上a，称为流向，由（若干个）流向构成的图称为流向图．每一个调运方案对应一个流向图．

用数学的方法可以证明，一个调运方案是最佳的，当且仅当：（1）流向图上没有对流；（2）如果流向图中有环形路线，在每一个环形路线（叫做圈）内，顺时针和逆时针方向调动的路程都不超过半圈长度．判断是否最佳调运方案的两条标准从直观上很容易接受．如在下图中，右边的方案就比左边的好．


在实际图上作业时，可以先采取就近分配的方法，然后再逐步调整，使流向图满足最佳方案的两个条件．

解答：解：用流向图的方法可得本题的最佳调运方案如图：
总运费为：
5×（20×8+10×13+20×14+30×9+30×12+
40×10+80×7+20×5）
=11300（元）．

点评：解决此类问题时，利用流向图可以使调配路线更清楚易懂．