多目標(biāo)規(guī)劃ppt課件.ppt

《多目標(biāo)規(guī)劃ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、§3.3多目標(biāo)規(guī)劃求解方法介紹一、約束法1.基本思想：在多個(gè)目標(biāo)函數(shù)中選擇一個(gè)主要目標(biāo)作為目標(biāo)函數(shù)，其它目標(biāo)處理為適當(dāng)?shù)募s束。無妨設(shè)為主要目標(biāo)，對(duì)其它各目標(biāo)可預(yù)先給定一個(gè)期望值，不妨記為，則有求解下列問題：容易證明，約束法求問題(P)的最優(yōu)解，其Kuhn-Tucker條件與(VP)有效解的K-T條件一致。因此，約束法求得的解是有效解。(P)問題中各目標(biāo)函數(shù)期望值的取得有多種方法，一種方法是取一點(diǎn)，而取得到下列問題：2.算法一般步驟：考慮上述(VP)問題，為主目標(biāo)。第一步：（1）對(duì)，求解單目標(biāo)問題：得解；（2）計(jì)算對(duì)應(yīng)的各目標(biāo)函數(shù)值，并對(duì)每個(gè)函數(shù)，求其p

2、個(gè)點(diǎn)值中的最大值Mj和最小值mj。得到下表：Mj與mj規(guī)定了在有效解集中的取值范圍。x(1)x(p)f1(x)f2(x)…fp(x)m1m2…mpf1(x(1))f2(x(1))…fp(x(1))f1(x(p))f2(x(p))…fp(x(p))M1M2…MpMjmj………第二步：選擇整數(shù)r>1，確定的r個(gè)不同閥值：第三步：對(duì)，分別求解問題：各目標(biāo)函數(shù)可對(duì)應(yīng)不同的（共有個(gè)約束問題）。求解后可得到(VP)的一有效解集合，是(VP)有效解集合的一個(gè)子集。例6：用約束法求解。設(shè)為主目標(biāo)。第一步：分別求解得得f1f2x(1)x(2)Mjmj-3063-1536

3、-30-15選定r=4:求解于是可得四組解，如圖15所示。j=2只有一個(gè)tf02t0123-15-8-16二、分層序列法：基本步驟：把(VP)中的p個(gè)目標(biāo)按其重要程度排一次序。依次求單目標(biāo)規(guī)劃的最優(yōu)解。2.過程：無妨設(shè)其次序?yàn)橄惹蠼獾米顑?yōu)值，記再解得最優(yōu)值，依次進(jìn)行，直到得最優(yōu)值則是在分層序列意義下的最優(yōu)解集合。3.性質(zhì)：，即在分層序列意義下的最優(yōu)解是有效解。證明：反證。設(shè)，但，則必存在使即至少有一個(gè)j0，使,由于，即，矛盾。得證。4.進(jìn)一步討論：上述方法過程中，當(dāng)某個(gè)問題(Pj)的解唯一時(shí)，則問題的求解無意義，因?yàn)榻舛际俏ㄒ坏?。?shí)際求解時(shí)，有較寬容意

4、義下的分層序列法：取為預(yù)先給定的寬容值，整個(gè)解法同原方法類似，只是取各約束集合時(shí)，分別取為：三、功效系數(shù)法：設(shè)目標(biāo)為：其中：要求min；要求max。由于量綱問題，處理目標(biāo)之間的關(guān)系時(shí)往往帶來困難。1.功效系數(shù)法：針對(duì)各目標(biāo)函數(shù)，用功效系數(shù)表示（俗稱“打分”）：滿足：或使最滿意時(shí)，最不滿意時(shí)（即最差時(shí)）。2.常用的兩種產(chǎn)生功效系數(shù)的方法：（1）線性型：設(shè)由于時(shí)求，令故取又時(shí)求，令故?。?）指數(shù)型：先討論求最大的函數(shù)，?？紤]：顯然，有如下性質(zhì)：10.當(dāng)充分大時(shí)，；20.是的嚴(yán)格遞增函數(shù)。（△）為了便于確定b0、b1，選取兩個(gè)估計(jì)值：取為合格值（勉強(qiáng)合格，即

5、可接受）；為不合格值（不合格，即不可接受）。令并取得解得：代入式(△)，得到功效系數(shù)：同理可得當(dāng)時(shí)的功效系數(shù)：3.利用功效系數(shù)求解問題(VP)：設(shè)(VP)的功效系數(shù)為令構(gòu)造問題：可以證明：上述問題(P)的最優(yōu)解，即原問題(VP)的有效解。四、評(píng)價(jià)函數(shù)法：1.理想點(diǎn)法：設(shè)，即各單目標(biāo)問題的最優(yōu)值。令評(píng)價(jià)函數(shù)，做為目標(biāo)函數(shù)。更一般地，取從不同角度出發(fā)，構(gòu)造評(píng)價(jià)函數(shù)h(F)，求問題,得到(VP)的有效解。下面介紹一些評(píng)價(jià)函數(shù)的構(gòu)造(即不同的方法)。2.平方和加權(quán)法：求出各單目標(biāo)問題最優(yōu)值的下界(期望的最好值)。令評(píng)價(jià)函數(shù)其中為預(yù)先確定的一組權(quán)數(shù)，且滿足的值為

6、各目標(biāo)函數(shù)的權(quán)數(shù)，較重要的取值較大。3.范數(shù)和加權(quán)法：同上面類似，先求出各單目標(biāo)問題的最優(yōu)值下界，取，構(gòu)造評(píng)價(jià)函數(shù)：其中為權(quán)系數(shù)，且。把此方法與分層序列法結(jié)合，取，用于線性多目標(biāo)規(guī)劃，即得到目標(biāo)規(guī)劃方法（運(yùn)籌學(xué)課中所學(xué)的）。4.虛擬目標(biāo)法：仍如“2、3”得到，設(shè)取評(píng)價(jià)函數(shù)：5.線性加權(quán)法：預(yù)先給出每一目標(biāo)函數(shù)的權(quán)系數(shù)，滿足。取評(píng)價(jià)函數(shù)：線性加權(quán)法是最常用的方法之一。此法可直接解釋(VP)有效解的Kuhn-Tucker條件?！鲙缀我饬x：設(shè)n=2,p=2。線性加權(quán)法解問題：在像空間，(P)等價(jià)為問題：記，則。及分別對(duì)應(yīng)單目標(biāo)問題(P1)及(P2)。當(dāng)正數(shù)確

7、定后，可得問題(PF)的最優(yōu)值，如圖18，可知對(duì)應(yīng)的原像。、?？梢岳镁€性加權(quán)法來逼近有效解的集合，但不是一種準(zhǔn)確尋找所有有效解的有效方法。當(dāng)μ從0→-∞時(shí)，可得到非劣解的一個(gè)子集。如上圖19所示。A、B為相應(yīng)集合的端點(diǎn)。當(dāng)或時(shí)，可能是弱有效解，如下圖20。只有，由A到B的其余點(diǎn)為弱有效點(diǎn)。它們對(duì)應(yīng)的原像為弱有效解。例7：其中：，F(xiàn)映射是由x1ox2到f1of2空間的一個(gè)線性變換?？尚杏蚴嵌喟蜨(A,B,C,D,E,F)。其A(0,0)T、B(6,0)T、C(6,2)T、D(4,4)T、E(1,4)T、F(0,3)T是每兩條直線的交點(diǎn)。F(A)=MA

8、=(0,0)T，F(xiàn)(B)=MB=(-30,6)T，F(xiàn)(C)=MC=(-26,-2)T，F(xiàn)(D)