最優(yōu)化問題最新課件

1、第四章 最優(yōu)化問題主講：陳元安電子信箱：商丘職業(yè)技術(shù)學(xué)院 愛因斯坦的一句名言： 想象力比知識更重要！因為知識是有限的，而想象力包括世界的一切，是知識的源泉。要 點歷年回顧:92A題施肥效果分析 回歸分析 數(shù)據(jù)擬合92B題實驗數(shù)據(jù)分解 離散模型、組合最優(yōu)化93A非線性交調(diào)的頻率設(shè)計 擬合、規(guī)劃 93B足球隊排名 圖論、層次分析、整數(shù)規(guī)劃 94A逢山開路 圖論、插值、動態(tài)規(guī)劃 94B鎖具裝箱問題 圖論、組合數(shù)學(xué) 95A飛行管理問題 非線性規(guī)劃、線性規(guī)劃 95B天車與冶煉爐的作業(yè)調(diào)度 動態(tài)規(guī)劃、排隊論、圖論 96A最優(yōu)捕魚策略 微分方程、優(yōu)化 96B節(jié)水洗衣機(jī) 非線性規(guī)劃 97A零件的參數(shù)設(shè)計 非線

2、性規(guī)劃 97B截斷切割的最優(yōu)排列 隨機(jī)模擬、圖論 98A一類投資組合問題 多目標(biāo)優(yōu)化、非線性規(guī)劃 98B災(zāi)情巡視的最佳路線 圖論、組合優(yōu)化 99A自動化車床管理 隨機(jī)優(yōu)化、計算機(jī)模擬 99B鉆井布局 0-1規(guī)劃、圖論 00A DNA序列分類 模式識別、Fisher判別、 人工神經(jīng)網(wǎng)絡(luò) 00B鋼管訂購和運輸 組合優(yōu)化、運輸問題 01A血管三維重建 曲線擬合、曲面重建 01B 公交車調(diào)度問題 多目標(biāo)規(guī)劃 02A車燈線光源的優(yōu)化 非線性規(guī)劃 02B彩票問題 單目標(biāo)決策 03A SARS的傳播 微分方程、差分方程 03B 露天礦生產(chǎn)的車輛安排 整數(shù)規(guī)劃、運輸問題04A奧運會臨時超市網(wǎng)點設(shè)計 統(tǒng)計分析、

3、數(shù)據(jù)處理、優(yōu)化04B電力市場的輸電阻塞管理 數(shù)據(jù)擬合、優(yōu)化 05A長江水質(zhì)的評價和預(yù)測 預(yù)測評價、數(shù)據(jù)處理 05B DVD在線租賃 隨機(jī)規(guī)劃、整數(shù)規(guī)劃 06A出版社書號問題 整數(shù)規(guī)劃、數(shù)據(jù)處理、優(yōu)化 06B Hiv病毒問題 線性規(guī)劃、回歸分析解法規(guī)劃問題圖論差微分方程數(shù)據(jù)擬合模擬處理優(yōu)化數(shù)據(jù)分析理論其它（排隊運輸離散）相關(guān)賽題93A,93B94A,95A95B,96B97A,98A99B,01B02A,03B06A,06B07B,09B10A93B94A94B95B97B98B99B07B96A03A07A08A09A92A,93A97B,99A01A,04A04B,05A06A,07A08B

4、,10A10B92B,96A98A,98B99A,00B 02B,04A04B,06A07A,08A93B04A09A09B10B92B94A94B95B00A00B合計1785131266賽題發(fā)展的特點： 1. 對選手的計算機(jī)能力提出了更高的要求：賽題的解決依賴計算機(jī)，題目的數(shù)據(jù)較多，手工計算不能完成，如03B，某些問題需要使用計算機(jī)軟件，01A。問題的數(shù)據(jù)讀取需要計算機(jī)技術(shù)，如00A（大數(shù)據(jù)），01A（圖象數(shù)據(jù)，圖象處理的方法獲得），04A（數(shù)據(jù)庫數(shù)據(jù)，數(shù)據(jù)庫方法，統(tǒng)計軟件包）。計算機(jī)模擬和以算法形式給出最終結(jié)果。 2. 賽題的開放性增大解法的多樣性，一道賽題可用多種解法。開放性還表現(xiàn)在對

5、模型假設(shè)和對數(shù)據(jù)處理上。 3. 試題向大規(guī)模數(shù)據(jù)處理方向發(fā)展 4. 求解算法和各類現(xiàn)代算法的融合，5.更關(guān)注于當(dāng)年的實事問題eg：04A奧運會臨時超市網(wǎng)點設(shè)計，07B 乘公交，看奧運，10B 2010年上海世博會影響力的定量評估等；引言4.1 線性規(guī)劃模型 4.2 整數(shù)規(guī)劃模型4.3 二次規(guī)劃模型4.4 非線性規(guī)劃模型4.5 應(yīng)用案例：搶渡長江問題4.6 應(yīng)用案例練習(xí)4.7 最優(yōu)化軟件規(guī)劃模型的應(yīng)用極其廣泛，其作用已為越來越多的人所重視.隨著計算機(jī)的逐漸普及，它越來越急速地滲透于工農(nóng)業(yè)生產(chǎn)、商業(yè)活動、軍事行為核科學(xué)研究的各個方面，為社會節(jié)省的財富、創(chuàng)造的價值無法估量. 在數(shù)模競賽過程中，規(guī)劃模

