一 最优化问题

1、第一讲统筹与优化战国时期，齐威王与将军田忌赛马。规定从自己的上等马、中等马、下等马中各选一匹来赛。如果按 同等马相比，田忌的马都不如齐威王的马，看来田忌 要连输三局了。后来，田忌请教了当时著名军事家孙 膑，孙膑向田忌献策，设计了三种马出场的先后顺序:第一场：用下等马跟齐王的上等马比，田忌输了 一场；第二场：用上等马跟齐王的中等马比，田忌赢了 一场；第三场：用中等马跟齐王的下等马比，田忌又赢了一场。结果，田忌以二比一获胜，这就是历史上有名的“田 忌赛马”的故事。故事中巧妙地安排上、中、下三种 马出场参赛的顺序，就是一个“最优化”问题，这也 是著名数学家华罗庚先生生前积极推广和普及的“统 筹方法”

2、和“优选法”。通常我们所碰到的最优化问题，就是在某些条件 的限制下，通过科学地规划安排，合理地设计，找到 一种最佳方案，使所用的时间最少、或所耗的费用最 少、或所需的人力最少。在众多方案中寻求一种最 合理、最科学的方案，这就是统筹与优化。【例1】在一个漆黑的夜晚，A、B、C、D四个人 结伴同行，途中要经过一座木桥，这座木桥最多能承 受两个人的重量，如果单独过去A要1分钟，B要3 分钟,C要8分钟，D要12分钟，而此时四个人只有 一只手电简。请同学们帮助他们设计一种最佳的过桥 方法，使他们能在最短时间内通过这座桥？思路点拨：由于这座桥每次只能通过两个人，且 只有一只手电简。所以，必须两人同时过去

3、.然后让 其中一人回来送手电筒。四个人要用最短的时问通过 这座桥应从以下两方面考虑：一是返回送手电筒的人 用的时间越少越好，二是让用的时间最多的两个人一 起过桥。解 方案一:让两个用时较多的C、D 一起过桥。那 么第一次过桥的人应是A和B，用时3分钟。然后由 A用1分钟时问把手电筒送回来，交给C、D,这两个 人过桥时间为12分钟。再由B用3分钟时间送回手 电。再由A、B同时过桥用时3分钟，返回送手电简 用时1分钟。全部通过所用时问为：3+1+12+3+3 =22（分 ）.方案二:让用时最少的A去送其余三人。A先送D 过去，用时12分钟，然后用1分钟回来，A再送C 过去，用时8分钟，然后用1分钟

4、回来；A再和B过去，用时3分钟。全部通过所用时问为:12+1+8+1+3=25（分 ）.通过比较知，第一种方案用时较少。答：他们五人最短用22分钟通过这座木桥。1!【例2】妈妈让小明给客人烧水沏茶，洗开水壶 用1分钟，烧开水要用15分钟，洗茶壶要1分钟， 洗茶杯要1分钟，放茶叶要2分钟。小明算了一下， 完成这些工作要花20分钟。为了使客人早喝上茶， 按照你认为最合理的安排，多少分钟就能沏茶了？1!思路点拨:题要做的事中，花时间最长的是烧开水， 要15分钟。所以不管怎么安排，至少要15分钟才能沏上茶。但在烧开水 的同时，可以做洗茶壶、洗茶杯、放茶叶这三件事情.解小明先洗开水壶用1分钟，接着烧开水

5、用15分钟，在等待水开的过程中，同时洗茶壶、茶杯、拿茶 叶，水开7就沏茶，这样用的时间最省，最省时间为1+15=16 （分钟）。1!具体程序如下图:烧开水一沏茶洗水毒分钟）（1分钟）洗茶壶、洗茶杯、拿茶叶（1分钟）（1分钟）（2分钟）图1 1说明：这个例子告诉我们，在做一件事时，经常会 遇到如何统筹兼顾，科学安排，以加快工作进度，提 高工作效率的问题。为了省时间、提高效率，能同时 去做的事应尽量同时去做。【例3】车间里有5台机床同时出了故障，只有一个修理工，从第1台到第5台的修复，时间依次为 济损失5万元。那么应怎样安排修复顺序，使经济损 失最小？最小是多少元？15、 8、 29、 7、10分

