非線性規(guī)劃的概念和原理

《非線性規(guī)劃的概念和原理》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第五章非線性規(guī)劃的概念和原理非線性規(guī)劃的理論是在線性規(guī)劃的基礎(chǔ)上發(fā)展起來(lái)的。1951年，庫(kù)恩（H.W.Kuhn）和塔克（A.W.Tucker）等人提出了非線性規(guī)劃的最優(yōu)性條件，為它的發(fā)展奠定了基礎(chǔ)。以后隨著電子計(jì)算機(jī)的普遍使用，非線性規(guī)劃的理論和方法有了很大的發(fā)展，其應(yīng)用的領(lǐng)域也越來(lái)越廣泛，特別是在軍事，經(jīng)濟(jì)，管理，生產(chǎn)過(guò)程自動(dòng)化，工程設(shè)計(jì)和產(chǎn)品優(yōu)化設(shè)計(jì)等方面都有著重要的應(yīng)用。一般來(lái)說(shuō)，解非線性規(guī)劃問題要比求解線性規(guī)劃問題困難得多，而且也不像線性規(guī)劃那樣有統(tǒng)一的數(shù)學(xué)模型及如單純形法這一通用解法。非線性規(guī)劃的各種算法大都有

2、自己特定的適用范圍。都有一定的局限性，到目前為止還沒有適合于各種非線性規(guī)劃問題的一般算法。這正是需要人們進(jìn)一步研究的課題。5.1非線性規(guī)劃的實(shí)例及數(shù)學(xué)模型[例題6.1]投資問題：假定國(guó)家的下一個(gè)五年計(jì)劃內(nèi)用于發(fā)展某種工業(yè)的總投資為b億元，可供選擇興建的項(xiàng)目共有幾個(gè)。已知第j個(gè)項(xiàng)目的投資為億元，可得收益為億元，問應(yīng)如何進(jìn)行投資，才能使盈利率（即單位投資可得到的收益）為最高？解：令決策變量為，則應(yīng)滿足條件同時(shí)應(yīng)滿足約束條件目標(biāo)函數(shù)是要求盈利率最大。[例題6.2]廠址選擇問題：設(shè)有n個(gè)市場(chǎng)，第j個(gè)市場(chǎng)位置為，它對(duì)某種貨物的需要

3、量為。現(xiàn)計(jì)劃建立m個(gè)倉(cāng)庫(kù)，第i個(gè)倉(cāng)庫(kù)的存儲(chǔ)容量為。試確定倉(cāng)庫(kù)的位置，使各倉(cāng)庫(kù)對(duì)各市場(chǎng)的運(yùn)輸量與路程乘積之和為最小。解：設(shè)第i個(gè)倉(cāng)庫(kù)的位置為，第i個(gè)倉(cāng)庫(kù)到第j個(gè)市場(chǎng)的貨物供應(yīng)量為，則第i個(gè)倉(cāng)庫(kù)到第j個(gè)市場(chǎng)的距離為目標(biāo)函數(shù)為約束條件為：（1）每個(gè)倉(cāng)庫(kù)向各市場(chǎng)提供的貨物量之和不能超過(guò)它的存儲(chǔ)容量；（2）每個(gè)市場(chǎng)從各倉(cāng)庫(kù)得到的貨物量之和應(yīng)等于它的需要量；（3）運(yùn)輸量不能為負(fù)數(shù)。因此，問題的數(shù)學(xué)模型為：s.t.,,,一般非線性規(guī)劃的數(shù)學(xué)模型可表示為：；s.t.,,式中是n維向量，，都是的映射（即自變量是n維向量，因變量是實(shí)數(shù)的函數(shù)

4、關(guān)系），且其中至少存在一個(gè)非線性映射。與線性規(guī)劃類似，把滿足約束條件的解稱為可行解。若記則稱為可行域。因此上述模型可簡(jiǎn)記為s.t.當(dāng)一個(gè)非線性規(guī)劃問題的自變量X沒有任何約束，或說(shuō)可行域即是整個(gè)n維向量空間,即，則稱這樣的非線性規(guī)劃問題為無(wú)約束問題：或有約束問題與無(wú)約束問題是非線性規(guī)劃的兩大類問題，它們?cè)谔幚矸椒ㄉ嫌忻黠@的不同。5.2無(wú)約束非線性規(guī)劃問題5.2.1無(wú)約束極值條件對(duì)于二階可微的一元函數(shù)，如果是局部極小點(diǎn)，則，并且；反之，如果，，則是局部極大點(diǎn)。關(guān)于多元函數(shù)，也有與此類似的結(jié)果，這就是下述的各定理?？紤]無(wú)約束極

