李　杰　劉兆鵬　費(fèi)時(shí)龍　蘇　婷

（宿州學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院　安徽宿州　234000）

非線性規(guī)劃約束問(wèn)題求解方法及其應(yīng)用

李杰劉兆鵬費(fèi)時(shí)龍?zhí)K婷

（宿州學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院安徽宿州234000）

非線性規(guī)劃于20世紀(jì)50年代形成，近幾十年里迅速發(fā)展，已經(jīng)在經(jīng)濟(jì)、軍事及工程等領(lǐng)域有著廣泛的應(yīng)用。文章一方面，簡(jiǎn)要介紹了非線性規(guī)劃的概念及非線性規(guī)劃的模型相關(guān)概念；另一方面，研究了非線性規(guī)劃約束極值問(wèn)題常見(jiàn)的求解方法Lagrange乘數(shù)法與可行方向法具體的運(yùn)算方法與步驟，并通過(guò)具體的實(shí)例闡述論證。

非線性規(guī)劃；模型；方法；極值

一、非線性規(guī)劃的數(shù)學(xué)模型

如果目標(biāo)函數(shù)[1]或者約束條件中含有非線性函數(shù)則稱為非線性規(guī)劃問(wèn)題，非線性規(guī)劃的數(shù)學(xué)模型[2]如下：

其中：x=(x1,x2,x3,……xn）是一個(gè)n維向量。

由于hk(x)=0等價(jià)于：

若把可行解區(qū)域[3]記為：Ω={x|gi(x)≥0,i=1,2,……m}則非線性規(guī)劃[4]問(wèn)題又簡(jiǎn)記為：minz=f(x),x∈Ω

Ω={x|gi(x)≥0,i=1,2,……m}與z=f(x)分別為非線性規(guī)劃問(wèn)題的可行解集和目標(biāo)函數(shù)。非線性規(guī)劃約束極值問(wèn)題的一般定義為：

函數(shù)f(x)或g(x)至少有一個(gè)非線性的，f(x)與g(x)是連續(xù)且可微函數(shù)。

二、非線性規(guī)劃約束極值求解方法及其應(yīng)用

（一）Lagrange乘數(shù)法。當(dāng)z=f(x,y)與φ(x，y)都可微，且φy(x0，y0)≠0知：在(x0,y0)處，φ(x，y)=0確定了唯一的單值函數(shù)y= φ(x)，

將λ帶入上式，得：fx(x0,y0)+λΦx(x0，y0)=0

則在φ(x,y)=0的前提條件下，目標(biāo)函數(shù)[5]z=f(x,y)在點(diǎn)(x0, y0)有極值的必要條件為x0,y0,λ滿足方程組：

或者記為：F(x,y,λ)=f(x,y)+λφy(x,y)（λ為L(zhǎng)agrange乘數(shù)）

n元函數(shù)的極值問(wèn)題為：Min（或Max） f(x)

它的Lagrange函數(shù)[6]為：

例1用Lagrange乘數(shù)法求解下述問(wèn)題

解：令F(x,y,λ)=x+y+λ(x2+y2-1)，x,y,λ滿足方程組

（二）可行方向法。若x(k)是非線性規(guī)劃{minf(x);gi(x)≥0, i=1,2，……，l}的一個(gè)可行解，并且不是極小點(diǎn)。為了求它的極小點(diǎn)或近似極小點(diǎn)，要在x(k)點(diǎn)的可行下降方向選取一方向D(k)及確定步長(zhǎng)λk，使（R代表可行域）且f(x(k+1))＜f(x(k))，當(dāng)滿足精度要求時(shí)，終止迭代，得到的點(diǎn)x(k+1)就是所求的極小點(diǎn)；否則，從(x(k+1)開(kāi)始繼續(xù)迭代，到滿足精度要求結(jié)束，稱此方法為可行方向法。

若x(k)點(diǎn)的有效約束集[7]非空，利用下述不等式組來(lái)確定x(k)點(diǎn)的可行下降方向D。

相當(dāng)于利用下述不等式組求向量D和實(shí)數(shù)

使▽f(x(k))TD和▽-gj(x(k))TD（對(duì)于所有的j∈J)的最大值η極小化（同時(shí)限制向量D的模），則將上述問(wèn)題轉(zhuǎn)化為求解線性規(guī)劃問(wèn)題。

式中di（i=1,2,……,n）是向量D的各個(gè)分量。將式（1）所有的線性規(guī)劃的最優(yōu)解記為（D(k),ηk），若ηk=0，則在x(k)點(diǎn)沒(méi)有可行下降方向，在▽gi(x(k)),(?j∈J)線性獨(dú)立的條件下，x(k)點(diǎn)是一個(gè)K-T點(diǎn)。若ηk＜0，則得到x(k)點(diǎn)所要的搜索方向D(k)。

解取初始點(diǎn) x(0)=(0,0)T，則有 f(x(0))=8．因?yàn)楱宖(x)=，所以.因?yàn)間i(x(0))=4＞0，所以約束條件gi(x)=4-x1-2x2≥0不是初始點(diǎn)x(0)的有效約束．取D(0)=-▽f(x(0))= (4,4)T，從而

