多目標(biāo)決策簡單概述

1、第十一章 多目標(biāo)決策(Multi-objective Decision-making) 主要參考文獻(xiàn) 68, 111 11.1 序言 MA： 評(píng)估與排序 MCDP MO： 數(shù)學(xué)規(guī)劃一、問題的數(shù)學(xué)表達(dá) N個(gè)決策變量 = , n個(gè)目標(biāo)函數(shù) () = (),(), ()m個(gè)約束條件 C 即: () 0(1) 不失一般性，MODP可表示成： P1 Max (),(), () s.t. C 這是向量優(yōu)化問題，要在可行域X中找一，使各目標(biāo)值達(dá)到極大。 通常并不存在，只能找出一集非劣解(2) 若能找到價(jià)值函數(shù)v(),(), () 則MODP可表示成： P2 Max v (),(), () s.t. C這是純

2、量優(yōu)化問題，困難在于v如何確定。二、最佳調(diào)和解(Best Compromise Solution)P3 DR (),(), () s.t. C即根據(jù)適當(dāng)?shù)腄ecision Rule在X中尋找BCS 常用的Decision Rule: max V maxEU min (-)求BCS必須引入決策人的偏好三、決策人偏好信息的獲取方式1.在優(yōu)化之前，事先一次提供全部偏好信息 如：效用函數(shù)法，字典式法，滿意決策，目的規(guī)則2.在優(yōu)化過程中：逐步索取偏好信息如：STEM SEMOP Geoffrion, SWT3.在優(yōu)化之后：事后索取偏好，由決策人在非劣解集中選擇i， 算法復(fù)雜，決策人難理解， ii,計(jì)算量

3、大，iii,決策人不易判斷各種方式的利弊比較黃慶來111的分類表:11.2 目的規(guī)劃法適用場合：決策人愿意并且能用 優(yōu)先級(jí)P (Preemptive priority) 權(quán) W (Weight) 目的 ( Goal ) 來表示偏好 理想點(diǎn) ( Ideal )一、距離測度的選擇 = 范數(shù)p的意義和作用p=1 絕對(duì)值范數(shù)p=2 歐幾里德范數(shù)p =契比E夫范數(shù)在上圖中，B、C點(diǎn)到A的距離AB間的距離066666AC間的距離5495p從1時(shí)最大偏差所起作用越來越大，二、目的規(guī)劃問題的表述min = s. t. C 即: () 0三、分類1.線性目的規(guī)劃 p = 1 , 為線性; 連續(xù); w, 事先給定

4、2.整數(shù)目的規(guī)劃 除各分量為整數(shù)外，均同線性目的規(guī)劃 (例：人才規(guī)劃)3.非線性目的規(guī)劃： p=1， w, 事先給定 , 為非線性，X為凸集，連續(xù)4.調(diào)和規(guī)劃和移動(dòng)理想點(diǎn)法: 1 p w事先給定 = 是移動(dòng)的理想點(diǎn)5. 字典序法 p = 1 = P1P2PL法 P= = 為理想點(diǎn)，權(quán)由計(jì)算得出7.SEMOP 目的標(biāo)定為區(qū)間，不是固定點(diǎn)四、例：某車間生產(chǎn)甲、乙兩種產(chǎn)品，產(chǎn)量分別為和，產(chǎn)品甲每單位需2個(gè)單位的勞動(dòng)力和3個(gè)單位原料,利潤為2；生產(chǎn)產(chǎn)品乙需3個(gè)單位勞動(dòng)力和個(gè)單位原料,利潤為3。在下一計(jì)劃期間車間有12單勞動(dòng)力12單位原料。假定車間主任有如下目標(biāo)：(1) 利潤至少為6個(gè)單位，(2)兩種產(chǎn)

5、品產(chǎn)量經(jīng)盡可能保持：= 3：2，(3) 勞動(dòng)力充分利用解：按傳統(tǒng)的線性規(guī)劃，使利潤最大： max 2+ 3 s. t. 2+ 312 (勞力約束) 312 (原料約束) , 0用圖解法可得=3, =2時(shí),利潤最大為12.五、例(續(xù)上例)已知條件中產(chǎn)品甲利潤改為4, 其余均不變。車間主任希望改為: 最低利潤12單位(2) 產(chǎn)量比例為1, 即=; (3)充分利用原料解: 新的目標(biāo)為 4+312 (最低限度利潤) - = 0 (產(chǎn)量比例) 3=12 (材料充分利用)設(shè)定偏差變量 : 利潤 : 產(chǎn)量比例 : 原料 :勞動(dòng)力利用正、負(fù)偏差變量可得： min P1+ P2(+) + P3s. t. 4+3

6、-+12 (利潤目標(biāo)) - - + = 0 (產(chǎn)量比例) 3 + =12 (材料充分利用) 2+ 3 + =12 (勞動(dòng)力約束)本題可以用改進(jìn)的單純形法求解(見pp217-221), 也可用圖解法求解:解得= (2.4, 2.4) , =0 , =1.2 , 字典序法第一步，由決策人給出n，按重要性由高到低排成 , 第二步，用適當(dāng)方法估計(jì)各屬性的偏好(效用或價(jià)值)函數(shù) (), (), , ()第三步，依次求解下列問題，進(jìn)行篩選問題P1 解為問題P2 解為 問題Pj 直到 a) 問題Pj 只有唯一解, 則該解為最優(yōu)解 b) n個(gè)問題全部解過：決策人用其他準(zhǔn)則從中選擇一個(gè)方案。11.4 逐步進(jìn)行法

