1、六年级奥数专题二十七：运筹学初步（1）关键词 ：运筹 运筹学 空驶 调运 奥数 千米 粮食 初步 物资 年级运筹学是利用数学来研究人力、物力的运用和筹划，使它们能发挥最大效率的科学。它包含的内容非常广泛，例如物资调运、场地设置、工作分配、排队、对策、实验最优等等，每类问题都有特定的解法。运筹学作为一门科学，要运用各种初等的和高等的数学知识及方法，但是其中分析问题的某些朴素的思想方法，如高效率优先的原则、调整比较的思想、尝试探索的方法等，都是我们小学生能够掌握的。这些来源于生活实际的问题，正是启发同学们学数学、用数学最好的思维锻炼题目。本讲主要研究物资调运问题。将一些物资从某些地方调往另一些地方
2、，要求总运费或物资运行的总吨千米数最少，就是物资调运问题。例 1 A，B，C 三地的距离（单位：千米）如左下图所示。现有一辆载重量 4 吨的汽车要完成下列任务：从 A 地运 12 吨煤到 B 地，从 B 地运 8 吨钢材到 C 地，从 C 地运 16 吨粮食到 A 地。怎样安排才能使汽车空驶里程最短？分析与解：如右上图所示，将各段需运输的次数（括号内的数）及运输走向（箭头指向）标在图上。由于 C 到 A 的次数最多，所以应从 C 开始。按 CABC，两次循环后，B 地的钢材运完，C 地还有 8 吨粮食待运，A 地还有 4 吨煤待运。再从 C 运 4 吨粮食到 A，然后空驶回 C 地，再从 C
3、运 4 吨粮食到 A，最后从 A 运 4 吨煤到 B。这样的安排只空驶了 7 千米，空驶里程最短。例 2 在一条公路上，每隔 10 千米有一座仓库（如下图），共有五座，图中数字表示各仓库库存货物的重量。现在要把所有的货物集中存放在一个仓库里，如果每吨货物运输1 千米需要运费 0.9 元，那么集中到哪个仓库运费最少？分析与解：最简单的方法是逐个计算集中到各个仓库所需的运费，然后加以比较。但这种方法计算繁琐，我们只需比较各点的优劣。例如，比较集中到 C 和集中到 D 的优劣。如上图所示，从右向左运的货物，如果集中到 D，那么只有 E 仓库的 60 吨运到D；如果集中到 C，那么等于 E 仓库的 6
4、0 吨运到 D，再将 D 仓库的 10 吨及 E 仓库运来的 60 吨一起运到 C。所以运到 C 仓库比运到 D 仓库多（6010 ）10700（吨千米）。同理，从左向右运的货物，运到 C 仓库比运到 D 仓库少（103020）10 600（吨千米）。两相比较，集中到 D 比集中到 C 好。经过对各点的比较，货物集中到 D 仓库运费最少，运费为：（1030 302020106010）0.9=1530 （元）。例 3 北京、洛阳分别有 11 台和 5 台完全相同的机器，准备给杭州 7 台、西安 9 台，每台机器的运费如下表：如何调运能使总运费最省？分析与解：由表中看出，北京到杭州的运费比到西安便
5、宜，而洛阳正相反，到西安的运费比到杭州便宜。所以，北京的机器应尽量运往杭州，洛阳的机器应尽量运往西安。最佳的调运方案为：北京发往杭州 7 台，发往西安 4 台，洛阳发往西安 5 台。总运费为8007 10004 6005=12600（元）。例 4 北京、上海分别有 10 台和 6 台完全相同的机器，准备给武汉 11 台，西安 5 台，每台机器的运费如下表：如何调运能使总运费最省？分析与解：与例 3 不同的是，北京、上海到西安的运费都比到武汉的高，没有出现一高一低的情况。此时，可以通过比较运输中的差价大小来决定最佳方案。上表中第一行的差价为 600-500100（元），第二行的差价为 10007
6、00= 300（元）。说明从北京给西安多发 1 台机器要多付运费 100 元，而从上海给西安多发 1 台机器要多付运费 300 元。所以应尽量把北京的产品运往西安，而西安只要 5 台，于是可知北京调往西安 5 台，其余 5 台调往武汉，上海 6 台全部调往武汉，总运费为：6005 500570069700（元）。如果改为看表中的列，那么由于第一列的差价为 700- 500=200（元），第二列差价为1000600=400（元），所以武汉需要的机器应尽量从上海调运，而上海只有 6 台，不足的部分由北京调运。这个结论同前面得到的相同。例 5 A，B 两个粮店分别有 70 吨和 60 吨大米，甲、乙
7、、丙三个居民点分别需要 30 吨、40 吨和 50 吨大米。从 A，B 两粮店每运 1 吨大米到三个居民点的运费如下表所示：如何调运才能使运费最少？分析与解： A，B 粮店共有大米 7060=130（吨），甲、乙、丙三个居民点需要大米 304050=120（吨），供应量与需求量不相等，这与例 4 不同。但是我们仍可以通过差价的大小来决定最佳方案。观察上表各列两数之差，最大的是第二列 107=3，因此 A 粮店的大米应尽可能多地供应乙，即 A 供应乙 40 吨。在剩下的两列中，第三列的差大于第一列的差，所以 A 粮店剩下的 30 吨应全部供应丙。因为 A 粮店的的大米已分配完，其余的由 B 粮店
8、供应，即 B 供应甲 30 吨，供应丙 20吨。调运方案如右表。相应的运费为：303407303205=560（元）。例 6 下图中有四个仓库（用 表示）和五个工厂（用表示），四个仓库中存放着五个工厂需要的同一种物资，内数字表示该仓库可调出物资的数量（单位：吨）， 内数字表示该工厂需调入物资的数量（单位：吨），两地之间连线上的数字表示两地间的距离（单位：千米）。已知每吨千米运费 5 元，请设计一个调运方案，使总运费最少？为解决这类问题，我们先介绍流向图的概念。在物资调运问题中，如果要将 a 吨物资从 A 地调往 B 地，那么从 A 沿路线右边向 B 画一箭头，并标上 a，称为流向（见下图）。由
9、（若干个）流向构成的图称为流向图。每一个调运方案对应一个流向图。用数学的方法可以证明，一个调运方案是最佳的，当且仅当：（1）流向图上没有对流；（2）如果流向图中有环形路线，在每一个环形路线（叫做圈）内，顺时针和逆时针方向调动的路程都不超过半圈长度。判断是否最佳调运方案的两条标准从直观上很容易接受。如在下图中，右边的方案就比左边的好。在实际图上作业时，可以先采取就近分配的方法，然后再逐步调整，使流向图满足最佳方案的两个条件。用流向图的方法可得本题的最佳调运方案如下图：总运费为：5（208101320143093012 4010 807205）11300 （元）。练习 271.如右图所示，工地上要
10、把 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 吨和
11、45 吨。从 A，B 两仓库每运 1 吨铝材到这两个工厂的运费如下表所示。运费最少是多少？5.某学校调整教室桌椅，右图中标出了教室的位置，图中内的数字表示该教室要搬出桌椅的数量，内的数字表示该教室要搬入桌椅的数量。怎样搬运最省事？6.60 个同学去野营，他们搭的五顶帐蓬正好位于正五边形的五个顶点上（见左下图），图中圆圈内的数字表示各个帐蓬内的人数。现在想将五个帐蓬内的人数调整为一样多，怎样调动最简便？7.右上图是粮店和居民点的位置示意图，表示粮店，内的数字表示该粮店的存粮数（单位：吨），表示居民点，线段表示道路，线段上的数字表示距离（单位：千米）。假设运输 1 吨粮食每千米的运费为 1.2 元，每个居民点都需要 30 吨粮食，应如何调运才能使运费最省？运费为多少元？
