1、第九讲 统筹规划 统筹方法，是一种研究如何安排工作进程的方法为什么要合理安排工作进 程呢？我们举一个例子 比如，想泡壶茶喝茶叶有，但还没有烧水，而且水壶、茶壶、茶杯都没有 洗过怎么办？ 办法一：洗水壶，灌上凉水，放在火上；在等待水开的时间里，洗茶壶、洗 茶杯、拿茶叶；等水烧开了，泡茶 办法二：洗水壶、茶壶、茶杯，拿茶叶；一切就绪，灌水烧水；等水烧开了， 泡茶 办法三：洗水壶，灌上凉水，放在火上，坐待水开；水开了之后，洗茶壶、 茶杯，拿茶叶，再泡茶 我们很容易看出第一种办法最好，后两种办法多多少少都浪费了时间 在这个简单的例子中，有些工作可以同时做，比如烧水时可以洗茶壶、拿茶 叶有些工作有先后顺
2、序的要求，比如洗水壶要安排在烧开水之前，而不能水烧 开了再去洗水壶如何根据实际情况，合理地安排工作顺序，使得总时间或总花 费最少，正是统筹法研究的问题 例题 1 萱萱中午做一道菜，共需要七道工序，每道工序的时间如下：切豆腐 2 分钟，切肉片 2 分钟，准备葱姜蒜 3 分钟，准备佐料 1 分钟，烧热 锅 2 分钟，烧热油 2 分钟，炒菜 4 分钟请问萱萱烧好这道菜最短需 要多少分钟？ 分析分析有哪些工序能同时做？哪些工序必须考虑先后顺序？ 练习 1 妈妈让冬冬给客人烧水沏茶洗开水壶要用 1 分钟，烧开水要用 15 分钟， 洗茶壶要用 1 分钟，洗茶杯要用 1 分钟，拿茶叶要用 2 分钟冬冬估算了
3、一下， 完成这些工作要花 20 分钟为了尽快给客人沏茶，你认为最合理的安排，最少 需要多少分钟？ 有很多工作需要做时，我们把能同时做的工作同时做，可以节约时间如果 都不能同时做，就要合理安排工作的顺序 例题 2 小杂货店里有一位售货员卖货， 同时来了 A、 B、 C、 D、 E 五个顾客 A 买糖果需要 2 分钟；B 买大米需要 6 分钟；C 买香烟和啤酒需要 4 分 钟；D 买水果需要 3 分钟；E 买蔬菜需要 5 分钟请问：售货员应该 如何安排五个人的顺序， 使得这五个人排队等候所用时间的总和最少？ 最少是多少？（只计算每个人排队的时间，不计算买东西的时间） 分析分析如果只有 A、B 两个
4、顾客，为了让等候时间最少，应该安排谁先买？如 果只有 A、B、C 三个顾客呢？五个顾客呢？ 练习 2 理发店里只有一位理发师，但同时来了五位顾客，理发师一次只能给一位顾 客理发 由于顾客要求的发型不同， 理发师给这五位顾客理发分别需要 10、 12、 16、20、25 分钟怎样安排他们理发的顺序，才能使这五人排队等候所用时间 的总和最少？最少是多少？ 在统筹规划问题中，我们往往需要找到最短时间、最短距离、最少花费等最 优方案在这类问题中，比较和调整是常用技巧当我们不能直接得到最优方案 时，可以从一个可行的方案出发，通过适当的调整让方案更优如果任何调整都 不能使方案更优，此时的方案就是最优方案
5、例题 3 下图是一张道路图，每段路旁标注的数字 表示小山羊走完这段路所需的分钟数请 问：小山羊从 A 出发走到 B 最快需要多少 分钟？ 分析分析走完右下角的两条路各需要 3 分钟和 4 分 钟， 这两条路的途中没有其他岔路可以走，能否把这两条路看成一条用时 7 分钟 的路呢？小山羊走不走这条路呢？ 练习 3 下图是某城市的道路图，每段路旁标注的数字表 示走完这段路所需用的分钟数（单位：分钟） 邮递 员从 A 点沿道路到达 B 点至少要经过多长时间？ B A 8 2 10 6 4 3 1 5 3 4 5 8 A B 10 8 5 3 9 11 4 2 1 5 7 例题 4 如图，一条路上从西向
6、东有 A、B、C、D、E 五所学校，分别有 200 人、300 人、 400 人、500 人、600 人任意相邻的两所学校之间的距离都是 100 米现在要 在某所学校的门口修建一个公共汽车站，要使所有人到达车站的距离之和最小， 车站应该建在什么地方？这时距离之和是多少？ 分析分析A、B、C、D、E 五所学校，把车站建在位于中间的 C 学校门口时总 距离是最小的吗？用不用把车站向左调整到 B？或者向右调整到 D 呢？ 练习 4 有八个村庄 1 A， 2 A， 3 A， 4 A， 5 A， 6 A， 7 A， 8 A分布在公路两侧，由一些 小路与公路相连现要在公路上设一个汽车站，并且使得汽车站到各
7、村庄的距离 之和最小，车站应设在哪里？ 例题 5 北京和上海分别制成同样型号的车床 10 台和 6 台这些车床准备分配给武汉 11 台、西安 5 台， 每台车床的运费如下图所示，单位为百元那么 总运费最少是多少元？ 分析分析无论是北京还是上海，把设备运到武汉都比运西安更便宜，但又不 能不给西安运从北京或上海运往西安的运费分别是每台 900 元和 1000 元，是 不是西安的 5 台都由北京提供呢？这样会使总运费最少吗？ A B C D E B C D E F G H I 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 终点 起点 武汉 西安 北京 5 9 上海 7 10 例题
8、6 西点店里卖的面包都是 5 个一袋或 3 个一袋的，不拆开零售已知 5 个一袋的售价是 8 元，3 个一袋的售价是 5 元，要给 47 位同学每人 发 1 个面包最少要花多少钱？ 分析分析买东西要想花钱少，必然是东西越便宜越好5 个一袋的售价是 8 元，3 个一袋的售价是 5 元，这两种哪一种更便宜呢？能否全买便宜的这种呢？ 课堂内外 丁谓施工 宋代沈括的梦溪笔谈记载有这样一个故事：祥符中，禁火时丁晋公主营复宫 室，患取土远，公乃令凿通衢取土，不日皆成巨堑乃决汴水入堑中，引诸道竹木排筏 及船运杂材，尽自堑中入至宫门事毕，却以斥弃瓦砾灰尘壤实於堑中，复为街衢一 举而三役济，计省费以亿万计 描述
9、的是中国古代有一个丁谓施工的故事，蕴含着运筹学的思想 传说宋真宗在位时，皇宫曾起火一夜之间，大片的宫室楼台殿阁亭榭变成 了废墟为了修复这些宫殿，宋真宗派当时的晋国公丁谓主持修缮工程当时， 要完成这项重大的建筑工程，面临着三个大问题：第一，需要把大量的废墟垃圾 清理掉；第二，要运来大批木材和石料；第三，要运来大量新土不论是运走垃 圾还是运来建筑材料和新土，都涉及到大量的运输问题如果安排不当，施工现 场会杂乱无章，正常的交通和生活秩序都会受到严重影响 丁谓研究了工程之后，制订了这样的施工方案：首先，从施工现场向外挖了 若干条大深沟，把挖出来的土作为施工需要的新土备用，于是就解决了新土问 题第二步，
10、从城外把汴水引入所挖的大沟中，于是就可以利用木排及船只运送 木材石料，解决了木材石料的运输问题最后，等到材料运输任务完成之后，再 把沟中的水排掉，把工地上的垃圾填入沟内，使沟重新变为平地 简单归纳起来，就是这样一个过程：挖沟（取土）引水入沟（水道运输） 填沟（处理垃圾） 按照这个施工方案，不仅节约了许多时间和经费，而且使工地秩序井然，使 城内的交通和生活秩序不受施工太大的影响，因而确实是很科学的施工方案 实可谓“丁渭施工，一举三得” ，成为中国古代项目管理实践中非常典型的进行 统筹规划的案例 作业 1. 早晨，妈妈起来准备早饭她烧开水需要 8 分钟，灌开水需要 1 分钟，擦桌子需要 5 分钟，
11、下楼拿牛奶需要 6 分钟，煮牛奶需要 6 分钟如果灶台上只有一个灶头，请问妈 妈准备早饭最少需要多少分钟？ 2. 四个人各拿一个大小不同的水壶在饮水机前打水，他们打水所需的时间分别是 1 分钟、 2 分钟、 3 分钟和 5 分钟 由于饮水机只有一个出水口， 请你适当安排他们打水的顺序， 使所有人排队和打水所用时间的总和最少这个总时间最少是多少？ 3. 下图是萱萱家附近的道路图，其中 A 地是萱萱家，B 地是学校各段路的路况不同，萱 萱走每段路所用的时间都已经标在图中（单位：分钟） 请问萱萱从家走到学校最少需 要多少分钟？ 4. 一条直街上有五栋楼， 相邻两栋楼的距离都是 50 米 这五栋楼从左
12、到右编号为 l、 2、 3、 4、5，楼里分别有 1 名、2 名、3 名、4 名、5 名职工在 A 工厂上班A 厂计划在直街上 建一个班车站接送这五栋楼的职工上下班， 为使这些职工到班车站所走的路程之和最小， 车站应建在距 l 号楼多少米处？ 5. 中国和美国分别制成了同一型号的大型电子计算机若干台 除本国外， 中国可以支援外 国 100 台，美国可以支援外国 40 台现在决定给日本 80 台，印度 60 台若每台大型 计算机的运费如下表所示（单位：万元） ，应该如何调运才能使总运费最省？请算出最 少的运费 日本 印度 中国 3 6 美国 9 14 A B 10 3 3 5 2 8 4 3 5
13、 第九讲 统筹规划 1. 例题 1 答案：12 分钟分钟 详解：炒菜这道工序必须要等前面六道完成后才能去做，所以要放到最后；切豆腐、切肉片、 准备葱姜蒜和准备佐料这四道工序都需要萱萱亲自完成，不可能一次同时做其中的两项；烧热 锅和烧热油这两道工序比较特别，可以在做的时候同时去做其它事情，故最少需要 223 1412 分钟 2. 例题 2 答案：按照 A、D、C、E、B 的顺序购买；30 分钟 详解：第一个人买东西时，有 4 个人等着；第二个人买东西时，有 3 个人等着因此尽可能 让 用 时 较 少 的 人 先 买 ， 即 按 照 A 、 D 、 C 、 E 、 B 的 顺 序 购 买 ， 这
14、样 共 需 要 等 待 2433425130分钟 3. 例题 3 答案：18 分钟 详解：先将左上角和右下角没有岔路的拐弯看成一条路，如图 1观察发现，如果要从 C 到 D， 经过 E 的路线比直接走更省时间因此 CD 之间的路实际上没有用，可以将它去掉类似的， 我们也可以去掉右下角长为 7 的路得到图 2这样容易看出，沿着 51102 的路线前进， 是最省时间的，用时为5 1 10218 分钟 4. 例题 4 答案：D 校；220 千米 详解：因为 C 校处在所有学校的中间，我们以 C 校为起点开始调整 如果车站从 C 校搬到 D 校，A、B、C 三所学校的200300400900名学生每人
15、要多走 100 米，而 D、E 两所学校的5006001100名学生每人要少走 100 米这样受益者更多，所以我 们先把车站搬到 D 校 如果继续搬到 E 校的话，A、B、C、D 四所学校的2003004005001400名学生每人多走 100 米， 而只有 E 校的 600 名学生每人少走 100 米， 所以不再向 E 校搬， 车站就修在 D 校门口 以千米为单位算出总路程为0.3 2000.2 3000.1 4000.1 600220 千米 5. 例题 5 答案：10700 元 详解：把一台设备从运到武汉改为运到西安，北京的厂家要多付 400 元运费，而上海的厂家要 图 2 B A 2 1
16、0 4 3 1 5 5 8 E 图 1 B A 14 2 10 4 3 1 5 7 5 8 C D E 多付 300 元运费，所以西安的设备都由上海提供时，能节省更多的运费这时上海需要给西安 提供 5 台设备，给武汉提供 1 台设备，北京给武汉提供 10 台设备，最少运费为 10 5 100 1 7 1005 10 10010700 元 6. 例题 6 答案：76 元 详解：5 个一袋的（后用表示）共个一袋的（后用表示）共 8 元，平均每个元，平均每个 1 元元 6 毛；毛；3 个一袋的（后用表示）共个一袋的（后用表示）共 5 元，平均每个要超过元，平均每个要超过 1 元元 6 毛，所以要尽量
17、多的买；毛，所以要尽量多的买； 共要给共要给 47 个同学买，所以可以买个同学买，所以可以买 9 袋，另外买袋，另外买 1 袋，共花费袋，共花费8 95 177 元；元； 但是，这个时候会多出一个，还是有点浪费，如果少买但是，这个时候会多出一个，还是有点浪费，如果少买 1 袋，则需要买袋，则需要买 3 袋，共花费袋，共花费 8 85 379 元，且浪费元，且浪费 2 个，更不划算；个，更不划算； 如果少买如果少买 2 袋，则需要买袋，则需要买 4 袋，此时，共花费袋，此时，共花费8 75 476 元，此时，花费最少，元，此时，花费最少， 而且没有浪费而且没有浪费 再减少，则不再划算了再减少，则
18、不再划算了 7. 练习 1 答案：16 分钟 详解：先洗开水壶，接下来烧开水的同时洗茶壶、洗茶杯、拿茶叶，共用时烧开水的同时洗茶壶、洗茶杯、拿茶叶，共用时1 1516分钟分钟 8. 练习 2 答案：按照 10-12-16-20-25 的顺序；128 分钟 详解：与例题 2 方法相同，最少需要10 4 12 3 16 220 1 128 分钟 9. 练习 3 答案： 18 分钟 简答：如图，逐步简化，去掉没有必要的路线 10. 练习 4 答案： E 到 F 之间的任意一点 简答：和例题 4 同理，应用调整法，汽车站应当建在 E 到 F 之间的任意一点 11. 作业 1 答案：14 分钟 简答：烧
19、开水时可以下楼拿牛奶，煮牛奶时可以灌开水、擦桌子 A B 15 8 3 20 4 2 1 5 7 A B 8 3 4 2 1 A B 8 3 4 2 1 5 7 12. 作业 2 答案：21 分钟 简答：花费时间少的人先打，注意本题要计算打水时间，1 42 33 25 121 分钟 13. 作业 3 答案：12 分钟 简答：如图进行化简易得最少需要4812分钟 14. 作业 4 答案：150 米 简答：先假设车站建在中间的 3 号楼处如果挪动到 4 号楼，有1236人多走 50 米，有 459人少走 50 米， 因此建在 4 号楼更好 如果从 4 号楼挪动到 5 号楼， 有123410 个 人多走 50 米，有 5 个人少走 50 米，因此建在 4 号楼是最好的，这时车站与 1 号楼相距 150 米 15. 作业 5 答案：中国给印度 60 台、给日本 40 台，美国给日本 40 台；840 万元 简答：同一台机器，目的地从日本换成印度，从中国运出时运费需要增加 3 万元，从美国运出 时运费需要增加 5 万元因此尽可能由中国供给印度，即中国给印度 60 台，给日本 40 台，美 国的 40 台都给日本运费共60 640 340 9840 万元 A B 10 3 3 5 2 4 3 5 A B 10 3 4 5 8
