（優(yōu)選）常用無約束最優(yōu)化方法單純形當前1頁，總共20頁。目錄一、單純形法基本原理二、單純形法迭代步驟

三、單純形法有關(guān)說明

四、習題當前2頁，總共20頁。

單純形法是利用比較簡單幾何圖形各頂點的目標函數(shù)值,在連續(xù)改變幾何圖形的過程中,逐步以目標函數(shù)值較小的頂點取代目標函數(shù)值最大的頂點,而求優(yōu)點的方法,屬于直接法。當前3頁，總共20頁。一、單純形法基本原理

現(xiàn)以求二元函數(shù)的極小點為例,說明單純形法形成原理。

設(shè)二元函數(shù)f(X

)=f(x1,x2)在x1x2平面上取不共線的三個點X1,

X2,X3，以此為頂點構(gòu)一單純形——三角形.算出各頂點的函數(shù)值f(X1),f(X2),f(X3),比較其大小,現(xiàn)設(shè)有f(X1)>f(X2)>f(X3)。這說明X1最差,X3最好,X2次差.為了尋找極小點,一般來說應(yīng)向最差點的反對稱方向進行搜索.以X4記為X2X3的中點在X1X4的延長線上取點X5,使稱為X5為X1關(guān)于X4的反射點.如圖5.15。當前4頁，總共20頁。圖5.15當前5頁，總共20頁。算出X5

的函數(shù)值f(X5

),可能有下列情形:⑴f(X5)<f(X3). 搜索方向正確,可進一步擴張,繼續(xù)沿X1X5向前搜索(擴張).

,其中α為擴張因子,可取 如f(X6)<f(X5),則擴張有利,以X6代替X1構(gòu)新單純形{X2,X3,X6}.如f(X6)>f(X5),則擴張不利,舍去X6,以X5代替X1構(gòu)新單純形{X2,X3,X5}.幾種情形的討論

(4)若方向上所有點的函數(shù)值都大于,則不能沿此方向搜索.這時,可以以為中心進行縮邊,若使頂點和向移近一半距離(如圖5.16所示),得新單純形.以此單純形為基礎(chǔ)再進行尋優(yōu).這時取當前6頁，總共20頁。⑵f(X3)<f(X5)<f(X2).這說明搜索方向正確,無須擴張,以X5代替X1構(gòu)成新的單純形{X2,X3,X5}.⑶f(X2)<f(X5)<f(X1).這表示X5走得太遠,應(yīng)縮回一些.若以β表示壓縮因子,則有常取β為0.5,以X7代替X1構(gòu)成新的單純形{X2,X3,X7}.當前7頁，總共20頁。⑷

f(X5)>f(X1).

這時應(yīng)更多壓縮,將新點壓縮至X1X4之間,有注意,上兩式只是X1和X5的差別.如f(X8)<f(X1),則以X8代替X1構(gòu)成新的單純形{X2,X3,X8}.否則可以認為X1X4方向上所有點的函數(shù)值f(X)都大于f(X1)不能沿此方向搜索．這時,可以以X3為中心進行縮邊,使頂點X1和X2向X3移近一半距離如右圖所示,以此單純形為基礎(chǔ)再進行尋優(yōu).得新單純形{X3,X9,X10}.當前8頁，總共20頁?？梢?不管如何,都可得到一新的單純形,其中至少有一頂點的函數(shù)值比原單純形為小.如此繼續(xù),直至滿足終止準則.在n維情況下,一個單純形含有n+1個頂點,計算工作量較大,但原理和上述二維情況相同.當前9頁，總共20頁。二、單純形法迭代步驟

已知設(shè)X為n維變量,目標函數(shù)為f(X),終止限為⑴構(gòu)造初始單純形在n維空間中選初始點X0(離最優(yōu)點越近越好),從X0出發(fā),沿各坐標方向以步長t移動得n個頂點,這樣選擇頂點可保證向量組線性無關(guān),否則,就會使搜索范圍局限在較低維的空間內(nèi),可能找不到極小點.當然,在各坐標方向可以走不同的距離.步長t的范圍可取0.5~15.0,開始時常取t=1.5~2.0,接近最優(yōu)點時要減小,例如取0.5~1.0.當前10頁，總共20頁。⑵計算各頂點的函數(shù)值比較各函數(shù)值的大小,確定最好點XL、最差點XH及次差點XG,即當前11頁，總共20頁。⑶計算XH之外各點的“重心”

求出反射點⑷擴張當f(Xn+2)<f(XL),需擴張,令

如f(Xn+3)<f(Xn+2),則以Xn+3代替XH形成一新單純形;否則,以代Xn+2替XH構(gòu)成新單純形.轉(zhuǎn)(8).⑸無擴縮當f(XL)≤f(Xn+2)<f(XG),以代Xn+2替XH構(gòu)成新單純形.轉(zhuǎn)(8).當前12頁，總共20頁。⑹收縮.當f(XG)≤f(Xn+2)<f(XH)時,則需收縮,令以代Xn+4替XH構(gòu)成新單純形.并轉(zhuǎn)(8).⑺縮邊.當f(XH)≤f(Xn+2),令,如果f(XH)≤f(Xn+5),則將單純形縮邊,可將向量Xi-XL的長度縮小一半,即這樣可得一新單純形.否則,以Xn+5代替XH形成一新單純形.轉(zhuǎn)(8).

當前13頁，總共20頁。⑻收斂性檢驗每次得新單純形后,即應(yīng)進行收斂性檢驗,如滿足收斂指標,則迭代停止,XL即為所求的近似解.否則,繼續(xù)進行迭代計算.常用的收斂準則是或ε1和ε2為預(yù)先給定的允許誤差.當前14頁，總共20頁。單純形法的流程如圖當前15頁，總共20頁。試用單純形法求的極小值.解選X0=(8,9)T,并取X1=(10,11)T和X2=(8,11)T.這三點不共線,它們作為初始單純形的頂點(如圖所示).然后計算各頂點的函數(shù)值:，可知X1為最差點,X0為最好點.以X3表示X0和X2的重心,則例5.6

(P118)當前16頁，總共20頁。續(xù)解例5.6反射點由于f(X4)<f(X0),故需擴張.取α=2,則當前17頁，總共20頁。因為f(X5)<f(X4),故以X5代替X1,由X5,X0和X2構(gòu)成新單純形,然后進行下一個循環(huán).該問題的最優(yōu)解為X*=(5,6)T,f(X

*)=0.經(jīng)32次循環(huán),可把目標函數(shù)f(X)減小到110-6.在圖中給出