第8章最優(yōu)化方法的MATLAB實(shí)現(xiàn)講稿

最優(yōu)化方法的MATLAB一維搜索問題基本數(shù)學(xué)原理xxx2最優(yōu)化方法的MATLAB一維搜索問題基本數(shù)學(xué)原理xxx2

x有關(guān)函數(shù)介紹實(shí)現(xiàn)f12

解決同一個(gè)問題若有多種方案。最優(yōu)化方法就是研究如何從多個(gè)方案中選出最優(yōu)方案的數(shù)學(xué)分支。MATLAB的最優(yōu)化工具箱實(shí)現(xiàn)了解決不同類型最優(yōu)化問題的算法。

8.1

一維搜索問題在某些情況下可以直接用于求解實(shí)際問題，但大多數(shù)情況下它作為多變量最優(yōu)化方法的基礎(chǔ)使用的，因?yàn)檫M(jìn)行多變量優(yōu)化要用到一維搜索算法。

8.1.1

一維搜索問題的數(shù)學(xué)模型為：minf(x)xxx式中，,和為標(biāo)量，該問題的搜索過程可用下式表達(dá)：xxdk1k式中為本次迭代的值，d為搜索方向，以一維搜索就是要利用本次迭代的信息來構(gòu)造下次迭代的條件。求解單變量最優(yōu)化問題的方法有很多種。根據(jù)目標(biāo)函數(shù)是否需要求導(dǎo)，可以分為兩類，即直接法和間接法。直接法不需要目標(biāo)函數(shù)的導(dǎo)數(shù)，而間接法則需要用到目標(biāo)函數(shù)的導(dǎo)數(shù)。如果函數(shù)的導(dǎo)數(shù)容易求得，一般來說首先考慮使用三次插值法，因?yàn)樗哂休^高的效率。對于只需計(jì)算函數(shù)值的方法，二次插值是一個(gè)很好的方法，它的收斂速度較快，在極小點(diǎn)所在區(qū)間較小時(shí)尤其如此。黃金分割法則是一種十分穩(wěn)定的方法，并且計(jì)算簡單。由于以上原因，MATLAB優(yōu)化工具箱中用得較多的方法是二次插值法、三次插值法、二次三次混合插值法和黃金分割法。

8.1.2

利用fminbnd函數(shù)找到固定區(qū)間內(nèi)單變量函數(shù)的最小值。調(diào)用格式為：●x=fminbnd(fun,x1,x2)：返回區(qū)間{x1,x2}上fun參數(shù)描述的標(biāo)量函數(shù)的最小值點(diǎn)x?！駒=fminbnd(fun,x1,x2,options)：用options參數(shù)指定的優(yōu)化參數(shù)進(jìn)行最小-1-

應(yīng)用實(shí)例，0

2。線性規(guī)劃基本數(shù)學(xué)原理axaxax應(yīng)用實(shí)例，0

2。線性規(guī)劃基本數(shù)學(xué)原理axaxaxbaxaxaxb1122nn

1111221nn12112222nn2

a

xaxaxbx,x,,xm11m22mnnm12●[x,fval]=fminbnd(…)：還返回解x處目標(biāo)函數(shù)的值。●[x,fval,exitflag]=fminbnd(…)：還返回exitflag值描述fminbnd函數(shù)的退出條件?！馵x,fval,exitflag,output]=fminbnd(…)：還返回包含優(yōu)化信息的結(jié)構(gòu)output。

8.1.3

例8－1對邊長為2m的正方形鐵板，在4個(gè)角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？

解設(shè)剪去的正方形的邊長為x，則水槽的容積為：f(x)(22x)2xx1。首先編寫目標(biāo)函數(shù)（文件名為example8_1_3a.m）%創(chuàng)建目標(biāo)函數(shù)functionf=example8_1_3a(x)f=-(2-2*x).^2*x;然后調(diào)用函數(shù)：x=fminbnd(@example8_1_3a,0,1)得到問題的解：x=0.3333，fval=-0.5926。即剪掉的正方形的邊長為0.333m時(shí)水槽的容積最大，最大值為0.593m

8.2

線性規(guī)劃是處理線性目標(biāo)函數(shù)和線性約束的一種較為成熟的方法，目前已經(jīng)廣泛應(yīng)用于軍事、經(jīng)濟(jì)、工業(yè)、農(nóng)業(yè)、教育、商業(yè)和社會(huì)科學(xué)等許多方面。

8.2.1

線性規(guī)劃問題的標(biāo)準(zhǔn)形式是：minzcxcxcx

或

-2-

min

n

minmin

n

minzCX有關(guān)函數(shù)介紹zcxxb,i1,2,,mijji

AXbjjj1

j1x0,j

XOn

a

寫成矩陣形式為：

線性規(guī)劃的標(biāo)準(zhǔn)形式要求使目標(biāo)函數(shù)最小化，約束條件取等式，變量b非負(fù)。不符合這幾個(gè)條件的線性模型可以轉(zhuǎn)化成標(biāo)準(zhǔn)形式。MATLAB采用投影法求解線性規(guī)劃問題，該方法是單純形法的變種。

8.2.2

