第十三讲 简单的统筹规划问题
引言
在人们的生产和生活活动中，经常面对这样的问题：怎样在尽可能节省人力、物力和时间的前提下，争取获得在可能范围内的最佳效果。这类问题，我们称之为统筹问题，也常常叫做最优化问题。
本课时我们将探讨有关物资调运，合理利用材料，合理利用时间，设计配套方案等问题。
了解它们的一般原则，解题思路等。
（一）物质调运问题
例1、某工地A处有20辆卡车，要把60车渣土从A运到B，把40车砖从C运到D，（工地道路图如图所示）问：如何调运，最节省汽油？
原则1、节省跑空车的路程
分析：不论怎样把渣土从A运到B或者把砖从C运到D，在装有货物是都无法节省汽油。只有设法减少跑空车的距离，才能节省汽油。
发挥你的聪明才智，看看怎样安排才能最节省汽油，用几种方案试一试，说出你的感受
方案一：派20辆车先把60车渣土运完，再派20辆车去把40车砖运完：
方案二：派这20车从A→B→C→D→A跑两圈，运40车渣土和40 车砖，再派20辆车都从A处运渣土到B处返回。
解：先派20辆车都从A开始运渣土到B，再空车开往C把砖到D，最后空车跑回A处，这样，两圈就可以运40车渣土和40车砖，最后派这20辆车都从A处运渣土到B后空返回，完成了所有任务。这时空车总共跑了（240+90）×40+300×20=19200（米）
2、避免对流原则
例2、一只勘探队在五个山头A、B、C、D、E设立了基地，人数如右图所示。为了使各基地人数相同，如何调动就方便？（调动时不考虑路程的远近）
右图叫做物资流向图，用利用流向图来表述调运方案，能直观地看出调运情况及有无对流现象。
有对流现象的调运方案不可能是最优化方案。
4
原则3、小往大处靠原则
例3、在一条公路上，每隔100 千米有一个仓库，（如图）共5个仓库。一号仓库里有10吨货物，二号仓库里有20 吨货物，五号仓库里有40吨货物。其余两个仓库是空的。现在想把所有的货物集中存放在一个仓库里，如果每吨货物运输1千米需要0.5元运输费，那么，怎样运输才能使运费最少？最少需要多少运费？
我们从最简单的情况开始分析
引例：公路上A、B两个仓库分别存有小麦10吨和15吨，相距10千米，问：打麦场建在何处运费最少？
C
设：打麦场建在离B第x千米的C处，每吨小麦每千米的运费为a元，
则A库小麦运往C处的费用是：a×10×（10－x）＝ 100a－10ax（元）
B处小麦运往C处的费用为a×15x＝ 15ax（元）
总费用为 100a－10ax＋15ax＝100a＋5ax （元）
我们看到：当a值确定时，这里100a是个定值，当x值越大，总运费也就越大，所以，只有当x=0时即B、C重合时总运费最小。由此我们可以得到原则：小往大处靠
解：因为一号与二号仓库的货物共有30吨，比五号仓库的40吨少，所以全部集中在五号仓库总运费最少，为
0.5×10×400＋0.5×20×300
＝2000＋3000＝5000（元）
答：
二、下料问题
例4 、189米长的钢筋要剪成4米或7米两种尺寸，如何剪法最省材料？
分析：显然，无余料是最优化方案，
设4米长的截x根，7米长的截y根，根据题意得：4x+7y=189
然后用不定方程的同余法求出共有7种截法，y≤27
7y≡3y≡189≡1(mod 4)
例5 、用10米长的竹竿做原材料，来截取3米、4长的甲、乙两种短竹竿各100根，至少要用去原材料几根?怎么截法最合算？
你能看出它与例4 的不同吗？
解：将10米的竹竿截成3米、4米的竹竿有三种方案：
①3、3、4三段（无余料）；
②3、3、3三段（余料1米）；
③4、4（两段余料2米）
根据无余料原则可知：可以用50根按截法①得到100根3米的，50根4米的，再取25根按截法③得到50根4米的。因此最少要用75根。
1.假设烙一个饼需要4分钟，每一面需要2分钟，一个烙饼锅每次正好可以烙两个，烙97张饼需要几分钟？
用时短的优先
2、学校大扫除，四位同学各拿大小不一的桶一同去打水，注满这些水桶，A需要5分钟，B需要3分钟，C需要4分钟，D需要2分钟。现只有一个水龙头，应如何安排这四个人打水次序使他们花费的等候时间总和最少，这个时间等于多少？
解根据用最短优先可知打水次序为D、B、C、A时等候的时间总和最少，
等候时间总和是
2×4＋3×3＋4×2＋5×1＝8＋9＋8＋5＝30（分钟）
（但最后一人走的时间不变，因此我们仍旧建议按先来后到较公平））
3、有一个80人的旅游团，其中男50人，女30 人，他们住的旅馆有11人、7人和5人的三种房间，男、女分别住不同的房间并且不能有空床，他们至少要住多少个房间？
分析：这个问题实际上就是求不定方程11x+7y+5z=50且满足x+y+z最小的整数解和不定方程11x+7y+5z=30且满足x+y+z最小的整数解
11x+7y+5z=50

z=
由(11x+7y)≡(x+2y)≡50≡0(mod 5)
及x≤4
得x=3,y=1,z=2
11x+7y+5z=30

z=
由(11x+7y)≡(x+2y)≡30≡0(mod 5)
及x≤2
得x=1,y=2,z=1
解：住房方案如下：男50人住3间11人间、1间7人间和2间5 人间；女30人住1间11人间、2间7人间和1间5人间。
所以他们至少要住10间客房。
4、A 、 B 、 C 、 D 、 E 、 F六座居民楼依次排在一条直线型的马路上，现要在这条马路上建造一个大型超市，那么应建在什么地方才能使这个超市到六座居民楼的总距离最近？
5.在一条公路上有4个工厂，任意相邻的两个工厂距离相等（如图所示）。现在要在这条公路上设一车站，使得这4个工厂的所有工人步行到车站的总路程最少，这个车站应设在几号工厂门口？
我们可以分类讨论看是在2、3、还是4处
解：可以将车站设在3处或4处
设每个工厂之间的路程为单位1，则车站设在3处时，工人步行到车站的总路程为100×2＋120×1＋80×0＋215×1＝535
车站设在4处时，工人步行的总路程为100×3＋120×2＋80×1＋215×0＝620
所以车站设在第三个工厂处。
课堂小结
节省跑空车的路程
1、物资调运 无对流原则
小往大处靠原则
2、下料问题 无余料原则
3、排队问题 用时短者优先原则