數(shù)學(xué)建模-最優(yōu)化模型

1、最優(yōu)化模型,一、最優(yōu)化方法概述,二、無約束最優(yōu)化問題,三、無約束最優(yōu)化問題的MATLAB 求解,四、有約束最優(yōu)化問題,最優(yōu)化方法概述,1、最優(yōu)化理論和方法是近二十多年來發(fā)展十分迅速的一個數(shù)學(xué)分支。 2、在數(shù)學(xué)上，最優(yōu)化是一種求極值的方法。 3、最優(yōu)化已經(jīng)廣泛的滲透到工程、經(jīng)濟(jì)、電子技術(shù)等領(lǐng)域。,在實際生活當(dāng)中，人們做任何事情，不管是分析問題，還是進(jìn)行決策，都要用一種標(biāo)準(zhǔn)衡量一下是否達(dá)到了最優(yōu)。 （比如基金人投資） 在各種科學(xué)問題、工程問題、生產(chǎn)管理、社會經(jīng)濟(jì)問題中，人們總是希望在有限的資源條件下，用盡可能小的代價，獲得最大的收獲。（比如保險）,數(shù)學(xué)家對最優(yōu)化問題的研究已經(jīng)有很多年的歷史。 以前

2、解決最優(yōu)化問題的數(shù)學(xué)方法只限于古典求導(dǎo)方法和變分法（求無約束極值問題），拉格朗日（Lagrange）乘數(shù)法解決等式約束下的條件極值問題。 計算機(jī)技術(shù)的出現(xiàn)，使得數(shù)學(xué)家研究出了許多最優(yōu)化方法和算法用以解決以前難以解決的問題。,最優(yōu)化：在一定的條件下，尋求使得目標(biāo)最大（最?。┑牟呗?約一半以上的問題與最優(yōu)化問題有關(guān)。如： 飛行管理問題（95A） 最優(yōu)捕魚策略（96A） 節(jié)水洗衣機(jī)（96B） 零件的參數(shù)設(shè)計(97A) 投資收益和風(fēng)險(98A) 鋼管訂購和運輸(2000B) 電力市場的堵塞管理(2004B) ,幾個概念,最優(yōu)化是從所有可能方案中選擇最合理的一種以達(dá)到最優(yōu)目標(biāo)的學(xué)科。 最優(yōu)方案是達(dá)到最優(yōu)

3、目標(biāo)的方案。 最優(yōu)化方法是搜尋最優(yōu)方案的方法。 最優(yōu)化理論就是最優(yōu)化方法的理論。,經(jīng)典極值問題,包括： 無約束極值問題 約束條件下的極值問題,1、無約束極值問題的數(shù)學(xué)模型,2、約束條件下極值問題的數(shù)學(xué)模型,其中，極大值問題可以轉(zhuǎn)化為極小值問題來進(jìn)行求解。如求：,可以轉(zhuǎn)化為：,1、無約束極值問題的求解,例1：求函數(shù)y=2x3+3x2-12x+14在區(qū)間-3,4上的最大值與最小值。 解：令f(x)=y=2x3+3x2-12x+14 f(x)=6x2+6x-12=6(x+2)(x-1) 解方程f(x)=0，得到x1= -2，x2=1，又 由于f(-3)=23，f(-2)=34，f(1)=7，f(4)

4、=142， 綜上得， 函數(shù)f(x)在x=4取得在-3,4上得最大值f(4)=142，在x=1處取得在-3,4上取得最小值f(1)=7,用MATLAB解無約束優(yōu)化問題,其中等式（3）、（4）、（5）的右邊可選用（1）或（2）的等式右邊. 函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解.,常用格式如下： （1）x= fminbnd (fun,x1,x2) （2）x= fminbnd (fun,x1,x2 ，options) （3）x，fval= fminbnd（） （4）x，fval，exitflag= fminbnd（） （5）x，fva

5、l，exitflag，output= fminbnd（）,MATLAB(wliti1),主程序為wliti1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作圖語句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin (x); xmax,ymax=fminbnd (f1, 0,8),例2 有邊長為3m的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？,解,先編寫M文件fun0.m如下: function f=fun0(x) f=-(3-2*x).2*x;,主程序為wliti2.m: x,

6、fval=fminbnd(fun0,0,1.5); xmax=x fmax=-fval,運算結(jié)果為: xmax = 0.5000,fmax =2.0000.即剪掉的正方形的邊長為0.5m時水槽的容積最大,最大容積為2m3.,MATLAB(wliti2),命令格式為: （1）x= fminunc（fun,X0 ）；或x=fminsearch（fun,X0 ） （2）x= fminunc（fun,X0 ，options）； 或x=fminsearch（fun,X0 ，options） （3）x，fval= fminunc（.）； 或x，fval= fminsearch（.） （4）x，fval，e

