分析与解： A，B粮店共有大米 70＋60=130（吨），甲、乙、丙三个居民点需要大米 30＋40＋50=120（吨），供应量与需求量不相等，这与例4不同。但是我们仍可以通过差价的大小来决定最佳方案。
观察上表各列两数之差，最大的是第二列10－7=3，因此A粮店的大米应尽可能多地供应乙，即A供应乙40吨。
在剩下的两列中，第三列的差大于第一列的差，所以A粮店剩下的30吨应全部供应丙。
因为A粮店的的大米已分配完，其余的由B粮店供应，即B供应甲30吨，供应丙20吨。
调运方案如右表。
相应的运费为：
30×3＋40×7＋30×3＋20×5=560（元）。
例6 下图中有四个仓库（用○表示）和五个工厂（用△表示），四个仓库中存放着五个工厂需要的同一种物资，○内数字表示该仓库可调出物资的数量（单位：吨），△ 内数字表示该工厂需调入物资的数量（单位：吨），两地之间连线上的数字表示两地间的距离（单位：千米）。已知每吨千米运费5元，请设计一个调运方案，使总运费最少？
为解决这类问题，我们先介绍流向图的概念。在物资调运问题中，如果要将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（元）。
练习27
1.如右图所示，工地上要把3车渣土从A运到B，把2车砖从C运到D。一辆汽车最少跑多远可完成任务？
2.A，B两个粮店分别有80吨和60吨大米，甲、乙两个居民点分别需要55吨和85吨大米。从A，B两个粮店每运1吨大米到两个居民点的运费如下表所示。运费最少是多少元？
3.A，B两化肥厂分别可以提供化肥2500吨和4000吨，甲、乙两地分别需要化肥3000吨和3500吨。从A，B两个化肥厂每运1吨化肥到甲、乙两地的运费如下表所示。
运费最少是多少？
4.有A，B两个金属仓库，分别存有铝材60吨和40吨，另有甲、乙两个工厂，分别需要铝材35吨和45吨。从A，B两仓库每运1吨铝材到这两个工厂的运费如下表所示。
运费最少是多少？
5.某学校调整教室桌椅，右图中标出了教室的位置，图中□内的数字表示该教室要搬出桌椅的数量，○内的数字表示该教室要搬入桌椅的数量。怎样搬运最省事？
6.60个同学去野营，他们搭的五顶帐蓬正好位于正五边形的五个顶点上（见左下图），图中圆圈内的数字表示各个帐蓬内的人数。现在想将五个帐蓬内的人数调整为一样多，怎样调动最简便？
7.右上图是粮店和居民点的位置示意图，○表示粮店，○内的数字表示该粮店的存粮数（单位：吨），●表示居民点，线段表示道路，线段上的数字表示距离（单位：千米）。假设运输1吨粮食每千米的运费为 1.2元，每个居民点都需要30吨粮食，应如何调运才能使运费最省？运费为多少元？
相关推荐：
loading