6、钟。每台机床停产一分钟造成经思路点拨：5台机床总的修复与等待的时间越少， 经济损失越小，陪等修复时间长的机床越少越有利， 因此，让修复时间长的陪等修复时间短的。解总的等待与修复时间为：7X 5+8X4+10X3 + 15X2+29X 1=156 （分钟）损失5X156=780 （万元）答：修复顺序为第4台、第2台、第5台、第1 台，第3台，可使经济损失最少，此时最少的损失为 780万元。说明：例3是一个比较简单的排队问题，为了使 所用时间最少，在规划排队先后顺序时，应尽量让时 间用的少的排在前面。【例4】在一条公路上，每隔100千米有一个仓 库，共有5个仓库。1号仓库有10吨货物，2号仓库 有

7、20吨货物，5号仓库有40吨货物，其余两个仓库 是空的，现在想把所有的货物集中存放在一个仓库 里，如果每吨货物运输1千米需要0.5元运输费，那 么最少需要多少运费才行？-1 | 2 | 3 | 4 | 10吨 20吨40吨图1 3思路点拨：要使运费最少，必须综合考虑两个因 素：（1）运走的货物尽可能少；（2）要运货物运输的 路程尽可能短。一共有货物10+20+40=70 （吨），先比 较两端的货物，10 40，可以先把1号仓库中的10 吨运往2号仓库，这样2号仓库就有了 30吨，30 40，所以应该把2号的货物运往5号仓库。解 需要把货物都运往五号仓库，运费为：0.5X （10X4X100+2

8、0X3X 100） =5000 （元）想一想：若一号仓库有30吨货物，二号仓库有 20吨货物，其他仓库的货物不变，那么应该运往哪个 仓库集中呢说明：这是一个厂址设置问题，常见解决方法为:（1）如果只有两个原料产地，它们有一条公路相 连，要在公路上找一处（包括两个产地在内）设工厂， 使原料运输总量最少：如果两个原料产地产量一样，则工厂设在公路 的任一点（包括端点）都行。如果两个原料产地产量不相等，则工厂应设在l=J|三目产量较大的原料产地，即把原料少的产地的原料往产 量大的原料产地运，这叫“小往大靠”。1=（2 ）如果不止两个原料产地，它们分布在一个道 路设有圈的交通图上（图1-2）。先计算各原

9、料产地的原料总和，然后看各原料产地的产量， 若小于总和的一半，则把它运往前一站， 这叫“抓各端，小半进一站”。反复运用 这一原理，最后看原料都集中何处，这 处便是厂址，它能使原料运输总量最少。【例5】甲、乙两厂生产同一型号的西服，甲厂每 月用16天的时间生产上衣，用14天的时间生产裤子， 共生产896套西服；乙厂每月用12天的时间生产上 衣，用18天的时间生产裤子，共生产1440套西服。 现在两个工厂合并，问每月（按30天计算）最多能 生产多少套西服？思路点拨：安排生产时要发挥每个厂子的生产优 势，让善于生产上衣的去生产上衣，让善于生产裤子 的去生产裤子。甲厂每天生产上衣：89616=56（件

10、）， 裤子：896! 14=64 （条）；乙厂每天生产上衣：1440 4-12=120 （件），裤子：1440! 18=80 （条）。可知， 甲厂生产裤子快，乙厂生产上衣快。让甲厂专门生产 裤子，乙厂先生产上衣与之配套，然后再独立生产。解 甲厂一个月可生产裤子：896 -14 X 30=1920 （条）乙厂先生产上衣1920件与之配套，需1920 -（1440+12 ） =16 （天）乙厂在剩下的30-16=14 （天）中，可生产（1440 + 30）X 14=672 （套）两厂共生产：1920+672=2592 （套）答每月最多能生产2592套西服。I=J说明：科学安排要坚持两个原则：一是效

