简单的统筹规划问题.docx

1、简单的统筹规划问题系列专题讲座（四）简单的统筹规划问题张忠超导读：最 优化概念反映了人类实践活动中十分普遍的现象，即要在尽可能节省人力、物力和时间的前提下，努力争取获得在允许范围内的最佳效益因此，最优化问题成为现 代应用数学的一个重要研究对象，它在生产、科学研究以及日常生活中都有广泛的应用作为数学爱好者，接触一些简单的实际问题，了解一些优化的思想是十分有 益的现在通过几个例题，学习一些简单的知识和解题方法。也介绍了一点不定方程的知识，只供学有余力的学生进一步学习的参考。例1、 妈妈让小明给客人烧水沏茶洗开水壶要用1分钟，烧开水要用15分钟洗茶壶要用1分钟，洗茶杯要用1分钟，拿茶叶要用2分钟小明

2、估算了一下，完成这些工作要20分钟为了使客人早点喝上茶，按你认为最合理的安排，多少分钟就能沏茶了？分析:本题取自华罗庚教授1965年发表的统筹方法平话烧水沏茶的情况是：开水要烧，开水壶要洗，茶壶茶杯要洗，茶叶要取怎样安排工作程序最省时间呢？办法甲：洗好开水壶，灌上凉水，放在火上，在等待水开的时候，洗茶杯，拿茶叶，等水开了，沏茶喝办法乙：先做好一切准备工作，洗开水壶，洗壶杯，拿茶叶，灌水烧水，坐等水开了沏茶喝办法丙：洗开水壶，灌上凉水，放在火上坐待水开，开了之后急急忙忙找茶叶，洗壶杯，沏茶喝谁都能一眼看出第一种办法好，因为后两种办法都“窝了工”开水壶不洗，不能烧开水，固为洗开水壶是烧开水的先决条

3、件，没开水、没茶叶、不洗壶杯，我们不能沏茶，因而这些又是沏茶的先决条件它们的相互关系可以用下图的箭头图来显示箭杆上的数字表示完成这一工作所需的时间，例如表示从把水放在炉上到水开的时间是15分钟从图上可以一眼看出，办法甲总共要16分钟，而办法乙、丙需20分钟洗壶杯、拿茶叶没有什么先后关系，而且是由同一个人来做，因此可以将上图合并成下图解:先洗开水壶用1分钟，接着烧开水用15分钟，在等待水开的过程中，同时洗茶杯、拿茶叶，水开了就沏茶，总共用了16分钟又因为烧开水的15分钟不能减少，烧水前必须用1分钟洗开水壶，所以用16分钟是最少的说明：本题涉及到的统筹方法，是生产、建设、工程和企业管理中合理安排工

4、作的一种科学方法，它对于进行合理调度、加快工作进展，提高工作效率，保证工作质量是十分有效的例2、用一只平底锅煎饼，每次能同时放两个饼如果煎1个饼需要2分钟（假定正、反面各需1分钟），问煎1993个饼至少需要几分钟？分析:由于1993数目较大，直接入手不容易我们不妨先从较小的数目来进行探索规律如果只煎1个饼，显然需要2分钟；如果煎2个饼，仍然需要2分钟；如果煎3个饼，初学者看来认为至少需要4分钟：因为先煎2个饼要2分钟；再单独煎第3个饼，又需要2分，所以一共需要4分钟但是，这不是最佳方案最优方法应该是：首先煎第1号、第2号饼的正面用1分钟；其次煎第1号饼的反面及第3号饼的正面又用1分钟；最后煎第

5、2号、第3号饼的反面再用1分钟；这样总共只用3分钟就煎好了3个饼解：如果煎1993个饼，最优方案应该是：煎第1、2、3号饼用“分析”中的方法只需要3分钟；煎后面1990个饼时，每两个饼需要2分钟，分19902=995（次）煎完，共需要2995=1990（分钟）；这样总共需要3+1990=1993（分钟）同学们再考虑一下：煎2006张，2007张各应如何解？从中总结出规律。说明：通过本例可以看出，掌握优化的思想，合理统筹安排操作程序，就能够节省时间，提高效率例3、5个人各拿一个水桶在自来水龙头前等候打水，他们打水所需的时间分别是1分钟、2分钟、3分钟、4分钟和5分钟如果只有一个水龙头，试问怎样适

