小學(xué)奧數(shù)最短路線問題(有答案)

1、學(xué)習(xí)必備歡迎下載小學(xué)六年級奧數(shù)教案一運(yùn)籌學(xué)初步本講主要講統(tǒng)籌安排問題、排隊(duì)問題、最短路線問題、場地設(shè)置問題 等。這些都是人們?nèi)粘Ｉ睢⒐ぷ髦薪?jīng)常碰到的問題，怎樣才能把它們安 排得更合理，多快好省地辦事，就是這講涉及的問題。當(dāng)然，限于現(xiàn)有的 知識水平，我們僅僅是初步探索一下。1 .統(tǒng)籌安排問題例1星期大媽媽要做好多事情。擦玻璃要 20分鐘，收拾廚房要15分鐘，洗臟衣服的領(lǐng)子、袖口要10分鐘，打開全自動洗衣機(jī)洗衣服要 40分鐘，晾衣服要10分鐘。媽媽干完所有這些事情最少用多長時間？分析與解：如果按照題目告訴的幾件事，一件一件去做，要95分鐘。 要想節(jié)約時間，就要想想在哪段時間里閑著，能否利用閑著的

2、時間做其它 事。最合理的安排是：先洗臟衣服的領(lǐng)子和袖口，接著打開全自動洗衣機(jī) 洗衣服，在洗衣服的40分鐘內(nèi)擦玻璃和收拾廚房，最后晾衣服，共需 60 分鐘（見下圖）。選§虹 油伊洗衣機(jī)洗衣金晾衣服, 1040* -10 *如， 擦玻璃15收拾鼠房例1告訴我們，當(dāng)有許多事要做時，科學(xué)地安排好先后順序，就能 用較少的時間完成較多的事情。2 .排隊(duì)問題例2理發(fā)室里有甲、乙兩位理發(fā)師，同時來了五位顧客，根據(jù)他們 所要理的發(fā)型，分別需要10, 12, 15, 20和24分鐘。怎樣安排他們的理 發(fā)順序，才能使這五人理發(fā)和等候所用時間的總和最少？最少要用多少時 問？分析與解：一人理發(fā)時，其他人需等待

3、，為使總的等待時間盡量短， 應(yīng)讓理發(fā)所需時間少的人先理。甲先給需10分鐘的人理發(fā)，然后15分鐘 的，最后24分鐘的；乙先給需12分鐘的人理發(fā)，然后20分鐘的。甲給 需10分鐘的人理發(fā)時，有2人等待，占用三人的時間和為（10X 3）分； 然后，甲給需15分鐘的人理發(fā)，有1人等待，占用兩人的時間和為（15 X2）分；最后，甲給需24分鐘的人理發(fā)，無人等待。甲理發(fā)的三個人，共用（10X3+15X 2+24）分，乙理發(fā)的兩個人， 共用（12X2+20）分。總的占用時間為（10X3+ 15X2 + 24） + （ 12X2 + 20） =128 （分）。按照上面的安排，從第一人開始理發(fā)到五個人全部理完，

4、用了 10 + 15 + 24= 49 （分）。如果題目中再要求從第一人開始理發(fā)到五人全部理完 的時間最短，那么做個調(diào)整，甲依次給需 10, 12, 20分鐘的人理發(fā)，乙 依次名&需15, 24分鐘的人理發(fā)，總的占用時間仍是 128分鐘，而五人全 部理完所用時間為10+ 12+20= 42 （分）。例3車間里有五臺車床同時出現(xiàn)故障，已知第一臺到第五臺修復(fù)時 間依次為18, 30, 17, 25, 20分鐘，每臺車床停產(chǎn)一分鐘造成經(jīng)濟(jì)損失 5元?，F(xiàn)有兩名工作效率相同的修理工，怎樣安排才能使得修復(fù)的時間最 短且經(jīng)濟(jì)損失最少？分析與解：因?yàn)椋?18+30+ 17+ 25+20） + 2=55

