第11讲---简单的统筹规划问题

第11讲简单的统筹规划问题专题简析：最优化概念反映了人类实践活动中十分普遍的现象，即要在尽可能节省人力、物力和时间的前提下，努力争取获得在允许范围内的最佳效益．因此，最优化问题成为现代应用数学的一个重要研究对象，它在生产、科学研究以及日常生活中都有广泛的应用．作为数学爱好者，接触一些简单的实际问题，了解一些优化的思想是十分有益的．例1、妈妈让小明给客人烧水沏茶．洗开水壶要用1分钟，烧开水要用15分钟．洗茶壶要用1分钟，洗茶杯要用1分钟，拿茶叶要用2分钟．小明估算了一下，完成这些工作要20分钟．为了使客人早点喝上茶，按你认为最合理的安排，多少分钟就能沏茶了？分析：烧水沏茶的情况是：开水要烧，开水壶要洗，茶壶茶杯要洗，茶叶要取．怎样安排工作程序最省时间呢？办法甲：洗好开水壶，灌上凉水，放在火上，在等待水开的时候，洗茶杯，拿茶叶，等水开了，沏茶喝．办法乙：先做好一切准备工作，洗开水壶，洗壶杯，拿茶叶，灌水烧水，坐等水开了沏茶喝．办法丙：洗开水壶，灌上凉水，放在火上坐待水开，开了之后急急忙忙找茶叶，洗壶杯，沏茶喝．谁都能一眼看出第一种办法好，因为后两种办法都“窝了工”．开水壶不洗，不能烧开水，固为洗开水壶是烧开水的先决条件，没开水、没茶叶、不洗壶杯，我们不能沏茶，因而这些又是沏茶的先决条件．它们的相互关系可以用下图的箭头图来显示．箭杆上的数字表示完成这一工作所需的时间，例如→表示从把水放在炉上到水开的时间是15分钟．从图上可以一眼看出，办法甲总共要16分钟，而办法乙、丙需20分钟．洗壶杯、拿茶叶没有什么先后关系，而且是由同一个人来做，因此可以将上图合并成下图．解：先洗开水壶用1分钟，接着烧开水用15分钟，在等待水开的过程中，同时洗壶杯、拿茶叶，水开了就沏茶，总共用了16分钟．又因为烧开水的15分钟不能减少，烧水前必须用1分钟洗开水壶，所以用16分钟是最少的．说明：本题涉及到的统筹方法，是生产、建设、工程和企业管理中合理安排工作的一种科学方法，它对于进行合理调度、加快工作进展，提高工作效率，保证工作质量是十分有效的．随堂练习：妈妈开始做饭，切菜3分钟，从冰箱取肉并解冻5分钟，切肉4分钟，倒油烧油3分钟，炒菜7分钟，你给妈妈安排一个合理的顺序，节省时间。并计算使用你安排的顺序，共需用多少分钟？例2．用一只平底锅煎饼，每次能同时放两个饼．如果煎一个饼需要4分钟（假定正、反面各需2分钟），问煎9个饼至少需要几分钟？随堂练习：用一只平底锅煎饼，每次能同时放两个饼．如果煎一个饼需要4分钟（假定正、反面各需1分钟），问煎6个饼至少需要几分钟？例35个人各拿一个水桶在自来水龙头前等候打水，他们打水所需的时间分别是1分钟、2分钟、3分钟、4分钟和5分钟．如果只有一个水龙头，试问怎样适当安排他们的打水顺序，才能使每个人排队和打水时间的总和最小？并求出最小值．分析：5个人排队一共有5×4×3×2×1=120种顺序，把所有情形的时间总和都计算出来，就太繁琐了．凭直觉，应该把打水时间少的人排在前面所费的总时间会省些．考虑用“逐步调整”法来严格求解．解：首先证明要使所费总时间最省，应该把打水时间需1分钟的人排在第一位置．假如第一位置的人打水时间要a分钟（其中2≤a≤5），而打水需1分钟的人排在第b位（其中2≤b≤5）．我们将这两个人位置交换，其他三人位置不变动．这样调整以后第b位后面的人每人排队打水所费的时间与调整前相同，并且前b个人每人打水所费时间也未受影响，但是第二位至第b位的人排队等候的时间都减少了（a-1）分钟，这说明调整后五个人排队和打水时间的总和减少了．换言之，把打水需1分钟的人排在第一位置所费总时间最省．其次，根据同样道理，再将打水需2分钟的人调整到第二位置；将打水需3、4、5分钟的人逐次调整到第三、四、五位．所以将五人按照打水所需时间由少到多的顺序排队，所费时间最省．这样得出5人排队和打水时间总和的最小值是1×5+2×4+3×3+4×2+5×1=35（分钟）．随堂练习：三车货物同时到达仓库门口，A车货物卸完需要20分钟，B车货物卸完需要10分钟，C货物卸完需要30分钟，只能一车一车卸货，怎么安排顺序，才能使三辆货车等候时间的总和最少？例4有157吨货物要从甲地运往乙地，大卡车的载重量是5吨，小卡车的载重量是2吨，大卡车与小卡车每车次的耗油量分别是10升与5升．问如何选派车辆才能使运输耗油量最少？这时共需用油多少升？解：依题意，大卡车每吨耗油量为10÷5=2（公升）；小卡车每吨耗油量为5÷2=2.5（公升）．为了节省汽油应尽量选派大卡车运货，又由于157=5×31+2，因此，最优调运方案是：选派31车次大卡车及1车次小卡车即可将货物全部运完，且这时耗油量最少，只需用油10×31+5×1=315（公升）随堂练习：有137吨货物要从甲地运往乙地，大卡车的载重量是5吨，小卡车的载重量是2吨，大卡车与小卡车每车次的耗油量分别是10升和5升，问如何选派车辆才能使运输耗油量最少？这时共需耗油多少升？【分析】：依题意，大卡车每吨耗油量为10÷5=2(公升)；小卡车每吨耗油量为5÷2=2.5(公升)。为了节省汽油应尽量选派大卡车运货，又由于137=5×27+2，因此，最优调运方案是：选派27车次大卡车及1车次小卡车即可将货物全部运完，且这时耗油量最少，只需用油10×27+5×1=275(公升)课堂训练：1、小明、小华、小强同时去卫生室找张大夫治病．小明打针要5分钟．小华换纱布要3分钟，小强点眼药水要1分钟．问张大夫如何安排治病次序，才能使他们耽误上课的时间总和最少？并求出这个时间．2、烧水沏茶时，洗水壶要用1分钟，烧开水要用10分钟，洗茶壶要用2分钟，洗茶杯用2分钟，拿茶叶要用1分钟，如何安排才能尽早喝上茶。【分析】：先洗水壶然后烧开水，在烧水的时候去洗茶壶、洗茶杯、拿茶叶。共需要1+10=11分钟。3、用一只平底锅烙饼，锅上只能放两个饼，烙熟饼的一面需要2分钟，两面共需4分钟，现在需要烙熟三个饼，最少需要几分钟？【分析】：一般的做法是先同时烙两张饼，需要4分钟，之后再烙第三张饼，还要用4分钟，共需8分钟，但我们注意到，在单独烙第三张饼的时候，另外一个烙饼的位置是空的，这说明可能浪费了时间，怎么解决这个问题呢？我们可以先烙第一、二两张饼的第一面，2分钟后，拿下第一张饼，放上第三张饼，并给第二张饼翻面，再过两分钟，第二张饼烙好了，这时取下第二张饼，并将第三张饼翻过来，同时把第一张饼未烙的一面放上。两分钟后，第一张和第三张饼也烙好了，整个过程用了6分钟。4、甲、乙、丙、丁四人同时到一个小水龙头处用水，甲洗拖布需要3分钟，乙洗抹布需要2分钟，丙用桶接水需要1分钟，丁洗衣服需要10分钟，怎样安排四人的用水顺序，才能使他们所花的总时间最少，并求出这个总时间。【分析】：所花的总时间是指这四人各自所用时间与等待时间的总和，由于各自用水时间是固定的，所以只能想办法减少等待的时间，即应该安排用水时间少的人先用。解：应按丙，乙，甲，丁顺序用水。丙等待时间为0，用水时间1分钟，总计1分钟乙等待时间为丙用水时间1分钟，乙用水时间2分钟，总计3分钟甲等待时间为丙和乙用水时间3分钟，甲用水时间3分钟，总计6分钟丁等待时间为丙、乙和甲用水时间共6分钟，丁用水时间10分钟，总计16分钟，总时间为1＋3＋6＋16＝26分钟。【试题】5、甲、乙、丙、丁四个人过桥，分别需要1分钟，2分钟，5分钟，10分钟。因为天黑，必须借助于手电筒过桥，可是他们总共只有一个手电筒，并且桥的载重能力有限，最多只能承受两个人的重量，也就是说，每次最多过两个人。现在希望可以用最短的时间过桥，怎样才能做到最短呢？你来帮他们安排一下吧。最短时间是多少分钟呢？【分析】：大家都很容易想到，让甲、乙搭配，丙、丁搭配应该比较节省时间。而他们只有一个手电筒，每次又只能过两个人，所以每次过桥后，还得有一个人返回送手电筒。为了节省时间，肯定是尽可能让速度快的人承担往返送手电筒的任务。那么就应该让甲和乙先过桥，用时2分钟，再由甲返回送手电筒，需要1分钟，然后丙、丁搭配过桥，用时10分钟。接下来乙返回，送手电筒，用时2分钟，再和甲一起过桥，又用时2分钟。所以花费的总时间为：2＋1＋10＋2＋2＝17分钟。解：2＋1＋10＋2＋2＝17分钟课后作业:1、小虎早晨要完成这样几件事：烧一壶开水需要10分钟，把开水灌进热水瓶需要2分钟，取奶需要5分钟，整理书包需要4分钟。他完成这几件事最少需要多少分钟？2、小强给客人沏茶，烧开水需要12分钟，洗茶杯要2分钟，买茶叶要8分钟，放茶叶泡茶要1分钟。为了让客人早点喝上茶，你认为最合理的安排，多少分钟就可以了？3、在早晨起床后的1小时内，小欣要完成以下事情：叠被3分钟，洗脸刷牙8分钟，读外语30分钟，吃早餐10分钟，收碗擦桌5分钟，收听广播30分钟。最少需要多少分钟？4、小明骑在牛背上赶牛过河，共有甲乙丙丁四头牛，甲牛过河需1分钟，乙牛需2分钟，丙牛需5分钟，丁牛需6分钟，每次只能骑一头牛，赶一头牛过河。【分析】：要使过河时间最少，应抓住以下两点：(1)同时过河的两头牛过河时间差要尽可能小(2)过河后应骑用时最少的牛回来。解：小明骑在甲牛背上赶乙牛过河后，再骑甲牛返回，用时2＋1＝3分钟然后骑在丙牛背上赶丁牛过河后，再骑乙牛返回，用时6＋2＝8分钟最后骑在甲牛背上赶乙牛过河，不用返回，用时2分钟。总共用时(2＋1)＋(6＋2)＋2＝13分钟。