6、当安排他们的打水顺序，才能使每个人排队和打水时间的总和最小？并求出最小值分析:5个人排队一共有54321=120种不同顺序，把所有情形的时间总和都计算出来，就太繁琐了凭直觉，应该把打水时间少的人排在前面，则后面等的人所费的总时间会省些 解：首先 需1分钟的人排在第一位置，需15=5分钟需2分钟的人排在第二位置，共需24=8分钟需3分钟的人排在第三位置，共需33=9分钟需4分钟的人排在第四位置，共需42=8分钟需5分钟的人排在第五位置，共需5分钟所以共用时：15+24+33+42+51=35（分钟）说明:排队提水的问题，在其他一些场合也是会遇到的例如，有一台机床要加工n个工件，每个工件需要的加工

7、时间不一样，问应该按照什么次序加工，才能使总的等待时间最短同学们可类比去解。例4、 有157吨货物要从甲地运往乙地，大卡车的载重量是5吨，小卡车的载重量是2吨，大卡车与小卡车每车次的耗油量分别是10公升与5公升问如何选派车辆才能使运输耗油量最少？这时共需用油多少公升？解：依题意，大卡车每吨耗油量为105=2（公升）；小卡车每吨耗油量为52=2.5（公升）为了节省汽油应尽量选派大卡车运货，又由于157=531+2，因此，最优调运方案是：选派31车次大卡车及1车次小卡车即可将货物全部运完，且这时耗油量最少，只需用油1031+51=315（公升）说明：本题是1960年上海市数学竞赛试题上述解法是最朴

8、素的优化思想选派每吨耗油量较少的卡车同学们可考虑： 货物分别为，158，159.160时如何解？ 大卡车的载重量是5吨，小卡车的载重量是3吨，又如何解？例5、某工地A有20辆卡车，要把60车渣土从A运到B，把40车砖从C运到D（工地道路图如右图所示），问如何调运最省汽油？分析:把渣土从A运到B或把砖从C运到D，都无法节省汽油.只有设法减少跑空车的距离，才能省汽油。解：如果各派10辆车分别运渣土和砖，那么每运一车渣土要空车跑回300米，每运一车砖则要空车跑回360米， 空车共跑60300+36040=32400米。如果一辆车从ABCDA跑一圈，那么每运一车渣土、再运一车砖要空车跑240+9033

9、0（米）.因此，先派20辆车都从A开始运渣土到B，再空车开往C运砖到D后空车返回A，这样每辆车跑两圈就完成了运砖任务.然后再派这20辆车都从A运渣土到B再空车返回A，则运渣土任务也完成了.这时总共空车跑了33040+3002019200（米）.是最佳节油的调运方案。说明：“节省跑空车的距离”是物资调运问题的一个原则。例6、 有 十个村，坐落在从县城出发的一条公路上（如下页图，距离单位是公里），要安装水管，从县城送自来水供给各村，可以用粗细两种水管粗管足够供应所有各村用 水，细管只能供一个村用水粗管每公里要用8000元，细管每公里要用2000元把粗管和细管适当搭配、互相连接，可以降低工程的总费用

10、请你设计一个 最节约的办法，并算出费用应是多少？分析: 由题意可知，粗管每公里的费用恰好是细管每公里费用的4倍因此，如果在同一段路上要安装4根以上的细管，就应该用一根粗管来代替，便可降低工程的总费用解：假设从县城到每个村子都各接一根细管（如上图），那么在BA1、BA2、BA3、BA4、BA5、BA6之间各有10、9、8、7、6、5根细管，应该把B与A6之间都换装粗管，只用一根，从A6A，A6A开始用细管，分别为 4，3，2，1根，则工程的总费用将最低，这时的总费用是：a=8000（30+5+4+2+3）+2000（24+23+22+5）=414000（元）说明：容易验证，从县城B起，铺设粗管到

11、A6或A7或者A6A7之间任何一个地点，都是最节约的办法，总费用仍是414000元下面详细论证其他安装方案的总费用都大于a当粗管从县城B铺设到超过A7向A8移动一段路程d（0d2）公里时，粗管费用增加8000d（元），而细管费用仅减少2000d3=6000d（元）这时总费用比 a多2000d（元）当粗管从县城B铺设到超过A8向A9移动一段路程d（0d2）公里时，粗管费用增加8000（2+d）=16000+8000d（元），而细管增费用仅减少2000（232d）=120004000d（元）这时总费用比a多4000+4000d（元）当粗管从县城B铺设到超过A9向A移动一段路程d（0d5）公里时，粗

