數(shù)學(xué)實(shí)驗(yàn)課件：最優(yōu)化方法實(shí)驗(yàn)

最優(yōu)化方法實(shí)驗(yàn)

最優(yōu)化是應(yīng)用數(shù)學(xué)的一個(gè)分支，主要指在一定條件限制下，選取某種研究方案使目標(biāo)達(dá)到最優(yōu)的一種方法．最優(yōu)化問(wèn)題在當(dāng)今的軍事、工程、管理等領(lǐng)域有著極其廣泛的應(yīng)用，根據(jù)不同表現(xiàn)特征和標(biāo)準(zhǔn)可分為無(wú)約束和有約束、線性和非線性、單目標(biāo)和多目標(biāo)優(yōu)化問(wèn)題等．建立一個(gè)優(yōu)化問(wèn)題的數(shù)學(xué)模型，應(yīng)明確三個(gè)基本要素：決策變量約束條件

目標(biāo)函數(shù)

一個(gè)向量

滿足約束條件，稱為可行解或可行點(diǎn)，所有可行點(diǎn)的集合稱為可行區(qū)域，達(dá)到目標(biāo)函數(shù)值最值的可行解稱為該優(yōu)化問(wèn)題的最優(yōu)解，相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)目標(biāo)函數(shù)值，簡(jiǎn)稱最優(yōu)值.最值有最大值和最小值兩種．

本章主要介紹利用MATLAB求解線性規(guī)劃、二次規(guī)劃和無(wú)約束規(guī)劃，展現(xiàn)數(shù)學(xué)知識(shí)和方法在現(xiàn)實(shí)中的應(yīng)用．CONTENTS10.1線性規(guī)劃10.2.二次規(guī)劃10.3無(wú)約束優(yōu)化10.3.1一元函數(shù)無(wú)約束優(yōu)化的最優(yōu)解求解10.3.2多元函數(shù)無(wú)約束優(yōu)化的最優(yōu)解求解10.1線性規(guī)劃

線性規(guī)劃（Linearprogramming,簡(jiǎn)稱LP），是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法．研究線性約束條件下線性目標(biāo)函數(shù)的極值問(wèn)題的數(shù)學(xué)理論和方法．MATLAB解決線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式為：其中c、x、b、beq、lb、ub均為列向量；A、Aeq為矩陣，求

z

的最大值就是求

–z

的最小值．

在MATLAB中利用函數(shù)linprog來(lái)解決這類問(wèn)題.函數(shù)linprog的調(diào)用格式如下：

X=linprog(f,A,b)

[X,fval,exitflag,output,lamnda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options)

這里，X是問(wèn)題的解向量，f是由目標(biāo)函數(shù)的系數(shù)構(gòu)成的向量，A是一個(gè)矩陣，b是一個(gè)向量，A，b和變量x={x1,x2,…,xn}一起，表示了線性規(guī)劃中不等式約束條件，A，b是系數(shù)矩陣和右端向量.Aeq和Beq表示了線性規(guī)劃中等式約束條件中的系數(shù)矩陣和右端向量.LB和UB是約束變量的下界和上界向量，X0是給定的變量的初始值，options為控制規(guī)劃過(guò)程的參數(shù)系列.返回值中fval是優(yōu)化結(jié)束后得到的目標(biāo)函數(shù)值.exitflag=0表示優(yōu)化結(jié)果已經(jīng)超過(guò)了函數(shù)的估計(jì)值或者已聲明的最大迭代次數(shù)；exitflag>0表示優(yōu)化過(guò)程中變量收斂于解X，exitflag<0表示不收斂.output有3個(gè)分量，iterations表示優(yōu)化過(guò)程的迭代次數(shù)，cgiterations表示PCG迭代次數(shù)，algorithm表示優(yōu)化所采用的運(yùn)算規(guī)則.lambda有4個(gè)分量，ineqlin是線性不等式約束條件，eqlin是線性等式約束條件，upper是變量的上界約束條件，lower是變量的下界約束條件.它們的返回值分別表示相應(yīng)的約束條件在約束條件在優(yōu)化過(guò)程中是否有效．例10.1求解線性規(guī)劃問(wèn)題：

