生產(chǎn)運(yùn)籌--非線性規(guī)劃的基本概念 78頁.ppt

1、第五講 非線性規(guī)劃的基本概念,非線性規(guī)劃問題 非線性規(guī)劃數(shù)學(xué)模型 非線性規(guī)劃的圖解法 梯度、Hesse矩陣、Jacobi陣 凸函數(shù)和凸規(guī)劃 解非線性規(guī)劃方法概述 一維最優(yōu)化,在科學(xué)管理和其他領(lǐng)域中，大量應(yīng)用問題可以歸結(jié)為線性規(guī)劃問題，但是，也有另外許多問題，其目標(biāo)函數(shù)和（或）約束條件很難用線性函數(shù)表達(dá)。如果目標(biāo)函數(shù)和（或）約束條件中包含有自變量的非線性函數(shù)，則這樣的規(guī)劃問題就屬于非線性規(guī)劃。 非線性規(guī)劃是運(yùn)籌學(xué)的重要分支之一。最近30多年來發(fā)展很快，不斷提出各種算法，而其應(yīng)用范圍也越來越廣泛。比如在各種預(yù)報(bào)、管理科學(xué)、最優(yōu)設(shè)計(jì)、質(zhì)量控制、系統(tǒng)控制等領(lǐng)域得到廣泛且不短深入的應(yīng)用。 一般來說，求解

2、非線性規(guī)劃問題比線性規(guī)劃問題困難得多。而且，也不象線性規(guī)劃那樣有單純形法這一通用的方法。非線性規(guī)劃的各種算法大都有自己特定的使用范圍，都有一定的局限性。到目前為止還沒有適合于各種問題的一般算法，這是需要深入研究的一個(gè)領(lǐng)域。我們只是對一些模型及應(yīng)用作簡單介紹。,非線性規(guī)劃問題舉例 例一：選址問題 設(shè)有 個(gè)市場，第 個(gè)市場位置為 ，它對某種貨物的需要 量為 ?，F(xiàn)計(jì)劃建立 個(gè)倉庫，第 個(gè)倉庫的存儲 容量為 試確定倉庫的位置，使各倉庫對各市場的 運(yùn)輸量與路程乘積之和為最小。 設(shè)第 個(gè)倉庫的位置為 第 個(gè)倉庫到第 個(gè)市場的貨物供應(yīng)量為 則第 個(gè) 倉庫到第 個(gè)市場的距離為,目標(biāo)函數(shù)為,約束條件為 （1）每

3、個(gè)倉庫向各市場提供的貨物量之和不能超過它的存儲容量。,（2）每個(gè)市場從各倉庫得到的貨物量之和應(yīng)等于它的需要量。,（3）運(yùn)輸量不能為負(fù)數(shù),例2. 木梁設(shè)計(jì)問題 把圓形木材加工成矩形橫截面的木梁，要求木梁高度 不超過 ，橫截面的慣性矩（高度的平方 寬度）不小 于 ，而且高度介于寬度與4倍寬度之間。問如何確定木 梁尺寸可使木梁成本最小.,設(shè)矩形橫截面的高度為 ， 寬度為 ，則圓形木材的半徑,而木梁長度無法改變，因此成本只與圓形 木材的橫截面積有關(guān)。,目標(biāo)函數(shù)為,約束條件為,（1）數(shù)學(xué)規(guī)劃模型的一般形式：,其中,簡記為MP(Mathematical Programming),2 非線性規(guī)劃問題的數(shù)學(xué)模

4、型,（2）簡記形式：,引入向量函數(shù)符號：,（3）數(shù)學(xué)規(guī)劃問題的分類：,若 為線性函數(shù)，即為線性規(guī)劃(LP)；,若 至少一個(gè)為非線性, 即為非線性規(guī)劃(NLP)；,對于非線性規(guī)劃，若沒有 ,即X=Rn,稱為 無約束非線性規(guī)劃或無約束最優(yōu)化問題； 否則稱為約束非線性規(guī)劃或約束最優(yōu)化問題。,（4）可行域和可行解：,稱,為MP問題的約束集或可行域。,若x在X內(nèi)，稱x為MP的可行解或者可行點(diǎn)。,（5）最優(yōu)解和極小點(diǎn),對于非線性規(guī)劃（MP），若 ，并且有,如果有,定義:,如果有,定義,則稱 x* 是(MP)的局部最優(yōu)解或局部極小解,例1： 用圖解法求解 min f(x)=(x12)2 +(x22)2 s.