在MATLAB工具箱中，可用linprog函數(shù)求解線性規(guī)劃問題。linprog函數(shù)的調(diào)用格式如下：●x=linprog(f,A,b)：求解問題minf'*x，約束條件為A*x<=b?！駒=linprog(f,A,b,Aeq,beq)：求解上面的問題，但增加等式約束，即Aeq*x=beq。若沒有不等式約束，則令A(yù)=[],b=[]。●x=linprog(f,A,b,Aeq,beq,lb,ub)：定義設(shè)計(jì)x的下界lb和上界ub，使得x始終在該范圍內(nèi)。若沒有等式約束，令A(yù)eq=[],beq=[]。●x=linprog(f,A,b,Aeq,beq,lb,ub,x0)：設(shè)置初值為x0。該選項(xiàng)只適用于中型問題，默認(rèn)時(shí)大型算法將忽略初值?！駒=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)：用options指定的優(yōu)化參數(shù)進(jìn)行最小化?！馵x,fval]=linprog(…)：返回解x處的目標(biāo)函數(shù)值fval?！馵x,lambda,exitflag]=linprog(…)：返回exitflag值，描述函數(shù)計(jì)算的退出條件?！馵x,lambda,exitflag,output]=linprog(…)：返回包含優(yōu)化信息的輸出參數(shù)output?！馵x,fval,exitflag,output,lambda]=linprog(…)：將解x處的拉格朗日乘子返回到lambda參數(shù)中。調(diào)用格式中，lambda參數(shù)為解x處包含拉格朗日乘子的結(jié)構(gòu)。它有以下一

-3-

應(yīng)用實(shí)例x2f1000x應(yīng)用實(shí)例x2f1000x800x2lower—下界lbupper—上界ubineqlin—線性不等式eqlin—線性等式exitflag參數(shù)表示算法終止的原因，下面列出不同值對應(yīng)的退出原因：1函數(shù)在解x處有解0迭代次數(shù)超過options.MaxIter-2沒有找到可行點(diǎn)-3問題無解-4執(zhí)行算法時(shí)遇到NaN-5原問題和對偶問題都不可行-7搜索方向太小，不能繼續(xù)前進(jìn)。

8.2.3

例8－2某河流邊有兩個(gè)化工廠，流經(jīng)第一個(gè)化工廠的河水流量是每天500萬立方米，在兩個(gè)工廠之間有一條流量為200萬立方米的支流（如圖8－1所示）。第一個(gè)化工廠每天排放工業(yè)污水2萬立方米，第二個(gè)化工廠每天排放工業(yè)污水1.4萬立方米，從第一個(gè)化工廠排出的污水流到第二個(gè)化工廠之前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%，因此兩個(gè)化工廠都必須各自處理凈化一部分污水，第一個(gè)化工廠處理污水的成本是0.1元∕立方米，第二個(gè)化工廠處理污水的成本是0.08元∕立方米。問在滿足環(huán)保要求的條件下，各化工廠每天應(yīng)處理多少污水，才能使兩廠總的處理污水費(fèi)用最少？

第一化工廠第二化工廠

圖8－1解：設(shè)，x（萬立方米∕天）。則目標(biāo)函數(shù)：

-4-

2x5000.8(2x)(1.4x2x5000.8(2x)(1.4x)12

x1x

12

無約束非線性最優(yōu)化問題基本數(shù)學(xué)原理1

700

0.8

x1.4x,x00.2%，即x

0.2%x2

1

2xx1.6121

約束條件：，即0.8x

約束條件3。

因此，該問題的線性規(guī)劃模型歸結(jié)為：minf1000x800xx1

st.x2

12求解程序：%線性規(guī)劃問題f=[1000800];A=[-10;-0.8-1;10;01];b=[-1;-1.6;2;1.4];lb=zeros(2,1);[x,fval,exitflag]=linprog(f,A,b,[],[],lb)運(yùn)行結(jié)果：x=1.00000.8000fval=1.6400e+003exitflag=1由上可知，第一個(gè)化工廠每天處理的污水量為1萬立方米∕天，第二個(gè)化工廠每天處理的污水量為0.8萬立方米∕天，才能使兩廠總的處理污水費(fèi)用最少。

8.3

8.3.1

求解無約束最優(yōu)化問題的方法主要有兩類，即直接搜索法(Directsearch-5-

f(x)的負(fù)梯度方向f(x)有關(guān)函數(shù)介紹f(x)的負(fù)梯度方向f(x)有關(guān)函數(shù)介紹xf(x)為函數(shù)，返回標(biāo)量。x直接搜索法適用于目標(biāo)函數(shù)高度非線性，沒有導(dǎo)數(shù)或?qū)?shù)很難計(jì)算的情況。由于實(shí)際工作中很多問題都是非線性的，故直接搜索法不失為一種有效的解決辦法。常用的直接搜索法為單純形法，此外還有Hooke-Jeeves搜索法、Pavell共軛方向法等，其缺點(diǎn)是收斂速度慢。在函數(shù)的導(dǎo)數(shù)可求的情況下，梯度法是一種更優(yōu)的方法。該法利用函數(shù)的梯度（一階導(dǎo)數(shù)）和Hess（二階導(dǎo)數(shù)）構(gòu)造算法，可以獲得更快的收斂速度。函數(shù)即反映了函數(shù)的最大下降方向。當(dāng)搜索方向取為負(fù)梯度方向時(shí)稱為最速下降法。常見的梯度法有最速下降法、Newton法、Marquart法、共軛梯度法和擬牛頓法（Quasi-Newtonmethod）等。在所有這些方法中，用得最多的是擬牛頓法。進(jìn)行一維搜索時(shí)，如果梯度值可以直接得到，用三次插值的方法進(jìn)行一維搜索，如果梯度值不能直接得到，采用二次、三次混合插值法。

8.3.2

MATLAB優(yōu)化工具箱中用于求解無約束非線性規(guī)劃問題的函數(shù)有fminunc和fminsearch。⒈fminunc函數(shù)用該函數(shù)求多變量無約束函數(shù)的最小值。多變量無約束函數(shù)的數(shù)學(xué)模型為：minf(x)