7、(STEP Method)特點(diǎn)：P= 只有最大偏差起作用 屬于Min max 決策規(guī)則算法步驟對(duì)多目標(biāo)決策問題 max=Cs. t. Ab 0 記作 第一步 求解n個(gè)單目標(biāo)優(yōu)化問題 j=1,n 解為 得= 理想點(diǎn) = (,) 列出支付表使決策人對(duì)取不同的時(shí)各目標(biāo)的值有直觀認(rèn)識(shí)第二步由 = max求解 min s. t. 等價(jià)于解 min入s. t. j=1,n 0 其中 j=1,n 式中 從支付表中獲得解(2)得 與 j=1,n第三步 由決策人判斷降低某個(gè)太好的目標(biāo) ，下降再修改約束條件，使 Ab 0 : =- j=1,n j 以取代，令=0重復(fù)第二步三、優(yōu)缺點(diǎn)：直觀; 修改有針對(duì)性; 較難定

8、11.5 調(diào)和解(Compromise solution)和移動(dòng)理想點(diǎn)法一、基本概念(思路)1.調(diào)和解 在求解MODP: 時(shí) (或), W , p要由決策人確定其中 由單調(diào)性假設(shè)，= j=1,n可以求得 W可由決策人設(shè)定 而P則很難設(shè)定因此，給定權(quán)向量W，定義調(diào)和解集 = |是給定W時(shí)的解它是非劣解的子集, 即 2.各目標(biāo)偏差的規(guī)范化 記= 用使偏差無量綱、歸一化，否則量綱、單位的選取有關(guān)二、求解步驟第一步 由決策人估計(jì)權(quán)W第二步 = =第三步 構(gòu)造調(diào)和集求解 p=1,2,其中 第四步若能從中找出BCS，則結(jié)束第五步 尋找新的理想點(diǎn)令 = 返回第二步.11.6 SEMOP(多目標(biāo)問題的序貫解法

9、)一、思路與記號(hào) 目的為區(qū)間目的類型目的表達(dá)式偏差測度 有上界/有下界/給定值= 區(qū)間內(nèi)區(qū)間外,n個(gè)目標(biāo)分為兩類:：加約束的r個(gè)目標(biāo)的下標(biāo)集合；=J J=1,2,n ：X中的子集，其中的使 j, 在標(biāo)定區(qū)間內(nèi) 求解min s. t. 將解與 j=1,n送決策人判斷 為了向決策人提供必要信息需解(n-r)個(gè)輔問題 mins. t. 其中, =1,n-r p是中第個(gè)元素在J中的序號(hào) 是j以及j=p的均嚴(yán)格處于標(biāo)定的目的區(qū)間內(nèi)二、解題步驟第一步 由決策人確定r個(gè)應(yīng)嚴(yán)格限定值域的目標(biāo)，并給出這r個(gè)目標(biāo)的目的區(qū)間，這r個(gè)目標(biāo)的序號(hào)構(gòu)成集合第二步 i, 解主問題 min s. t. ii, 解n-r個(gè)輔問

10、題 mins. t. 得出與 j=1,n和 與 j=1,n =1,n-r第三步 由決策人對(duì)第二步結(jié)果作判斷基對(duì)滿意則停止若 不滿意則q=q+1返回第一步三、優(yōu)缺點(diǎn)1.可用于非單調(diào)區(qū)間2.容易反映目標(biāo)間的矛盾關(guān)系3.非線性規(guī)劃問題求解困難,沒有規(guī)范化的步驟保證收斂法一、思路 用Frank-Wolfe法解線性約束的非線性規(guī)劃問題max v() (0) s. t. 是在 處，以一階Taylor展開線性逼接v()記作v(): = v() + (-) (1)求(1)的極大值等價(jià)于求解線性規(guī)劃問題 (2)令(2)的最優(yōu)解為，則i,若 (-) 是(2)的最優(yōu)解，迭代停止；ii,若(-)0, 則從出發(fā)沿-方向

11、作一維搜索即求 v(+(-)的最優(yōu)解只要 0足夠小, 必有 v()v() 式中 = +(-)對(duì)，重復(fù)上述步驟，可得原問題(0)的最優(yōu)解雖屬未知，但= 除以, 得 其中，- j=1,n二、求解步驟三、優(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)一、思路：置換率：在某個(gè)非劣點(diǎn)處若要提高某一目標(biāo)值一個(gè)單位，必須使另一目標(biāo)降低多少，(設(shè)其他目標(biāo)函數(shù)值不變)置換率給出了非常有用的信息:如決策人愿意進(jìn)行這種置換，說明該方向上有決策人更喜愛的非劣解。二、求解步驟第一步：產(chǎn)生非劣解的有代表性的子集任選一種方法去求得非劣解的有代表性的子集。不失一般性，選作為參考目標(biāo)，構(gòu)成不等式約束問題:min (1)s. t. i=1,m j=1,n-1 其中, 為了便于比較，最好選用重要目標(biāo)或其計(jì)量單位是決策人所熟悉的目標(biāo)作為目標(biāo)n。第二步：獲得置換信息在求解(1)時(shí)，可以得到 j=1,n-1其中是(1)的解， 是(1)的Kuhn-Tucker乘子， 就是在處的置換率第三步：了解決策人的偏好把第二步計(jì)算結(jié)果遞交給