運籌學-第十章-多目標決策

第十章多目標決策多目標決策問題及其有效解偏愛和多目標決策問題的求解評價函數法目標規(guī)劃層次分析法軟件應用10.1多目標決策問題及其有效解多目標決策問題引例

多目標決策問題的有效解

例1（投資決策問題）公司有50萬元資金，打算向兩個項目投資。已知項目1的利潤為投資額的10%，但風險??；項目2的利潤為投資額的20%，但風險大。由于其他原因，公司對項目1的投資不能少于10萬元。試問：如何投資，才能兼顧利潤和風險？x1

+x2

50

x1

10

x1，x2

0

maxz1=0.1x1

+0.2x2maxz2=x1

-x2s.t.設x1為項目1的投資額，x2為項目2的投資額

常用的風險度量：VaR&CVaR例2（生產計劃問題）某工廠生產5種產品：1號品，…，5號品。該廠生產i號品的生產能力是ai

件/小時，每件i號品可獲利

元。根據市場預測，下一季度3,4,5號品的最大銷售量為bi噸，而市場對1和2號品的需求是盡可能多的。工廠下一季度的生產能力為T小時。試問：如何安排下一季度的生產計劃，在避免開工不足的條件下，使工人加班時間盡量地少、工廠獲利最大、滿足市場對1號品和2號品盡可能多的需求？設該廠下一季度生產i號品的時間為xi小時（i=1,…,5）多目標最優(yōu)化模型

(MultiobjectiveOptimization/VectorOptimization)

其中多目標決策問題的共同特點目標之間的不可公度性：指各個目標一般沒有統(tǒng)一的衡量標準，因而很難進行比較目標之間的沖突性：大部分多目標決策問題存在著沖突。即如果采用某種方案去改進一個目標值，很可能會使另一目標值變壞多目標線性規(guī)劃分層多目標最優(yōu)化模型第1優(yōu)先層，…，第L優(yōu)先層與偏好有關多目標決策問題的有效解對于一個可行解，如果不存在“優(yōu)于”它的可行解，則稱其為有效解（帕累托最優(yōu)解；非劣解）設。若不存在使得且至少有一個是嚴格不等式，則稱是（VP）的有效解例1的有效解P3(10,40)P1(10,0)x10x2決策空間P’2(5,50)P’1(1,10)P’3(9,-30)A(7,10)z2z1目標空間設。若不存在使得則稱是弱有效解找不到一個解，使得各目標值都比的嚴格小若，則它是有效解的充要條件是為的最優(yōu)解有效解判別方法之一對多目標線性規(guī)劃如何判斷一個可行解是否為有效解？

結論：若為LP的最優(yōu)解，則必為有效解若不是LP的最優(yōu)解，而是y，則y即是有效解例已知一個多目標決策問題（Max問題）可行解(2,0,0)是否為有效解?

構建線性規(guī)劃有效解存在定理設X?Rn.若f(x)=(f1(x),…,fp(x))中的各函數fk(x)(k=1,…,p)在X上連續(xù)，并存在使集合是有界閉集，則（VP）存在有效解

有效解判別方法之二對若wk>0，是(Pw)的最優(yōu)解，則它是有效解若wk≥0且至少有一個>0，是(Pw)的最優(yōu)解，則它是弱有效解

有效解判別方法之三10.2偏愛和多目標決策問題的求解

偏愛與價值函數多目標決策問題的偏愛結構

多目標決策問題的求解思路

偏愛例某公司準備提升一位部門經理，由人事部門對三個候選人就能力、合作精神、進取心進行評優(yōu)，給出分數如下：

得分候選人1(x1)候選人2(x2)候選人3(x3)能力789合作897進取978該公司總裁在選拔干部時，注意特長，他喜歡在某一方面比別人分數高的人，當某人一項指標高過另一人2分，他就認為前者好，因此他的看法是：

該公司副總裁則注意合作精神和進取心，他認為這兩項評分之和高者是優(yōu)秀人才，因此他的看法是：

每個人有不同的偏愛，因而產生不同的選擇

價值函數

U(x1)>U(x2),A(7,10)B(6,45)C(8,-20)z2z1偏愛結構

多目標決策問題的求解利用決策者偏愛結構確定價值函數，將多目標問題轉化為單目標問題線性加權法理想點法極大極小法參考目標法10.3評價函數法線性加權法最簡單、最基本的方法（其中)若決策者認為某可行解是一個比較好的選擇，則例某公司有A,B,C三種產品，利用兩種資源I,II,數據如下：ABC總量I756250II695210價格系數10.80.9產量111外銷總量0.40.60.2

