生產(chǎn)運(yùn)籌非線性規(guī)劃的基本概念 二

第五講非線性規(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)用。

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

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

（1）數(shù)學(xué)規(guī)劃模型的一般形式：其中,簡(jiǎn)記為MP(MathematicalProgramming)2非線性規(guī)劃問題的數(shù)學(xué)模型（2）簡(jiǎn)記形式：引入向量函數(shù)符號(hào)：（3）數(shù)學(xué)規(guī)劃問題的分類：若為線性函數(shù)，即為線性規(guī)劃(LP)；若至少一個(gè)為非線性,即為非線性規(guī)劃(NLP)；對(duì)于非線性規(guī)劃，若沒有,即X=Rn,稱為

無約束非線性規(guī)劃或無約束最優(yōu)化問題；否則稱為約束非線性規(guī)劃或約束最優(yōu)化問題。（4）可行域和可行解：稱為MP問題的約束集或可行域。若x在X內(nèi)，稱x為MP的可行解或者可行點(diǎn)。（5）最最優(yōu)解和和極小點(diǎn)點(diǎn)對(duì)于非線性規(guī)劃（MP），若，并且有如果有定義:如果有定義則稱x*是(MP)的局部最優(yōu)優(yōu)解或局部極小小解,例1：用圖圖解法求求解minf(x)=(x1－2)2+(x2－2)2s.t.h(x)=x1+x2-6=0x1x20662233最優(yōu)解x*=(3，，3)T可行解x=(1.5，4.5)T最優(yōu)級(jí)解解即為最最小圓的的半徑：：f(x)=(x1－2)2+(x2－2)2=23非線線性規(guī)劃劃問題的的圖解法法對(duì)二維最最優(yōu)化問問題，總總可以用用圖解法法求解，，而對(duì)三三維或高高維問題題，已不不便在平平面上作作圖，此此法失效效。x1x206622D可行域最優(yōu)解x*=(2，，2)T例2：用圖解法法求解minf(x)=(x1-2)2+(x2-2)2s.t.h(x)=x1+x2-6≤03非線性性規(guī)劃問題的的圖解法最優(yōu)級(jí)解即為為最小圓的半半徑：f(x)=(x1-2)2+(x2-2)2=0解：①先畫出等等式約束曲線線的的圖形——拋拋物線，例3：用圖解法求求解②再畫出不等等式約束區(qū)域域，③最后畫出目目標(biāo)函數(shù)等值值線，所以最優(yōu)解x*=(4,1),最優(yōu)值值minf(x)=4.4梯度、Hesse矩矩陣、Jacobi陣(1)二二次函數(shù)一般形式:矩陣形式:二次型:矩陣A的正定性:正正定、半正定定、負(fù)定、不不定。其中A＝AT。二次型的正定性:正正定、半正定定、負(fù)定、不不定。（2）梯度度定義：f(x)是定義在在En上的可微函數(shù)數(shù)。f(x)的n個(gè)偏導(dǎo)數(shù)為分分量的向量稱稱為f(x)的梯度.性質(zhì)：設(shè)f(x)在定義域域內(nèi)有連續(xù)偏偏導(dǎo)數(shù)，即有有連續(xù)梯度，，則梯度有以以下兩個(gè)重要要性質(zhì)：性質(zhì)一函數(shù)在某點(diǎn)的的梯度不為零零，則該梯度度方向必與過過該點(diǎn)的等值值面垂直;性質(zhì)二梯度方向是函函數(shù)具有最大大變化率的方方向（負(fù)梯度度方向也叫最速下降方向向）。解：由于例：試求目標(biāo)函數(shù)數(shù)在在點(diǎn)點(diǎn)x=[0,1]T處的最速下降降方向，并求求沿這個(gè)方向向移動(dòng)一個(gè)單單位長(zhǎng)度后新新點(diǎn)的目標(biāo)函函數(shù)值。則函數(shù)在x=[0,1]T處的最速下降降方向是這個(gè)方向上的的單位向量是是：解：由于例：試求目標(biāo)函數(shù)數(shù)在在點(diǎn)x=[0,1]T處的最速下降降方向，并求求沿這個(gè)方向向移動(dòng)一個(gè)單單位長(zhǎng)度后新新點(diǎn)的目標(biāo)函函數(shù)值。新點(diǎn)是：函數(shù)值：幾個(gè)常用的梯梯度公式：（3）Hesse矩陣多元函數(shù)f(x)關(guān)于x的二階導(dǎo)數(shù)，，稱為f(x)的Hesse矩陣.當(dāng)f(x)的所有二階階偏導(dǎo)數(shù)連續(xù)續(xù)時(shí),即Hesse矩矩陣是對(duì)稱的的.時(shí)，幾個(gè)常用Hessian公式：（4）Jacobi矩陣向量變量值函函數(shù)：向量值函數(shù)g(x)在點(diǎn)x0處的Jacobi矩陣向量變量值函函數(shù)的導(dǎo)數(shù)：(1)凸函數(shù)數(shù)：定義5凸函數(shù)和和凸規(guī)劃例：正定二次次函數(shù)其中A是正定定矩陣，f(x)是凸函數(shù)。。參見P104例。性質(zhì)1:（2）凸函數(shù)數(shù)的性質(zhì)性質(zhì)2:是凸集。證明:略.定理1：（一一階條件）n=1時(shí)幾何何意義：可微微函數(shù)是凸的的等價(jià)于切線線不在函數(shù)圖圖像上方。（3）凸凸函數(shù)的判定定定理2：（二二階條件）（4）凸規(guī)劃劃的定義及其其性質(zhì)：凸規(guī)劃定義：：凸規(guī)劃性質(zhì)：：凸規(guī)劃的任一一局部最優(yōu)解解都是它的整整體最優(yōu)解。。凸規(guī)劃是以后后重點(diǎn)討論的的一類非線性性規(guī)劃凸函數(shù)線性函數(shù)（1）微分學(xué)學(xué)方法的局限限性：實(shí)際的問題中中，函數(shù)可能能是不連續(xù)或或者不可微的的。需要解復(fù)雜的的方程組，而而方程組到目目前仍沒有有有效的算法。。實(shí)際的問題可可能含有不等等式約束，微微分學(xué)方法不不易處理。6非線性性規(guī)劃方法概概述（2）數(shù)值方方法的基本思思路：迭代給定初始點(diǎn)x0根據(jù)x0,依次迭代產(chǎn)產(chǎn)生點(diǎn)列{xk}{xk}的最后一點(diǎn)點(diǎn)為最優(yōu)解{xk}有限{xk}無限{xk}收斂于最優(yōu)優(yōu)解迭代格式xkxk+1pk稱pk為第k輪搜索方向，tk為第k輪沿pk方向的步長(zhǎng)。產(chǎn)生tk和pk的不同方法，，形成了不同同的算法。定義：特殊搜索方方向——下降方向向定義：特殊搜索方向向——可行下降方向解非線性規(guī)劃劃問題，關(guān)鍵鍵在于找到某某個(gè)方向，使使得在此方向向上，目標(biāo)函函數(shù)得到下降降，同時(shí)還是是可行方向。。這樣的方向稱稱為可行下降方向向。定義：算法收收斂、下降迭迭代算法集合S上的迭迭代算法：（1）初始點(diǎn)點(diǎn)；（2）按照某某種搜索方向向pk產(chǎn)生下一個(gè)迭迭代點(diǎn)（i）如果點(diǎn)點(diǎn)列收斂于最優(yōu)解解，則稱此算法收斂。（ii）如果果，則稱此算法法為下降迭代算法法。...（3）下降迭迭代算法步驟驟（1）給出初初始點(diǎn)，令；（2）按照某某種規(guī)則確定定下降搜索方方向；（3）按照某某種規(guī)則確定定搜索步長(zhǎng)，使得；（4）令，；（5）判斷是否滿足停止條件。是則停止，，否則轉(zhuǎn)第2步。搜索步長(zhǎng)確定定方法：稱為最優(yōu)步長(zhǎng)，且有對(duì)k的梯度（4）終終止條件②④①③（5）常用的的收斂性判別別準(zhǔn)則:（１）點(diǎn)收斂準(zhǔn)則:(可取Rn中任一種模)。e￡--)1()(kkxx·（２）目標(biāo)函數(shù)值準(zhǔn)則：（絕對(duì)差）。e￡--)()()1()(kkffxx（３）目標(biāo)函數(shù)值準(zhǔn)則：（相對(duì)差）。e￡--)()()()()1()(kkkfffxxx取其中之一一,也可同同時(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)化一維最優(yōu)化化問題進(jìn)退法黃金分割法法拋物線搜索索法三次插值法法下降迭代算算法中最優(yōu)步長(zhǎng)長(zhǎng)的確定..一維最優(yōu)化化問題：解析的方法法（極值點(diǎn)的必必要條件））一、一維最最優(yōu)化問題題1.單單峰函數(shù)定義：設(shè)是區(qū)間上的一元函函數(shù)，是在上的極小點(diǎn)點(diǎn)，且對(duì)任任意的有（a）當(dāng)時(shí)，（b）當(dāng).....則稱是是單峰函數(shù)數(shù)。..性質(zhì)：通過計(jì)算算區(qū)間[a,b]內(nèi)兩個(gè)個(gè)不同點(diǎn)的的函數(shù)值，，就可以確確定一個(gè)包包含極小點(diǎn)點(diǎn)的子區(qū)間間。定理

設(shè)是區(qū)間上的一元函數(shù)，是在上的極小點(diǎn)。任取點(diǎn)則有（1）如果，則（2）如果則.....2搜索法法求解：或基本過程：：給出[a,b],使使得x*在[a,b]中。[a,b]稱為搜索區(qū)間。迭代縮短[a,b]的長(zhǎng)度。。當(dāng)[a,b]的長(zhǎng)度度小于某個(gè)個(gè)預(yù)設(shè)的值值，或者導(dǎo)導(dǎo)數(shù)的絕對(duì)對(duì)值小于某某個(gè)預(yù)設(shè)的的正數(shù)，則則迭代終止止。二．進(jìn)退法法思想從一點(diǎn)出發(fā)發(fā),按一定定的步長(zhǎng),試圖確確定出函數(shù)數(shù)值呈現(xiàn)““高-低低-高高”的三點(diǎn)。一一個(gè)方向不不成功，就就退回來，，再沿相反反方向?qū)ふ艺?。進(jìn)退法的計(jì)計(jì)算步驟如何確定包包含極小點(diǎn)點(diǎn)的一個(gè)區(qū)區(qū)間？例：假定定：：已已經(jīng)經(jīng)確確定定了了單單峰峰區(qū)區(qū)間間[a,b]x1x2ababx12新搜搜索索區(qū)區(qū)間間為為[a,x2]新搜搜索索區(qū)區(qū)間間為為[x1,b]三.黃黃金金分分割割法法（（0.618法法））區(qū)間間縮縮小小比比例例的的確確定定：：區(qū)間間縮縮短短比比例例為為(x2-a)/(b-a)縮短短比比例例為為(b-x1)/(b-a)縮短短比比例例滿滿足足：：每次次插插入入搜搜索索點(diǎn)點(diǎn)使使得得兩兩個(gè)個(gè)區(qū)區(qū)間間[a,x2]和和[x1,b]相相等等；；每次次迭迭代代都都以以相相等等的的比比例例縮縮小小區(qū)區(qū)間間。。0.618法x1x2ababx1x2黃金金分分割割法法的的計(jì)計(jì)算算公公式式的的推推導(dǎo)導(dǎo)：：通過過確確定定的的取取值值，，使使上上一一次次迭迭代代剩剩余余的的迭迭代代點(diǎn)點(diǎn)恰恰與與下下一一次次迭迭代代的的一一個(gè)個(gè)迭迭代代點(diǎn)點(diǎn)重重合合，，從從而而減減少少算算法法的的計(jì)計(jì)算算量量。。同理理可可得得。。3.0.618法法的的算算法法步步驟驟：：確定定[a,b],計(jì)計(jì)算算探探索索點(diǎn)點(diǎn)x1=a+0.382(b-a)x2=a+0.618(b-a)是否是停止止，，輸輸出出x1否以[a,x2]為為新新的的搜搜索索區(qū)區(qū)間間是停止止，，輸輸出出x2否以[x1,b]為為新新的的搜搜索索區(qū)區(qū)間間3.0.618法法的的算算法法框框圖圖：：黃金金分分割割法法的的迭迭代代效效果果：：第k次后后迭迭代代后后所所得得區(qū)區(qū)間間長(zhǎng)長(zhǎng)度度為為初初始始區(qū)區(qū)間間長(zhǎng)長(zhǎng)度度的的其它它的的試試探探點(diǎn)點(diǎn)算算法法：：Fibonacci算算法法。。例：解：：t1t230t1、、第第一一輪輪：：t1=1.146,t2=1.854t2－0>0.52、、第第二二輪輪：：t2=1.146,t1=0.708t2－0=1.146>0.53、、第第三三輪輪：：t1=0.438,t2=0.708b-t1=1.146-0.438>0.51.8540tt2t11.1460tt2t14、第四四輪：t2=0.876=(1.146-0.438),t1=0.708b-t1=1.146-0.708<0.5輸出：t*=t2=0.876為為最優(yōu)解解，最優(yōu)優(yōu)值為-0.079801.146tt1t2四．Fibonacci法法此法類似似于0.618法，也也是用于于單峰函函數(shù)。其其計(jì)算過過程也與與0.618類類似，第第1次迭迭代計(jì)算算兩個(gè)試試探點(diǎn)，，以后每每次迭代代只需新新加一點(diǎn)點(diǎn)，另一一試探點(diǎn)點(diǎn)取自上上次的迭迭代點(diǎn)。。此法與與0.618法法的主要要差別為為：區(qū)間間長(zhǎng)度的的縮短比比率不是是常數(shù)，，而是由由Fibonacci數(shù)確確定；給給出精度度后，迭迭代次數(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。。通過求求解遞推推關(guān)系可可求得該該數(shù)列的的通項(xiàng)為為úú?ùêê?é????è?--????è?+=++1125125151nnnF（2.3）由（2.3）式可求得。利用Fibonacci數(shù)的這一特點(diǎn)，用法中的0.618，再梢加改進(jìn)，便是Fibonacci法。618.01?-nnFF618.01代替nnFF-在Fibonacci法法中，，第n次迭代代的搜搜索區(qū)區(qū)間的的長(zhǎng)度度（記記為）是上上一次次區(qū)間間長(zhǎng)度度的倍倍所以要要使在在第n次迭代代時(shí)搜搜索區(qū)區(qū)間的的長(zhǎng)度度不超超過εε，只只需￡01LFnε

（2.4）

即可。。因是已知知值，，所以以給出出精度度ε后后利用用（2.4）式式可求求得迭迭代次次數(shù)。。Fibonacc法法在迭迭代中中計(jì)算算試探探點(diǎn)的的公式式為即有Fibonacci法(1)對(duì)對(duì)初初始區(qū)區(qū)間和和精度度ε>0，，求目目標(biāo)函函數(shù)值值的計(jì)計(jì)算次次數(shù)n，使置辨別別常數(shù)數(shù)δ>0。。計(jì)算算試探探點(diǎn)計(jì)算函函數(shù)值值和。。置置k=1。。（2））若若，，則轉(zhuǎn)轉(zhuǎn)（3）；；若，，則轉(zhuǎn)轉(zhuǎn)（4）。。（3））（5））置置k﹕=k+1，，轉(zhuǎn)（（2））。（4））（6））思想在極小小點(diǎn)附附近，，用二二次三三項(xiàng)式式四.拋拋物物線（（二次次）插插值即“兩兩頭大大中間間小””如何計(jì)計(jì)算函函數(shù)令x=33221123322221111111121fxfxfxxfxfxf-拋物線線插值值算法法步驟驟：解出思路：：五.三三次次插值值法設(shè)令則有求解滿滿足的極小小點(diǎn)令而解方程（3），有兩兩種情況：：由（2）可可知極小點(diǎn)的計(jì)計(jì)算公式：：令算法步驟：：其它插值算算法：有理插值。。收斂速度：：三次插值值算法的收收斂階為2。六、MATLAB單變量函數(shù)數(shù)求最小值值的標(biāo)準(zhǔn)形形式為s.t函數(shù)fminbnd格式x=fminbnd(fun,x1,x2)%返回自變量量x在區(qū)間上函數(shù)fun取最小小值時(shí)x