第27讲运筹学初步（1）
运筹学是利用数学来研究人力、物力的运用和筹划，使它们能发挥最大效率的科学。它包含的内容非常广泛，例如物资调运、场地设置、工作分配、排队、对策、实验最优等等，每类问题都有特定的解法。运筹学作为一门科学，要运用各种初等的和高等的数学知识及方法，但是其中分析问题的某些朴素的思想方法，如高效率优先的原则、调整比较的思想、尝试探索的方法等，都是我们小学生能够掌握的。
这些**于生活实际的问题，正是启发同学们学数学、用数学最好的思维锻炼题目。
本讲主要研究物资调运问题。
将一些物资从某些地方调往另一些地方，要求总运费或物资运行的总吨千米数最少，就是物资调运问题。
例1 a，b，c三地的距离（单位：千米）如左下图所示。现有一辆载重量4吨的汽车要完成下列任务：从a地运12吨煤到b地，从b地运8吨钢材到c地，从c地运16吨粮食到a地。
怎样安排才能使汽车空驶里程最短？
分析与解：如右上图所示，将各段需运输的次数（括号内的数）及运输走向（箭头指向）标在图上。由于c到a的次数最多，所以应从c开始。
按c→a→b→c，两次循环后，b地的钢材运完，c地还有8吨粮食待运，a地还有4吨煤待运。再从c运4吨粮食到a，然后空驶回c地，再从c运4吨粮食到a，最后从a运4吨煤到b。这样的安排只空驶了7千米，空驶里程最短。
例2 在一条公路上，每隔10千米有一座仓库（如下图），共有五座，图中数字表示各仓库库存货物的重量。现在要把所有的货物集中存放在一个仓库里，如果每吨货物运输1千米需要运费0.9元，那么集中到哪个仓库运费最少？
分析与解：最简单的方法是逐个计算集中到各个仓库所需的运费，然后加以比较。但这种方法计算繁琐，我们只需比较各点的优劣。例如，比较集中到c和集中到d的优劣。
如上图所示，从右向左运的货物，如果集中到d，那么只有e仓库的60吨运到d；如果集中到c，那么等于e仓库的60吨运到d，再将d仓库的10吨及e仓库运来的60吨一起运到c。所以运到c仓库比运到d仓库多[小精灵儿童**]
（60＋10）×10＝700（吨千米）。
同理，从左向右运的货物，运到c仓库比运到d仓库少。
（10＋30＋20）×10＝600（吨千米）。
两相比较，集中到d比集中到c好。
经过对各点的比较，货物集中到d仓库运费最少，运费为：
（10×30＋30×20＋20×10＋60×10）×0.9=1530（元）。
例3 北京、洛阳分别有11台和5台完全相同的机器，准备给杭州7台、西安9台，每台机器的运费如下表：
如何调运能使总运费最省？
分析与解：由表中看出，北京到杭州的运费比到西安便宜，而洛阳正相反，到西安的运费比到杭州便宜。所以，北京的机器应尽量运往杭州，洛阳的机器应尽量运往西安。
最佳的调运方案为：北京发往杭州7台，发往西安4台，洛阳发往西安5台。总运费为。
800×7＋1000×4＋600×5=12600（元）。
例4 北京、上海分别有10台和6台完全相同的机器，准备给武汉11台，西安5台，每台机器的运费如下表：
如何调运能使总运费最省？
分析与解：与例3不同的是，北京、上海到西安的运费都比到武汉的高，没有出现一高一低的情况。此时，可以通过比较运输中的差价大小来决定最佳方案。
上表中第一行的差价为600-500＝100（元），第二行的差价为 1000－700= 300（元）。说明从北京给西安多发1台机器要多付运费100元，而从上海给西安多发1台机器要多付运费300元。所以应尽量把北京的产品运往西安，而西安只要5台，于是可知北京调往西安5台，其余5台调往武汉，上海6台全部调往武汉，总运费为：
600×5＋500×5＋700×6＝9700（元）。
如果改为看表中的列，那么由于第一列的差价为700- 500=200（元），第二列差价为1000－600=400（元），所以武汉需要的机器应尽量从上海调运，而上海只有6台，不足的部分由北京调运。这个结论同前面得到的相同。
例5 a，b两个粮店分别有70吨和60吨大米，甲、乙、丙三个居民点分别需要30吨、40吨和50吨大米。从a，b两粮店每运1吨大米到三个居民点的运费如下表所示：
如何调运才能使运费最少？
分析与解： 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）如果流向图中有环形路线，在每一个环形路线（叫做圈）内，顺时针和逆时针方向调动的路程都不超过半圈长度。
判断是否最佳调运方案的两条标准从直观上很容易接受。如在下图中，右边的方案就比左边的好。
在实际图上作业时，可以先采取就近分配的方法，然后再逐步调整，使流向图满足最佳方案的两个条件。
用流向图的方法可得本题的最佳调运方案如下图：总运费为：
＝11300（元）。
练习271.如右图所示，工地上要把3车渣土从a运到b，把2车砖从c运到d。一辆汽车最少跑多远可完成任务？
两个粮店分别有80吨和60吨大米，甲、乙两个居民点分别需要55吨和85吨大米。从a，b两个粮店每运1吨大米到两个居民点的运费如下表所示。运费最少是多少元？
两化肥厂分别可以提供化肥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吨粮食，应如何调运才能使运费最省？
运费为多少元？
运筹学初步 一
六年级数奥第四讲 运筹学初步 一 例1 a，b，c三地的距离 单位 千米 如左下图所示。现有一辆载重量4吨的汽车要完成下列任务 从a地运12吨煤到b地，从b地运8吨钢材到c地，从c地运16吨粮食到a地。怎样安排才能使汽车空驶里程最短？例2 在一条公路上，每隔10千米有一座仓库 如下图 共有五座，图中...
运筹学试卷 物流运筹学
2012 2013学年第一学期。运筹学 试卷。试卷 自拟送卷人 唐文广打印 校对 唐文广。一 6分 已知线性规划模型。写出该问题的对偶问题。二 15分 用单纯形法求解下面线性规划问题 作1张表即可 三 10分 求解下面标准指派问题，其中效率矩阵为。四 15分 某项工程由a b i j k等11项工序...
运筹学试题与案例集 运筹学
20xx年运筹学试题与案例集 天津。全国运筹学精品课程建设与题库案例交流研讨会运筹学试题与案例集 内部交流资料 中国运筹学会教育普及工作委员会 天津运筹学会 天津工业大学 20xx年5月 全国运筹学精品课程建设与题库案例交流研讨会 2010.05 目录 第一部分运筹学试题4 试题 1 北京工商大学4...