奧數(shù)：小學(xué)奧數(shù)系列：第十三講 簡單的統(tǒng)籌規(guī)劃問題

《奧數(shù)：小學(xué)奧數(shù)系列：第十三講 簡單的統(tǒng)籌規(guī)劃問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第十三講簡單的統(tǒng)籌規(guī)劃問題　　這一講我們討論有關(guān)物資調(diào)運(yùn)、下料問題及配套生產(chǎn)等實(shí)例。例1某工地A有20輛卡車，要把60車渣土從A運(yùn)到B，把40車磚從C運(yùn)到D（工地道路圖如右圖所示），問如何調(diào)運(yùn)最省汽油？　　分析把渣土從A運(yùn)到B或把磚從C運(yùn)到D，都無法節(jié)省汽油.只有設(shè)法減少跑空車的距離，才能省汽油。解：如果各派10輛車分別運(yùn)渣土和磚，那么每運(yùn)一車渣土要空車跑回300米，每運(yùn)一車磚則要空車跑回360米，這樣到完成任務(wù)總共空車跑了　　300×60＋360×40=32400（米）?！　∪绻惠v車從A→B→C→D→A跑一圈，那么每

2、運(yùn)一車渣土、再運(yùn)一車磚要空車跑　　240+90＝330（米）.　　因此，先派20輛車都從A開始運(yùn)渣土到B，再空車開往C運(yùn)磚到D后空車返回A，這樣每輛車跑兩圈就完成了運(yùn)磚任務(wù).然后再派這20輛車都從A運(yùn)渣土到B再空車返回A，則運(yùn)渣土任務(wù)也完成了.這時(shí)總共空車跑了　　330×40+300×20＝19200（米）.　　后一種調(diào)運(yùn)方案比前一種減少跑空車13200米，這是最佳節(jié)油的調(diào)運(yùn)方案?！　≌f明：“節(jié)省跑空車的距離”是物資調(diào)運(yùn)問題的一個(gè)原則：下面通過例子再介紹“避免對流”的原則。例2一支勘探隊(duì)在五個(gè)山頭A、B、C、D、E設(shè)立了

3、基地，人數(shù)如右圖所示.為調(diào)整使各基地人數(shù)相同，如何調(diào)動(dòng)最方便？（調(diào)動(dòng)時(shí)不考慮路程遠(yuǎn)近）　　分析在人員調(diào)運(yùn)時(shí)不考慮路程遠(yuǎn)近的因素，就只需避免兩個(gè)基地之間相互調(diào)整，即“避免對流現(xiàn)象”?！　〗猓何鍌€(gè)基地人員總數(shù)為　　17+4+16+14+9=60（人）　　依題意，調(diào)整后每個(gè)基地應(yīng)各有　　60÷5=12（人）?！　∫虼?，需要從多于12人的基地A、C、D向不足12人的基地B、E調(diào)人.為了避免對流，經(jīng)試驗(yàn)容易得到調(diào)整方案如下：　　先從D調(diào)2人到E，這樣E尚缺1人；再由A調(diào)1人給E，則E達(dá)到要求.此時(shí)，A尚多余4人，C也多余4人，總共

