简单的统筹规划问题.docx

简单的统筹规划问题.docx

《简单的统筹规划问题.docx》由会员分享，可在线阅读，更多相关《简单的统筹规划问题.docx（14页珍藏版）》请在冰点文库上搜索。

简单的统筹规划问题

系列专题讲座（四）  简单的统筹规划问题

张忠超

    导读：

最优化概念反映了人类实践活动中十分普遍的现象，即要在尽可能节省人力、物力和时间的前提下，努力争取获得在允许范围内的最佳效益．因此，最优化问题成为现代应用数学的一个重要研究对象，它在生产、科学研究以及日常生活中都有广泛的应用．作为数学爱好者，接触一些简单的实际问题，了解一些优化的思想是十分有益的．现在通过几个例题，学习一些简单的知识和解题方法。

也介绍了一点不定方程的知识，只供学有余力的学生进一步学习的参考。

    例1、妈妈让小明给客人烧水沏茶．洗开水壶要用1分钟，烧开水要用15分钟．洗茶壶要用1分钟，洗茶杯要用1分钟，拿茶叶要用2分钟．小明估算了一下，完成这些工作要20分钟．为了使客人早点喝上茶，按你认为最合理的安排，多少分钟就能沏茶了？

    分析:

 本题取自华罗庚教授1965年发表的《统筹方法平话》．烧水沏茶的情况是：

开水要烧，开水壶要洗，茶壶茶杯要洗，茶叶要取．怎样安排工作程序最省时间呢？

    办法甲：

洗好开水壶，灌上凉水，放在火上，在等待水开的时候，洗茶杯，拿茶叶，等水开了，沏茶喝．

    办法乙：

先做好一切准备工作，洗开水壶，洗壶杯，拿茶叶，灌水烧水，坐等水开了沏茶喝．

    办法丙：

洗开水壶，灌上凉水，放在火上坐待水开，开了之后急急忙忙找茶叶，洗壶杯，沏茶喝．

    谁都能一眼看出第一种办法好，因为后两种办法都“窝了工”．

    开水壶不洗，不能烧开水，固为洗开水壶是烧开水的先决条件，没开水、没茶叶、不洗壶杯，我们不能沏茶，因而这些又是沏茶的先决条件．它们的相互关系可以用下图的箭头图来显示．

    箭杆上的数字表示完成这一工作所需的时间，例如→表示从把水放在炉上到水开的时间是15分钟．从图上可以一眼看出，办法甲总共要16分钟，而办法乙、丙需20分钟．

    洗壶杯、拿茶叶没有什么先后关系，而且是由同一个人来做，因此可以将上图合并成下图．

    解:

 先洗开水壶用1分钟，接着烧开水用15分钟，在等待水开的过程中，同时洗茶杯、拿茶叶，水开了就沏茶，总共用了16分钟．又因为烧开水的15分钟不能减少，烧水前必须用1分钟洗开水壶，所以用16分钟是最少的．

    说明：

本题涉及到的统筹方法，是生产、建设、工程和企业管理中合理安排工作的一种科学方法，它对于进行合理调度、加快工作进展，提高工作效率，保证工作质量是十分有效的．

    例2、用一只平底锅煎饼，每次能同时放两个饼．如果煎1个饼需要2分钟（假定正、反面各需1分钟），问煎1993个饼至少需要几分钟？

    分析:

 由于1993数目较大，直接入手不容易．我们不妨先从较小的数目来进行探索规律．

    如果只煎1个饼，显然需要2分钟；

    如果煎2个饼，仍然需要2分钟；

    如果煎3个饼，初学者看来认为至少需要4分钟：

因为先煎2个饼要2分钟；再单独煎第3个饼，又需要2分，所以一共需要4分钟．但是，这不是最佳方案．最优方法应该是：

    首先煎第1号、第2号饼的正面用1分钟；

    其次煎第1号饼的反面及第3号饼的正面又用1分钟；

    最后煎第2号、第3号饼的反面再用1分钟；这样总共只用3分钟就煎好了3个饼．

    解：

如果煎1993个饼，最优方案应该是：

    煎第1、2、3号饼用“分析”中的方法只需要3分钟；煎后面1990个饼时，每两个饼需要2分钟，分1990÷2=995（次）煎完，共需要2×995=1990（分钟）；这样总共需要3+1990=1993（分钟）．

同学们再考虑一下：

煎2006张，2007张各应如何解？

从中总结出规律。

说明：

通过本例可以看出，掌握优化的思想，合理统筹安排操作程序，就能够节省时间，提高效率．

    例3、5个人各拿一个水桶在自来水龙头前等候打水，他们打水所需的时间分别是1分钟、2分钟、3分钟、4分钟和5分钟．如果只有一个水龙头，试问怎样适当安排他们的打水顺序，才能使每个人排队和打水时间的总和最小？

