1、高等運籌學(xué),第二篇 運籌學(xué)中的數(shù)學(xué)規(guī)劃,第三章 線性規(guī)劃 第四章 非線性規(guī)劃 第五章 錐規(guī)劃 第六章 矩陣規(guī)劃 第七章 變分不等式與互補問題 第八章 整數(shù)規(guī)劃 第九章 動態(tài)規(guī)劃 第十章 向量優(yōu)化（多目標(biāo)優(yōu)化） 第十一章 全局優(yōu)化,第三講,5.1基本概念 5.2凸函數(shù)和凸規(guī)劃 5.3一維搜索方法 5.4無約束最優(yōu)化方法 5.5約束最優(yōu)化方法,第四章 非線性規(guī)劃,非線性規(guī)劃問題,例1 曲線的最優(yōu)擬合問題,例2 構(gòu)件容積問題,某鋼鐵廠準(zhǔn)備用5000萬元用于A、B兩個項目技改進行投資。預(yù)估投資項目的年收益分別為20%和16%。同時，投資后總的風(fēng)險損失隨總投資和單項投資的增加而增加，應(yīng)如何分配資金，才能

2、使期望收益達最大，同時又使風(fēng)險損失為最?。?例3: 投資決策問題,問題假設(shè),1、設(shè)x1, x2分別表示分配給項目A、B的投資資金； 2、總的風(fēng)險損失與總投資的平方成正比，也與單項投資的平方成正比，即風(fēng)險損失函數(shù)為： g(x1,x2)= (x1+x2)2 +2x12+x22 3、收益函數(shù)為：f(x1,x2)=20 x1+16x2 (高收益，高風(fēng)險),數(shù)學(xué)模型,max f(x1,x2)- g(x1,x2) max 20 x1+16x2- (x1+x2)2 +2x12+x22 s.t. x1+ x25000 x1, x20 其中，0為權(quán)系數(shù)。 特殊情形： =0，不考慮風(fēng)險； = 1，考慮收益和風(fēng)險同

3、等重要； 1，表示風(fēng)險最小是第一目標(biāo)， 其次才考慮收益目標(biāo)。,投資決策問題另外一種提法:,某公司在一個時期內(nèi)可用于投資的總資本為b萬元, 可供選擇的項目有n個。假定對第i個項目的投資總額為ai萬元，收益總額為ci萬元。 問如何確定投資方案，使總的利潤率達最高？ 設(shè)投資決策變量為：,數(shù)學(xué)模型,關(guān)于決策變量xi的非線性約束整數(shù)規(guī)劃問題。,收益占總投資 的比率,1.非線性規(guī)劃模型：,數(shù)學(xué)規(guī)劃模型的一般形式：,其中,x=(x1 ,x2, xn)T，f(x),gi(x),hj(x)為x的實值函數(shù),簡記為MP(Mathematical Programming),退 出,前一頁,后一頁,2.1 基本概念,可

4、行域和可行解：,稱,為MP問題的約束集或可行域。,若x在X內(nèi)，稱x為MP的可行解或者可行點。,退 出,前一頁,后一頁,簡記形式：,引入向量函數(shù)符號：,退 出,前一頁,后一頁,數(shù)學(xué)規(guī)劃問題的分類：,若f(x),gi(x),hj(x)為線性函數(shù)，即為線性規(guī)劃(LP)；,若f(x),gi(x),hj(x)至少一個為非線性，即為非線性規(guī)劃(NLP)；,對于非線性規(guī)劃，若沒有g(shù)i(x),hj(x)即X=Rn,稱為無約束非線性規(guī)劃或無約束最優(yōu)化問題；否則稱為約束非線性規(guī)劃或約束最優(yōu)化問題。,退 出,前一頁,后一頁,最優(yōu)解和極小點,對于數(shù)學(xué)規(guī)劃（MP），若 ，并且有,如果有,定義:,退 出,前一頁,后一頁,

5、如果有,定義,退 出,前一頁,后一頁,例,退 出,前一頁,后一頁,三角形表示的是可行域。,同心圓表示的是目標(biāo)函數(shù)的等值線。,最優(yōu)解為（1/2，1/2） 最優(yōu)值為1/2,問題：(1/2,1/2)是整體的還是局部的？是嚴格的還是非嚴格的？,1/2,1/2,退 出,前一頁,后一頁,2.非線性規(guī)劃方法概述,微分學(xué)方法的局限性：,實際的問題中，函數(shù)可能是不連續(xù)或者不可微的。 需要解復(fù)雜的方程組，而方程組到目前仍沒有有效的算法。 實際的問題可能含有不等式約束，微分學(xué)方法不易處理。,退 出,前一頁,后一頁,數(shù)值方法的基本思路：迭代,給定初始點x0,根據(jù)x0,依次迭代產(chǎn)生點列xk,xk的最后一點為最優(yōu)解,xk