12、管费用增加8000（2+2+d）=32000+8000d（元）而细管费用仅减少2000（23+22+d）=20000+2000d（元）这时总费用比a多120006000d（元）综上所述，从县城B铺设粗管到超过A7点以东的任何地点的安装总费用都大于a类似地，可以验证从县城铺设粗管到A6点以西的任何地点的总费用也都大于a例7、在一条公路上每隔100千米有一个仓库（如图），共有5个仓库.一号仓库存有10吨货物，二号仓库有20吨货物，五号仓库存有40吨货物，其余两个仓库是空的。现在想把所有的货物集中存放在一个仓库里，如果每吨货物运输1公里需要0.5元运输费，那么最少要多少运费才行？分析：欲使花费的运输

13、费少，关键在于运输的货物和路程尽可能少，实际经验告诉我们一个原则“小往大处靠”.下面就以两地调运问题为例加以计算验证：如下图，在公路上A、B两地各有10吨、15吨麦子，问打麦场建在何处运费最少？同学们先考虑一下，建在B处是不是运费最少？是。现在做一简要说明。设打麦场建在C点，则总运费是（假定每吨小麦运输1千米的费用是a元）W10aAC15aBC10aAC10aBC5aBC10a（ACBC）5aBC=10aAB5aBC 上式中10aAB是固定的值，不随C点的选取而改变；只有5aBC随BC的变化而改变，若BC越小，则W也越小.当BC=0时，即C点与B点重合时， W的值最小.因此打麦场建在B点时总运

14、费是10aAB（元）为最少.显然当打麦场建在AB线段之外时，总运费都大于10aAB（元）。解：根据“小往大处靠”的原则，先把一号仓库的10吨货物送往二号仓库集中，需运费100.5100=500（元）。这时可以认为二号仓库有30吨货物，而五号仓库有40吨货物，于是又应把二号仓库的30吨货物运往五号仓库集中，需运费300.5300=4500（元）。所以，把货物集中存放在五号仓库时所花运费最少，需要5004500=5000（元）。说明：“小往大处靠”的原则也不是一成不变的，具体问题还要具体分析。再举两例如下：例如：一号仓库有20吨货物，二号仓库有30吨货物，其他仓库存货照样如前，那么应该往哪个仓库集

15、中呢？首先仍应把一号仓库的20吨货物运往二号仓库集中，然后再把五号仓库的40吨货物也运往二号仓库集中，这样运费最少。又如：一号仓库有30吨货物，二号仓库有20吨货物，其他仓库存货仍然如前，那么应该往哪个仓库集中呢？先把一号仓库的30吨货物运往二号仓库集中，再把五号仓库的40吨货物也运往二号仓库集中，这样运费最省.（想想为什么？）还有一点值得注意：在决定货物往何处集中时，起决定作用的是货物的重量，至于距离仅仅是为了计算运费.如果把本题中各个仓库之间的距离换成另外一些数值，仍应该把货物集中到五号仓库。本题可以推广为一般命题：“一条公路上有n个仓库，它们分别存货A1吨、A2吨、an吨.现在需要把所有

16、的货物集中存放在一个仓库里，应该选取哪个仓库可以使总运输费最少？”它的解法将涉及到一次函数的知识，同学们在学过初三代数之后就会完全明白了。例8、 山区有一个工厂它的十个车间分散在一条环行的铁道上四列货车在铁道上转圈运送货物。货车到了某一车间，就要有装卸工人装上或卸下货物各车间由于工作 量不同，所需装卸工人数也不同，各车间所需装卸工人数如图所示。当然，装卸工可以固定在车间等车；也可以坐在货车上跟车到各车间去干活；也可以一部分装卸 工固定在车间，另一部分跟车问怎样安排跟车人数和各车间固定人数，才能使装卸工的总人数最少？最少需多少名工人？分析： 如跟车人数为57，则各车间都不用安排人，但这样在需要人

17、数少的车间，浪费人力,不行；为此找出各车间人数的平均数，后再调整。各车间人数的平均数为. 43.9.若跟车人数为43，则需人数多于43的车间需增加的人数分别为14，7，5，3，9，此时共需人数434+14+7+5+3+9=210。若 跟车人数为46，由于需人数多于46的有四个车间，货车上增多的人数与四个车间减少的人数一样。故跟车人数为46人，需人数多于46的四个车间人数各增加 所差数即可解：464+4+2+6+11=207（人）。同学们可用其它数再算算，看这个结果是否最少？例9、189米长的钢筋要剪成4米或7米两种尺寸，如何剪法最省材料？分析：显然无残料的剪法是最优方案.于是考虑二元一次不定方