6、型是最常見的一類數(shù)學(xué)模型. 從92-2011年全國大學(xué)生數(shù)模競賽試題的解題方法統(tǒng)計結(jié)果來看，規(guī)劃模型共出現(xiàn)了16次，占到了近50%，也就是說每兩道競賽題中就有一道涉及到利用規(guī)劃理論來分析、求解. 最優(yōu)化是一門應(yīng)用十分廣泛的學(xué)科，它研究在有限種或無限種可行方案中挑選最優(yōu)方案，構(gòu)造尋求最優(yōu)解的計算方法。達(dá)到最優(yōu)目標(biāo)的方案，稱為最優(yōu)方案，搜索最優(yōu)方案的方法，稱為最優(yōu)化方法。這種方法的數(shù)學(xué)理論，稱為最優(yōu)化理論。最優(yōu)化方法已廣泛應(yīng)用于空間技術(shù)、軍事科學(xué)、電子工程、通訊工程、自動控制、系統(tǒng)識別、資源分配、計算數(shù)學(xué)、經(jīng)濟(jì)管理等等領(lǐng)域。最優(yōu)化方法包括的內(nèi)容很廣泛，如線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、多

7、目標(biāo)規(guī)劃、組合優(yōu)化等等。運用最優(yōu)化方法解決最優(yōu)化問題的一般方法步驟如下：前期分析：分析問題，找出要解決的目標(biāo)，約束條件，并確立最優(yōu)化的目標(biāo)。定義變量，建立最優(yōu)化問題的數(shù)學(xué)模型，列出目標(biāo)函數(shù)和約束條件。針對建立的模型，選擇合適的求解方法或數(shù)學(xué)軟件。編寫程序，利用計算機(jī)求解。對結(jié)果進(jìn)行分析，討論諸如：結(jié)果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與誤差等。線 性 規(guī) 劃某豆腐店用黃豆制作兩種不同口感的豆腐出售。制作口感較鮮嫩的豆腐每千克需要0.3千克一級黃豆及0.5千克二級黃豆，售價10元；制作口感較厚實的豆腐每千克需要0.4千克一級黃豆及0.2千克二級黃豆，售價5元?，F(xiàn)小店購

8、入9千克一級黃豆和8千克二級黃豆。問：應(yīng)如何安排制作計劃才能獲得最大收益。一、問題前期分析該問題是在不超出制作兩種不同口感豆腐所需黃豆總量條件下合理安排制作計劃，使得售出各種豆腐能獲得最大收益。二、模型假設(shè)1假設(shè)制作的豆腐能全部售出。2假設(shè)豆腐售價無波動。變量假設(shè)： 設(shè)計劃制作口感鮮嫩和厚實的豆腐各x1千克和 x2千克，可獲得收益R元。目標(biāo)函數(shù)：獲得的總收益最大。 總收益可表示為： 受一級黃豆數(shù)量限制： 受二級黃豆數(shù)量限制： 綜上分析，得到該問題的線性規(guī)劃模型 s.t.LINGO程序：max=10*x1+5*x2;0.3*x1+0.4*x2=9;0.5*x1+0.2*x2=8;4.1、線性規(guī)劃

9、模型 線性規(guī)劃模型是所有規(guī)劃模型中最基本、最例1.（食譜問題）設(shè)有 n 種食物，各含 m 種營養(yǎng)素，第 j 種食物中第 i 種營養(yǎng)素的含量為 aij , n 種食物價格分別為c1, c2, , cn，請確定食譜中n 種食物的數(shù)量x1, x2, , xn，要求在食譜中 m 種營養(yǎng)素簡單的一種. 4.1 線性規(guī)劃模型的基本形式 的含量分別不低于b1, b2, , bm 的情況下，使得總總的費用最低. 首先根據(jù)食物數(shù)量及價格可寫出食譜費用為 其次食譜中第 i 種營養(yǎng)素的含量為 因此上述問題可表述為： 解線性規(guī)劃的數(shù)學(xué)模型max z = S.T線性規(guī)劃、線性規(guī)劃的可行解，最優(yōu)解的概念線性規(guī)劃一般可寫作

10、min(or max) f=s.t. 線性規(guī)劃問題還可以用矩陣表示 min f= s.t Ax b, x0其中f被稱作目標(biāo)函數(shù)，目標(biāo)函數(shù)下的等式或不等式被稱作約束條件， A=,b= 一組滿足約束條件的變量 的值稱為一組可行解。 可行解的集合稱為可行解域，或可行解空間。 線性規(guī)劃問題也就是在可行解域上尋找使目標(biāo)函數(shù)取得極小（或極大）值的可行解，稱之為最優(yōu)解。 針對標(biāo)準(zhǔn)形式的線性規(guī)劃問題，其解的理論分析已經(jīng)很完備，在此基礎(chǔ)上也提出了很好的算 單純形方法是線性規(guī)劃問題的最為基礎(chǔ)、也法單純形方法及其相應(yīng)的變化形式（兩階段4.2 線性規(guī)劃模型的求解 法，對偶單純形法等）. 是最核心的算法。它是一個迭代算

