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

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

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

3、、西安9臺，每臺機器的運費如卜表，如何調(diào)運才能使總費用最省?運到杭州西安北京600500洛陽800600法一：設(shè)從北京發(fā)杭州x個機器，則北京發(fā)西安11-x個機器，從洛陽發(fā)杭州7-x個機器，從洛陽發(fā)西安x-2個機器，依題意得：總費用=600 x+500(ll-x)+800(7-x)+600(x-2)=9900-100 x當x最人為7時候，總費用最少，為9200元。法二觀察表格，發(fā)現(xiàn)從北京調(diào)往杭州比從洛陽調(diào)往杭州每臺節(jié)約200元，而從北京調(diào)往西安比從杭州調(diào)往西安每臺節(jié)約100元，200100。可見從北京調(diào)往杭州更劃算。所以從北京往杭州調(diào)7臺，從北京往西安調(diào)4臺；從洛陽往西安調(diào)5臺?？傎M用最省，為9

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