理想點法理想點：通過定義目標與理想點之間的距離，將多目標問題轉化為單目標問題來求解距離定義可采用幾種方式：距離模評價函數p-模評價函數極大模評價函數幾何平均評價函數例（極大模評價函數）權重確定方法α－法均差排序法專家小組法判斷矩陣法其他求解多目標規(guī)劃的方法交互規(guī)劃法逐步寬容約束法權衡比替代法逐次線性加權和法混合優(yōu)選法－－多目標混合最優(yōu)化模型分目標乘除法功效函數法選擇法分層求解法－－分層模型完全分層法，分層評價法，分層單純形法目標規(guī)劃法10.4目標規(guī)劃目標規(guī)劃的產生與發(fā)展目標規(guī)劃模型目標規(guī)劃的產生與發(fā)展目標規(guī)劃由美國學者查恩斯與庫伯于1961年首次提出，基本思想是求盡可能接近某個目標值的解1965年，艾吉里在處理多目標問題、分析各類目標的重要性時，引入了賦予各目標一個優(yōu)先因子及加權系數的概念，進一步完善了目標規(guī)劃的數學模型求解目標規(guī)劃的方法則由杰斯基萊恩和桑·李提出并加以改進目標規(guī)劃是在線性規(guī)劃的基礎上，為適應企業(yè)經營管理中多目標決策的需要而逐步發(fā)展起來的。目標規(guī)劃是一種數學方法基本含義：在一定約束條件下，要求多個目標達到或盡可能接近于給定的對應目標值特點：既保持了線性規(guī)劃易于計算的特點，又克服了線性規(guī)劃只能解決單一目標優(yōu)化問題的局限性目標規(guī)劃模型目標函數目標值引入距離得到目標規(guī)劃模型分層目標規(guī)劃模型不一定是理想值

距離的若干種定義

fk

關于的正偏差fk

關于的負偏差

由定義知一般目標規(guī)劃為

可以略去r=1距離定義下的目標規(guī)劃模型

r=∞距離定義下的目標規(guī)劃模型x1

+x2

50

x1

10

x1，x2

0

max(0.1x1

+0.2x2,x1

-x2)s.t.例1

令目標點f＊=(9,15)，得到r=1距離定義下的目標規(guī)劃模型

安全度，理想點(9,50)仍令目標點f*=(9,15)，可得r=∞距離定義下的目標規(guī)劃模型轉化為線性規(guī)劃模型仍令目標點f*=(9,15).決策者希望，若安全度比15小，則盡量接近15；若超過15，則多少均無差別.對利潤目標亦然.即要求負偏差盡可能地小若決策者對各目標的偏差有不同偏重，可以適當添加權重目標規(guī)劃的形式：Minf(d+,d-)

要求盡量接近目標值，即正負偏差都要盡可能地小。則有Minf(d+,d-)要求不超過目標值，即允許達不到目標值，但盡量不超過目標值，即正偏差盡可能地小。則有

Minf(d+)要求超過目標值，超過量不限，即負偏差變量要盡可能地小。則有Minf(d-)對具體問題，可根據決策者的要求來構造適當的目標規(guī)劃若決策者對各目標偏差劃分不同等級，也可以對目標賦予優(yōu)先因子，得到分層的目標規(guī)劃例某廠生產A，B兩種產品，具體情況如表：現管理部門提出三級目標：第一級目標：每班產值達到750元第二級目標：充分利用兩個車間的工時第三級目標：盡量減少加班時間

試利用目標規(guī)劃法在爭取上述管理目標實現的條件下，擬訂一個滿意生產規(guī)劃單位消耗A產品B產品生產能力（小時/班）加工車間1360裝配車間1140產值（元/件）1525設x1,

x2

分別為兩種產品的產量，正偏差變量dk+表示決策值超過目標值的部分，負偏差變量dk-

表示決策值未達到目標值的部分。則分層目標規(guī)劃模型為分層多目標規(guī)劃……例某電視機廠裝配黑白和彩色兩種電視機，每裝配一臺電視機需占用裝配線1小時，裝配線每周計劃開動40小時，預計市場每周彩色電視機的銷售量是24臺，每臺獲利80元；黑白電視機的銷售量是30臺，每臺獲利40元。該廠確定的目標是：第一優(yōu)先級：充分利用裝配線每周計劃開動40小時第二優(yōu)先級：允許裝配線加班，但每周加班時間盡量不超過10小時第三優(yōu)先級：裝配電視機的數量盡量滿足市場的需要試建立該問題的目標規(guī)劃模型設x1,x2

分別表示彩色和黑白電視機的產量，引進正負偏差變量，得目標規(guī)劃為練習

某工廠生產I、II兩種產品，有關數據見表。試求：獲利最大的生產方案III擁有量原材料（kg）2111設備（hr）1210利潤（萬元/件）810解：設x1,x2

分別為生產I、II的件數，則這是一個單目標線性規(guī)劃問題，不難求得最優(yōu)決策方案為x1*=4，x2*=3，z*=62在實際中，決策時需要考慮一系列其它因素，例如：（1）根據市場信息，產品I的銷售量有下降的趨勢，故考慮產品I的產量不大于產品II的產量（2）超過計劃供應的原材料，需用高價采購，這就使成本增加（3）應盡可能充分利用設備的臺時，但不希望加班（4）應盡可能達到并超過計劃利潤指標56元這樣在考慮產品決策時，便成為多目標決策問題。目標規(guī)劃的方法是解這類決策問題的方法之一設x1,