并求出最小值．

    分析:

 5个人排队一共有5×4×3×2×1=120种不同顺序，把所有情形的时间总和都计算出来，就太繁琐了．凭直觉，应该把打水时间少的人排在前面，则后面等的人所费的总时间会省些．

    解：

首先需1分钟的人排在第一位置，需1×5=5分钟

    需2分钟的人排在第二位置，共需2×4=8分钟

    需3分钟的人排在第三位置，共需3×3=9分钟

    需4分钟的人排在第四位置，共需4×2=8分钟

    需5分钟的人排在第五位置，共需5分钟

    所以共用时：

1×5+2×4+3×3+4×2+5×1=35（分钟）．

    说明:

 排队提水的问题，在其他一些场合也是会遇到的．例如，有一台机床要加工n个工件，每个工件需要的加工时间不一样，问应该按照什么次序加工，才能使总的等待时间最短．同学们可类比去解。

    例4、有157吨货物要从甲地运往乙地，大卡车的载重量是5吨，小卡车的载重量是2吨，大卡车与小卡车每车次的耗油量分别是10公升与5公升．问如何选派车辆才能使运输耗油量最少？

这时共需用油多少公升？

    解：

依题意，大卡车每吨耗油量为10÷5=2（公升）；小卡车每吨耗油量为5÷2=2.5（公升）．为了节省汽油应尽量选派大卡车运货，又由于

157=5×31+2，

因此，最优调运方案是：

选派31车次大卡车及1车次小卡车即可将货物全部运完，且这时耗油量最少，只需用油

10×31+5×1=315（公升）

    说明：

本题是1960年上海市数学竞赛试题．上述解法是最朴素的优化思想——选派每吨耗油量较少的卡车．同学们可考虑：

货物分别为，158，159.160时如何解？

大卡车的载重量是5吨，小卡车的载重量是3吨，又如何解？

    例5、某工地A有20辆卡车，要把60车渣土从A运到B，把40车砖从C运到D（工地道路图如右图所示），问如何调运最省汽油？

    分析:

 把渣土从A运到B或把砖从C运到D，都无法节省汽油.只有设法减少跑空车的距离，才能省汽油。

    解：

如果各派10辆车分别运渣土和砖，那么每运一车渣土要空车跑回300米，每运一车砖则要空车跑回360米，空车共跑60×300+360×40=32400米。

    如果一辆车从A→B→C→D→A跑一圈，那么每运一车渣土、再运一车砖要空车跑

240+90＝330（米）.

因此，先派20辆车都从A开始运渣土到B，再空车开往C运砖到D后空车返回A，这样每辆车跑两圈就完成了运砖任务.然后再派这20辆车都从A运渣土到B再空车返回A，则运渣土任务也完成了.这时总共空车跑了

330×40+300×20＝19200（米）.

是最佳节油的调运方案。

    说明：

“节省跑空车的距离”是物资调运问题的一个原则。

    例6、有十个村，坐落在从县城出发的一条公路上（如下页图，距离单位是公里），要安装水管，从县城送自来水供给各村，可以用粗细两种水管．粗管足够供应所有各村用水，细管只能供一个村用水．粗管每公里要用8000元，细管每公里要用2000元．把粗管和细管适当搭配、互相连接，可以降低工程的总费用．请你设计一个最节约的办法，并算出费用应是多少？

    分析:

由题意可知，粗管每公里的费用恰好是细管每公里费用的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×（2×4+2×3+2×2+5）

 =414000（元）．

    说明：

容易验证，从县城B起，铺设粗管到A6或A7或者A6A7之间任何一个地点，都是最节约的办法，总费用仍是414000元．下面详细论证其他安装方案的总费用都大于a．

    当粗管从县城B铺设到超过A7向A8移动一段路程d（0＜d≤2）公里时，粗管费用增加8000d（元），而细管费用仅减少

2000d×3=6000d（元）．

这时总费用比a多2000d（元）．

    当粗管从县城B铺设到超过A8向A9移动一段路程d（0＜d≤2）公里时，粗管费用增加

8000×（2+d）=16000+8000d（元），

而细管增费用仅减少

2000×（2×3＋2d）=12000＋4000d（元）．

这时总费用比a多4000+4000d（元）．

    当粗管从县城B铺设到超过A9向A

移动一段路程d（0＜d≤5）公里时，粗管费用增加

8000×（2+2+d）=32000+8000d（元）．

而细管费用仅减少

2000×（2×3+2×2+d）=20000+2000d（元）．

这时总费用比a多12000＋6000d（元）．

    综上所述，从县城B铺设粗管到超过A7点以东的任何地点的安装总费用都大于a．

    类似地，可以验证从县城铺设粗管到A6点以西的任何地点的总费用也都大于a．

    例7、在一条公路上每隔100千米有一个仓库（如图），共有5个仓库.一号仓库存有10吨货物，二号仓库有20吨货物，五号仓库存有40吨货物，其余两个仓库是空的。