7、xitflag= fminunc（.）； 或x，fval，exitflag= fminsearch （5）x，fval，exitflag，output= fminunc（.）； 或x，fval，exitflag，output= fminsearch（.）,2.多元函數(shù)無約束優(yōu)化問題,標(biāo)準(zhǔn)型為：min,例 用fminsearch函數(shù)求解,輸入命令: f=100*(x(2)-x(1)2)2+(1-x(1)2; x,fval,exitflag,output=fminsearch(f,-1.2 2),運行結(jié)果: x =1.0000 1.0000 fval =1.9151e-010 exitflag =

8、 1 output= iterations: 108 funcCount: 202 algorthm: Nelder-Mead simplex direct search ,建立數(shù)學(xué)模型時要盡可能簡單，而且要能完整地描述所研究的系統(tǒng)，具體建立怎樣的數(shù)學(xué)模型需要豐富的經(jīng)驗和熟練的技巧。即使在建立了問題的數(shù)學(xué)模型之后，通常也必須對模型進(jìn)行必要的數(shù)學(xué)簡化以便于分析、計算。,一般的模型簡化工作包括以下幾類： （1）將離散變量轉(zhuǎn)化為連續(xù)變量。 （2）將非線性函數(shù)線性化。 （3）刪除一些非主要約束條件。,最優(yōu)化問題的數(shù)學(xué)模型,建立最優(yōu)化問題數(shù)學(xué)模型的三要素：,（1）決策變量和參數(shù)。 決策變量是由數(shù)學(xué)模型的

9、解確定的未知數(shù)。參數(shù)表示系統(tǒng)的控制變量，有確定性的也有隨機(jī)性的。,（2）約束或限制條件。 由于現(xiàn)實系統(tǒng)的客觀物質(zhì)條件限制，模型必須包括把決策變量限制在它們可行值之內(nèi)的約束條件，而這通常是用約束的數(shù)學(xué)函數(shù)形式來表示的。,（3）目標(biāo)函數(shù)。 這是作為系統(tǒng)決策變量的一個數(shù)學(xué)函數(shù)來衡量系統(tǒng)的效率，即系統(tǒng)追求的目標(biāo)。,解：決定圓柱體表面積大小有兩個決策變量：圓柱體底面半徑r、高h(yuǎn)。 問題的約束條件是所鑄圓柱體重量與球重相等。即,例1.把半徑為1的實心金屬球熔化后，鑄成一個實心圓柱體，問圓柱體取什么尺寸才能使它的表面積最??？,則得數(shù)學(xué)模型： s.t. Subject to.,問題目標(biāo)是圓柱體表面積最小。即

10、min,即 即,此時圓柱體的表面積為,分別對r.h.求偏導(dǎo)數(shù),并令其等于零.有:,利用在高等數(shù)學(xué)中所學(xué)的Lagrange乘子法可求解本問題,例4.多參數(shù)曲線擬合問題 已知兩個物理量x和y之間的依賴關(guān)系為: 其中 和 待定參數(shù),為確定這些參數(shù),對x.y測得m個實驗點: 試將確定參數(shù)的問題表示成最優(yōu)化問題.,解:很顯然對參數(shù) 和 任意給定的一組數(shù)值,就由上式確定了 y關(guān)于x的一個函數(shù)關(guān)系式,在幾何上它對應(yīng)一條曲線,這條曲線不一定通過那m個測量點,而要產(chǎn)生“偏差”. 將測量點沿垂線方向到曲線的距離的 平方和作為這種“偏差”的度量.即 顯然偏差S越小,曲線就擬合得越好,說明參數(shù)值就選擇得越好，從而我們

11、的問題就轉(zhuǎn)化為5維無約束最優(yōu)化問題。即：,有約束最優(yōu)化 最優(yōu)化方法分類 （一）線性最優(yōu)化：目標(biāo)函數(shù)和約束條件都是線性的則稱為線性最優(yōu)化。 非線性最優(yōu)化：目標(biāo)函數(shù)和約束條件如果含有非線性的，則稱為非線性最優(yōu)化。 （二）靜態(tài)最優(yōu)化：如果可能的方案與時間無關(guān)，則是靜態(tài)最優(yōu)化問題。 動態(tài)最優(yōu)化：如果可能的方案與時間有關(guān)，則是動態(tài)最優(yōu)化問題,有約束最優(yōu)化問題的數(shù)學(xué)建模,有約束最優(yōu)化模型一般具有以下形式：,或,其中f(x)為目標(biāo)函數(shù)，省略號表示約束式子，可以是等式約束，也可以是不等式約束。,根據(jù)目標(biāo)函數(shù)，約束條件的特點將最優(yōu)化方法包含的主要內(nèi)容大致如下劃分： 線性規(guī)劃 整數(shù)規(guī)劃 非線性規(guī)劃 動態(tài)規(guī)劃 多目

12、標(biāo)規(guī)劃 對策論,最優(yōu)化方法主要內(nèi)容,最優(yōu)化問題的一般數(shù)學(xué)模型,最優(yōu)化問題的一般算法,整體（全局）最優(yōu)解：若 ，對于一切 ，恒有 則稱 是最優(yōu)化問題的整體最優(yōu)解。 局部最優(yōu)解：若 ，存在某鄰域 ，使得對于一切 ，恒有 則稱 是最優(yōu)化問題的局部最優(yōu)解。其中 嚴(yán)格最優(yōu)解：當(dāng) ，有 則稱 為問題的嚴(yán)格最優(yōu)解。,f(X),局部最優(yōu)解,整體最優(yōu)解,運用最優(yōu)化方法解決最優(yōu)化問題的一般方法步驟如下： 前期分析：分析問題，找出要解決的目標(biāo)，約束條件，并確立最優(yōu)化的目標(biāo)。 定義變量，建立最優(yōu)化問題的數(shù)學(xué)模型，列出目標(biāo)函數(shù)和約束條件。 針對建立的模型，選擇合適的求解方法或數(shù)學(xué)軟件。 編寫程序，利用計算機(jī)求解。 對結(jié)

13、果進(jìn)行分析，討論諸如：結(jié)果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與誤差等。,線性規(guī)劃的模型的一般形式: 目標(biāo)函數(shù) 滿足約束條件 通常稱 為決策變量， 為價值系數(shù)， 為消耗系數(shù), 為資源限制系數(shù)。,線性規(guī)劃,用單純法求解時，常將標(biāo)準(zhǔn)形式化為：,線性規(guī)劃的基本算法單純形法,用MATLAB優(yōu)化工具箱解線性規(guī)劃,命令：x=linprog（c，A，b）,2、模型：min z=cX,命令：x=linprog（c，A，b，Aeq,beq）,注意：若沒有不等式： 存在，則令A(yù)= ，b= .,命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linpr

14、og（c，A，b，Aeq,beq, VLB，VUB, X0）,注意：1 若沒有等式約束: , 則令A(yù)eq= , beq= . 2其中X0表示初始點,4、命令：x,fval=linprog() 返回最優(yōu)解及處的目標(biāo)函數(shù)值fval.,問題 ： 任務(wù)分配問題：某車間有甲、乙兩臺機(jī)床，可用于加工三種工件。假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表。問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費用最低？,引例,解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3

15、，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型：,問題的解答,編寫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; Aeq=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),結(jié)果: x = 0.0000 600.0000 0.0000 400.0000

