1優(yōu)化模型.ppt

1、最優(yōu)化理論在建模中的應(yīng)用,如投資的成本最小、利潤(rùn)最大問(wèn)題，郵遞員的投遞路線最短問(wèn)題，貨物的運(yùn)輸調(diào)度問(wèn)題，風(fēng)險(xiǎn)證券投資中的收益最大，風(fēng)險(xiǎn)最小問(wèn)題.,（一）優(yōu)化模型的數(shù)學(xué)描述,一 優(yōu)化模型的一般意義,“受約束于”之意,（二）優(yōu)化模型的分類,1.根據(jù)是否存在約束條件 有約束問(wèn)題和無(wú)約束問(wèn)題。 2.根據(jù)設(shè)計(jì)變量的性質(zhì) 靜態(tài)問(wèn)題和動(dòng)態(tài)問(wèn)題。,3.根據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式的性質(zhì) 線性規(guī)劃，非線性規(guī)劃，二次規(guī)劃，多目標(biāo)規(guī)劃等。,（1）非線性規(guī)劃 目標(biāo)函數(shù)和約束條件中，至少有一個(gè)非線性函數(shù)。,（2）線性規(guī)劃（LP） 目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量 的線性函數(shù)。,（3）二次規(guī)劃問(wèn)題 目標(biāo)函數(shù)為二次函數(shù)

2、，約束條件為線性約束,5. 根據(jù)變量具有確定值還是隨機(jī)值 確定規(guī)劃和隨機(jī)規(guī)劃。,4. 根據(jù)設(shè)計(jì)變量的允許值,整數(shù)規(guī)劃（0-1規(guī)劃）和實(shí)數(shù)規(guī)劃。,（三）建立優(yōu)化模型的一般步驟,(1) 確定目標(biāo)函數(shù)（按照模型所需要解決的問(wèn)題，用數(shù)學(xué)函數(shù)來(lái)描述目標(biāo)） （2） 確定決策變量（目標(biāo)的實(shí)現(xiàn)與那些變量有關(guān)，這里有主要變量和次要變量，在建模的初期可以進(jìn)考慮主要變量對(duì)目標(biāo)的影響，隨后可以逐步增加變量的個(gè)數(shù)） （3） 確定約束條件（這是優(yōu)化模型建模過(guò)程中最重要，也是最難的，在很多情況下，是否能夠得到最優(yōu)解，最優(yōu)解是否合理，都是取決于約束條件的建立） （4） 模型求解（使用數(shù)學(xué)工具或數(shù)學(xué)軟件求解） （5） 結(jié)果分析

3、（分析結(jié)果的合理性、穩(wěn)定性、敏感程度等）,最優(yōu)化理論,最優(yōu)化理論與算法是數(shù)學(xué)的一個(gè)重要分支，它所研究的問(wèn)題是討論在眾多的方案中什么樣的方案最優(yōu)以及怎樣找出最優(yōu)方案，這類問(wèn)題很普遍，比如，工程設(shè)計(jì)中怎樣選擇設(shè)計(jì)參數(shù)，使設(shè)計(jì)方案既滿足設(shè)計(jì)要求又能降低成本；在資源配置中，怎樣分配有限資源使得分配方案既能滿足各方面的基本要求，又能獲得好的經(jīng)濟(jì)效益；生產(chǎn)計(jì)劃安排中，選擇怎樣的計(jì)劃方案才能提高產(chǎn)值和利潤(rùn)；城建規(guī)劃中，怎樣安排工廠、機(jī)關(guān)、學(xué)校、商店、醫(yī)院、住戶和其他單位的合理布局，才能方便群眾，有利于城市各個(gè)行業(yè)的發(fā)展；在人類生活的各個(gè)領(lǐng)域，諸如此類，不勝枚舉。最優(yōu)化這一數(shù)學(xué)分支，正是為這些問(wèn)題的解決，提供

4、理論基礎(chǔ)和求解方法。,20世紀(jì)40年代以來(lái)，由于生產(chǎn)和科學(xué)研究的突飛猛進(jìn)，特別是電子計(jì)算機(jī)日益廣泛應(yīng)用，使最優(yōu)化問(wèn)題的研究不僅成為一種迫切需要，而且有了求解的有力工具，例如lingo和lindo軟件。最優(yōu)化理論迅速發(fā)展成為一個(gè)新的學(xué)科，至今已經(jīng)出現(xiàn)了線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、幾何規(guī)劃、動(dòng)態(tài)規(guī)劃、網(wǎng)絡(luò)流等許多分支，最優(yōu)化理論與方法在實(shí)際應(yīng)用中的作用越來(lái)越大。 下面我們就分成幾塊了解一下數(shù)學(xué)建模中經(jīng)常用到的最優(yōu)化理論的基礎(chǔ)知識(shí) -規(guī)劃論中的線性規(guī)劃、非線性規(guī)劃問(wèn)題。,1.線性規(guī)劃的標(biāo)準(zhǔn)形式：,線性規(guī)劃,問(wèn)題一 ： 任務(wù)分配問(wèn)題：某車間有甲、乙兩臺(tái)機(jī)床，可用于加工三種工件。假定這兩臺(tái)車床的可用