现在想把所有的货物集中存放在一个仓库里，如果每吨货物运输1公里需要0.5元运输费，那么最少要多少运费才行？

    分析：

欲使花费的运输费少，关键在于运输的货物和路程尽可能少，实际经验告诉我们一个原则——“小往大处靠”.下面就以两地调运问题为例加以计算验证：

如下图，在公路上A、B两地各有10吨、15吨麦子，问打麦场建在何处运费最少？

    同学们先考虑一下，建在B处是不是运费最少？

是。

现在做一简要说明。

    设打麦场建在C点，则总运费是（假定每吨小麦运输1千米的费用是a元）

W＝10×a×AC＋15×a×BC

＝10a×AC＋10a×BC＋5a×BC

＝10a×（AC＋BC）＋5a×BC

=10a×AB＋5a×BC

    上式中10a×AB是固定的值，不随C点的选取而改变；只有5a×BC随BC的变化而改变，若BC越小，则W也越小.当BC=0时，即C点与B点重合时，W的值最小.因此打麦场建在B点时总运费是10a×AB（元）为最少.显然当打麦场建在AB线段之外时，总运费都大于10a×AB（元）。

    解：

根据“小往大处靠”的原则，先把一号仓库的10吨货物送往二号仓库集中，需运费

10×0.5×100=500（元）。

    这时可以认为二号仓库有30吨货物，而五号仓库有40吨货物，于是又应把二号仓库的30吨货物运往五号仓库集中，需运费

30×0.5×300=4500（元）。

    所以，把货物集中存放在五号仓库时所花运费最少，需要

500＋4500=5000（元）。

    说明：

“小往大处靠”的原则也不是一成不变的，具体问题还要具体分析。

    再举两例如下：

    例如：

一号仓库有20吨货物，二号仓库有30吨货物，其他仓库存货照样如前，那么应该往哪个仓库集中呢？

首先仍应把一号仓库的20吨货物运往二号仓库集中，然后再把五号仓库的40吨货物也运往二号仓库集中，这样运费最少。

    又如：

一号仓库有30吨货物，二号仓库有20吨货物，其他仓库存货仍然如前，那么应该往哪个仓库集中呢？

先把一号仓库的30吨货物运往二号仓库集中，再把五号仓库的40吨货物也运往二号仓库集中，这样运费最省.（想想为什么？

）

    还有一点值得注意：

在决定货物往何处集中时，起决定作用的是货物的重量，至于距离仅仅是为了计算运费.如果把本题中各个仓库之间的距离换成另外一些数值，仍应该把货物集中到五号仓库。

    本题可以推广为一般命题：

“一条公路上有n个仓库，它们分别存货A1吨、A2吨、…、an吨.现在需要把所有的货物集中存放在一个仓库里，应该选取哪个仓库可以使总运输费最少？

”它的解法将涉及到一次函数的知识，同学们在学过初三代数之后就会完全明白了。

    例8、山区有一个工厂．它的十个车间分散在一条环行的铁道上．四列货车在铁道上转圈运送货物。

货车到了某一车间，就要有装卸工人装上或卸下货物．各车间由于工作量不同，所需装卸工人数也不同，各车间所需装卸工人数如图所示。

当然，装卸工可以固定在车间等车；也可以坐在货车上跟车到各车间去干活；也可以一部分装卸工固定在车间，另一部分跟车．问怎样安排跟车人数和各车间固定人数，才能使装卸工的总人数最少？

最少需多少名工人？

    分析：

如跟车人数为57，则各车间都不用安排人，但这样在需要人数少的车间，浪费人力,不行；为此找出各车间人数的平均数，后再调整。

各车间人数的平均数为.43.9.若跟车人数为43，则需人数多于43的车间需增加的人数分别为14，7，5，3，9，此时共需人数43×4+14+7+5+3+9=210。

若跟车人数为46，由于需人数多于46的有四个车间，货车上增多的人数与四个车间减少的人数一样。

故跟车人数为46人，需人数多于46的四个车间人数各增加所差数即可

    解：

46×4+4+2+6+11=207（人）．

。

    同学们可用其它数再算算，看这个结果是否最少？

    例9、189米长的钢筋要剪成4米或7米两种尺寸，如何剪法最省材料？

    分析：

显然无残料的剪法是最优方案.于是考虑二元一次不定方程的整数解问题

这里我们先用算术方法来解。

因为189÷7=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根，依题意列方程

4x＋7y＝189。

    根据倍数分析法可知

