第九講非線性規(guī)劃基本概念

第九講非線性規(guī)劃基本概念1第1頁，共22頁，2023年，2月20日，星期一引言在科學(xué)管理和其他領(lǐng)域中，很多實(shí)際問題可歸結(jié)為線性規(guī)劃問題。但也有很多問題，其目標(biāo)函數(shù)和(或)約束條件很難用線性函數(shù)表達(dá)。如果目標(biāo)函數(shù)或約束條件中含有非線性函數(shù)，就稱這種問題為非線性規(guī)劃問題。解這類問題需要用非線性規(guī)劃方法。目前，非線性規(guī)劃已成為運(yùn)籌學(xué)一個(gè)重要分支，在最優(yōu)設(shè)計(jì)、管理科學(xué)、系統(tǒng)控制等許多領(lǐng)域得到越來越廣泛的應(yīng)用。一般說來，由于非線性函數(shù)的復(fù)雜性，解非線性規(guī)劃問題要比解線性規(guī)劃問題困難得多。而且，也不像線性規(guī)劃那樣有單純形法等通用方法。非線性規(guī)劃目前還沒有適于各種問題的一般性算法，各個(gè)方法都有自己特定的適用范圍。2第2頁，共22頁，2023年，2月20日，星期一基本概念－問題的提出例1

某公司經(jīng)營兩種產(chǎn)品，第一種產(chǎn)品每件售價(jià)30元，第二種產(chǎn)品每件售價(jià)450元。根據(jù)統(tǒng)計(jì)，售出一件第一種產(chǎn)品所需要的服務(wù)時(shí)間平均是0.5小時(shí)，第二種產(chǎn)品是(2+0.25x2)小時(shí)，其中x2是第二種產(chǎn)品的售出數(shù)量。已知該公司在這段時(shí)間內(nèi)的總服務(wù)時(shí)間為800小時(shí)，試決定使其營業(yè)額最大的營業(yè)計(jì)劃。設(shè)該公司計(jì)劃經(jīng)營第一種產(chǎn)品x1件，第二種產(chǎn)品x2件。根據(jù)題，其營業(yè)額為由于服務(wù)時(shí)間的限制，該計(jì)劃必須滿足此外，這個(gè)問題還應(yīng)滿足

，得到本問題數(shù)學(xué)模型為：3第3頁，共22頁，2023年，2月20日，星期一非線性規(guī)劃問題的數(shù)學(xué)模型非線性規(guī)劃的數(shù)學(xué)模型常表示成以下形式其中自變量是n維歐氏空間中的向量(點(diǎn))；為目標(biāo)函數(shù)，和為約束條件。

4第4頁，共22頁，2023年，2月20日，星期一由于當(dāng)需使目標(biāo)函數(shù)極大化時(shí)，只需使其負(fù)值極小化即可。因而僅考慮目標(biāo)函數(shù)極小化，這無損于一般性。若某約束條件是“≤”不等式時(shí)，僅需用“-1”乘該約束的兩端，即可將這個(gè)約束變?yōu)椤啊荨钡男问?。由于等式約束等價(jià)于下述兩個(gè)不等式約束：因而，也可將非線性規(guī)劃的數(shù)學(xué)模型寫成以下形式數(shù)學(xué)模型5第5頁，共22頁，2023年，2月20日，星期一圖解法例1：用圖解法求解非線性規(guī)劃6第6頁，共22頁，2023年，2月20日，星期一在x1Ox2坐標(biāo)平面上畫出目標(biāo)函數(shù)的等值線，它是以點(diǎn)(2，1)為圓心的同心圓。1x1x112354O0解題步驟7第7頁，共22頁，2023年，2月20日，星期一二維問題的圖解根據(jù)約束條件畫出可行域，它是拋物線段ABCD1x1x112354O0ABCD分析：令動點(diǎn)從A出發(fā)沿拋物線ABCD移動，當(dāng)動點(diǎn)從A移向B時(shí)，目標(biāo)函數(shù)值下降；當(dāng)動點(diǎn)由B移向C時(shí)，目標(biāo)函數(shù)值上升。從而可知，在可行域AC這一范圍內(nèi)，B點(diǎn)的目標(biāo)函數(shù)值f(B)最小，因而點(diǎn)B是一個(gè)極小點(diǎn)。當(dāng)動點(diǎn)由C向D移動時(shí)，目標(biāo)函數(shù)值再次下降，在D點(diǎn)(其坐標(biāo)為(4，1))目標(biāo)函數(shù)值最小。8第8頁，共22頁，2023年，2月20日，星期一練習(xí)：圖解法求解非線性規(guī)劃最優(yōu)解：x1*=x2*=3，目標(biāo)函數(shù)值：f(X*)=2。9第9頁，共22頁，2023年，2月20日，星期一作業(yè)：用圖解法求解10第10頁，共22頁，2023年，2月20日，星期一在例1中，目標(biāo)函數(shù)值f(B)僅是目標(biāo)函數(shù)f(X)在一部分可行域上的極小值，而不是在整個(gè)可行域上的極小值，這樣的極小值稱為局部極小值(或相對極小值)。像B這樣的點(diǎn)稱為局部極小點(diǎn)(或相對極小點(diǎn))。f(D)是整個(gè)可行域上的極小值，稱全局極小值(最小值)，或絕對極小值；像D這樣的點(diǎn)稱全局極小點(diǎn)(最小點(diǎn))，或絕對極小點(diǎn)。全局極小點(diǎn)當(dāng)然也是局部極小點(diǎn)，但局部極小點(diǎn)不一定是全局極小點(diǎn)。1x1x112354O0ABCD11第11頁，共22頁，2023年，2月20日，星期一局部極?。喝謽O?。涸O(shè)f(X)為定義在En的某一區(qū)域R上的n元實(shí)函數(shù)，若存在X*∈R，對所有X∈R都有f(X)≥f(X*)，則稱X*為f(X)在R上的全局極小點(diǎn)，f(X*)為全局極小值。若對于所有X∈R且X≠X*，都有f(X)＞f(X*)，則稱X*為f(X)在R上的嚴(yán)格全局極小點(diǎn)，f(X*)為嚴(yán)格全局極小值。設(shè)f(X)為定義在n維歐氏空間En的某一區(qū)域R上的n元實(shí)函數(shù)(可記為f(X):REn→E1)，對于X*∈R，如果存在某個(gè)ε＞0，使所有與X*的距離小于ε的X∈R(即X∈R且‖X?X*‖＜ε)，都有f(X)≥f(X*)，則稱X*為f(X)在R上的局部極小點(diǎn)，f(X*)為局部極小值。若對于所有X≠X*且與X*的距離小于ε的X∈R，都有f(X)＞f(X*)，則稱X*為f(X)在R上的嚴(yán)格局部極小點(diǎn)，f(X*)為嚴(yán)格局部極小值。12第12頁，共22頁，2023年，2月20日，星期一一元函數(shù)極值點(diǎn)存在的條件二階可微的一元函數(shù)f(x)極值點(diǎn)存在的條件如下：必要條件：