11、法，先從一個特殊的可行解（極點）出發(fā)，通過判別條件去判斷該可行解是否為最優(yōu)解（或問題無界），若不商丘職業(yè)技術(shù)學(xué)院生產(chǎn)計劃問題線性規(guī)劃模型商丘職業(yè)技術(shù)學(xué)院 2x1 + x2 8 s.t . x1 3 x2 4 x1，x2 0 max f= 5x1 +2x2 求最大利潤三種材料量的限制生產(chǎn)量非負(fù)線性規(guī)劃模型商丘職業(yè)技術(shù)學(xué)院運輸問題線性規(guī)劃模型商丘職業(yè)技術(shù)學(xué)院解：假設(shè)費用與運輸量和距離成正比。 設(shè)A1,A2調(diào)運到三個糧站的大米分別為x1，x2， x3， x4， x5， x6噸。題設(shè)量可總到下表：線性規(guī)劃模型商丘職業(yè)技術(shù)學(xué)院結(jié)合存量限制和需量限制得數(shù)學(xué)模型：線性規(guī)劃模型商丘職業(yè)技術(shù)學(xué)院程序編寫mode

12、l:optmin=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23 ;st1x11+x12+x134 ;st2x21+x22+x232 ;st4x12+x224 ;st5x13+x235 ;end運行結(jié)果 Global optimal solution found. Objective value: 160.0000 Total solver iterations: 5 Variable Value Reduced Cost X11 2.000000 0.000000 X12 0.000000 28.00000 X13 2.000000 0.000000 X21

13、 0.000000 2.000000 X22 4.000000 0.000000 X23 3.000000 0.000000 Row Slack or Surplus Dual Price 1 160.0000 -1.000000 2 0.000000 16.00000 3 1.000000 0.000000 4 0.000000 -28.00000 5 0.000000 -12.00000 6 0.000000 -24.00000模型標(biāo)準(zhǔn)化 程序編寫MODEL:TITLE 調(diào)運大米的運輸問題程序; !定義集合段; SETS: HANG/1.5/:B;!定義矩陣的行; LIE/1.11/:C,

14、X;!定義矩陣的列以及變量; XISHU(HANG,LIE):A;!定義約束的系數(shù)矩陣; ENDSETS !定義數(shù)據(jù)段; DATA: A= 1 1 1 0 0 0 1 0 0 0 0!系數(shù)矩陣賦值; 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 -1 0 0 0 1 0 0 1 0 0 0 0 -1 0 0 0 1 0 0 1 0 0 0 0 -1; C= 12 24 8 30 12 0 24 0 0 0 0 0;!目標(biāo)函數(shù)的系數(shù); B= 4 8 2 4 5;!約束的右端項; ENDDATA !標(biāo)準(zhǔn)形式的目標(biāo)函數(shù)的矩陣形式; OBJMIN=SUM(LIE:C*X)