式中，是矢量，fminunc函數(shù)在給定初值的情況下，求多變量標(biāo)量函數(shù)的最小值。常用于無約束非線性最優(yōu)化問題。其調(diào)用格式為：●x=fminunc(fun,x0)：給定初值x0，求fun函數(shù)的局部極小值點(diǎn)x。x0可以是標(biāo)量、矢量或矩陣?！駒=fminunc(fun,x0,options)：用options參數(shù)中指定的優(yōu)化參數(shù)進(jìn)行最小化。●x=fminunc(fun,x0,options,P1,P2,…)：將問題參數(shù)P1,P2等直接輸給目標(biāo)函數(shù)fun，將options參數(shù)設(shè)置為空矩陣，作為options參數(shù)的默認(rèn)值。●[x,fval]=fminunc(…)：將解x處目標(biāo)函數(shù)值返回到fval參數(shù)中。●[x,fval,exitflag]=fminunc(…)：返回exitflag值，描述函數(shù)的退出條件?！馵x,fval,exitflag,output]=fminunc(…)：返回包含優(yōu)化信息的結(jié)構(gòu)輸出?！馵x,fval,exitflag,output,grad]=fminunc(…)：將解x處fun函數(shù)的梯度值返回到grad參數(shù)中?！馵x,fval,exitflag,output,grad,hessian]=fminunc(…)：將解x處目標(biāo)函數(shù)的Hessian矩陣信息返回到hessian參數(shù)中。

-6-

應(yīng)用實(shí)例112

⒉應(yīng)用實(shí)例112fminsearch求解多變量無約束函數(shù)的最小值。該函數(shù)常用于無約束非線性最優(yōu)化問題。其調(diào)用格式為：●x=fminsearch(fun,x0)：初值為x0，求fun函數(shù)的局部極小值點(diǎn)x。x0可以是標(biāo)量、矢量或矩陣?！駒=fminsearch(fun,x0,options)：用options參數(shù)中指定的優(yōu)化參數(shù)進(jìn)行最小化?！駒=fminsearch(fun,x0,options,P1,P2,…)：將問題參數(shù)P1,P2等直接輸給目標(biāo)函數(shù)fun，將options參數(shù)設(shè)置為空矩陣，作為options參數(shù)的默認(rèn)值?！馵x,fval]=fminsearch(…)：將解x處目標(biāo)函數(shù)值返回到fval參數(shù)中?！馵x,fval,exitflag]=fminsearch(…)：返回exitflag值，描述函數(shù)的退出條件?！馵x,fval,exitflag,output]=fminsearch(…)：返回包含優(yōu)化信息的輸出結(jié)構(gòu)output。fminsearch函數(shù)使用單純形法進(jìn)行計(jì)算。對于求解二次以上的問題，fminsearch函數(shù)比fminunc函數(shù)效率低。但是，當(dāng)問題為高度非線性時(shí)，fminsearch函數(shù)更具穩(wěn)健性。

8.3.3

例8－3最小化函數(shù)：f(x)3x22xxx2解：創(chuàng)建目標(biāo)函數(shù)程序（文件名為example8_3_3a1.m）：%創(chuàng)建目標(biāo)函數(shù)functionf=example8_3_3a1(x)f=3*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2);●調(diào)用fminunc函數(shù)，求[1,1]附近的極小值點(diǎn)、極小值。x0=[1,1];[x,fval,exitflag]=fminunc(@example8_3_3a1,x0)運(yùn)行結(jié)果：x=1.0e-006*0.2541-0.2029fval=1.3173e-013exitflag=1●調(diào)用fminsearch函數(shù)，求[1,1]附近的極小值點(diǎn)、極小值。x0=[1,1];[x,fval,exitflag]=fminsearch(@example8_3_3a1,x0)

-7-

運(yùn)行結(jié)果：x=1.0e-004*-0.06750.1715fval=1.9920e-010exitflag=1用提供的梯度g使函數(shù)最小化，創(chuàng)建目標(biāo)函數(shù)程序（文件名為example8_3_3b1.m）：%創(chuàng)建目標(biāo)函數(shù),并提供梯度函數(shù)。function[f,g]=example8_3_3b1(x)f=3*x(1)^2+2*x(1)*x(2)+x(2)^2;%目標(biāo)函數(shù)ifnargout>1g(1)=6*x(1)+2*x(2);g(2)=2*x(1)+2*x(2);end●調(diào)用fminunc函數(shù)，求[1,1]附近的極小值點(diǎn)、極小值。options=optimset('GradObj','on');x0=[11];[x,fval,exitflag]=fminunc(@example8_3_3b1,x0,options)運(yùn)行結(jié)果：x=1.0e-015*0.1110-0.8882fval=6.2862e-031exitflag=1●調(diào)用fminsearch函數(shù)，求[1,1]附近的極小值點(diǎn)、極小值。options=optimset('GradObj','on');x0=[11];[x,fval,exitflag]=fminsearch(@example8_3_3b1,x0,options)運(yùn)行結(jié)果：x=1.0e-004*-0.06750.1715fval=1.9920e-010-8-

有約束非線性最優(yōu)化問題基本數(shù)學(xué)原理有關(guān)函數(shù)介紹x

Aeq

Aeq有約束非線性最優(yōu)化問題基本數(shù)學(xué)原理有關(guān)函數(shù)介紹x

Aeq

Aeqf(x)，c(x)和ceq(x)可以是非線性函數(shù)。

Axb，x0Axb

xbeqlbxubceq(x)0Axb1

8.4

8.4.1

