文档文本内容
使学习渐入“加”境;让思维“海”阔天空
兰海&姜付加&吴忠 |
1
统筹与最优化练习题
一. 夯实基础:
1. 一只平底锅上最多只能煎两张饼,用它煎1 张饼需要2 分钟(正面、反面各1 分钟).问:
煎2009 张饼需几分钟?
2. 小强、小明、小红和小蓉4 个小朋友效游回家时天色已晚,他们来到一条河的东岸,要
通过一座小木桥到西岸,但是他们4 个人只有一个手电筒,由于桥的承重量小,每次只
能过2 人,因此必须先由2 个人拿着手电筒过桥,并由1 个人再将手电筒送回,再由2
个人拿着手电筒过桥……直到4 人都通过小木桥.已知,小强单独过桥要1 分钟;小明
单独过桥要1.5 分钟;小红单独过桥要2 分钟;小蓉单独过桥要2.5 分钟.那么,4 个人
都通过小木桥,最少要多少分钟?
3. 6 个人各拿一只水桶到水龙头接水,水龙头注满6 个人的水桶所需时间分别是5 分钟、4
分钟、3 分钟、10 分钟、7 分钟、6 分钟.现在只有这一个水龙头可用,问怎样安排这6
人的打水次序,可使他们总的等候时间最短?这个最短时间是多少?
4. 理发室里有甲、乙两位理发师,同时来了五位顾客,根据他们所要理的发型,分别需要
10、12、15、20 和24 分钟,怎样安排他们理发的顺序,才能使这五人理发和等候所用
时间的总和最少?最少时间为多少?
5. 有一家五口人要在夜晚过一座独木桥.他们家里的老爷爷行动非常不便,过桥需要12
分钟;孩子们的父亲贪吃且不爱运动,体重严重超标,过河需要时间也较长,8 分钟;
母亲则一直坚持劳作,动作还算敏捷,过桥要6 分钟;两个孩子中姐姐需要3 分钟,弟
使学习渐入“加”境;让思维“海”阔天空
兰海&姜付加&吴忠 |
2
弟只要1 分钟.当时正是初一夜晚又是阴天,不要说月亮,连一点星光都没有,真所谓
伸手不见五指.所幸的是他们有一盏油灯,同时可以有两个人借助灯光过桥.但要命的
灯油将尽,这盏灯只能再维持30 分钟了!他们焦急万分,该怎样过桥呢?
6. 5 所学校A,B,C,D,E 之间有公路相通,图中标出了各段公路的千米数,现在想在某所学
校召开一次学生代表会议,应出席会议的A,B,C,D,E 校分别有6 人,4 人,8 人,7 人,
10 人,为使参加会议的代表所走的路程总和最小,会议应选在哪个学校召开?
2
2
2
3
4
A
B
D
E
C
二. 拓展提高:
7. 在一条公路上,每隔100 千米有一座仓库,共有8 座,图中数字表示各仓库库存货物的
重量(单位:吨),其中C、G 为空仓库.现在要把所有的货物集中存入一个仓库里,如
果每吨货物运输1 千米需要0.5 元,那么集中到那个仓库中运费最少,需要多少元运费?
8. 一支勘探队在五个山头A、B、C、D、E 设立了基地,人数如下图所示.为调整使各基地
人数相同,如何调动最方便?(调动时不考虑路程远近)
17
4
16
14
9
A
B
C
D
E
60
10
5
20
10
30
H
G
F
E
D
C
B
A
使学习渐入“加”境;让思维“海”阔天空
兰海&姜付加&吴忠 |
3
9. 下图是一张道路示意图,每段路上的数字表示小明走这段路所需要的时间(单位:分).小
明从A 到B 最快要几分钟?
10. 新建的自来水厂要给沿公路的十个村庄供应自来水(如下图,距离单位为千米),要安装
水管有粗细两种选择,粗管足够供应所有村庄使用,细管只能供一个村用水,粗管每千
米要用8000 元,细管每千米要2000 元,如果粗细管适当搭配,互相连接,可以降低费
用,怎样安排才能使这项工程费用最低?费用是多少元?
11. 某工地A 有20 辆卡车,要把60 车渣土从A 运到B,把40 车砖从C 运到D(工地道路图
如下所示).问如何调运最省汽油?
三. 超常挑战
12. 北京和上海同时制成了电子计算机若干台,除了供应本地外,北京可以支援外地10 台,
H
G
F
E
D
C
B
A
7
5
6
5
0
4
6
4
6
3
3
4
1
5
2
2
2
3
2
4
2
5
30
J
I
H
G
F
E
D
C
B
A
自来水厂
使学习渐入“加”境;让思维“海”阔天空
兰海&姜付加&吴忠 |
4
上海可以支持外地4 台.现决定给重庆8 台,汉口6 台,若每台计算机的运费如右表,
上海和北京制造的机器完全相同,应该怎样调运,才能使总的运费最省?最省的运费是
多少?
13. 设有十个人各拿着一只提桶同时到水龙头前打水,设水龙头注满第一个人的桶需要1 分
钟,注满第二个人的桶需要2 分钟,…….如此下去,当只有两个水龙头时,如何巧妙
安排这十个人打水,使他们总的费时时间最少?最少的时间是多少?
14. 有十个村庄,座落在从县城出发的一条公路上,现要安装水管,从县城供各村自来水.可
以用粗、细两种水管,粗管每千米7000 元,细管每千米2000 元.粗管足够供应所有各
村用水,细管只能供应一个村用水,各村与县城间距离如下图所示(图中单位是千米),
现要求按最节约的方法铺设,总费用是多少?
5
8
3
4
上海
北京
重庆
汉口
发站
运费/元
到站
A 10
A 9
A 8
A 7
A 6
A 5
A 4
A 3
A 2
A 1
5
2
2
2
3
2
4
2
5
30
县城
使学习渐入“加”境;让思维“海”阔天空
兰海&姜付加&吴忠 |
5
四.杯赛演练:
15. (三帆中学分班考试题)有七个村庄
1A ,
2
A ,
,
7
A 分布在公路两侧(见右图),由一些
小路与公路相连,要在公路上设一个汽车站,要使汽车站到各村庄的距离和最小,车站
应设在哪里?
公路
A 6
A 5
A 7
A 4
A 3
A 2
A 1
F
E
D
B
C
使学习渐入“加”境;让思维“海”阔天空
兰海&姜付加&吴忠 |
6
答案:
1. 在不浪费时间的情况下:两张饼可同时煎完,三张饼也可以:首先A,B 的正面,然后拿
走A,煎B 的反面和C 的正面,然后拿走B,煎A,C 的反面. 2009
2 1003
3
,完全可
以不浪费时间煎完,从而所需时间为:2009 2
2
2009
分钟.
2. 方法一:要想用最少的时间,4 人都通过小木桥,可采用让过桥最快的小强往返走,将
手电筒送回,这样就能保证时间最短了.
第一步:小强与小明一起过桥,并由小强带手电筒返回,共用:1.5 1
2.5
(分钟);
第二步:返回原地的小强与小红过桥后再返回,共用了2 1
3
(分钟);
第三步:最后小强与小蓉一起过桥用了2.5 分钟;
所以,4 个人都通过小木桥,最少用2.5
3
2.5
8
(分钟).
方法二:要想用最少的时间,4 人都能过桥,保证时间最短还可以:
第一步:小强与小明一起过桥,并由小强带手电筒返回,共用:1.5 1
2.5
(分钟);
第二步:返回原地的小红与小蓉过桥后再由小明带手电返回,共用了2.5 1.5
4
(分钟);
第三步:最后小强与小小明一起过桥用了1.5 分钟;
所以,4 个人都通过小木桥,最少用2.5
4 1.5
8
(分钟).
3. 第一个人接水时,包括他本人在内,共有6 个人等候,第二个人接水时,有5 个人等候;
第6 个人接水时,只有他1 个人等候.可见,等候的人越多(一开始时),接水时间
应当越短,这样总的等候时间才会最少,因此,应当把接水时间按从少到多顺序排列等
候接水,这个最短时间是3 6
4 5
5 4
6 3
7 2 10
100
(分).
4. 一人理发时,其他人需等待,为使总的等待时间尽量短,应让理发所需时间少的人先
理.甲先给需10 分钟的人理发,然后15 分钟的,最后24 分钟的;乙先给需12 分钟的
人理发,然后20 分钟的,甲给需10 分钟的人理发时,有2 人等待,占用三人的时间和
为(10 3
)分;然后,甲给需 15 分钟的人理发,有1 人等待,占用两人的时间和为(15 2
)
分;最后,甲给需 24 分钟的人理发,无人等待.甲理发的三个人,共用(10 3 15 2
24
)
分,乙理发的两个人,共用( 12 2
20
) 分.总的占用时间为
10 3 15 2
24
12 2
20
128
(
)(
)
(分).
5. 首先姐姐跟弟弟一起过,用时3 分钟,姐姐再回去送油灯,用时3 分钟,老爷爷跟爸爸
一起过河,用时12 分钟,弟弟将灯送回去,用时1 分钟,弟弟和母亲一起过,用时6
分钟,弟弟送灯过河,用时1 分钟,最后与姐姐一起过河,用时3 分钟.一共用时:
3
3 12 1 6 1 3
29
(分钟).最后能够安全全部过河.
6. 根据小往大靠的原则,A 处的人数相对BCDE 的总人数要小很多,因此首先排除A 地,而
B,C,D,E 不能简单比较出.枚举结果如下:
B 地集合:共行走6 2
8 3
7 2 10 (3
2)
100
千米.
C 地集合:共行走6 (2
3)
4 3
7 (2
3) 10 2
97
千米.
D 地集合:共行走6 (2
2)
4 2
8 (3
2) 10 4
112
千米.
E 地集合:共行走6 (2
3
2)
4 (3
2)
8 2
7 4
106
千米.
其中C 地集合的路程总和最小,所以集合地应选在C 地.
7. 根据这道题可以用“小往大处靠”的原则来解决.H 点60 吨,存的货物最多,那么先处
使学习渐入“加”境;让思维“海”阔天空
兰海&姜付加&吴忠 |
7
理小势力,A 往H 那个方向集中,集中到B,B 变成40 吨,判断仍是H 的势力最大,所
以继续向H 方向集中,B 点集中到D 点,D 点变成60 吨.此时D 点和H 点都是60 吨,
那么D、H 谁看成大势力都可以.例如把H 点集中到F 点,F 点是70 吨.把D 点集中到
E 点,E 点是65 吨所以E 点也要集中到F 点.确定了集中地点为F 点,运输费用也就容
易求了.运费最少为:10 500
30 400
20 200
5 100
60 200
0.5 16750
(
)
(元).
8. 五个基地人员总数为17
4 16 14
9
60
(人).
依题意,调整后每个基地应各有60
5
12
(人).
因此,需要从多于12 人的基地, ,
A C D向不足12 人的基地,
B E 调人.为了避免对流,经
试验容易得到调整方案如下:
先从D 调2 人到E,这样E 尚缺1 人;再由A 调1 人给E ,则E 达到要求.此时,A 尚
多余4 人,C 也多余4 人,总共8 人全部调到B ,则B 亦符合要求.
调动示意图如下所示,这样的图形叫做物资流向图.用流向图代替调运方案,能直观地
看出调运状况及有无对流现象,又可避免列表和计算的麻烦.图中箭头表示流向,箭杆
上的数字表示流量.
17
4
16
14
9
A
B
C
D
E
4
1
4
2
说明:发生对流的调运方案不可能是最优方案,这个原则可以证明:
如上图,设A1B2=a 千米,B2B1=b 千米,B1A2=c 千米.如果从A1运1 吨货物到B1,同时又
从A2运1 吨货物到B2,那么在B1B2之间A1的物资从西向东运输,A2的货物从东向西运
输,两者发生对流,于是这样调动的总吨千米数为:(
)
(
)
2
a
b
b
c
a
c
b
.而如果
从A1运1 吨货物到B2,同时从A2运1 吨货物到B1,则运输总吨千米数为a
c
,显然
2
a
c
a
c
b
.
9. 我们采用分析排除法,将道路图逐步简化.
从A 到O 有两条路,A→C→O 用6 分钟,A→F→O 用7 分钟,排除后者,可将FO 抹去,
但AF 不能抹去,因为从A 到B 还有其它路线经过AF,简化为图⑴.从A 到E 还剩两条
路,A→C→G→E 用12 分钟,A→C→O→E 用10 分钟,排除前者,可将CG,GE 抹去,简
化为图⑵.从A 到D 还剩两条路,A→C→O→D 用12 分钟,A→H→D 用13 分钟,排除后
者,可将AH,HD 抹去,简化为图⑶.从A 到B 还剩两条路,A→C→O→E→B 用17 分钟,
A→C→O→D→B 用16 分钟,排除前者,可将OE,EB 抹去,简化为图⑷.
小明按A→C→O→D→B 走最快,用16 分钟.
5
5
D
C
B
A
O 6
4
1
1
4
6
4
O
7
A
B
C
D
E
H
F
E
D
C
B
A
7
O
4
6
4
6
7
1
1
7
6
4
6
4
O
5
6
5
7
A
B
C
D
E
F
G
H
使学习渐入“加”境;让思维“海”阔天空
兰海&姜付加&吴忠 |
8
⑴ ⑵ ⑶ ⑷
10. 由于细管相对于粗管来讲,价钱要少一些,因此先假设都用细管.那么从自来水厂到J
村要铺设10 根细管,自来水厂到I 村要铺设9 根细管,依次下去,我们用图表示铺细
管的情况.因为粗管是细管价格的4 倍,如果用细管代替粗管重叠数超过4 条费用更大,
仅在3 条或3 条以下才会节约,而细管只能供应一村用水,所以粗管从水厂一直接到G
村为止,再用三条细管连接H、I、J 三个村,这样费用最低,总费用:
8000
30
5
2
4
2
3
2
2000
2 3
2 2
5
414000
(
)
(
)
(元).
11. 如果各派10 辆车分别运渣土和砖,那么每运一车渣土要空车跑回300 米,每运一车砖
则要空车跑回360 米,这样到完成任务总共空车跑了:300 60
360 40
32400
(米).
如果一辆从从A→B→C→D→A 跑一圈,那么每运一车渣土,运一车砖要空车跑:
240
90
330
(米);因此,先派20 辆车都从A 开始运渣土到B,再空车开往C 运砖
到D 后空车返回A,这样每辆车跑两圈就完成了运砖任务.然后再派这20 辆车都从A 运
渣土到B 再空车返回A ,则运渣土任务也完成了. 这时总共空车跑了:
330 40
300 20
19200
(米)
后一种调运方案比前一种减少跑空车13200 米,这是最佳节油的调运方案.
12. 方法一:本题中虽然上海到汉口的运费最少,只有3 百元,但是上海到汉口比北京到汉
口只节省( 4
3
)1 百元,相比之下,上海到重庆比北京到重庆要节省(8
5
)3 百元.所
以重庆所需台数应由上海尽量满足,即上海的4 台全部调运重庆,北京再补给重庆4 台,
汉口的6 台从北京调运.总运费为:5 4
8 4
4 6
76
(百元).
方法二:本题也可以采用下面的代数方法解决,设北京调运汉口x 台,调运重庆(10
x
)
台,则上海应调运汉口( 6
x
)台,调运重庆4
6
2
x
x
(
)
(台),总运费
4
8 10
W
x
x
(
) 3 6
5
2
4
80 8
18
3
5
10
88
2
x
x
x
x
x
x
x
(
)(
)
,因为要
使总运费88
2x
最小,需要2x 最大.由于x 是北京调运汉口的台数,且
6
x
,所以当
6
x
时,总运费
88
2 6
76
W
(百元)最小.由
6
x
可知,北京调运汉口6 台,调
运重庆4 台,上海调运汉口0 台,调运重庆4 台.
13. 要想总的时间最少,应该安排打水时间少的人先来打水,下面给出排队方式:
第一个水龙头
第二个水龙头
第一个
1
2
第二个
3
4
第三个
5
6
第四个
7
8
第五个
9
10
显然计算总时间时,1、2 计算了5 次,3、4 计算了4 次,5、6 计算了3 次,7、8 计算
了2 次,9、10 计算了1 次.所以有最短时间为:
1 2
5
3
4
4
5
6
3
7
8
2
9 10
1 125
(
)
(
)
(
)
(
)
(
)
分钟.
14. 由于细管相对于粗管来讲,价钱要少一些,因此先假设都用细管.那么从县城到
1A 村要
铺设10 根细管,1A 村到
2
A 村要铺设9 根细管,依次下去,我们用图表示铺细管的情况.
因为粗管每千米7000 元,细管每千米2000 元,所以4 根细管的价钱将大于1 根粗管的
价钱.这样一来,凡是超过3 根细管的路段,都应改铺粗管.
使学习渐入“加”境;让思维“海”阔天空
兰海&姜付加&吴忠 |
9
因此,从县城到
7
A 村铺1 根粗管,
7
A 村到
8A 村铺3 根细管,
8A 村到
9A 村铺2 根细管,
9A 村到
10
A 村铺1 根细管.总费用为:
7000
30
5
2
4
2
3
2
2000
2 3
2 2
5 1
36600
(
)
(
)
(元).
15. B,C,F 都是1 个村的出口,而D,E 是2 个村的出口,如下图示:
B
C
D
E
F
1
1
2
2
1
令F 处的1 左移到E,则E 处1 2 1 1 2
,
则还需继续左移到D,此时1 2
2
1 1
,因此车站应设在D 处.