1、第十一章 多目標決策(Multi-objective Decision-making) 主要參考文獻 68, 111 §11.1 序言 MA： 評估與排序 MCDP MO： 數學規劃一、問題的數學表達 N個決策變量 = , n個目標函數 () = (),(), ()m個約束條件 ÎC 即: ()< 0 k=1,m > 0(1) 不失一般性，MODP可表示成： P1 Max (),(), () s.t. ÎC 這是向量優化問題，要在可行域X中找一，使各目標值達到極大。 通常并不存在，只能找出一集非劣解(2) 若能找到價值函數v(),(), () 則MOD

2、P可表示成： P2 Max v (),(), () s.t. ÎC這是純量優化問題，困難在于v如何確定。二、最佳調和解(Best Compromise Solution)P3 DR (),(), () s.t. ÎC即根據適當的Decision Rule在X中尋找BCS 常用的Decision Rule: max V maxEU min (-)求BCS必須引入決策人的偏好三、決策人偏好信息的獲取方式1.在優化之前，事先一次提供全部偏好信息 如：效用函數法，字典式法，滿意決策，目的規則2.在優化過程中：逐步索取偏好信息如：STEM SEMOP Geoffrion, SWT3.

3、在優化之后：事后索取偏好，由決策人在非劣解集中選擇i， 算法復雜，決策人難理解， ii,計算量大，iii,決策人不易判斷各種方式的利弊比較黃慶來111的分類表:§11.2 目的規劃法適用場合：決策人愿意并且能用 優先級P (Preemptive priority) 權 W (Weight) 目的 ( Goal ) 來表示偏好 理想點 ( Ideal )一、距離測度的選擇 = 范數p的意義和作用p=1 絕對值范數p=2 歐幾里德范數p =契比E夫范數在上圖中，B、C點到A的距離AB間的距離066666AC間的距離5496.45.745p從1時最大偏差所起作用越來越大，二、目的規劃問題的

4、表述min = s. t. ÎC 即: ()< 0 k=1,m > 0三、分類1.線性目的規劃 p = 1 , 為線性; 連續; w, 事先給定2.整數目的規劃 除各分量為整數外，均同線性目的規劃 (例：人才規劃)3.非線性目的規劃： p=1， w, 事先給定 , 為非線性，X為凸集，連續4.調和規劃和移動理想點法: 1£ p£¥ w事先給定 = 是移動的理想點5. 字典序法 p = 1 = P1P2PL6.STEM法 P= = 為理想點，權由計算得出7.SEMOP 目的標定為區間，不是固定點四、例：某車間生產甲、乙兩種產品，產量分別為和，產

5、品甲每單位需2個單位的勞動力和3個單位原料,利潤為2；生產產品乙需3個單位勞動力和1.5個單位原料,利潤為3。在下一計劃期間車間有12單勞動力12單位原料。假定車間主任有如下目標：(1) 利潤至少為6個單位，(2)兩種產品產量經盡可能保持：= 3：2，(3) 勞動力充分利用解：按傳統的線性規劃，使利潤最大： max 2+ 3 s. t. 2+ 312 (勞力約束) 3+1.512 (原料約束) , 0用圖解法可得=3, =2時,利潤最大為12.五、例(續上例)已知條件中產品甲利潤改為4, 其余均不變。車間主任希望改為: 最低利潤12單位(2) 產量比例為1, 即=; (3)充分利用原料解: 新

6、的目標為 4+312 (最低限度利潤) - = 0 (產量比例) 3+1.5=12 (材料充分利用)設定偏差變量 : 利潤 : 產量比例 : 原料 :勞動力利用正、負偏差變量可得： min P1+ P2(+) + P3s. t. 4+3-+12 (利潤目標) - - + = 0 (產量比例) 3+1.5 + =12 (材料充分利用) 2+ 3 + =12 (勞動力約束)本題可以用改進的單純形法求解(見pp217-221), 也可用圖解法求解:解得= (2.4, 2.4) , =0 , =1.2 , =4.8§11.3字典序法第一步，由決策人給出n，按重要性由高到低排成 , 第二步，用

7、適當方法估計各屬性的偏好(效用或價值)函數 (), (), , ()第三步，依次求解下列問題，進行篩選問題P1 解為問題P2 解為 問題Pj 直到 a) 問題Pj 只有唯一解, 則該解為最優解 b) n個問題全部解過：決策人用其他準則從中選擇一個方案。§11.4 逐步進行法(STEP Method)特點：P= 只有最大偏差起作用 屬于Min max 決策規則算法步驟對多目標決策問題 max=Cs. t. Ab 0 記作 第一步· 求解n個單目標優化問題 j=1,n 解為 得= 理想點 = (,) · 列出支付表使決策人對取不同的時各目標的值有直觀認識第二步由 =