充分條件：對于極小點(diǎn)：且對于極大點(diǎn)：且13第13頁，共22頁，2023年，2月20日，星期一多元函數(shù)極值點(diǎn)存在的條件對于無約束多元函數(shù)，其極值點(diǎn)存在的必要條件和充分條件，與一元函數(shù)極值點(diǎn)的相應(yīng)條件類似。1.必要條件下述定理1給出了n元實(shí)函數(shù)f(X)在X*點(diǎn)取得極值的必要條件。設(shè)R是n維歐氏空間En上的某一開集，f(X)在R上有連續(xù)一階偏導(dǎo)數(shù)，且在點(diǎn)X*∈R取得局部極值，則必有或?qū)懗桑浩渲?，為函?shù)f(X)在點(diǎn)X*處的梯度。定理114第14頁，共22頁，2023年，2月20日，星期一多元函數(shù)極值點(diǎn)存在的條件函數(shù)f(X)的梯度▽f(X)有兩個(gè)十分重要的性質(zhì)：(1)函數(shù)f(X)在某點(diǎn)X0的梯度▽f(X0)必與函數(shù)過該點(diǎn)的等值面(或等值線)正交(設(shè)▽f(X0)不為零)；(2)梯度向量的方向是函數(shù)值(在該點(diǎn)處)增加最快的方向，而負(fù)梯度方向則是函數(shù)值(在該點(diǎn)處)減少最快的方向。15第15頁，共22頁，2023年，2月20日，星期一二次型二次型是X=(x1,x2,…，xn)T的二次齊次函數(shù)：式中，aij=aji，A為n×n對稱矩陣。若A的所有元素都是實(shí)數(shù)，則稱上述二次型為實(shí)二次型。一個(gè)二次型惟一對應(yīng)一個(gè)對稱矩陣A；反之，一個(gè)對稱矩陣A也惟一確定一個(gè)二次型。16第16頁，共22頁，2023年，2月20日，星期一若對任意X≠0(即X的元素不全等于零)，實(shí)二次型f(X)=XTAX總為正，則稱該二次型是正定的。若對任意X≠0，實(shí)二次型f(X)=XTAX總為負(fù)，則稱該二次型是負(fù)定的。若對某些X≠0，實(shí)二次型f(X)=XTAX＞0；而對另一些X≠0，實(shí)二次型f(X)=XTAX＜0，即它既非正定，又非負(fù)定，則稱它是不定的。若對任意X≠0，總有f(X)=XTAX≥0，即對某些X≠0，f(X)=XTAX＞0，對另外一些X≠0，f(X)=XTAX=0，則稱該實(shí)二次型半正定。類似地，若對任意X≠0，總有f(X)=XTAX≤0，則稱其為半負(fù)定。如果實(shí)二次型XTAX為正定、負(fù)定、不定、半正定或半負(fù)定，則稱它的對稱矩陣A分別為正定、負(fù)定、不定、半正定或半負(fù)定。幾個(gè)定義17第17頁，共22頁，2023年，2月20日，星期一實(shí)二次型XTAX為正定的充要條件是，它的矩陣A的左上角順序各階主子式都大于零，即18第18頁，共22頁，2023年，2月20日，星期一實(shí)二次型XTAX為負(fù)定的充要條件是，它的矩陣A的左上角順序各階主子式負(fù)、正相間，即19第19頁，共22頁，2023年，2月20