13简单的统筹规划问题.doc

1、第十三讲 简单的统筹规划问题这一讲我们讨论有关物资调运、下料问题及配套生产等实例。例 1 某工地 A 有 20 辆卡车，要把 60 车渣土从 A 运到 B，把 40 车砖从C 运到 D（工地道路图如右图所示），问如何调运最省汽油？分析 把渣土从 A 运到 B 或把砖从 C 运到 D，都无法节省汽油.只有设法减少跑空车的距离，才能省汽油。解：如果各派 10 辆车分别运渣土和砖，那么每运一车渣土要空车跑回 300 米，每运一车砖则要空车跑回360 米，这样到完成任务总共空车跑了3006036040=32400（米）。如果一辆车从 ABCDA 跑一圈，那么每运一车渣土、再运一车砖要空车跑240+90

2、 330（米）.因此，先派 20 辆车都从 A 开始运渣土到 B，再空车开往 C 运砖到D 后空车返回 A，这样每辆车跑两圈就完成了运砖任务.然后再派这 20辆车都从 A 运渣土到 B 再空车返回 A，则运渣土任务也完成了.这时总共空车跑了33040+300 2019200（米）.后一种调运方案比前一种减少跑空车 13200 米，这是最佳节油的调运方案。说明：“节省跑空车的距离”是物资调运问题的一个原则：下面通过例子再介绍“避免对流”的原则。例 2 一支勘探队在五个山头 A、B、C、D、E 设立了基地，人数如右图所示.为调整使各基地人数相同，如何调动最方便？（调动时不考虑路程远近）分析 在人员

3、调运时不考虑路程远近的因素，就只需避免两个基地之间相互调整，即“避免对流现象”。解：五个基地人员总数为17+4+16+14+9=60（人）依题意，调整后每个基地应各有605=12（人）。因此，需要从多于 12 人的基地 A、C、D 向不足 12 人的基地 B、E调人.为了避免对流，经试验容易得到调整方案如下：先从 D 调 2 人到 E，这样 E 尚缺 1 人；再由 A 调 1 人给 E，则 E 达到要求.此时，A 尚多余 4 人，C 也多余 4 人，总共 8 人全部调到 B，则B 亦符合要求。调动示意图如右图所示.这样的图形叫做物资流向图.用流向图代替调运方案，能直观地看出调运状况及有无对流现

4、象，又可避免列表和计算的麻烦，图中箭头表示流向，箭杆上的数字表示流量。说明：发生对流的调运方案不可能是最优方案.这个原则可以证明：如右图，设 A1B2a 千米， B2B1=b 千米，B1A 2c 千米.如果从 A1 运 1 吨货物到 B1，同时又从 A2 运 1 吨货物到 B2，那么在 B1B2 之间 A1 的物资从西向东运输，A2 的货物从东向西运输，两者发生对流，于是这样调动的总吨千米数为（a b）+（bc ）ac+2b.而如果从 A1 运 1 吨货物到 B2，同时从 A2 运 1 吨货物到 B1，栽蛟耸渥芏智 资 猘+c. 显然a+c a+c+2b。例 3 在一条公路上每隔 100 千米

5、有一个仓库（如右图，）共有 5 个仓库.一号仓库存有 10 吨货物，二号仓库有 20 吨货物，五号仓库存有 40 吨货物，其余两个仓库是空的。现在想把所有的货物集中存放在一个仓库里，如果每吨货物运输 1 公里需要 0.5 元运输费，那么最少要多少运费才行？分析 欲使花费的运输费少，关键在于运输的货物和路程尽可能少，实际经验告诉我们一个原则“小往大处 靠”.下面就以两地调运问题为例加以计算验证：如上图，在公路上 A、B 两地各有 10 吨、15吨麦子，问打麦场建在何处运费最少？设打麦场建在 C 点，则总运费是（假定每吨小麦运输 1 千米的费用是 a 元）W10 aAC15aBC10aAC 10a

6、 BC5aBC10a（AC BC）5aBC=10aAB5aBC上式中 10aAB 是固定的值，不随 C 点的选取而改变；只有 5aBC 随 BC 的变化而改变，若 BC 越小，则 W 也越小 .当 BC=0 时，即 C 点与 B 点重合时，W 的值最小.因此打麦场建在 B 点时总运费是10aAB（元）为最少.显然当打麦场建在 AB 线段之外时，总运费都大于 10aAB（元）。解：根据“小往大处靠”的原则，先把一号仓库的 10 吨货物送往二号仓库集中，需运费100.5100=500（元）。这时可以认为二号仓库有 30 吨货物，而五号仓库有 40 吨货物，于是又应把二号仓库的 30 吨货物运往五号