5、t. h(x)= x1 + x2 - 6 = 0,x1,x2,0,6,6,2,2,3,3,最優(yōu)解 x* = ( 3，3 )T,可行解 x = ( 1.5，4.5 )T,最優(yōu)級解即為最小圓的半徑： f(x)=(x12)2 +(x22)2 = 2,3 非線性規(guī)劃問題的圖解法,對二維最優(yōu)化問題，總可以用圖解法求解，而對三維或高維問題，已不便在平面上作圖，此法失效。,x1,x2,0,6,6,2,2,D可行域,最優(yōu)解 x* = ( 2，2 )T,例2： 用圖解法求解 min f(x)=(x1 - 2)2 +(x2 - 2)2 s.t. h(x)= x1 + x2 - 6 0,3 非線性規(guī)劃問題的圖解法,

6、最優(yōu)級解即為最小圓的半徑： f(x)=(x1 - 2)2 +(x2 - 2)2 = 0,解：先畫出等式約束曲線 的圖形拋物線，,例3：用圖解法求解,再畫出不等式約束區(qū)域，,最后畫出目標(biāo)函數(shù)等值線，,所以 最優(yōu)解 x*=(4,1), 最優(yōu)值 min f(x)=4.,4 梯度、Hesse矩陣、Jacobi陣,(1) 二次函數(shù),一般形式:,矩陣形式:,二次型:,矩陣A的正定性: 正定、半正定、負(fù)定、不定。,其中AAT。,二次型的正定性: 正定、半正定、負(fù)定、不定。,（2） 梯度,定義：f(x) 是定義在En上的可微函數(shù)。f(x) 的n個(gè)偏導(dǎo)數(shù)為分量的向量稱為f(x) 的梯度.,性質(zhì)：設(shè)f(x) 在定

7、義域內(nèi)有連續(xù)偏導(dǎo)數(shù)，即有連續(xù)梯度，則梯度有以下兩個(gè)重要性質(zhì)： 性質(zhì)一 函數(shù)在某點(diǎn)的梯度不為零，則該梯度方向必與過該點(diǎn)的等值面垂直; 性質(zhì)二 梯度方向是函數(shù)具有最大變化率的方向（負(fù)梯度方向也叫最速下降方向）。,解： 由于,例：試求目標(biāo)函數(shù) 在點(diǎn) x =0,1T 處的最速下降方向，并求沿這個(gè)方向移動(dòng)一個(gè)單位長度后新點(diǎn)的目標(biāo)函數(shù)值。,則函數(shù)在 x =0,1T 處的最速下降方向是,這個(gè)方向上的單位向量是：,解： 由于,例：試求目標(biāo)函數(shù) 在點(diǎn)x =0,1T 處的最速下降方向，并求沿這個(gè)方向移動(dòng)一個(gè)單位長度后新點(diǎn)的目標(biāo)函數(shù)值。,新點(diǎn)是：,函數(shù)值：,幾個(gè)常用的梯度公式：,（3）Hesse矩陣,多元函數(shù) f(

8、x) 關(guān)于x的二階導(dǎo)數(shù)，稱為 f(x)的Hesse矩陣.,當(dāng)f(x)的所有二階偏導(dǎo)數(shù)連續(xù)時(shí),即,Hesse矩陣是對稱的.,時(shí)，,幾個(gè)常用Hessian公式：,（4）Jacobi矩陣,向量變量值函數(shù)：,向量值函數(shù)g(x)在點(diǎn) x0處的Jacobi矩陣,向量變量值函數(shù)的導(dǎo)數(shù)：,(1)凸函數(shù)：,定義,5 凸函數(shù)和凸規(guī)劃,例：正定二次函數(shù),其中A是正定矩陣，,f(x)是凸函數(shù)。,參見P104例。,性質(zhì)1:,（2）凸函數(shù)的性質(zhì),性質(zhì)2:,是凸集。,證明:略.,定理1：（一階條件）,n=1時(shí)幾何意義：可微函數(shù)是凸的等價(jià)于切線不在函數(shù)圖像上方。,（3） 凸函數(shù)的判定,定理2：（二階條件）,（4）凸規(guī)劃的定義

9、及其性質(zhì)：,凸規(guī)劃定義：,凸規(guī)劃性質(zhì)：,凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。,凸規(guī)劃是以后重點(diǎn)討論的一類非線性規(guī)劃,線性函數(shù),（1）微分學(xué)方法的局限性：,實(shí)際的問題中，函數(shù)可能是不連續(xù)或者不可微的。 需要解復(fù)雜的方程組，而方程組到目前仍沒有有效的算法。 實(shí)際的問題可能含有不等式約束，微分學(xué)方法不易處理。,6 非線性規(guī)劃方法概述,（2）數(shù)值方法的基本思路：迭代,給定初始點(diǎn)x0,根據(jù)x0,依次迭代產(chǎn)生點(diǎn)列xk,xk的最后一點(diǎn)為最優(yōu)解,xk有限,xk無限,xk收斂于最優(yōu)解,迭代格式,xk,xk+1,稱pk為第k輪搜索方向，tk為第k輪沿pk方向的步長。,產(chǎn)生tk和pk的不同方法，形成了不同的算