15、; FOR(HANG(I):YUESHU SUM(LIE(J):A(I,J)*X(J)=B(I);END程序編寫 推薦模型MODEL:TITLE 調(diào)運大米的運輸問題程序3;!定義集合段;SETS:LIANGKU/1.2/:A;!定義糧庫的集合;LIANGZHAN/1.3/:B;!定義糧站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定義運量和距離;ENDSETSDATA:!糧庫到糧站的距離;C= 12 24 8 30 12 24;!糧庫的限量;A=4 8 ;!糧站的限量;B=2 4 5;ENDDATAOBJMIN=SUM(YULIANG:C*X);!糧庫上限的約束;F

16、OR(LIANGKU(I):LK SUM(LIANGZHAN(J):X(I,J)B(J);END 程序的調(diào)試1.直接點擊運行，如果出錯會彈出錯誤提示，根據(jù)提示做相應(yīng)的修改；2.可以用“！”把約束變成說明語句，而把這條語句屏蔽掉，縮小尋找出錯的范圍；3.可以邊寫程序邊運行，保證每行書寫都是正確的程序； m個產(chǎn)地A1,Am聯(lián)合供應(yīng)n個銷地B1,Bn,各產(chǎn)地至各銷地單位運價(單位:元/噸)為cij，問如何調(diào)運使總運費最少?一般運輸問題總運價產(chǎn)量限制需量限制運量非負(fù)線性規(guī)劃模型假設(shè)產(chǎn)銷平衡: 在很多實際問題中,解題思想和運輸問題同出一轍,也就是說我們可以用運輸模型解決其他問題.線性規(guī)劃模型2010年塔

17、里木大學(xué)數(shù)學(xué)建模競賽C題甲、乙兩處分別有70噸和55噸物資要外運，A、B和C三點各需要物資34噸、40噸和50噸。運送時，物資可以直接運達(dá)目的地，也可以經(jīng)某點轉(zhuǎn)運。乙010100甲乙甲發(fā)點收點距離乙12151410甲BA發(fā)點收點距離C12001280CBA發(fā)點收點距離ABC14111014甲A B C 乙A B C甲乙首先確定各發(fā)點到各收點的最短距離；這樣就把網(wǎng)絡(luò)流問題化為了運輸問題。model:SETS: CITIES /jia,yi,A,B,C/: L; !屬性L(i)表示城市甲到城市i的最短路線的路長; ROADS(CITIES, CITIES)/ !派生集合ROADS表示的是網(wǎng)絡(luò)中的道

18、路（弧）; jia,yi jia,A jia,B jia,C yi,jia yi ,A yi ,B yi ,C !由于并非所有城市間都有道路直接連接，所以將弧具體列出; A,jia A,yi A,B A,C B,jia B,yi B,A B,C C,jia C,yi C,A C,B/: d; !屬性d( i, j) 是城市i到j(luò)的直接距離（已知）;ENDSETSDATA: d = 10 10 14 12 10 15 12 0 !改乙到C為10; 10 15 14 11 14 12 10 4 12 0 8 12 ; L= 0, , , , ; !先求L(jia)，后改為L(yi);ENDDATA

19、 FOR( CITIES( i)|i#ne#index(jia): !這行中index(jia)可以直接寫成1; L( i) = MIN( ROADS( j, i): L( j) + D( j, i); ); !這就是前面寫出的最短路關(guān)系式;end 設(shè)有n件工作B1, B2, Bn,分派給n人A1, A2, An去做,每人只做一件工作且每件工作只派一個人去做,設(shè)Ai完成Bj的工時為cij,問應(yīng)如何分派才能完成全部工作的總工時最少.每件工作只派1人每個人只派做1件變量xi只取0和1,故建立的模型也稱0-1規(guī)劃.分派問題線性規(guī)劃模型選址問題線性規(guī)劃模型 現(xiàn)要做100套鋼架,用長為2.9m、2.1m

20、和1.5m的元鋼各一根,已知原料長7.4m,問如何下料,使用的原材料最省?分析:下料方式：最省：1.所用剛架根數(shù)最少；2.余料最少下料問題線性規(guī)劃模型原料截成所需長度的根數(shù)下料方法所需根長2.9m211100002.1m021032101.5m10130234剩余料頭0.10.30.901.10.20.81.4線性規(guī)劃模型不同方法截得每種根長的總數(shù)至少100例3,4中的此例的變量xi只取正整數(shù),故建立的模型也稱整數(shù)規(guī)劃.0-1規(guī)劃是整數(shù)規(guī)劃的特殊情形.線性規(guī)劃模型model:Title 鋼管下料; Min=0.1*x1 + 0.3*x2 + 0.9*x3 + 0*x4 +1.1* x5 +0.

21、2* x6 + 0.8*x7 +1.4*x8; 2*x1 +x2 +x3 + x4 100; 2*x2 + 3*x3+ 3*x5 + 2*x6+x7 100; x1+ x3 +3*x4+ 2*x6 +3*x7+ 4*x8100;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);end 某公司生產(chǎn)某產(chǎn)品,最大生產(chǎn)能力為100單位,每單位存儲費2元,預(yù)定的銷售量與單位成本如下:月份單位成本(元) 銷售量1234 70 60 72 70 80 120 76 60求一生產(chǎn)計劃,使 1)滿足需求; 2)不超過生產(chǎn)能力;3)成本(生產(chǎn)成本與存儲

22、費之和)最低.階段生產(chǎn)問題線性規(guī)劃模型 解:假定1月初無庫存,4月底買完,當(dāng)月生產(chǎn)的不庫存,庫存量無限制.第j+1個月的庫存量第j+1個月的庫存費共3個月的庫存費到本月總生產(chǎn)量大于等于銷售量4個月總生產(chǎn)量等于總銷售量4個月總生產(chǎn)成本線性規(guī)劃模型model:title 階段生產(chǎn);Sets: yuefen/1.4/:c,x,e,d; !設(shè)置集合;endsetsDATA:c= 70 72 80 76; d = 6000 7000 12000 6000;e=2 2 2 2;a=10000; ENDDATA min=sum(yuefen:c*x)+sum(yuefen(j)|j#lt#4: sum(yu

23、efen(i)|i#le#j: x-d)*e(j+1);for(yuefen(j)|j#lt#4:sum(yuefen(i)|i#le#j: x)sum(yuefen(i)|i#le#j: d);sum(yuefen: x)=sum(yuefen:d);for(yuefen:xa);end線性規(guī)劃模型月份單位成本(元) 銷售量1234 70 60 72 70 80 120 76 60線性規(guī)劃模型76827676-80-7472-747270生產(chǎn)月100100100100產(chǎn)量6041207060銷量4321321需求月費用cij線性規(guī)劃模型本題3個模型為整數(shù)規(guī)劃模型.線性規(guī)劃模型 線性模型1桶牛

24、奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶 時間480小時 至多加工100公斤A1 制訂生產(chǎn)計劃，使每天獲利最大 35元可買到1桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計劃？ 每天：加工奶制品的生產(chǎn)計劃模型分析與假設(shè) 比例性 可加性 連續(xù)性 xi對目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比 xi對約束條件的“貢獻(xiàn)”與xi取值成正比 xi對目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無關(guān) xi對約束條件的“貢獻(xiàn)”與xj取值無關(guān) xi取值連續(xù) A1,A2每公斤的獲利是與各自產(chǎn)量無關(guān)的

25、常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時間是與相互產(chǎn)量無關(guān)的常數(shù)加工A1,A2的牛奶桶數(shù)是實數(shù) 線性規(guī)劃模型 線性模型建立x1桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)A2 獲利 243x1 獲利 164 x2 原料供應(yīng) 勞動時間 加工能力 決策變量 目標(biāo)函數(shù) 每天獲利約束條件非負(fù)約束 線性規(guī)劃模型(LP)模型求解 圖解法 x1x20ABCDl1l2l3l4l5約束條件目標(biāo)函數(shù) Z=0Z=2400Z=3600z=c (常數(shù)) 等值線c在B(20,30)點得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域為直線段

26、圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊形的某個頂點取得。 線性模型求解Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 N

27、O. ITERATIONS= 220桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤3360元。 結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料無剩余時間無剩余加工能力剩余40max 72x1+

28、64x2st2）x1+x2503）12x1+8x24804）3x1100end三種資源“資源” 剩余為零的約束為緊約束（有效約束） 結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最優(yōu)解下“

29、資源”增加1單位時“效益”的增量 原料增加1單位, 利潤增長48 時間增加1單位, 利潤增長2 加工能力增長不影響利潤影子價格 35元可買到1桶牛奶，要買嗎？35 =0;則lb=0,ub用代替求解線性規(guī)劃問題 編寫Matlab程序如下：c=2;3;1;a=-1,-4,-2;-3,-2,-0;b=-8;-6;x,y=linprog(c,a,b,zeros(3,1)例5.1某家具公司制造書桌、餐桌和椅子，所用的資源有三種：木料、木工和漆工。生產(chǎn)數(shù)據(jù)如下表所示：若要求桌子的生產(chǎn)量不超過5件，如何安排三種產(chǎn)品的生產(chǎn)可使利潤最大？每個書桌每個餐桌每個椅子現(xiàn)有資源總數(shù)木料8單位6單位1單位48單位漆工4單

30、位2單位1.5單位20單位木工2單位1.5單位0.5單位8單位成品單價60單位30單位20單位max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs=48;4*desks+2*tables+1.5*chairs=20;2*desks+1.5*tables+.5*chairs=8;tables=5;連續(xù)投資10萬元A：從第1年 到第4年每年初要投資，次年末回收本利1.15B：第3年初投資，到第5年末回收1.25，最大投資4萬元C：第2年初投資，到第5年末回收1.40，最大投資3萬元D：每年初投資，每年末回收1.11。求：5年末總資本最大。

31、練習(xí)1:連續(xù)投資練習(xí)2某服務(wù)部門一周中每天需要不同數(shù)目的雇員，周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人，現(xiàn)規(guī)定應(yīng)聘者需連續(xù)工作5天，試確定聘用方案。練習(xí)3某班準(zhǔn)備從5名游泳員中選擇人組成接力隊，藏家學(xué)校的4100m混合泳接力比賽，5名隊員4種泳姿的百米平均成績?nèi)绫恚瑔柸绾芜x拔隊員。隊員甲乙丙丁戊蝶泳10685721181101074仰泳115610611421142111蛙泳1271064109610961238自由泳586535945721024 線性模型題目1 生產(chǎn)計劃問題某工廠計劃安排生產(chǎn)，兩種產(chǎn)品，已知每種單位產(chǎn)品的利潤，生產(chǎn)單位產(chǎn)品所需設(shè)備臺時及A,

32、B兩種原材料的消耗，現(xiàn)有原材料和設(shè)備臺時的定額如表所示，問：）怎么安排生產(chǎn)使得工廠獲利最大？）產(chǎn)品的單位利潤降低到1.8萬元，要不要改變生產(chǎn)計劃，如果降低到1萬元呢？）產(chǎn)品的單位利潤增大到5萬元，要不要改變生產(chǎn)計劃？）如果產(chǎn)品，的單位利潤同時降低了1萬元，要不要改變生產(chǎn)計劃？ 產(chǎn)品產(chǎn)品最大資源量設(shè)備128臺時原材料A4016kg原材料B0412kg單位產(chǎn)品利潤23 線性模型建立 線性模型求解程序編寫model:title 生產(chǎn)計劃問題;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END 線性模型求解運行結(jié)果 Model Title: 生產(chǎn)計劃問

33、題 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 對問題1，安排是生產(chǎn)產(chǎn)品4單位，產(chǎn)品2單位，最大盈利為14萬元 。 線性模型敏感性理論1目標(biāo)函數(shù)的系數(shù)變化的敏感性分析如果目標(biāo)函數(shù)的系數(shù)發(fā)生變化，將會影響目標(biāo)函數(shù) f 斜率的變化，但是只要f 的斜率小于等于-1/2（也

34、就是直線l夾在l1與l2之間時），最優(yōu)解都在(4,2)上取到，最優(yōu)解不變，從而生產(chǎn)計劃不會變. 線性模型敏感性分析1要使用敏感性分析必須要在這里選擇Prices & Ranges然后保存退出路徑：LINGOOptionsGeneral Solver(通用求解程序)選項卡 線性模型敏感性分析1要調(diào)出敏感性分析的結(jié)果，必須先求解后再在程序窗口下點擊LINGORange， 線性模型敏感性分析1Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable

35、 Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 當(dāng)前變量系數(shù)允許增加量允許減少量對問題2，產(chǎn)品的單位利潤降低到1.8萬元，在（1.5

36、，）之間，所以不改變生產(chǎn)計劃。如果降低到1萬元，不在（1.5，）內(nèi)，要改變生產(chǎn)計劃。在程序中將目標(biāo)函數(shù)的系數(shù)“2”改為“1”，可得新的計劃為安排是生產(chǎn)產(chǎn)品2單位，產(chǎn)品3單位，最大盈利為11萬元.對問題3，要改變生產(chǎn)計劃，更改程序得新計劃為生產(chǎn)產(chǎn)品2單位，產(chǎn)品3單位，最大盈利為19萬元.對問題4，因為兩個系數(shù)同時改變了，所以只有更改程序的數(shù)據(jù)，重新運行得：不改變生產(chǎn)計劃，但是最大利潤降低到8萬元. 線性模型敏感性理論2 線性模型影子價格理論把y1,y2,y3作為三種原料的定價，定價的目標(biāo)是在比生產(chǎn)產(chǎn)品獲得更多利潤的前提下的最小利潤. 在最優(yōu)情況下，y的值就是資源的影子價格，影子價格有意義是有范圍

37、的。影子價格經(jīng)濟(jì)含義是：在資源得到最優(yōu)配置，使總效益最大時，該資源投入量每增加一個單位所帶來總收益的增加量 線性模型綜合討論Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowab

38、le Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 運行結(jié)果 Model Title: 生產(chǎn)計劃問題 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.0

39、00000 0.1250000 TIME 4.000000 0.000000 線性模型題目21桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶 時間480小時 至多加工100公斤A1 制訂生產(chǎn)計劃，使每天獲利最大 35元可買到1桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計劃？ 每天：加工奶制品的生產(chǎn)計劃 線性模型建立x1桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)A2 獲利 243x1 獲利 164 x2 原料供應(yīng) 勞動時間 加工能力 決策變量 目標(biāo)函數(shù) 每天獲利約束條件非

