常用無(wú)約束最優(yōu)化方法-單純形課件

§5.8單純形法1精選ppt課件目錄一、單純形法基本原理二、單純形法迭代步驟

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

四、習(xí)題2精選ppt課件

單純形法是利用比較簡(jiǎn)單幾何圖形各頂點(diǎn)的目標(biāo)函數(shù)值,在連續(xù)改變幾何圖形的過(guò)程中,逐步以目標(biāo)函數(shù)值較小的頂點(diǎn)取代目標(biāo)函數(shù)值最大的頂點(diǎn),而求優(yōu)點(diǎn)的方法,屬于直接法。3精選ppt課件一、單純形法基本原理

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

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

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

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

的函數(shù)值f(X5

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

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

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

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

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

求出反射點(diǎn)⑷擴(kuò)張

當(dāng)f(Xn+2)<f(XL),需擴(kuò)張,令

如f(Xn+3)<f(Xn+2),則以Xn+3代替XH形成一新單純形;否則,以代Xn+2替XH構(gòu)成新單純形.轉(zhuǎn)(8).⑸無(wú)擴(kuò)縮當(dāng)f(XL)≤f(Xn+2)<f(XG),以代Xn+2替XH構(gòu)成新單純形.轉(zhuǎn)(8).12精選ppt課件⑹收縮.當(dāng)f(XG)≤f(Xn+2)<f(XH)時(shí),則需收縮,令以代Xn+4替XH構(gòu)成新單純形.并轉(zhuǎn)(8).⑺縮邊.當(dāng)f(XH)≤f(Xn+2),令,如果f(XH)≤f(Xn+5),則將單純形縮邊,可將向量Xi-XL的長(zhǎng)度縮小一半,即這樣可得一新單純形.否則,以Xn+5代替XH形成一新單純形.轉(zhuǎn)(8).

13精選ppt課件⑻收斂性檢驗(yàn)每次得新單純形后,即應(yīng)進(jìn)行收斂性檢驗(yàn),如滿足收斂指標(biāo),則迭代停止,XL即為所求的近似解.否則,繼續(xù)進(jìn)行迭代計(jì)算.常用的收斂準(zhǔn)則是或ε1和ε2為預(yù)先給定的允許誤差.14精選ppt課件單純形法的流程如圖15精選ppt課件試用單純形法求的極小值.解

選X0=(8,9)T,并取X1=(10,11)T和X2=(8,11)T.這三點(diǎn)不共線,它們作為初始單純形的頂點(diǎn)(如圖所示).然后計(jì)算各頂點(diǎn)的函數(shù)值:，可知X1為最差點(diǎn),X0為最好點(diǎn).以X3表示X0和X2的重心,則例5.6

(P118)16精選ppt課件續(xù)解例5.6反射點(diǎn)由于f(X4)<f(X0),故需擴(kuò)張.取α=2,則17精選ppt課件因?yàn)閒(X5)<f(X4),故以X5代替X1,由X5,X0和X2構(gòu)成新單純形,然后進(jìn)行下一個(gè)循環(huán).該問(wèn)題的最優(yōu)解為X*=(5,6)T,f(X

*)=0.經(jīng)32次循環(huán),可把目標(biāo)函數(shù)f(X)減小到1

10-6.在圖中給出了前幾次迭代的情形.續(xù)解例5.618精選ppt課