在有約束最優(yōu)化問題中，通常要將該問題轉(zhuǎn)化為更簡單的子問題，這些子問題可以求解并作為迭代過程的基礎(chǔ)。早期的方法通常是通過構(gòu)造懲罰函數(shù)等來將有約束的最優(yōu)化問題轉(zhuǎn)換為無約束最優(yōu)化問題進(jìn)行求解。現(xiàn)在，這些方法已經(jīng)被更有效的基于K-T(Kuhn-Tucker)方程解的方法所取代。K-T方程的解形成了許多非線性規(guī)劃算法的基礎(chǔ)。這些算法直接計(jì)算拉格朗日乘子。用擬牛頓法更新過程，給K-T方程積累二階信息，可以保證有約束擬牛頓的超線性收斂。這些方法稱為序列二次規(guī)劃法（SQP），因?yàn)樵诿看沃饕牡^程中都求解一次二次規(guī)劃子問題。該子問題可以用任意一種二次規(guī)劃算法求解，求得的解可以用來形成新的迭代公式。

8.4.2

利用fmincon函數(shù)求多變量有約束非線性函數(shù)的最小值。假設(shè)多變量非線性函數(shù)的數(shù)學(xué)模型為：minf(x)c(x)0

式中，x，b，beq，lb和ub為矢量，A和為矩陣，c(x)和ceq(x)為函數(shù)，返回標(biāo)量。fmincon函數(shù)的調(diào)用格式如下：●x=fmincon(fun,x0,A,b)：給定初值x0，求解fun函數(shù)的最小值點(diǎn)x。fun函數(shù)的約束條件為可以是標(biāo)量、矢量或矩陣?！駒=fmincon(fun,x0,A,b,Aeq,beq)：最小化fun函數(shù)，約束條件為和Aeqxbeq，若沒有不等式存在，則設(shè)置A=[]，b=[]?！駒=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)：定義設(shè)計(jì)變量x的下界lb和上界

-9-

xub

c(x)0

c(x)xub

c(x)0

c(x)0和等式約束參數(shù)是一個(gè)包含函數(shù)名的字符串。該函數(shù)可以是M文件、應(yīng)用實(shí)例minf(x,x,x)x2(x2)x123123

3753.5610

x30310

51244103x4xx0

x/x01133

x

123

(x1.5)4.410x4xx3.7x0121233

x44.512333xxx0

31

x1●x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)：在上面的基礎(chǔ)上，在nonlcon參數(shù)中提供非線性的c(x)或ceq(x)。fmincon函數(shù)要求且ceq(x)0。當(dāng)無邊界存在時(shí)，令lb=[]和（或）ub=[]?！駒=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)：用options參數(shù)指定的參數(shù)進(jìn)行最小化?！馵x,fval]=fmincon(…)：還返回解x處的目標(biāo)函數(shù)值。●[x,fval,exitflag]=fmincon(…)：還返回exitflag參數(shù)，描述函數(shù)計(jì)算的退出條件?！馵x,fval,exitflag,output]=fmincon(…)：還返回包含優(yōu)化信息的輸出參數(shù)output?！馵x,fval,exitflag,output,lambda]=fmincon(…)：還返回解x處包含拉格朗日乘子的lambda參數(shù)?！馵x,fval,exitflag,output,lambda,grad]=fmincon(…)：還返回解x處fun函數(shù)的梯度?！馵x,fval,exitflag,output,lambda,grad,hessian]=fmincon(…)：還返回解x處fun函數(shù)的Hess矩陣。各調(diào)用格式中，nonlcon參數(shù)計(jì)算非線性不等式約束ceq(x)0。nonlcon內(nèi)部文件或MEX文件。它要求輸入一個(gè)矢量x，返回兩個(gè)變量——x處的非線性矢量c和ceq。

8.4.3

例8－4350163x2.86x0.860

.t.

10解：創(chuàng)建目標(biāo)函數(shù)

-10-

二次規(guī)劃12

AeqTT

二次規(guī)劃12

AeqTT

lbxubfunctionf=example8_4_3a(x)f=x(1)*x(1)*(x(2)+2)*x(3);創(chuàng)建非線性約束條件函數(shù)程序（文件名為example8_4_3b.m）：function[c,ceq]=example8_4_3b(x)c(1)=350-163*x(1)^(-2.86)*x(3)^0.86;c(2)=10-0.004*(x(1)^(-4))*x(2)*(x(3)^3);c(3)=x(1)*(x(2)+1.5)+0.0044*(x(1)^(-4))*x(2)*(x(3)^3)-3.7*x(3);c(4)=375-356000*x(1)*(x(2)^(-1))*x(3)^(-2);c(5)=4-x(3)/x(1);ceq=0;求解程序：x0=[22520]';lb=[14.510]';ub=[45030]';[x,fval,exitflag]=fmincon(@example8_4_3a,x0,[],[],[],[],lb,ub,@example8_4_3b)運(yùn)行結(jié)果：x=1.00004.500010.0000fval=65exitflag=1

8.5

如果某非線性規(guī)劃的目標(biāo)函數(shù)為自變量的二次函數(shù)，約束條件全是線性函數(shù)，就稱這種規(guī)劃為二次規(guī)劃。其數(shù)學(xué)模型為：minxHxfxxAxbs.t.xbeq

-11-

A

2Axb。

Aeqxbeq

。

x和x處的目標(biāo)函數(shù)值fval。

x處包含拉格朗日乘f(x)xxxx2x6x

f(x)xA

2Axb。

Aeqxbeq

。

x和x處的目標(biāo)函數(shù)值fval。

x處包含拉格朗日乘f(x)xxxx2x6x

f(x)xxxx2x6x12fAeqfx為列矢量。

xHxfx最小化，其約12x2x2xx3