16、 0.0000 500.0000 fval =1.3800e+004 即在甲機(jī)床上加工600個工件2,在乙機(jī)床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費最小為13800。,例1，某鐵器加工廠要制作100套鋼架，每套要用長為2.9米，2.1米和1.5米的圓鋼各一根。已知原料長為7.4米，問應(yīng)如何下料，可使材料最?。?分析：在長度確定的原料上截取三種不同規(guī)格的圓鋼，可以歸納出8種不同的下料方案：,問題歸納為如何混合使用這8種不同的下料方案，來制造100套鋼架，且要使剩余的料頭總長為最短。,線性規(guī)劃的一些應(yīng)用,設(shè)xj表示用第j種下料方案下料的原料根數(shù)，j=1,28, 數(shù)學(xué)模

17、型 s.t. 這是一個下料問題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織生產(chǎn)， 使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題。 滿足一組約束條件的同時，尋求變量x1至x8的值,使目標(biāo)函數(shù)取得最 小值。,且為整數(shù),數(shù)學(xué)模型 s.t.,且為整數(shù),設(shè)xj表示用第j種下料方案下料的原料根數(shù)，j=1,28,例2:人力資源分配問題 紅旗商場是個中型的百貨商場，它對售貨人員的需求經(jīng)過統(tǒng)計分析如表所示。為了保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應(yīng)該如何安排售貨人員的作息，既滿足了工作需要又使配備的售貨人員的人數(shù)最少？ 表,解：設(shè)x1為星期一開始上班的人數(shù)，x2為星期二開始上班的人