18、程的整数解问题这里我们先用算术方法来解。因为1897=27。第一种方案：7米27个，4米0个，又由于4与7的最小公倍数为28，所以7米的减少4根，4米的增加7根即可，所以有：第二种方案7米 23个 4米 7个第三种方案7米 19个 4米 14个第四种方案7米 15个 4米 21个第五种方案7米 11个 4米 28个第六种方案7米 7个 4米 35个第七种方案7米 3个 4米42个如用求二元一次不定方程的整数解的方法。解：设4米长的剪x根，7米长的剪y根，依题意列方程4x7y189。根据倍数分析法可知7x（即x是7的倍数）。令x10，则7y189，解出y1=27；x27，则7y161，解出y22

19、3；x3=14，则7y133，解出y319；x4=21，则7y=105，解出y4=15；x528，则7y=77，解出y5=11；x6=35，则7y49，解出y67；x7=42，则7y21，解出y7=3。因此，有七种剪法都是最省材料的。说明： 本例是最简单的下料问题，属于“线性规划”的范畴，线性规划是运用一次方程（组）、一次函数来解决规划问题的数学分支。规划论研究的问题主要有两类：一确 定了一项任务，研究怎样精打细算使用最少人力、物力和时间去完成它；另一类是在已有一定数量的人力、物力和财力的条件下，研究怎样合理调配，使它们发挥最 大限度的作用，从而完成最多的任务。这种解法仅供学习有余力的学生进一

20、步学习时参考例10、用10尺长的竹竿做原材料，来截取3尺、4尺长的甲、乙两种短竹竿各100根，至少要用去原材料几根？怎么截法最合算？分析: 不难想到有三种截法省料：截法1：截成3尺、3尺、4尺三段，无残料；截法2：截成3尺、3尺、3尺三段，残料1尺；截法3：截成4尺、4尺两段，残料2尺。由于截法1最理想（无残料），因此应该充分应用截法1.考虑用原材料50根，可以截成100根3尺长的短竹竿，而4尺长的仅有50根，还差50根.于是再应用截法3，截原材料25根，可以得到4尺长的短竹竿50根，留下残料22550（尺）。解：至少要用75根原材料，其中50根用截法1，25根用截法3，这样的截法最省料.说明

21、：一般说来，一定长度的条形材料要截取两种毛坯的下料问题，用本例的方法求解是比较省料的，这种解法的理论根据要用到二元不等式及一次函数图像，有兴趣且有余力的同学可参阅有关书刊。例11、有1993名少先队员分散在一条公路上值勤宣传交通法规，问完成任务后应该在公路的什么地点集合，可以使他们从各自的宣传岗位沿公路走到集合地点的路程总和最小？分析 由于1993数目较大，不易解决我们先从人数较小的情况入手“退一步想”，这是一种很重要的数学思想方法。解：当只有2个人时，设2人宣传岗位分别为A1和A2（如上图），显然集合地点选在A1点或A2点或者A1A2之间的任何一个地点都可以因为由A1、A2出发的人走过的路程

22、总和都等于A1A2当有3个人时，则集合地点应该选在A2点（如右图）因为若集合地点选在A1A2之间的B点，那时3个人所走的路程总和是A1B+A2B+A3B=（A1B+A3B）+A2B=A1A3+A2B；若集合地点选在A2A3之间的C点，那时3个人所走的路程总和是：A1C+A2C+A3C=（A1C+A3C）+A2C=A1A3+A2C；而集合地点选在A2点时，3个人所走路程总和仅是A1A3当然A1A3比A1A3+A2B及A1A3+A2C都小当有4个人时，由于集合地点无论选在A1A4之间的任何位置，对A1、A4岗位上的人来说，这2人走的路程和都是A1A4（如下图）因此，集合地点的选取只影响A2、A3岗