7｜x（即x是7的倍数）。

    令x1＝0，则7y＝189，解出y1=27；

    x2＝7，则7y＝161，解出y2＝23；

    x3=14，则7y＝133，解出y3＝19；

    x4=21，则7y=105，解出y4=15；

    x5＝28，则7y=77，解出y5=11；

    x6=35，则7y＝49，解出y6＝7；

    x7=42，则7y＝21，解出y7=3。

    因此，有七种剪法都是最省材料的。

    说明：

本例是最简单的下料问题，属于“线性规划”的范畴，线性规划是运用一次方程（组）、一次函数来解决规划问题的数学分支。

规划论研究的问题主要有两类：

一确定了一项任务，研究怎样精打细算使用最少人力、物力和时间去完成它；另一类是在已有一定数量的人力、物力和财力的条件下，研究怎样合理调配，使它们发挥最大限度的作用，从而完成最多的任务。

这种解法仅供学习有余力的学生进一步学习时参考

    例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根，留下残料

2×25＝50（尺）。

    解：

至少要用75根原材料，其中50根用截法1，25根用截法3，这样的截法最省料.

    说明：

一般说来，一定长度的条形材料要截取两种毛坯的下料问题，用本例的方法求解是比较省料的，这种解法的理论根据要用到二元不等式及一次函数图像，有兴趣且有余力的同学可参阅有关书刊。

    例11、有1993名少先队员分散在一条公路上值勤宣传交通法规，问完成任务后应该在公路的什么地点集合，可以使他们从各自的宣传岗位沿公路走到集合地点的路程总和最小？

   分析由于1993数目较大，不易解决．我们先从人数较小的情况入手．“退一步想”，这是一种很重要的数学思想方法。

    解：

当只有2个人时，设2人宣传岗位分别为A1和A2（如上图），显然集合地点选在A1点或A2点或者A1A2之间的任何一个地点都可以．因为由A1、A2出发的人走过的路程总和都等于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岗位上的人所走的路程，这就是说，问题转化为“2个人站在A2和A3岗位的情形”．根据上面已讨论的结论可知，集合地点应选在A2或A3或者A2A3之间任何地点．

    当有5个人时，类似地可把问题转化为“3个人站在A2、A3、A4岗位的情形”（如下图）根据已讨论的结论可知，集合地点应选在A3点．

    依此递推下去，我们就得到一个规律：

    当有偶数（2n）个人时，集合地点应选在中间一段AnAn+1之间的任何地点（包括An和An+1点）；

    当有奇数（2n+1）个人时，集合地点应选在正中间岗位An+1点．

    本题有1993=2×996+1（奇数）个人，因此集合地点应选在从某一端数起第997个岗位处．

    说明：

本题的解题思路值得掌握，那就是先从简单的较少的人数入手，通过逐步递推，探索一般规律，从而解决某些数字较大的问题．

练习

    *1．妈妈杀好鱼后，让小明帮助烧鱼．他洗鱼、切鱼、切姜片葱花、洗锅煎烧，各道工序共花了17分钟（如下图），请你设计一个顺序，使花费的时间最少．

    *2．用一只平底锅煎饼，每次能同时放两个饼．如果煎一个饼需要4分钟（假定正、反面各需2分钟），问煎m个饼至少需要几分钟？

    *3．小明、小华、小强同时去卫生室找张大夫治病．小明打针要5分钟．小华换纱布要3分钟，小强点眼药水要1分钟．问张大夫如何安排治病次序，才能使他们耽误上课的时间总和最少？

并求出这个时间．

    *4．赵师傅要加工某项工程急需的5个零件，如果加工零件A、B、C、D、E所需时间分别是5分钟、3分钟、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吨.试求出使总运输吨公里数最小的调运方案。

    *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个.如何安排这些机器的生产任务才能获得最大数量的成套产品？

每天最多可生产多少套产品？

答案

    *1．12分钟．

    *2．若m＝1时，至少需要4分；

        若m≥2时，至少需要2m分钟．

    *3．按小强、小华、小明的顺序安排，耽误上课的时间总和为：

1×3+3×2+5=14（分钟）．

    *4．按B、C、A、E、D的顺序加工，耽误时间总和最少为：

3×5+4×4+5×3+6×2+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，可得非负整数解为x＝7，y=5。

    **9.解：

截法1：

2.9＋2.9＋1.5=7.3

            截法2：

2.1＋2.1＋1.5＋1.5＝7.2

            截法3：

2.9+2.1+2.1＝7.1

    答：

共用钢筋90根，其中40根用截法1；30根用截法2；20根用截法3.

    10、解：

    所以：

自动机床最善于生产乙零件；车床最善于生产甲零件.因此确定：

自动机床只生产乙零件，车床只生产甲零件；铣床生产部分甲零件和部分乙零件，使其配套。

    答：

自动机床一天生产80个乙零件；

    车床一天生产3×20＝60个甲零件；

    铣床一天生产

个乙零件、

个甲零件，三种机器一天共生产

套产品（即三天共生产

套产品）.