18、數(shù)，x7星期日開始上班的人數(shù)。我們就可得到如下的數(shù)學(xué)模型： min x1+x2+x3+x4+x5+x6+x7 x3+x4+x5+x6+x728 x4+x5+x6+x7+x115 x5+x6+x7+x1+x224 x6+x7+x1+x2+x325 x7+x1+x2+x3+ x419 x1+x2+x3+x4+x531 x2+x3+x4+x5+x628 x1、x2、x3、x4、x5、x6、x70 該問題的最優(yōu)解為：x1=8，x2=0，x3=12，x4=0，x5=11，x6=5，x7=0；目標(biāo)函數(shù)的最小值為36。,例3: 某公司現(xiàn)有68名員工申請?zhí)崆巴诵?。公司必須在此后?年內(nèi)對這些員工分期支付一定數(shù)

19、量的現(xiàn)金，如下表所示。,注意，三種政府債券的票面價值均為1000元，債券到期時按票面價值進(jìn)行支付，利率的計算也以票面的價值為基準(zhǔn)。銀行儲蓄年利率為4%。如何安排投資計劃，使公司以最小的投資額完成對退休員工的現(xiàn)金支付任務(wù)？,為了完成這項現(xiàn)金支付任務(wù)，公司的財務(wù)人員必須現(xiàn)在就為此制定一個投資計劃。投資計劃有政府債券投資和銀行儲蓄兩種方式組成。政府債券投資有三種債券類型可供選擇，如下表所示。,解： 1確定決策變量 設(shè)F為完成投資計劃所需要的總資金額。x1、x2、x3分別表示債券1、2、3的購買量；yi ( i =1,，8)表示第 i年初銀行儲蓄的投資額。 2確定約束條件 這類問題的一個典型特征就是每

20、年現(xiàn)金支付的一般表達(dá)式為： 年初可用資金額 當(dāng)年用于債券和儲蓄的資金額 = 當(dāng)年現(xiàn)金支付 于是有 F 1.15x1 1x2 1.35x3 y1 =430 （第1年）,對于第二年，用于三種債券投資的第一年利息加上第一年儲蓄利息為年初可用資金，第二年用于儲蓄的資金為y2，因此有 0.08875x1 +0.055x2 +0.1175x3 + 1.04y1 y2 = 210（第2年） 同理對于其它年份有 0.08875x1 +0.055x2 +0.1175x3 + 1.04y2 y3 = 222（第3年） 0.08875x1 +0.055x2 +0.1175x3 + 1.04y3 y4= 231（第4

21、年） 0.08875x1 +0.055x2 +0.1175x3 + 1.04y4 y5= 240（第5年） 1.08875x1 +0.055x2 +0.1175x3 + 1.04y5 y6 = 195（第6年） 1.055x2 +0.1175x3 + 1.04y6 y7 = 225（第7年） 1.1175x3 + 1.04y7 y8 = 255（第8年） 因此事實上，y8的值應(yīng)為0，若大于0，那么對應(yīng)的投資計劃必定不是最優(yōu)的。,3.確定目標(biāo)函數(shù) 目標(biāo)就是使?jié)M足要求的投資額最小，即Minz=F 綜合有如下數(shù)學(xué)模型 Minz=F F 1.15x1 1x2 1.35x3 y1 =430 0.0887

22、5x1 +0.055x2 +0.1175x3 + 1.04y1 y2 = 210 0.08875x1 +0.055x2 +0.1175x3 + 1.04y2 y3 = 222 0.08875x1 +0.055x2 +0.1175x3 + 1.04y3 y4= 231 0.08875x1 +0.055x2 +0.1175x3 + 1.04y4 y5= 240 1.08875x1 +0.055x2 +0.1175x3 + 1.04y5 y6 = 195 1.055x2 +0.1175x3 + 1.04y6 y7 = 225 1.1175x3 + 1.04y7 y8 = 255 x1，x2，x30，

23、yi0，i=1，8,該線性規(guī)劃模型的求解結(jié)果為 目標(biāo)函數(shù)最優(yōu)值為：1728.794 變量 最優(yōu)解 檢驗數(shù) F 1728.794 0 x1 144.988 0 x2 187.856 0 x3 228.188 0 y1 636.148 0 y2 501.606 0 y3 349.682 0 y4 182.681 0 y5 0 0.064 y6 0 0.0126 y7 0 0.0213 y8 0 0.671,即得到最佳投資計劃如下表所示。,約束 松弛/剩余變量 對偶價格 1 0 1.000 2 0 0.962 3 0 0.925 4 0 0.889 5 0 0.855 6 0 0.760 7 0 0