5、值問題：，定理6.1（必要條件）設(shè)是n元可微實(shí)函數(shù)，如果是以上問題的局部極小解，則。定理6.2（充分條件）設(shè)是n元二次可微實(shí)函數(shù)，如果是上述問題的局部最小解，則，半正定；反之，如果在點(diǎn)有，正定，則為嚴(yán)格局部最小解。定理6.3設(shè)是n元可微凸函數(shù)，如果，則是上述問題的最小解。[例題6.3]試求二次函數(shù)的極小點(diǎn)。解：由極值存在的必要條件求出穩(wěn)定點(diǎn)：，，則由得，再用充分條件進(jìn)行檢驗(yàn)：，，，則由為正定矩陣得極小點(diǎn)為。5.2.3無(wú)約束極值問題的解法5.2.3.1梯度法（i）給定初始點(diǎn)，；（ii）計(jì)算和，若，迭代停止，得近似極小點(diǎn)和近

6、似極小值；否則，進(jìn)行下一步；（iii）做一維搜索或取作為近似最佳步長(zhǎng)，并計(jì)算，令，轉(zhuǎn)向第二步。[例題6.4]求解無(wú)約束極值問題解：取，，則，，，，故為極值點(diǎn)，極小值為。5.2.3.2牛頓法對(duì)正定二次函數(shù)，，其中A為n階方陣，B為n維列向量，c為常數(shù)，設(shè)為其極小點(diǎn)，則，所以；任給，，消去B，得所以，這說(shuō)明，從任意近似點(diǎn)出發(fā)，沿方向搜索，步長(zhǎng)為1，一步即可達(dá)極小點(diǎn)。[例題6.5]求解無(wú)約束極值問題解：任取，，，，由可知，確實(shí)為極小點(diǎn)。牛頓法與梯度法的搜索方向不同，優(yōu)點(diǎn)是收斂速度快，但有時(shí)不好用而需采取改進(jìn)措施，當(dāng)維數(shù)較高時(shí)，

7、的計(jì)算量很大。5.3約束非線性規(guī)劃問題前面我們介紹了無(wú)約束問題的最優(yōu)化方法，但實(shí)際問題中，大多數(shù)都是有約束條件的問題。求解帶有約束條件的問題比起無(wú)約束問題要困難得多，也復(fù)雜得多。在每次迭代時(shí)，不僅要使目標(biāo)函數(shù)值有所下降，而且要使迭代點(diǎn)都落在可行域內(nèi)（個(gè)別算法除外）。求解帶有約束的極值問題常用方法是：將約束問題化為一個(gè)或一系列的無(wú)約束極值問題；將非線性規(guī)劃化為近似的線性規(guī)劃；將復(fù)雜問題變?yōu)檩^簡(jiǎn)單問題等等。5.3.1凸規(guī)劃問題約束問題的情況較為復(fù)雜，先討論其中的一種較為特殊的情況，即凸規(guī)劃問題。一般來(lái)說(shuō)，非線性規(guī)劃的局部最優(yōu)

8、解和全局最優(yōu)解是不同的，但是，對(duì)凸規(guī)劃問題，局部最優(yōu)解就是全局最優(yōu)解。定義6.1設(shè)為定義在非空凸集上的實(shí)值函數(shù)，如果對(duì)于任意的兩點(diǎn)，和任意實(shí)數(shù)，恒有則稱為S上的凸函數(shù)。定理6.4設(shè)S是n維歐氏空間上的一個(gè)開凸集，是定義在S上的具有二階連續(xù)導(dǎo)數(shù)的函數(shù)，那么，在S上為凸函數(shù)的充要條件是：對(duì)所有，海賽矩陣都是半正定的；如果