40、負(fù)約束 線性規(guī)劃模型(LP) 線性模型求解Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 220桶牛奶生產(chǎn)A

41、1, 30桶生產(chǎn)A2，利潤3360元。 線性模型影子價格 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 35元可買到1桶牛奶，要買嗎？35 48, 應(yīng)該買！ 聘用臨時工人付出的工資最多每小時幾元？ 2元！ 線性模型敏感性分析RANG

42、ES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.0000

43、00 53.333332 80.000000 4 100.000000 INFINITY 40.000000 A1獲利增加到 30元/千克，應(yīng)否改變生產(chǎn)計劃？ 不變！ 35元可買到1桶牛奶，每天最多買多少？最多買10桶！2.整數(shù)規(guī)劃 定義規(guī)劃中的變量（部分或全部）限制為整數(shù)時，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃 1o 變量全限制為整數(shù)時，稱純（完全）整數(shù)規(guī)劃。2o 變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。3o 變量只能取0或1時，稱之為0-1整數(shù)規(guī)劃。（i）分枝

44、定界法可求純或混合整數(shù)線性規(guī)劃。（ii）割平面法可求純或混合整數(shù)線性規(guī)劃。（iii）隱枚舉法求解“0-1”整數(shù)規(guī)劃： 過濾隱枚舉法； 分枝隱枚舉法。（iv）匈牙利法解決指派問題（“0-1”規(guī)劃特殊情形）。（v）蒙特卡洛法求解各種類型規(guī)劃(隨機(jī)取樣法) 特殊的整數(shù)規(guī)劃指派問題（又稱分配問題Assignment Problem） 擬分配 人去干 項工作，每人干且僅干一項工作，若分配第 人去干第 項工作，需花費 單位時間，問應(yīng)如何分配工作才能使工人花費的總時間最少？求解下列指派問題，已知指派矩陣為 編寫Matlab程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 5；8 4 2

