奥数：最优化问题

第十四讲 最优化问题 我国著名大数学家华罗庚爷爷曾积极推广、普及的“统筹方法”和“优选法“华罗庚曾利用数学知识创造许多优化解决问题的方法。我们所破到的最优化问题，是通过适当规划安排，在许多方案中，寻找一个最合理、最节约、最省事的方案。 典型例题l 例1 妈妈让小明给客人烧开水切茶，洗开水壶要用1分钟，烧开水要用15分钟，洗茶壶要用2分钟，洗茶杯要用1分钟，拿茶叶要用2分钟。小明估算了一下，完成这些工作要花20分钟。为了使客人早点和上茶，按你认为最合理的安排，多少分钟就能切茶了？ 先决条件。这1分钟不能省，而洗茶壶、洗开水杯、拿茶叶等切茶的准备工作都可以放在烧开水的15分钟里完成。 解 最省时间的安排是：纤细开水壶（用1分钟），按着烧开水（用15分钟），在等待水烧开的时间里，可以洗茶壶、洗茶杯、拿茶叶，水开了就切茶。这样一共用了16分钟。l 例2 在一条公路上，每隔100其千米有一个仓库，共有5个仓库，一号仓库存有10吨货物，二号仓库存有20吨货物，五号仓库存有40吨货物，其余两仓库是空的。现在想把所有的货集中存在同一仓库里，如果每吨货物运输1千米需0.5元运费，那么最少要花多少运费才行？ 分析 要做到所花运费最少，必须综合考虑两个因素：（1）运走的货物尽可能少；（2）要运货物运输的路程将可能短。如果考虑第一因素，就要将货物集中在五仓库；如果考虑第二因素，就要将货物集中在四仓库。比较这两种情况，选择运费最少的一种。将货物集中到五号仓库。 解 0.5（10400+20300）=5000（元）l 例3 A、B两批发部分别有电视机70台与60台，甲乙丙三个商店分别需要电视机30台、40台和50台。从A、B两批发部每运一台电视到三个销售店的运费如表所示。如何调运才能使运费最少？ 甲乙丙A207030B3010050分析 该题中供应量70+60=130台，需求量为30+40+50=120台。供求量不等，供大于求。由表可知，由差价可知，A尽量供应给乙，即A给乙40台。接着A应尽可能多地供应给丙，即A供应给丙7040=30（台）。B供应30台给甲，供应5030=20（台）给丙。按此调运方案运费最少。 解 3030+7040+（3030+5020）=5600（元）l 例4 甲、乙两位沙漠探险者要到沙漠深处探险，他们每天向沙漠深处走20千米，已知每人最多可以携带一个人24天的事物和水，如果允许将部分事物存放于途中，那么其中1人最远可以深入沙漠多少千米？（要求二人都能安全返回出发点）分析 甲、乙两人同时出发向沙漠腹地进发，若干天后，甲返回出发地，这时甲和乙的给养都消耗了相同部分，甲将余下的部分平均分成三成，一份补足乙刚才消耗的给养，另一份存放于甲的返回点，自己携带一份返回，可见甲的给养平均分成了4份，而乙的给养平均分成2份。解244=6（天） 242=12（天） 6+12=18（天） 2018=360（天）l 例5 有10个村，坐落在从县城出发的一条公路（如图，距离单位都是千米），要安装水管，从县城输送自来水供给各村，可以用粗细两种水管，粗管足够供应所有各村用水，细管只能供应一个村用水。粗管每千米用8000元，细管每千米用2000元。把粗管和细管适当搭配，互相连接，可以降低工程的总费用。按你认为最节省的办法，费用应是多少？ 分析 首先考虑全用粗管，因为8000元是2000元的4倍，所有G之后粗管，费用将减少。在F与G之间不论安装粗管还是细管，花的钱一样多。在F之前如果不安装粗管，需要5条以上的细管，费用将增加。因此，工程的设计是：从县城到G安装一条粗管；G和H之间安装三条细管；H与I之间安装两条细管；I与J之间安装一条细管。这样做，工程费用最少。 解 8000（30+5+2+4+2+3+2）+2000（23+23+5）=（元）l 例6 仓库内有一批14米长的钢材，现要取出若干根，把它们切割成3米和5米长的50根。如果不计切割时的损耗，最少要从仓库最出多少根钢材？ 分析 因为14=33+5，所有把每根14米的钢材切割成3根3米和1根5米的最少料。但是这种“最优方案”会导致3米的大大多于5米的，不符合各50根的要求，于是应该想到13=5+5+3，即把14米的钢材切割成2根多5米的和1根3米的，每用一根钢材仅浪费1米的“次优方案”，这一方案中5米的多于3米的，因把“最优方案”与“次优方案”切割了Y根。 按“最优方案”可得3X根3米的，X根5米的；按“次优方案”可得Y根3米的，2Y根5米的。根据3米的与5米的根数相等，可得： 3X+Y=X+2Y 得2X=Y因为3X+Y=50，所以3X+2X=5X，解之得X=10，这样Y=20，也就是说最少要从仓库取出10+20=30（根）钢材。在我国古代数学著作孙子算经中，记载了这样一道题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?这一问题及其解法，被中外数学家称之为”孙子定理“，也称为”中国剩余定理“。l 例7 一个数除以3余2，除以5余3，除以7余2.求满足条件的最小整数”。 分析 这类问题的解题依据是： （1）如果被除数增加（或减少）除数的若干部，除数不变，那么余数仍然是2. 例如：173=5.2 那么17依次加上（或减去）3的倍数，余数仍然是2. （2）如果被除数扩大（或缩小）若干部，除数不变，则余数也扩大（或缩小）相同的倍数。 例如 253=4.3如果将23扩大3倍，余数也扩大3倍变成9（实际余4）。 本题所求的最小的整数要满足三个条件，解答时可先求满足其中一个条件的数，再依次增加条件，最终找到满足所有条件的数。 解 解法一：（1）先找出满足：“除以3余2 ”的最小的数2，再依次加上3的倍数，余数不变：2+3=5,5+3=8. (2)从中找到满足“除以5余3”的最小的数是8，我们再依次加上3和5的公倍数，仍然能满足前两个条件。8+15=23,23+15=38，.(3) 上利数中满足“除以7余2”的最小的数是23.这是同时满足三个条件的最小的整数，如果依次加上3、5、7的公倍，仍然满足这三个条件。 因此，满足条件的最小整数是23 解法二 （1)先找出能不被3、5正处而被7除余1的数：15，能被3、7整除而被5除余1的数：21，能被5、7整除而被3除余1的数：70。 （2）题目中要求的数倍7、5、3除得的余数分别是2、3、2，用它们分别去乘15、21、70，再把积加起来：152+213+702=30+63+140=233、 （3）233是满足条件的数，但不是最小的，从中减去3、5、7的公倍数，使得差小于他们的最小公倍数105，这个差就是满足条件的最小的数：233-1052=23 注 解法一，小学生较易理解和掌握。解法二更科学、简明，但理解起来有难度l 例8 篮子里有若干只鸡蛋，每次去处5只，最最后剩3只；每次去处6只，最后剩下4只；每次去处7只，最后剩1只。篮子里至少有多少只鸡蛋？分析 本题与例1类型相同，鸡蛋的数量除以5余3，除以6余4，除以7余1.求篮子里至少有多少只鸡蛋，也就是求符合条件的最小的数。解 （1）“除以5余3”的最小的数是3，加上5的倍数：8、13、18、23、28（2） 从中找到满足“除以6余4”的最小的数是28，再一次加上5和6的公倍数30：58、88、118、148（3） 上列数中满足“除以7余1”的最小数是148.因此，148就是符合条件的最小的数，即篮子里至少148只鸡蛋。例9 一个数被7除余5，被4除余3，这个数被28除余几？分析 先找出“被7除余5、被4除余3”的最小数，用这个数除以28的余数，就是所求的数。解 （1）“被7除余5”的数有：5、12、19、26（2） 从中找出满足“被4除余3”的最小的数是19，用19依次加上7和4的公倍数28，可以得到所有符合条件的数。（3） 因为1928的余数是19，其他符合条件的数被28除的余数也是19. 因此，这个数被28除余19.例10 再一次讨论会上，与会代表没3人一组，则多1人；每5人一组，则多2人；每7人一组，则多3人。已知与会代表人数350400之间，就是与会代表的人数。解：（1）“被除3余1”的数有：1、4、7（2） 从中找出满足“被5除余2”的最小的数是7，用7依次加上3和5的公倍数15：22、37、52、.（3） 上列数中满足“除以7余3”的最小的数是52.（4） 因为人数在350400之间，所以用52依次加上3、5和7的最小公倍数105;157/262/367、. 那么，与会代表共有367人。例11 在500以内的整数中，除以4余3，除以5余2，除以7余4的最大数是多少？ 分析 先找出符合条件的最小的数，再加上4、5和7的公倍数的若干倍，找到500以内最大的数。 解（1）“被除4余3”的数有：3、7.（2）从中找到满足“被5除余2的最小的数是7，用7依次加上4和5的公倍数20:27、47、67、. （3）上列数中满足”除以7余4“的最小的数是67. （4）4、5和7的最小公倍数是140,67+1403=487. 因此，满足条件的最大的数是487.例12 在小于1000的整数中，除以3余2，除以5余2，除以7余4的数共有多少个？ 分析 先找出符合条件的最小的数，再加上3、5和7的公倍数的若干倍，找出1000以内符合条件的最大的数，将若干倍加上1，也就是满足条件的数的个数。 解（1）”被出3余2、被5除余2“的最小数，也就是3和5的最小公倍数加上2： 35+2=17 （2）用17依次加上3和5的公倍数15:32、47、. （3）上列数中满足“除以7余4”的最小的数是32. （4）3,5和7=105,32+1059=977 9+1=10，所以满足条件的数共有10个 “一堆草可供8头牛吃6天，这堆草可供10头牛吃几天?,这个问题分成简单，因为草的问题是固定不变的，于是可以得到，可供12头牛吃：8612=4（天） 但如果将“一堆草”改为“一片正在生长的草地”，此时问题就复杂多了，因为草的总量是在不断变化的（假设其均匀变化）。这类工作总量不固定但均匀变化的问题称为牛吃草问题，由于这类问题首先由牛顿提出的，因而也叫牛顿问题。 此类题，它的解题思路具有一定的规律和模式，只要认真学习，仔细分析，就能掌握方法，正确解答。例13 牧场上长满了青草，而且每天还在匀速生长，这片牧场上的草可供9头牛吃20天，可供15头牛吃10天，如果要供18头牛吃，可吃几天？ 分析 如果我们将1头牛1天的吃草量看作1份，则9头牛20天共吃了1920=180份草，而15头牛10天共吃了11510=150份草，同一片牧场原有草的份数相等，产生180150=30份草的差异是由（2010）天中长出的新草，因此可以先求每天新生的草是30（2010）=3（份），再从吃草总量中减去一共新生的草，就是牧场上原有的草，由于每天都新生出3份的草量，可供3头牛吃，所以18头牛中只有（183）头牛在吃原有草，原有草可供（183）头牛吃几天，就是所求的问题。 解 （1） 每天新生的草： （9201510）（2010）=3 （2）牧场原有的草： 920320=120 （3）18头牛吃的天数： 120（183）=8（天） 答 要供18头牛吃，可以吃8天说明 解答“牛顿问题”的基础，是要通过两种不同吃法所产生的差异，来先求出每天新生的草，接着再求出原来牧场上的草，通过假设每天涨几份草就被几头牛吃掉，剩下的牛只能吃原来的草，然后再求出吃的天数。由于草没有具体的数量，往往假设1头牛1天吃1份草。例14 有一口水井，持续不断地涌出泉水，每分钟涌出的水量都相等，如果使用8架抽水机抽水，60分钟可以抽完水，现在要在18分钟内抽完水，需要多少架抽水机？分析 我们可将么分钟每架抽水机抽出的水量看作1份，分别求出每分钟涌出的水量和井中原有的水量，而实际抽水量应是原来水量与18分新涌出的水量之和，一架抽水机18分钟可抽水（118）份，有几个（118）份，就是所求抽水机的数量。 解 （1）每分钟涌出水量： （560830）（6030）=2 （2）井中原有水量： 560260=180（3） 实际抽水量： 180+218=216（4） 所用抽水机架数： 21618=12（架）答 需要12架抽水机。 说明 抽水问题与牛顿问题类似，也必须先求出每分钟涌水的水量和原来有的水量，要求用多少台抽水机，则可先求出实际抽水量（即原来水量与新涌水的水量之和）再求所用的抽水机数例15 有一漫池水，池底有泉水总能均匀地向外涌出，如果用25部售水机6天可以将水池抽干，如果用20部抽水机12天可将水池抽干，如果每部抽水机水量相等，要使这一池水永远抽不干，则至多只能用多少部抽水机抽水？分析 我们可以假设1部抽水机1天的抽水量为1份，可以先求出每天新涌出了多少份水，要使这池水永远不干，每天抽掉的水量不能超过每天新涌出的水量，因此每天最多只能抽掉新涌出的水。解 （1）每天新涌出的水量： （2012256）（126）=15 （2）至多安排抽水机的部数 151=15（部） 答 至多安排15部抽水机说明 这一题与一般的“牛顿问题”不同，它要使原有水留下来，唯一的方法是抽得的水只能等于或小于新涌出的水量。解答不同的问题，要认真分析，把握实质，才能正确解答。例16 东升牧场南面一块20000平方米的牧场上长满牧草，牧草每天都在匀速生长。这片牧草可供18头牛吃16天，或者供27头牛吃8天。如果东升牧草西侧有一块6000平方米的牧草，6天中可供多少牛吃草？分析 由于要计算的牧场是原牧草的3倍，可将这个牧场看作3个原来的牧场，求出每个牧场牛的头数扩大3倍即可。解（1）每天新生草：（1816278）（168）=9（2）2000平方米牧场原来有草：27898=144（3）2000平方米吃6天，牛的头数：（144+96）6=33（头）（4）6000平方米可供牛吃的头数：33（60002000）=99（头） 答 6天中可供99头 牛吃草说明 要计算二片大小不等的但草量与新生草量都相同的牧场可供多少头牛吃草，只要将较大的牧场看作几个同样大小的牧场，则大牧场的面积是小牧场的几倍，牛的头数也是几倍。例17 有三块牧场，场上的草长得一样密，而且长得一样快。他们的面积分别是3公顷、10公顷和24公顷。第一块牧场饲养12头牛，可以维持4周；第二块牧场饲养21头牛，可以维持9周。问第三块牧场上饲养多少头牛恰好可以维持18周？分析 我们假设1头牛1周吃草量为1份。第一块地12头牛可以吃4周；第二块地是第一块地的10/3倍，所以第二块应该够36头牛吃4周。可以先求出第二块每周的新生草量和原有草量，再根据第三块地是第二块的的2.4倍，求出第三块每天新生草量和原有草量，最后再求第三块够多少头牛吃18周。解 （1）第二块地每天新生草量 （21912（103）4）（94）=9 （2）第二块地原有草量： 21999=108 （3）第三块地每天新生草量： 9（2410）=21.6 （4）第三块地原有草量108（2410）=259.2（5）第三块吃18周牛的头数：（259.2+21.618）18=36 答 饲养36头牛恰好可以维持18周 说明 当牧场不是同样大小时，我们可以根据不同牧场之间的倍数“折算”成同样面积时牛的头数，这样可以解答了。千万不可将面积之间的关系“折算”成牛吃的时间，因为时间变化了，新生的草量会变化，所求解的结果就变化了。例18 甲，乙，丙三个仓库，各存放着数量相同的煤炭，甲仓库用一台电运输送机和12个工人，5小时可将甲仓库里的煤矿搬完；乙仓库用一台电动运输送机和28个工人，3小时内将仓库内的煤炭搬完；丙仓库现有2台运输送机，如果要在2小时内把丙仓库内的煤炭搬完，还有多少工人？（每个工人每小时工作效率相等，每台电动运输送机每小时工作效率相等，另外电动运输送机与工人同时玩外搬运煤炭） 分析 我们还是假设1个工人1小时搬运煤炭量为1，则可根据甲，乙两仓库的搬运情况的差别，先求出1太电动输送机1小时的搬运量，接着再求甲，乙，丙三个仓库各存有多少煤炭，最后在求出丙仓库需要配套多少个工人参加搬运煤炭。解 （1）1台电动输送机1小时候的输送量（2831125）（53）=12（2）每个仓库存有的煤炭量 283+123=120(3)丙仓库还需要工人搬运的工人数1201222=72（4）2小时需参加搬运的工人数： 722=36（人）答 还需要36名工人搬运说明 这一题是“牛顿问题”的变式，解答时也要先求出原有煤炭量，由于仓库里没有新的煤炭芸人，在计算人数时，不再要考虑时间与煤炭问题之间的变化。例19 人民商场9时开门营业，开门前就有人等候入场，如果从第一个顾客来时起，每分钟来的顾客人数都同样多。那么开4个门等候的人全部进入商场要8分钟，开6个门等候的人全部进入商场只要4分钟，问第一个顾客到达时是几时几分？ 分析 我们可以把每分钟从每个门进入商场的人看作1份，就可以分别求出每分钟到达门口的顾客和开门时已经等候的顾客份数，由于每分钟到达的人数相等，只要看开门前已到达门口的顾客有多少份，就可以计算出第一个顾客到达的时间解 （1）每分钟到达等候开门的顾客有：（4864）（84）=2（2）9时就等候的顾客有：6424=16（3） 第一个顾客到达等候开门所需时间： 162=8（分钟）（4） 第一个顾客到达的时间 9时8分钟=8时52分 答 第一个顾客到时是8时52分 说明 这也是“牛顿问题”的一种变式。我们只要将等候的人当作“原有的草”，将每分钟到达的人数当作“新生草”来分析，大体的解答思路就比较清晰了。例20 两个顽皮的孩子逆着自动扶梯行驶的方向行走，男孩每秒可走3级电梯，女孩每秒可走2级电梯，结果从扶梯的一端到达另一端男孩走了100秒，女孩走了300秒。问该扶梯共有多少级？ 分析 男孩共走了300级，这300级包含扶梯的级数和100秒扶梯自动降下的级数。女孩300秒走了600级中包含扶梯的级数和300秒扶梯自动降下的级数。理解了这些就可以解答问题了 。 解（1）扶梯每秒自动下降的级数 （23003100）（300100）=1.5（级）（2） 扶梯的级数 31001.5100=150（级）答 扶梯共150级 说明 扶梯匀速下降就相当于草自然生长一样，所以这类问题用“牛顿问题”也是“牛顿问题”的变式练习十四1、 张教师找甲、乙、丙三名学生来办公室谈话，甲要10分钟谈完，乙要20分钟谈完、丙要8分钟谈完。怎么安排三人谈话顺序，使三人花的总时间最少？最少需要多少分钟？2、 小王和小李都是发型师，一天同时来了五名顾客，根据顾客所要理的发型，分别需要12,17,14,20,45分钟，怎样安排理