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