5、臺(tái)時(shí)數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表。問(wèn)怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？,兩個(gè)引例,解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6。可建立以下線性規(guī)劃模型：,解答,問(wèn)題二： 某廠每日8小時(shí)的產(chǎn)量不低于1800件。為了進(jìn)行質(zhì)量控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員。一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時(shí)，正確率98%，計(jì)時(shí)工資4元/小時(shí)；二級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15小時(shí)/件，正確率95%，計(jì)

6、時(shí)工資3元/小時(shí)。檢驗(yàn)員每錯(cuò)檢一次，工廠要損失2元。為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？,解 設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的人數(shù)分別為x1、x2人, 則應(yīng)付檢驗(yàn)員的工資為：,因檢驗(yàn)員錯(cuò)檢而造成的損失為：,故目標(biāo)函數(shù)為：,約束條件為：,線性規(guī)劃模型：,解答,返 回,用MATLAB優(yōu)化工具箱解線性規(guī)劃,命令：x=linprog（c，A，b）,2、模型：min z=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若沒(méi)有不等式： 存在，則令A(yù)= ，b= .,命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，

7、Aeq,beq, VLB，VUB, X0）,注意：1 若沒(méi)有等式約束: , 則令A(yù)eq= , beq= . 2其中X0表示初始點(diǎn),4、命令：x,fval=linprog() 返回最優(yōu)解及處的目標(biāo)函數(shù)值fval.,解 編寫(xiě)M文件xxgh1.m如下： c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=

8、; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh1),解: 編寫(xiě)M文件xxgh2.m如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh2),例3 問(wèn)題一的解答,問(wèn)題,編寫(xiě)M文件xxgh3.m如下: f = 13 9 10 11 12 8; A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3; b = 800; 900; A

9、eq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1; beq=400 600 500; vlb = zeros(6,1); vub=; x,fval = linprog(f,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh3),結(jié)果: x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000 fval =1.3800e+004 即在甲機(jī)床上加工600個(gè)工件2,在乙機(jī)床上加工400個(gè)工件1、500個(gè)工件3，可在滿足條件的情況下使總加工費(fèi)最小為13800。,例2 問(wèn)題二的解答,問(wèn)題,改寫(xiě)為：,編寫(xiě)M文件

10、xxgh4.m如下： c = 40;36; A=-5 -3; b=-45; Aeq=; beq=; vlb = zeros(2,1); vub=9;15; %調(diào)用linprog函數(shù)： x,fval = linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh4),結(jié)果為： x = 9.0000 0.0000 fval =360 即只需聘用9個(gè)一級(jí)檢驗(yàn)員。,注：本問(wèn)題應(yīng)還有一個(gè)約束條件：x1、x2取整數(shù)。故它是一個(gè)整數(shù)線性規(guī)劃問(wèn)題。這里把它當(dāng)成一個(gè)線性規(guī)劃來(lái)解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解。若用線性規(guī)劃解法求得的最優(yōu)解

11、不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門(mén)的方法求解。,返 回,投資的收益和風(fēng)險(xiǎn),二、基本假設(shè)和符號(hào)規(guī)定,三、模型的建立與分析,1.總體風(fēng)險(xiǎn)用所投資的Si中最大的一個(gè)風(fēng)險(xiǎn)來(lái)衡量,即max qixi|i=1，2,n,4. 模型簡(jiǎn)化：,四、模型1的求解,由于a是任意給定的風(fēng)險(xiǎn)度，到底怎樣給定沒(méi)有一個(gè)準(zhǔn)則，不同的投資者有不同的風(fēng)險(xiǎn)度。我們從a=0開(kāi)始，以步長(zhǎng)a=0.001進(jìn)行循環(huán)搜索，編制程序如下：,a=0; while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq

12、=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001; end xlabel(a),ylabel(Q),To Matlab（xxgh5）,計(jì)算結(jié)果：,五、 結(jié)果分析,返 回,4.在a=0.006附近有一個(gè)轉(zhuǎn)折點(diǎn)，在這一點(diǎn)左邊，風(fēng)險(xiǎn)增加很少時(shí)，利潤(rùn)增長(zhǎng) 很快。在這一點(diǎn)右