解MATLAB命令如下：clearf=-[5,4,6];A=[1,-2,1;3,2,4;3,2,0];b=[20,42,30];LB=[0;0;0];[X,fval]=linprog(f,A,b,[],[],LB)運(yùn)行結(jié)果：Optimalsolutionfound.X=015.00003.0000fval=-78可知當(dāng)x1=0，x2=15，x3=3時(shí)，得到最小值-78．例10.2求解線性規(guī)劃問(wèn)題：解先將最大值問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式：MATLAB命令如下：c=[-2,-3,5];A=[-2,5,-1];b=-10;Aeq=[111];beq=7;x0=[000];[x,fval]=linprog(c,A,b,Aeq,beq,x0)運(yùn)行結(jié)果為：Optimalsolutionfound.x=6.42860.57140fval=-14.5714可知，當(dāng)x1=6.4286，x2=0.5714，x3=0時(shí)，得到最大值z(mì)=14.5714．

例10.3某工廠生產(chǎn)A，B兩種產(chǎn)品，所用原料均為甲、乙、丙三種，生產(chǎn)一件產(chǎn)品所需原料和所獲利潤(rùn)以及庫(kù)存原料情況如表10-1所示.

在該廠只有表中所列庫(kù)存原料的情況下，如何安排A，B兩種產(chǎn)品的生產(chǎn)數(shù)量可以獲得最大利潤(rùn)？原料甲（公斤）原料乙（公斤）原料丙（公斤）利潤(rùn)（元）產(chǎn)品A8447000產(chǎn)品B68610000庫(kù)存原料量380300220

表10-1利潤(rùn)以及庫(kù)存原料情況表解設(shè)生產(chǎn)A產(chǎn)品x1件，生產(chǎn)B產(chǎn)品x2件，z為所獲利潤(rùn)，我們將問(wèn)題歸結(jié)為如下的線性規(guī)劃問(wèn)題：

轉(zhuǎn)換成最小值問(wèn)題

接著寫出MATLAB程序如下：clearf=-[7000,10000];A=[8,6;4,8;4,6];b=[380,300,220];[X,fval]=linprog(f,A,b)運(yùn)行結(jié)果為：Optimalsolutionfound.X=40.000010.0000fval=-380000可知生產(chǎn)A產(chǎn)品40件，B產(chǎn)品10件時(shí)可獲得最大利潤(rùn)380000元．10.2二次規(guī)劃類似于線性規(guī)劃，求解二次規(guī)劃之前需要先將其化為標(biāo)準(zhǔn)形式：其中f、x、b、beq、lb、ub均為列向量；A、Aeq為矩陣；H為二次型（對(duì)稱正定矩陣）．在MATLAB中利用函數(shù)quadprog求解，調(diào)用格式如下

[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub)求解約束條件下的二次規(guī)劃例10.4求解二次規(guī)劃：解將二次規(guī)劃寫成標(biāo)準(zhǔn)形式其中MATLAB程序如下：H=[1-1;-12];f=[-2;-6];A=[11;-12;21];b=[2;2;3];[x,fval]=quadprog(H,f,A,b)運(yùn)行后得到Minimumfoundthatsatisfiestheconstraints.Optimizationcompletedbecausetheobjectivefunctionisnon-decreasinginfeasibledirections,towithinthevalueoftheoptimalitytolerance,andconstraintsaresatisfiedtowithinthevalueoftheconstrainttolerance.<stoppingcriteriadetails>x=0.66671.3333fval=-8.2222可得當(dāng)x1=0.6667，x2=1.3333時(shí)，最小值是z=-8.2222．10.3無(wú)約束優(yōu)化10.3.1一元函數(shù)無(wú)約束優(yōu)化的最優(yōu)解求解

一元函數(shù)優(yōu)化一般要給定自變量的取值范圍，其標(biāo)準(zhǔn)形式為：

在MATLAB中利用fminbnd函數(shù)求解，調(diào)用格式如下：

[x,fval]=fminbnd(fun,x1,x2)返回一個(gè)值x，該值是fun中描述的標(biāo)量值函數(shù)在區(qū)間x1<x<x2中的局部最小值；

