《《數(shù)學建?！稰PT課件》由會員分享，可在線閱讀，更多相關《《數(shù)學建?！稰PT課件（40頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù) 學 模 型Mathematical Model（ 7） 優(yōu) 化 模 型 人們在解決實際問題時往往會提出若干方案，通過各方面的信息論證，從中提取最佳方案。我們關心的是如何從多個方案中科學合理地提取出最佳方案。優(yōu)化問題無所不在，它包含兩個方面的內(nèi)容： （1）建立數(shù)學模型。模型中的數(shù)學關系式反映了最優(yōu)化問題所要達到的目標和各種約束條件。 （2）求解。數(shù)學模型建好以后，選擇合理的最優(yōu)化方法進行求解。 優(yōu)化問題包含有多個分支，如線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、多目標規(guī)劃等。 按變量的多少可分為單變量和多變量優(yōu)化問題 優(yōu) 化 模 型一、單變量優(yōu)化問題 只有一個變量的最小(大)化問題，即一維搜

2、索問題。該問題在某些情況下可以直接用于求解實際問題，但大多數(shù)情況下它是作為多變量最優(yōu)化方法的基礎在應用，因為進行多變量最優(yōu)化要用到一維搜索法。 該問題的數(shù)學模型為： 其中，x、x 1和x2為標量，f(x)為函數(shù)，返回標量。21 )(min xxx xfx 優(yōu) 化 模 型 該問題的搜索過程為： 其中xk為本次迭代的值，d為搜索方向，為搜索方向上的步長參數(shù)。所以一維搜索就是要利用本次迭代的信息來構(gòu)造下次迭代的條件。 求解單變量最優(yōu)化問題的方法有很多種，根據(jù)目標函數(shù)是否需要求導，可以分為兩類，即直接法和間接法。直接法不需要對目標函數(shù)進行求導，而間接法則需要用到目標函數(shù)的導數(shù)。dxx kk 1 優(yōu) 化

3、 模 型1、直接法 常用的一維直接法主要有消去法和近似法兩種： （1）消去法 該法利用單峰函數(shù)具有的消去性質(zhì)進行反復迭代，逐漸消去不包含極小點的區(qū)間，縮小搜索區(qū)間，直到搜索區(qū)間縮小到給定允許精度為止。一種典型的消去法為黃金分割法(Golden Section Search）。黃金分割法的基本思想是在單峰區(qū)間內(nèi)適當插入兩點，將區(qū)間分為三段，然后通過比較這兩點函數(shù)值的大小來確定是刪去最左段還是最右段，或同時刪去左右兩段保留中間段。重復該過程使區(qū)間無限縮小。插入點的位置放在區(qū)間的黃金分割點及其對稱點上，所以該法稱為黃金分割法。該法的優(yōu)點是算法簡單，效率較高，穩(wěn)定性好。 優(yōu) 化 模 型 （2）多項式近

4、似法 該法用于目標函數(shù)比較復雜的情況。此時尋找一個與它近似的函數(shù)代替目標函數(shù)，并用近似函數(shù)的極小點作為原函數(shù)極小點的近似。常用的近似函數(shù)為二次和三次多項式。 二次內(nèi)插涉及到形如下式的二次函數(shù)數(shù)據(jù)擬合問題：其中步長極值為：cbam q 2)( ab2 優(yōu) 化 模 型 然后只要利用三個梯度或函數(shù)方程組就可以確定系數(shù)a和b，從而可以確定*。得到該值以后，進行搜索區(qū)間的收縮。在縮短的新區(qū)間中，重新安排三點求出下一次的近似極小點*，如此迭代下去，直到滿足終止準則為止。其迭代公式為： 其中)()()( )()()(21 312231123 3122311231 xfxfxf xfxfxfxk 22 jii

5、j xx jiij xx 優(yōu) 化 模 型2、間接法 間接法需要計算目標函數(shù)的導數(shù)，優(yōu)點是計算速度很快。常見的間接法包括牛頓切線法、對分法、割線法和三次插值多項式近似法等。用得較多的是三次插值法。 三次插值的基本思想與二次插值的一致，是用四個已知點構(gòu)造一個三次多項式P3(x)，用它逼近函數(shù)f(x)，以P3(x)的極小點作為f(x)的近似極小點。一般講，三次插值法比二次插值法的收斂速度要快些，但每次迭代需要計算兩個導數(shù)值。 優(yōu) 化 模 型 三次插值法的迭代公式為 其中 如函數(shù)的導數(shù)容易求得，一般首先考慮使用三次插值法，因為它具有較高效率。對于只需要計算函數(shù)值的方法中，二次插值法是一個很好的方法，它

6、的收斂速度較快，尤其在極小點所在區(qū)間較小時尤其如此。黃金分割法則是一種十分穩(wěn)定的方法，并且計算簡單。212 1221221 2)()( )()( xfxf xfxxxxk 21 21211 )()(3)()( xx xfxfxfxf 2/121212 )()( xfxf 優(yōu) 化 模 型3、單變量優(yōu)化的Matlab實現(xiàn) fminbnd 返回固定區(qū)間內(nèi)單變量函數(shù)的最小值 x = fminbnd(fun,x1,x2) 返回區(qū)間x1，x2上fun參數(shù)描述的標量函數(shù)的最小值x x = fminbnd(fun,x1,x2,options) 用options參數(shù)指定的優(yōu)化參數(shù)進行最小化 x = fminbn

7、d(fun,x1,x2,options,P1,P2,.) 提供另外參數(shù)P 1,P2等,傳輸給目標函數(shù)fun。如果沒有設置options選項，則令options= 優(yōu) 化 模 型注(1) Fun ： 需要最小化的目標函數(shù)。fun函數(shù)需要輸入自變量x，返回x處的目標函數(shù)值f。如 x = fminbnd(sin,0,5) 同樣，fun參數(shù)可以是一個包含函數(shù)名的字符串。對應的函數(shù)可以是M文件、內(nèi)部函數(shù)或MEX文件。 上述問題最小值情況可以圖形化說明 x= 0:pi/100:5; y = sin(x); plot(x,y) 優(yōu) 化 模 型注(2) Options： 優(yōu)化參數(shù)選項。可以用optimset函

8、數(shù)設置或改變這些參數(shù)的值。options參數(shù)有以下幾個選項： Display 顯示的水平。 選擇off，不顯示輸出；選擇iter，顯示每一步迭代過程的輸出；選擇final，顯示最終結(jié)果。 MaxFunEvals 函數(shù)評價的最大允許次數(shù)。 MaxIter 最大允許迭代次數(shù)。 TolX x處的終止容限。 優(yōu) 化 模 型例：對邊長為3m的正方形鐵板，在四個角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？ 優(yōu) 化 模 型二、多變量優(yōu)化模型1、線性規(guī)劃(Linear Programming)模型 （1） 線性規(guī)劃模型的一般形式是： 0,., ),(. ),(. ),(. .max(m

9、in)21 2211 22222121 11212111 2211n mnmnmm nn nn nnxxx bxaxaxa bxaxaxa bxaxaxa xcxcxcz 優(yōu) 化 模 型 （2）線性規(guī)劃模型的壓縮形式是： njx mibxa xczj inj jij nj jj,.,2,1,0 ,.,2,1,),(max(min)1 1 優(yōu) 化 模 型 （3）線性規(guī)劃模型的矩陣形式是：其中 0X )b , (AX CXmax(min) z),.,(C 21 nccc nj xxx.X 21 mjjjj aaa.A 21 mbbb.b 21 mnmm nnn aaa aaa aaaAAA . .

10、),.,(A 21 22221 1121121 優(yōu) 化 模 型 （4）線性規(guī)劃問題的標準形式是： 或 矩陣形式為： 0,max 21 2211 22222121 11212111 2211 n mnmnmm nn nn nnxxx bxaxaxa bxaxaxa bxaxaxa xcxcxcz njx mibxa xczjnj ijij nj jj,.,2,1,0 ,.,2,1,max1 1 0maxX bAX CXz 優(yōu) 化 模 型 （5）線性規(guī)劃模型的一般解法 圖解法 單純形法 對偶單純形法 表上作業(yè)法 動態(tài)規(guī)劃法 等等 優(yōu) 化 模 型 （6）解法的Matlab實現(xiàn) x = linprog

11、(c,A,b) 求解問題 min c*x，約束條件為A*x = b x = linprog(c,A,b,Aeq,beq) 求解上面的問題，增加等式約束，即Aeq*x = beq。若沒有不等式存在，則令A=、b=。 x = linprog(c,A,b,Aeq,beq,lb,ub) 定義設計變量x的下界lb和上界ub，使得x始終在該范圍內(nèi)。若沒有等式約束，令Aeq=、beq=。 x = linprog(f,A,b,Aeq,beq,lb,ub,x0) 設置初值為x0。該選項只適用于中型問題，缺省時大型算法將忽略初值。 優(yōu) 化 模 型 x=linprog(f,A,b,Aeq,beq,lb,ub,x0,

12、options) 用options指定的優(yōu)化參數(shù)進行最小化。 x,fval = linprog(.) 返回解x處的目標函數(shù)值fval。 x,lambda,exitflag = linprog(.) 返回exitflag值，描述函數(shù)計算的退出條件。 x,lambda,exitflag,output = linprog(.) 返回包含優(yōu)化信息的輸出變量output。 x,fval,exitflag,output,lambda = linprog(.) 將解x處的拉格朗日乘子返回到lambda參數(shù)中。 優(yōu) 化 模 型例子： 某廠生產(chǎn)甲乙兩種產(chǎn)品，制成一噸產(chǎn)品甲需用資源A 3噸，資源B 4m3；制成一

13、噸產(chǎn)品乙需用資源A 2噸，資源B 6m3，資源C 7個單位。若一噸產(chǎn)品甲和乙的經(jīng)濟價值分別為7萬元和5萬元，三種資源限制量分別為90噸、200m3和210個單位，試決定應生產(chǎn)這兩種產(chǎn)品各多少噸才能使創(chuàng)造的總經(jīng)濟價值最高？ 令生產(chǎn)產(chǎn)品甲的數(shù)量為x1，生產(chǎn)產(chǎn)品乙的數(shù)量為x2。由題意可以建立下面的模型： 該模型中要求目標函數(shù)最大化，需要按照Matlab的要求進行轉(zhuǎn)換，即目標函數(shù)為優(yōu) 化 模 型 0,0 2107 20064 9023 57max 21 221 21 21xx xxx xx xxz 21 57max xxz 優(yōu) 化 模 型 首先輸入下列系數(shù)： f = -7;-5; A = 3 2；4

14、6；0 7; b = 90; 200; 210; lb = zeros(2,1); 然后調(diào)用linprog函數(shù)： x,fval,exitflag,output,lambda = linprog(f,A,b,lb) 優(yōu) 化 模 型Optimization terminated successfully.x = 14.0000 24.0000fval = -218.0000exitflag = 1output = iterations: 5cgiterations: 0algorithm: lipsol lambda =ineqlin: 3x1 doubleeqlin: 0 x1 doubleup

15、per: 2x1 doublelower: 2x1 double 優(yōu) 化 模 型 由上可知，生產(chǎn)甲種產(chǎn)品14噸、乙種產(chǎn)品24噸可使創(chuàng)建的總經(jīng)濟價值最高。 最高經(jīng)濟價值為218萬元。 exitflag=1表示過程正常收斂于解x處。練習1練習2練習3 優(yōu) 化 模 型2、整數(shù)規(guī)劃(Integer Programming)模型 一般來說，所謂整數(shù)規(guī)劃即整數(shù)線性規(guī)劃，也就是要求全部或部分變量取值為整數(shù)這一特殊條件。模型為 且 為 整 數(shù)0,X )b , (AX CXmax(min) z 優(yōu) 化 模 型3、非線性規(guī)劃模型 所謂非線性規(guī)劃也就是在目標函數(shù)或約束條件中含有自變量的非線性函數(shù)。 求解這類問題的方

16、法一般有兩類:直接搜索法(Search method)和梯度法(Gradient method)。 直接搜索法適用于目標函數(shù)高度非線性，沒有導數(shù)或?qū)?shù)很難計算的情況，由于實際工程中很多問題都是非線性的，直接搜索法不失為一種有效的解決辦法。常用的有Hooke-Jeeves搜索法、Pavell共軛方向法等，其缺點是收斂速度慢。 優(yōu) 化 模 型 在函數(shù)的導數(shù)可求的情況下，梯度法是一種更優(yōu)的方法，該法利用函數(shù)的梯度(一階導數(shù))和Hessian矩陣(二階導數(shù))構(gòu)造算法，可以獲得更快的收斂速度。函數(shù)f(x)的負梯度方向 f(x)即反映了函數(shù)的最大下降方向。當搜索方向取為負梯度方向時稱為最速下降法。常見的梯