23、位上的人所走的路程，这就是说，问题转化为“2个人站在A2和A3岗位的情形”根据上面已讨论的结论可知，集合地点应选在A2或A3或者A2A3之间任何地点当有5个人时，类似地可把问题转化为“ 3个人站在A2、A3、A4岗位的情形”（如下图）根据已讨论的结论可知，集合地点应选在A3点依此递推下去，我们就得到一个规律：当有偶数（2n）个人时，集合地点应选在中间一段AnAn+1之间的任何地点（包括An和An+1点）；当有奇数（2n+1）个人时，集合地点应选在正中间岗位An+1点本题有1993=2996+1（奇数）个人，因此集合地点应选在从某一端数起第997个岗位处说明：本题的解题思路值得掌握，那就是先从简

24、单的较少的人数入手，通过逐步递推，探索一般规律，从而解决某些数字较大的问题练习*1妈妈杀好鱼后，让小明帮助烧鱼他洗鱼、切鱼、切姜片葱花、洗锅煎烧，各道工序共花了17分钟（如下图），请你设计一个顺序，使花费的时间最少*2用一只平底锅煎饼，每次能同时放两个饼如果煎一个饼需要4分钟（假定正、反面各需2分钟），问煎m个饼至少需要几分钟？*3小明、小华、小强同时去卫生室找张大夫治病小明打针要5分钟小华换纱布要3分钟，小强点眼药水要1分钟问张大夫如何安排治病次序，才能使他们耽误上课的时间总和最少？并求出这个时间*4赵师傅要加工某项工程急需的5个零件，如果加工零件A、B、C、D、E所需时间分别是5分钟、3分

25、钟、4分钟、7分钟、6分钟问应该按照什么次序加工，使工程各部件组装所耽误的时间总和最少？这个时间是多少？*5某水池可以用甲、乙两个水管注水，单放甲管需12小时注满，单放乙管需24小时注满若要求10小时注满水池，并且甲、乙两管合放的时间尽可能地少，则甲、乙两管合放最少需要多少小时？*6.某乡共有六块甘蔗地，每块地的产量如下图所示.现在准备建设一座糖厂，问糖厂建于何处总运费最省？*7.产地A1、A2、A3和销售地B1、B2、B3、B4都在铁路线上，位置如下图所示.已知A1、A2、A3的产量分别为5吨、3吨、2吨；B1、B2、B3、B4的销售量分别是1吨、2吨、3吨、4吨.试求出使总运输吨公里数最小

26、的调运方案。*8.把长239米的钢筋截成17米和24米长的钢筋，如何截法最省材料？*9.钢筋原材料每件长7.3米，每套钢筋架子用长2.9米、2.1米和1.5米的钢筋各1段.现在需要绑好钢筋架子100套，至少要用去原材料几件？截料方法怎样最省？*10. 某车间有铣床3台，车床3台，自动机床1台，生产一种由甲、乙两个零件组成的产品.每台铣床每天生产甲零件10个，或者生产乙零件20个；每台车床每天生 产甲零件20个，或者生产乙零件30个；每台自动机床每天生产甲零件30个，或者生产乙零件80个.如何安排这些机器的生产任务才能获得最大数量的成套产 品？每天最多可生产多少套产品？答案*112分钟*2若m1

27、时，至少需要4分；若m2时，至少需要2m分钟*3按小强、小华、小明的顺序安排，耽误上课的时间总和为：13+32+5=14（分钟）*4按B、C、A、E、D的顺序加工，耽误时间总和最少为：35+44+53+62+7=65（分钟）*6.答：糖厂建于C处总运费最省。如下图（a），根据“小往大处靠”的原则，把A靠到B；E靠到G，F靠到G，这样就成图（b）同理：B靠到C，D靠到C，这时，C为16吨；G为11吨.最后，G靠到C。*7.答：A运往B处1吨；运往B处2吨；运往B处2吨。A运往B处1吨；运往B处2吨。A运往B处2吨。*8.解：设截成17米长的钢筋x根，截成24米长的钢筋y根。则有17x+24y=239，可得非负整数解为x7，y=5。*9.解：截法1：2.92.91.5=7.3截法2：2.12.11.51.57.2截法3：2.9+2.1+2.17.1答：共用钢筋90根，其中40根用截法1；30根用截法2；20根用截法3.10、解：所以：自动机床最善于生产乙零件；车床最善于生产甲零件.因此确定：自动机床只生产乙零件，车床只生产甲零件；铣床生产部分甲零件和部分乙零件，使其配套。答：自动机床一天生产80个乙零件；车床一天生产32060个甲零件；铣床一天生产个乙零件、个甲零件，三种机器一天共生产套产品（即三天共生产套产品）.