多目標(biāo)規(guī)劃求解方法介紹

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

得解；〔2〕計算對應(yīng)的各目標(biāo)函數(shù)值，并對每個函數(shù)，求其p個點值中的最大值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個不同閥值：第三步：對，分別求解問題：各目標(biāo)函數(shù)可對應(yīng)不同的〔共有個約束問題〕。求解后可得到(VP)的一有效解集合，是(VP)有效解集合的一個子集。編輯課件例6：用約束法求解。設(shè)為主目標(biāo)。第一步：分別求解

得得f1f2x(1)x(2)Mjmj-3063-1536-30-15編輯課件選定r=4:求解于是可得四組解，如圖15所示。j=2只有一個tf02t0123-15-8-16編輯課件編輯課件二、分層序列法：根本步驟：把(VP)中的p個目標(biāo)按其重要程度排一次序。依次求單目標(biāo)規(guī)劃的最優(yōu)解。2.過程：無妨設(shè)其次序為先求解得最優(yōu)值，記再解得最優(yōu)值，依次進行，直到得最優(yōu)值那么是在分層序列意義下的最優(yōu)解集合。編輯課件3.性質(zhì)：，即在分層序列意義下的最優(yōu)解是有效解。證明：反證。設(shè)，但，那么必存在使即至少有一個j0，使,由于，即，矛盾。得證。4.進一步討論：上述方法過程中，當(dāng)某個問題(Pj)的解唯一時，那么問題的求解無意義，因為解都是唯一的。實際求解時，有較寬容意義下的分層序列法：取為預(yù)先給定的寬容值，整個解法同原方法類似，只是取各約束集合時，分別取為：編輯課件三、成效系數(shù)法：設(shè)目標(biāo)為：其中：要求min；要求max。由于量綱問題，處理目標(biāo)之間的關(guān)系時往往帶來困難。1.成效系數(shù)法：針對各目標(biāo)函數(shù)，用成效系數(shù)表示〔俗稱“打分〞〕：滿足：或使最滿意時，最不滿意時〔即最差時〕。2.常用的兩種產(chǎn)生成效系數(shù)的方法：〔1〕線性型：設(shè)編輯課件由于時求，令故取又時求，令故取〔2〕指數(shù)型：先討論求最大的函數(shù)，?？紤]：顯然，有如下性質(zhì)：10.當(dāng)充分大時，；20.是的嚴(yán)格遞增函數(shù)。（△）編輯課件為了便于確定b0、b1，選取兩個估計值：取為合格值〔勉強合格，即可接受〕；為不合格值〔不合格，即不可接受〕。令并取得解得：代入式(△)，得到成效系數(shù)：同理可得當(dāng)時的成效系數(shù)：編輯課件編輯課件3.利用成效系數(shù)求解問題(VP)：設(shè)(VP)的成效系數(shù)為令構(gòu)造問題：可以證明：上述問題(P)的最優(yōu)解，即原問題(VP)的有效解。四、評價函數(shù)法：1.理想點法：設(shè)，即各單目標(biāo)問題的最優(yōu)值。令評價函數(shù)，做為目標(biāo)函數(shù)。更一般地，取編輯課件從不同角度出發(fā)，構(gòu)造評價函數(shù)h(F)，求問題,得到(VP)的有效解。下面介紹一些評價函數(shù)的構(gòu)造(即不同的方法)。2.平方和加權(quán)法：求出各單目標(biāo)問題最優(yōu)值的下界(期望的最好值)。令評價函數(shù)其中為預(yù)先確定的一組權(quán)數(shù)，且滿足的值為各目標(biāo)函數(shù)的權(quán)數(shù)，較重要的取值較大。編輯課件3.范數(shù)和加權(quán)法：同上面類似，先求出各單目標(biāo)問題的最優(yōu)值下界，取，構(gòu)造評價函數(shù)：其中為權(quán)系數(shù)，且。把此方法與分層序列法結(jié)合，取，用于線性多目標(biāo)規(guī)劃，即得到目標(biāo)規(guī)劃方法〔運籌學(xué)課中所學(xué)的〕。4.虛擬目標(biāo)法：仍如“2、3〞得到，設(shè)取評價函數(shù)：編輯課件5.線性加權(quán)法：

預(yù)先給出每一目標(biāo)函數(shù)的權(quán)系數(shù)，滿足。取評價函數(shù)：線性加權(quán)法是最常用的方法之一。此法可直接解釋(VP)有效解的Kuhn-Tucker條件。△幾何意義：