x2

分別為兩種產品的產量，正偏差變量dk+表示決策值超過目標值的部分，負偏差變量dk-

表示決策值未達到目標值的部分。則分層目標規(guī)劃模型為目標規(guī)劃與線性規(guī)劃相比有以下優(yōu)點1.線性規(guī)劃只能處理一個目標，而現實問題往往要處理多個目標。目標規(guī)劃即能統(tǒng)籌兼顧地處理多個目標的關系，求得更切合實際要求的解2.線性規(guī)劃立足于求滿足所有約束條件的最優(yōu)解。而在實際問題中，可能存在相互矛盾的約束條件。目標規(guī)劃可以在相互矛盾的約束條件下找到滿意解3.目標規(guī)劃的最優(yōu)解指的是盡可能地達到或接近一個或若干個已給定的指標值

4.線性規(guī)劃的約束條件是不分主次地同等對待，而目標規(guī)劃可根據實際的需要給予輕重緩急的考慮

10.5層次分析法

（AHP,AnalyticHierarchyProcess)概述具體原理與步驟應用舉例判斷矩陣的一致性矩陣特征向量計算法概述層次分析法是由美國匹茲堡大學教授T.L.Saaty在70年代中期提出的。其基本思想是把一個復雜問題分解為各個組成因素，并將這些因素按支配關系分組，從而形成一個有序的遞階層次結構。通過兩兩比較的方式確定層次中諸因素的相對重要性，然后綜合人的判斷以確定決策諸因素相對重要性的總排序層次分析法的出現給決策者解決那些難以定量描述的決策問題帶來了極大的方便，從而使它的應用幾乎涉及任何科學領域步驟建立層次結構模型兩兩比較構造判斷矩陣層次單排序及其一致性檢驗層次總排序層次總排序的一致性檢驗(1)建立層次結構模型明確目標建立層次結構(多階層次結構)比如：（選人才的四標準）德、勤、能、績、（?。﹤€人能力，組織能力進取心，執(zhí)行力；業(yè)績增長如何，效率如何，戰(zhàn)略舉措如何，人才培養(yǎng)如何。A型B型C型例：人才甄選指標體系潛質思想素質知識水平能力素質專業(yè)相關度學歷企業(yè)經歷競爭意識風險意識創(chuàng)新意識人才意識基礎和專業(yè)知識培訓和學習交流經濟管理水平決策能力判斷能力協(xié)調能力應變能力進而轉換成層次結構模型兩兩比較構造判斷矩陣例如

B=具體標度見下頁長相

品質財富長相品質

財富111判斷矩陣標度確定方法標度含

義1甲乙相比，具有同樣重要性。3甲乙相比，甲比乙稍微重要。5甲乙相比，甲比乙明顯重要。7甲乙相比，甲比乙顯得很重要。9甲乙相比，甲比乙顯得極重要。2，4，6，8表示上述兩相鄰判斷的中值倒數（如1/3）表示甲與乙相比，乙比甲稍重要。例如：某單位擬從3名干部中選拔一人擔任領導職務，選拔標準是:(1)健康水平、(2)業(yè)務知識、(3)寫作能力、(4)口才、(5)政策水平、(6)工作作風。調查得到判斷矩陣如下：

按行求積開方根規(guī)一化（3）層次單排序及其一致性檢驗層次單排序方法和積法按列規(guī)一化(以一列為例)按行求和(以一行為例）對向量規(guī)一化(例)方根法：按行求積——求n(階）方根——規(guī)一化存在眾多方法。。。。。。階數(n)123456789RI000.580.91.121.241.321.411.45一致性檢驗(R.I見下頁)檢驗準則；若C.R<0.1,則滿足一致性；若C.R>=0.1,則不滿足一致性，就必須重新確定（4）層次總排序（5）層次總排序的一致性檢驗舉例:(一般)應用舉例某廠有一筆企業(yè)留成利潤，要由廠領導和職代會決定如何使用。可供選擇的方案有：作為獎金發(fā)給職工；擴建職工宿舍、食堂、托兒所等福利設施；辦職工業(yè)余技術學校；建圖書館、俱樂部和文體工隊；引進新技術設備進行企業(yè)技術改造等。從調動職工勞動積極性，提高職工文化技術水平和改善職工物質文化生活狀況來看，這些方案都各有其合理的因素。如何使工廠這筆企業(yè)留成利潤更合理地使用，進一步促進企業(yè)發(fā)展，這是廠領導和職代會所面臨需要分析的問題。準則層C措施層PA：合理使用企業(yè)利潤促進企業(yè)新發(fā)展C1：調動職工勞動積極性C2：提高企業(yè)技術水平C3：改善職工物質文化生活P1：發(fā)獎金P2：擴建集體福事業(yè)P3：辦職工業(yè)余技校P4：建圖書館、俱樂部P5：引進新設備目標層A判斷矩陣A—C

（相對于企業(yè)發(fā)展的總目標，各準則之間的相對重要性比較）AC1C2C3C111/51/3C2513C331/31判斷矩陣C1—P