學(xué)而思講義第13講---統(tǒng)籌與最優(yōu)化(競賽班程度)

1、第十三講統(tǒng)籌與最優(yōu)化木講用繞盡可能在節(jié)省人力物力時間的前提卜，在允許的范用內(nèi)獲得最好的效 益這個中心，出現(xiàn)了以卜兒類題型：d過河（橋）問題：解題思路1、選擇時間瑕少的兩個過河，到達對岸后，選擇時間垠少的一個返回;2、選擇時間最多的兩個過河，到達對岸后，選擇時間最少的-個返回:3、反復(fù)上邊1、2步驟，貢至全部過河為止。如：騎牛趕牛題；夜里打燈過橋題。4排隊等待題：解題思路1、將所用時間從小到人排出一列：2、按照分配對彖個數(shù)分出組數(shù)：3、從左到右，從上到卜地將時間分配到備組。例：水龍頭打水趣（水龍頭的個數(shù)決'足組數(shù)）；機器加匚零件（機器數(shù)決定組數(shù)）; 維修隊維修電器（維修隊個數(shù)決定組數(shù)）2

2、集合點選址：解題思路1、如果線上有奇數(shù)（2n+l）個點，集介點位于第n個點：2、如果線上有偶數(shù)（2n）個點，集合點位J：第11個點到第n+1個點之間的線段 上均可。例：街道上選公交站；1993個少先隊員選集介點。4 倉庫選址：原則：“小往人靠，支往干靠”。解題思路1、先觀察圖形，選定最人點出發(fā)，考慮它與另一邊的大小。如果大，倉庫選 在此。如果小，它往另一邊的最近點靠。2、重復(fù)上一步，比較被靠上點的數(shù)與其另一邊的人小。如果人，倉庫選在此。 如果小，它往另一邊最近點靠。3、覓復(fù)上一步，貢至確定倉庫選址。例：倉庫選址、小學(xué)選址、糖廠選址、麥場選址d 調(diào)運貨物問題：例:北京、洛陽分別仃11臺和5臺完全

3、柑同的機器，準(zhǔn)備調(diào)運給杭州7臺、西安9臺,每臺機器的運費如卜表,如何調(diào)運才能使總費用蜃省?運到杭州西安北京600500洛陽800600法一：設(shè)從北京發(fā)杭州x個機器，則北京發(fā)西安11-x個機器，從洛陽發(fā)杭州7-x 個機器，從洛陽發(fā)西安x-2個機器，依題意得：總費用= 600x+500(ll-x)+800(7-x)+600(x-2)= 9900-100工當(dāng)x最人為7時候，總費用最少，為9200元。法二：觀察農(nóng)格，發(fā)現(xiàn)從北京調(diào)往杭州比從洛陽調(diào)往杭州毎臺卩約200尤，而從北 京調(diào)往西安比從杭州調(diào)往兩安每臺節(jié)約100元，200>1009可見從北京調(diào)往杭州更 劃算。所以從北京往杭州調(diào)7臺，從北京往西

4、安調(diào)4臺；從洛陽往芮安調(diào)5臺?？傎M用垠 省，為9200元。(法二雖然更簡單，但務(wù)必耍學(xué)握法一)競賽班 A、E兩個糧店分別何70噸和60噸人米，甲、乙、丙三個居民點分別 需要30噸、40噸和50噸大米。從A、B兩糧店每運1噸大米到三個居民點的費用 如2如何調(diào)運才能最省錢？運到甲乙丙A273B3105【分析】方法如上題法:,觀察圖形：3-2=1, 10-7=3, 5-3=2貞屮第二列差最人。 因此A糧店的人米應(yīng)盡力可能多的供應(yīng)給乙，即A供應(yīng)給乙40噸。同理, 第三列的差比第一列的差大，A店余卜的30噸給了丙。丙還差20噸，從E糧店調(diào)20噸。F是B糧店余F40噸。從這40噸當(dāng)中調(diào)出30噸給甲。 此時運費址少。為：30x3 + 40x7 + 30x3 + 20x5 = 560元。調(diào)運方案如下:A04030B30020丄物資流向圖：原則一一避免對流例：勘探隊調(diào)整人數(shù)題4勞力組介之效率比問題：多種勞力（或者機械）干兩種配套活的一般分工原則：設(shè)甲生產(chǎn)A產(chǎn)陽與生產(chǎn)E產(chǎn)