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

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

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

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

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

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