5、 （分），經(jīng)過組合， 一人修需18, 17和20分鐘的三臺，另一人修需30和25分鐘的兩臺，修 復(fù)時間最短，為55分鐘。上面只考慮修復(fù)時間，沒考慮經(jīng)濟(jì)損失，要使經(jīng)濟(jì)損失少，就要使總 停產(chǎn)時間盡量短，顯然應(yīng)先修理修復(fù)時間短的。第一人按需 17, 18, 20 分鐘的順序修理，第2人按需25, 30分鐘的順序修理，經(jīng)濟(jì)損失為5X （17X3+18X2+20）+（ 25X 2+30） =935 （元）。3 .最短路線問題例4右圖是一張道路示意圖，每段路上的數(shù)字表示小明走這段路所 需要的時間（單位：分）。小明從 A到B最快要幾分鐘？分析與解：我們采用分析排除法，將道路圖逐步簡化。從A到。有兩條路，ZC

6、-。用6分鐘，A- F一。用7分鐘，排除后 者，可將FO抹去，但AF不能抹去，因?yàn)閺腁到B還有其它路線經(jīng)過AF, 簡化為左下圖。從A到E還剩兩條路，A-C- GH E用12分鐘，A- C- Of E用10分 鐘，排除前者，可將CG GE抹去，簡化為右上圖。從A到D還剩兩條路，A-C-Of D用12分鐘，A- HH D用13分鐘, 排除后者，可將AH HD抹去，簡化為左下圖。從A到B還剩兩條路，2CE B用17分鐘，A- CA B 用16分鐘，排除前者，可將OE EB抹去，簡化為右上圖。小明按A-C-O- AB走最快，用16分鐘4 .場地設(shè)置問題例5下圖是A, B, C, D, E五個村之間的道

7、路示意圖，。中數(shù)字是 各村要上學(xué)的學(xué)生人數(shù)，道路上的數(shù)表示兩村之間的距離（單位：千米） 現(xiàn)在要在五村之中選一個村建立一所小學(xué)。為使所有學(xué)生到學(xué)校的總距離 最短，試確定最合理的方案。分析與解：我們采用比較學(xué)校設(shè)在相鄰兩村的差別的方法。 例如比較 A和C,若設(shè)在A村，則在C村一側(cè)將集結(jié)20 +20+35+ 50=125（人）， 這些人都要走AC這段路；若設(shè)在C村，則只有40人走AC這段路。對這 兩種方案，走其余各段路的人數(shù)完全相同，所以設(shè)在 C村比設(shè)在A村好。從上面比較A和C的過程可以看出，場地設(shè)置問題不必考慮場地之間 的距離，只需比較兩個場地集結(jié)的人數(shù)多少，哪個場地集結(jié)的人數(shù)越多， 就應(yīng)設(shè)在哪。

8、同理，經(jīng)比較得到C比B好，D比E好。最后比較C和D。若設(shè)在C 村，則在D村一側(cè)將集結(jié)35 + 50= 85 （人）；若設(shè)在D村，則在C村 一側(cè)將集結(jié)40 +20+ 20=80 （人）。因?yàn)樵贒村集結(jié)的人數(shù)比C村多，所 以設(shè)在D村比C村好。經(jīng)過上面的比較，最合理的方案是設(shè)在 D村。不難發(fā)現(xiàn)，本題的解法與第27講例2的解法十分類似例6某天然氣站要安裝天然氣管道通往位于一條環(huán)形線上的 AG七 個居民區(qū)，每兩個居民區(qū)間的距離如下圖所示（單位：千米）。管道有粗 細(xì)兩種規(guī)格，粗管可供所有7個居民區(qū)用氣，每千米8000元，細(xì)管只能 供1個居民區(qū)用氣，每千米3000元。粗、細(xì)管的轉(zhuǎn)接處必須在居民區(qū)中。 問：應(yīng)

