小学奥数最短路线问题

1、小学六年级奥数教案运筹学初步本讲主要讲统筹安排问题、 排队问题、 最短路线问题、 场地设置问题等。 这些都是人们日常生活、 工作中经常碰到的问题， 怎样才能把它们安排得更合理，多快好省地办事，就是这讲涉及的问题。当然，限于现有的知识水平，我们仅仅是初步探索一下。1 .统筹安排问题例 1 星期天妈妈要做好多事情。擦玻璃要20 分钟，收拾厨房要15分钟，洗脏衣服的领子、袖口要10 分钟，打开全自动洗衣机洗衣服要40分钟，晾衣服要10 分钟。妈妈干完所有这些事情最少用多长时间？分析与解： 如果按照题目告诉的几件事，一件一件去做，要 95 分钟。要想节约时间， 就要想想在哪段时间里闲着，能否利用闲着的

2、时间做其它事。 最合理的安排是： 先洗脏衣服的领子和袖口， 接着打开全自动洗衣机洗衣服，在洗衣服的 40 分钟内擦玻璃和收拾厨房，最后晾衣服，共需60分钟（见下图）。例 1 告诉我们，当有许多事要做时，科学地安排好先后顺序，就能用较少的时间完成较多的事情。2. 排队问题例 2 理发室里有甲、乙两位理发师，同时来了五位顾客，根据他们所要理的发型，分别需要10， 12， 15， 20 和 24 分钟。怎样安排他们的理发顺序， 才能使这五人理发和等候所用时间的总和最少？最少要用多少时间？分析与解： 一人理发时，其他人需等待，为使总的等待时间尽量短，应让理发所需时间少的人先理。 甲先给需 10 分钟的

3、人理发， 然后 15 分钟的，最后 24 分钟的；乙先给需 12 分钟的人理发，然后 20 分钟的。甲给需10分钟的人理发时，有2人等待，占用三人的时间和为（10X 3）分；然后，甲给需 15 分钟的人理发，有1 人等待，占用两人的时间和为（ 15X2）分；最后，甲给需24分钟的人理发，无人等待。甲理发的三个人，共用（10X3+15X 2+24）分，乙理发的两个人， 共用（12X2+20）分。总的占用时间为(10X3+ 15X2 + 24) + ( 12X2 + 20) =128 (分)按照上面的安排，从第一人开始理发到五个人全部理完，用了 10 15 + 24= 49 （分）。如果题目中再要

4、求从第一人开始理发到五人全部理完的时间最短，那么做个调整，甲依次给需 10， 12， 20 分钟的人理发，乙依次给需 15， 24 分钟的人理发，总的占用时间仍是128 分钟，而五人全部理完所用时间为10+ 12+20= 42 （分）。例 3 车间里有五台车床同时出现故障，已知第一台到第五台修复时间依次为 18， 30， 17， 25， 20 分钟，每台车床停产一分钟造成经济损失5 元。现有两名工作效率相同的修理工，怎样安排才能使得修复的时间最短且经济损失最少？分析与解：因为（ 18+30+ 17+ 25+20） + 2=55 （分），经过组合，一人修需 18， 17和 20分钟的三台， 另一

5、人修需30和 25分钟的两台， 修复时间最短，为 55 分钟。上面只考虑修复时间， 没考虑经济损失， 要使经济损失少， 就要使总停产时间尽量短，显然应先修理修复时间短的。第一人按需 17， 18， 20分钟的顺序修理，第 2 人按需25， 30 分钟的顺序修理，经济损失为5X （17X3+18X2+20）+（ 25X 2+30） =935 （元）。3. 最短路线问题例 4 右图是一张道路示意图，每段路上的数字表示小明走这段路所需要的时间（单位：分）。小明从 A到B最快要几分钟？分析与解： 我们采用分析排除法，将道路图逐步简化。从A到。有两条路，ZC-。用6分钟，2F-O用7分钟，排除后 者，可

6、将FO抹去，但AF不能抹去，因为从A到B还有其它路线经过AF, 简化为左下图。从A到E还剩两条路，A- C- GH E用12分钟，A- C- O- E用10分 钟，排除前者，可将CG GE抹去，简化为右上图。从A到D还剩两条路，A-C-O- D用12分钟，Q HH D用13分钟, 排除后者，可将AH HD抹去，简化为左下图。从A到B还剩两条路，2C- M E- B用17分钟，A- C- M A B 用16分钟，排除前者，可将OE EB抹去，简化为右上图。小明按A-C-O- AB走最快，用16分钟。4. 场地设置问题例5下图是A, B, C, D, E五个村之间的道路示意图，。中数字是 各村要上