24、.719 8 0 0.671 結(jié)果分析： 前4年的儲蓄額均大于0，可見從第6年起債券的利息和債券到期收入才能夠完全滿足當(dāng)前現(xiàn)金支付需要。 每一個約束條件的對偶價格均為負(fù)值，說明減少任何一年的現(xiàn)金支付都將有利于公司總投資額的降低。 對偶價格的逐年降低也說明了，在前面年份減少現(xiàn)金支付將對總投資額的減少更為有效。從而暗示了公司可以適當(dāng)減少前面年份的現(xiàn)金支付量，而在后面年份進(jìn)行補(bǔ)足。,Minz=F F 1.15x1 1x2 1.35x3 y1 =430 0.08875x1 +0.055x2 +0.1175x3 + 1.04y1 y2 = 210 0.08875x1 +0.055x2 +0.1175x3

25、 + 1.04y2 y3 = 222 0.08875x1 +0.055x2 +0.1175x3 + 1.04y3 y4= 231 0.08875x1 +0.055x2 +0.1175x3 + 1.04y4 y5= 240 1.08875x1 +0.055x2 +0.1175x3 + 1.04y5 y6 = 195 1.055x2 +0.1175x3 + 1.04y6 y7 = 225 1.1175x3 + 1.04y7 y8 = 255 x1，x2，x30，yi0，i=1，8,線性規(guī)劃應(yīng)用小結(jié),線性規(guī)劃有著廣泛的應(yīng)用； 線性規(guī)劃的應(yīng)用非常靈活； 所講案例只是真實情況的縮微；,投資的收益和風(fēng)險(

26、98A),二、基本假設(shè)和符號規(guī)定,三、模型的建立與分析,1.總體風(fēng)險用所投資的Si中最大的一個風(fēng)險來衡量,即max qixi|i=1，2,n,4. 模型簡化：,四、模型1的求解,由于a是任意給定的風(fēng)險度，到底怎樣給定沒有一個準(zhǔn)則，不同的投資者有不同的風(fēng)險度。我們從a=0開始，以步長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=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0

27、 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),計算結(jié)果：,五、 結(jié)果分析,3.曲線上的任一點都表示該風(fēng)險水平的最大可能收益和該收益要求的最小風(fēng)險。對于不同風(fēng)險的承受能力，選擇該風(fēng)險水平下的最優(yōu)投資組合。,2.當(dāng)投資越分散時，投資者承擔(dān)的風(fēng)險越小，這與題意一致。即: 冒險的投資者會出現(xiàn)集中投資的情況，保守的投資者

28、則盡量分散投資。,1.風(fēng)險大，收益也大。,4.在a=0.006附近有一個轉(zhuǎn)折點，在這一點左邊，風(fēng)險增加很少時，利潤增長很快。在這一點右邊，風(fēng)險增加很大時，利潤增長很緩慢，所以對于風(fēng)險和收益沒有特殊偏好的投資者來說，應(yīng)該選擇曲線的拐點作為最優(yōu)投資組合，大約是a*=0.6%，Q*=20% ，所對應(yīng)投資方案為: 風(fēng)險度 收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212,無約束最優(yōu)化問題,標(biāo)準(zhǔn)形式：,求解無約束最優(yōu)化問題的基本思想,求解的基本思想 ( 以二元函數(shù)為例 ),5,3,1,連續(xù)可微,多局部極小,唯一極小 (全局極小),

29、搜索過程,最優(yōu)點 (1 1) 初始點 (-1 1),-1,1,4.00,-0.79,0.58,3.39,-0.53,0.23,2.60,-0.18,0.00,1.50,0.09,-0.03,0.98,0.37,0.11,0.47,0.59,0.33,0.20,0.80,0.63,0.05,0.95,0.90,0.003,0.99,0.99,1E-4,0.999,0.998,1E-5,0.9997,0.9998,1E-8,無約束優(yōu)化問題的基本算法,最速下降法是一種最基本的算法，它在最優(yōu)化方法中占有重要地位.最速下降法的優(yōu)點是工作量小，存儲變量較少,初始點要求不高；缺點是收斂慢，最速下降法適用于尋

