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

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

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

3、后20分鐘的。甲給需10分鐘的人理發(fā)時(shí)，有2人等待，占用三人的時(shí)間和為（103）分；然后，甲給需 15分鐘的人理發(fā)，有 1人等待，占用兩人的時(shí)間和為（152）分；最后，甲給需 24分鐘的人理發(fā)，無(wú)人等待。甲理發(fā)的三個(gè)人，共用（10315224）分，乙理發(fā)的兩個(gè)人，共用（12220）分?？偟恼加脮r(shí)間為（10315224）（12220）=128（分）。按照上面的安排，從第一人開(kāi)始理發(fā)到五個(gè)人全部理完，用了 10152449（分）。如果題目中再要求從第一人開(kāi)始理發(fā)到五人全部理完的時(shí)間最短，那么做個(gè)調(diào)整，甲依次給需10，12，20分鐘的人理發(fā)，乙依次給需15，24分鐘的人理發(fā)，總的占用時(shí)間仍是128分

4、鐘，而五人全部理完所用時(shí)間為10122042（分）。例3 車間里有五臺(tái)車床同時(shí)出現(xiàn)故障，已知第一臺(tái)到第五臺(tái)修復(fù)時(shí)間依次為18，30，17，25，20分鐘，每臺(tái)車床停產(chǎn)一分鐘造成經(jīng)濟(jì)損失5元。現(xiàn)有兩名工作效率相同的修理工，怎樣安排才能使得修復(fù)的時(shí)間最短且經(jīng)濟(jì)損失最少？分析與解：因?yàn)椋?830172520）2=55（分），經(jīng)過(guò)組合，一人修需18，17和20分鐘的三臺(tái)，另一人修需30和25分鐘的兩臺(tái)，修復(fù)時(shí)間最短，為55分鐘。上面只考慮修復(fù)時(shí)間，沒(méi)考慮經(jīng)濟(jì)損失，要使經(jīng)濟(jì)損失少，就要使總停產(chǎn)時(shí)間盡量短，顯然應(yīng)先修理修復(fù)時(shí)間短的。第一人按需17，18，20分鐘的順序修理，第2人按需25，30分鐘的順序修

5、理，經(jīng)濟(jì)損失為5（17318220）（25230）=935（元）。3.最短路線問(wèn)題例4 右圖是一張道路示意圖，每段路上的數(shù)字表示小明走這段路所需要的時(shí)間（單位：分）。小明從A到B最快要幾分鐘？分析與解：我們采用分析排除法，將道路圖逐步簡(jiǎn)化。從A到O有兩條路，ACO用6分鐘，AFO用7分鐘，排除后者，可將FO抹去，但AF不能抹去，因?yàn)閺腁到B還有其它路線經(jīng)過(guò)AF，簡(jiǎn)化為左下圖。從A到E還剩兩條路，ACGE用12分鐘，ACOE用10分鐘，排除前者，可將CG，GE抹去，簡(jiǎn)化為右上圖。從A到D還剩兩條路，ACOD用12分鐘，AHD用13分鐘，排除后者，可將AH，HD抹去，簡(jiǎn)化為左下圖。從A到B還剩兩條

6、路，ACOEB用17分鐘，ACODB用16分鐘，排除前者，可將OE，EB抹去，簡(jiǎn)化為右上圖。小明按ACODB走最快，用16分鐘。4.場(chǎng)地設(shè)置問(wèn)題例5 下圖是A，B，C，D，E五個(gè)村之間的道路示意圖，中數(shù)字是各村要上學(xué)的學(xué)生人數(shù)，道路上的數(shù)表示兩村之間的距離（單位：千米）?，F(xiàn)在要在五村之中選一個(gè)村建立一所小學(xué)。為使所有學(xué)生到學(xué)校的總距離最短，試確定最合理的方案。分析與解：我們采用比較學(xué)校設(shè)在相鄰兩村的差別的方法。例如比較 A和 C，若設(shè)在 A村，則在 C村一側(cè)將集結(jié) 20203550=125（人），這些人都要走 AC這段路；若設(shè)在C村，則只有40人走AC這段路。對(duì)這兩種方案，走其余各段路的人數(shù)完