10、法。,定義：特殊搜索方向下降方向,定義：特殊搜索方向可行下降方向,解非線性規(guī)劃問題，關(guān)鍵在于找到某個(gè)方向，使得在此方向上，目標(biāo)函數(shù)得到下降，同時(shí)還是可行方向。 這樣的方向稱為可行下降方向。,定義：算法收斂、下降迭代算法,集合S上的迭代算法：,（1）初始點(diǎn),；,（2）按照某種搜索方向pk產(chǎn)生下一個(gè)迭代點(diǎn),（i）如果點(diǎn)列,收斂于最優(yōu)解,，則稱此算法收斂。,（ii）如果,，則稱此算法為,下降迭代算法。,.,.,.,（3）下降迭代算法步驟,（1）給出初始點(diǎn),，令,；,（2）按照某種規(guī)則確定下降搜索方向,；,（3）按照某種規(guī)則確定搜索步長,，使得,；,（4）令,，,；,（5）判斷,是否滿足停止條件。是則

11、停止，否則轉(zhuǎn)第2步。,搜索步長確定方法：,稱,為最優(yōu)步長，且有對k的梯度,（4） 終止條件,（5）常用的收斂性判別準(zhǔn)則:,取其中之一,也可同時(shí)取(1)與(2);(1)與(3);或(1),(2)和(3)等。,（6）算法的收斂速度,則稱 的收斂階為 。,設(shè)算法所得的點(diǎn)列為,，如果,1.線性收斂（當(dāng)k充分大時(shí)）：,2.超線性收斂：,3.二階收斂： （*）式中 =2時(shí)成立。,（*）,單變量(一維)最優(yōu)化,一維最優(yōu)化問題 進(jìn)退法 黃金分割法 拋物線搜索法 三次插值法,下降迭代算法中最優(yōu)步長的確定,.,.,一維最優(yōu)化問題：,解析的方法（極值點(diǎn)的必要條件）,一、一維最優(yōu)化問題,1. 單峰函數(shù),定義：設(shè),是區(qū)

12、間,上的一元函數(shù)，,是,在,上的極小點(diǎn)，且對任意的,有,（a）當(dāng),時(shí)，,（b）當(dāng),.,.,.,.,.,則稱 是單峰函數(shù)。,.,.,性質(zhì)：通過計(jì)算區(qū)間 a, b 內(nèi)兩個(gè)不同點(diǎn)的函數(shù)值，就可以確定一個(gè)包含極小點(diǎn)的子區(qū)間。,.,.,.,.,.,2 搜索法求解：,或,基本過程： 給出a,b,使得x*在a,b中。a,b稱為搜索區(qū)間。 迭代縮短a,b的長度。 當(dāng)a,b的長度小于某個(gè)預(yù)設(shè)的值，或者導(dǎo)數(shù)的絕對值小于某個(gè)預(yù)設(shè)的正數(shù)，則迭代終止。,二進(jìn)退法,思想,從一點(diǎn)出發(fā),按一定的步長, 試圖確定出函數(shù)值呈現(xiàn)“高 - 低 - 高”的三點(diǎn)。一個(gè)方向不成功，就退回來，再沿相反方向?qū)ふ摇?進(jìn)退法的計(jì)算步驟,如何確定包

13、含極小點(diǎn)的一個(gè)區(qū)間？,例：,假定：已經(jīng)確定了單峰區(qū)間a,b,新搜索區(qū)間為a,x2,新搜索區(qū)間為x1,b,三. 黃金分割法（0.618法）,區(qū)間縮小比例的確定：,區(qū)間縮短比例為(x2-a)/(b-a),縮短比例為(b-x1)/(b-a),縮短比例 滿足： 每次插入搜索點(diǎn)使得兩個(gè)區(qū)間a,x2和x1,b相等； 每次迭代都以相等的比例縮小區(qū)間。,黃金分割法的計(jì)算公式的推導(dǎo)：,通過確定 的取值，使上一次迭代剩余的迭代點(diǎn)恰與下一次迭代的一個(gè)迭代點(diǎn)重合，從而減少算法的計(jì)算量。,同理可得。,3. 0.618法的算法步驟：,確定a,b,計(jì)算探索點(diǎn) x1=a+0.382(b-a) x2=a+0.618(b-a),