11、率优先， 即让每个车间生产比另一个车间产量高的那种产品； 二是成套生产，生产的上衣和裤子必须完全配套。的装卸工太多会造 部分工人跟车。那么 田人固定，才能使装【例6】某公司运输队有2辆汽车，为4个工厂 作循环运输，每个工厂需配备的装卸工如图1-6所示。 如果每个工厂固定 成人力浪费，可以让 派多少人跟车，怎样 卸工的总人数最少？思路点拨：先假定所有的装卸工都在各点等车， 我们从每一个点抽出一名装卸工（共抽4人），每辆 车上安排一人（共2人），则汽车到各点的装卸工的 人数未变，但装卸工的人数可节约2人。装卸工人数最少的工厂是4人，这样抽了 4次后， 各点人数为A（4人）、B（2人）、C（0人）、

12、D（1人）, 此时人数不为0的点还有3个：A、B、D，多于车辆 数2,可以再从这三个点各抽1人，每辆车上再多派 1人，又可节约1人。若再继续抽调调整的话，装卸工人总数不会再减少， 这时装卸工的总数是：5X2+3+1=14 （人）其中每辆车上5人。每个工厂的 人数分别为:A （3人）、B （1人）、C （0人）、D （0人） 想一想：若车队派出3辆车，怎样安排才能使装 卸工的人数最少？说明：这类题我们可以采用“逐步调整法”来验 证这一调整方案是否最优的。注意，只有当人数不为 0的工厂的数量不大于车的数量时，才停止抽调。【例7】仓库里存有一批8米长的钢筋，现在要截 出3米长的毛坯40根，2米长的毛

13、坯40根，试设计 最省料的下料方案。问要几根原材料？思路点拨：最合理下料方案就是8米长的钢筋截取后所余下的废料最少。可以把一根8米长的钢筋截 成两种毛坯的不同方法一一枚举，如下表所示。然后 把不同方法综合起来，便达到题目的要求，构成一个 下料方案。毛云数3米2102米124残料010解要使原材料最省，应该尽量不用有残料的方 案二。从表上看出，要截3米毛坯40根，如果用方 案一截20根原材料，这时得到了 3米毛坯40根，2 米毛坯20根，再用方法三截5根原材料，可得2米 毛坯20根，合起来正好满足题目要求。说明：一般来说，一定长度的材料要截取几种毛 坯的下料问题，常常先通过枚举法列出几种截取方

14、法，通过分析、比较，看哪几种方法残料比较少，然 后得出最佳的下料方案。【例8】北京和上海同时制成计算机若干台，北京i=可调运外地10台，上海可调运 外地4台，现决定给重庆8台， 汉口 6台，若每台计算机的运 费如下表，怎样调运使运费最 省？r=i思路点拨：先作图（见图1-7），使题中的条件集 中在图上反映出来，便于分析。根据“就近分配”的 原则，先就近分配，然后进行适当调整。假如上海的 4台全发运汉口，北京10台发重庆8台，发汉口 2台, 这时总运费为 800 X 8+400 X 2+300 X 4=8400 （元）。这 时我们设想，北京一台改发汉口，节省运费400元， 上海发汉口改为发重庆，

15、经费增加200元，合计节省 运费200元，于是将上海4台全发往重庆，北京发重 庆的4台改发汉口，一共可节省200X4=800 （元） 这时总运费为8400-800=7600元。解上海4台发往重庆，北京发4台至重庆，6台 至汉口，总运费为：500 X 4+800 X 4+400 X 6=7600（元）答：上海4台发往重庆，北京发4台至重庆，6台 至汉口。说明：在确定最佳方案的过程中，要注意调整、 比较的方法，本题中应该先比较一下需要量多运费也 多的地方如何运最省。练习一用一只平底锅煎饼，每次只能放2个饼，煎一个 需要2分钟（正、反面各1分钟）。问：（1）煎三个 饼至少需要几分钟？怎样煎？（2）煎

16、n个饼（nN3） 至少需要几分钟？煎三个饼需要3分钟.方法:两个饼先煎一面，1分 钟后，拿下一个饼,另一个翻面并放上第三个饼，再煎 1分钟，一个饼已煎好,把拿下去的饼及第三个饼都翻 一面再煎1分钟就都煎好了.煎n个饼用n分钟，当n为奇数时，先用上法煎 三个饼，用去3分.余下偶数个饼，每两个饼用2分 钟煎。1!1!小明骑在牛背上赶牛过河，共有甲、乙、丙、丁 4 头牛。甲牛过河需2分钟。乙牛过河需3分钟，丙牛 过河需6分钟，丁牛过河需7分钟。每次只能赶两头 牛过河，那么小明要把这4头牛都赶到对岸，最少要 用几分钟？18分钟提示：甲、乙先过，甲回来，丙、丁 起过，乙回来，最后甲、乙过。1!小明早晨起

