數(shù)學模型第六講整數(shù)規(guī)劃模型與求解軟件市公開課獲獎課件

1、主講人：周大勇E-MAIL:理學院應用數(shù)學教研室 數(shù)學模型課程教學課件版權所有：大連交通大學理學院應用數(shù)學教研室 Copyright Dalian Jiaotong University. All rights reserved.-年第二學期第1頁第1頁第六講 整數(shù)規(guī)劃模型與0-1規(guī)劃 時間：3月24日主講人：周大勇E-MAIL:整數(shù)規(guī)劃模型及其處理辦法0-1規(guī)劃模型及其處理辦法數(shù)學軟件求解上述模型分析第2頁第2頁請各小組思考下列問題 數(shù)學規(guī)劃模型普通形式是什么？E-mail: 慣用處理規(guī)劃模型軟件有哪些？第3頁第3頁規(guī)劃模型構成及軟件處理實際問題中優(yōu)化模型x決議變量f(x)目的函數(shù)gi(x)

2、0約束條件數(shù)學規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃重點在模型建立和結(jié)果分析E-mail:處理軟件LindoLingo MatlabMathematica 第4頁第4頁設每月生產(chǎn)小、中、大型汽車數(shù)量分別為x1, x2, x3汽車廠生產(chǎn)計劃 模型建立 小型 中型 大型 既有量鋼材 1.5 3 5 600時間 280 250 400 60000利潤 2 3 4 線性規(guī)劃模型(LP)E-mail:第5頁第5頁模型求解 3） 模型中增長條件：x1, x2, x3 均為整數(shù)，重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST

3、 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，算出目的函數(shù)值z=629，與LP最優(yōu)值632.2581相差不大。2）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數(shù)值z，通過比較也許得到更優(yōu)解。 但必須檢查它們是否滿足約束條件。為何？請寫出在Lindo軟件源程序E-mail:第6

4、頁第6頁IP可用LINDO直接求解整數(shù)規(guī)劃(Integer Programming,簡記IP)“gin 3”表示“前3個變量為整數(shù)”，等價于：gin x1gin x2gin x3 IP 最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE 1) 632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000

5、 X3 0.000000 -4.000000 IP 結(jié)果輸出E-mail:第7頁第7頁其中3個子模型應去掉，然后逐一求解，比較目的函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：辦法1：分解為8個LP子模型 汽車廠生產(chǎn)計劃-討論 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。x1,x2, x3=0 或 80 x1=80，x2= 150，x3=0，最優(yōu)值z=610第8頁第8頁LINDO中對0-1變量限定：int y1int y2int y3 辦法2：引入0-1變量，化為整數(shù)規(guī)劃 M為大正數(shù)，可取1000 OBJECTIVE FUNCTION VALUE 1) 610.0000VARIABLE VALUE RE

6、DUCED 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)計劃。x1=0 或 80 x2=0 或 80 x3=0 或 80最優(yōu)解同前 E-mail:第9頁第9頁NLP即使可用現(xiàn)成數(shù)學軟件求解(如LINGO, MATLAB)，但是其結(jié)果常依賴于初值選擇。 辦法3：化為非線性規(guī)劃 非線性規(guī)劃（Non- Linear Programmi

7、ng，簡記NLP） 實踐表明，本例僅當初值非?？拷厦孓k法算出最優(yōu)解時，才干得到正確結(jié)果。 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。 x1=0 或 80 x2=0 或 80 x3=0 或 80E-mail:第10頁第10頁分派問題 接力隊選拔和選課策略若干項任務分給一些候選人來完成，每人專長不同，完成每項任務取得效益或需要資源就不同，怎樣分派任務使取得總效益最大，或付出總資源最少。若干種策略供選擇，不同策略得到收益或付出成本不同，各個策略之間有相互制約關系，怎樣在滿足一定條件下作出決擇，使得收益最大或成本最小。E-mail:第11頁第11頁丁蛙泳成績退步到115”2；戊自由泳成績進步到5

8、7”5, 構成接力隊方案是否應當調(diào)整？如何選拔隊員構成4100米混合泳接力隊?混合泳接力隊選拔 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”45名候選人百米成績窮舉法：構成接力隊方案共有5!=120種。E-mail:第12頁第12頁目的函數(shù)若選擇隊員i參與泳姿j 比賽，記xij=1, 不然記xij=0 0-1規(guī)劃模型 cij(秒)隊員i 第j 種泳姿百米成績約束條件每人最多入選泳姿之一 ciji=1i=2i=3i=4i=5j=166.8

9、57.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人 E-mail:第13頁第13頁模型求解 最優(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.4x54SUBJECT TO x11+x12+x13+x14 =1 x41+x42+x43+x44 =1 x11+x21+x31+x41+x51 =1 x

10、14+x24+x34+x44+x54 =1END INT 20 輸入LINDO求解 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.E-mail:第14頁第14頁丁蛙泳c43 =69.675.2，戊自由泳c54=62.4 57.5, 方案是否調(diào)整？ 敏感性分析？乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳IP規(guī)劃普通沒有與LP規(guī)劃相類似理論，LINDO輸出敏感性分析結(jié)果通常是沒故意義。最優(yōu)解：x21

11、= x32 = x43 = x54 = 1, 成績?yōu)?17”7 c43, c54 新數(shù)據(jù)重新輸入模型，用LINDO求解 指派(Assignment)問題：每項任務有且只有一人承擔，每人只能承擔一項，效益不同，怎樣分派使總效益最大. 討論甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.原方案E-mail:第15頁第15頁為了選修課程門數(shù)至少，應學習哪些課程 ？ 選課策略要求至少選兩門數(shù)學課、三門運籌學課和兩門計算機課 課號課名學分所屬類別先修課要求1微積分5數(shù)學2線性代數(shù)4數(shù)學3最優(yōu)化辦法4數(shù)學；運籌學微積分；線性代數(shù)4數(shù)據(jù)結(jié)構3數(shù)學；計算機計算機編程5應用統(tǒng)計4數(shù)學；運籌學微積分；線性代數(shù)6計算機模