6、收斂于最優(yōu)解,退 出,前一頁,后一頁,迭代格式,xk,xk+1,稱pk為第k輪搜索方向，tk為第k輪沿pk方向的步長。,產(chǎn)生tk和pk的不同方法，形成了不同的算法。,退 出,前一頁,后一頁,定義：下降方向,退 出,前一頁,后一頁,定義,解非線性規(guī)劃問題，關(guān)鍵在于找到某個方向，使得在此方向上，目標(biāo)函數(shù)得到下降，同時還是可行方向。 這樣的方向稱為可行下降方向。,退 出,前一頁,后一頁,1.凸函數(shù)及其性質(zhì)：,定義,退 出,前一頁,后一頁,2.2 凸函數(shù)和凸規(guī)劃,退 出,前一頁,后一頁,定理:,關(guān)于凸函數(shù)的一些結(jié)論,定理:,是凸集。,函數(shù)f在集合S上關(guān)于c的水平集,退 出,前一頁,后一頁,定理,? 還

7、有什么方法判斷一個函數(shù)是凸函數(shù)呢？,退 出,前一頁,后一頁,退 出,前一頁,后一頁,2.凸規(guī)劃及其性質(zhì)：,凸規(guī)劃定義：,退 出,前一頁,后一頁,凸規(guī)劃性質(zhì)：,凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。,凸規(guī)劃是以后重點討論的一類非線性規(guī)劃,線性函數(shù),退 出,前一頁,后一頁,解：,（1）目標(biāo)函數(shù)是不是凸函數(shù)？ （2）gi(x)是不是凸函數(shù)？,退 出,前一頁,后一頁,t為實數(shù),一維搜索問題指目標(biāo)函數(shù)為單變量的非線性規(guī)劃問題。又稱線性搜索問題。其模型為：,什么叫一維搜索問題？,或,退 出,前一頁,后一頁,2.3一維搜索方法,一維搜索問題的算法分類：,精確一維搜索（最優(yōu)一維搜索） 非精確一維搜索（可接

