六年级奥林匹克数学基础教程 29 运筹学初步(三)

六年级奥林匹克数学基础教程29运筹学初步(三)小学数学奥数基础教程运筹学初步（二）本讲主要讲统筹安排问题、排队问题、最短路线问题、场地设置问题等。这些都是人们日常生活、工作中经常碰到的问题，怎样才能把它们安排得更合理，多快好省地办事，就是这讲涉及的问题。当然，限于现有的知识水平，我们仅仅是初步探索一下。1.统筹安排问题例1星期天妈妈要做好多事情。擦玻璃要20分钟，收拾厨房要15分钟，洗脏衣服的领子、袖口要10分钟，打开全自动洗衣机洗衣服要40分钟，晾衣服要10分钟。妈妈干完所有这些事情最少用多长时间？分析与解：如果按照题目告诉的几件事，一件一件去做，要95分钟。要想节约时间，就要想想在哪段时间里闲着，能否利用闲着的时间做其它事。最合理的安排是：先洗脏衣服的领子和袖口，接着打开全自动洗衣机洗衣服，在洗衣服的40分钟内擦玻璃和收拾厨房，最后晾衣服，共需60分钟（见下图）。例1告诉我们，当有许多事要做时，科学地安排好先后顺序，就能用较少的时间完成较多的事情。2.排队问题例2理发室里有甲、乙两位理发师，同时来了五位顾客，根据他们所要理的发型，分别需要10，12，15，20和24分钟。怎样安排他们的理发顺序，才能使这五人理发和等候所用时间的总和最少？最少要用多少时间？分析与解：一人理发时，其他人需等待，为使总的等待时间尽量短，应让理发所需时间少的人先理。甲先给需10分钟的人理发，然后15分钟的，最后24分钟的；乙先给需12分钟的人理发，然后20分钟的。甲给需10分钟的人理发时，有2人等待，占用三人的时间和为（10×3）分；然后，甲给需15分钟的人理发，有1人等待，占用两人的时间和为（15×2）分；最后，甲给需24分钟的人理发，无人等待。甲理发的三个人，共用（10×3＋15×2＋24）分，乙理发的两个人，共用（12×2＋20）分。总的占用时间为（10×3＋15×2＋24）＋（12×2＋20）=128（分）。按照上面的安排，从第一人开始理发到五个人全部理完，用了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（分），经过组合，一人修需18，17和20分钟的三台，另一人修需30和25分钟的两台，修复时间最短，为55分钟。上面只考虑修复时间，没考虑经济损失，要使经济损失少，就要使总停产时间尽量短，显然应先修理修复时间短的。第一人按需17，18，20分钟的顺序修理，第2人按需25，30分钟的顺序修理，经济损失为5×［（17×3＋18×2＋20）＋（25×2＋30）］=935（元）。3.最短路线问题例4右图是一张道路示意图，每段路上的数字表示小明走这段路所需要的时间（单位：分）。小明从A到B最快要几分钟？分析与解：我们采用分析排除法，将道路图逐步简化。从A到O有两条路，A→C→O用6分钟，A→F→O用7分钟，排除后者，可将FO抹去，但AF不能抹去，因为从A到B还有其它路线经过AF，简化为左下图。从A到E还剩两条路，A→C→G→E用12分钟，A→C→O→E用10分钟，排除前者，可将CG，GE抹去，简化为右上图。从A到D还剩两条路，A→C→O→D用12分钟，A→H→D用13分钟，排除后者，可将AH，HD抹去，简化为左下图。从A到B还剩两条路，A→C→O→E→B用17分钟，A→C→O→D→B用16分钟，排除前者，可将OE，EB抹去，简化为右上图。小明按A→C→O→D→B走最快，用16分钟。4.场地设置问题例5下图是A，B，C，D，E五个村之间的道路示意图，○中数字是各村要上学的学生人数，道路上的数表示两村之间的距离（单位：千米）。现在要在五村之中选一个村建立一所小学。为使所有学生到学校的总距离最短，试确定最合理的方案。分析与解：我们采用比较学校设在相邻两村的差别的方法。例如比较A和C，若设在A村，则在C村一侧将集结20＋20＋35＋50=125（人），这些人都要走AC这段路；若设在C村，则只有40人走AC这段路。对这两种方案，走其余各段路的人数完全相同，所以设在C村比设在A村好。从上面比较A和C的过程可以看出，场地设置问题不必考虑场地之间的距离，只需比较两个场地集结的人数多少，哪个场地集结的人数越多，就应设在哪。同理，经比较得到C比B好，D比E好。最后比较C和D。若设在C村，则在D村一侧将集结35＋50=85（人）；若设在D村，则在C村一侧将集结40＋20＋20=80（人）。因为在D村集结的人数比C村多，所以设在D村比C村好。经过上面的比较，最合理的方案是设在D村。不难发现，本题的解法与第27讲例2的解法十分类似。