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

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

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

2、30（米）.　　因此，先派20輛車都從A開始運渣土到B，再空車開往C運磚到D后空車返回A，這樣每輛車跑兩圈就完成了運磚任務(wù).然后再派這20輛車都從A運渣土到B再空車返回A，則運渣土任務(wù)也完成了.這時總共空車跑了　　330×40+300×20＝19200（米）.　　后一種調(diào)運方案比前一種減少跑空車13200米，這是最佳節(jié)油的調(diào)運方案?！　≌f明：“節(jié)省跑空車的距離”是物資調(diào)運問題的一個原則：下面通過例子再介紹“避免對流”的原則。例2一支勘探隊在五個山頭A、B、C、D、E設(shè)立了基地，人數(shù)如右圖所示.為調(diào)整使各基地人數(shù)相同，如何調(diào)動最方便？（調(diào)動時不考慮路程遠近）　　分析在人員

3、調(diào)運時不考慮路程遠近的因素，就只需避免兩個基地之間相互調(diào)整，即“避免對流現(xiàn)象”。　　解：五個基地人員總數(shù)為　　17+4+16+14+9=60（人）　　依題意，調(diào)整后每個基地應(yīng)各有　　60÷5=12（人）。　　因此，需要從多于12人的基地A、C、D向不足12人的基地B、E調(diào)人.為了避免對流，經(jīng)試驗容易得到調(diào)整方案如下：　　先從D調(diào)2人到E，這樣E尚缺1人；再由A調(diào)1人給E，則E達到要求.此時，A尚多余4人，C也多余4人，總共8人全部調(diào)到B，則B亦符合要求?！　≌{(diào)動示意圖如右圖所示.這樣的圖形叫做物資流向圖.用流向圖代替調(diào)運方案，能直觀地看出調(diào)運狀況及有無對流現(xiàn)象，又可避免

4、列表和計算的麻煩，圖中箭頭表示流向，箭桿上　　的數(shù)字表示流量?！　≌f明：發(fā)生對流的調(diào)運方案不可能是最優(yōu)方案.這個原則可以證明：　　如右圖，設(shè)A1B2＝a千米，B2B1=b千米，B1A2＝c千米.如果從A1運1噸貨物到B1，同時又從A2運1噸貨物到B2，那么在B1B2之間A1的物資從西向東運輸，A2的貨物從東向西運輸，兩者發(fā)生對流，于是這樣調(diào)動的總噸千米數(shù)為　?。╝＋b）+（b＋c）＝a＋c+2b.　　而如果從A1運1噸貨物到B2，同時從A2運1噸貨物到B1，栽蛟聳渥芏智資猘+c.顯然　　a+c＜a+c+2b。例3在一條公路上每隔100千米有一個倉庫（如右圖，）共有5

5、個倉庫.一號倉庫存有10噸貨物，二號倉庫有20噸貨物，五號倉庫存有40噸貨物，其余兩個倉庫是空的?，F(xiàn)在想把所有的貨物集中存放在一個倉庫里，如果每噸貨物運輸1公里需要0.5元運輸費，那么最少要多少運費才行？　　分析欲使花費的運輸費少，關(guān)鍵在于運輸?shù)呢浳锖吐烦瘫M可能少，實際經(jīng)驗告訴我們一個原則——“小往大處靠”.下面就以兩地調(diào)運問題為例加以計算驗證：如上圖，在公路上A、B兩地各有10噸、15噸麥子，問打麥場建在何處運費最少？　　設(shè)打麥場建在C點，則總運費是（假定每噸小麥運輸1千米的費用是a元）　　W＝10×a×AC＋15×a×BC　?。?0a×AC＋10a×BC＋5a×B

6、C　　＝10a×（AC＋BC）＋5a×BC=10a×AB＋5a×BC　　上式中10a×AB是固定的值，不隨C點的選取而改變；只有5a×BC隨BC的變化而改變，若BC越小，則W也越小.當(dāng)BC=0時，即C點與B點重合時，W的值最小.因此打麥場建在B點時總運費是10a×AB（元）為最少.顯然當(dāng)打麥場建在AB線段之外時，總運費都大于10a×AB（元）。解：根據(jù)“小往大處靠”的原則，先把一號倉庫的10噸貨物送往二號倉庫集中，需運費　　10×0.5×100=500（元）?！　∵@時可以認為二號倉庫有30噸貨物，而五號倉庫有40噸貨物，于是又應(yīng)把二號倉庫的30噸貨物運往五號倉庫集中，需

7、運費　　30×0.5×300=4500（元）。　　所以，把貨物集中存放在五號倉庫時所花運費最少，需要　　500＋4500=5000（元）。　　說明：“小往大處靠”的原則也不是一成不變的，具體問題還要具體分析?！　≡倥e兩例如下：　　例如一號倉庫有20噸貨物，二號倉庫有30噸貨物，其他倉庫存貨照樣如前，那么應(yīng)該往哪個倉庫集中呢？首先仍應(yīng)把一號倉庫的20噸貨物運往二號倉庫集中，然后再把五號倉庫的40噸貨物也運往二號倉庫集中，這樣運費最少?！　∮秩缫惶杺}庫有30噸貨物，二號倉庫有20噸貨物，其他倉庫存貨仍然如前，那么應(yīng)該往哪個倉庫集中呢？先把一號