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

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

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

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

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

充分條件：對于極小點(diǎn)：且對于極大點(diǎn)：且13第13頁，課件共22頁，創(chuàng)作于2023年2月多元函數(shù)極值點(diǎn)存在的條件對于無約束多元函數(shù)，其極值點(diǎn)存在的必要條件和充分條件，與一元函數(shù)極值點(diǎn)的相應(yīng)條件類似。1.必要條件下述定理1給出了n元實函數(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頁，創(chuàng)作于2023年2月多元函數(shù)極值點(diǎn)存在的條件函數(shù)f(X)的梯度▽f(X)有兩個十分重要的性質(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頁，創(chuàng)作于2023年2月二次型二次型是X=(x1,x2,…，xn)T的二次齊次函數(shù)：式中，aij=aji，A為n×n對稱矩陣。若A的所有元素都是實數(shù)，則稱上述二次型為實二次型。一個二次型惟一對應(yīng)一個對稱矩陣A；反之，一個對稱矩陣A也惟一確定一個二次型。16第16頁，課件共22頁，創(chuàng)作于2023年2月若對任意X≠0(即X的元素不全等于零)，實二次型f(X)=XTAX總為正，則稱該二次型是正定的。若對任意X≠0，實二次型f(X)=XTAX總為負(fù)，則稱該二次型是負(fù)定的。若對某些X≠0，實二次型f(X)=XTAX＞0；而對另一些X≠0，實二次型f(X)=XTAX＜0，即它既非正定，又非負(fù)定，則稱它是不定的。若對任意X≠0，總有f(X)=XTAX≥0，即對某些X≠0，f(X)=XTAX＞0，對另外一些X≠0，f(X)=XTAX=0，則稱該實二次型半正定。類似地，若對任意X≠0，總有f(X)=XTAX≤0，則稱其為半負(fù)定。如果實二次型XTAX為正定、負(fù)定、不定、半正定或半負(fù)定，則稱它的對稱矩陣A分別為正定、負(fù)定、不定、半正定或半負(fù)定。幾個定義17第17頁，課件共22頁，創(chuàng)作于2023年2月實二次型XTAX為正定的充要條件是，它的矩陣A的左上角順序各階主子式都大于零，即18第18頁，課件共22頁，創(chuàng)作于2023年2月實二次型XTAX為負(fù)定的充要條件是，它的矩陣A的左上角順序各階主子式負(fù)、正相間，即19第19頁，課件共22頁