最新數(shù)學(xué)建模-優(yōu)化問(wèn)題精品課件ppt資料講解

1、數(shù)學(xué)建模-優(yōu)化問(wèn)題整數(shù)規(guī)劃整數(shù)規(guī)劃(IP) 決策變量決策變量(全部或部分全部或部分)為整數(shù)為整數(shù)Integer programming 整數(shù)整數(shù)線性線性規(guī)劃規(guī)劃(ILP)，整數(shù)，整數(shù)非線性非線性規(guī)劃規(guī)劃(INLP) 純整數(shù)規(guī)劃純整數(shù)規(guī)劃(PIP), 混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃(MIP) Pure (mixed) Integer programming 一般整數(shù)規(guī)劃，一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃（整數(shù)）規(guī)劃Zero-one programming離散優(yōu)化離散優(yōu)化discrete optimization或組合優(yōu)化或組合優(yōu)化combinatorial optimization一般優(yōu)化問(wèn)題概述多局

2、部極小298.0f0f298.0f 唯一極小(全局極小)2122212121322)(xxxxxxxxf搜索過(guò)程搜索過(guò)程21221221)1 ()(100)(minxxxxxf最優(yōu)點(diǎn) (1 1)初始點(diǎn) (-1 1)1x2xf-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.330.200.800.630.050.950.90 0.0030.990.991E-40.9990.9981E-50.9997 0.9998 1E-8返回 給定初始點(diǎn)nEX 0，允許誤差0,令 k=0； 計(jì)算kXf； 檢

3、驗(yàn)是否滿足收斂性的判別準(zhǔn)則： kXf， 若滿足，則停止迭代，得點(diǎn)kXX*，否則進(jìn)行； 令kkXfS，從kX出發(fā)，沿kS進(jìn)行一維搜索， 即求k使得： kkkkkSXfSXf0min； 令kkkkSXX1，k=k+1 返回.無(wú)約束優(yōu)化問(wèn)題的基本算法無(wú)約束優(yōu)化問(wèn)題的基本算法 最速下降法是一種最基本的算法，它在最優(yōu)化方法中占有重要地位.最速下降法的優(yōu)點(diǎn)是工作量小，存儲(chǔ)變量較少,初始點(diǎn)要求不高；缺點(diǎn)是收斂慢，最速下降法適用于尋優(yōu)過(guò)程的前期迭代或作為間插步驟，當(dāng)接近極值點(diǎn)時(shí)，宜選用別種收斂快的算法. 1 1最速下降法（共軛梯度法）算法步驟：最速下降法（共軛梯度法）算法步驟：2 2牛頓法算法步驟：牛頓法算法

4、步驟：(1) 選定初始點(diǎn)nEX 0，給定允許誤差0，令 k=0；(2) 求kXf,12kXf,檢驗(yàn)：若kXf,則 停止迭代,kXX*.否則, 轉(zhuǎn)向(3)；(3) 令 kkkXfXfS12（牛頓方向） ； (4) kkkSXX1,1 kk,轉(zhuǎn)回(2). 如果f是對(duì)稱正定矩陣A的二次函數(shù)，則用牛頓法經(jīng)過(guò)一次迭代一次迭代就可達(dá)到最優(yōu)點(diǎn),如不是二次函數(shù)，則牛頓法不能一步達(dá)到極值點(diǎn)，但由于這種函數(shù)在極值點(diǎn)附近和二次函數(shù)很近似,因此牛頓法的收斂速度還是很快的. 牛頓法的收斂速度雖然較快，但要求Hessian矩陣要可逆，要計(jì)算二階導(dǎo)數(shù)和逆矩陣，就加大了計(jì)算機(jī)計(jì)算量和存儲(chǔ)量.MatlabMatlab優(yōu)化工具箱

5、簡(jiǎn)介優(yōu)化工具箱簡(jiǎn)介1.MATLAB1.MATLAB求解優(yōu)化問(wèn)題的主要函數(shù)求解優(yōu)化問(wèn)題的主要函數(shù)類 型模 型基本函數(shù)名一元函數(shù)極小Min F（x）s.t.x1xx2x=fminbnd(F,x1,x2)無(wú)約束極小Min F(X)X=fminunc(F,X0)X=fminsearch(F,X0)線性規(guī)劃Min XcTs.t.AX=bX=linprog(c,A,b)二次規(guī)劃Min 21xTHx+cTxs.t. Ax=bX=quadprog(H,c,A,b)約束極?。ǚ蔷€性規(guī)劃）Min F(X)s.t. G(X)=0X=fmincon(FG,X0)達(dá)到目標(biāo)問(wèn)題Min rs.t. F(x)-wr=goal

6、X=fgoalattain(F,x,goal,w)極小極大問(wèn)題Min max Fi(x)X Fi(x)s.t. G(x)0,則x為解;否則,x不是最終解,它只是迭代制止時(shí)優(yōu)化過(guò)程的值所有優(yōu)化函數(shù)fval解x處的目標(biāo)函數(shù)值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin, fminbndexitflag描述退出條件: exitflag0,表目標(biāo)函數(shù)收斂于解x處 exitflag=0,表已達(dá)到函數(shù)評(píng)價(jià)或迭代的最大次數(shù) exitflag0,表目標(biāo)函數(shù)不收斂output包含優(yōu)化結(jié)果信息的輸出結(jié)構(gòu). Iteration

7、s:迭代次數(shù) Algorithm:所采用的算法 FuncCount:函數(shù)評(píng)價(jià)次數(shù)所有優(yōu)化函數(shù)用用MatlabMatlab解無(wú)約束優(yōu)化問(wèn)題解無(wú)約束優(yōu)化問(wèn)題 1. 一一元元函函數(shù)數(shù)無(wú)無(wú)約約束束優(yōu)優(yōu)化化問(wèn)問(wèn)題題: : min f（x） 21xxx 其中（3）、（4）、（5）的等式右邊可選用（1）或（2）的等式右邊。 函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。常用格式如下：常用格式如下：（1）x= fminbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2) )（2）x= fminbnd (x= fminbnd (

8、fun,xfun,x1 1,x,x2 2 ，options)options)（3）xx，fval= fminbndfval= fminbnd（.）（4）xx，fvalfval，exitflag= fminbndexitflag= fminbnd（.）（5）xx，fvalfval，exitflagexitflag，output= fminbndoutput= fminbnd（.）運(yùn)行結(jié)果： xmin = 3.9270 ymin = -0.0279 xmax = 0.7854 ymax = 0.6448To Matlab(wliti1) 例例 1 1 求 f = 2xexsin在 0 x8 中的最