45、 3 5;9 10 6 9 10;c=c(:);a=zeros(10,25);for i=1:5 a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1;endb=ones(10,1);x,y=linprog(c,a,b,zeros(25,1),ones(25,1) 整數(shù)規(guī)劃的計算機(jī)解法整數(shù)規(guī)劃問題的求解可以使用Lingo,Lindo等專用軟件 .例5.1某家具公司制造書桌、餐桌和椅子，所用的資源有三種：木料、木工和漆工。生產(chǎn)數(shù)據(jù)如下表所示：若要求桌子的生產(chǎn)量不超過5件，如何安排三種產(chǎn)品的生產(chǎn)可使利潤最大？每個書桌每個餐桌每個椅子現(xiàn)有資源總數(shù)木料8單位6單位1單位48單位漆

46、工4單位2單位1.5單位20單位木工2單位1.5單位0.5單位8單位成品單價60單位30單位20單位max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs=48;4*desks+2*tables+1.5*chairs=20;2*desks+1.5*tables+.5*chairs=8;tables總銷量和總產(chǎn)量總銷量.形式，我們總可以通過引入假想的銷地或產(chǎn)地，將不平衡的運輸問題轉(zhuǎn)化為平衡的運輸問題. 從而，我們的重點就是解決平衡運輸問題的求解. 顯然，運輸問題是一個標(biāo)準(zhǔn)的線性規(guī)劃問題，因而當(dāng)然可以運用單純形方法求解. 但由于平衡的運輸問

47、題的特殊性質(zhì)，它還可以用其它的一些特殊方法求解，其中最常用的就是表上作業(yè)法，該方法將單純形法與平衡的運輸問題的特殊性質(zhì)結(jié)合起來，很方便地實行了運輸問題的求解. 關(guān)于運輸問題及其解法的進(jìn)一步介紹可參考相關(guān)文獻(xiàn). 第三節(jié) 整數(shù)規(guī)劃在工程設(shè)計和企業(yè)管理中，常會遇到要求決策變量取離散的非負(fù)整數(shù)值的線性規(guī)劃問題。例如，最優(yōu)調(diào)度的車輛數(shù)，設(shè)置的銷售網(wǎng)點數(shù)，指派工作的人數(shù)等。這類問題在形式上與線性規(guī)劃類似，只是比線性規(guī)劃增加了某些約束條件，來限制全部或部分決策變量必須取離散的非負(fù)整數(shù)值。我們稱之為整數(shù)線性規(guī)劃問題，簡稱為整數(shù)規(guī)劃問題。整數(shù)規(guī)劃是近三十年來發(fā)展起來的、規(guī)劃論的一個重要的理論分支。根據(jù)對決策變量

48、的要求不同，分為四種類型：純整數(shù)規(guī)劃：所有決策變量均要求為離散的非負(fù)整數(shù)?；旌险麛?shù)規(guī)劃：部分決策變量要求為離散的非負(fù)整數(shù)。純01整數(shù)規(guī)劃：所有決策變量均要求為0或1?；旌?1整數(shù)規(guī)劃：部分決策變量要求為0或1。4.1 引例生產(chǎn)組織計劃問題與選址問題（生產(chǎn)組織計劃問題）某工廠在一個計劃期內(nèi)擬生產(chǎn)甲、乙兩種大型設(shè)備。除了A、B兩種部件需要外部供應(yīng)且供應(yīng)受到嚴(yán)格限制之外，該廠有充分的能力來加工制造這兩種設(shè)備所需的其余零件，并且所需原材料和能源也可滿足供應(yīng)。每種設(shè)備所用部件數(shù)量和部件的供應(yīng)限額以及設(shè)備的利潤由表3.2.1給出。問該廠在本計劃期內(nèi)如何安排甲、乙設(shè)備的生產(chǎn)數(shù)量，才能獲取最大利潤？設(shè)備 部件