17、来淘米要2分钟，插上开关用电饭锅烧 饭要18分钟，背外语单词要12分钟，刷牙洗脸要3分钟，吃早饭要8分钟，小明经过合理安排，起床后多少分钟就能上学了？他是怎样合理安排的?28分钟，安排顺序如图:烧饭分钟2W吃饭8分钟上学某加油站能够对两辆车同时进行加油，现在有6 辆车同时来到加油站加油，各辆车加油所需时间分别为：A车7分钟，B车5分钟，C车4分钟，D车10分钟，E车3分钟，F车2分钟,问：加油站怎样安排加油顺序，才能使这6辆车加油总共需要的时间最 短？这6辆车分两组加油，顺序是F、C、A和E、B、D 一共需要的时间是：3 X (2+3)+2 X (44-5) + (7+10)=50(分),也可

18、以分为 F、B、A 和 E、C、 D两组，并按此顺序加油总时间也是50分.李乡长下乡召开甲、乙、丙、丁四个村的干部会议,这些村都相距4千米，如图1-8。参加会议的人数分别为7人、6人、2人、8人，请你想一想，李乡长在哪个村召开会议最为合理。乙处如图，是某个城市的部分街道图，相邻两个交点 之间的连线表示道路，连线旁标注的数表示该道路在 单位时间内最多可以通过的汽车数.现从A点向B点 发车,汽车可以分开沿不同的路线行驶,那么,在单位时间内最多可以通过多少辆汽车?19 辆 提示：3+4+6+6=19（辆）l=J|三目l=J有284吨货物运往“希望工程”，大卡车载重量为8 吨，小卡车载重量为4吨，它们

19、的耗油量分别为12 升和7升，用大小车各多少辆参加运输，耗油量最少？35辆大卡车，1辆小卡车提示：大卡车每吨耗油 量少，应尽量安排大卡车工地上有手推车20辆，其中10辆从A到B运垃圾， 要60车次运完，另外10辆从C到D运砖块，要40 车次运完。各地距离如图所示（单位：米）。有人说 这样的安排不合理，因为跑空车的路程可以再少些。 那么，怎样安排才合理呢？运垃圾和运转头的车都不必返回，按ABCDA 的顺序循环运输，使运垃圾和运转头交替进行。每走 一圈空车路程由360米、300米分别缩短为90米、240 米。彩虹服装公司的A, B两个制衣车间，生产同 澈式的西服。A车间每月生产这种西服600套，其

20、中生产上衣需18天，生产裤子需12天。B车间每月 也可以生产这种西服600套，其中生产上衣和裤子各 需15天。如果让两个车间合作，则可以提高每个月 的产量。A, B两个车间应怎样合作生产，可以使每 月产量达到最大？最大月产量是多少套？(每月按30 天计算)1320套 提示:比较可知,A生产裤子的效率比B高,B生产上衣的效率比A高，让B用30天时间生产上 衣，共生产上衣1200件，A生产裤子与之配套，用时 1200+ (600+12)= 24天，剩下6天可生产西服(600 + 30 ) X 6=120 (套)，因此，最大月产量是1200+120=1320 （套）。解放军某部有4辆汽车，要陆续派往A、B、C、 D、E五个地方执行循环运输任务，各 点所需装卸战士人数如图1-9所示。装 卸的战士可以固定在装卸地，也可以跟 车流动，问怎样安排才能使装卸战士人 数最少？最少要多少人？每辆车跟车4人，A、C各固定1人，B固定2人，共 需 4X4+1 X2+2=20（人） 11.仓库内有一批14米长的钢筋，把它们割成3米 长的和5米长的各50根。试设计最省料的下料方案， 问最少要几根钢筋？最少要30根提示：割成3根3米和1根5米的钢筋 需10根，割