17、度法有最速下降法、Newton法、Marquart法、共軛梯度法和擬牛頓法（Quasi-Newton method）等。 在所有這些方法中用得最多的是擬牛頓法，這些方法在每次迭代過程中建立曲率信息，構(gòu)成下式得二次模型問題 優(yōu) 化 模 型 其中，Hessian矩陣H為一正定對稱矩陣，C為常數(shù)向量，b為常數(shù)。對x求偏導數(shù)可以獲得問題的最優(yōu)解解x*可寫作： bXCHXX21 TTXmin 0CHx)f(x * CHx 1* 優(yōu) 化 模 型 解法的Matlab實現(xiàn) x = fminunc(fun,x0) 給定初值x0，求fun函數(shù)的局部極小點x。x0可以是標量、向量或矩陣。 x = fminunc(f

18、un,x0,options) 用options參數(shù)中指定的優(yōu)化參數(shù)進行最小化。 x = fminunc(fun,x0,options,P1,P2,.) 將問題參數(shù)p1、p2等直接輸給目標函數(shù)fun，將options參數(shù)設置為空矩陣，作為options參數(shù)的缺省值。 x,fval = fminunc(.) 將解x處目標函數(shù)的值返回到fval參數(shù)中。 優(yōu) 化 模 型 x,fval,exitflag = fminunc(.) 返回exitflag值，描述函數(shù)的輸出條件。 x,fval,exitflag,output = fminunc(.) 返回包含優(yōu)化信息的結(jié)構(gòu)輸出。 x,fval,exitfla

19、g,output,grad = fminunc(.) 將解x處fun函數(shù)的梯度值返回到grad參數(shù)中。 x,fval,exitflag,output,grad,hessian = fminunc(.) 將解x處目標函數(shù)的Hessian矩陣信息返回到hessian參數(shù)中。 優(yōu) 化 模 型三、特殊優(yōu)化算法1、模擬退火算法(Simulated Annealing,簡稱SA算法)2、遺傳算法（Genetic Algorithm,簡稱GA算法） 優(yōu) 化 模 型模擬退火算法 模擬退火算法(Simulated Annealing,簡稱SA算法)是模擬加熱熔化的金屬的退火過程，來尋找全局最優(yōu)解的有效方法之一。

20、 模擬退火的基本思想和步驟如下： 設Ss1,s2,sn為所有可能的狀態(tài)所構(gòu)成的集合， f：SR為非負代價函數(shù)，即優(yōu)化問題抽象如下：尋找s* S，使得f(s*)min f(s i) 任意si S 優(yōu) 化 模 型（1）給定一較高初始溫度T，隨機產(chǎn)生初始狀態(tài)S（2）按一定方式，對當前狀態(tài)作隨機擾動，產(chǎn)生一個新的狀態(tài)S SSsign().其中為給定的步長， 為1,1的隨機數(shù) 計算f(S)f(S)（3）若0，則令SS，轉(zhuǎn)第(5)步（4）若0，則以概率exp(/T)接受S，即SS 優(yōu) 化 模 型 具體操作：產(chǎn)生一個在0，1上服從均勻分布的隨機數(shù)x，若xexp(/T)，則SS 否則S保持不變(5)按一定方式

21、降溫，使TTi1， Ti1 Ti， 如： Ti1Ti， 習慣上取 (0.8，0.9999)(6)檢查退火是否結(jié)束 是轉(zhuǎn)向第(7)步 否轉(zhuǎn)向第(2)步 優(yōu) 化 模 型(7)以當前Si作為最優(yōu)解輸出注：1、結(jié)束標志：溫度是否小于某一閥值(循環(huán)次數(shù)) f的值變化是否明顯 2、初始溫度的高低：下降是否充分慢對結(jié)果有影響 Sin(x)在x4.7124處取得極小 優(yōu) 化 模 型練習1 投資問題 某單位有一批資金用于四個工程項目的投資，用于各工程項目時所得到得凈收益（投入資金的百分比）如下表所示 ，由于某種原因，決定用于項目A的投資不大于其它各項投資之和；而用于項目B和C的投資要大于項目D的投資。試確定該單

22、位收益最大的投資分配方案。 優(yōu) 化 模 型練習2 工件加工任務分配問題 某車間有兩臺機床甲和乙，可用于加工三種工件。假定這兩臺機床的可用臺時數(shù)分別為700和800，三種工件的數(shù)量分別為300、500和400，且已知用三種不同機床加工單位數(shù)量的不同工件所需的臺時數(shù)和加工費用（如表所示），問怎樣分配機床的加工任務，才能既滿足加工工件的要求，又使總加工費用最低？ 優(yōu) 化 模 型練習3 裁料問題 在某建筑工程施工中需要制作10000套鋼筋，每套鋼筋由2.9m、2.1m和1.5m三種不同長度的鋼筋各一根組成，它們的直徑和材質(zhì)相同。目前在市場上采購到的同類鋼筋的長度每根均為7.4m，問應購進多少根7.4m長的鋼筋才能滿足工程的需要？