1、河海大學研究生最優(yōu)化方法考試范圍授課老師：丁根宏（2016年春）考試范圍：線性和非線性約束占比70%,多目標和動態(tài)規(guī)劃占30%,題型為計算和證明共8道題，其中一道證明題。線性規(guī)劃：兩階段法改進單純形法對偶單純形法的計算基變換的定理保證對偶理論的證明無約束非線性規(guī)劃：一維搜索（0.618法，F(xiàn)ibonaci法，牛頓切線法和二次插值法）牛頓法公式及推導計算題（最速下降法、牛頓法和共腕梯度法）步驟簡單，主要是思想的比較變尺度法和牛頓法的對比有約束非線性規(guī)劃：K-T條件及驗證求K-T點SUMT方法（外點法和內(nèi)點法）投影梯度法理論及投影梯度的定義多目標規(guī)劃：解的定義求Rpa*,Rwp*變量空間和函數(shù)空間

2、評價函數(shù)的收斂性動態(tài)規(guī)劃：最優(yōu)性原理步驟（6個概念）泛函方程應用舉例（多階段決策問題包括資源分配問題）函數(shù)空間和策略空間迭代法考試試卷（2016年6月3號）1、 改進單純形法，從中間某步繼續(xù)往下迭代至求出最優(yōu)解例（P66）用改進單純形法求解問題min卜-3X|-x2-3xa2X1+m+x3+x4=2X+2xz+3x3+x5=52X1+2x2+x3+x6=6x；20,i=l,62、 對偶理論的證明定理1（弱對偶定理）若K和V分別為互為對偶的線性規(guī)劃問題和的可行解則有證明，因為yAWc,所以yb=y（A尤）=（yA）k這c工定理2（強標搞定理）若x*和V*分別為互為對偶的線性規(guī)劃問題和的可行解，且

3、cx*-y*bf則、了分別為和的最優(yōu)解.證明：因?qū)θ我豢尚薪鈞,故爐為的最優(yōu)解口同理可證/為的最優(yōu)解44定理3（對偶定理）若對偶問題（1）和Q）中有一個有最優(yōu)解，則另一個也一定有最優(yōu)解，并且兩個問題的目標函數(shù)的最優(yōu)值相等。證明：設鏟是的最優(yōu)基可行解，對應的基為B,則其檢驗數(shù)為口=cbB-A-cO令，C#T（單純形乘子）則有*AWc且露b氣匕時）b=cB（B-1b）=c3Xjjcx*由定理Z知y*為（2）的最優(yōu)解。i由對偶問題的對稱性，可證定理的另一種情形3、牛頓切線法的公式及推導.*tnhif(x)基本思想：用Rk)在近似點“的二階丁”lor展開式近似代替食工)I設、F(x)是在忸.b上的&#

4、39;單峰函數(shù),fM(xk)>0,作炳冷=/(.%)+令g'(H)=/'氏)+)任一.)二。得x-x-EG&1,"L*，"*)S3注意；求出的點兒內(nèi)與MQ的值無關。,設X的是f(X)的近似點，將f(X)在X陽點作二階Taylor展開，嬉+*(X-Xm)r77(X,t)(X-X)記右端=4>(X)«令6(X)=0得V/IX)+(X(")(X_X)=0A=牙叫0(')此即為Ncwtoii迭代公式口4、 變尺度法和牛頓法的比較 1)基本原理 在上述阻尼牛頓法中，.H(Xg尸V.X的) X(k+l>=X<k

5、J+x川臉K Xk：minf(X®+AS) 由于逆矩陣H(X*)尸的計算量太大，實現(xiàn)困濰口一 為了保持牛頓法的優(yōu)點，試圖構造H(X尸卜的近似陣才”，不需要求逆矩陣 若WX)為二次函數(shù)，其He弱gn矩陣H(X)為常數(shù)陣，則在XM1)和X處的梯度之差等于 i(X(k+昨Vf(XQ=A(XW1LXS XW】)-X(k=A*1Vf(X<l+1),Vf(X<k)J 記G(X)=f(X),AGgG(X仲丹 上式又變?yōu)锳X«>=A-iAG的5、 K-T條件及驗證如果設為(i不屬于1)在X*也可微，則上述條件可改為：Fwa力+£儼”=o*I/=1產(chǎn)區(qū)(X*)=0

6、.i=1班I必之。，熱稱X業(yè)為K-T點。2.考察如:下問題；min7tx)=.#；+料.t*：+彳M5上i+=4l4一y0*驗證在最優(yōu)點jt=(1，5,85)處.KT條件成立*并求在x點的Liigrangi乘子.6、 SUMT外點法(書上例題)例2用外點法求miif(X)=x+x2gi(X)=x-x±WOgz(X尸-也W0解：構造罰函數(shù)1(X,M)=X,+x3+4/(|max(0,jrJx3J)|2+mai(O,)|2當殖I時0時，令.=1+2jW|(jcJ-)+Jtj=03FT=112M(.V；.Yj)=0dx1一-12(H)”4(1+AJ)Z1M當Aff8時,X*二(凡0),7、

7、簡述動態(tài)規(guī)劃的使用條件及步驟，用空間迭代法求最短路徑所謂多階段決策問題，是指一類活動過程，它可以分為互相聯(lián)系的若干個階段，在每一階段都需要作出決策，從而使整個過程達到最優(yōu)的活動效果.因此，各個階段決策的選取常依賴于當前面臨的狀態(tài),又影響下一個階段的決策，從而影響整個過程的活動路線，這種把一個問題看成一個前后關聯(lián)具有鏈狀結構的多階段過程就稱為康過程.也稱貫決策過程©動態(tài)規(guī)劃的量優(yōu)性原理工一個(整個過程的)最優(yōu)策略所具有的性質(zhì)是，不論過去的狀態(tài)和決策如何，其余下的諸決策必構成一個最優(yōu)子策略.1、函數(shù)空間迭代法設h(i)表示由i點出發(fā)向N走k步所構成的所有路線中的最短距離。函數(shù)空間迭代法求

8、解步驟如下；1°Hl,2，.N-1心尸02"九=min。+1)，i=l2，斗1Jfk(N)=OT反復迭代”直到勾=3率)=蟲為止，A1,2N例3下圖為一街區(qū)的單行道交通網(wǎng)絡，分別用函數(shù)空間迭代法和策略空間迭代法求各點到頂點5的最短路線。I解I先用函數(shù)空間迭代法求解.為了便于運算，將距離C”寫成下列矩陣的形式，將人寫成列向量的形式,利用菌數(shù)空間迭代法求解,步驟迭代如下：其中最后一列i為i點的最優(yōu)決策,于是得到各點到頂點5的最短路線和最短蹈離如下表，8、多目標規(guī)劃，評價函數(shù)的收斂性設X*ER,若不存在XER滿足F(X)WF(X比),則稱X*為問題(VP)的(1-2”)口有效解的

9、全體記為R/G設X曦ER,若不存在X£R滿足F(X)F(X。則稱X*為問題(VP)的弱有效虹(Paret®#?)»弱有效解的全體記為匕10.設多目標規(guī)劃間即為JV-min尸(才)=1 s.t.才>0；r6A其中f(%)=O1)?4-1r-/+4,&3人(工)=<1,3Vh<4、/一3,1>4求；.；R0.R"和/，。評價函數(shù)的收斂性過義7若對任意F,PGEA當FWF時，都有U(F)<U(F»)成立，則稱U(F)是F的h格單調(diào)增函數(shù)定義8若對任意F.PEEP,當FP時，都有U(F)<U(F*)成立，則稱U(F)是F的單調(diào)增函數(shù)。定理8若對