多目標分析21課件

多目標決策分析(II)多目標分析2[1]內容提要無限方案多目標決策問題目標規(guī)劃法逐步求解法DIDASSGeoffrion法極小化極大法不精確不完全判斷兩兩比較的典型類型一種處理和分析方法多目標分析2[1]無限方案多目標決策問題多目標分析2[1]無限方案多目標決策問題引入效用函數后，問題可以改寫為：然而，多目標決策問題的效用函數通常極難得到。處理方法： 重點在如何獲取和利用決策者的偏好信息多目標分析2[1]目標規(guī)劃法決策者通常很難說清楚自己的偏好，但在他心里會有一個理想的目標(可能很模糊)。因此，我們取與決策者的理想目標最接近的方案為“最優(yōu)方案”。多目標分析2[1]線性目標規(guī)劃多目標分析2[1]線性目標規(guī)劃多目標分析2[1]線性目標規(guī)劃多目標分析2[1]線性目標規(guī)劃多目標分析2[1]求解線性目標規(guī)劃例題某公司需要確定三種產品P1,P2,P3的產量，在做出決策前，管理層希望達到如下的目標：目標1：總利潤不少于1.25億美元目標2：保持現有的4000人的員工水平目標3：將投資資金控制在5500萬美元以內三個目標在重要性上的排序：目標1，目標2的前半部分避免減少員工，目標3，目標2的后半部分避免增加員工懲罰權重：總利潤5（低于目標每100萬美元），員工水平4（低于目標每100名員工）2（高于目標每100名員工）3（超過目標每100萬美元）產品的單位貢獻P1P2P3利潤12915員工534資金578多目標分析2[1]線性目標規(guī)劃人們通常對目標的要求可能有“數量級”的差別，如：〖船廠建設問題〗通常要考慮如下指標首要條件 －岸線 －水文 －地質 －水域主要條件 －陸域 －交通 －生產服務 。。。。一般條件 。。。?？梢姏Q策者對不同的指標的要求有時會有“質”的差別多目標分析2[1]線性目標規(guī)劃兩類“權”系數 －“搶先優(yōu)先權”：表達一種“質”的度量 －普通權：表示“量”的差別多目標分析2[1]線性目標規(guī)劃求解算法：令K=1，求線性規(guī)劃問題，使第一優(yōu)先級中的各目標得以優(yōu)化如果K=L，或最優(yōu)解是唯一解，則停止，否則下一步令K=K＋1，在滿足第K－1優(yōu)先級及以前各類目標要求的前提下，求線性規(guī)劃問題，使第K優(yōu)先級中所有目標得以優(yōu)化最多需要求解L個線性規(guī)劃問題。多目標分析2[1]Excel求解優(yōu)先目標規(guī)劃續(xù)前例公司再次明確了目標重要度差異較大，存在不同的優(yōu)先級，如下：優(yōu)先級1總利潤不得少于1.25億美元優(yōu)先級2避免員工人數少于4000人優(yōu)先級3投資資金控制在5500萬美元以內優(yōu)先級4避免員工人數超過4000人多目標分析2[1]案例討論計算之古巴的良方案例關鍵點b)c)說明了對于加權目標規(guī)劃的影響因素，是目標的偏離權重，以及資源的分配d)說明了在一定情況下，目標與約束條件的轉換多目標分析2[1]逐步求解法基本思想同目標規(guī)劃，增加與決策者的交互過程。決策者在每次對話中都應該評價所得結果，并確定改進方向。求解過程分為三步：1)求理想點多目標分析2[1]逐步求解法2)求調和解多目標分析2[1]逐步求解法多目標分析2[1]逐步求解法3)與決策者交互對話 將2)得出的最優(yōu)解x1和f1(x1),…,fn(x1)提供給決策者，決策者可以根據自己的意愿調整某些目標值，即他可能認為某些目標太差，而有些可以放寬。如：他可以降低fj(x1)到fj(x1)－

fj，并將它作為一個約束重新計算最優(yōu)解x2和f1(x2),…,fn(x2)，直到滿意為止。多目標分析2[1]逐步求解法：例題例：某工廠生產A和B兩種產品，A產品每臺利潤100元，B產品每臺利潤80元。A產品平均生產時間為3小時/臺，B產品平均生產時間為2小時/臺。工廠每周生產120小時，尚可加班48小時，加班生產的A產品利潤90元/臺，B產品利潤70元/臺。設市場每周需求量為A，B產品各30臺以上。問在盡量滿足市場的前提下，如何安排生產，才能使利潤最大，加班時間最少？多目標分析2[1]逐步求解法：例題多目標分析2[1]逐步求解法：例題多目標分析2[1]逐步求解法：例題多目標分析2[1]逐步求解法：小結一般情況下，對多目標問題求最小值，當決策者決定放寬對某個目標函數的要求時，約束條件X1相應調整為同時，令wj=0。當然，可以同時放寬多個目標。STEM法的優(yōu)點是分析者在每一計算后可以從決策者那里得到一些信息，以確定進一步計算的方向。但是，這一方法采用的理想點是固定的(有一定的客觀性，并沒有很好地反映決策者的偏好)，決策者的偏好只是在每次調整對目標的要求時得以體現，權系數計算也比較麻煩。多目標分析2[1]DIDASS(1)傳統多目標決策分析方法，主要依賴權系數，存在以下問題：權系數難以確定完全兩兩比較過程相當長前后不一致決策者對唯一的“最優(yōu)”解不一定滿足在分析過程中沒有充分包含決策者的經驗和判斷DIDASS——交互式的方法以目標規(guī)劃為基礎決策者按他試圖到達的目標去思考在分析過程中始終利用決策者自身的知識、經驗及對問題的判斷多目標分析2[1]DIDASS(2)求解的基本過程 決策者給出要達到的目標--第i次根據決策者給出的目標(參考點)，系統找到相應的最好結果如果決策者滿意，則過程停止；否則要求決策者給出新的參考點或改變(調整)某些約束。通過不斷反復直至找到一個符合決策者要求的解。多目標分析2[1]DIDASS(3)DIDASS的基礎是參考點法。即，在給定的參考點下，從非劣解集中尋求一個與參考點“最接近”的解。 為此，要設計一個標量化函數去評價非劣解與參考點之間的“距離”?？尚杏蚨嗄繕朔治?[1]DIDASS(4)設是問題的可行域是目標空間目標函數定義為標量化函數定義為要求具有如下性質而且非劣解集多目標分析2[1]DIDASS(5)設多目標問題可表示為：處理分為兩個階段：

1)對每個目標函數分別求最優(yōu)，從而得到一決策支持矩陣Ds(支付表)多目標分析2[1]DIDASS(6)其中－－理想點－－負理想點多目標分析2[1]DIDASS(7)搜索階段，構造一標量化函數求滿意解或加權系數，通常取1交互：修改參考點，返回上一步； 若已滿意，則停止。多目標分析2[1]DIDASS(8)例：污水處理系統：設S1、S2和S3處的污水量分別為20，10和70萬噸；S1和S2處建I級處理廠，S3處建II級處理廠；Qi為處理廠的容量；qi為通過管線運送的污水量。S1S2S3IIIIq2q1q3目標函數：

1)費用

2)電力

3)土地占用各目標求最小。多目標分析2[1]DIDASS(9)約束條件：首先計算決策支持矩陣多目標分析2[1]DIDASS(10)給定參考點：求得非劣解：修改參考點：求得非劣解：修改參考點：求得非劣解：若決策者認為目標已符合要求，則停止計算。最優(yōu)決策方案為：Q1＝20，Q2＝45.04，Q3＝34.96 q1=0,q2=35.04,q3=0多目標分析2[1]Geoffrion法(1)假設多目標決策問題存在多屬性價值函數，方法的步驟：選擇一初始點尋找價值函數V的改進方向確定步長停止判斷例：設某廠打算生產兩種新產品A和B，生產費用A：2萬元/噸，B：5萬元/噸；污染環(huán)境引起的損失A：4單位/噸，B：1單位/噸；生產能力A：5噸，B：6噸；市場需要A＋B不少于7噸；A產品利潤3千元/噸，B：1千元/噸。問題：如何安排生產，在滿足市場的條件下，使費用和污染最小，且利潤最大？多目標分析2[1]Geoffrion法(2)該問題的數學模型為第一步：選擇初始點令x’=[3,5]T，其對應的目標函數值為f=[-31,-17,14]T第二步：確定價值函數V的改進方向1)計算權w1,w2,w3設決策人認為以下兩組目標函數值是等價的，對于f1和f2有 [-31,-17,14]~[-31+1,-17-1/3,14]多目標分析2[1]Geoffrion法(3)對于f1和f3有

[-31,-17,14]~[-31+1,-17,14-1/2]wj1稱為目標函數f1和fj之間的邊際替換率或無差異置換率。

f2

f1這是目標fi對比fj的重要程度嗎？多目標分析2[1]Geoffrion法(4)2)計算最優(yōu)解y1和z1構造價值函數(在x1點附近的線性逼近)求解以下線性規(guī)劃問題得到y1最優(yōu)解最優(yōu)的y1=[1,6]T,而V的改進方向z1為

z1=y1-x1=[-2,1]T第三步：確定步長t1將t1分為5等分，分別計算fj(x1+t1z1),j=1,2,3,如下表多目標分析2[1]Geoffrion法(5)假定決策者認為f2=[-31.6,-12.8,11]T

相對最好，從而x2=x1+0.6z1=[1.8,5.6]T.回到第一步設決策人認為以下兩組目標函數值是等價的，對于f1和f2有 [-31.6,-12.8,11]~[-31.6+1,-12.8-1/2,11]對于f1和f3有

[-31.6,-12.8,11]~[-31.6+1,-12.8,11-1/2]多目標分析2[1]Geoffrion法(6)計算得：由于：求解以下線性規(guī)劃問題得到y2最優(yōu)解最優(yōu)的y2=[5,2]T,而V的改進方向z2為

z2=y2-x2=[3.2,-3.6]T多目標分析2[1]Geoffrion法(7)假定決策者認為f3=[-29.28,-14.64,12.2]T

相對最好，從而x3=x2+0.2z2=[2.44,4.88]T.第四步：停止判斷計算第二次迭代較第一次迭代的改進多目標分析2[1]Geoffrion法(8)關于這個例子，如果決策人確定的域值為0.2，則迭代停止，如果為0.1，則迭代繼續(xù)。該方法的主要優(yōu)點：在分析之前不需要利用決策者的偏好去構造價值函數決策者在過程中只要給出局部偏好信息決策者能積極參與求解過程主要缺點：對決策者要求較高：結果判斷；局部偏好信息多目標分析2[1]極小化極大法多目標分析2[1]兩兩比較的典型類型精確判斷 例如：目標A比目標B重要一倍，即：1.01.02/31/3w1w2松弛判斷例如：目標A比目標B重要，即：1.01.01/21/2w1w2多目標分析2[1]兩兩比較的典型類型(續(xù))近似判斷 例如：目標A比目標B重要，但不超過一倍，即1.01.02/31/3w1w2多目標分析2[1]兩兩比較的典型類型(續(xù))一般情況下，權重的可行域為：顯然，權重可行域是一個凸域，因此其頂點十分重要。例：設權重可行域如下：一共有幾個頂點呢？多目標分析2[1]兩兩比較的典型類型(續(xù))該例題有四個頂點：示意圖多目標分析2[1]兩兩比較的典型類型(續(xù))傳遞性

1)強傳遞性 如：A：B＝2：1且B：C＝3：1

A：C＝6：1 2)弱傳遞性 如：A：B＝2：1且B：C＝3：1

而A：C＝4：1不是A：C＝6：1

但是滿足：多目標分析2[1]一種處理不精確不完全判斷的決策分析方法通常，精確、一致、完整的兩兩比較很難獲得 決策者經常給出如下形式的判斷：

1）“產量至少比質量重要兩倍但不超過3倍”2）“產量的重要性應在30％至40％之間”3）“若將費用和質量聯合起來則比產量更重要”這一類判斷可以用區(qū)間數表示：其中：uij和lij分別為第個i目標比第j個目標相對重要性的上下限。多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))一般有，若則Iij退化為一數值，這時決策者給出的是一準確判斷。由于判斷結果可表示為區(qū)間，故稱為區(qū)間判斷。由于實數是區(qū)間的一特例因此這種表示法并不排斥準確判斷。利用區(qū)間判斷，我們可以得到關于權值的可行域。例：考慮一個三目標決策問題，決策者給出如下判斷：I12=[１２]I23=[２，３]注意：這里決策者并設有給出關于目標完全的兩兩判斷判斷的I13=?多目標分析2[1])一種處理不精確不完全判斷的決策分析方法(續(xù))如果決策者能給出全部的兩兩判斷和準確的判斷值，則可行域將可能收縮為一個點（滿足一致性檢驗）；否則無解。一般情況下：傳統方法

不可行解示意圖多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))另一方面，對復雜決策問題,可行方案的結果也具有很大的不確定性。在估計一個方案x關于某一屬性ai可能產生的結果時，經常只能得出一個范圍。例如：某一夫婦的后代的身高會是多少？只能根據雙親的特點得出像160cm至190cm之間的區(qū)間估計。又例：某一船廠候選地質：岸線長度：良；走向：合理：曲直程度：尚可等。一般情況，某方案x關于屬性ai的區(qū)間估計記作：其中和分別為上、下限。理想情況，即信息完全的情形。多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))Xi對目標的貢獻由價值函數V(·)來確定。幾種典型的價值函數

1)若V(.)為單調增函數，則2)若V(.)單調減函數，則3)對于任意的V(.)，有多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))單調增單峰單調降示意圖多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))考慮目標間相互獨立的情形,因此,可以利用分別計算出和,2…,n,進而求該方案總目標值區(qū)間,對于給定的權值域,V(X)可由下式求出:這種情況下，如何比較方案的優(yōu)劣呢？多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))定義1：（絕對優(yōu)勢） 給定兩方案它們的目標值區(qū)間分別為和，如滿足則稱方案X絕對優(yōu)于方案Y，記作定義2：（弱優(yōu)勢） 給定兩個方案它們的目標值區(qū)間分別為和，若滿足則稱方案X弱優(yōu)于方案Y，記作：多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))在確定最優(yōu)方案時，最理想的情形是定義１，這樣可以排出各方案的優(yōu)先順序。對于復雜問題，絕對優(yōu)勢經常不成立，尤其是在決策分析過程的初期（掌握的信息，對問題的分析均較初步）是很正常的。經常有：這時可以考慮采用定義２，即弱優(yōu)勢，以確定方案間的優(yōu)劣關系關系。但是對于一些問題，一些方案間的弱優(yōu)勢也不一定成立，這時按上述分析給不出唯一的最優(yōu)方案。

1)如果我們無法得到進一步的信息，那么這時只能給決策者提供一個有效優(yōu)選子集，供決策者挑選。分析過程暫時結束。多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))

2)隨著決策過程的深入，決策者將根據自己的意愿，對問題所具備的知識和掌握進一步的信息修改原先的判斷或提供關于問題的新信息。因此，有必要為決策者提供必要的支持，從而具有一定的誘導效果，以免決策者作出與原先不一致的判斷或提供無意義的信息。 Ａ)前者會導致現權值可行域不存在的情形。 Ｂ)后者對改進決策結果不起任何作用.

所以，有必要讓決策者盡可能了解當前的決策情況，如：權值可行域的情況，引導他們提供有助于改進決策結果的信息。多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))為此，我們定義一致性區(qū)間反映了當前條件下目標相對于目標的重要性范圍。所有目標之間相對重要性范圍由如下區(qū)間矩陣反映：多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))求的方法較多，由于是一個凸域，一種簡便的方法是通過計算權值可行域頂點，進而計算。例：考慮一個三目標決策問題，假設決策者給出如下判斷：則權值可行域由如下約束圍成：示意圖多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))容易求出可行域的四個頂點:從而，多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))這時如果決策者給出：由于，所以它不會對原決策結果產生影響。如果決策者給出：由于，出現前后判斷不一致的現象。且當且僅當對任意的存在,且多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))例：找工作問題：目標：工作穩(wěn)定性 單位穩(wěn)定性 個人工作安全性 收入 起薪 加薪情況 事業(yè)發(fā)展機會 繼續(xù)教育機會 單位前景方案：1)國營企業(yè)X2)效益很好的大公司Y3)小公司 Z多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))即，多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))多目標分析2[1]一種處理不精確不完全判斷的決策分析方法(續(xù))*規(guī)范化：[0