線性與非線性

1、線性規(guī)劃與非線性規(guī)劃線性linear指量與量之間按比例、成直線的關(guān) 系，在數(shù)學(xué)上可以理解為一階導(dǎo)數(shù)為常數(shù)的函數(shù)； 非線性non-linea則指不按比例、不成直線的關(guān)系， 一階導(dǎo)數(shù)不為常數(shù)。如問：兩個眼睛的視敏度是一個眼睛的幾倍？很 容易想到的是兩倍，可實際是610倍！這就是非線性。激光也是非線性的！天體運動存在混沌；電、 光與聲波的振蕩，會突陷混沌；地磁場在400萬年間，方向突變16次，也是由于混沌。甚至人類自己， 原來都是非線性的：與傳統(tǒng)的想法相反，健康人的 腦電圖和心臟跳動并不是規(guī)則的，而是混沌的，混 沌正是生命力的表現(xiàn)，混沌系統(tǒng)對外界的刺激反應(yīng)， 比非混沌系統(tǒng)快。非線性規(guī)劃nonline

2、ar programming具有非線性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃， 是運籌學(xué)的一個重要分支。非線性規(guī)劃研究一個n元實函數(shù)在一組等式或不等式的約束條件下的極值 問題，且目標(biāo)函數(shù)和約束條件至少有一個是未知量 的非線性函數(shù)。目標(biāo)函數(shù)和約束條件都是線性函數(shù) 的情形則屬于線性規(guī)劃。簡史非線性規(guī)劃是20世紀(jì)50年代才開始形成的一 門新興學(xué)科。195侔H.W.庫恩和A.W.塔克發(fā)表的關(guān) 于最優(yōu)性條件（后來稱為庫恩-塔克條件）的論文是 非線性規(guī)劃正式誕生的一個重要標(biāo)志。在50年代還得出了可分離規(guī)劃和 二次規(guī)劃的n種解法，它們大都 是以G.B.丹齊克提出的解線性規(guī)劃的單純形法為基 礎(chǔ)的。50年代末到60年代末

3、出現(xiàn)了許多解非線性規(guī) 劃問題的有效的算法，70年代又得到進(jìn)一步的發(fā)展。 非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方 面都有廣泛的應(yīng)用，為最優(yōu)設(shè)計提供了有力的工具。 實例下面通過實例歸納出非線性規(guī)劃數(shù)學(xué)模型的一 般形式，介紹有關(guān)非線性規(guī)劃的基本概念。例1 （投資決策問題）某企業(yè)有 n個項目可供 選擇投資，并且至少要對其中一個項目投資。已知該企業(yè)擁有總資金 A元，投資于第i個項目需花資 金ai元，并預(yù)計可收益bi元。試選擇最佳投資方案。解設(shè)投資決策變量為I.即EEM聚r./m用U網(wǎng)不swiu十項目則投資總額為三aixi,投資總收益為三bixL因為 該公司至少要對一個項目投資，并且總的投資金額 不

4、能超過總資金，故有限制條件o向”/另外，由于xi只取值0或1,所以還有號（1 一玉）=0/ = 1,，次+最佳投資方案應(yīng)是投資額最小而總收益最大的 方案，所以這個最佳投資決策問題歸結(jié)為總資金以 及決策變量（取0或1）的限制條件下，極大化總收 益和總投資之比。因此，其數(shù)學(xué)模型為：maz Q -耳2用 二1*t. 04二因/£工川勺（1一勺）=0,?二 L ，.上面例題是在一組等式或不等式的約束下，求 一個函數(shù)的最大值(或最小值)問題，其中目標(biāo)函 數(shù)或約束條件中至少有一個非線性函數(shù)，這類問題 稱之為非線性規(guī)劃問題，簡記為( NP)?？筛爬?一般形式min / (a)s.t. M0. 八