49、AB利潤（百萬）甲6A15乙4320設(shè)備的最大供應(yīng)量2510設(shè)x1，x2分別為該計劃期內(nèi)甲、乙設(shè)備的生產(chǎn)數(shù)量，Z為生產(chǎn)這兩種設(shè)備可獲得的總利潤。依題意，給問題的數(shù)學(xué)模型為： max Z = 15x1 20 x2，s.t.6x1 4x2 25 x1 3x2 10 xi 0, 1, 2, 這是一個純整數(shù)規(guī)劃問題。（選址問題）某商業(yè)連鎖集團(tuán)擬在n個連鎖店所在城市中建立m個配貨中心，每個城市最多建立一個配貨中心。若在第i個城市建立配貨中心，其配貨能力為Di，單位時間的固定成本為ai，i = 1，m，第j個連鎖店的需求量為bj，j = 1，n。從第i個配貨中心到第j個連鎖店的單位運輸成本為cij。應(yīng)如何

50、選擇配貨中心位置和安排運輸計劃，才能得到經(jīng)濟(jì)上花費最少的方案。設(shè)在單位時間內(nèi)，從配貨中心i運往連鎖店j的物資數(shù)量為xij，Z為單位時間內(nèi)的總費用。引入布爾變量則上述問題可歸結(jié)為如下的數(shù)學(xué)模型：這是一個混合01規(guī)劃問題。4.7 最優(yōu)化軟件MATLAB由美國MathWorks公司開發(fā)研制，采用MATLAB語言編寫,擅長數(shù)值計算. 可用于求解線性規(guī)劃、無約束非線性規(guī)劃、約束非線性規(guī)劃、二次規(guī)劃、線性與非線性約束最小二乘問題、純整與混整規(guī)劃、0-1規(guī)劃及遺傳算法等.專業(yè)的優(yōu)化軟件對優(yōu)化問題的求解通常更有效,目前比較流行的專業(yè)優(yōu)化軟件有Lingo,GAMS,Tomlab等LINGOLingo是美國芝加哥

51、大學(xué)的Linus Schrage教授于1980年前后開發(fā)而得.早期版本沒有全局優(yōu)化功能.Lingo8.0版本增加了全局優(yōu)化功能.Liongo9.0全局優(yōu)化方面又做了很大的改進(jìn)，使得Liongo成為最優(yōu)秀的一種專業(yè)軟件.Lingo的官方網(wǎng)站為 . 可用于求解所有的常見優(yōu)化模型.圖的模型一個時間安排問題圖論的起源七橋問題人、狼、羊、菜渡河問題圖論的起源：七橋問題 a c b d a c b d 圖論的起源：七橋問題graph一般用大寫字母G,H表示無向圖。一種表示工具圖頂點邊 d c a b 三要素：頂點集V；邊集E；關(guān)聯(lián)函數(shù)G=(V,E,)如 (e1)=a,b，e2e3e1e4e5無向圖 e與頂