12

2211221112,x1TT221212112

12

22121212262x0,x22,12,Ax11x21121,b2。23利用quadprog函數(shù)求解二次規(guī)劃問題，其調(diào)用格式為：

●x=quadprog(H,f,A,b)：返回矢量x，使函數(shù)1

束條件為●x=quadprog(H,f,A,b,Aeq,beq)：仍然求解上面的問題，但添加了等式約束條件●x=quadprog(H,f,A,b,lb,ub)：定義設(shè)計(jì)變量的下界lb和上界ub，使得lbxub●x=quadprog(H,f,A,b,lb,ub,x0)：同上，并設(shè)置初值x0。●x=quadprog(H,f,A,b,lb,ub,x0,options)：根據(jù)options參數(shù)指定的優(yōu)化參數(shù)進(jìn)行最小化?！馵x,fval]=quadprog(?)：返回解●[x,fval,exitflag]=quadprog(?)：返回exitflag參數(shù)，描述計(jì)算的退出條件。●[x,fval,exitflag,output]=quadprog(?)：返回包含優(yōu)化信息的結(jié)構(gòu)輸出output?！馵x,fval,exitflag,output,lambda]=quadprog(?)：返回解子的lambda結(jié)構(gòu)參數(shù)。

例8－5求解下面的最優(yōu)化問題：

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

xx2

解

(x2xx2x)2x6x

記，H

-12-

12Axb0)12Axb0)TxTxAeq

AxTTxbeqAeqfminxHxfxxs.t.(0求解程序：H=[1-1;-12];f=[-2;-6];A=[11;-12;21];b=[2;2;3];lb=zeros(2,1);[x,fval,exitflag]=quadprog(H,f,A,b,[],[],lb)運(yùn)行結(jié)果：x=0.66671.3333fval=-8.2222exitflag=1

8.60－1規(guī)劃

0－1規(guī)劃是一種特殊形式的整數(shù)規(guī)劃。這種規(guī)劃的決策變量僅取值0或1。0－1變量可以數(shù)量化地描述諸如開與關(guān)、取與棄、有與無等現(xiàn)象所反映的離散變量間的邏輯關(guān)系、順序關(guān)系以及互斥的約束條件，因此0－1規(guī)劃非常適合描述和解決如線路設(shè)計(jì)、工廠選址、生產(chǎn)計(jì)劃安排、旅行購物、背包問題、人員安排、代碼選取、可靠性等人們所關(guān)心的多種問題。

8.6.1基本原理

0－1規(guī)劃問題具有下面的形式：minfxAxb

式中，和為矩陣，,b和beq為列矢量，必須是二值矢量，即值必須是0和1。

-13-

xb。

。x0

x和x處的目標(biāo)函數(shù)值fval。bintproxb。

。x0

x和x處的目標(biāo)函數(shù)值fval。bintprog函數(shù)的輸入?yún)?shù)及其意義意義包含線性目標(biāo)函數(shù)系數(shù)矢量包含線性不等式約束的系數(shù)的矩陣對應(yīng)于線性不等式約束右端項(xiàng)的矢量包含線性等式約束系數(shù)的矩陣包含線性等式約束常數(shù)的矢量算法的初值包含算法選項(xiàng)的選項(xiàng)結(jié)構(gòu)x處收斂；

8.6.2有關(guān)函數(shù)介紹

用bintprog函數(shù)求解0－1規(guī)劃問題，該函數(shù)具有下面的調(diào)用格式。●x=bintprog(f)：求解無約束0－1規(guī)劃問題。●x=bintprog(f,A,b)：求解0－1規(guī)劃問題，有不等式約束A●x=bintprog(f,A,b,Aeq,beq)：求解前面的0－1規(guī)劃問題，還有等式約束Aeqxbeq●x=bintprog(f,A,b,Aeq,beq,x0)：設(shè)置算法的初值x，如果內(nèi)，bintprog函數(shù)調(diào)用默認(rèn)的初值。●x=bintprog(f,A,b,Aeq,beq,x0,options)：用options結(jié)構(gòu)中的值代替優(yōu)化選項(xiàng)，可以用optimset函數(shù)創(chuàng)建該結(jié)構(gòu)?！馵x,fval]=bintprog(┅)：返回解●[x,fval,exitflag]=bintprog(┅)：還返回描述bintprog函數(shù)退出狀態(tài)的參數(shù)exitflag。●[x,fval,exitflag,output]=bintprog(┅)：還返回包含優(yōu)化相關(guān)信息的output結(jié)構(gòu)。表8－1列出了bintprog函數(shù)輸入?yún)?shù)的意義。

表8－1

參數(shù)f

AbAeqbeqx0options

bintprog函數(shù)的輸出參數(shù)exitflag用來識(shí)別計(jì)算終止的原因，可取下面的值。1函數(shù)在解0迭代次數(shù)超過了options.MaxIter；-2問題不可行；-4搜索節(jié)點(diǎn)數(shù)超過了options.MaxNodes；

-14-

數(shù)據(jù)表13202070x,x,x,x,x

i

1數(shù)據(jù)表13202070x,x,x,x,x

i

12345

f(7055422811)T228018550,

1234520x32401542表示在i地不建廠；1,

421011282345

表示在i地建廠。

18x15x11x8x60x5180811xxxx312345

12345x,x,x,x,x2345-6LP求解器在某節(jié)點(diǎn)處求解LP松弛問題時(shí)的迭代次數(shù)超過了options.MaxRLP。bintprog函數(shù)的輸出參數(shù)output為包含與優(yōu)化有關(guān)信息的結(jié)構(gòu)。結(jié)構(gòu)的字段為：iterations：迭代次數(shù)nodes：搜索過的節(jié)點(diǎn)數(shù)time：算法執(zhí)行時(shí)間algorithm：使用的算法message：算法終止的原因

