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

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

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

3、需10分鐘的人理發(fā)，然后15分鐘的，最后24分鐘的；乙先給需12分鐘的人理發(fā)，然后20分鐘的。甲給需10分鐘的人理發(fā)時，有2人等待，占用三人的時間和為（10X3）分；然后，甲給需15分鐘的人理發(fā)，有1人等待，占用兩人的時間和為（15X2）分；最后，甲給需24分鐘的人理發(fā)，無人等待。甲理發(fā)的三個人，共用（10X3+15X2+24）分，乙理發(fā)的兩個人，共用（12X2+20）分?？偟恼加脮r間為（10X3+15X2+24）+（12X2+20）=128（分）。按照上面的安排，從第一人開始理發(fā)到五個人全部理完，用了10+15+24=49（分）。如果題目中再要求從第一人開始理發(fā)到五人全部理完的時間最短，那么

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

5、損失少，就要使總停產(chǎn)時間盡量短，顯然應先修理修復時間短的。第一人按需17,18,20分鐘的順序修理，第2人按需25,30分鐘的順序修理，經(jīng)濟損失為5X（17X3+18X2+20）+（25X2+30）=935（元）。3 .最短路線問題例4右圖是一張道路示意圖，每段路上的數(shù)字表示小明走這段路所需要的時間（單位：分）。小明從A到B最快要幾分鐘？分析與解：我們采用分析排除法，將道路圖逐步簡化。從A到O有兩條路，ZCfO用6分鐘，A-F-O用7分鐘，排除后者，可將FO抹去，但AF不能抹去，因為從A到B還有其它路線經(jīng)過AF,簡化為左下圖。從A到E還剩兩條路，A-C-GHE用12分鐘，A-C-CfE用10分

6、鐘，排除前者，可將CGGE抹去，簡化為右上圖。從A到D還剩兩條路，A-CCfD用12分鐘，A一4D用13分鐘，排除后者，可將AHHD抹去，簡化為左下圖。從A到B還剩兩條路，2CEB用17分鐘，A-CAB用16分鐘，排除前者，可將OEEB抹去，簡化為右上圖。小明按A-C-O»AB走最快，用16分鐘。4 .場地設(shè)置問題例5下圖是A,B,C,D,E五個村之間的道路示意圖，。中數(shù)字是各村要上學的學生人數(shù)，道路上的數(shù)表示兩村之間的距離（單位：千米）現(xiàn)在要在五村之中選一個村建立一所小學。為使所有學生到學校的總距離最短，試確定最合理的方案。分析與解：我們采用比較學校設(shè)在相鄰兩村的差別的方法。例如比

7、較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ù)越多，就應設(shè)在哪。同理，經(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（人）。因為在D村集結(jié)的人數(shù)比C村多，所以設(shè)在D村比C村好。經(jīng)過上面的比較，最合理的方案是設(shè)在D村

8、。不難發(fā)現(xiàn)，本題的解法與第27講例2的解法十分類似例6某天然氣站要安裝天然氣管道通往位于一條環(huán)形線上的AG七個居民區(qū)，每兩個居民區(qū)間的距離如下圖所示（單位：千米）。管道有粗細兩種規(guī)格，粗管可供所有7個居民區(qū)用氣，每千米8000元，細管只能供1個居民區(qū)用氣，每千米3000元。粗、細管的轉(zhuǎn)接處必須在居民區(qū)中。問：應怎樣搭配使用這兩種管道，才能使費用最?。糠治雠c解：在長度相同的情況下，每根粗管的費用大于2根細管的費用，小于3根細管的費用，所以安裝管道時，只要后面需要供氣的居民區(qū)多于2個，這一段就應選用粗管。從天然氣站開始，分成順時針與逆時針兩條線路安裝，因為每條線路的后面至多有兩個居民區(qū)由細管通達，

9、共有7個居民區(qū)，所以至少有3個居民區(qū)由粗管通達。因為長度相同時，2根或1根細管的費用都低于1根粗管的費用，所以由粗管通達的幾個居民區(qū)的距離越短越好，而順時針與逆時針兩條線路未銜接部份的距離越長越好。經(jīng)過計算比較，得到最佳方案：（1）天然氣站經(jīng)G,F,E到D安裝粗管，D到C安裝2根細管，C到B安裝1根細管；（2）天然氣站到A安裝1根細管此時總費用最少，為8000X(3+12+8+6)+3000X2X5+3000X(9+10)=(元)練習291 .早飯前媽媽要干好多的事：燒開水要15分鐘，擦桌椅要8分鐘，準備暖瓶要1分鐘，灌開水要2分鐘，買油條要10分鐘，煮牛奶要7分鐘。如果灶具上只有一個火，那么

10、全部做完這些工作最少需要多少時間？怎樣安排？2 .甲、乙、內(nèi)三名車工準備在同樣效率的3個車床上加工七個零件，各零件加工所需時間分別為4,5,6,6,8,9,9分鐘，三人同時開始工作。問：加工完七個零件最少需多長時間？3 .車間里有5臺車床同時出現(xiàn)故障。已知第一臺至第五臺修復的時間依次為15,8,29,7,10分鐘，每臺車床停產(chǎn)一分鐘造成經(jīng)濟損失5元問：（1）如果只有一名修理工，那么怎樣安排修理順序才能使經(jīng)濟損失最少？（2）如果有兩名修理工，那么修復時間最少需多少分鐘？4.下頁左上圖是一張道路圖，問（單位：分）。小王從A到B,每條路上的數(shù)是小王走這段路所需的時最快需要幾分鐘？5 .東升鄉(xiāng)有8個行

11、政村。分布如右上圖所示，點表示村莊，線表示道路，數(shù)字表示道路的長（單位：千米）?，F(xiàn)在這個鄉(xiāng)要建立有線廣播網(wǎng)，沿道路架設(shè)電線。問：電線至少要架多長？6 .有七個村莊A1,A2,A7分布在公路兩側(cè)（見下圖），由一些小路與公路相連，要在公路上設(shè)一個汽車站，要使汽車站到各村莊的距離和最小，車站應設(shè)在哪里？7 .有一個水塔要供應某條公路旁的AF六個居民點用水（見下圖，單位：千米），要安裝水管，有粗細兩種水管，粗管足夠供應6個居民點用水，細管只能供應1個居民點用水，粗管每千米要7000元，細管每千米要2000元，粗細管怎樣互相搭配，才能使費用最省？費用應是多少？_J22_i_2_i_L_a.水塔"BC口eF答案與提示練習291.22分提示：先燒開水后煮牛奶共需22分，其它事情可以在這個期間做,順序是買油條，準備暖瓶，擦桌椅（水開時暫停，煮上奶），灌開水，繼續(xù)擦桌椅。8 .17分。9 .（1）780元；（2）36分。提示：（1）按修復時間需7,8,10,15,29分的順序修理；（2）一人修需7分和29分的，另一人修需8,10,15分的。4.48分。