5、1 .國 “(4=0, |(NP)其中x=x1xn豚為模型(NP)的決策變量，f 稱為目標(biāo)函數(shù)，gi和hj稱為約束函數(shù)。另外，gi(x)=0 稱為等式約束，hj(x)<=0稱為不等式約束。常見問題對于一個實際問題，在把它歸結(jié)成非線性規(guī)劃 問題時，一般要注意如下幾點：(i)確定供選方案：首先要收集同問題有關(guān)的 資料和數(shù)據(jù)，在全面熟悉問題的基礎(chǔ)上，確認(rèn)什么 是問題的可供選擇的方案，并用一組變量來表示它 們。(ii)提出追求目標(biāo)：經(jīng)過資料分析，根據(jù)實際 需要和可能，提出要追求極小化或極大化的目標(biāo)。并且，運用各種科學(xué)和技術(shù)原理，把它表示成數(shù)學(xué)關(guān)系式。(iii)給出價值標(biāo)準(zhǔn)：在提出要追求的目標(biāo)之

6、后，要確立所考慮目標(biāo)的“好”或“壞”的價值標(biāo) 準(zhǔn)，并用某種數(shù)量形式來描述它。(iv)尋求限制條件：由于所追求的目標(biāo)一般都 要在一定的條件下取得極小化或極大化效果，因此 還需要尋找出問題的所有限制條件，這些條件通常 用變量之間的一些不等式或等式來表示。數(shù)學(xué)模型對實際規(guī)劃問題作定量分析，必須建立數(shù)學(xué)模 型。建立數(shù)學(xué)模型首先要選定適當(dāng)?shù)哪繕?biāo)變量和決 策變量，并建立起目標(biāo)變量與決策變量之間的函數(shù) 關(guān)系，稱之為目標(biāo)函數(shù)。然后將各種限制條件加以抽 象,得出決策變量應(yīng)滿足的一些等式或不等式，稱之為約束條件。非線性規(guī)劃問題的一般數(shù)學(xué)模型可表 述為求未知量x1 x2,，xn使?jié)M足約束條件：gi(x1 ，xn戶0

7、 i= 1,，mhj(x1,，xn)= 0 j = 1,p并使目標(biāo)函數(shù)f(x1,xn讓到最小值(或最大 值)。其中f,諸gi和諸hj都是定義在n維向量空間Rn的某子集D(定義域)上的實值函數(shù)，且至少有一個 是非線性函數(shù)。上述模型可簡記為：min f(x)s.t. gi(x)>0 i= 1,，mhj(x)= 0 j = 1,p其中x= (x1,xn)屬于定義域 D,符號min表示 “求最小值”，符號 s.t.表示“受約束于”。定義域D中滿足約束條件的點稱為問題的可 行解。全體可行解所成的集合稱為問題的可行集。 對于一個可行解x*,如果存在x*l勺一個鄰域，使目標(biāo) 函數(shù)在x處的值f(x*玳于

8、(指不大于或不小于)該令B 域中任何其他可行解處的函數(shù)值，則稱x的問題的局部最優(yōu)解(簡稱局部解)。如果f(x*X于一切可行解處的目標(biāo)函數(shù)值，則稱x為問題的整體最優(yōu)解(簡稱整體解)。實用非線性規(guī)劃問題要求整體解， 而現(xiàn)有解法大多只是求出局部解。一維最優(yōu)化方法指尋求一元函數(shù)在某區(qū)間上的最優(yōu)值點的方 法。這類方法不僅有實用價值，而且大量多維最優(yōu) 化方法都依賴于一系列的一維最優(yōu)化。常用的一維 最優(yōu)化方法有黃金分割法、切線法和插值法。黃金分割法又稱0.618法。它適用于單 峰函數(shù)。其基本思想是：在初始尋查區(qū)間中設(shè)計一 列點，通過逐次比較其函數(shù)值，逐步縮小尋查區(qū)間， 以得出近似最優(yōu)值點。切線法又稱牛頓法。

9、它也是針對單峰函 數(shù)的。其基本思想是：在一個猜測點附近將目標(biāo)函 數(shù)的導(dǎo)函數(shù)線性化，用此線性函數(shù)的零點作為新的 猜測點，逐步迭代去逼近最優(yōu)點。插值法又稱多項式逼近法。其基本思想 是用多項式（通常用二次或三次多項式）去擬合目 標(biāo)函數(shù)。此外，還有斐波那契法、割線法、有理插值法、 分批搜索法等。無約束最優(yōu)化方法指尋求n元實函數(shù)f在整個n維向量空間Rn上 的最優(yōu)值點的方法。這類方法的意義在于：雖然實 用規(guī)劃問題大多是有約束的，但許多約束最優(yōu)化方 法可將有約束問題轉(zhuǎn)化為若干無約束問題來求解。無約束最優(yōu)化方法大多是逐次一維搜索的迭代 算法。這類迭代算法可分為兩類。一類需要用目標(biāo) 函數(shù)的導(dǎo)函數(shù)，稱為解析法。另

10、一類不涉及導(dǎo)數(shù)，只 用到函數(shù)值，稱為直接法。這些迭代算法的基本思想是：在一個近似點處選定一個有利搜索方向，沿這個方向進(jìn)行一維尋查，得出新的近似點。然后對新點施 行同樣手續(xù)，如此反復(fù)迭代，直到滿足預(yù)定的精度 要求為止。根據(jù)搜索方向的取法不同，可以有各種 算法。屬于解析型的算法有：梯度法：又稱最速 下降法。這是早期的解析法，收斂速度較慢。牛 頓法：收斂速度快，但不穩(wěn)定，計算也較困難。 共軻梯度法：收斂較快，效果較好。變尺度法： 這是一類效率較高的方法。其中達(dá)維登-弗萊徹-鮑威爾變尺度法，簡稱 DFP法，是最常用的方法。屬于直接型的算法有交替方向法（又稱坐標(biāo)輪換 法）、模式搜索法、旋轉(zhuǎn)方向法、鮑威爾

11、共朝方向 法和單純形加速法等。約束最優(yōu)化方法指前述一般非線性規(guī)劃模型的求解方法。常用 的約束最優(yōu)化方法有 4種。拉格朗日乘子法：它 是將原問題轉(zhuǎn)化為求拉格朗日函數(shù)的駐點。制約 函數(shù)法：又稱系列無約束最小化方法，簡稱 SUMT 法。它又分兩類，一類叫懲罰函數(shù)法，或稱外點法； 另一類叫障礙函數(shù)法，或稱內(nèi)點法。它們都是將原 問題轉(zhuǎn)化為一系列無約束問題來求解?？尚蟹较?法：這是一類通過逐次選取可行下降方向去逼近最優(yōu)點的迭代算法。如佐坦迪克法、弗蘭克沃爾夫 法、投影梯度法和簡約梯度法都屬于此類算法。 近似型算法：這類算法包括序貫線性規(guī)劃法和序貫 二次規(guī)劃法。前者將原問題化為一系列線性規(guī)劃問 題求解，后者

12、將原問題化為一系列二次規(guī)劃問題求 解。凸規(guī)劃這是一類特殊的非線性規(guī)劃。在前述非線性規(guī)劃數(shù)學(xué)模型中，若f是凸函數(shù)，諸gi都是凹函數(shù)，諸 hj都是一次函數(shù)，則稱之為凸規(guī)劃。所謂 f是凸函 數(shù)，是指f有如下性質(zhì)：它的定義域是凸集，且對于定 義域中任意兩點x和y及任一小于1的正數(shù)a,下式 都成立：f(1- a )x + ay)a<(1-a )f(x)+ a f(y)將上述不等式中的不等號反向即得凹函數(shù)的定 義。所謂凸集，是指具有如下性質(zhì)的集合：連結(jié)集 合中任意兩點的直線段上的點全部屬于該集合。對于一般的非線性規(guī)劃問題，局部解不一定是 整體解。但凸規(guī)劃的局部解必為整體解，而且凸規(guī) 劃的可行集和最優(yōu)

13、解集都是凸集。二次規(guī)劃一類特殊的非線性規(guī)劃。它的目標(biāo)函數(shù)是二次 函數(shù)，約束條件是線性的。求解二次規(guī)劃的方法很 多。較簡便易行的是沃爾夫法。它是依據(jù)庫恩一塔 克條件，在線性規(guī)劃單純形法的基礎(chǔ)上加以修正而 成的。此外還有萊姆基法、畢爾法、凱勒法等。 幾何規(guī)劃幾何規(guī)劃 一類特殊的非線性規(guī)劃。它的目標(biāo)函 數(shù)和約束函數(shù)都是正定多項式（或稱正項式）。幾 何規(guī)劃本身一般不是凸規(guī)劃，但經(jīng)適當(dāng)變量替換， 即可變?yōu)橥挂?guī)劃。幾何規(guī)劃的局部最優(yōu)解必為整體 最優(yōu)解。求解幾何規(guī)劃的方法有兩類。一類是通過 對偶規(guī)劃去求解；另一類是直接求解原規(guī)劃，這類 算法大多建立在根據(jù)幾何不等式將多項式轉(zhuǎn)化為單 項式的思想上。應(yīng)用問題在經(jīng)

14、營管理、工程設(shè)計、科學(xué)研究、軍事指揮 等方面普遍地存在著最優(yōu)化問題。例如：如何在現(xiàn) 有人力、物力、財力條件下合理安排產(chǎn)品生產(chǎn)，以 取得最高的利潤；如何設(shè)計某種產(chǎn)品，在滿足規(guī)格、 性能要求的前提下，達(dá)到最低的成本；如何確定一 個自動控制系統(tǒng)的某些參數(shù)，使系統(tǒng)的工作狀態(tài)最 10佳；如何分配一個動力系統(tǒng)中各電站的負(fù)荷，在保 證一定指標(biāo)要求的前提下，使總耗費最?。蝗绾伟?排庫存儲量，既能保證供應(yīng)，又使儲存費用最低； 如何組織貨源，既能滿足顧客需要，又使資金周轉(zhuǎn) 最快等。對于靜態(tài)的最優(yōu)化問題，當(dāng)目標(biāo)函數(shù)或約 束條件出現(xiàn)未知量的非線性函數(shù)，且不便于線性化， 或勉強(qiáng)線性化后會招致較大誤差時，就可應(yīng)用非線 性規(guī)劃的方法去處理。參考書目席少霖、趙鳳治： 最優(yōu)化計算方法，上海 科學(xué)技術(shù)出版社，上海，1983阿佛里耳著，李元