13、邊，風(fēng)險(xiǎn)增加很大時(shí)，利潤(rùn)增長(zhǎng)很緩慢，所以對(duì)于風(fēng)險(xiǎn)和 收益沒(méi)有特殊偏好的投資者來(lái)說(shuō)，應(yīng)該選擇曲線的拐點(diǎn)作為最優(yōu)投資組合， 大約是a*=0.6%，Q*=20% ，所對(duì)應(yīng)投資方案為: 風(fēng)險(xiǎn)度 收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212,3.曲線上的任一點(diǎn)都表示該風(fēng)險(xiǎn)水平的最大可能收益和該收益要求的最小風(fēng)險(xiǎn)。對(duì)于不同風(fēng)險(xiǎn)的承受能力，選擇該風(fēng)險(xiǎn)水平下的最優(yōu)投資組合。,2.當(dāng)投資越分散時(shí)，投資者承擔(dān)的風(fēng)險(xiǎn)越小，這與題意一致。即: 冒險(xiǎn)的投資者會(huì)出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資。,1.風(fēng)險(xiǎn)大，收益也大。,*非線性規(guī)

14、劃的基本解法,*非線性規(guī)劃的基本概念,非線性規(guī)劃,返回,定義 如果目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線性函數(shù)時(shí)的最優(yōu)化問(wèn)題就叫做非線性規(guī)劃問(wèn)題,非線性規(guī)劃的基本概念,一般形式: （1） 其中 ， 是定義在 En 上的實(shí)值函數(shù)，簡(jiǎn)記:,其它情況: 求目標(biāo)函數(shù)的最大值或約束條件為小于等于零的情況，都可通過(guò)取其相反數(shù)化為上述一般形式,用MATLAB軟件求解,其輸入格式如下: 1.x=quadprog(H,C,A,b); 2.x=quadprog(H,C,A,b,Aeq,beq); 3.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4.x=quadprog(H,C,A,b,

15、 Aeq,beq ,VLB,VUB,X0); 5.x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6.x,fval=quaprog(.); 7.x,fval,exitflag=quaprog(.); 8.x,fval,exitflag,output=quaprog(.);,1、二次規(guī)劃,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20,MATLAB（youh1）,1、寫(xiě)成標(biāo)準(zhǔn)形式：,2、 輸入命令： H=1 -1; -1 2; c=-2 ;-6;A=1

16、1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),3、運(yùn)算結(jié)果為： x =0.6667 1.3333 z = -8.2222,s.t.,1. 首先建立M文件fun.m,定義目標(biāo)函數(shù)F（X）: function f=fun(X); f=F(X);,2、一般非線性規(guī)劃,其中X為n維變?cè)蛄浚珿(X)與Ceq(X)均為非線性函數(shù)組成的向量，其它變量的含義與線性規(guī)劃、二次規(guī)劃中相同.用Matlab求解上述問(wèn)題，基本步驟分三步：,3. 建立主程序.非線性規(guī)劃求解的函數(shù)是fmincon,命令的基本格式

17、如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon) (5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon(.) (7) x,fval,exitflag= fmincon(.) (8)x,fval,exitflag,output= fmin

18、con(.),輸出極值點(diǎn),M文件,迭代的初值,參數(shù)說(shuō)明,變量上下限,注意： 1 fmincon函數(shù)提供了大型優(yōu)化算法和中型優(yōu)化算法。默認(rèn)時(shí)，若在fun函數(shù)中提供了梯度（options參數(shù)的GradObj設(shè)置為on），并且只有上下界存在或只有等式約束，fmincon函數(shù)將選擇大型算法。當(dāng)既有等式約束又有梯度約束時(shí)，使用中型算法。 2 fmincon函數(shù)的中型算法使用的是序列二次規(guī)劃法。在每一步迭代中求解二次規(guī)劃子問(wèn)題，并用BFGS法更新拉格朗日Hessian矩陣。 3 fmincon函數(shù)可能會(huì)給出局部最優(yōu)解，這與初值X0的選取有關(guān)。,1、寫(xiě)成標(biāo)準(zhǔn)形式： s.t.,2x1+3x2 6 s.t x1

19、+4x2 5 x1,x2 0,例2,2、先建立M-文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,MATLAB(youh2),3、再建立主程序youh2.m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB),4、運(yùn)算結(jié)果為： x = 0.7647 1.0588 fval = -2.0294,1先建立M文件 fun4.m,定義目標(biāo)函數(shù): function f=f

20、un4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0,例3,2再建立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;,3主程序youh3.m為: x0=-1;1; A=;b=; Aeq=1 1;beq=0; vlb=;vub=; x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb

21、,vub,mycon),MATLAB(youh3),3. 運(yùn)算結(jié)果為： x = -1.2250 1.2250 fval = 1.8951,例4,1先建立M-文件fun.m定義目標(biāo)函數(shù): function f=fun(x); f=-2*x(1)-x(2);,2再建立M文件mycon2.m定義非線性約束： function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;,3. 主程序fxx.m為: x0=3;2.5; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0,VLB,VUB,my