9、小值與最大值 主程序?yàn)橹鞒绦驗(yàn)閣liti1.m:wliti1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作圖語(yǔ)句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin(x); xmax,ymax=fminbnd (f1, 0,8)例例2 2 對(duì)邊長(zhǎng)為3米的正方形鐵板，在四個(gè)角剪去相等的正方形以制成方形無(wú)蓋水槽，問(wèn)如何剪法使水槽的容積最大？設(shè)剪去的正方形的邊長(zhǎng)為x，則水槽的容積為：xx )23(2建立無(wú)約束優(yōu)化模型為：min y=-xx )23(2， 0 x 0，且a11 a12；同理， p2 = b2 - a21 x1-

10、 a22 x2 ，b2，a21，a22 0，且a22 a21 .2 2成本與產(chǎn)量成負(fù)指數(shù)關(guān)系成本與產(chǎn)量成負(fù)指數(shù)關(guān)系甲的成本隨其產(chǎn)量的增長(zhǎng)而降低,且有一個(gè)漸進(jìn)值,可以假設(shè)為負(fù)指數(shù)關(guān)系,即: 0,11111111crcerqx 同理， 0,22222222crcerqx 模型建立模型建立 若根據(jù)大量的統(tǒng)計(jì)數(shù)據(jù),求出系數(shù)b1=100,a11=1,a12=0.1,b2=280,a21=0.2,a22=2,r1=30,1=0.015,c1=20, r2=100,2=0.02,c2=30,則問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題：求甲,乙兩個(gè)牌號(hào)的產(chǎn)量x1，x2，使總利潤(rùn)z最大. 為簡(jiǎn)化模型,先忽略成本,并令a12=0

11、,a21=0,問(wèn)題轉(zhuǎn)化為求: z1 = ( b1 - a11x1 ) x1 + ( b2 - a22x2 ) x2 的極值. 顯然其解為x1 = b1/2a11 = 50, x2 = b2/2a22 = 70,我們把它作為原問(wèn)題的初始值.總利潤(rùn)為：總利潤(rùn)為： z z( (x x1 1,x,x2 2)=()=(p p1 1-q-q1 1) )x x1 1+(+(p p2 2-q-q2 2) )x x2 2 模型求解模型求解 1.建立M-文件fun.m: function f = fun(x) y1=(100-x(1)- 0.1*x(2)-(30*exp(-0.015*x(1)+20)*x(1);

12、 y2=(280-0.2*x(1)- 2*x(2)-(100*exp(-0.02*x(2)+30)*x(2); f=-y1-y2; 2.輸入命令: x0=50,70; x=fminunc(fun,x0), z=fun(x) 3.計(jì)算結(jié)果: x=23.9025, 62.4977, z=6.4135e+003 即甲的產(chǎn)量為23.9025,乙的產(chǎn)量為62.4977,最大利潤(rùn)為6413.5.To Matlab(wliti5)返回練習(xí)練習(xí)1. 求下列函數(shù)的極小點(diǎn)： 1) 2123222118294xxxxxXf；2) 212122212223xxxxxxXf；3) 224121 xXf. 第1） ，2）

13、題的初始點(diǎn)可任意選取， 第3）題的初始點(diǎn)取為TX1 , 00.（1）線性逼近法）線性逼近法基本思想：基本思想： 將目標(biāo)函數(shù)和約束函數(shù)近似為線性函數(shù)，轉(zhuǎn)將目標(biāo)函數(shù)和約束函數(shù)近似為線性函數(shù)，轉(zhuǎn)化為線性規(guī)劃問(wèn)題求解，重復(fù)這個(gè)過(guò)程?；癁榫€性規(guī)劃問(wèn)題求解，重復(fù)這個(gè)過(guò)程。步驟：步驟：給定控制誤差給定控制誤差0，初始可行點(diǎn)，初始可行點(diǎn)xk,初始步長(zhǎng)初始步長(zhǎng)k0,在在xk線性化得線性規(guī)劃問(wèn)題：線性化得線性規(guī)劃問(wèn)題： min . . 0,1, 0,1, TkkkTikikkTjkjkkkkfxfxxxs txxxxikxxxxjkmxx 非線性規(guī)劃有約束問(wèn)題 求出此線性規(guī)劃問(wèn)題得最優(yōu)解求出此線性規(guī)劃問(wèn)題得最優(yōu)解

14、xk1，檢驗(yàn)，檢驗(yàn)是否為原問(wèn)題的的可行解，若是轉(zhuǎn)是否為原問(wèn)題的的可行解，若是轉(zhuǎn)，否則縮短，否則縮短步長(zhǎng)轉(zhuǎn)步長(zhǎng)轉(zhuǎn)；判斷精度。判斷精度。1,kkxx 若若則取則取最優(yōu)解最優(yōu)解x*=xk+1,停，否則令停，否則令k=k+1轉(zhuǎn)轉(zhuǎn)。 12211221 min . . 0 0fXxxs tgxxxgxx 例例：非線性規(guī)劃有約束問(wèn)題（2）罰函數(shù)法）罰函數(shù)法轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題：轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題： 22min, min 0,ijF x MfxMxMx M為足夠大的正數(shù)。稱為為足夠大的正數(shù)。稱為罰因子罰因子。算法分析：算法分析：設(shè)可行域?yàn)樵O(shè)可行域?yàn)镾，構(gòu)造函數(shù)：，構(gòu)造函數(shù)： 20 , 1iixSuxim