令gi(x(1))=4-12λ=0，可得．而f(x(1))=32λ2-32λ+8

為了便于求解，令y1=d1+1，y2=d2+1,y3=-η于是min(-y3);

現(xiàn)暫時(shí)用此步長(zhǎng)計(jì)算x(2)，有x(2)=(1.467,1.239)T．由于g1(x(2))=0.055＞0，則x(2)是可行點(diǎn)，λ=0.134是可行的．繼續(xù)迭代[8]下去，求得最優(yōu)解x*=(1.6,1.2)T，最優(yōu)值f(x(*))=0.8。

三、結(jié)語(yǔ)

求解非線性規(guī)劃問(wèn)題比求解線性規(guī)劃問(wèn)題復(fù)雜，因?yàn)榍蠼夥蔷€性規(guī)劃問(wèn)題沒(méi)有一種通用的方法，而求解線性規(guī)劃問(wèn)題有一種通用的方法（單純形法）。本文研究了求解非線性規(guī)劃約束問(wèn)題的幾種典型方法Lagrange乘數(shù)法與可行方向法，當(dāng)然解決非線性規(guī)劃求解問(wèn)題的方法還有很多，如將約束問(wèn)題化為無(wú)約束問(wèn)題的罰函數(shù)法。隨著社會(huì)的不斷發(fā)展，新的問(wèn)題也不斷出現(xiàn)，這要求我們?cè)谑煜鹘y(tǒng)解法的基礎(chǔ)上開(kāi)創(chuàng)新的解法。

[1]呂鵬，潘志.運(yùn)籌學(xué)（數(shù)學(xué)規(guī)劃篇）[M].北京:清華大學(xué)出版社；北京交通大學(xué)出版社，2011:100-150.

[2]希利爾，利伯曼.胡運(yùn)權(quán)等譯.運(yùn)籌學(xué)導(dǎo)論（第九版）[M].北京:清華大學(xué)出版社，2010:85-86.

[3]馬超群，蘭秋軍.運(yùn)籌學(xué)[M].長(zhǎng)沙:湖南大學(xué)出版社，2008:300-305.

[4]謝政，李建平.非線性最優(yōu)化理論與方法[M].北京:高等教育出版社，2010:309-314.

[5]王宜舉，修乃華.非線性最優(yōu)化理論與方法[M].北京:科學(xué)出版社，2012:49-68.

[6]袁亞湘.非線性優(yōu)化計(jì)算方法[M].北京:科學(xué)出版社，2008:201-210.

[7]大學(xué)數(shù)學(xué)編寫(xiě)委員會(huì)編寫(xiě)組.運(yùn)籌學(xué)[M].北京:高等教育出版社，2011:118-209.

[8]HamdyA.Taha.運(yùn)籌學(xué)導(dǎo)論（第八版）[M].薛毅,劉德剛等譯.北京:人民郵電出版社，2008:678-685.

[責(zé)任編輯鄭麗娟]

O222.4

A

2095-0438（2016）11-0142-03

2016-05-07

李杰（1983-），男，安徽六安人，宿州學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院助教，碩士，研究方向：概率統(tǒng)計(jì)。

安徽省高校創(chuàng)新訓(xùn)練項(xiàng)目（AH201410379077)；安徽省高校自然科學(xué)研究項(xiàng)目(KJ2016A770)；安徽省高校優(yōu)秀青年人才支持計(jì)劃重點(diǎn)項(xiàng)目(gxyqZD2016340)。