22、con2),MATLAB(fxx(fun),4. 運(yùn)算結(jié)果為: x = 4.0000 3.0000 fval =-11.0000 exitflag = 1 output = iterations: 4 funcCount: 17 stepsize: 1 algorithm: 1x44 char firstorderopt: cgiterations: ,返回主要內(nèi)容,多目標(biāo)規(guī)劃問(wèn)題及其數(shù)學(xué)模型,例5.1 某企業(yè)計(jì)劃生產(chǎn)甲，乙兩種產(chǎn)品，這些產(chǎn)品分別要在A,B,C,D四種不同設(shè)備上加工。按工藝文件規(guī)定，如表所示。,問(wèn)該企業(yè)應(yīng)如何安排計(jì)劃，使得計(jì)劃期內(nèi)的總利潤(rùn)收入為最大？,解：設(shè)甲、乙產(chǎn)品的產(chǎn)量分別

23、為x1，x2，建立線性規(guī)劃模型：,其最優(yōu)解為x14，x22，z14元,但企業(yè)的經(jīng)營(yíng)目標(biāo)不僅僅是利潤(rùn)，而且要考慮多個(gè)方面，如： 力求使利潤(rùn)指標(biāo)不低于12元； 考慮到市場(chǎng)需求，甲、乙兩種產(chǎn)品的生產(chǎn)量需保持1:1的比例； C和D為貴重設(shè)備，嚴(yán)格禁止超時(shí)使用； 設(shè)備B必要時(shí)可以加班，但加班時(shí)間要控制；設(shè)備A即要求充分利用，又盡可能不加班。,要考慮上述多方面的目標(biāo)，需要借助目標(biāo)規(guī)劃的方法。,線性規(guī)劃模型存在的局限性： 1）要求問(wèn)題的解必須滿足全部約束條件，實(shí)際問(wèn)題中并非所有約束都需要嚴(yán)格滿足。 2）只能處理單目標(biāo)的優(yōu)化問(wèn)題。實(shí)際問(wèn)題中，目標(biāo)和約束可以相互轉(zhuǎn)化。 3）線性規(guī)劃中各個(gè)約束條件都處于同等重要地

24、位，但現(xiàn)實(shí)問(wèn)題中，各目標(biāo)的重要性即有層次上的差別，同一層次中又可以有權(quán)重上的區(qū)分。 4）線性規(guī)劃尋求最優(yōu)解，但很多實(shí)際問(wèn)題中只需找出滿意解就可以。,目標(biāo)規(guī)劃怎樣解決上述線性規(guī)劃模型建模中的局限性？,1. 設(shè)置偏差變量，用來(lái)表明實(shí)際值同目標(biāo)值之間的差異。,偏差變量用下列符號(hào)表示：,d+超出目標(biāo)的偏差，稱正偏差變量 d-未達(dá)到目標(biāo)的偏差，稱負(fù)偏差變量,正負(fù)偏差變量?jī)烧弑赜幸粋€(gè)為0。 當(dāng)實(shí)際值超出目標(biāo)值時(shí)： d+0, d-=0; 當(dāng)實(shí)際值未達(dá)到目標(biāo)值時(shí)： d+=0, d-0; 當(dāng)實(shí)際值同目標(biāo)值恰好一致時(shí)： d+=0, d-=0; 故恒有d+d-=0,2. 統(tǒng)一處理目標(biāo)和約束。,對(duì)有嚴(yán)格限制的資源使用建立系統(tǒng)約束，數(shù)學(xué)形式同線性規(guī)劃中的約束條件。如C和D設(shè)備的使用限制。,對(duì)不嚴(yán)格限制的約束，連同原線性規(guī)劃建模時(shí)的目標(biāo)，均通過(guò)目標(biāo)約束來(lái)表達(dá)。,1）例如要求甲、乙兩種產(chǎn)品保持1:1的比例，系統(tǒng)約束表達(dá)為： x1=x2。由于這個(gè)比例允許有偏差， 當(dāng)x1x2時(shí)，出現(xiàn)正偏差d+，即： x1-d+ =x2或x1x2-d+ =0,正負(fù)偏差不可能同時(shí)出現(xiàn)，故總有： x1x2+d-d+ =0,若希望甲的產(chǎn)量不低于乙的產(chǎn)量，即不希望d-0,用目標(biāo)約束可表為:,若希望甲的產(chǎn)量低于乙的產(chǎn)量，即不希望d0,用目標(biāo)約束可表為:,若希望甲的產(chǎn)量恰好等于乙的產(chǎn)量，即不希望d0,也不希望d-0用目標(biāo)約束可表為:,3）