生產(chǎn)運(yùn)籌--非線性規(guī)劃的基本概念(已修改)
2025-03-03 12:17 本頁(yè)面
【正文】 第五講 非線性規(guī)劃的基本概念 ? 非 線性規(guī)劃問(wèn)題 ? 非 線性規(guī)劃數(shù)學(xué)模型 ? 非線性規(guī)劃的圖解法 ? 梯度、 Hesse矩陣、 Jacobi陣 ? 凸函數(shù)和凸規(guī)劃 ? 解非線性規(guī)劃方法概述 ? 一維最優(yōu)化 在科學(xué)管理和其他領(lǐng)域中，大量應(yīng)用問(wèn)題可以歸結(jié)為線性規(guī)劃問(wèn)題，但是，也有另外許多問(wèn)題，其目標(biāo)函數(shù)和（或）約束條件很難用線性函數(shù)表達(dá)。如果目標(biāo)函數(shù)和（或）約束條件中包含有自變量的非線性函數(shù)，則這樣的規(guī)劃問(wèn)題就屬于非線性規(guī)劃。 非線性規(guī)劃是運(yùn)籌學(xué)的重要分支之一。最近 30多年來(lái)發(fā)展很快，不斷提出各種算法，而其應(yīng)用范圍也越來(lái)越廣泛。比如在各種預(yù)報(bào)、管理科學(xué)、最優(yōu)設(shè)計(jì)、質(zhì)量控制、系統(tǒng)控制等領(lǐng)域得到廣泛且不短深入的應(yīng)用。 一般來(lái)說(shuō)，求解非線性規(guī)劃問(wèn)題比線性規(guī)劃問(wèn)題困難得多。而且，也不象線性規(guī)劃那樣有單純形法這一通用的方法。非線性規(guī)劃的各種算法大都有自己特定的使用范圍，都有一定的局限性。到目前為止還沒(méi)有 適合于各種問(wèn)題的一般算法 ，這是需要深入研究的一個(gè)領(lǐng)域。我們只是對(duì)一些模型及應(yīng)用作簡(jiǎn)單介紹。 1 非線性規(guī)劃問(wèn)題舉例 例一：選 址問(wèn)題 設(shè)有 個(gè)市場(chǎng)，第 個(gè)市場(chǎng)位置為 ，它對(duì)某種貨物的需要 量為 ?，F(xiàn)計(jì)劃建立 個(gè)倉(cāng)庫(kù)，第 個(gè)倉(cāng)庫(kù)的存儲(chǔ) 容量為 試確定倉(cāng)庫(kù)的位置，使各倉(cāng)庫(kù)對(duì)各市場(chǎng)的 運(yùn)輸量與路程乘積之和為最小。 設(shè)第 個(gè)倉(cāng)庫(kù)的位置為 第 個(gè)倉(cāng)庫(kù)到第 個(gè)市場(chǎng)的貨物供應(yīng)量為 則第 個(gè) 倉(cāng)庫(kù)到第 個(gè)市場(chǎng)的距離為 jn ),( jj qp ),2,1( nb j ??mi ).,( mia ii ,2,1),( miyx ii ??i j ).,2,1,2,1( njmiz ij ?? ??ij ,)()( 22jijiij qypxd ???? ,)()(min 221 11 1jijiminjijijminjij qypxzdz ???? ? ?? ?? ?? ?目標(biāo)函數(shù)為 約束條件為 （ 1）每個(gè)倉(cāng)庫(kù)向各市場(chǎng)提供的貨物量之和不能超過(guò)它的存儲(chǔ)容量。 miaz injij ,2,1,1????? njbz jmiij ,2,1,1????? （ 2）每個(gè)市場(chǎng)從各倉(cāng)庫(kù)得到的貨物量之和應(yīng)等于它的需要量。 （ 3）運(yùn)輸量不能為負(fù)數(shù) njmiz ij ,2,1,2,1,0 ?? ??? 例 2. 木 梁設(shè)計(jì)問(wèn)題 把圓形木材加工成矩形橫截面的木梁，要求木梁高度 不超過(guò) ，橫截面的慣性矩（高度的平方 寬度）不小 于 ，而且高度介于寬度與 4倍寬度之間。問(wèn)如何確定木 梁尺寸可使木梁成本最小 . H ?W2x1x設(shè)矩形橫截面的高度為 ， 寬度為 ，則圓形木材的半徑 1x2x222122 ?????????????? xxr而木梁長(zhǎng)度無(wú)法改變，因此成本只與圓形 木材的橫截面積有關(guān)。 ,44min22212 ???????? ??? xxrs ??目標(biāo)函數(shù)為 約束條件為 )( .0,4 4( W)( )(2121212211高度與寬度非負(fù)倍寬度之間）高度介于寬度與慣性矩不小于高度不小于?????xxxxxxWxxHHx ?（ 1）數(shù)學(xué)規(guī)劃模型的一般形式： 其中 , 簡(jiǎn)記為 MP(Mathematical Programming) 2 非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型 ?????????qjxhpixgxfii,1 ,0)( ,1 ,0)( .)( min??的實(shí)值函數(shù)，為 xxhxgxfxxxx jiTn )(),(),(,),( 21 ?? ?（ 2）簡(jiǎn)記形式： Tp xgxgxg ))(,),(()( 1 ?? Tq xhxhxh ))(,),(()( 1 ??引入 向量函數(shù) 符號(hào)： ?????????qjxhpixgtsxfii,1 ,0)( ,1 ,0)( ..)( min?????????0)( 0)( ..)( minxhxgtsxfXxxf?)(min ?????? ?? ???? qjxh pixgRxX iin ,1,0)( ,1,0)( ?? ?（ 3）數(shù)學(xué)規(guī)劃問(wèn)題的分類(lèi)： ???????0)( 0)( .)( minxhxgxf?若 為線性函數(shù)，即為 線性規(guī)劃 (LP)； ?若 至少一個(gè)為非線性 , 即為 非線性規(guī)劃 (NLP)； ?對(duì)于非線性規(guī)劃， 若沒(méi)有 ,即 X=Rn,稱(chēng)為 無(wú)約束非線性規(guī)劃 或 無(wú)約束最優(yōu)化問(wèn)題 ； 否則稱(chēng)為 約束非線性規(guī)劃或約束最優(yōu)化問(wèn)題 。 ?（ 4）可行域和可行解： ????????????qjxhpixgRxXiin,1,0)(,1,0)(??稱(chēng) 為 MP問(wèn)題的 約束集 或 可行域 。 若 x在 X內(nèi)，稱(chēng) x為 MP的 可行解 或者 可行點(diǎn) 。 ?????????qjxhpixgtsxfii,1 ,0)( ,1 ,0)( ..)( min?? ?（ 5）最優(yōu)解和極小點(diǎn) 對(duì)于非線性規(guī)劃（ MP），若 ，并且有 Xx ?* Xxxfxf ??? ),()( * 極小值。）的整體最優(yōu)值或整體是（稱(chēng) MP)( *xf如果有 ** , ),()( xxXxxfxf ???? 嚴(yán)格整體極小點(diǎn)，）的嚴(yán)格整體最優(yōu)解或是（稱(chēng) MP*x 嚴(yán)格整體極小值。）的嚴(yán)格整體最優(yōu)值或是（稱(chēng) MP)( *xf定義 : 極小點(diǎn)，）的整體最優(yōu)解或整體是（則稱(chēng) MP*x ? ? 使的鄰域并且存在若）對(duì)于非線性規(guī)劃（ )( ,MP****?? ?????xxRxxNxXxn XxNxxfxf ?)()()( **???? ， 極小值）的局部最優(yōu)值或局部是（稱(chēng) MP)( *xf如果有 *** ,)()()( xxXxNxxfxf ???? ??，定義 嚴(yán)格局部極小點(diǎn)）的嚴(yán)格局部最優(yōu)解或是（稱(chēng) MP*x 嚴(yán)格局部極小值。）的嚴(yán)格局部最優(yōu)值或是（)( *xf則稱(chēng) x* 是 (MP)的 局部最優(yōu)解 或 局部極小解 , 例 1： 用圖解法求解 min f(x)=(x1－ 2)2 +(x2－ 2)2 . h(x)= x1 + x2 6 = 0 x1 x2 0 6 6 2 2 3 3 最優(yōu)解 x* = ( 3， 3 )T 可行解 x = ( ， )T 最優(yōu)級(jí)解即為最小圓的半徑： f(x)=(x1－ 2)2 +(x2－ 2)2 = 2 3 非線性規(guī)劃問(wèn)題的圖解法 對(duì)二維最優(yōu)化問(wèn)題，總可以用圖解法求解，而對(duì)三維或高維問(wèn)題，已不便在平面上作圖，此法失效。 x1 x2 0 6 6 2 2 D可行域 最優(yōu)解 x* = ( 2， 2 )T 例 2： 用圖解法求解 min f(x)=(x1 2)2 +(x2 2)2 . h(x)= x1 + x2 6 ≤ 0 3 非線性規(guī)劃問(wèn)題的圖解法 最優(yōu)級(jí)解即為最小圓的半徑： f(x)=(x1 2)2 +(x2 2)2 = 0 ? 解 ：①先畫(huà)出等式約束曲線 的圖形 —— 拋物線， ? ? ? ???????????????????0,0505.12)(min212122212221xxxxxxxtsxxxf05 2221 ??? xxxx1x2?12?34?5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1