4、8人全部調(diào)到B，則B亦符合要求?！　≌{(diào)動(dòng)示意圖如右圖所示.這樣的圖形叫做物資流向圖.用流向圖代替調(diào)運(yùn)方案，能直觀地看出調(diào)運(yùn)狀況及有無對流現(xiàn)象，又可避免列表和計(jì)算的麻煩，圖中箭頭表示流向，箭桿上　　的數(shù)字表示流量?！　≌f明：發(fā)生對流的調(diào)運(yùn)方案不可能是最優(yōu)方案.這個(gè)原則可以證明：　　如右圖，設(shè)A1B2＝a千米，B2B1=b千米，B1A2＝c千米.如果從A1運(yùn)1噸貨物到B1，同時(shí)又從A2運(yùn)1噸貨物到B2，那么在B1B2之間A1的物資從西向東運(yùn)輸，A2的貨物從東向西運(yùn)輸，兩者發(fā)生對流，于是這樣調(diào)動(dòng)的總噸千米數(shù)為　?。╝＋b）+（

5、b＋c）＝a＋c+2b.　　而如果從A1運(yùn)1噸貨物到B2，同時(shí)從A2運(yùn)1噸貨物到B1，栽蛟聳渥芏智資猘+c.顯然　　a+c＜a+c+2b。例3在一條公路上每隔100千米有一個(gè)倉庫（如右圖，）共有5個(gè)倉庫.一號倉庫存有10噸貨物，二號倉庫有20噸貨物，五號倉庫存有40噸貨物，其余兩個(gè)倉庫是空的。現(xiàn)在想把所有的貨物集中存放在一個(gè)倉庫里，如果每噸貨物運(yùn)輸1公里需要0.5元運(yùn)輸費(fèi)，那么最少要多少運(yùn)費(fèi)才行？　　分析欲使花費(fèi)的運(yùn)輸費(fèi)少，關(guān)鍵在于運(yùn)輸?shù)呢浳锖吐烦瘫M可能少，實(shí)際經(jīng)驗(yàn)告訴我們一個(gè)原則——“小往大處靠”.下面就以兩地調(diào)

6、運(yùn)問題為例加以計(jì)算驗(yàn)證：如上圖，在公路上A、B兩地各有10噸、15噸麥子，問打麥場建在何處運(yùn)費(fèi)最少？　　設(shè)打麥場建在C點(diǎn)，則總運(yùn)費(fèi)是（假定每噸小麥運(yùn)輸1千米的費(fèi)用是a元）　　W＝10×a×AC＋15×a×BC　?。?0a×AC＋10a×BC＋5a×BC　?。?0a×（AC＋BC）＋5a×BC=10a×AB＋5a×BC　　上式中10a×AB是固定的值，不隨C點(diǎn)的選取而改變；只有5a×BC隨BC的變化而改變，若BC越小，則W也越小.當(dāng)BC=0時(shí)，即C點(diǎn)與B點(diǎn)重合時(shí)，W的值最小.因此打麥場建在B點(diǎn)時(shí)總運(yùn)費(fèi)是10a×AB（元）為

7、最少.顯然當(dāng)打麥場建在AB線段之外時(shí)，總運(yùn)費(fèi)都大于10a×AB（元）。解：根據(jù)“小往大處靠”的原則，先把一號倉庫的10噸貨物送往二號倉庫集中，需運(yùn)費(fèi)　　10×0.5×100=500（元）。　　這時(shí)可以認(rèn)為二號倉庫有30噸貨物，而五號倉庫有40噸貨物，于是又應(yīng)把二號倉庫的30噸貨物運(yùn)往五號倉庫集中，需運(yùn)費(fèi)　　30×0.5×300=4500（元）。　　所以，把貨物集中存放在五號倉庫時(shí)所花運(yùn)費(fèi)最少，需要　　500＋4500=5000（元）。　　說明：“小往大處靠”的原則也不是一成不變的，具體問題還要具體分析?！　≡倥e兩例如下：

8、　　例如一號倉庫有20噸貨物，二號倉庫有30噸貨物，其他倉庫存貨照樣如前，那么應(yīng)該往哪個(gè)倉庫集中呢？首先仍應(yīng)把一號倉庫的20噸貨物運(yùn)往二號倉庫集中，然后再把五號倉庫的40噸貨物也運(yùn)往二號倉庫集中，這樣運(yùn)費(fèi)最少?！　∮秩缫惶杺}庫有30噸貨物，二號倉庫有20噸貨物，其他倉庫存貨仍然如前，那么應(yīng)該往哪個(gè)倉庫集中呢？先把一號