8、受一維搜索）,本節(jié)內(nèi)容：,兩種精確一維搜索方法：0.618法，Newton法。 兩種非精確一維搜索方法：Goldstein(戈德斯坦）法,Armijo（阿米霍）法。,退 出,前一頁,后一頁,1. 0.618法（近似黃金分割法）,問題：凸函數(shù)是不是單谷函數(shù)？嚴格凸函數(shù)是不是單谷函數(shù)？單谷函數(shù)是不是凸函數(shù)？,單谷函數(shù),退 出,前一頁,后一頁,搜索法求解：,或,基本過程： 給出a,b,使得t*在a,b中。a,b稱為搜索區(qū)間。 迭代縮短a,b的長度。 當(dāng)a,b的長度小于某個預(yù)設(shè)的值，或者導(dǎo)數(shù)的絕對值小于某個預(yù)設(shè)的正數(shù)，則迭代終止。,退 出,前一頁,后一頁,假定：已經(jīng)確定了單谷區(qū)間a,b,新搜索區(qū)間為a

9、,t2,新搜索區(qū)間為t1,b,退 出,前一頁,后一頁,區(qū)間縮小比例的確定：,區(qū)間縮短比例為(t2-a)/(b-a),縮短比例為(b-t1)/(b-a),縮短比例 滿足： 每次插入搜索點使得兩個區(qū)間a,t2和t1,b相等； 每次迭代都以相等的比例縮小區(qū)間。,退 出,前一頁,后一頁,確定a,b,計算探索點 t1=a+0.382(b-a) t2=a+0.618(b-a),0.618法解題步驟：,停止，輸出t1,以a,t2為新的搜索區(qū)間,停止，輸出t2,以t1,b為新的搜索區(qū)間,退 出,前一頁,后一頁,例：,解：,1.第一輪： t1=1.146, t2=1.854,t200.5,退 出,前一頁,后一頁

10、,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, t1=0.708,b-t1=1.146-0.7080.5,輸出：t*=t2=0.876為最優(yōu)解，最優(yōu)值為-0.0798,課下練習(xí)：分析上述迭代過程，體會0.618法的實質(zhì)。,退 出,前一頁,后一頁,2.Newton法,Newton法基本思想：,用探索點tk處的二階Taylor展開式近似代替目標(biāo)函數(shù)，以展開式的最小點為新的探索點。,退 出,前一頁,后一頁,解題步驟：,給

11、定初始點t1和精度,停止，輸出t1,停止，解題失敗,停止，輸出t2,退 出,前一頁,后一頁,例：,解：,取t1=1,計算：,迭代過程如下表：,退 出,前一頁,后一頁,3.非精確一維搜索法,數(shù)值方法的關(guān)鍵是從一個點迭代到下一個點。,確定下一個點的關(guān)鍵是確定搜索方向和步長,如果已經(jīng)確定了搜索方向pk,則只要確定一個最佳的步長即可。,所謂的最佳步長即是在pk方向上走一個最好的長度使得目標(biāo)函數(shù)下降的最多，即下述的最優(yōu)化問題：,這樣的最優(yōu)化問題不需要太高的精度，只要滿足某些更寬松的精度要求即可。 這樣的搜索方法稱之為非精確一維搜索方法,退 出,前一頁,后一頁,Goldstein法原理：,Y=(0)+ (

12、0)t,Y=(0)+ m2(0)t,Y=(0)+ m1(0)t,退 出,前一頁,后一頁,是,Goldstein算法,確定m1,m2,t0, a=0,b=+,(t0) (0)+m1 (0)t0,(t0) (0)+m2(0)t0,是,停止,輸出t0,否,a=a, b=t0, t1=(a+b)/2,否,a=t0,b=b, t1=(a+b)/2 (若b=+,則t1= a),退 出,前一頁,后一頁,Armijo法原理：,退 出,前一頁,后一頁,本節(jié)課討論n元函數(shù)的無約束非線性規(guī)劃問題：,求解此類模型(UMP)的方法稱為無約束最優(yōu)化方法。,無約束最優(yōu)化方法通常有兩類： 解析法：要使用導(dǎo)數(shù)的方法； 直接法：

13、無須考慮函數(shù)是否可導(dǎo)，直接使用函數(shù)值。,退 出,前一頁,后一頁,2.4無約束最優(yōu)化方法,1.無約束問題的最優(yōu)性條件,定理1,定理2,梯度為0的點稱為函數(shù)的駐點。 駐點可能是極小點，也可能是極大點，也可能即不是極大也不是極小，這時稱為函數(shù)的鞍點。 定理2說明：UMP問題的局部最優(yōu)解必是目標(biāo)函數(shù)的駐點。,注：,退 出,前一頁,后一頁,定理3,定理4,退 出,前一頁,后一頁,例,解： 1.先求出目標(biāo)函數(shù)的全部駐點； 2.利用充分條件判斷駐點是不是最優(yōu)點。,退 出,前一頁,后一頁,關(guān)于梯度的復(fù)習(xí)： 梯度是一個向量。n元函數(shù)f(x1 ,x2 ,xn)在某點x處的梯度為：,梯度的方向與函數(shù)f的等值線的一個

14、法線方向相同，從較低的等值線指向較高的等值線。,梯度的方向就是函數(shù)f的值增加最快的方向，其相反方向就是函數(shù)值降低最快的方向。,2.最速下降法,退 出,前一頁,后一頁,最速下降法又稱為梯度法，由Cauchy于1847年給出。,最速下降法解決的是具有連續(xù)可微的目標(biāo)函數(shù)的UMP問題。,最速下降法的基本思想：從當(dāng)前點xk出發(fā)尋找使得目標(biāo)函數(shù)下降最快的方向，即負梯度方向。,退 出,前一頁,后一頁,最速下降法計算步驟：,選區(qū)初始點x0和精度,計算,停止，輸出x0,求p0=,計算t0,使,計算x1= x0+ t0 p0,退 出,前一頁,后一頁,例,解：,退 出,前一頁,后一頁,說明： 觀察P119的圖，可以

15、發(fā)現(xiàn)x1 x0垂直于目標(biāo)函數(shù)的等值線（圖中的虛線）在x0的切線； 最速下降方法相鄰的兩個搜索方向是相互垂直的，即x1 x0垂直x1 x2； 最速下降法解決UMP的缺陷：迭代點越靠近最優(yōu)解則目標(biāo)函數(shù)下降的速度越慢； 優(yōu)點：迭代點列總是收斂的，而且計算過程簡單。,退 出,前一頁,后一頁,本節(jié)課討論約束非線性規(guī)劃問題MP,其中,x=(x1 ,x2, xn)T，f(x),gi(x),hj(x)為x的實值函數(shù),求解此類模型(MP)的方法稱為約束最優(yōu)化方法。,退 出,前一頁,后一頁,2.5約束最優(yōu)化方法,1.約束最優(yōu)化問題的最優(yōu)性條件,對于MP問題：,退 出,前一頁,后一頁,若x*有變化，則約束條件可能沒

16、有破壞,若x*有變化，則約束條件一定被破壞,令J表示MP的全部等式約束的下標(biāo)集合，即J=1,2q, I表示MP的全部不等式約束的下標(biāo)集合，即I=1,2p,x*的積極約束的下標(biāo)集合,退 出,前一頁,后一頁,定理1,對于,若x*是局部最優(yōu)解,則,退 出,前一頁,后一頁,定理1的說明：,2、稱下述表達式為MP的Kuhn-Tucker條件，簡稱K-T條件,滿足K-T條件的點稱為MP的K-T點，定理1說明MP的局部最優(yōu)解一定是MP的K-T點。,為了求出MP的最優(yōu)解，可以先找出MP的K-T點，再做進一步的判斷。,退 出,前一頁,后一頁,3、定理1的實例說明,定理1表明：若(x1,x2)T是局部最優(yōu)解，g1

17、和g2為積極約束，則：,退 出,前一頁,后一頁,4.定理1的特例1,退 出,前一頁,后一頁,5.定理1的特例2,退 出,前一頁,后一頁,6.定理1的改進：,對于,若x*是局部最優(yōu)解,則,互補松緊條件,退 出,前一頁,后一頁,7.實例說明改 進后的定理1：,定理1改進后表明：若(x1,x2)T是局部最優(yōu)解，則：,退 出,前一頁,后一頁,互補松緊條件,退 出,前一頁,后一頁,定理2,對于,注：定理2表明，在凸性條件下，K-T點是整體最優(yōu)解。,退 出,前一頁,后一頁,例：寫出K-T條件; 求出相應(yīng)的K-T點; 判斷K-T點是不是問題的最優(yōu)解,解：由于全部函數(shù)都是連續(xù)可微的，所以應(yīng)用以下K-T條件,退

18、 出,前一頁,后一頁,首先寫出原MP問題的K-T條件：,根據(jù)定理1,K-T點還應(yīng)該滿足原問題的約束條件,互補松緊條件,退 出,前一頁,后一頁,利用互補松緊條件，可以求出K-T點：,利用定理2，由于全部函數(shù)都連續(xù)可微，并且f和g都是凸函數(shù)，h是線性函數(shù)，所以K-T點就是整體最優(yōu)解。,退 出,前一頁,后一頁,2.懲罰函數(shù)法,懲罰函數(shù)法的基本思想：利用原問題的中的約束函數(shù)構(gòu)造適當(dāng)?shù)膽土P函數(shù)，并和原問題的目標(biāo)函數(shù)相加，得到帶參數(shù)的增廣目標(biāo)函數(shù)，從而將原問題題轉(zhuǎn)換為一系列無約束非線性規(guī)劃問題。 懲罰函數(shù)法的分類：罰函數(shù)法（外部懲罰法），障礙函數(shù)法（內(nèi)部懲罰法）,退 出,前一頁,后一頁,(1) 罰函數(shù)法,