[x,fval]=fminbnd(fun,x1,x2,options)使用options中指定的優(yōu)化選項(xiàng)求最小值.

在實(shí)際求解過(guò)程中如果需要給出求解的初值，要求能夠從問(wèn)題本身進(jìn)行初步分析后得到最優(yōu)解的大致位置．例10.5求sin(x)函數(shù)在0<x<2π范圍內(nèi)的最小值的點(diǎn)．解>>fun=@sin;>>x1=0;>>x2=2*pi;>>x=fminbnd(fun,x1,x2)x=4.7124此值與正確值

x=3π/2

相同>>3*pi/2ans=4.7124

例10.6對(duì)邊長(zhǎng)為5m的正方形鐵板，在4個(gè)角處減去相等的正方形，以制成方形無(wú)蓋水槽，問(wèn)如何剪才能使水槽的容積最大？

解假設(shè)剪去正方形的邊長(zhǎng)為x，則水槽的容積為

水槽的容積最大的目標(biāo)函數(shù)是

，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式為

首先建立函數(shù)文件：

functionv=myfun1(x)

v=-(5-2*x)^2*x;然后在命令行調(diào)用fminbnd函數(shù)，>>[x,v]=fminbnd('myfun1',0,2.5)x=0.8333v=-9.2593可知，當(dāng)剪去正方形的邊長(zhǎng)為0.8333m時(shí)，水槽的容積最大為9.2593m3．10.3.2多元函數(shù)無(wú)約束優(yōu)化的最優(yōu)解求解

多元函數(shù)無(wú)約束優(yōu)化的標(biāo)準(zhǔn)形式：

，其中

是向量

在MATLAB中利用函數(shù)fminunc和fminsearch求解，fminunc調(diào)用格式如下：

[x,fval]=fminunc(fun,x0)在點(diǎn)x0處開(kāi)始并嘗試求fun中描述的函數(shù)的局部最小值點(diǎn)x和函數(shù)值fval

[x,fval]=fminunc(fun,x0,options)使用options中指定的優(yōu)化選項(xiàng)求最小值

fminsearch調(diào)用格式與fminunc相同，fminunc為無(wú)約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法，fminsearch采用簡(jiǎn)單搜索法.當(dāng)函數(shù)的階數(shù)大于2時(shí)，使用fminunc比f(wàn)minsearch更有效，當(dāng)函數(shù)高度不連續(xù)時(shí)，使用fminsearch更有效．

例10.7求

的最小值點(diǎn).解為了對(duì)函數(shù)有一個(gè)直觀認(rèn)識(shí)，先繪制出其三維圖形．clear[x,y]=meshgrid(-10:0.01:10);z=100*(y-x.^2).^2+(1-x).^2;mesh(x,y,z)得到圖形如圖10-1所示，可知f(x,y)存在最小值，可取初始值x0=[-5,0]．>>fun=@(x)100*(x(2)-x(1)^2)^2+(1-x(1))^2;>>x0=[-5,0];>>x=fminsearch(fun,x0)x=1.00001.0000可知，當(dāng)x=1,y=1時(shí)，f(x,y)得到最小值．圖10-1函數(shù)f(x,y)的三維圖形例10.8求

的最小值．解>>fun=@(x)3*x(1)^2+2*x(1)*x(2)+x(2)^2-4*x(1)+5*x(2);>>x0=[1,1];>>[x,fval]=fminunc(fun,x0)Localminimumfound.Optimizationcompletedbecausethesizeofthegradientislessthanthevalueoftheoptimalitytolerance.<stoppingcriteriadetails>x=2.2500-4.7500fval=-16.3750可知當(dāng)x=2.25,y=-4.75時(shí)，f(x,y)得到最小值-16.375．例10.9（選址問(wèn)題）某鎮(zhèn)為推進(jìn)新農(nóng)村建設(shè)，準(zhǔn)備引進(jìn)兩個(gè)環(huán)保項(xiàng)目：

籌建天然氣輸送中心，通過(guò)管道由輸送中心直接向各村輸送天然氣；

籌建垃圾處理站