7、仓库集中，需运费300.5300=4500（元）。所以，把货物集中存放在五号仓库时所花运费最少，需要5004500=5000（元）。说明：“小往大处靠”的原则也不是一成不变的，具体问题还要具体分析。再举两例如下：例如一号仓库有 20 吨货物，二号仓库有 30 吨货物，其他仓库存货照样如前，那么应该往哪个仓库集中呢？首先仍应把一号仓库的 20 吨货物运往二号仓库集中，然后再把五号仓库的 40 吨货物也运往二号仓库集中，这样运费最少。又如一号仓库有 30 吨货物，二号仓库有 20 吨货物，其他仓库存货仍然如前，那么应该往哪个仓库集中呢？先把一号仓库的 30 吨货物运往二号仓库集中，再把五号仓库的

8、40 吨货物也运往二号仓库集中，这样运费最省.（想想为什么？）还有一点值得注意，在决定货物往何处集中时，起决定作用的是货物的重量，至于距离仅仅是为了计算运费.如果把本题中各个仓库之间的距离换成另外一些数值，仍应该把货物集中到五号仓库。本题可以推广为一般命题：“一条公路上有 n 个仓库，它们分别存货 A1 吨、A 2 吨、a n 吨.现在需要把所有的货物集中存放在一个仓库里，应该选取哪个仓库可以使总运输费最少？”它的解法将涉及到一次函数的知识，同学们在学过初三代数之后就会完全明白了。例 4 189 米长的钢筋要剪成 4 米或 7 米两种尺寸，如何剪法最省材料？分析 显然无残料的剪法是最优方案.于

9、是考虑二元一次不定方程的整数解问题。解：设 4 米长的剪 x 根，7 米长的剪 y 根，依题意列方程4x7y189。根据倍数分析法可知7x（即 x 是 7 的倍数）。令 x10，则 7y189，解出 y1=27；x 27，则 7y161，解出 y223；x 3=14，则 7y133，解出 y319；x 4=21，则 7y=105，解出 y4=15；x 528，则 7y=77，解出 y5=11；x 6=35，则 7y49，解出 y67；x 7=42，则 7y21，解出 y7=3。因此，有七种剪法都是最省材料的。说明：本例是最简单的下料问题，属于“线性规划”的范畴，线性规划是运用一次方程（组）、一

10、次函数来解决规划问题的数学分支。规划论研究的问题主要有两类：一类是确定了一项任务，研究怎样精打细算使用最少人力、物力和时间去完成它；另一类是在已有一定数量的人力、物力和财力的条件下，研究怎样合理调配，使它们发挥最大限度的作用，从而完成最多的任务。例 5 用 10 尺长的竹竿做原材料，来截取 3 尺、4 尺长的甲、乙两种短竹竿各 100 根，至少要用去原材料几根？怎么截法最合算？分析 不难想到有三种截法省料：截法 1：截成 3 尺、3 尺、4 尺三段，无残料；截法 2：截成 3 尺、3 尺、3 尺三段，残料 1 尺；截法 3：截成 4 尺、4 尺两段，残料 2 尺。由于截法 1 最理想（无残料）

11、，因此应该充分应用截法 1.考虑用原材料 50 根，可以截成 100 根 3 尺长的短竹竿，而 4 尺长的仅有 50 根，还差 50 根.于是再应用截法 3，截原材料 25 根，可以得到 4 尺长的短竹竿 50 根，留下残料22550（尺）。解：至少要用 75 根原材料，其中 50 根用截法 1，25 根用截法 3，这样的截法最省料.说明：一般说来，一定长度的条形材料要截取两种毛坯的下料问题，用本例的方法求解是比较省料的，这种解法的理论根据要用到二元不等式及一次函数图像，有兴趣的读者可参阅有关书刊。例 6 甲、乙两个服装厂每个工人和设备都能全力生产同一规格的西产 1200 套西服.现在两厂联合

12、生产，尽量发挥各自特长多生产西服，那么现在每月比过去多生产西服多少套？分析 根据已知条件，甲厂生产一条裤子与一件上衣的时间之比为 23，因此在单位时间内甲厂生产的上衣与裤子的数量之比也是 23（注意：在固定时间内，数量与每件所用时间成反比）；同理可知，在单位时间内乙厂生产上衣与裤子的数量之比是 34。单说明理由：如果甲厂生产 9 条裤子，则相当甲厂生产 6 件上衣；如果让乙厂生产这 6 件上衣，则相当于生产 8 条裤子.这就是说，甲厂生产 9 条裤子时乙厂只能生产 8 条裤子.显然甲厂善于生产裤子.类似地，如果乙厂生产 9件上衣，则相当于乙厂生产 12 条裤子；如果让甲厂生产这 12 条裤子，则相当甲厂生产 8 件上衣.这就是说，乙厂生产 9 件上衣时甲厂只能生产 8 件上衣.显然乙厂善于生产上衣.解：两厂联合生产，尽量发挥各自特长，安排乙厂全力生产上衣.由同时，安排甲厂全力生产裤子，则甲厂全月可生产裤子为了配套生产，甲厂先全力生产 2100 条裤子，这需要于是，现在联合生产每月比过去多生产西服（210060）-（9001200）=60（套）。说明：本例是线性规划中劳力组合问题.劳力组合最简单的情况就是效率比问题.这里给出多种劳力（或机械）干两种配套活的一般分工原则：