8.6.3應(yīng)用實(shí)例

例8－6在5個(gè)地點(diǎn)中選3處建生產(chǎn)同一產(chǎn)品的工廠，在這5個(gè)地點(diǎn)建廠所需投資，點(diǎn)用農(nóng)田，建成以后的生產(chǎn)能力等數(shù)據(jù)如表8－2所示。表8－2地點(diǎn)所需投資(萬元)占用農(nóng)田(畝)生產(chǎn)能力(萬噸)

現(xiàn)在有總投資800萬元，占用農(nóng)田指標(biāo)60畝，應(yīng)如何選擇廠址，使建成后總生產(chǎn)能力最大。解：設(shè)5個(gè)0－1變量

xi1,2,3,5。

整數(shù)規(guī)劃模型為：maxz70x55x42x28x11x320x280x240x210x180x800

s.t.

記，；

-15-

320280240210180800

67320280240210180800

67ccccc148.720008cxcii件，c2345652.061.372.048.752.030001000500400020007966420181511860764.0100081

Aeq1111，beq3；求解程序：f=[-70;-55;-42;-28;-11];A=[320280240210180;201815118];b=[800;60];Aeq=[11111];beq=[3];[x,fval,exitflag]=bintprog(f,A,b,Aeq,beq)運(yùn)行結(jié)果：x=10110fval=-140exitflag=1即選擇在地點(diǎn)1、3、4建廠，總投資770萬元，占用農(nóng)田46畝，總生產(chǎn)能力可以達(dá)到140萬噸。例8－7（平板車的優(yōu)化裝載問題）有七種規(guī)格的包裝箱要裝到兩輛鐵路平板車上去。包裝箱的寬和高是一樣的，但厚度（t，以cm計(jì)）及重量（w，以kg計(jì)）是不同的。表8－3給出了每種包裝箱的厚度、重量及數(shù)量。每輛平板車有10.2m長的地方可用來裝包裝箱（像面包片那樣），載重為40t。由于當(dāng)?shù)刎涍\(yùn)的限制，對c，c，c路平板車上的這類箱子所占的空間（厚度）不能超過302.7cm。試建立將包裝箱裝到平板車上去使得浪費(fèi)的空間最小的數(shù)學(xué)模型。表8－3各種包裝箱的厚度、重量及數(shù)量ct(cm)w(kg)件數(shù)

解設(shè)裝在第一輛車上的類箱子為件，裝在第二輛車上的yi1,,7。i-16-

(t,,t)(48.7,52.0,61.3,72.0,48.7,52.0,64.0)；

17

1(t,,t)(48.7,52.0,61.3,72.0,48.7,52.0,64.0)；

17

17

7

i1

模型1

1,c類的第j個(gè)箱子裝在第k輛車上；k1,2;i1,,7;

x。

iii7

77

7

ij1ij2n(xx)n,i1,,7;

,x0,1,i1,i,57;j11,,n。iij1ij2wx40,wy40;

iiiii

i0,c類的第

i

j1j7

iiii1i1

1i177t

j個(gè)箱子不裝在第k輛車上。j1,,ni.i

ij1ij2ix302.7,ty302.7;x

j17wx40,wiiiii5i5

x,y為整數(shù)，且x，y0，i

nini

模型27

ij1iij2iij1iij2i1i1j1i1j177

tx1020,tx1020;

7nini

txt302.7;xj1i1j1niniw(w1,,w7)(2,3,1,0.5,4,2,1)；n(n,,n)(8,7,9,6,6,4,8)●建立整數(shù)規(guī)劃模型：maxft(xy)iiixyn,i1,,7;

s.tx1020,ty1020;

iii●為了將模型1改寫為0－1規(guī)劃模型，再記，xijk則由模型1可得0－1規(guī)劃模型：maxft[ni(xx)]iij1ij2i1j1xx1,i1,,7;j1,,n

s.t.

iij1iij2i5

-17-

7

i1

t模型3

i5

i7

i1

t模型3

i5

i

i1,,7;

ii7

7

為整數(shù)，且x0，i

1,c類的第，。

7

nwx40;

iii

0,c類的第

ni

iijij17ii1

17t

j個(gè)箱子不裝在車上。1,,n

xn,i1,,7;

x302.7;ii

j

w40;i

xiij模型4ni

i1j17txni

iiji1j11020;

7txni

iiji5j1x302.7;

0,1,i1,,7;jimaxftxiixn,i1,,7;

sx1020;

x為了將模型3改寫為0－1規(guī)劃模型，記xij則由模型3可得0－1規(guī)劃模型：maxftxiiji1j1

s.t.

模型4的求解程序：%0-1規(guī)劃問題。t=[48.7;52;61.3;72;48.7;52;64];w=[2;3;1;0.5;4;2;1];n=[8;7;9;6;6;4;8];%下面構(gòu)造矢量f-18-

f=zeros(sum(n),1);m=0;fori=1:7forj=1:n(i)m=m+1;f(m)=(-1)*t(i);endend%下面構(gòu)造AA1=zeros(7,sum(n));m=0;fori=1:7forj=1:n(i)m=m+1;A1(i,m)=1;endendA2=zeros(1,sum(n));m=0;fori=1:7forj=1:n(i)m=m+1;A2(m)=w(i);endendA3=zeros(1,sum(n));m=0;fori=1:7forj=1:n(i)m=m+1;A3(m)=t(i);endendA4=zeros(1,sum(n));m=0;fori=1:7forj=1:n(i)m=m+1;ifi>=5A4(m)=t(i);endend-19-