14、停止，輸出x1,以a,x2為新的搜索區(qū)間,停止，輸出x2,以x1,b為新的搜索區(qū)間,3. 0.618法的算法框圖：,黃金分割法的迭代效果： 第 k 次后迭代后所得區(qū)間長度為初始區(qū)間長度的,其它的試探點(diǎn)算法：Fibonacci算法。,例：,解：,1、第一輪： t1=1.146, t2=1.854,t200.5,2、第二輪： t2=1.146, t1=0.708,t20=1.1460.5,3、第三輪： t1=0.438, t2=0.708,b -t1=1.146-0.4380.5,4、第四輪： t2=0.876=(1.146-0.438), t1=0.708,b-t1=1.146-0.7080.5

15、,輸出：t*=t2=0.876為最優(yōu)解，最優(yōu)值為-0.0798,四 Fibonacci法,此法類似于0.618法，也是用于單峰函數(shù)。其計(jì)算過程也與0.618類似，第1次迭代計(jì)算兩個(gè)試探點(diǎn)，以后每次迭代只需新加一點(diǎn)，另一試探點(diǎn)取自上次的迭代點(diǎn)。此法與0.618法的主要差別為：區(qū)間長度的縮短比率不是常數(shù)，而是由Fibonacci 數(shù)確定；給出精度后，迭代次數(shù)可預(yù)先確定；適合于參數(shù)只能取整數(shù)值的情況。,定義 稱滿足條件 （i）F0 = F1 = 1； （ii） 的數(shù)列 Fn 為Fibonacci數(shù)列。,由定義推知Fibonacci數(shù)列的前10項(xiàng)為1,1,2,3,5,8,13,21,34,55,89。

16、通過求解遞推關(guān)系可求得該數(shù)列的通項(xiàng)為,在Fibonacci法中，第n次迭代的搜索區(qū)間的長度（記為 ）是上一次區(qū)間長度的 倍,所以要使在第n次迭代時(shí)搜索區(qū)間的長度不超過，只需,即可。因 是已知值，所以給出精度后利用（2.4）式可求得迭代次數(shù)。,Fibonacc法在迭代中計(jì)算試探點(diǎn)的公式為,即有,Fibonacci法,(1) 對初始區(qū)間 和精度0，求目標(biāo)函數(shù)值的計(jì)算次數(shù) n，使 置辨別常數(shù)0。計(jì)算試探點(diǎn) 計(jì)算函數(shù)值和 。置k =1。,（2） 若 ，則轉(zhuǎn)（3）； 若 ，則轉(zhuǎn)（4）。,（3）,（5） 置k= k+1，轉(zhuǎn)（2）。,（4）,（6）,思想,在極小點(diǎn)附近，用二次三項(xiàng)式,四. 拋物線（二次）插值

17、,即“兩頭大中間小”,如何計(jì)算函數(shù),令,拋物線插值算法步驟：,解出,思路：,五. 三次插值法,設(shè),令,則有,求解滿足,的極小點(diǎn),令,而,解方程（3），有兩種情況：,由（2）可知,極小點(diǎn)的計(jì)算公式：,令,算法步驟：,其它插值算法：,有理插值。,收斂速度：三次插值算法的收斂階為2。,六、MATLAB,單變量函數(shù)求最小值的標(biāo)準(zhǔn)形式為 s.t,函數(shù) fminbnd 格式 x = fminbnd(fun,x1,x2) %返回自變量x在區(qū)間 上函數(shù)fun取最小值時(shí)x值，fun為目標(biāo)函數(shù)的表達(dá)式字符串或MATLAB自定義函數(shù)的函數(shù)柄。 函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(shù)必須是

18、連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。,x = fminbnd(fun,x1,x2,options) % options為指定優(yōu)化參數(shù)選項(xiàng) x,fval = fminbnd() % fval為目標(biāo)函數(shù)的最小值 x,fval,exitflag = fminbnd() %xitflag為終止迭代的條件 x,fval,exitflag,output = fminbnd() % output為優(yōu)化信息 說明 若參數(shù)exitflag0，表示函數(shù)收斂于x，若exitflag=0，表示超過函數(shù)估計(jì)值或迭代的最大數(shù)字，exitflag0表示函數(shù)不收斂于x；若參數(shù)output=iterations表示迭代次數(shù)，output=funccount表示函數(shù)賦值次數(shù)，output=algorithm表示所使用的算法。,例1 計(jì)算下面函數(shù)在區(qū)間(0，1)內(nèi)的最小值。,解：x,fval,exitflag,output =fminbnd(x3+