科普-中华学生百科全书-第5部分
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
纯形法”来求最优解；对于大型工厂、地区、部门，相关因素可能成百上千，
这时就要借助于电子计算机来求解了。通过图形法或单纯形法解决上述工厂
的问题时，可以得出：每天安排生产甲产品 2．36 吨，乙产品 1．45 吨，可得
到最大收入 18180 元。
还有一类问题也可以用线性规划模型来解决。例如有甲、乙、丙、丁 4
个糖果厂，生产同一种水果糖供给 A、B、C、D4 个商店零售。若已知 4 个工
厂的产量，4 个商店的需要量，而且还知道每个工厂运给每个商店 1 吨水果
糖的运费是多少，又叫运输问题，是实际工作中会经常遇到的问题。这些问
题，都可以用线性规划模型来解决。
如何才能赚最多的钱
——整数规划模型
一个汽车队，有甲、乙两种汽车。甲汽车每辆可装体积为 1 立方米的货
物，载重量为 5 吨，可收入 500 元。乙种汽车每辆每次可装体积为 1 立方米
的货物，载重量为 9 吨，可收入 800 元。由于值班司机人数、汽油燃料等条
件的限制，每次车队派车运货体积总计不能超过 6 立方米，载重量不能超过
45 吨。问题是每次安排甲、乙车各多少辆，才能既满足限制条件，又取得最
多的收入？
我们想一想这个问题，会发现两种汽车装载货物的体积、重量与汽车的
数量是成比例关系的，而车队的收入也是与车辆数目成比例关系的。因此，
用线性规划模型可以解决这一问题。应用图解法或单纯形法，可以计算出结
果，每次应派甲种车 2．25 辆，乙种车 3．75 辆，总收入为：
5×2．25＋8×3．75＝41．25（百元）
现在新的问题又来了，这种安排是不可能实行的。2．25 辆甲种车怎么
派？要么是 2 辆、要么是 3 辆，谁也不可能派出不是整数的车。乙种车也是
同样要派出整数。像这种要求得到整数结果的线性规划模型通常被称做整数
规划模型。
可不可以集零为整？如果把小数点后面的第一位数四舍五入，即甲种车
派 2 辆，乙种车派 4 辆，这是不是上面整数规划模型的最优结果呢？通过计
算会发现该结果超过了限制条件：2 辆甲车装载 10 吨，4 辆乙车可装载 36
吨，合计可装载 46 吨，但规定不能超过 45 吨。如果把小数点后的数字舍掉，
就不会超出限制条件了，但这样的结果是不是符合最优要求呢？再来计算一
下，每次甲种车派 2 辆，乙种车派 3 辆，总收入为：
500×2＋800×3＝3400（元）
这种情况下，每次派车运货的体积总量为：
1×2＋1×3＝5（立方米）
每次派车运货的载重量总计为：
5×2＋9×3＝37（吨）
可以看出还有 1 立方米体积和 8 吨载重量没有利用，还可再增加一辆甲
种车，即 3 辆甲种车，这时收益为：
500×3＋800×3＝3900（元）
从而我们知道，四舍五入和去掉小数点后面的尾数化零为整的方法都不
能求出整数规划模型的最优结果。
有人建议将条件允许的派车方案都列举出来，一一进行计算、比较，就
可以找到最优结果。
对于上面汽车队的派车的问题，要计算 25 种方案。如果因素增加，解决
整数规划模型的方案就可能成百上千，不仅计算复杂，光列举这些方案就会
令人头晕眼花。
那该怎么办呢？现在，科学家已找到了一种解决整数规划问题的方法，
叫做“分支定界法”。这种方法首先是找到相对应的线性规划问题的最优结
果，这个结果是整数规划的界限（例如上述汽车队派车问题，相对应的线性
规划的最大收入是 4125 元，整数规划的结果一定不会超过 4125 元）。然后
作出判断并进行计算，如果线性规划求出的结果恰恰是整数，这时可以认为
已找到答案。如果线性规划求出的因素中有非整数结果，如 2．25 辆车，就要
设法分别在限制条件内把各非整数因素化整，求出结果，进行比较，最后找
到整数规划的最优结果。对于上面派车问题，可以找到的结果是，不派甲种
车，派乙种车 5 辆，可以得到最高收入：
5×0＋8×5＝40（百元）
在实际系统中，存在许多因素，它们一定要用整数值来表示，如机器台
数、人数、火车车厢数目、集装箱数、工厂个数、商店家数以及在某地是不
是建工厂，建不建商店、学校、车站等等，这些数值都不能有分数（如建，
可用 1 表示；若不建，用 0 表示）。涉及这些因素的线性规划模型，都要用
整数规划来解决，用分支定界法等方法求出最优结果。
分派问题也是另一类广泛应用的整数规划问题。例如学校周末劳动，有
四项工作（给树木花草浇水、打扫教室、修理桌椅、出黑板报）要分配 4 位
同学去完成。这 4 位同学中，不同的人对不同的工作所用时间不一样。有人
力气大，浇水快；有人写字娴熟，出黑板报花的时间少。安排得好，4 位同
学总计花费的时间就会最少。还有分派不同的工人到不同的车间去工作，不
同的轮船按不同的航线航行，不同的飞机去不同的城市等，都是属于分派问
题。
系统工程的妙用
植树问题
某班长带领 60 位同学上山去值树，主要的工作有 3 项：挖坑、运树苗、
挑水浇树。根据情况得知：用 20 或 20 以上的人挖坑，需要 20 分钟；用 20
或 20 以上的人运树苗，需要 15 分钟；用 20 或 20 以上的人挑水浇树，需 30
分钟。这样，便会有 5 种安排：
第 1 种，可以在一项工作完成以后，再进行第二项工作，最后进行第三
项，这样总计要花 65 分钟时间；
第 2 种是在挖坑的同时派人去运树苗，在完成挖坑工作以后再组织人力
挑水，这样需要 50 分钟；
第 3 种是在挖坑的同时就派人去挑水，在挑完水后再去运树苗，这样需
要 45 分钟；
第 4 种是在挖坑的同时就派人去挑水，在挖完坑后又派人去运树苗，这
样只需花 35 分钟；
第 5 种安排是 3 项工作同时开始，那么，总共只需要 30 分钟就可以完成
任务了。
很显然，在人力、工具等条件都允许的情况下，第 5 种安排最省时间，
其他安排费时间多，会出现“窝工”现象。
同样，对于一个生产汽车的工厂，厂长一定会安排不同的车间（分厂），
分别生产汽车的发动机、轮胎、底盘、外壳、仪表、座椅、车灯、电器等零
部件，最后进行总体装配，一辆辆崭新、漂亮、别致的汽车就会从流水作业
线上徐徐开出来。任何一位厂长都不会安排先生产一种零部件，完成后再生
产第二种，一直到最后一种零部件制造出来后，再去一一组装。这样，无疑
要浪费许多时间，没有生产效率。
建筑队要盖一幢楼房，一定要打地基，运砖瓦石、水泥、钢材等建筑材
料，砌砖，安门窗，装水管和下水道，粉刷墙面等，如果安排不当，就会出
现窝工现象。
生活中也有许多例子，需要人们开动脑筋巧妙安排。你可能听过这样一
个故事，讲的是一个人挑着一担菜，牵着一只羊，带着一条狗过河，河边只
有一小小的船，因船太小，当人不在场时，不能把狗和羊留在一起，因为狗
要咬羊，也不能把羊和菜留在一起，因为羊会把菜吃掉怎知办？这个人运用
他的聪明才智，巧妙安排，把三者安全顺利地带过了河。你知道他是怎样干
的吗？
如果在家里做饭烧菜，你一定会先煮米饭（或蒸馒头），并利用煮饭的
时间去洗菜、切菜，等饭（或馒头）做好了，你的准备工作也做得差不多了，
然后再烧菜，这样可节约不少时间。
当你仔细观察一下周围发生的事情，或者回想一下你的经历，你就会了
解到，生活当中有着许多精明的“管家”——他们能管理好班级，管理好企
业，管理好农业生产。这里介绍的内容，就是用图和网络的方法，解决前面
提到的各种问题，帮助人们统筹安排时间，精打细算，提高工作效率。
著名的哥尼斯堡七桥问题
欧洲有一座城市，叫哥尼斯堡。有一条河流经城区，河中有两个小岛，
共有七座桥将河的两岸和两个小岛联接起来。图中 A、B 表示两岸，C、D 表
示两个小岛，数字 1 至 7 表示七座桥。
有人提出一个问题，能不能从某一地点出发（例如 D 点），通过七座桥
各一次（即不能重复过桥），然后回到出发地（也就是 D 点）？这就是有名
的哥尼斯堡七桥问题。
1736 年，数学家欧拉发表了一篇论文，将上面的问题用下图表示出来。
同样地，图上 A、B 表示两岸，C、D 表示两个小岛，数字 1 至 7 表示七座桥。
图中的点叫顶点，用来表示具体的事物。图中的线叫做边，用来表示事
物之间的某种关系。这种图不是按比例画出的，边长不代表真正距离或其他
数量关系，顶点和边的位置也不与实际位置一一对应。这样，就可以将复杂
的工程系统、运输系统、管理系统等等简化成图，来解决工程任务花费时间
最少、运输距离最短、管理费用最省等最优化问题。
欧拉将哥尼斯堡七桥问题抽象成一个图，将上述过桥问题抽象成一笔画
问题后，他证明，上图中的顶点都只与奇数条边相连接，因此不能将图一笔
画成而不重复任一条边。假设第 4 条桥不是连接 C、D 小岛，而是连接 A、B
两岸，则可用下图表示。可以明显地看出各点均与偶数条边相连接，此图就
可以不重复地一笔画成。
我们再看一下架设电话线的例子。在下图中，要在各单位之间架设电话
线。电话线必须将它们连接，但为了节省线路，两单位之间也可以通过其他
单位接通电话，例如乙村可以通过甲村、汽车站同学校接通电话，因此不必
在乙村与学校间再架设一条电话线。这种简单形式的图就是“树”。
由于每两单位之间架线的长度不同，因此，实际上要求找到所架电线最
短的“树”，按这“树”的样子架线，所花时间最少、也最省钱。
架设电话线的“树”
供应问题
请看供水系统管路图，某村供水站要向新开垦的土地送水浇地，供水管
路要经过东南西北 4 片地区，每段管线最大供水能力分别表示在线中边上，
如供水站向南片土地每分钟最多能供应 5 立方米水，再由南片向东片最多每
分钟供应 2 立方米水等等。而这种有发点（如供水站）和收点（如新开垦地）
的有方向的图（从发点开始到收点为止）就组成了一个网络。研究供水站通
过这个网络每分钟最多能供给新开地多少立方米的水，这就是网络最大流问
题。
古代战争中就非常重视供应问题，“兵马未到，粮草先行”，说的就是
这个问题。现代化的战争供应问题更加复杂。因为现代战争，是对多兵种、
高技术、快速反应的全面考验，在一次战役之前，准备工作显得十分重要、
紧迫。因此，战前往往要研究从后方向前线调运各种武器弹药，集结各地作
战兵员和医疗、后勤保障、军事技术等各类人员，储备燃料、食品、饮用水、
药品等等问题。
还有许多系统都需要研究最大质量问题。如春节期间，铁路部门要研究
铁路网络最大客运能力，以便安排列车将旅客送回家过年。发电厂（还有水
电站）要研究电网最大送电能力，以满足工厂、农村和人民生活用电的需要。
油田和炼油厂要研究输油管网络的最大输油能力。电话局要研究电话网的最
大通话容量，等等。
邮路捷径
当你收到邮递员送来的报纸、信件的时候，你一定很高兴能从报纸上了
解到国内外大事，从信中知晓亲戚朋友的消息。但不知道你是否注意到，邮
递员每次送信都是沿着相同的街道、相同的方向送信。你会说，这些绿衣天
使熟悉这些街道，甚至熟悉许多家庭，他们习惯于沿同样的路线送信，不管
酷暑寒冬、刮风下雨，日复一日，年复一年。如何为他们选一条路程最短的
“邮路”，使他们能相对轻松地完成他们的工作呢？这个问题是 1962 年由我
国数学家管梅谷教授提出的，国际上因此而称为中国邮递员问题。
我们看一看下图所表示的一个简单的街区路线图，数字表示街道的长度
（米）。那么，假设邮递员从邮局出发，沿什么路线送完信件返回邮局，所
走的路最少呢？
首先，要送完信、报等邮件，邮递员必须要经过每条街道至少一次。如
果他能够每条街道只走一次而不重复，这样的路线当然就是最短路线。但在
街道示意图上可以看出有 4 个交叉路口均与三条道路相连接（奇数条边），
因此，这个图所表示的街道必然会有重复经过的路线。我们通过添加重复路
线，使那些与奇数条边相连的点均变成与偶数条边相连。
然后，检查每一个回路，使重复路线的总长度不大于该回路总长度的一
半。例如下图中，添加了 BC、CD、FG、GH 四条重复路线（在图中以弧线来表
示）。检查回路 BCDE，回路总长度是 850 米，而重复边总长是 400 米，符合
要求。再看 EFGH 回路，回路总长度是 750 米，重复边总长度是 350 米，也符
合要求。这样，图上所有的点均与偶数条边相连接，每条原街道或者没添重
复边，或者只添一条重复边。因此，上图就是邮递员所走的最小距离的“邮
路”。你不妨试试看，如果不是这样的路线，其他路线均要走更长的路程。
泡茶与导弹
50 年代末期，在美国海军研制“北极星”潜艇导弹过程中，接受任务的
公司、研究单位和大学共有 11000 多个。为了完成这项�
