MBA決策分析教材-多目標(biāo)決策

1、多目標(biāo)決策(Multi-objective Decision-making)主要參考文獻(xiàn)68, 111§ 11.1序言MA：評(píng)估與排序MCDPMO：數(shù)學(xué)規(guī)劃一、問題的數(shù)學(xué)表達(dá)N個(gè)決策變量x = x1 , x2 , ,xN ?n個(gè)目標(biāo)函數(shù)f ( x ) = (f 1 ( x ),?m個(gè)約束條件x即 :gk ( x )?f 2 ( x ), ,f n ( x )?0 k=1, ,mx0?(1) 不失一般性， MODP可表示成：P1 Max f 1( x ),f 2( x ), ,f n( x )?s.t.x?這是向量?jī)?yōu)化問題， 要在可行域X 中找一 x S ，使各目標(biāo)值達(dá)?到極大。通常

2、x S 并不存在，只能找出一集非劣解x*?(2)若能找到價(jià)值函數(shù) v( f 1(x),f2(x),fn(x)則可?MODP表示成：P2 Max v (f 1( x ), f2( x ), ,f n( x )?s.t.x?這是純量?jī)?yōu)化問題，困難在于v 如何確定。二、最佳調(diào)和解 (Best Compromise Solution)P3 DR(f1 ( x ), f2( x ), , f n( x )?s.t.x?即根據(jù)適當(dāng)?shù)?Decision Rule在 X 中尋找 BCS xc?常用的 Decision Rule:max VmaxEU11- 1mind p ( f - f )?求 BCS必須引入

3、決策人的偏好三、決策人偏好信息的獲取方式1. 在優(yōu)化之前，事先一次提供全部偏好信息如：效用函數(shù)法，字典式法，滿意決策，目的規(guī)則2. 在優(yōu)化過程中：逐步索取偏好信息如： STEM SEMOP Geoffrion, SWT3. 在優(yōu)化之后：事后索取偏好，由決策人在非劣解集中選擇i， 算法復(fù)雜，決策人難理解， ii, 計(jì)算量大， iii, 決策人不易判斷各種方式的利弊比較黃慶來 111 的分類表 :§ 11.2 目的規(guī)劃法適用場(chǎng)合：決策人愿意并且能用優(yōu)先級(jí) P (Preemptive priority)權(quán)W (Weight)目的 f( Goal )來表示偏好?理想點(diǎn)f * ( Ideal

4、)?11- 2一、距離測(cè)度的選擇1d p ( f ( x)f ) = w j | f j ( x) f j |p p?范數(shù) p 的意義和作用p=1絕對(duì)值范數(shù)p=2歐幾里德范數(shù)p = 契比 E 夫范數(shù)在上圖中， B、 C點(diǎn)到 A 的距離f1f 2d1d2d3dAB間的距 066666離AC間的距離 5496.45.754p 從 1時(shí)最大偏差所起作用越來越大，二、目的規(guī)劃問題的表述min d p ( f ( x)f ) =f j |p1p w j | f j ( x)?s. t.x即: gk (x )0k=1, ,m?x0?三、分類1. 線性目的規(guī)劃p = 1f j ,gk 為線性 ;x 連續(xù) ;

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

6、1.5 個(gè)單位原料 , 利潤(rùn)為 3。在下一計(jì)劃期間車間有 12 單勞動(dòng)力 12 單位原料。假定車間主任有如下目標(biāo)：(1) 利潤(rùn)至少為6 個(gè)單位，(2) 兩種產(chǎn)品產(chǎn)量經(jīng)盡可能保持x1 ： x2 = 3 ：2，(3) 勞動(dòng)力充分利用解：按傳統(tǒng)的線性規(guī)劃，使利潤(rùn)最大：max 2x1 + 3 x2s. t. 2x1 +3x2 12 ( 勞力約束 )3x1+1.5x212 ( 原料約束 )x1,x20用圖解法可得 x1=3,x2=2 時(shí), 利潤(rùn)最大為 12.五、例 ( 續(xù)上例 )已知條件中產(chǎn)品甲利潤(rùn)改為4,其余均不變。車間主任希望改為 : 最低利潤(rùn)12 單位(2) 產(chǎn)量比例為 1, 即 x1 = x2