9、怎樣搭配使用這兩種管道，才能使費(fèi)用最?。糠治雠c解：在長度相同的情況下，每根粗管的費(fèi)用大于2根細(xì)管的費(fèi) 用，小于3根細(xì)管的費(fèi)用，所以安裝管道時，只要后面需要供氣的居民區(qū) 多于2個，這一段就應(yīng)選用粗管。從天然氣站開始，分成順時針與逆時針 兩條線路安裝，因?yàn)槊織l線路的后面至多有兩個居民區(qū)由細(xì)管通達(dá)，共有7個居民區(qū)，所以至少有3個居民區(qū)由粗管通達(dá)。因?yàn)殚L度相同時，2根 或1根細(xì)管的費(fèi)用都低于1根粗管的費(fèi)用，所以由粗管通達(dá)的幾個居民區(qū) 的距離越短越好，而順時針與逆時針兩條線路未銜接部份的距離越長越 好。經(jīng)過計算比較，得到最佳方案：（1）天然氣站經(jīng)G, F, E到D安裝粗管，D到C安裝2根細(xì)管，C 到B安

10、裝1根細(xì)管；（2）天然氣站到A安裝1根細(xì)管此時總費(fèi)用最少，為8000X (3+12+8+6)+3000X2X5+3000X (9+10) =319000 (元)練習(xí)291 .早飯前媽媽要干好多的事：燒開水要 15分鐘，擦桌椅要8分鐘， 準(zhǔn)備暖瓶要1分鐘，灌開水要2分鐘，買油條要10分鐘，煮牛奶要7分 鐘。如果灶具上只有一個火，那么全部做完這些工作最少需要多少時間？ 怎樣安排？2 .甲、乙、內(nèi)三名車工準(zhǔn)備在同樣效率的 3個車床上加工七個零件， 各零件加工所需時間分別為4, 5, 6, 6, 8, 9, 9分鐘，三人同時開始工 作。問：加工完七個零件最少需多長時間？3 .車間里有5臺車床同時出現(xiàn)故

11、障。已知第一臺至第五臺修復(fù)的時間 依次為15, 8, 29, 7, 10分鐘，每臺車床停產(chǎn)一分鐘造成經(jīng)濟(jì)損失 5元 問：（1）如果只有一名修理工，那么怎樣安排修理順序才能使經(jīng)濟(jì)損失 最少？ （2）如果有兩名修理工，那么修復(fù)時間最少需多少分鐘？4.下頁左上圖是一張道路圖， 問（單位：分）。小王從 A到B,每條路上的數(shù)是小王走這段路所需的時 最快需要幾分鐘？5 .東升鄉(xiāng)有8個行政村。分布如右上圖所示，點(diǎn)表示村莊，線表示道 路，數(shù)字表示道路的長（單位：千米）。現(xiàn)在這個鄉(xiāng)要建立有線廣播網(wǎng)， 沿道路架設(shè)電線。問：電線至少要架多長？6 .有七個村莊A1, A2,，A7分布在公路兩側(cè)（見下圖），由一些 小路

12、與公路相連，要在公路上設(shè)一個汽車站，要使汽車站到各村莊的距離 和最小，車站應(yīng)設(shè)在哪里？7 .有一個水塔要供應(yīng)某條公路旁的 AF六個居民點(diǎn)用水（見下圖， 單位：千米），要安裝水管，有粗細(xì)兩種水管，粗管足夠供應(yīng) 6個居民點(diǎn) 用水，細(xì)管只能供應(yīng)1個居民點(diǎn)用水，粗管每千米要 7000元，細(xì)管每千 米要2000元，粗細(xì)管怎樣互相搭配，才能使費(fèi)用最??？費(fèi)用應(yīng)是多少？_ J22_i_2_i_b_jLb_L_a. 水塔 " B C 口 e F答案與提示練習(xí)291.22 分提示：先燒開水后煮牛奶共需22分，其它事情可以在這個期間做, 順序是買油條，準(zhǔn)備暖瓶，擦桌椅（水開時暫停，煮上奶），灌開水，繼 續(xù)擦桌椅。8 .17 分。9 . （1） 780 元；（2） 36 分。提示：（1）按修復(fù)時間需7, 8, 10, 15, 29分的順序修理；（2）一人修需7分和29分的，另一人修需8, 10, 15分的。10 48 分。提?。篈r&g