線性規(guī)劃模型自來水輸送混合泳接力隊的選拔.ppt

1、線性規(guī)劃模型,指導(dǎo)老師: 梁海峰,其他費用:450元/千噸,應(yīng)如何分配水庫供水量，公司才能獲利最多？,若水庫供水量都提高一倍，公司利潤可增加到多少？,運(yùn)輸問題：自來水輸送,收入：900元/千噸,支出,總供水量：160,確定送水方案使利潤最大,問題分析, 總需求量：120+180=300,總收入900160=144,000(元),收入：900元/千噸,其他費用:450元/千噸,支出,引水管理費,其他支出450160=72,000(元),供應(yīng)限制,約束條件,需求限制,線性規(guī)劃模型(LP),目標(biāo)函數(shù),水庫i 向j 區(qū)的日供水量為 xij（x34=0）,決策變量,模型建立,確定3個水庫向4個小區(qū)的供水

2、量,模型求解,OBJECTIVE FUNCTION VALUE 1) 24400.00 VARIABLE VALUE REDUCED COST X11 0.000000 30.000000 X12 50.000000 0.000000 X13 0.000000 50.000000 X14 0.000000 20.000000 X21 0.000000 10.000000 X22 50.000000 0.000000 X23 0.000000 20.000000 X24 10.000000 0.000000 X31 40.000000 0.000000 X32 0.000000 10.00000

3、0 X33 10.000000 0.000000,利潤=總收入-其它費用-引水管理費=144000-72000-24400 = 47600（元）,引水管理費 24400(元),丁的蛙泳成績退步到115”2；戊的自由泳成績進(jìn)步到57”5, 組成接力隊的方案是否應(yīng)該調(diào)整？,如何選拔隊員組成4100米混合泳接力隊?,5名候選人的百米成績,窮舉法：組成接力隊的方案共有5!=120種。,0-1規(guī)劃分配問題：混合泳接力隊的選拔,目標(biāo)函數(shù),若選擇隊員i參加泳姿j 的比賽，記xij=1, 否則記xij=0,cij(秒)隊員i 第j 種泳姿的百米成績,約束條件,每人最多入選泳姿之一,每種泳姿有且只有1人,0-1

4、規(guī)劃模型,模型求解,最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其它變量為0; 成績?yōu)?53.2(秒)=413”2,MIN 66.8x11+75.6x12+87x13+58.6x14 + +67.4x51+71 x52+83.8x53+62.4x54 SUBJECT TO x11+x12+x13+x14 =1 x41+x42+x43+x44 =1 x11+x21+x31+x41+x51 =1 x14+x24+x34+x44+x54 =1 END INT 20,輸入LINDO求解,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,丁蛙泳c43 =69.675.2，戊自由泳c54=62

5、.4 57.5, 方案是否調(diào)整？,敏感性分析？,乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳,IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。,最優(yōu)解：x21 = x32 = x43 = x51 = 1, 成績?yōu)?17”7,c43, c54 的新數(shù)據(jù)重新輸入模型，用LINDO求解,指派(Assignment)問題：每項任務(wù)有且只有一人承擔(dān)，每人只能承擔(dān)一項，效益不同，怎樣分派使總效益最大.,討論,為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程 ？,多目標(biāo)規(guī)劃：選課策略,要求至少選兩門數(shù)學(xué)課、三門運(yùn)籌學(xué)課和兩門計算機(jī)課,選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程 ？,0

6、-1規(guī)劃模型,決策變量,目標(biāo)函數(shù),xi=1 選修課號i 的課程（xi=0 不選）,選修課程總數(shù)最少,約束條件,最少2門數(shù)學(xué)課，3門運(yùn)籌學(xué)課， 2門計算機(jī)課。,先修課程要求,最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它為0；6門課程，總學(xué)分21,0-1規(guī)劃模型,約束條件,x3=1必有x1 = x2 =1,模型求解（LINDO）,學(xué)分最多,多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。,兩目標(biāo)(多目標(biāo))規(guī)劃,討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？,課程最少,以學(xué)分最多為目標(biāo)，不管課程多少。,以課程最少為目標(biāo)，不管學(xué)分多少。,最優(yōu)解如上，6門課程，總學(xué)分21 。,最優(yōu)解顯然是選修所有9門課程 。,多目標(biāo)規(guī)劃,在課程最少的前提下以學(xué)分最多為目標(biāo)。,最優(yōu)解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它為0；總學(xué)分由21增至22。,注意：最優(yōu)解不唯一！,LINDO無法告訴優(yōu)化問題的解是否唯一。,可將x9 =1 易為x6 =1,增加約束 ， 以學(xué)分最多為目標(biāo)求解。,多目標(biāo)規(guī)劃,對學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個目標(biāo)，如三七開。,最優(yōu)解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x