多目標(biāo)規(guī)劃求解方法介紹（37頁)ppt課件

1、3.3 多目的規(guī)劃求解方法引見一、約束法1.根本思想：在多個目的函數(shù)中選擇一個主要目的作為目的函數(shù)，其它目的處置為適當(dāng)?shù)募s束。無妨設(shè) 為主要目的，對其它各目的 可預(yù)先給定一個期望值，無妨記為 ，那么有求解以下問題： 容易證明，約束法求問題(P)的最優(yōu)解，其Kuhn-Tucker條件與(VP)有效解的K-T條件一致。 因此，約束法求得的解是有效解。 (P)問題中各目的函數(shù)期望值的獲得有多種方法，一種方法是取一點 ，而取 得到以下問題：2. 算法普通步驟： 思索上述(VP)問題， 為主目的。第一步：1對 ，求解單目的問題： 得解 ；2計算 對應(yīng)的各目的函數(shù)值，并對每個函數(shù) ，求其p個點值中的最大值

2、Mj和最小值mj。得到下表： Mj與mj規(guī)定了 在有效解集中的取值范圍。x(1)x(p)f 1(x) f 2(x) f p(x) m 1 m 2 m pf 1(x(1) f 2(x(1) f p(x(1)f 1(x(p) f 2(x(p) f p(x(p) M 1 M 2 M pMjmj第二步：選擇整數(shù)r1，確定 的r個不同閥值：第三步：對 ，分別求解問題：各目的函數(shù) 可對應(yīng)不同的 共有 個約束問題。求解后可得到(VP)的一有效解集合，是(VP)有效解集合的一個子集。例6：用約束法求解。設(shè) 為主目的。第一步：分別求解 得得f1f2x(1)x(2)Mjmj-3063-1536-30-15選定r=

3、4:求解于是可得四組解，如圖15所示。 j=2只需一個 tf 02t 0 1 2 3 -15 -8 -1 6二、分層序列法：根本步驟：把(VP)中的p個目的 按其重要程度排一次序。依次求單目的規(guī)劃的最優(yōu)解。2. 過程：無妨設(shè)其次序為 先求解 得最優(yōu)值 ，記再解 得最優(yōu)值 ，依次進(jìn)展，直到 得最優(yōu)值那么 是在分層序列意義下的最優(yōu)解集合。3. 性質(zhì)： ，即在分層序列意義下的最優(yōu)解是有效解。證明：反證。設(shè) ，但 ，那么必存在 使 即至少有一個j0 ，使 , 由于 ，即 ， 矛盾。得證。4. 進(jìn)一步討論： 上述方法過程中，當(dāng)某個問題(Pj)的解獨一時，那么問題 的求解無意義，由于解都是獨一的。 實踐求

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

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

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

7、數(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空間的一個線性變換?？尚杏蚴嵌喟蜨(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)=M

8、A= (0,0)T ， F(B)=MB= (-30,6)T ，F(xiàn)(C)=MC= (-26,-2)T ， F(D)=MD= (-12,-12)T ，F(xiàn)(E)=ME= (3,-15)T ， F(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 ,

9、 對應(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法極小-極大法 對策論中常遇到“在最不利情況下找出最有利戰(zhàn)略的問題，即“min-max問題。 取評價函數(shù)然后求解 設(shè)得解 ,是x的函數(shù)。如右圖。 適用中，可以運用以下加權(quán)方式，取 ，令 為了求解方便，可把問題(PMm)等價化為以下數(shù)學(xué)規(guī)劃問題:定理：設(shè) 是 的最優(yōu)解，那么 為(PMm)的最優(yōu) 解；反之，假設(shè)

10、 是(PMm)的最優(yōu)解, 且 那么 是 的最優(yōu)解。證：設(shè) 是問題 的最優(yōu)解，明顯地，有 由第一組約束知： 由目的min t知 獲得滿足上式的最小值。 對(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.

11、假設(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.虛擬目的法、5.線性加權(quán)法( )、7.乘除法均為嚴(yán)厲單調(diào)增函數(shù)；而5.線性加權(quán)法( )、6. min-max方法為單調(diào)增函數(shù)。 由此，

12、根據(jù)定理可得，方法5(線性加權(quán)法( )方法6(min-max法)得到的解 ；其它各方法得到的解 。9.確定權(quán)系數(shù)的方法： (VP)問題的評價函數(shù)h(F(x)中所需預(yù)先給出的權(quán)系數(shù)：1“老手法根本過程：約請一批“老手專家，有閱歷的人員等， 汲取他們對權(quán)系數(shù)的意見，加以綜合得到權(quán)系數(shù)。 設(shè)有k位“老手，為了便于其獨立發(fā)表意見，將事先預(yù)備好的調(diào)查表送給他們分別填寫。設(shè)第i位“老手對第j個目的 給出的權(quán)系數(shù)為 。 針對每個目的函數(shù) ，計算平均權(quán)系數(shù)：得到下表： 計算每一位老手i(i=1,2,k)關(guān)于平均權(quán)系數(shù) 評價的偏向： 。 第二輪討論，請最大偏向的老手首先發(fā)表意見，經(jīng)充分討論以到達(dá)對目的重要度的正

13、確認(rèn)識，消除參數(shù)估計中的誤解。然后重新評價。 如此反復(fù)進(jìn)展，最后到達(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。 對于普通情況：p2 。 記單目的問題 的最優(yōu)解為 ，記過p個點 做超平面，得方程組 當(dāng)(VP)不存在獨一解時，可確定獨一一組解( 共p+1個變量，p+1個方程 )。 該解 即

14、為一組權(quán)系數(shù)。10.有限方案多目的決策問題簡介 前述的一些方法均是針對無限方案多目的決策問題的模型進(jìn)展討論的。也是在這一領(lǐng)域中遇到較多的且要求根底知識較深的一部分內(nèi)容。1有限方案多目的決策問題的特征及根本思緒：特征：僅含有限多個方案； 決策情況的范圍只涉及分析-評價的內(nèi)容。根本解題思緒：挑選排序集結(jié)綜合挑選：對有限個能夠方案，按照某種(些)準(zhǔn)那么，篩去顯著不稱心的方案，使下一步所思索的方案盡能夠的少；排序：根據(jù)各屬性特征給各屬性賦權(quán)。然后，按照不同的方法，給各方案排序。集結(jié)：常用三種技術(shù)，對上步得到的不同方法下各方案的排序進(jìn)展集結(jié)(按不同技術(shù)的綜合評價)。有以下三種技術(shù)：常用的集結(jié)方法： 平均

15、值法：求各方案在不同方法下名次的平均值。按平均值的大小得到集結(jié)名次，假設(shè)平均值一樣時，那么取方差較小的排在前。例8：有四個方案 ，用四種方法 進(jìn)展 排序，得到下表： 對各方案兩兩比較(如xi與xj)，假設(shè)以為xi好于xj的方案多，記為勝(M)，否那么記為敗(X)(不優(yōu)于)。 Borda法：找各方案“勝的次數(shù)之和，進(jìn)展集結(jié)。 Copaland法：找各方案“勝(取正)與“敗(取負(fù))次數(shù)的代數(shù)和，進(jìn)展集結(jié)。例9：同上例，結(jié)果如下。綜合：上步得到三種技術(shù)下的排序，普通仍存在不可比的關(guān)系。構(gòu)造一排序集：當(dāng)xi優(yōu)于xj時，記為 ，否那么以為不可比。當(dāng) 時，節(jié)點xi位于xj上，這樣得到一個偏序構(gòu)造圖：2決策

16、矩陣和規(guī)范化決策矩陣：把各方案xi (i=1,2,m)及屬性集yj(j=1, ,n) 、 列表得到?jīng)Q策矩陣。其中 (方案xi的第j個屬性值)。向量規(guī)范化：(化為無量綱值 ) 普通達(dá)不到0或1。x1x4x5x2x3-第1等級-第2等級-第3等級 計算線性變換規(guī)范化：(使 ) 假設(shè)求最大時：(效益) , 求最小時：(本錢) ,其它規(guī)范化變換：(一致變換后的屬性)求最大時：求最小時：一致最優(yōu)時： ；最劣時： 。3權(quán)系數(shù)確實定： 普通采用類似層次分析法中的兩兩比較判別, 構(gòu)造判別矩陣， 用特征根法, 或和積法, 方根法求特征向量的方法確定權(quán)系數(shù)。理想最優(yōu)時最劣時4常用的挑選方案的方法：優(yōu)選法：利用非劣