第十一章 多目標(biāo)決策_(dá)
第十一章 多目標(biāo)決策 (Multi-objective Decision-making) 主要參考文獻(xiàn) 68, 111 §11.1 序言 MA： 評估與排序 MCDP MO： 數(shù)學(xué)規(guī)劃 一、問題的數(shù)學(xué)表達(dá) N個決策變量 [pic]= {[pic],[pic],…, [pic]} n個目標(biāo)函數(shù) [pic]([pic]) = ([pic]([pic]),[pic]([pic]),…, [pic]([pic])) m個約束條件 [pic](( 即: [pic]([pic])( 0 k=1,…,m [pic]( 0 (1) 不失一般性，MODP可表示成： P1 Max {[pic]([pic]),[pic]([pic]),…, [pic]([pic])} s.t. [pic](( 這是向量優(yōu)化問題，要在可行域X中找一[pic]，使各目標(biāo)值達(dá)到極大。 通常[pic]并不存在，只能找出一集非劣解[pic] 2) 若能找到價值函數(shù)v([pic]([pic]),[pic]([pic]),…, [pic]([pic])) 則MODP可表示成： P2 Max v ([pic]([pic]),[pic]([pic]),…, [pic]([pic])) s.t. [pic](( 這是純量優(yōu)化問題，困難在于v如何確定。 二、最佳調(diào)和解(Best Compromise Solution) P3 DR ([pic]([pic]),[pic]([pic]),…, [pic]([pic])) s.t. [pic](( 即根據(jù)適當(dāng)?shù)腄ecision Rule在X中尋找BCS [pic] 常用的Decision Rule: max V maxEU min [pic]([pic]-[pic]) 求BCS必須引入決策人的偏好 三、決策人偏好信息的獲取方式 1.在優(yōu)化之前，事先一次提供全部偏好信息 如：效用函數(shù)法，字典式法，滿意決策，目的規(guī)則 2.在優(yōu)化過程中：逐步索取偏好信息 如：STEM SEMOP Geoffrion, SWT 3.在優(yōu)化之后：事后索取偏好，由決策人在非劣解集中選擇 i. 算法復(fù)雜，決策人難理解， ii,計算量大， iii,決策人不易判斷各種方式的利弊比較 黃慶來[111]的分類表: [pic] §11.2 目的規(guī)劃法 適用場合： 決策人愿意并且能用 優(yōu)先級P (Preemptive priority) 權(quán) W (Weight) 目的[pic] ( Goal ) 來表示偏好 理想點(diǎn) [pic]( Ideal ) 一、距離測度的選擇 [pic] = [pic] 范數(shù)p的意義和作用 p=1 絕對值范數(shù) p=2 歐幾里德范數(shù) p =∞契比E夫范數(shù) [pic] 在上圖中，B、C點(diǎn)到A的距離 | |[pic]|[pic]|[pic]|[pic]|[pic]|[pic]| | | | |[pic]| | | | |AB間的距 |0 |6 |6 |6 |6 |6 | |離 | | | | | | | |AC間的距 |5 |4 |9 |6.4 |5.74 |5 | |離 | | | | | | | p從1→∞時最大偏差所起作用越來越大， 二、目的規(guī)劃問題的表述 min{[pic] = [pic]} s. t. [pic](( 即: [pic]([pic])( 0 k=1,…,m [pic]( 0 三、分類 1.線性目的規(guī)劃 p = 1 [pic], [pic]為線性; [pic]連續(xù); w, [pic]事先給定 2.整數(shù)目的規(guī)劃 除[pic]各分量為整數(shù)外，均同線性目的規(guī)劃 (例：人才規(guī)劃) 3.非線性目的規(guī)劃： p=1， w, [pic]事先給定 [pic], [pic] 為非線性，X為凸集，[pic]連續(xù) 4.調(diào)和規(guī)劃和移動理想點(diǎn)法: 1( p(( w事先給定 [pic]= [pic] 是移動的理想點(diǎn) 5. 字典序法 p = 1 [pic]= [pic] P1》P2》…》PL 6.STEM法 P=∞ [pic]= [pic]為理想點(diǎn)，權(quán)由計算得出 7.SEMOP 目的標(biāo)定為區(qū)間，不是固定點(diǎn) 四、例： 某車間生產(chǎn)甲、乙兩種產(chǎn)品，產(chǎn)量分別為[pic]和[pic]，產(chǎn)品甲每單位需2個單位的勞動 力和3個單位 原料,利潤為2；生產(chǎn)產(chǎn)品乙需3個單位勞動力和1.5個單位原料,利潤為3。在下一計劃期 間車間有12單勞動力12單位原料。 假定車間主任有如下目標(biāo)： 1) 利潤至少為6個單位， (2)兩種產(chǎn)品產(chǎn)量經(jīng)盡可能保持[pic]：[pic]= 3：2， 3) 勞動力充分利用 解：按傳統(tǒng)的線性規(guī)劃，使利潤最大： max 2[pic]+ 3[pic] s. t. 2[pic]+ 3[pic]≤12 (勞力約束) 3[pic]+1.5[pic]≤12 (原料約束) [pic], [pic]≥0 用圖解法可得[pic]=3, [pic]=2時,利潤最大為12. [pic] 五、例(續(xù)上例) 已知條件中產(chǎn)品甲利潤改為4, 其余均不變。 車間主任希望改為: 最低利潤12單位 2) 產(chǎn)量比例為1, 即[pic]=[pic]; (3)充分利用原料 解: 新的目標(biāo)為 4[pic]+3[pic]≥12 (最低限度利潤) [pic]- [pic] = 0 (產(chǎn)量比例) 3[pic]+1.5[pic]=12 (材料充分利用) 設(shè)定偏差變量 [pic]: 利潤 [pic]: 產(chǎn)量比例 [pic]: 原料 [pic]:勞動力 利用正、負(fù)偏差變量可得： min P1[pic][pic]+ P2([pic][pic]+[pic][pic]) + P3[pic][pic] s. t. 4[pic]+3[pic]-[pic][pic]+[pic][pic]≥12 (利潤目標(biāo)) [pic]- [pic] -[pic] + [pic][pic]= 0 (產(chǎn)量比例) 3[pic]+1.5[pic] + [pic][pic] =12 (材料充分利用) 2[pic]+ 3[pic] + [pic][pic] =12 (勞動力約束) 本題可以用改進(jìn)的單純形法求解(見pp217-221), 也可用圖解法求解: [pic] 解得[pic]= (2.4, 2.4) , [pic][pic]=[pic][pic]=[pic][pic]=[pic][pic]=0 , [pic][pic]=1.2 , [pic][pic]=4.8 §11.3字典序法 第一步，由決策人給出n，按重要性由高到低排成 [pic],[pic],…, [pic] 第二步，用適當(dāng)方法估計各屬性的偏好(效用或價值)函數(shù) [pic]([pic]), [pic]([pic]), …, [pic]([pic]) 第三步，依次求解下列問題，進(jìn)行篩選 問題P1 [pic] 解為[pic] 問題P2 [pic] 解為[pic] … … 問題Pj [pic] 直到 a) 問題Pj 只有唯一解, 則該解為最優(yōu)解 b) n個問題全部解過：決策人用其他準(zhǔn)則從[pic]中選擇一個方案。 §11.4 逐步進(jìn)行法(STEP Method) 特點(diǎn)：P=∞ 只有最大偏差起作用 屬于Min max 決策規(guī)則 算法步驟 對多目標(biāo)決策問題 max{[pic]=C[pic]} s. t. A[pic]≤b [pic] ≥0 記作[pic] 第一步 求解n個單目標(biāo)優(yōu)化問題 [pic] j=1,…,n 解為 [pic]得[pic]= [pic] 理想點(diǎn) [pic]= ([pic],…,[pic]) 列出支付表——使決策人對取不同的[pic]時各目標(biāo)的值有直觀認(rèn)識[pic] | |[pic]|… |[pic]|… |[pic]| |[pic|[pic]|… |[pic]|… |[pic]| |] | | | | | | |… |… |… |… |… |… | |[pic|[pic]|… |[pic]|… |[pic]| |] | | | | | | |… |… |… |… |… |… | |[pic|[pic]|… |[pic]|… |[pic]| |] | | | | | | 第二步 由 [pic] = max[pic] 求解 min [pic] s. t. [pic] 等價于解 min入 s. t. λ≥[pic] j=1,…,n [pic] λ≥0 其中 [pic] j=1,…,n [pic][pic] 式中 [pic]從支付表中獲得 ·解(2)得 [pic]與 [pic] j=1,…,n 第三步 由決策人判斷 降低某個太好的目標(biāo) [pic]，下降[pic]再修改約束條件，使 A[pic]≤b [pic]≥0 [pic]: [pic]=[pic]-[pic] [pic]≥[pic] j=1,…,n j≠[pic] 以[pic]取代[pic]，令[pic]=0重復(fù)第二步 三、優(yōu)缺點(diǎn)： 直觀; 修改有針對性; [pic]較難定 §11.5 調(diào)和解(Compromise solution)和移動理想點(diǎn)法 一、基本概念(思路) 1.調(diào)和解 [pic] 在求解MODP: [pic][pic] 時 [pic](或[pic]), W , p要由決策人確定 其中 ·由單調(diào)性假設(shè)，[pic]=[pic][pic] j=1,…,n可以求得 ·W可由決策人設(shè)定 而P則很難設(shè)定 因此，給定權(quán)向量W，定義調(diào)和解集 [pic] = {[pic]|[pic]是給定W時[pic][pic]的解} 它是非劣解的子集, 即 [pic]([pic] 2.各目標(biāo)偏差的規(guī)范化 記[pic]= [pic][pic] 用[pic]使偏差無量綱、歸一化，否則[pic]量綱、單位的選取有關(guān) 二、求解步驟 第一步 由決策人估計權(quán)W 第二步 [pic]= [pic][pic] [pic]=[pic][pic] 第三步 構(gòu)造調(diào)和集 求解 [pic][pic] p=1,2,∞ 其中 [pic][pic] [pic][[pic]][pic] [pic][pic] 第四步 若能從[pic]中找出BCS，則結(jié)束 第五步 尋找新的理想點(diǎn) 令 [pic]=[pic] 返回第二步. §11.6 SEMOP(多目標(biāo)問題的序貫解法) 一、思路與記號 目的為區(qū)間 |目的類|目的表達(dá)式 |偏差測度 [pic] | |型 | | | |有上界|[pic]≤[pic] |[pic]/[pic] | |有下界|[pic]≥[pic] |[pic]/[pic] | |給定值|[pic]= [pic] |[pic] | |區(qū)間內(nèi)|[pic]≤[pic]≤[pic]|[pic] | |區(qū)間外|[pic]≤[pic],[pic]|[pic] | | |≥[pic] | | ·n個目標(biāo)分為兩類: [pic]：加約束的r個目標(biāo)的下標(biāo)集合； [pic]=J[pic] J={1,2,…,n} [pic]：X中的子集，其中的[pic]使 (j([pic], [pic]在標(biāo)定區(qū)間內(nèi) 求解min{[pic]} s. t. [pic] 將解[pic]與 [pic] j=1,…,n送決策人判斷 為了向決策人提供必要信息需解(n-r)個輔問題 min{[pic]} s. t. [pic] 其中, [pic]=1,…,n-r p是[pic]中第[pic]個元素在J中的序號 [pic]是j([pic]以及j=p的[pic]均嚴(yán)格處于標(biāo)定的目的區(qū)間內(nèi) 二、解題步驟 第一步 由決策人確定r個應(yīng)嚴(yán)格限定值域的目標(biāo)，并給出這r個目標(biāo)的目的區(qū)間，這r個目標(biāo)的序 號構(gòu)成集合[pic] 第二步 i, 解主問題 min{[pic]} s. t. [pic] ii, 解n-r個輔問題 min{[pic]} s. t. [pic] 得出[pic]與 [pic] j=1,…,n 和 [pic]與 [pic] j=1,…,n [pic]=1,…,n-r 第三步 由決策人對第二步結(jié)果作判斷 基對[pic]滿意則停止 若 不滿意則q=q+1返回第一步 三、優(yōu)缺點(diǎn) 1.可用于非單調(diào)區(qū)間 2.容易反映目標(biāo)間的矛盾關(guān)系 3.非線性規(guī)劃問題求解困難,沒有規(guī)范化的步驟保證收斂 §11.7Geoffrion法 一、思路 用Frank-Wolfe法解線性約束的非線性規(guī)劃問題 max v([pic]) (0) s. t. [pic] 是在[pic] 處，以一階Taylor展開[pic]線性逼接v([pic])[記作v([pic])]: [pic]= v([pic]) + [[pic]][pic]([pic]-[pic]) (1) 求(1)的極大值等價于求解線性規(guī)劃問題 [pic][[pic]][pic]·[pic] (2) 令(2)的最優(yōu)解為[pic]，則 i,若 [[pic]][pic]([pic]-[pic]) 是(2)的最優(yōu)解，迭代停止； ii,若[[pic]][pic]([pic]-[pic])(0, 則從[pic]出發(fā)沿[pic]-[pic]方向作一維搜索 即求 [pic]v([pic]+[pic]([pic]-[pic]))的最優(yōu)解[pic] 只要 [pic](0足夠小, 必有 v([pic])(v([pic]) 式中 [pic]= [pic]+[pic]([pic]-[pic]) 對[pic]，重復(fù)上述步驟，可得原問題(0)的最優(yōu)解 [pic]雖屬未知，但[pic]=[pic] [pic] 除以[pic], 得[pic][pic] 其中，[pic](-[pic] j=1,…,n 二、求解步驟 2. 三、優(yōu)缺點(diǎn) 1.只要決策者心目中的效用函數(shù)確實(shí)存在，并能給出各點(diǎn)的邊際置換率，不必給出具體 的 效用函數(shù)值。 2.只適用于線性約束的多目標(biāo)規(guī)劃 3.每次迭代 都有所增加，收斂性有保證 但在實(shí)際上所得到的解的優(yōu)劣取決于決策人提供的局部偏好信息的準(zhǔn)確性。 §11.8 代理值置換法(Surrogate worth Trade-off Method) 一、思路： ·置換率：在某個非劣點(diǎn)處若要提高某一目標(biāo)值一個單位，必須使另一目標(biāo)降低多少，( 設(shè) 其他目標(biāo)函數(shù)值不變) 置換率給出了非常有用的信息: 如決策人愿意進(jìn)行這種置換，說明該方向上有決策人更喜愛的非劣解。 二、求解步驟 第一步：產(chǎn)生非劣解的有代表性的子集 任選一種方法去求得非劣解的有代表性的子集。 不失一般性，選[pic]作為參考目標(biāo)，構(gòu)成不等式約束問題: min [pic] (1) s. t. [pic] i=1,…,m [pic] j=1,…,n-1 其中, [pic] [pic] [pic] 為了便于比較，最好選用重要目標(biāo)或其計量單位是決策人所熟悉的目標(biāo)作為目標(biāo)n。 第二步：獲得置換信息 在求解(1)時，可以得到 [pic] j=1,…,n-1 其中[pic]是(1)的解，[pic] 是(1)的Kuhn-Tucker乘子， 就是在[pic]處的置換率 第三步：了解決策人的偏好 把第二步計算結(jié)果遞交給決策人，要決策人回答是否愿意進(jìn)行這種調(diào)整，愿意到何種 程度，并據(jù)以構(gòu)造代用值函數(shù)[pic] j=1,…,n-1 +10 非常愿意增加[pic]個單位的[pic]減去一個單位的[pic] -10 非常愿意減少 [pic]個單位的[pic]以提高 [pic]一個單位 第四步：尋求最佳調(diào)和解 當(dāng)某個[pic]使 [pic]=0 j=1,…,n-1時, [pic]為最佳調(diào)和解. 若在第一步生成的非劣點(diǎn)中不包含[pic]，可用多元回歸法構(gòu)造代理值函數(shù)[pic] 令[pic]=0 即 [pic]=0 求解聯(lián)列方程 得 [pic] 可用這組 [pic]代入(1)求得[pic] .
第十一章 多目標(biāo)決策_(dá)