設(shè)n=2,p=2。線性加權(quán)法解問題：編輯課件在像空間，(P)等價為問題：記，那么。及分別對應(yīng)單目標(biāo)問題(P1)及(P2)。當(dāng)正數(shù)確定后，可得問題(PF)的最優(yōu)值，如圖18，可知對應(yīng)的原像。、。編輯課件可以利用線性加權(quán)法來逼近有效解的集合，但不是一種準(zhǔn)確尋找所有有效解的有效方法。當(dāng)μ從0→-∞時，可得到非劣解的一個子集。如上圖19所示。A、B為相應(yīng)集合的端點。當(dāng)或時，可能是弱有效解，如以下圖20。只有，由A到B的其余點為弱有效點。它們對應(yīng)的原像為弱有效解。例7：編輯課件其中：，F(xiàn)映射是由x1ox2到f1of2空間的一個線性變換。可行域是多胞形H(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是每兩條直線的交點。F(A)=MA=(0,0)T，F(xiàn)(B)=MB=(-30,6)T，F(xiàn)(C)=MC=(-26,-2)T，F(xiàn)(D)=MD=(-12,-12)T，F(xiàn)(E)=ME=(3,-15)T，F(xiàn)(F)=MF=(6,-12)T。F(S)是由F(A)、F(B)、F(C)、F(D)、F(E)、F(F)構(gòu)成的多胞形。如圖21。編輯課件圖21：編輯課件

當(dāng),即時,即(P2)的解:E(1,4)T,對應(yīng)F(E)=(3,-15)T；當(dāng),即時,即(P1)的解:B(6,0)T,對應(yīng)F(B)=(-30,6)T；

取μ=-1,即時,問題為：最優(yōu)解為:C(6,2)T,對應(yīng)F(C)=(-26,-2)T；取μ=-1/2,即時,問題為：最優(yōu)解為:D(4,4)T,對應(yīng)F(D)=(-12,-12)T；

取μ=-1/3,即時,問題為:最優(yōu)解為:D(4,4)T,對應(yīng)F(D)=(-12,-12)T。編輯課件6.“min-max〞法〔極小-極大法〕對策論中常遇到“在最不利情況下找出最有利策略〞的問題，即“min-max〞問題。取評價函數(shù)然后求解設(shè)得解,是x的函數(shù)。如右圖。實用中，可以使用以下加權(quán)形式，取，令編輯課件為了求解方便，可把問題(PMm)等價化為以下數(shù)學(xué)規(guī)劃問題:定理：設(shè)是的最優(yōu)解，那么為(PMm)的最優(yōu)解；反之，假設(shè)是(PMm)的最優(yōu)解,且那么是的最優(yōu)解。證：設(shè)是問題的最優(yōu)解，明顯地，有由第一組約束知：由目標(biāo)mint知取得滿足上式的最小值。對(PMm)的任意可行解x，令那么。于是即是問題(PMm)的最優(yōu)解。編輯課件反之，考慮是的任意可行解，那么〔第一組約束〕是(PMm)的最優(yōu)解，可得，對(PMm)的任意可行解x，有于是。即為的最優(yōu)解。7.乘除法：設(shè)(VP)中，對，均有再設(shè)求min；求max。取評價函數(shù)

求解，。編輯課件8.評價函數(shù)法的收斂性：考慮(VP)，h(F(x))為評價函數(shù)。定義：設(shè)，10.假設(shè)滿足時，均有，那么稱h(F)是F的嚴(yán)格單調(diào)增函數(shù)；20.假設(shè)滿足：當(dāng)時，均有，那么稱h(F)是F的單調(diào)增函數(shù)。定理：假設(shè)，10.假設(shè)h(F)是嚴(yán)格單調(diào)增函數(shù)，那么數(shù)學(xué)規(guī)劃的最優(yōu)解；20.假設(shè)h(F)是單調(diào)增函數(shù)，那么數(shù)學(xué)規(guī)劃的最優(yōu)解。編輯課件證明：10.反證。設(shè)，由定義，使由h(F)的單調(diào)增性質(zhì)，得到與是(P1)的最優(yōu)解矛盾。20.反證。設(shè)，由定義，使由h(F)的單調(diào)增性質(zhì)，得到與是(P2)的最優(yōu)解矛盾。證畢。

可以證明，上述各評價函數(shù)：1.理想點法、2.平方和加權(quán)法、范數(shù)和加權(quán)法、4.虛擬目標(biāo)法、5.線性加權(quán)法()、7.乘除法均為嚴(yán)格單調(diào)增函數(shù)；而5.線性加權(quán)法()、6.min-max方法為單調(diào)增函數(shù)。由此，根據(jù)定理可得，方法5(線性加權(quán)法())方法6(min-max法)得到的解；其它各方法得到的解。編輯課件9.確定權(quán)系數(shù)的方法：(VP)問題的評價函數(shù)h(F(x))中所需預(yù)先給出的權(quán)系數(shù)：〔1〕“老手法〞根本過程：邀請一批“老手〞〔專家，有經(jīng)驗的人員等〕，汲取他們對權(quán)系數(shù)的意見，加以綜合得到權(quán)系數(shù)。設(shè)有k位“老手〞，為了便于其獨立發(fā)表意見，將事先準(zhǔn)備好的調(diào)查表送給他們分別填寫。設(shè)第i位“老手〞對第j個目標(biāo)給出的權(quán)系數(shù)為。針對每個目標(biāo)函數(shù)，計算平均權(quán)系數(shù)：得到下表：編輯課件計算每一位老手i(i=1,2,…,k)關(guān)于平均權(quán)系數(shù)評價的偏差：。第二輪討論，請最大偏差的老手首先發(fā)表意見，經(jīng)充分討論以到達(dá)對目標(biāo)重要度的正確認(rèn)識，消除參數(shù)估計中的誤解。然后重新評價。如此反復(fù)進行，最后到達(dá)較為一致的認(rèn)識。編輯課件〔2〕α-方法：對p=2的情形表達(dá)：求的最優(yōu)解。記，像空間的圖形如下〔圖23〕。在像空間中，點確定一條直線L1，記其方程為。把上面兩個點的坐標(biāo)代入，得到：。假設(shè)問題(VP)不存在絕對最優(yōu)解(存在絕對最優(yōu)解時，上述方程組為一個點，)，即。那么有記，解方程組得：

編輯課件取這組時，線性加權(quán)法的最優(yōu)解對應(yīng)的像點為，如圖23。對于一般情況：p≥2。

記單目標(biāo)問題的最優(yōu)解為，記過p個點做超平面，得方程組

當(dāng)(VP)不存在唯一解時，可確定唯一一組解(共p+1個變量，p+1個方程)。該解即為一組權(quán)系數(shù)。編輯課件10.有限方案多目標(biāo)決策問題簡介前述的一些方法均是針對無限方案多目標(biāo)決策問題的模型進行討論的。也是在這一領(lǐng)域中遇到較多的且要求根底知識較深的一局部內(nèi)容?！?〕有限方案多目標(biāo)決策問題的特征及根本思路：特征：僅含有限多個方案；決策情況的范圍只涉及分析-評價的內(nèi)容。根本解題思路：篩選→排序→集結(jié)→綜合①篩選：對有限個可能方案，按照某種(些)準(zhǔn)那么，篩去顯著不滿意的方案，使下一步所考慮的方案盡可能的少；②排序：根據(jù)各屬性特征給各屬性賦權(quán)。然后，按照不同的方法，給各方案排序。③集結(jié)：常用三種技術(shù)，對上步得到的不同方法下各方案的排序進行集結(jié)(按不同技術(shù)的綜合評價)。有以下三種技術(shù)：編輯課件常用的集結(jié)方法：Δ平均值法：求各方案在不同方法下名次的平均值。按平均值的大小得到集結(jié)名次，假設(shè)平均值相同時，那么取方差較小的排在前。例8：有四個方案，用四種方法進行排序，得到下表：對各方案兩兩比較(如xi與xj)，假設(shè)認(rèn)為xi好于xj的方案多，記為勝(M)，否那么記為敗(X)(不優(yōu)于)。ΔBorda法：找各方案“勝〞的次數(shù)之和，進行集結(jié)。編輯課件ΔCopaland法：找各方案“勝〞(取正)與“敗〞(取負(fù))次數(shù)的代數(shù)和，進行集結(jié)。例9：同上例，結(jié)果如下。④綜合：上步得到三種技術(shù)下的排序，一般仍存在不可比的關(guān)系。構(gòu)造一排序集：當(dāng)xi優(yōu)于xj時，記為