《第29讲 运筹学初步》由会员分享，可在线阅读，更多相关《第29讲 运筹学初步（10页珍藏版）》请在金锄头文库上搜索。
1、第29讲 运筹学初步（三）本讲主要讲统筹安排问题、排队问题、最短路线问题、场地设置 问题等。这些都是人们日常生活、工作中经常碰到的问题，怎样才能 把它们安排得更合理，多快好省地办事，就是这讲涉及的问题。当然， 限于现有的知识水平，我们仅仅是初步探索一下。1. 统筹安排问题例1星期天妈妈要做好多事情。擦玻璃要20分钟，收拾厨房要15 分钟，洗脏衣服的领子、袖口要10分钟，打开全自动洗衣机洗衣服要 40分钟，晾衣服要10分钟。妈妈干完所有这些事情最少用多长时间？分析与解：如果按照题目告诉的几件事，一件一件去做，要95 分钟。要想节约时间，就要想想在哪段时间里闲着，能否利用闲着的 时间做其它事。最合
2、理的安排是：先洗脏衣服的领子和袖口，接着打 开全自动洗衣机洗衣服，在洗衣服的40分钟内擦玻璃和收拾厨房，最 后晾衣服，共需60分钟（见下图）。洗额、社.洗衣机洗衣限晾衣服10 40-10_*收抬厨房20. T例1告诉我们，当有许多事要做时，科学地安排好先后顺序，就 能用较少的时间完成较多的事情。2排队问题例2理发室里有甲、乙两位理发师，同时来了五位顾客，根据他 们所要理的发型，分别需要10，12, 15, 20和24分钟。怎样安排他们 的理发顺序，才能使这五人理发和等候所用时间的总和最少？最少要 用多少时间？分析与解：一人理发时，其他人需等待，为使总的等待时间尽量 短，应让理发所需时间少的人先
3、理。甲先给需10分钟的人理发，然后 15分钟的，最后24分钟的；乙先给需12分钟的人理发，然后20分钟的。 甲给需10分钟的人理发时，有2人等待，占用三人的时间和为（10X3） 分；然后，甲给需15分钟的人理发，有1人等待，占用两人的时间 和为（15X2）分；最后，甲给需24分钟的人理发，无人等待。甲理发的三个人，共用（10X3 + 15X2+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) + (25X2 + 30) =935 (元)。3.最短路线问题例4右图是一张道路示意图，每段路上的数字表示小明走这段路 所需要的时间(单位：分)。小明从A到B最快要几分钟？分析与解：我们采用分析排除法，将道路图逐步简化。从A到0有两条路，0用6分钟，A-Ff 0用7分钟，排除 后者，可将F0抹去，但AF不
6、能抹去，因为从A到B还有其它路线经 过AF,简化为左下图。从A到E还剩两条路，AfCGfE用12分钟，AfCOfE用10分钟，排除前者，可将CG, GE抹去，简化为右上图。从A到D还剩两条路,A-CfO-D用12分钟,A-H-D用13分钟,排除后者，可将AH, HD抹去，简化为左下图。从A到B还剩两条路，ACOEB用17分钟，ACODB 用16分钟，排除前者，可将OE, EB抹去，简化为右上图。小明按A-C-O-D-B走最快，用16分钟。4.场地设置问题例5下图是A, B, C, D, E五个村之间的道路示意图，O中数字 是各村要上学的学生人数，道路上的数表示两村之间的距离（单位： 千米）。现
7、在要在五村之中选一个村建立一所小学。为使所有学生到 学校的总距离最短，试确定最合理的方案。分析与解：我们采用比较学校设在相邻两村的差别的方法。例如 比较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村一侧将集结
8、35+ 50= 85 （人）若设在D村， 则在C村一侧将集结40 + 20 + 20=80 （人）因为在D村集结的人数 比C村多，所以设在D村比C村好。经过上面的比较，最合理的方案是设在D村。不难发现，本题的解法与第27讲例2的解法十分类似。例6某天然气站要安装天然气管道通往位于一条环形线上的A G七个居民区，每两个居民区间的距离如下图所示（单位：千米）。 管道有粗细两种规格，粗管可供所有7个居民区用气，每千米8000元, 细管只能供1个居民区用气，每千米3000元。粗、细管的转接处必须 在居民区中。问：应怎样搭配使用这两种管道，才能使费用最省？分析与解：在长度相同的情况下，每根粗管的费用大于
9、2根细管 的费用，小于3根细管的费用，所以安装管道时，只要后面需要供气 的居民区多于2个，这一段就应选用粗管。从天然气站开始，分成顺 时针与逆时针两条线路安装，因为每条线路的后面至多有两个居民区 由细管通达，共有7个居民区，所以至少有3个居民区由粗管通达。因 为长度相同时，2根或1根细管的费用都低于1根粗管的费用，所以由 粗管通达的几个居民区的距离越短越好，而顺时针与逆时针两条线路 未衔接部份的距离越长越好。经过计算比较，得到最佳方案：（1）天然气站经G，F，E到D安装粗管，D到C安装2根细管，C到B安装1根细管；（2）天然气站到A安装1根细管。此时总费用最少，为8000X （3+12+8+6
10、） +3000X2X5+3000X （9+10） =319000 （元）练习291. 早饭前妈妈要干好多的事：烧开水要15分钟，擦桌椅要8分钟, 准备暖瓶要1分钟，灌开水要2分钟，买油条要10分钟，煮牛奶要7分 钟。如果灶具上只有一个火，那么全部做完这些工作最少需要多少时 间？怎样安排？2. 甲、乙、丙三名车工准备在同样效率的3个车床上加工七个零 件，各零件加工所需时间分别为4, 5，6, 6, 8, 9, 9分钟，三人同 时开始工作。问：加工完七个零件最少需多长时间？3. 车间里有5台车床同时出现故障。已知第一台至第五台修复的 时间依次为15, 8, 29, 7, 10分钟，每台车床停产一分
11、钟造成经济损 失5元。问：（1）如果只有一名修理工，那么怎样安排修理顺序才能 使经济损失最少？ （2）如果有两名修理工，那么修复时间最少需多少分钟?4. 下页左上图是一张道路图，每条路上的数是小王走这段路所需的时间（单位：分）。小王从A到B最快需要几分钟？5东升乡有8个行政村。分布如右上图所示，点表示村庄，线表 示道路，数字表示道路的长（单位：千米）。现在这个乡要建立有线 广播网，沿道路架设电线。问：电线至少要架多长？6.有七个村庄Al，A2，A7分布在公路两侧（见下图），由一 些小路与公路相连，要在公路上设一个汽车站，要使汽车站到各村庄 的距离和最小，车站应设在哪里？7有一个水塔要供应某条公路旁的AF六个居民点用水（见下 图，单位：千米），要安装水管，有粗细两种水管，粗管足够供应6 个居民点用水，细管只能供应1个居民点用水，粗管每千米要7000元, 细管每千米要2000元，粗细管怎样互相搭配，才能使费用最省？费用 应是多少？.J 30 水塔A B C D E F
