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

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

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

3、柑同的機(jī)器，準(zhǔn)備調(diào)運(yùn)給杭州7臺、西安9臺,每臺機(jī)器的運(yùn)費(fèi)如卜表,如何調(diào)運(yùn)才能使總費(fèi)用蜃省?運(yùn)到杭州西安北京600500洛陽800600法一：設(shè)從北京發(fā)杭州x個(gè)機(jī)器，則北京發(fā)西安11-x個(gè)機(jī)器，從洛陽發(fā)杭州7-x 個(gè)機(jī)器，從洛陽發(fā)西安x-2個(gè)機(jī)器，依題意得：總費(fèi)用= 600x+500(ll-x)+800(7-x)+600(x-2)= 9900-100工當(dāng)x最人為7時(shí)候，總費(fèi)用最少，為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(fèi)用垠 省，為9200元。(法二雖然更簡單，但務(wù)必耍學(xué)握法一)競賽班 A、E兩個(gè)糧店分別何70噸和60噸人米，甲、乙、丙三個(gè)居民點(diǎn)分別 需要30噸、40噸和50噸大米。從A、B兩糧店每運(yùn)1噸大米到三個(gè)居民點(diǎn)的費(fèi)用 如2如何調(diào)運(yùn)才能最省錢？運(yùn)到甲乙丙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噸給甲。 此時(shí)運(yùn)費(fèi)址少。為：30x3 + 40x7 + 30x3 + 20x5 = 560元。調(diào)運(yùn)方案如下:A04030B30020丄物資流向圖：原則一一避免對流例：勘探隊(duì)調(diào)整人數(shù)題4勞力組介之效率比問題：多種勞力（或者機(jī)械）干兩種配套活的一般分工原則：設(shè)甲生產(chǎn)A產(chǎn)陽與生產(chǎn)E產(chǎn)