8、max求解 min s. t. 等價于解 min入s. t. j=1,n 0 其中 j=1,n 式中 從支付表中獲得·解(2)得 與 j=1,n第三步 由決策人判斷降低某個太好的目標 ，下降再修改約束條件，使 Ab 0 : =- j=1,n j 以取代，令=0重復第二步三、優缺點：直觀; 修改有針對性; 較難定§11.5 調和解(Compromise solution)和移動理想點法一、基本概念(思路)1.調和解 在求解MODP: 時 (或), W , p要由決策人確定其中 ·由單調性假設，= j=1,n可以求得 ·W可由決策人設定 而P則很難設定因此，

9、給定權向量W，定義調和解集 = |是給定W時的解它是非劣解的子集, 即 Ì2.各目標偏差的規范化 記= 用使偏差無量綱、歸一化，否則量綱、單位的選取有關二、求解步驟第一步 由決策人估計權W第二步 = =第三步 構造調和集求解 p=1,2,其中 第四步若能從中找出BCS，則結束第五步 尋找新的理想點令 = 返回第二步.§11.6 SEMOP(多目標問題的序貫解法)一、思路與記號· 目的為區間目的類型目的表達式偏差測度 有上界/有下界/給定值= 區間內區間外,·n個目標分為兩類:：加約束的r個目標的下標集合；=J J=1,2,n ：X中的子集，其中的使 &q

10、uot;jÎ, 在標定區間內· 求解min s. t. 將解與 j=1,n送決策人判斷· 為了向決策人提供必要信息需解(n-r)個輔問題· mins. t. 其中, =1,n-r p是中第個元素在J中的序號 是jÎ以及j=p的均嚴格處于標定的目的區間內二、解題步驟第一步 由決策人確定r個應嚴格限定值域的目標，并給出這r個目標的目的區間，這r個目標的序號構成集合第二步 i, 解主問題 min s. t. ii, 解n-r個輔問題 mins. t. 得出與 j=1,n和 與 j=1,n =1,n-r第三步 由決策人對第二步結果作判斷基對滿意則停止若

11、 不滿意則q=q+1返回第一步三、優缺點1.可用于非單調區間2.容易反映目標間的矛盾關系3.非線性規劃問題求解困難,沒有規范化的步驟保證收斂§11.7Geoffrion法一、思路· 用Frank-Wolfe法解線性約束的非線性規劃問題max v() (0) s. t. 是在 處，以一階Taylor展開線性逼接v()記作v(): = v() + (-) (1)求(1)的極大值等價于求解線性規劃問題 · (2)令(2)的最優解為，則i,若 (-) 是(2)的最優解，迭代停止；ii,若(-)>0, 則從出發沿-方向作一維搜索即求 v(+(-)的最優解只要 >

12、0足夠小, 必有 v()>v() 式中 = +(-)對，重復上述步驟，可得原問題(0)的最優解雖屬未知，但= 除以, 得 其中，»- j=1,n二、求解步驟三、優缺點1.只要決策者心目中的效用函數確實存在，并能給出各點的邊際置換率，不必給出具體的效用函數值。2.只適用于線性約束的多目標規劃3.每次迭代 都有所增加，收斂性有保證但在實際上所得到的解的優劣取決于決策人提供的局部偏好信息的準確性。§11.8 代理值置換法(Surrogate worth Trade-off Method)一、思路：·置換率：在某個非劣點處若要提高某一目標值一個單位，必須使另一目標降低多少，(設其他目標函數值不變)置換率給出了非常有用的信息:如決策人愿意進行這種置換，說明該方向上有決策人更喜愛的非劣解。二、求解步驟第一步：產生非劣解的有代表性的子集任選一種方法去求得非劣解的有代表性的子集。不失一般性，選作為參考目標，構成不等式約束問題:min (1)s. t. i=1,m j=1,n-1 其中, 為了便于比較，最好選用重要目標或其計量單位是決策人所熟悉的目標作為目標n。第二步：獲得置換信息在求解(1)時，可以得到 j=1,n-1其中是(1)的解， 是(1)的Kuhn-Tucker乘子， 就是在處的置換率第三步：了解決策人