數(shù)學(xué)模型第六講整數(shù)規(guī)劃模型與求解軟件-2011.ppt

主講人：周大勇 E-MAIL:理學(xué)院應(yīng)用數(shù)學(xué)教研室,數(shù)學(xué)模型課程教學(xué)課件,版權(quán)所有：大連交通大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)教研室 Copyright 2011 Dalian Jiaotong University. All rights reserved.,2010-2011學(xué)年第二學(xué)期,第六講 整數(shù)規(guī)劃模型與0-1規(guī)劃,時(shí)間：2011年3月24日 主講人：周大勇 E-MAIL:,整數(shù)規(guī)劃模型及其處理方法 0-1規(guī)劃模型及其處理方法 數(shù)學(xué)軟件求解上述模型分析,請(qǐng)各小組思考下列問題,數(shù)學(xué)規(guī)劃模型的一般形式是什么？,E-mail:,常用的解決規(guī)劃模型的軟件有哪些？,規(guī)劃模型構(gòu)成及軟件處理,實(shí)際問題中 的優(yōu)化模型,x決策變量,f(x)目標(biāo)函數(shù),gi(x)0約束條件,數(shù)學(xué)規(guī)劃,線性規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃,重點(diǎn)在模型的建立和結(jié)果的分析,E-mail:,處理軟件,Lindo Lingo Matlab Mathematica,設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1, x2, x3,汽車廠生產(chǎn)計(jì)劃,模型建立,線性規(guī)劃模型(LP),E-mail:,模型求解,3） 模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。,OBJECTIVE FUNCTION VALUE 1) 632.2581 VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.000000 0.003226,結(jié)果為小數(shù)，怎么辦？,1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)=629，與LP最優(yōu)值632.2581相差不大。,2）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值z(mì)，通過比較可能得到更優(yōu)的解。,但必須檢驗(yàn)它們是否滿足約束條件。為什么？,請(qǐng)寫出在Lindo軟件的源程序,E-mail:,IP可用LINDO直接求解,整數(shù)規(guī)劃(Integer Programming,簡(jiǎn)記IP),“gin 3”表示“前3個(gè)變量為整數(shù)”，等價(jià)于： gin x1 gin x2 gin x3,IP 的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632,max 2x1+3x2+4x3 st 1.5x1+3x2+5x3600 280x1+250x2+400x360000 end gin 3,OBJECTIVE FUNCTION VALUE 1) 632.0000 VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000,IP 結(jié)果輸出,E-mail:,其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：,方法1：分解為8個(gè)LP子模型,汽車廠生產(chǎn)計(jì)劃-討論,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。,x1,x2, x3=0 或 80,x1=80，x2= 150，x3=0，最優(yōu)值z(mì)=610,LINDO中對(duì)0-1變量的限定： int y1 int y2 int y3,方法2：引入0-1變量，化為整數(shù)規(guī)劃,M為大的正數(shù)，可取1000,OBJECTIVE FUNCTION VALUE 1) 610.0000 VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。,x1=0 或 80,最優(yōu)解同前,E-mail:,NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO, MATLAB)，但是其結(jié)果常依賴于初值的選擇。,方法3：化為非線性規(guī)劃,非線性規(guī)劃（Non- Linear Programming，簡(jiǎn)記NLP）,實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí)，才能得到正確的結(jié)果。,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。,x1=0 或 80,E-mail:,分派問題,接力隊(duì)選拔和選課策略,若干項(xiàng)任務(wù)分給一些候選人來完成，每人的專長不同，完成每項(xiàng)任務(wù)取得的效益或需要的資源就不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少。,若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個(gè)策略之間有相互制約關(guān)系，如何在滿足一定條件下作出決擇，使得收益最大或成本最小。,E-mail:,丁的蛙泳成績退步到115”2；戊的自由泳成績進(jìn)步到57”5, 組成接力隊(duì)的方案是否應(yīng)該調(diào)整？,如何選拔隊(duì)員組成4100米混合泳接力隊(duì)?,混合泳接力隊(duì)的選拔,5名候選人的百米成績,窮舉法：組成接力隊(duì)的方案共有5!=120種。,E-mail:,目標(biāo)函數(shù),若選擇隊(duì)員i參加泳姿j 的比賽，記xij=1, 否則記xij=0,0-1規(guī)劃模型,cij(秒)隊(duì)員i 第j 種泳姿的百米成績,約束條件,每人最多入選泳姿之一,每種泳姿有且只有1人,E-mail:,模型求解,最優(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求解,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,E-mail:,丁蛙泳c43 =69.675.2，戊自由泳c54=62.4 57.5, 方案是否調(diào)整？,敏感性分析？,乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳,IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。,最優(yōu)解：x21 = x32 = x43 = x54 = 1, 成績?yōu)?17”7,c43, c54 的新數(shù)據(jù)重新輸入模型，用LINDO求解,指派(Assignment)問題：每項(xiàng)任務(wù)有且只有一人承擔(dān)，每人只能承擔(dān)一項(xiàng)，效益不同，怎樣分派使總效益最大.,討論,E-mail:,為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程 ？,選課策略,要求至少選兩門數(shù)學(xué)課、三門運(yùn)籌學(xué)課和兩門計(jì)算機(jī)課,選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程 ？,E-mail:,0-1規(guī)劃模型,決策變量,目標(biāo)函數(shù),xi=1 選修課號(hào)i 的課程（xi=0 不選）,選修課程總數(shù)最少,約束條件,最少2門數(shù)學(xué)課，3門運(yùn)籌學(xué)課， 2門計(jì)算機(jī)課。,E-mail:,先修課程要求,最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它為0；6門課程，總學(xué)分21,0-1規(guī)劃模型,約束條件,x3=1必有x1 = x2 =1,模型求解（LINDO）,E-mail:,學(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é)分多少。,E-mail:,多目標(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,E-mail:,多目標(biāo)規(guī)劃,對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開。,最優(yōu)解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1， 其它為0；總學(xué)分28。,E-mail:,討論與思考,最優(yōu)解與1=0，2=1的結(jié)果相同學(xué)分最多,多目標(biāo)規(guī)劃,最優(yōu)解與1=1，2=0的結(jié)果相同課程最少,E-mail:,“課程論文二”發(fā)布時(shí)間，請(qǐng)安靜！,論文上交時(shí)間：2011年 9月 27 日,E-mail:,注意 （1）封面必須是打印版，格式已下發(fā) （2）從摘要開始全部為手寫稿。,課程論文評(píng)分標(biāo)準(zhǔn),方法新穎巧妙，格式非常好 20分 模型建立，求解合理，格式很好 18-19分 模型建立，求解合理，格式規(guī)范 16-17分 模型建立，求解基本合理，格式一般 14-15分 模型建立，求解有問題，格式一般 12-13分 模型建立不正確，格式糟糕，態(tài)度有問題 0-6分,E-mail:,E-mail:,A題：營養(yǎng)配餐問題 每種蔬菜含有的營養(yǎng)素成份是不同的，從醫(yī)學(xué)上知道，每人每周對(duì)每種營養(yǎng)成分的最低需求量。某醫(yī)院營養(yǎng)室在制定下一周菜單時(shí)，需要確定表A-1中所列六種蔬菜的供應(yīng)量，以便使費(fèi)用最小而又能滿足營養(yǎng)素等其它方面的要求。規(guī)定白菜的供應(yīng)一周內(nèi)不多于20 kg，其它蔬菜的供應(yīng)在一周內(nèi)不多于40kg，每周共需供應(yīng)140kg蔬菜，為了使費(fèi)用最小又滿足營養(yǎng)素等其它方面的要求，試建立數(shù)學(xué)模型，說明在下一周內(nèi)應(yīng)當(dāng)供應(yīng)每種蔬菜各多少kg？,表A-1,E-mail:,B題 :廣告競(jìng)爭(zhēng)計(jì)劃 某市場(chǎng)研究小組考慮下一步如何選擇廣告競(jìng)爭(zhēng)計(jì)劃，在進(jìn)行大量的調(diào)查研究后，制定了各種可供選擇的方案，