7、学的学生人数， 道路上的数表示两村之间的距离 （单位： 千米） 现在要在五村之中选一个村建立一所小学。 为使所有学生到学校的总距离 最短，试确定最合理的方案。分析与解： 我们采用比较学校设在相邻两村的差别的方法。 例如比较A和C,若设在A村，则在C村一侧将集结20 +20+35+ 50=125（人）， 这些人都要走AC这段路；若设在C村，则只有40人走AC这段路。对这 两种方案，走其余各段路的人数完全相同，所以设在 C村比设在A村好。从上面比较A和C的过程可以看出，场地设置问题不必考虑场地之间 的距离，只需比较两个场地集结的人数多少，哪个场地集结的人数越多， 就应设在哪。同理，经比较得到C比B

8、好，D比E好。最后比较C和D。若设在C 村，则在D村一侧将集结35 + 50= 85 （人）；若设在D村，则在C村 一侧将集结40 +20+ 20=80 （人）。因为在D村集结的人数比C村多，所 以设在D村比C村好。经过上面的比较，最合理的方案是设在 D村。不难发现，本题的解法与第 27 讲例 2 的解法十分类似。例6某天然气站要安装天然气管道通往位于一条环形线上的AG七个居民区，每两个居民区间的距离如下图所示（单位：千米）。管道有粗细两种规格，粗管可供所有7 个居民区用气，每千米8000 元，细管只能供 1 个居民区用气， 每千米 3000元。 粗、 细管的转接处必须在居民区中。问：应怎样搭

9、配使用这两种管道，才能使费用最省？分析与解： 在长度相同的情况下， 每根粗管的费用大于2 根细管的费用， 小于 3 根细管的费用， 所以安装管道时， 只要后面需要供气的居民区多于 2 个， 这一段就应选用粗管。 从天然气站开始， 分成顺时针与逆时针两条线路安装， 因为每条线路的后面至多有两个居民区由细管通达， 共有7 个居民区，所以至少有3 个居民区由粗管通达。因为长度相同时， 2 根或 1 根细管的费用都低于1 根粗管的费用， 所以由粗管通达的几个居民区的距离越短越好，而顺时针与逆时针两条线路未衔接部份的距离越长越好。经过计算比较，得到最佳方案：（1）天然气站经G, F, E到D安装粗管，D

10、到C安装2根细管，C 到 B 安装 1 根细管；（ 2）天然气站到A 安装 1 根细管。此时总费用最少，为8000X （3+12+8+6）+3000X2X5+3000X （9+10） =319000 （元）。练习 291. 早饭前妈妈要干好多的事：烧开水要 15分钟，擦桌椅要8 分钟，准备暖瓶要1 分钟，灌开水要2 分钟，买油条要10 分钟，煮牛奶要7 分钟。 如果灶具上只有一个火， 那么全部做完这些工作最少需要多少时间？怎样安排？2. 甲、乙、丙三名车工准备在同样效率的 3 个车床上加工七个零件，各零件加工所需时间分别为 4， 5， 6， 6， 8， 9， 9 分钟，三人同时开始工作。问：加

11、工完七个零件最少需多长时间？3. 车间里有 5 台车床同时出现故障。 已知第一台至第五台修复的时间依次为 15， 8， 29， 7， 10 分钟，每台车床停产一分钟造成经济损失5 元。问：（ 1）如果只有一名修理工，那么怎样安排修理顺序才能使经济损失最少？（2）如果有两名修理工，那么修复时间最少需多少分钟？4. 下页左上图是一张道路图， 每条路上的数是小王走这段路所需的时问（单位：分）。小王从 A到B,最快需要几分钟？5. 东升乡有 8 个行政村。 分布如右上图所示， 点表示村庄， 线表示道路，数字表示道路的长（单位：千米）。现在这个乡要建立有线广播网，沿道路架设电线。问：电线至少要架多长？6

12、. 有七个村庄A1, A2,，A7分布在公路两侧（见下图），由一些小路与公路相连， 要在公路上设一个汽车站， 要使汽车站到各村庄的距离和最小，车站应设在哪里？7. 有一个水塔要供应某条公路旁的AF六个居民点用水（见下图，单位：千米），要安装水管，有粗细两种水管，粗管足够供应6 个居民点用水，细管只能供应1 个居民点用水，粗管每千米要7000 元，细管每千米要 2000 元，粗细管怎样互相搭配，才能使费用最省？费用应是多少？答案与提示练习 29分。提示：先烧开水后煮牛奶共需22 分，其它事情可以在这个期间做，顺序是买油条，准备暖瓶，擦桌椅（水开时暂停，煮上奶），灌开水，继续擦桌椅。分。3. （ 1） 780元；（2） 36分。提示：（ 1）按修复时间需7， 8， 10， 15， 29 分的顺序修理；（ 2）一人修需 7 分和 29 分的，另一人修需8， 10