19、罰函數(shù)法基本原理：,考慮：,構(gòu)造懲罰函數(shù)：,很大的正數(shù),無約束最優(yōu)化問題min F(x)=f(x)+p(x)的最優(yōu)解必定是原問題的最優(yōu)解。,退 出,前一頁,后一頁,可選的懲罰函數(shù)：,懲罰函數(shù)法的經(jīng)濟解釋： f(x)為產(chǎn)品成本，約束條件為產(chǎn)品質(zhì)量約束； 如果違反質(zhì)量約束，就給予一定的懲罰p(x)； 追求的目標(biāo)就是成本f(x)和懲罰量p(x)的總和最小（即構(gòu)造的無約束最優(yōu)化問題）； 如果懲罰條件很苛刻，最好的結(jié)果就是不違反質(zhì)量約束（無約束最優(yōu)化問題的最優(yōu)解為MP的最優(yōu)解）,退 出,前一頁,后一頁,(2) 障礙函數(shù)法,障礙函數(shù)法基本原理： 構(gòu)造一個新的目標(biāo)函數(shù)，它在可行區(qū)域的邊界筑起一道墻； 當(dāng)?shù)?/p>

20、點靠近邊界時，新的目標(biāo)函數(shù)迅速增加；迭代點被檔在可行區(qū)域的內(nèi)部； 迭代得到的點列就只可能在可行區(qū)域的內(nèi)部。,退 出,前一頁,后一頁,可選的懲罰函數(shù)：,考慮：,構(gòu)造最優(yōu)化問題：,或：,當(dāng)x靠近邊界時，至少有一個gi(x)趨近于零，則F(x)將無限增大，從而使得迭代點保持在可行區(qū)域的內(nèi)部。,退 出,前一頁,后一頁,應(yīng)用實例： 供應(yīng)與選址,某公司有6個建筑工地要開工，每個工地的位置（用平面坐標(biāo)系a，b表示，距離單位：千米 ）及水泥日用量d(噸)由下表給出。目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20噸。假設(shè)從料場到工地之間均有直線道路相連。 （1）試制定每天的供應(yīng)計劃，即從A，B

