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

.小學六年級奧數(shù)教案運籌學初步本講主要講統(tǒng)籌安排問題、排隊問題、最短路線問題、場地設置問題等。這些都是人們日常生活、工作中經常碰到的問題，怎樣才能把它們安排得更合理，多快好省地辦事，就是這講涉及的問題。當然，限于現(xiàn)有的知識水平，我們僅僅是初步探索一下。1.統(tǒng)籌安排問題例1 星期天媽媽要做好多事情。擦玻璃要20分鐘，收拾廚房要15分鐘，洗臟衣服的領子、袖口要10分鐘，打開全自動洗衣機洗衣服要40分鐘，晾衣服要10分鐘。媽媽干完所有這些事情最少用多長時間？分析與解：如果按照題目告訴的幾件事，一件一件去做，要95分鐘。要想節(jié)約時間，就要想想在哪段時間里閑著，能否利用閑著的時間做其它事。最合理的安排是：先洗臟衣服的領子和袖口，接著打開全自動洗衣機洗衣服，在洗衣服的40分鐘內擦玻璃和收拾廚房，最后晾衣服，共需60分鐘（見下圖）。例1 告訴我們，當有許多事要做時，科學地安排好先后順序，就能用較少的時間完成較多的事情。2.排隊問題例2 理發(fā)室里有甲、乙兩位理發(fā)師，同時來了五位顧客，根據(jù)他們所要理的發(fā)型，分別需要10，12，15，20和24分鐘。怎樣安排他們的理發(fā)順序，才能使這五人理發(fā)和等候所用時間的總和最少？最少要用多少時間？分析與解：一人理發(fā)時，其他人需等待，為使總的等待時間盡量短，應讓理發(fā)所需時間少的人先理。甲先給需10分鐘的人理發(fā)，然后15分鐘的，最后24分鐘的；乙先給需12分鐘的人理發(fā)，然后20分鐘的。甲給需10分鐘的人理發(fā)時，有2人等待，占用三人的時間和為（103）分；然后，甲給需 15分鐘的人理發(fā)，有 1人等待，占用兩人的時間和為（152）分；最后，甲給需 24分鐘的人理發(fā)，無人等待。甲理發(fā)的三個人，共用（10315224）分，乙理發(fā)的兩個人，共用（12220）分。總的占用時間為（10315224）（12220）=128（分）。按照上面的安排，從第一人開始理發(fā)到五個人全部理完，用了 10152449（分）。如果題目中再要求從第一人開始理發(fā)到五人全部理完的時間最短，那么做個調整，甲依次給需10，12，20分鐘的人理發(fā)，乙依次給需15，24分鐘的人理發(fā)，總的占用時間仍是128分鐘，而五人全部理完所用時間為10122042（分）。例3 車間里有五臺車床同時出現(xiàn)故障，已知第一臺到第五臺修復時間依次為18，30，17，25，20分鐘，每臺車床停產一分鐘造成經濟損失5元。現(xiàn)有兩名工作效率相同的修理工，怎樣安排才能使得修復的時間最短且經濟損失最少？分析與解：因為（1830172520）2=55（分），經過組合，一人修需18，17和20分鐘的三臺，另一人修需30和25分鐘的兩臺，修復時間最短，為55分鐘。上面只考慮修復時間，沒考慮經濟損失，要使經濟損失少，就要使總停產時間盡量短，顯然應先修理修復時間短的。第一人按需17，18，20分鐘的順序修理，第2人按需25，30分鐘的順序修理，經濟損失為5（17318220）（25230）=935（元）。3.最短路線問題例4 右圖是一張道路示意圖，每段路上的數(shù)字表示小明走這段路所需要的時間（單位：分）。小明從A到B最快要幾分鐘？分析與解：我們采用分析排除法，將道路圖逐步簡化。從A到O有兩條路，ACO用6分鐘，AFO用7分鐘，排除后者，可將FO抹去，但AF不能抹去，因為從A到B還有其它路線經過AF，簡化為左下圖。從A到E還剩兩條路，ACGE用12分鐘，ACOE用10分鐘，排除前者，可將CG，GE抹去，簡化為右上圖。從A到D還剩兩條路，ACOD用12分鐘，AHD用13分鐘，排除后者，可將AH，HD抹去，簡化為左下圖。從A到B還剩兩條路，ACOEB用17分鐘，ACODB用16分鐘，排除前者，可將OE，EB抹去，簡化為右上圖。小明按ACODB走最快，用16分鐘。4.場地設置問題例5 下圖是A，B，C，D，E五個村之間的道路示意圖，中數(shù)字是各村要上學的學生人數(shù)，道路上的數(shù)表示兩村之間的距離（單位：千米）?，F(xiàn)在要在五村之中選一個村建立一所小學。為使所有學生到學校的總距離最短，試確定最合理的方案。分析與解：我們采用比較學校設在相鄰兩村的差別的方法。例如比較 A和 C，若設在 A村，則在 C村一側將集結 20203550=125（人），這些人都要走 AC這段路；若設在C村，則只有40人走AC這段路。對這兩種方案，走其余各段路的人數(shù)完全相同，所以設在C村比設在A村好。從上面比較A和C的過程可以看出，場地設置問題不必考慮場地之間的距離，只需比較兩個場地集結的人數(shù)多少，哪個場地集結的人數(shù)越多，就應設在哪。同理，經比較得到C比B好，D比E好。最后比較C和D。若設在 C村，則在 D村一側將集結 35 50= 85（人）；若設在 D村，則在C村一側將集結 402020=80（人）。因為在D村集結的人數(shù)比C村多，所以設在D村比C村好。經過上面的比較，最合理的方案是設在D村。不難發(fā)現(xiàn)，本題的解法與第27講例2的解法十分類似。例6 某天然氣站要安裝天然氣管道通往位于一條環(huán)形線上的AG七個居民區(qū)，每兩個居民區(qū)間的距離如下圖所示（單位：千米）。管道有粗細兩種規(guī)格，粗管可供所有7個居民區(qū)用氣，每千米8000元，細管只能供1個居民區(qū)用氣，每千米3000元。粗、細管的轉接處必須在居民區(qū)中。問：應怎樣搭配使用這兩種管道，才能使費用最省？分析與解：在長度相同的情況下，每根粗管的費用大于2根細管的費用，小于3根細管的費用，所以安裝管道時，只要后面需要供氣的居民區(qū)多于2個，這一段就應選用粗管。從天然氣站開始，分成順時針與逆時針兩條線路安裝，因為每條線路的后面至多有兩個居民區(qū)由細管通達，共有7個居民區(qū)，所以至少有3個居民區(qū)由粗管通達。因為長度相同時，2根或1根細管的費用都低于1根粗管的費用，所以由粗管通達的幾個居民區(qū)的距離越短越好，而順時針與逆時針兩條線路未銜接部份的距離越長越好。經過計算比較，得到最佳方案：（1）天然氣站經G，F(xiàn)，E到D安裝粗管，D到C安裝2根細管，C到B安裝1根細管；（2）天然氣站到A安裝1根細管。此時總費用最少，為8000（3+12+8+6）+300025+3000（9+10）=319000（元）。練習291.早飯前媽媽要干好多的事：燒開水要15分鐘，擦桌椅要8分鐘，準備暖瓶要1分鐘，灌開水要2分鐘，買油條要10分鐘，煮牛奶要7分鐘。如果灶具上只有一個火，那么全部做完這些工作最少需要多少時間？怎樣安排？2.甲、乙、丙三名車工準備在同樣效率的3個車床上加工七個零件，各零件加工所需時間分別為4，5，6，6，8，9，9分鐘，三人同時開始工作。問：加工完七個零件最少需多長時間？3.車間里有5臺車床同時出現(xiàn)故障。已知第一臺至第五臺修復的時間依次為15，8，29，7，10分鐘，每臺車床停產一分鐘造成經濟損失5元。問：（1）如果只有一名修理工，那么怎樣安排修理順序才能使經濟損失最少？（2）如果有兩名修理工，那么修復時間最少需多少分鐘？4.下頁左上圖是一張道路圖，每條路上的數(shù)是小王走這段路所需的時間（單位：分）。小王從A到B，最快需要幾分鐘？5.東升鄉(xiāng)有8個行政村。分布如右上圖所示，點表示村莊，線表示道路，數(shù)字表示道路的長（單位：千米）?，F(xiàn)在這個鄉(xiāng)要建立有線廣播網，沿道路架設電線。問：電線至少要架多長？6.有七個村莊A1，A2，A7分布在公路兩側（見下圖），由一些小路與公路相連，要在公路上設一個汽車站，要使汽車站到各村莊的距離和最小，車站應設在哪里？7.有一個水塔要供應某條公路旁的AF六個居民點用水（見下圖，單位：千米），要安裝水管，有粗細兩種水管，粗管足夠供應6個居民點用水，細管只能供應1個居民點用水，粗管每千米要7000元，細管每千米要2000元，粗細管怎樣互相搭配，才能使費用最??？費用應是多少？ 答案與提示練習291.22分。提示：先燒開水后煮牛奶共需22分，其它事情可以在這個期間做，順序是買油條，準備暖瓶，擦桌椅（水開時暫停，煮上奶），灌開水，繼續(xù)擦桌椅。2.17分。3.（1）780元；（2）36分。提示：（1）按修復時間需7，8，10，15，29分的順序修理；（2）一人修需7分和29分的，另一人修需8，10，15分的。