52、點u, v相關(guān)聯(lián) u與v相鄰 兩邊相鄰 重邊 c a b d 一種表示工具圖你能給出一些可用無向圖描述的實際例子嗎？想無向圖 任何兩個以上的人組成的人群中，至少有兩個人，他們的朋友數(shù)一樣多。 在一次象棋比賽中，若每名選手與其余選手都比賽過，人數(shù)是n，求總盤數(shù)。 設(shè)S=（x1，,x2，xn）是平面上的點集，其中任意兩點間的距離至少是1，證明：距離正好是1的點對數(shù)最多為3n。 在n個運動隊間安排了一項競賽，已賽n+1局，試證：存在一個隊，它至少參加過3局比賽。 一種表示工具圖 一些特殊的圖一種表示工具圖) 既沒有環(huán)也沒有重邊的圖，稱為簡單圖 ) 任意兩頂點都相鄰的簡單圖,稱為完全圖. 記為Kv 一

53、種表示工具圖) 若 ， ，且X 中任意兩頂點不 相鄰，Y 中任意兩頂點不相鄰，則稱為二部圖或 偶圖；若X中每一頂點皆與Y 中一切頂點相鄰,稱為完全二部圖或完全偶圖,記為 (m=|X|,n=|Y|)二部圖你能給出一些可用二部圖描述的實際例子嗎？有向圖：V1V2V3V5V4你能給出一個可用有向圖描述的實際例子嗎？一種表示工具圖想加權(quán)圖這些數(shù)字可以代表距離，費用，可靠性或其他的相關(guān)參數(shù)。12345869157103一種表示工具圖返 回一種表示工具圖返 回定義 若圖 的每一條邊e 都賦以一個實數(shù)w(e)，稱w(e)為邊e的權(quán)，G 連同邊上的權(quán)稱為賦權(quán)圖. 定義 設(shè) 和 是兩個圖. 1) 若 ,稱 是

54、的一個子圖,記 2) 若 ， ，則稱 是 的生成子圖.路徑與連通返 回定義 1) 無向圖G的一條通路是指一個有限非空序列 ，它的項交替地為頂點和邊，使得對 ， 的端點是 和 ,稱W是從 到 的一條通路，整數(shù)k稱為W的長. 頂點 和 分別稱為W的起點和終點 . 2) 若通路W的邊互不相同但頂點可重復(fù)，則稱W為跡或道路. 3) 若通路W的頂點和邊均互不相同，則稱W為路徑記為路徑與連通 定義 1) 起點與終點重合的通路稱為閉通路. 2) 起點與終點重合的的路徑稱為圈，長為k的圈稱為k階圈，記為Ck. 3) 若在圖G中存在(u,v)路徑，則稱頂點u和v在圖G中連通. 4) 若在圖G中頂點u和v是連通的

55、，則頂點u和v之之間的距離d(u,v)是指圖G中最短(u,v)路徑的長；若沒有路徑連接u和v，則定義為無窮大. 5) 圖G中任意兩點皆連通的圖稱為連通圖 一個時間安排問題 學(xué)校要為一年級的研究生開設(shè)六門基礎(chǔ)數(shù)學(xué)課：數(shù)理統(tǒng)計(S)，數(shù)值分析(N)，圖論(G)，矩陣論(M)，隨機(jī)過程(R)和數(shù)理方程(P)。按培養(yǎng)計劃，注冊的學(xué)生必須選修其中的一門以上，你作為教務(wù)管理人員，要設(shè)法安排一個課表，使每個學(xué)生所選的課程，在時間上不會發(fā)生沖突。一個時間安排問題SNGRPMSNGRPM用盡可能少的時段數(shù)安排這6門課的時間表，使沒有同學(xué)發(fā)生沖突。一個時間安排問題返 回122233人狼羊菜渡河問題擺渡人Ferry

56、man狼Wolf羊Sheep菜Vegatable南岸狀態(tài)：C44+ C43 + C42 + C41 + C40=24=16種，其中WS,SV,WSV，從而FV,FW,F為不允許狀態(tài)10種允許狀態(tài)：FWSVFWSFWCVFSVFSOVSWWVFWSVFWSFWVFSVFSOVSWWV1.渡河方案對應(yīng)于圖中從頂點“FWSV”到頂點“O”的鏈路？2.尋求圖中從頂點“FWSV”到頂點“O”的最短路徑，這樣的路徑有幾條？求出最優(yōu)的渡河方案。人狼羊菜渡河問題FWSVFWSFWVFSVFSOVSWWV想FWSVFWSFWVFSVFSOVGWWVFWSVFWSFWVFSVFSOVSWWV人狼羊菜渡河問題返 回圖的矩陣表示方法可達(dá)性矩陣關(guān)聯(lián)矩陣邊矩陣鄰接順序表返 回鄰接矩陣v1v2v5v6v7v4v3abjkcghidfe鄰接矩陣 無向圖的鄰