小学奥数最短路线问题(有答案)

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

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

3、，为使总的等待时间尽量短， 应让理发所需时间少的人先理。甲先给需10分钟的人理发，然后15分钟 的，最后24分钟的；乙先给需12分钟的人理发，然后20分钟的。甲给 需10分钟的人理发时，有2人等待，占用三人的时间和为（10X 3）分； 然后，甲给需15分钟的人理发，有1人等待，占用两人的时间和为（15 X2）分；最后，甲给需24分钟的人理发，无人等待。甲理发的三个人，共用（10X3+15X 2+24）分，乙理发的两个人， 共用（12X2+20）分。总的占用时间为（10X3+ 15X2 + 24） + （ 12X2 + 20） =128 （分）。按照上面的安排，从第一人开始理发到五个人全部理完，

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

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

6、-。用6分钟，A- F一。用7分钟，排除后 者，可将FO抹去，但AF不能抹去，因为从A到B还有其它路线经过AF, 简化为左下图。从A到E还剩两条路，A-C- GH E用12分钟，A- C- Of E用10分 钟，排除前者，可将CG GE抹去，简化为右上图。从A到D还剩两条路，A-C-Of D用12分钟，A- HH D用13分钟, 排除后者，可将AH HD抹去，简化为左下图。从A到B还剩两条路，2CE B用17分钟，A- CA 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的过程可以看出，场地设置问题不必考虑场地之间 的距离，只需比较两个场地集结的人数多少，哪个场地集结的人数越多， 就应设在哪。

8、同理，经比较得到C比B好，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到C安装2根细管，C 到B安

10、装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分钟，三人同时开始工 作。问：加工完七个零件最少需多长时间？3 .车间里有5台车床同时出现故

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

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