21、兩料場分別向各工地運送多少噸水泥，使總的噸千米數(shù)最小。 （2）為了進一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20噸，問應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？,（一）、建立模型,記工地的位置為(ai，bi)，水泥日用量為di，i=1,6;料場位置為(xj，yj)，日儲量為ej，j=1,2；從料場j向工地i的運送量為Xij。,當(dāng)用臨時料場時決策變量為：Xij， 當(dāng)不用臨時料場時決策變量為：Xij，xj，yj。,（二）使用臨時料場的情形,使用兩個臨時料場A(5,1)，B(2,7).求從料場j向工地i的運送量為Xij，在各工地用量必須滿足和各料場運送量不超過日儲量的條件下，使總的噸

22、千米數(shù)最小，這是線性規(guī)劃問題. 線性規(guī)劃模型為：,設(shè)X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 編寫程序gying1.m,MATLAB（gying1）,clear a=1.25 8.75 0.5 5.75 3 7.25; b=1.25 0.75 4.75 5 6.5 7.75; d=3 5 4 7 6 11; x=5 2; y=1 7; e=20 20; for i=1:6 for j=1:2 aa(i

23、,j)=sqrt(x(j)-a(i)2+(y(j)-b(i)2); end end,CC=aa(:,1); aa(:,2); A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1; B=20;20; Aeq=1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 ; beq=d(1);d(2);d(3);d(4);d(5

24、);d(6); VLB=0 0 0 0 0 0 0 0 0 0 0 0;VUB=; x0=1 2 3 0 1 0 0 1 0 1 0 1; xx,fval=linprog(CC,A,B,Aeq,beq,VLB,VUB,x0),計算結(jié)果為：,x = 3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000 fval = 136.2275,（三）改建兩個新料場的情形,改建兩個新料場，要同時確定料場的位置(xj,yj)和運送量Xij，在同樣條件下使總噸千米數(shù)最小。這是非線性規(guī)劃問題。非線性

25、規(guī)劃模型為：,設(shè) X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 x1=X13, y1=X14, x2=X15, y2=X16,（1）先編寫M文件liaoch.m定義目標(biāo)函數(shù)。,MATLAB（liaoch）,function f=liaoch(x) a=1.25 8.75 0.5 5.75 3 7.25; b=1.25 0.75 4.75 5 6.5 7.75; d=3 5 4 7 6 11; e=20 2

26、0; f1=0; for i=1:6 s(i)=sqrt(x(13)-a(i)2+(x(14)-b(i)2); f1=s(i)*x(i)+f1; end f2=0; for i=7:12 s(i)=sqrt(x(15)-a(i-6)2+(x(16)-b(i-6)2); f2=s(i)*x(i)+f2; end f=f1+f2;,(2) 取初值為線性規(guī)劃的計算結(jié)果及臨時料場的坐標(biāo): x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7; 編寫主程序gying2.m.,MATLAB（gying2）,x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7; A=1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0; B=20;20; Aeq=1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0