endA=[A1;A2;A3;A4];b=[n;40;1020;302.7];[x,fval,exitflag]=bintprog(f,A,b)運(yùn)行結(jié)果：x=000001001111111111000000110000011000-20-

最大最小化F

Aeq

最大最小化F

Aeq

x

xbeqlbxubAeqceq(x)0Axb10001100000fval=-1018exitflag=-4

8.7

通常我們遇到的都是目標(biāo)函數(shù)的最大化和最小化問題，但是在某些情況下，則要求使最大值最小化才有意義。例如，城市規(guī)劃中需要確定急救中心、消防中心的位置，可取的目標(biāo)函數(shù)應(yīng)該是到所有地點(diǎn)最大距離的最小值，而不是到所有目的地的距離和為最小。這是兩種完全不同的準(zhǔn)則，在控制理論、逼近論、決策論中也使用最大最小化原則。

8.7.1基本數(shù)學(xué)原理

最大最小化問題的數(shù)學(xué)模型為：minmaxF(x)xc(x)0

式中,b,beq,lb和ub為矢量，A和為矩陣，c(x),ceq(x)和F(x)為函數(shù)，返回矢量。F(x),c(x)和ceq(x)可以是非線性函數(shù)。

-21-

Axb，求解最大最小化問題。AeqAxb，求解最大最小化問題。Aeqxbeq

xub

0且ceq(x)0。若

fminimax使多目標(biāo)函數(shù)中的最壞情況達(dá)到最小化。給定初值估計(jì)，該值必須服從一定的約束條件。其調(diào)用格式如下：●x=fminimax(fun,x0)：初值為x0，找到fun函數(shù)的最大最小化解x。●x=fminimax(fun,x0,A,b)：給定線性不等式●x=fminimax(fun,x0,A,b,Aeq,beq)：還給定線性等式，求解最大最小化問題。如果沒有不等式存在，設(shè)置A=[]、b=[]?！駒=fminimax(fun,x0,A,b,Aeq,beq,lb,ub)：還為設(shè)計(jì)變量x定義一系列下限lb和上限ub，使得總有l(wèi)b?！駒=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)：在nonlcon參數(shù)中給定非線性不等式c(x)或等式ceq(x)。fminimax函數(shù)要求c(x)無邊界存在，則設(shè)lb=[]和（或）ub=[]?！駒=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)：用options參數(shù)指定的參數(shù)進(jìn)行優(yōu)化?！駒=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2,┅)：將問題參數(shù)P1,P2等直接傳遞給函數(shù)fun和nonlcon。如果不需要變量A,b,Aeq,beq,lb,ub，nonlcon和options，則將它們設(shè)置為空矩陣。●[x,fval]=fminimax(…)：還返回解x處的目標(biāo)函數(shù)值?！馵x,fval,maxfval]=fminimax(…)：還返回解x處的最大函數(shù)值?！馵x,fval,maxfval,exitflag]=fminimax(…)：返回exitflag參數(shù)，描述函數(shù)計(jì)算的退出條件。●[x,fval,maxfval,exitflag,output]=fminimax(…)：返回描述優(yōu)化信息的結(jié)構(gòu)輸出output參數(shù)?！馵x,fval,maxfval,exitflag,output,lambda]=fmincon(…)：返回包含解x處拉格朗日乘子的lambda參數(shù)。其中，maxfval變量為解x處函數(shù)值的最大值，即maxfval=max{fun(x)}。使用fminimax函數(shù)時(shí)需要注意下面幾個(gè)問題：⑴在options.MinAbsMax中設(shè)置F最大絕對值最小化了的目標(biāo)數(shù)。該目標(biāo)應(yīng)該放到F的第1個(gè)元素中去。⑵當(dāng)提供了等式約束并且在二次子問題中發(fā)現(xiàn)并剔除了因變等式時(shí)，則在等式連續(xù)的情況下才被剔除。若系統(tǒng)不連續(xù)，則子問題不可行并且在過程標(biāo)題中打印‘infeasible’字樣。另外，要求目標(biāo)函數(shù)必須連續(xù)，否則fminimax函數(shù)有可能給出局部最優(yōu)解。

-22-

,bii

x

,bii

x

a108181451089y)，要求它到最遠(yuǎn)需求點(diǎn)的距離盡可能小。

i

ii

ii：1435912620178

。