7、全相同，所以設(shè)在C村比設(shè)在A村好。從上面比較A和C的過(guò)程可以看出，場(chǎng)地設(shè)置問(wèn)題不必考慮場(chǎng)地之間的距離，只需比較兩個(gè)場(chǎng)地集結(jié)的人數(shù)多少，哪個(gè)場(chǎng)地集結(jié)的人數(shù)越多，就應(yīng)設(shè)在哪。同理，經(jīng)比較得到C比B好，D比E好。最后比較C和D。若設(shè)在 C村，則在 D村一側(cè)將集結(jié) 35 50= 85（人）；若設(shè)在 D村，則在C村一側(cè)將集結(jié) 402020=80（人）。因?yàn)樵贒村集結(jié)的人數(shù)比C村多，所以設(shè)在D村比C村好。經(jīng)過(guò)上面的比較，最合理的方案是設(shè)在D村。不難發(fā)現(xiàn)，本題的解法與第27講例2的解法十分類似。例6 某天然氣站要安裝天然氣管道通往位于一條環(huán)形線上的AG七個(gè)居民區(qū)，每?jī)蓚€(gè)居民區(qū)間的距離如下圖所示（單位：千米）

8、。管道有粗細(xì)兩種規(guī)格，粗管可供所有7個(gè)居民區(qū)用氣，每千米8000元，細(xì)管只能供1個(gè)居民區(qū)用氣，每千米3000元。粗、細(xì)管的轉(zhuǎn)接處必須在居民區(qū)中。問(wèn)：應(yīng)怎樣搭配使用這兩種管道，才能使費(fèi)用最?。糠治雠c解：在長(zhǎng)度相同的情況下，每根粗管的費(fèi)用大于2根細(xì)管的費(fèi)用，小于3根細(xì)管的費(fèi)用，所以安裝管道時(shí)，只要后面需要供氣的居民區(qū)多于2個(gè)，這一段就應(yīng)選用粗管。從天然氣站開(kāi)始，分成順時(shí)針與逆時(shí)針兩條線路安裝，因?yàn)槊織l線路的后面至多有兩個(gè)居民區(qū)由細(xì)管通達(dá)，共有7個(gè)居民區(qū)，所以至少有3個(gè)居民區(qū)由粗管通達(dá)。因?yàn)殚L(zhǎng)度相同時(shí)，2根或1根細(xì)管的費(fèi)用都低于1根粗管的費(fèi)用，所以由粗管通達(dá)的幾個(gè)居民區(qū)的距離越短越好，而順時(shí)針與逆時(shí)

9、針兩條線路未銜接部份的距離越長(zhǎng)越好。經(jīng)過(guò)計(jì)算比較，得到最佳方案：（1）天然氣站經(jīng)G，F(xiàn)，E到D安裝粗管，D到C安裝2根細(xì)管，C到B安裝1根細(xì)管；（2）天然氣站到A安裝1根細(xì)管。此時(shí)總費(fèi)用最少，為8000（3+12+8+6）+300025+3000（9+10）=319000（元）。練習(xí)291.早飯前媽媽要干好多的事：燒開(kāi)水要15分鐘，擦桌椅要8分鐘，準(zhǔn)備暖瓶要1分鐘，灌開(kāi)水要2分鐘，買油條要10分鐘，煮牛奶要7分鐘。如果灶具上只有一個(gè)火，那么全部做完這些工作最少需要多少時(shí)間？怎樣安排？2.甲、乙、丙三名車工準(zhǔn)備在同樣效率的3個(gè)車床上加工七個(gè)零件，各零件加工所需時(shí)間分別為4，5，6，6，8，9，9

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

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