7、;(3)充分利用原料11- 4解 : 新的目標(biāo)為 4 x1 +3x2 12(最低限度利潤(rùn) )x1 -x2= 0(產(chǎn)量比例 )3x1 +1.5 x2 =12(材料充分利用 )設(shè)定偏差變量d1 : 利潤(rùn) d2 :產(chǎn)量比例d3 : 原料d 4 : 勞動(dòng)力利用正、負(fù)偏差變量可得：min P1d1+ P2( d 2+d 2)+P3d 3s. t.4x1 +3x2 - d1+d112(利潤(rùn)目標(biāo) )x1 -x2 -d2 +d2= 0(產(chǎn)量比例 )3x1 +1.5x2+d3=12(材料充分利用 )2x1 + 3x2+d4=12(勞動(dòng)力約束 )本題可以用改進(jìn)的單純形法求解( 見 pp217-221),也可用圖解

8、法求解 :解得 x * = (2.4, 2.4) , d1 = d 2 = d 2 = d 4 =0 , d3 =1.2 , d4 =4.8§ 11.3 字典序法第一步，由決策人給出n，按重要性由高到低排成y1 , y2 , ,yn第二步，用適當(dāng)方法估計(jì)各屬性的偏好( 效用或價(jià)值 ) 函數(shù)w1 ( y1 ), w2 ( y2 ), , wn ( yn )第三步，依次求解下列問題，進(jìn)行篩選問題 P1max w1 ( y1 (x) 解為 X1x X問題 P2max w2 ( y2 ( x) 解為 X 2x X1 問題 Pj直到 a)max w2 ( y2 ( x)x X j 1問題 Pj

9、 只有唯一解 ,則該解為最優(yōu)解b) n 個(gè)問題全部解過：決策人用其他準(zhǔn)則從 X n 中選擇一個(gè)方案。11- 5§ 11.4 逐步進(jìn)行法 (STEP Method)特點(diǎn)： P= 只有最大偏差起作用屬于 Min max 決策規(guī)則算法步驟對(duì)多目標(biāo)決策問題max f ( x) =Cx ?s.t. Ax b?x 0記作 X1?第一步· 求解 n 個(gè)單目標(biāo)優(yōu)化問題max f j( x)j=1,nx X?解為 x*j得 f j* = f j (x *j )?理想點(diǎn)f * = ( f1* , , f n* )?· 列出支付表使決策人對(duì)取不同的x *j時(shí)各目標(biāo)的值有直觀?認(rèn)識(shí) f

10、1f1x1*f 1*?f jf 1 jf nf 1nx *jf j 1f j*f jn?xn*f n1f njf n*?第二步由 d ( f (x)f *)= max w j ( f j*?求解 mind( f ( x)f * )?s. t.xX1等價(jià)于解 min入s. t. w j ( f j*xX1 0f j ( x)?f j ( x)j=1,n?11- 6其中 w jnjj=1,nj1j| f j*jf j* (Nf jmin |1c2ji ) 2式中·解 (2) 得x1 與?i 1f jmin 從支付表中獲得f j ( x1 )j=1,n?第三步 由決策人判斷降低某個(gè)太好的目

11、標(biāo)f l ( x1 ) ，下降 f l 再修改約束條件，使?Ax b?x 0?X 2 :f l ( x) = f l ( x1 ) - f l?f j ( x) f j(x 1 ) j=1, ,n j l?以 X 2 取代 X 1 ，令 w l =0 重復(fù)第二步三、優(yōu)缺點(diǎn)：直觀 ;修改有針對(duì)性 ;f l 較難定§ 11.5 調(diào)和解 (Compromise solution)和移動(dòng)理想點(diǎn)法一、基本概念 ( 思路 )1. 調(diào)和解 x p? W在求解 MODP:min dp ( f ( x)f * ) 時(shí)x X?f * ( 或 f), W, p要由決策人確定?其中 ·由單調(diào)性假設(shè)

12、，f =maxf j ( x)j=1, ,n 可以求得?x X?·W可由決策人設(shè)定而 P 則很難設(shè)定因此，給定權(quán)向量 W，定義調(diào)和解集XWC = xX | x 是給定 W時(shí) min 1w j | f j ( x) f j |p p 的解 ?x X?它是非劣解的子集 ,即 XWCX *2. 各目標(biāo)偏差的規(guī)范化11- 7記 f j0 = minf j ( x)xX?f j*f j ( x)使偏差無量綱、歸一化，否則d p 量綱、單位的選用f*f0?jj取有關(guān)二、求解步驟第一步 由決策人估計(jì)權(quán) W第二步f j0 =min f j( x)f * = max f j ( x)xX?x X?第三

13、步構(gòu)造調(diào)和集求解mind p ( f ( x)f * ) p=1,2,x X?nf j*f j ( x)其中d1 ( ?)w j?f*0j1jf jnf j*f j ( x)d2 (?)w j f*0? 2j1jf jf j*f j ( x)d(?)maxw j?f*0jjf j第四步若能從X C 中找出BCS，則結(jié)束W令 X2 = XWC 返回第二步 .§ 11.6 SEMOP(多目標(biāo)問題的序貫解法 )一、思路與記號(hào)· 目的為區(qū)間目的 目的表達(dá)式 偏差測(cè)度 d j 類型有上f j(x) bj界?有下f j( x) aj界?f j ( x) / b j?a j / f j

14、( x)?給定f j(x) = c j值?區(qū)間a j f j ( x) b j?內(nèi)1f j(x)?(2 cjb jfj( x)(?a j b jb jcj)f j ( x)?a j)f j ( x)?11- 8區(qū)間f j (x) aj, f j( x) bja jf j (x)(?外?bjb jb j· n 個(gè)目標(biāo)分為兩類 :I q ：加約束的 r 個(gè)目標(biāo)的下標(biāo)集合；JqI qJ=1,2,nX q ：X 中的子集，其中的x 使jI q ,?· 求解 min Sqd jq j J qa j1)f j (x)?f j ( x) 在標(biāo)定區(qū)間內(nèi)?s. t.x X q?將解 x q

15、與 f j ( xq ) j=1,n 送決策人判斷?· 為了向決策人提供必要信息需解(n-r)個(gè)輔問題· min Slqj Jq , jd jps.t. xX pq?其中 ,l =1, ,n-rp是 J q 中第 l 個(gè)元素在 J 中的序號(hào)X pq 是 jI q 以及 j=p 的 f j (x) 均嚴(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 q第二步 i,解主問題minSqd jq j Jqs. t.x X q?ii, 解 n-r 個(gè)輔問題minSlqd j j Jq ,

16、j ps.t.xX q?p得出 xq 與?和xq 與? lf j ( x q )?f j ( x q )? lj=1, ,nj=1, ,nl =1, ,n-r第三步由決策人對(duì)第二步結(jié)果作判斷基對(duì) x q 滿意則停止?11- 9若 不滿意則 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(f ( x) )(0)?s. t.xX?是在 x0處，以一階Taylor展開 v(

17、x) 線性逼接 v(f (x) ) 記作?v( x ):?0) + 0)T( x -x0)(1)v (x) = v( xxv( x?求 (1)的極大值等價(jià)于求解線性規(guī)劃問題max x v(x 0 ) T · x(2)x X?令 (2)的最優(yōu)解為 y 0 ，則?i,若 x v( x 0 ) T (y0 -x 0 ) 是(2) 的最優(yōu)解，迭代停止；?ii,若x v( x 0 ) T (y0 -x 0 ) 0,則從 x 0 出發(fā)沿 y0 - x 0 方向作一維搜索?即求 max v(x 0 +t 0 (y0 - x 0 ) 的最優(yōu)解 t 00 t 01?只要 t 00足夠小,必有 v(x

18、1 ) v(x 0 )?式中 x1 =x 0 +t 0 ( y 0 - x 0 )?對(duì) x1X ，重復(fù)上述步驟，可得原問題(0)的最優(yōu)解?xv( x0 ) 雖屬未知，但x v( x0 ) = nvx f j (x 0 )j1f j,n0vf j-f l除 以w jx f j ( x )其 中 ， w jf jv得vf lf lj1j=1, ,n二、求解步驟11- 10三、優(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)生非劣解的有代表性的子集任選一種方法去求得非劣解的有代表性的子集。不失一般性，選f n ( x) 作為參考目標(biāo)