例8－8定位問題。設(shè)某城市有某種物品的10個(gè)需求點(diǎn)，第i個(gè)需求點(diǎn)P的坐標(biāo)為(a道路網(wǎng)與坐標(biāo)軸平行，彼此正交?，F(xiàn)打算建一個(gè)該物品的供應(yīng)中心，且由于受到城市某些條件的限制，該供應(yīng)中心只能設(shè)在界于[5,8]，y界于[5,8]的范圍內(nèi)。問該中心應(yīng)建在何處為好？P點(diǎn)的坐標(biāo)為：i

bi：2i解設(shè)供應(yīng)中心的位置為(x,由于此處應(yīng)采用沿道路行走的距離，可知用戶P到該中心的距離為：|xa||yb|從而可得目標(biāo)函數(shù)如下：minmax|xa||yb|x,y1im創(chuàng)建目標(biāo)函數(shù)（文件名為example8_7_3a.m）：functionf=example11_3_3a(x)a=[1435912620178]';b=[2108181451089]';f=abs(x(1)-a)+abs(x(2)-b);end輸入初值，調(diào)用fminimax函數(shù)進(jìn)行計(jì)算：x0=[7;7];lb=[5;5];ub=[8;8];[x,fval,maxfval]=fminimax(@example8_7_3a,x0,[],[],[],[],lb,ub)運(yùn)行結(jié)果：x=88fval=1365138

-23-

多目標(biāo)決策

xbA和ceq(x)可以是非線性

A多目標(biāo)決策

xbA和ceq(x)可以是非線性

Axb。c(x)

weightgoalbeqlbubAeq0ceq(x)0AxbAeqxbeqlbxub51491maxfval=14.0000（最小的最大距離）

8.8

前面介紹的規(guī)劃問題只有一個(gè)目標(biāo)函數(shù)，是單目標(biāo)最優(yōu)化問題。但是，在許多實(shí)際工程問題中，往往希望多個(gè)指標(biāo)都達(dá)到最優(yōu)值，所以就有多個(gè)目標(biāo)函數(shù)。這種問題稱為多目標(biāo)規(guī)劃問題。多目標(biāo)規(guī)劃有權(quán)和法、約束法、目標(biāo)達(dá)到法和改進(jìn)的目標(biāo)達(dá)到法等多種解法。

8.8.1有關(guān)函數(shù)介紹

利用fgoalattain函數(shù)求解多目標(biāo)達(dá)到問題。假設(shè)多目標(biāo)達(dá)到問題的數(shù)學(xué)模型為minx,F(x)weightgoal

式中,,,,,和為矢量，和為矩陣，c(x),ceq(x)和F(x)為函數(shù)，返回矢量。F(x),c(x)函數(shù)。fgoalattain函數(shù)的調(diào)用格式如下。●x=fgoalattain(fun,x0,goal,weight)：試圖通過變化x來使目標(biāo)函數(shù)fun達(dá)到goal指定的目標(biāo)。初值為x0，weight參數(shù)指定權(quán)重?！駒=fgoalattain(fun,x0,goal,weight,A,b)：求解目標(biāo)達(dá)到問題，約束條件為線性不等式●x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq)：求解目標(biāo)達(dá)到問題，除提

-24-

beq

xbeq

xub

c(x)ceq(x)0和ceq(x)0。若不存在邊界，則設(shè)

c(x)0函數(shù)是一個(gè)包含函數(shù)名的字符串，該函數(shù)可以是M文件、時(shí)，設(shè)置A=[],b=[]?！駒=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)：為設(shè)計(jì)變量x定義下界lb和上界ub集合，這樣始終有l(wèi)b?！駒=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)：將目標(biāo)達(dá)到問題歸結(jié)為nonlcon參數(shù)定義的非線性不等式或非線性等式。fgoalattain函數(shù)優(yōu)化的約束條件為c(x)置lb=[]和（或）ub=[]。●x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,┅,options)：用options中設(shè)置的優(yōu)化參數(shù)進(jìn)行最小化?！駒=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,┅,options,P1，P2,┅)：將問題參數(shù)P1,P2等直接傳遞給函數(shù)fun和nonlcon。如果不需要變量A,b,Aeq,beq,lb,ub,nonlcon和options，則將它們設(shè)置為空矩陣?！馵x,fval]=fgoalattain(…)：返回解x處的目標(biāo)函數(shù)值?！馵x,fval,attainfactor]=fgoalattain(…)：返回解x處的目標(biāo)達(dá)到因子。●[x,fval,attainfactor,exitflag]=fgoalattain(…)：返回exitflag參數(shù)，描述計(jì)算的退出條件?！馵x,fval,attainfactor,exitflag,output]=fgoalattain(…)：返回包含優(yōu)化信息的輸出參數(shù)output?！馵x,fval,attainfactor,exitflag,output,lambda]=fgoalattain(…)：返回包含拉格朗日乘子的lambda參數(shù)。各調(diào)用格式中，goal變量為目標(biāo)希望達(dá)到的矢量值。矢量的長度與fun函數(shù)返回的目標(biāo)函數(shù)F長度相等。fgoalattain函數(shù)試圖通過使矢量F的值最小化來達(dá)到goal參數(shù)給定的目標(biāo)。nonlcon參數(shù)計(jì)算非線性不等式約束和非線性等式約束ceq(x)0。nonlcon內(nèi)部函數(shù)或MEX文件。nonlcon函數(shù)需要輸入矢量x，返回兩個(gè)變量──x處的非線性不等式矢量c和x處的非線性等式矢量ceq。例如，若nonlcon=’mycon’，則M文件的形式如下：function[c,ceq]=mycon(x)c=┅%計(jì)算x處的非線性不等式ceq=┅%計(jì)算x處的非線性等式若約束函數(shù)的梯度可以計(jì)算，且options.GradConstr設(shè)為’on’，即options=optimset(‘GradConstr’,’on’)則函數(shù)nonlcon也必須在第3個(gè)和第4個(gè)輸出變量中輸出c(x)的梯度Gc和ceq(x)的梯度Gceq。注意，可以通過核對nargout參數(shù)來避免計(jì)算Gc和Gceq。

-25-

nm的矩陣，其中Gc(i,j)是p若nonlconm的矩陣，其中Gc(i,j)是p若nonlcon函數(shù)返回m維的矢量c和長度為n的x，則c(x)的梯度Gc是一c=┅%計(jì)算x處的非線性不等式ceq=┅%計(jì)算x處的非線性等式ifnargout>2%被調(diào)用的nonlcon函數(shù)，有4個(gè)輸出。Gc=%不等式的梯度Gceq=%等式的梯度end

個(gè)c(j)對x(i)的偏導(dǎo)數(shù)。同樣ceq是一個(gè)p維矢量，則ceq(x)的梯度Gceq是一個(gè)n的矩陣，其中