30、優(yōu)過程的前期迭代或作為間插步驟，當(dāng)接近極值點時，宜選用別種收斂快的算法.,1最速下降法（共軛梯度法）算法步驟：,2牛頓法算法步驟：,如果f是對稱正定矩陣A的二次函數(shù)，則用牛頓法經(jīng)過一次迭代 就可達(dá)到最優(yōu)點,如不是二次函數(shù)，則牛頓法不能一步達(dá)到極值點， 但由于這種函數(shù)在極值點附近和二次函數(shù)很近似,因此牛頓法的收 斂速度還是很快的.,牛頓法的收斂速度雖然較快，但要求Hessian矩陣要可逆，要計算二階導(dǎo)數(shù)和逆矩陣，就加大了計算機(jī)計算量和存儲量.,3擬牛頓法,其他多種直接算法(單純形調(diào)優(yōu)法,H_J法,Powell方向加速法等),Matlab優(yōu)化工具箱簡介,1.MATLAB求解優(yōu)化問題的主要函數(shù),2.

31、 優(yōu)化函數(shù)的輸入變量,使用優(yōu)化函數(shù)或優(yōu)化工具箱中其它優(yōu)化函數(shù)時, 輸入變量見下表:,3. 優(yōu)化函數(shù)的輸出變量下表:,用Matlab解無約束優(yōu)化問題,其中（3）、（4）、（5）的等式右邊可選用（1）或（2）的等式右邊。 函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。,常用格式如下： （1）x= fminbnd (fun,x1,x2) （2）x= fminbnd (fun,x1,x2 ，options) （3）x，fval= fminbnd（.） （4）x，fval，exitflag= fminbnd（.） （5）x，fval，exitf

32、lag，output= fminbnd（.）,主程序為wliti1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作圖語句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin(x); xmax,ymax=fminbnd (f1, 0,8),例2 對邊長為3米的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？,解,先編寫M文件fun0.m如下: function f=fun0(x) f=-(3-2*x).2*x;,主程序為wliti2.m: x,fval=fminbnd(fun0,0,1.

33、5); xmax=x fmax=-fval,運算結(jié)果為: xmax = 0.5000,fmax =2.0000.即剪掉的正方形的邊長為0.5米時水槽的容積最大,最大容積為2立方米.,命令格式為: （1）x= fminunc（fun,X0 ）；或x=fminsearch（fun,X0 ） （2）x= fminunc（fun,X0 ，options）； 或x=fminsearch（fun,X0 ，options） （3）x，fval= fminunc（.）； 或x，fval= fminsearch（.） （4）x，fval，exitflag= fminunc（.）； 或x，fval，exitfla

34、g= fminsearch （5）x，fval，exitflag，output= fminunc（.）； 或x，fval，exitflag，output= fminsearch（.）,2、多元函數(shù)無約束優(yōu)化問題,標(biāo)準(zhǔn)型為：min F(X),3 fminunc為中型優(yōu)化算法的步長一維搜索提供了兩種算法， 由options中參數(shù)LineSearchType控制： LineSearchType=quadcubic(缺省值)，混合的二次和三 次多項式插值； LineSearchType=cubicpoly，三次多項式插,使用fminunc和 fminsearch可能會得到局部最優(yōu)解.,說明:,fmin