15、xxS 非線性規(guī)劃有約束問(wèn)題 iixux 令令 求無(wú)約束問(wèn)題得最優(yōu)解為求無(wú)約束問(wèn)題得最優(yōu)解為X(M),直觀看出，直觀看出，只有當(dāng)只有當(dāng)X(M) S才可能真正取得極小值，若才可能真正取得極小值，若 ,X MS 就就加大加大罰因子罰因子M，使，使X(M) 向向S逼近，逼近，當(dāng)當(dāng)M時(shí)，點(diǎn)列時(shí)，點(diǎn)列 。外外趨趨于于最最優(yōu)優(yōu)解解從從*XSMXK非線性規(guī)劃有約束問(wèn)題計(jì)算步驟計(jì)算步驟：（第：（第k次迭代）次迭代） 。優(yōu)優(yōu)解解，求求解解無(wú)無(wú)約約束束問(wèn)問(wèn)題題得得最最取取kkXM01 .,*k121轉(zhuǎn)轉(zhuǎn)，否否則則取取則則若若kkkkMMXXxM 12211221 min . . 0 0fXxxs tgxxxgxx

16、 例例： 2111,min,2124 1TXSX MMMM 非線性規(guī)劃有約束問(wèn)題有約束問(wèn)題matlab解法ubxlbbeqxAeqbAxxceqxctosubjuctxf0)(0)()(minx,fval = fmincon(myfun,x0,A,b)x,fval = fmincon(myfun,x0,A,b,Aeq,beq)x,fval = fmincon(myfun,x0,A,b,Aeq,beq,lb,ub)x ,fval= fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,comfun)缺省的用代替myfun與confun是M- 函數(shù)的地址具體如:目標(biāo)函數(shù)：Funct