12、擬3計算機；運籌學計算機編程7計算機編程2計算機8預測理論2運籌學應用統(tǒng)計9數(shù)學試驗3運籌學；計算機微積分；線性代數(shù)選修課程最少，且學分盡也許多，應學習哪些課程 ？ E-mail:第16頁第16頁0-1規(guī)劃模型 決議變量 目的函數(shù) xi=1 選修課號i 課程（xi=0 不選） 選修課程總數(shù)至少 約束條件至少2門數(shù)學課，3門運籌學課，2門計算機課。 課號課名所屬類別1微積分數(shù)學2線性代數(shù)數(shù)學3最優(yōu)化辦法數(shù)學；運籌學4數(shù)據(jù)結(jié)構數(shù)學；計算機5應用統(tǒng)計數(shù)學；運籌學6計算機模擬計算機；運籌學7計算機編程計算機8預測理論運籌學9數(shù)學試驗運籌學；計算機E-mail:第17頁第17頁先修課程要求最優(yōu)解： x1

13、 = x2 = x3 = x6 = x7 = x9 =1, 其它為0；6門課程，總學分21 0-1規(guī)劃模型 約束條件x3=1必有x1 = x2 =1模型求解（LINDO） 課號課名先修課要求1微積分2線性代數(shù)3最優(yōu)化辦法微積分；線性代數(shù)4數(shù)據(jù)結(jié)構計算機編程5應用統(tǒng)計微積分；線性代數(shù)6計算機模擬計算機編程7計算機編程8預測理論應用統(tǒng)計9數(shù)學試驗微積分；線性代數(shù)E-mail:第18頁第18頁學分最多多目的優(yōu)化處理辦法：化成單目的優(yōu)化。兩目的(多目的)規(guī)劃 討論：選修課程最少，學分盡也許多，應學習哪些課程？ 課程至少 以學分最多為目的，無論課程多少。 以課程至少為目的，無論學分多少。最優(yōu)解如上，6門

14、課程，總學分21 。最優(yōu)解顯然是選修所有9門課程 。E-mail:第19頁第19頁多目的規(guī)劃 在課程至少前提下以學分最多為目的。最優(yōu)解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它為0；總學分由21增至22。注意：最優(yōu)解不唯一！課號課名學分1微積分52線性代數(shù)43最優(yōu)化辦法44數(shù)據(jù)結(jié)構35應用統(tǒng)計46計算機模擬37計算機編程28預測理論29數(shù)學試驗3 LINDO無法告訴優(yōu)化問題解是否唯一?？蓪9 =1 易為x6 =1增長約束 ，以學分最多為目的求解。E-mail:第20頁第20頁多目的規(guī)劃 對學分數(shù)和課程數(shù)加權形成一個目的，如三七開。 最優(yōu)解： x1 = x2 =

15、x3 = x4 = x5 = x6 = x7 = x9 =1，其它為0；總學分28。課號課名學分1微積分52線性代數(shù)43最優(yōu)化辦法44數(shù)據(jù)結(jié)構35應用統(tǒng)計46計算機模擬37計算機編程28預測理論29數(shù)學試驗3 E-mail:第21頁第21頁討論與思考最優(yōu)解與1=0，2=1結(jié)果相同學分最多多目的規(guī)劃 最優(yōu)解與1=1，2=0結(jié)果相同課程至少E-mail:第22頁第22頁“課程論文二”公布時間，請安靜！ 論文上交時間： 9月 27 日E-mail:注意 （1）封面必須是打印版，格式已下發(fā) （2）從摘要開始所有為手寫稿。第23頁第23頁課程論文評分原則 辦法新奇巧妙，格式非常好 20分模型建立，求解合

16、理，格式較好 18-19分 模型建立，求解合理，格式規(guī)范 16-17分模型建立，求解基本合理，格式普通 14-15分模型建立，求解有問題，格式普通 12-13分模型建立不正確，格式糟糕，態(tài)度有問題 0-6分E-mail:第24頁第24頁E-mail:A題：營養(yǎng)配餐問題每種蔬菜含有營養(yǎng)素成份是不同，從醫(yī)學上知道，每人每七天對每種營養(yǎng)成份最低需求量。某醫(yī)院營養(yǎng)室在制訂下一周菜單時，需要確定表A-1中所列六種蔬菜供應量，方便使費用最小而又能滿足營養(yǎng)素等其它方面要求。要求白菜供應一周內(nèi)不多于20 kg，其它蔬菜供應在一周內(nèi)不多于40kg，每七天共需供應140kg蔬菜，為了使費用最小又滿足營養(yǎng)素等其它方面要求，試建立數(shù)學模型，說明在下一周內(nèi)應該供應每種蔬菜各多少kg？第25頁第25頁表A-1E-mail:第26頁第26頁B題:廣告