35、search是用單純形法尋優(yōu). fminunc的算法見以下 幾點說明：,1 fminunc為無約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法。由options中的參數(shù)LargeScale控制： LargeScale=on(默認(rèn)值),使用大型算法 LargeScale=off,使用中型算法,2 fminunc為中型優(yōu)化算法的搜索方向提供了4種算法，由 options中的參數(shù)HessUpdate控制： HessUpdate=bfgs（默認(rèn)值），擬牛頓法的BFGS公式； HessUpdate=dfp，擬牛頓法的DFP公式； HessUpdate=steepdesc，最速下降法,例3 min f(x)=(4x1

36、2+2x22+4x1x2+2x2+1)*exp(x1),1、編寫M-文件 fun1.m: function f = fun1 (x) f = exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1); 2、輸入M文件wliti3.m如下: x0 = -1, 1; x=fminunc(fun1,x0); y=fun1(x),3、運行結(jié)果: x= 0.5000 -1.0000 y = 1.3029e-10,3.用fminsearch函數(shù)求解,輸入命令: f=100*(x(2)-x(1)2)2+(1-x(1)2; x,fval,exitflag,output=f

37、minsearch(f, -1.2 2),運行結(jié)果: x =1.0000 1.0000 fval =1.9151e-010 exitflag = 1 output = iterations: 108 funcCount: 202 algorithm: Nelder-Mead simplex direct search,4. 用fminunc 函數(shù),(1)建立M-文件fun2.m function f=fun2(x) f=100*(x(2)-x(1)2)2+(1-x(1)2,(2)主程序wliti44.m,Rosenbrock函數(shù)不同算法的計算結(jié)果,可以看出，最速下降法的結(jié)果最差.因為最速下降法

38、特別不適合于從一狹長通道到達(dá)最優(yōu)解的情況.,例5 產(chǎn)銷量的最佳安排 某廠生產(chǎn)一種產(chǎn)品有甲、乙兩個牌號，討論在產(chǎn)銷平衡的情況下如何確定各自的產(chǎn)量，使總利潤最大. 所謂產(chǎn)銷平衡指工廠的產(chǎn)量等于市場上的銷量.,基本假設(shè),1價格與銷量成線性關(guān)系,2成本與產(chǎn)量成負(fù)指數(shù)關(guān)系,模型建立,若根據(jù)大量的統(tǒng)計數(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,則 問題轉(zhuǎn)化為無約束優(yōu)化問題：求甲,乙兩個牌號的產(chǎn)量x1，x2，使 總利潤z最大.,為簡化模型,先忽略成本,并令a12=0,a2

39、1=0,問題轉(zhuǎn)化為求: z1 = ( b1 - a11x1 ) x1 + ( b2 - a22x2 ) x2 的極值. 顯然其解為x1 = b1/2a11 = 50, x2 = b2/2a22 = 70, 我們把它作為原問題的初始值.,總利潤為： z(x1,x2)=(p1-q1)x1+(p2-q2)x2,模型求解,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); y2=(280-0.2*x(1)- 2*x(2)-(100*exp(-0.02*x(2)+30)*x(2);

40、 f=-y1-y2;,2.輸入命令: x0=50,70; x=fminunc(fun,x0), z=fun(x),3.計算結(jié)果: x=23.9025, 62.4977, z=6.4135e+003 即甲的產(chǎn)量為23.9025,乙的產(chǎn)量為62.4977,最大利潤為6413.5.,約束非線性規(guī)劃,定義 如果目標(biāo)函數(shù)或約束條件中至少有一個是非線性函數(shù)時的最優(yōu)化問題就叫做非線性規(guī)劃問題,約束非現(xiàn)性規(guī)劃的基本概念,一般形式: （1） 其中 ， 是定義在 En 上的實值函數(shù)，簡記:,其它情況: 求目標(biāo)函數(shù)的最大值或約束條件為小于等于零的情況，都可通過取其相反數(shù)化為上述一般形式,非線性規(guī)劃的基本解法,SUT

41、M外點法,SUTM內(nèi)點法（障礙罰函數(shù)法）,1、罰函數(shù)法,2、近似規(guī)劃法,罰函數(shù)法,罰函數(shù)法基本思想是通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題，進(jìn)而用無約束最優(yōu)化方法去求解這類方法稱為序列無約束最小化方法簡稱為SUMT法 其一為SUMT外點法，其二為SUMT內(nèi)點法,其中T(X,M)稱為罰函數(shù)，M稱為罰因子，帶M的項稱為罰項，這里的罰函數(shù)只對不滿足約束條件的點實行懲罰：當(dāng) 時，滿足各 ，故罰項=0，不受懲罰當(dāng) 時，必有 的約束條件，故罰項0，要受懲罰,SUTM外點法,罰函數(shù)法的缺點是：每個近似最優(yōu)解Xk往往不是容許解，而只能近似滿足約束，在實際問題中這種結(jié)果可能不能使用；在解一系列無約

42、束問題中，計算量太大，特別是隨著Mk的增大，可能導(dǎo)致錯誤,1、任意給定初始點X0，取M11，給定允許誤差 ，令k=1； 2、求無約束極值問題 的最優(yōu)解，設(shè)為Xk=X(Mk)，即 ； 3、若存在 ，使 ，則取MkM( )令k=k+1返回（2），否則，停止迭代得最優(yōu)解 . 計算時也可將收斂性判別準(zhǔn)則 改為 .,SUTM外點法(罰函數(shù)法)的迭代步驟,SUTM內(nèi)點法（障礙函數(shù)法）,內(nèi)點法的迭代步驟,近似規(guī)劃法的基本思想：將問題(3)中的目標(biāo)函數(shù) 和約束條件 近似為線性函數(shù)，并對變量的取值范圍加以限制，從而得到一個近似線性規(guī)劃問題，再用單純形法求解之，把其符合原始條件的最優(yōu)解作為(3)的解的近似,近似規(guī)

43、劃法,每得到一個近似解后，都從這點出發(fā)，重復(fù)以上步驟,這樣，通過求解一系列線性規(guī)劃問題，產(chǎn)生一個由線性規(guī)劃最優(yōu)解組成的序列，經(jīng)驗表明，這樣的序列往往收斂于非線性規(guī)劃問題的解。,近似規(guī)劃法的算法步驟如下,用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, Aeq,beq ,VLB,VUB,X0); 5.x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0

44、,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,1、寫成標(biāo)準(zhǔn)形式：,2、 輸入命令： H=1 -1; -1 2; c=-2 ;-6;A=1 1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),

45、3、運算結(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維變元向量，G(X)與Ceq(X)均為非線性函數(shù)組成的向量，其它變量的含義與線性規(guī)劃、二次規(guī)劃中相同.用Matlab求解上述問題，基本步驟分三步：,3. 建立主程序.非線性規(guī)劃求解的函數(shù)是fmincon,命令的基本格式如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fminco

46、n(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= fmincon(.),輸出極值點,M文件,迭代的初值,參數(shù)說明,變量上下限,注意： 1 fmincon函數(shù)提供了大型優(yōu)化算法和中型優(yōu)化算法。默認(rèn)時，若在fun函

47、數(shù)中提供了梯度（options參數(shù)的GradObj設(shè)置為on），并且只有上下界存在或只有等式約束，fmincon函數(shù)將選擇大型算法。當(dāng)既有等式約束又有梯度約束時，使用中型算法。 2 fmincon函數(shù)的中型算法使用的是序列二次規(guī)劃法。在每一步迭代中求解二次規(guī)劃子問題，并用BFGS法更新拉格朗日Hessian矩陣。 3 fmincon函數(shù)可能會給出局部最優(yōu)解，這與初值X0的選取有關(guān)。,1、寫成標(biāo)準(zhǔn)形式： s.t.,2x1+3x2 6 s.t x1+4x2 5 x1,x2 0,例2,2、先建立M-文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)

48、*x(1)2+(1/2)*x(2)2,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、運算結(jié)果為： x = 0.7647 1.0588 fval = -2.0294,1先建立M文件 fun4.m,定義目標(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);,x1+x2=0 s.t. 1.5+x1x2 - x1 - x

49、2 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,vub,mycon),3. 運算結(jié)果為： x = -1.2250 1.2250 fval = 1.8951,例4,1先建立M-文件fun.m定義目標(biāo)函數(shù): function f=

50、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,mycon2),4. 運算結(jié)果為: x = 4.0000 3.0000 fval =-11.0000 exitflag = 1 output = iterations: 4 funcCount: 17 steps

51、ize: 1 algorithm: 1x44 char firstorderopt: cgiterations: ,應(yīng)用實例： 供應(yīng)與選址,某公司有6個建筑工地要開工，每個工地的位置（用平面坐標(biāo)系a，b表示，距離單位：千米 ）及水泥日用量d(噸)由下表給出。目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20噸。假設(shè)從料場到工地之間均有直線道路相連。 （1）試制定每天的供應(yīng)計劃，即從A，B兩料場分別向各工地運送多少噸水泥，使總的噸千米數(shù)最小。 （2）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20噸，問應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？,（一）、建立模型,

52、記工地的位置為(ai，bi)，水泥日用量為di，i=1,6;料場位置為(xj，yj)，日儲量為ej，j=1,2；從料場j向工地i的運送量為Xij。,當(dāng)用臨時料場時決策變量為：Xij， 當(dāng)不用臨時料場時決策變量為：Xij，xj，yj。,（二）使用臨時料場的情形,使用兩個臨時料場A(5,1)，B(2,7).求從料場j向工地i的運送量為Xij，在各工地用量必須滿足和各料場運送量不超過日儲量的條件下，使總的噸千米數(shù)最小，這是線性規(guī)劃問題. 線性規(guī)劃模型為：,設(shè)X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22=

53、X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 編寫程序gying1.m,計算結(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.0000 fval = 136.2275,（三）改建兩個新料場的情形,改建兩個新料場，要同時確定料場的位置(xj,yj)和運送量Xij，在同樣條件下使總噸千米數(shù)最小。這是非線性規(guī)劃問題。非線性規(guī)劃模型為：,設(shè) X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X

54、 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ù)。,(2) 取初值為線性規(guī)劃的計算結(jié)果及臨時料場的坐標(biāo): x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7; 編寫主程序gying2.m.,(3) 計算結(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.1867 fval = 105.4626 exitflag = 1,(4) 若修改主程序gying2.m, 取初值為上面的計算結(jié)果: x0= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.38