17、ion f=myfun(x)非線性約束：function c, ceq = confun(x)%Nonlinear inequality constraintsc = c1(x);c2(x);.;%Nonlinear equality constraintsceq = ceq1(x); ceq2(x);.;M-函數(shù)1先建立先建立M文件文件 fun4.m,定義目標(biāo)函數(shù)定義目標(biāo)函數(shù): function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);) 12424()(22122211xxxxxexfx x1+x2=0 s

18、.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例例32再建立再建立M文件文件mycon.m定義非線性約束：定義非線性約束： function g,ceq=mycon(x) g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10; 例4 100 , 50 07 025 . .2min 21222122221121xxxxXgxxXgtsxxXf1先建立先建立M-文件文件fun.m定義目標(biāo)函數(shù)定義目標(biāo)函數(shù): function f=fun(x); f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2.m定義非線性約束：

19、定義非線性約束： function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;應(yīng)用實(shí)例：應(yīng)用實(shí)例： 供應(yīng)與選址供應(yīng)與選址 某公司有6個(gè)建筑工地要開(kāi)工，每個(gè)工地的位置（用平面坐標(biāo)系a，b表示，距離單位：千米 ）及水泥日用量d(噸)由下表給出。目前有兩個(gè)臨時(shí)料場(chǎng)位于A(5,1)，B(2,7)，日儲(chǔ)量各有20噸。假設(shè)從料場(chǎng)到工地之間均有直線道路相連。 （1）試制定每天的供應(yīng)計(jì)劃，即從A，B兩料場(chǎng)分別向各工地運(yùn)送多少噸水泥，使總的噸千米數(shù)最小。 （2）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個(gè)臨時(shí)料場(chǎng)，改建兩個(gè)新的，日儲(chǔ)量各為20噸，問(wèn)應(yīng)建在何處，節(jié)省的噸

20、千米數(shù)有多大？工地位置（a，b）及水泥日用量 d 1 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.25 d 3 5 4 7 6 11 （一）、建立模型（一）、建立模型 記工地的位置為記工地的位置為(ai，bi)，水泥日用量為，水泥日用量為di，i=1,6;料場(chǎng)位置為料場(chǎng)位置為(xj，yj)，日儲(chǔ)量為，日儲(chǔ)量為ej，j=1,2；從料場(chǎng)；從料場(chǎng)j向工地向工地i的運(yùn)送量為的運(yùn)送量為Xij。目標(biāo)函數(shù)為：216122)()(minjiijijijbyaxXf 約束條件為：2 , 1 ,6 , 2 , 1 ,6121jeXi

21、dXjiijijij 當(dāng)用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，當(dāng)不用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，xj，yj。（二）使用臨時(shí)料場(chǎng)的情形（二）使用臨時(shí)料場(chǎng)的情形 使用兩個(gè)臨時(shí)料場(chǎng)A(5,1)，B(2,7).求從料場(chǎng)j向工地i的運(yùn)送量為Xij，在各工地用量必須滿足和各料場(chǎng)運(yùn)送量不超過(guò)日儲(chǔ)量的條件下，使總的噸千米數(shù)最小，這是線性規(guī)劃問(wèn)題. 線性規(guī)劃模型為：2161),(minjiijXjiaaf2 , 1 , 6 , 2 , 1 , s.t.6121jeXidXjiijijij其中 22)()(),(ijijbyaxjiaa，i=1,2,6,j=1,2,為常數(shù)。 設(shè)X11=X1, X21= X 2, X3

22、1= X 3, X41= X 4, X51= X 5, X61= X 6X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 編寫程序gying1.mMATLAB（gying1）計(jì)算結(jié)果為：計(jì)算結(jié)果為：x = 3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval = 136.2275即由料場(chǎng)A、B向6 個(gè)工地運(yùn)料方案為： 1 2 3 4 5 6 料場(chǎng)A 3 5 0 7 0 1 料場(chǎng)B 0 0 4 0 6

23、 10 總的噸千米數(shù)為136.2275。 （三）改建兩個(gè)新料場(chǎng)的情形（三）改建兩個(gè)新料場(chǎng)的情形 改建兩個(gè)新料場(chǎng)，要同時(shí)確定料場(chǎng)的位置(xj,yj)和運(yùn)送量Xij，在同樣條件下使總噸千米數(shù)最小。這是非線性規(guī)劃問(wèn)題。非線性規(guī)劃模型為：216122)()(minjiijijijbyaxXf2 , 1 , 6 , 2 , 1 , . .6121jeXidXtsjiijijij設(shè) X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 x1=X13, y1=X14, x2=X15, y2=X16 （1）先編寫M文件liaoch.m定義目標(biāo)函數(shù)。MATLAB（liaoch）(2) 取初值為線性規(guī)劃的計(jì)算結(jié)果及臨時(shí)料場(chǎng)的坐標(biāo): x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;編寫主程序gying2.m.MATLAB（gying2）(3) 計(jì)算結(jié)果為：x= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7