matlab-多目標規(guī)劃模型

1、1多目標規(guī)劃模型多目標規(guī)劃模型 在現實生活中在現實生活中,決策的目標往往有多個決策的目標往往有多個,例如例如,對企業(yè)產品的生產管對企業(yè)產品的生產管理理,既希望達到高利潤既希望達到高利潤,又希望優(yōu)質和低消耗又希望優(yōu)質和低消耗,還希望減少對環(huán)境的污還希望減少對環(huán)境的污染等染等.這就是一個多目標決策的問題這就是一個多目標決策的問題.又如選購一個好的計算機系統(tǒng)又如選購一個好的計算機系統(tǒng),似乎只有一個目標似乎只有一個目標,但由于要從多方面去反映但由于要從多方面去反映,要用多個不同的準則要用多個不同的準則來衡量來衡量,比如比如,性能要好性能要好,維護要容易維護要容易,費用要省費用要省.這些準則自然構成了多

2、這些準則自然構成了多個目標個目標,故也是一個多目標決策問題故也是一個多目標決策問題.矛盾性、不可公度性。矛盾性、不可公度性。一般來說一般來說,多目標決策問題有兩類多目標決策問題有兩類.一類是多目標規(guī)劃問題一類是多目標規(guī)劃問題,其對其對象是在管理決策過程中求解使多個目標象是在管理決策過程中求解使多個目標都達到都達到滿意結果的最優(yōu)方案滿意結果的最優(yōu)方案.另一類是多目標優(yōu)選問題另一類是多目標優(yōu)選問題,其對象是在管理決策過程中根據多個目標其對象是在管理決策過程中根據多個目標或多個準則衡量和得出各種備選方案的或多個準則衡量和得出各種備選方案的優(yōu)先等級與排序優(yōu)先等級與排序. 多目標決策由于考慮的目標多多目

3、標決策由于考慮的目標多,有些目標之間又有些目標之間又彼此有矛盾彼此有矛盾,這就使多目標問題成為一個復雜而困難這就使多目標問題成為一個復雜而困難的問題的問題.但由于客觀實際的需要但由于客觀實際的需要,多目標決策問題越來多目標決策問題越來越受到重視越受到重視,因而出現了許多解決此決策問題的方法因而出現了許多解決此決策問題的方法.一般來說一般來說,其基本途徑是其基本途徑是,把求解多目標問題把求解多目標問題轉化為求轉化為求解單目標問題解單目標問題.其主要步驟是其主要步驟是,先轉化為單目標問題先轉化為單目標問題,然后利用單目標模型的方法然后利用單目標模型的方法,求出單目標模型的最優(yōu)求出單目標模型的最優(yōu)解

4、解,以此作為多目標問題的解以此作為多目標問題的解. 化多目標問題為單目標問題的方法大致可分為兩化多目標問題為單目標問題的方法大致可分為兩類類,一類是轉化為一個單目標問題一類是轉化為一個單目標問題,另一類是轉化為多另一類是轉化為多個單目標問題個單目標問題,關鍵是如何轉化關鍵是如何轉化. 下面下面,我們介紹幾種主要的轉化方法我們介紹幾種主要的轉化方法:主要目標法、主要目標法、線性加權和法、字典序法、步驟法。線性加權和法、字典序法、步驟法。f1f21234567810.1多目標決策問題的特征多目標決策問題的特征 在解決單目標問題時，我們的任務是選擇一個或一組變在解決單目標問題時，我們的任務是選擇一個

5、或一組變量量X，使目標函數使目標函數f(X)取得最大（或最?。τ谌我鈨煞桨溉〉米畲螅ɑ蜃钚。τ谌我鈨煞桨杆鶎慕?，只要比較它們相應的目標值，就可以判斷誰優(yōu)所對應的解，只要比較它們相應的目標值，就可以判斷誰優(yōu)誰劣。但在多目標情況下，問題卻不那么單純了。例如，有誰劣。但在多目標情況下，問題卻不那么單純了。例如，有兩個目標兩個目標f1(X)，f2(X),希望它們都越大越好。下圖列出在這兩希望它們都越大越好。下圖列出在這兩個目標下共有個目標下共有8個解的方案。其中方案個解的方案。其中方案1，2，3，4稱為劣解，稱為劣解，因為它們在兩個目標值上都比方案因為它們在兩個目標值上都比方案5差，是可以

6、淘汰的解。而差，是可以淘汰的解。而方案方案5，6，7，8是非劣解（或稱為有效解，滿意解），因為是非劣解（或稱為有效解，滿意解），因為這些解都不能輕易被淘汰掉，它們中間的一個與其余任何一這些解都不能輕易被淘汰掉，它們中間的一個與其余任何一個相比，總有一個指標更優(yōu)越，而另一個指標卻更差。個相比，總有一個指標更優(yōu)越，而另一個指標卻更差。一、解的特點一、解的特點二、模型結構二、模型結構 多目標決策問題包含有三大要素：目標、方案和決策者。多目標決策問題包含有三大要素：目標、方案和決策者。在多目標決策問題中，目標有多層次的含義。從最高層次在多目標決策問題中，目標有多層次的含義。從最高層次來看，目標代表了問

7、題要達到的總目標。如確定最滿意的來看，目標代表了問題要達到的總目標。如確定最滿意的投資項目、選擇最滿意的食品。從較低層次來看，目標可投資項目、選擇最滿意的食品。從較低層次來看，目標可看成是體現總目標得以實現的各個具體的目標，如投資項看成是體現總目標得以實現的各個具體的目標，如投資項目的盈利要大、成本要低、風險要??；目標也可看成衡量目的盈利要大、成本要低、風險要??；目標也可看成衡量總目標得以實現的各個準則，如食品的味道要好，質量要總目標得以實現的各個準則，如食品的味道要好，質量要好，花費要少。好，花費要少。 多目標決策問題中的方案即為決策變量，也稱為多目多目標決策問題中的方案即為決策變量，也稱為

8、多目標問題的解。備選方案即決策問題的可行解。在多目標決標問題的解。備選方案即決策問題的可行解。在多目標決策中，有些問題的方案是有限的，有些問題策中，有些問題的方案是有限的，有些問題 的方案是無限的方案是無限的。方案有其特征或特性，稱之為屬性。的。方案有其特征或特性，稱之為屬性。1、多目標規(guī)劃問題的模型結構0)(0)(. .)(),.,(),()(21XhXgtsXfXfXfXoptFjiTp),.,(21nxxxX 為決策變量如對于求極大(max)型，其各種解定義如下：絕對最優(yōu)解：若對于任意的X，都有F(X*)F(X)有效解：若不存在X，使得F(X*) F(X)弱有效解：若不存在X，使得F(X

9、*)F(X)2、多目標優(yōu)選問題的模型結構 可用效用函數來表示。設方案的效用是目標屬性的函數：),.,()(21pfffUxU并設)(jiijxfa 且各個方案的效用函數分別為),.,()(21pjjjjaaaUxU則多目標優(yōu)選模型的結構可表示如下：0)(0)(. .)(),.,(),()(21XhXgtsXUXUXUXordUjiTp10.2 多目標規(guī)劃問題的求解多目標規(guī)劃問題的求解1、主要目標法、主要目標法 在有些多目標決策問題中，各種目標的重要性程度往往不一樣。其中一個重要性程度最高和最為關鍵的目標，稱之為主要目標法。其余的目標則稱為非主要目標。0)(0)(. .)(),.,(),()(2

10、1XhXgtsXfXfXfXoptFjiTp例如，在上述多目標問題中，假定f1(X)為主要目標，其余p-1個為非主要目標。這時，希望主要目標達到極大值，并要求其余的目標滿足一定的條件，即1,.,2 , 1,)(,.,2 , 1, 0)(,.,2 , 1, 0)(. .)(max1pkXfmjXhniXgtsXfkkji例題例題1 某工廠在一個計劃期內生產甲、乙兩種產品，各產品某工廠在一個計劃期內生產甲、乙兩種產品，各產品都要消耗都要消耗A，B，C三種不同的資源。每件產品對資源的單位三種不同的資源。每件產品對資源的單位消耗、各種資源的限量以及各產品的單位價格、單位利潤和消耗、各種資源的限量以及各

11、產品的單位價格、單位利潤和所造成的單位污染如下表。假定產品能全部銷售出去，問每所造成的單位污染如下表。假定產品能全部銷售出去，問每期怎樣安排生產，才能使利潤和產值都最大，且造成的污染期怎樣安排生產，才能使利潤和產值都最大，且造成的污染最小？最??？解：問題的多目標模型如下0,300103200542404923)(max(600400)(max12070)(max21212121213212211xxxxxxxxxxXfxxXfxxXf對于上述模型的三個目標，工廠確定利潤最大為主要目標。另兩個目標則通過預測預先給定的希望達到的目標值轉化為約束條件。經研究，工廠認為總產值至少應達到20000個單位

12、，而污染控制在90個單位以下，即9023)(20000600400)(213212xxXfxxXf由主要目標法化為單目標問題0,300103200542404990232000060040012070)(max212121212121211xxxxxxxxxxxxxxXf用單純形法求得其最優(yōu)解為90)(,20750)(,4025)(,25.26, 5 .1232121xfxfxfxx2、線性加權和目標規(guī)劃、線性加權和目標規(guī)劃0)(0)(. .)(),.,(),()(21XhXgtsXfXfXfXoptFjiTp在上述目標規(guī)劃中，假定f1(X),f2(X),fp(X)具有相同的量綱,按照一定的規(guī)

13、則分別給fi賦予相同的權系數i，作線性加權和評價函數piiiXfXU1)()(則多目標問題化為如下的單目標問題0)(0)(. .)()(max1XhXgtsXfXUjipiii例如，某公司計劃購進一批新卡車，可供選擇的卡車有如例如，某公司計劃購進一批新卡車，可供選擇的卡車有如下下4種類型：種類型：A1，A2，A3，A4?，F考慮現考慮6個方案屬性：維個方案屬性：維修期限修期限f1，每每100升汽油所跑的里數升汽油所跑的里數f2，最大載重噸數最大載重噸數f3，價價格（萬元）格（萬元）f4，可靠性可靠性f5，靈敏性靈敏性f6。這這4種型號的卡車分別種型號的卡車分別關于目標屬性的指標值關于目標屬性的指

14、標值fij如下表所示。如下表所示。首先對不同度量單位和不同數量級的指標值進行標準化處理。首先對不同度量單位和不同數量級的指標值進行標準化處理。先將定性指標定量化：先將定性指標定量化：可靠性和靈敏性都屬于效益型指標，其打分如下按以下公式作無量綱的標準化處理1*)*(99jjjijijffffa其中：ijijijijffffminmax*變換后的指標值矩陣為：設權系數向量為W=（0.2,0.1,0.1,0.1,0.2,0.3),則925.57)(max*27.40)(925.57)(6 .40)(34)(36144613361226111XUUUaXUaXUaXUaXUjjjjjjjjjjjj故最

15、優(yōu)方案為選購A3型卡車3、分層序列法：、分層序列法：1.基本步驟：把(VP)中的p個目標 按其重要程度排序。依次求單目標規(guī)劃的最優(yōu)解。2. 過程：無妨設其次序為 先求解 得最優(yōu)值 ，記再解 得最優(yōu)值 ，依次進行，直到 得最優(yōu)值則 是在分層序列意義下的最優(yōu)解集合。)(,),(1xfxfppfff,21SxtsxfP. .)(min)(11*1fSfxfxS*111)(122. .)(min)(SxtsxfP*2f1*222)(SfxfxS1. .)(min)(pppSxtsxfP*pf1*)(ppppSfxfxS3. 性質： ，即在分層序列意義下的最優(yōu)解是有效解。證明：反證。設 ，但 ，則必存在

16、 使 即至少有一個j0 ，使 , 由于 ，即 ， 矛盾。得證。4. 進一步討論： 上述方法過程中，當某個問題(Pj)的解唯一時，則問題 的求解無意義，因為解都是唯一的。 實際求解時，有較寬容意義下的分層序列法： 取 為預先給定的寬容值，整個解法同原方法類似，只是取各約束集合時，分別取為：pjPP,10, 011ppjSfxfxSjjjj, 3 , 2,)(1*)(min)(0000*xffxfjSxjjj0jSx)()(00 xfyfjj1, 1),()(0jjxfyfjj)()(xFyFSy *paSxpSx *papSS 4、步驟法（、步驟法（STEM法）法） 這是一種交互方法，其求解過程

17、通過分析者與決策者之間的對話逐步進行，故稱步驟法。 步驟法的基本思想是，首先需要求出原多目標問題的一組理想解(f1*,f2*,fp*)。實際上，這些解fi*(i=1,2,p)無法同時達到，但可以當作一組理想的最優(yōu)值。以理想解作為一個標準，可以估計有效解，然后通過對話，不斷修改目標值，并把降低要求的目標作為新的約束條件加入原來的約束條件中去重新計算，直到決策者得到滿意的解。 步驟法算法如下：第一步：分別求解以下p個單目標問題的最優(yōu)解0)(0)(. .)(max1XhXgtsxcXfjinjjiji得到最優(yōu)解 ，其相應的目標值 即為理想值，此最優(yōu)解處別的目標所取的值用 表示，即 ，把上述計算結果列

18、入下表).,2 , 1(*piXi).,2 , 1(*pifikizpkikXfzikki,.,2 , 1,),(*21*21*11211*121pipppppiiiiipipifzzzXzfzzXzzzfXffffX在表中，確定每一列的最小值并記第i列的最小值為fip(i=1,2,p)第二步：求解0,.,2 , 1,)(*(minSXpiXffiii其中：piiii1這里0*,*0*,*2/1122/112injijpiipiinjijipiiifcffffcfff（1）第三步：將上述模型（1）的解X0與相應的目標值f1(X0), f2(X0), ,fp(X0) 交給決策者去判斷。決策者把這

19、些目標值與理想值進行比較后，如果認為其中某些目標值太壞，另一些目標值可以不要那么太好，可以把比較好的目標值中的某一個修改得差一些，以使水平太壞的目標得到改善。 當決策者減少了第j個目標的值 之后，約束條件S應該改為S*jfpijiXfXfkjfXfXfSSiijjj,.,2 , 1,),()(,.,2 , 1,)()(*00在進行下一次迭代時，對應于降低了要求的那些目標fj(j=1,2,k)的權系數i應該設為0。這種迭代繼續(xù)下去，直到決策者滿意為止。例題：例題：某公司考慮生產兩種光電太陽能電池：產品甲和產品乙。這種生產過程會在空氣中引起放射性污染。因此，公司經理有兩個目標：極大化利潤與極小化總

20、的放射性污染。已知在一個生產周期內，每單位甲產品的收益是1元，每單位乙產品的收益是3元。而放射性污染的數量，每單位甲產品是1.5個單位,每單位乙產品是1個單位.由于機器能力(小時)、裝配能力（人時）和可用的原材料（單位）的限制，約束條件是)(725)(42 . 02 . 0)(825. 05 . 0212121原材料裝配能力機器能力xxxxxx目標有兩個:一是利潤最大,二是污染最小.該問題的多目標規(guī)劃模型如下:)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(,3)()(),()(max21212121221121原材料裝配能力機器能力xxxxxxxxXfxxXfXf

21、XfXFT解:首先,分別求解兩個單目標問題的最優(yōu)解,由它們得到的目標函數值組成理想解.)(725)(42 . 02 . 0)(825. 05 . 03)(max212121211原材料裝配能力機器能力xxxxxxxxXf)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(max212121212原材料裝配能力機器能力xxxxxxxxXf46*)13, 7(1*1fX0*)0 , 0(1*2fX由此,構造支付表由此計算兩個目標與理想值偏離的權重637. 0,363. 0,555. 0,316. 02121解下列線性規(guī)劃問題:0,7254)2 . 02 . 08)25. 0

22、5 . 0)230(637. 0)346(363. 0min212121212121xxxxxxxxxxxx由此求得,064. 7,192.21,064. 7, 02121ffxx分析者把計算結果交給決策者,決策者將目標值與理想值(21.192,-7.064)與理想值(46,0)比較,如果認為f2是滿意的,但利潤太低,并認為污染可接受到10個單位.于是,約束集修改成0,192.213105 . 17254)2 . 02 . 08)25. 05 . 0212121212121xxxxxxxxxxxx進行下一輪迭代.首先設2=0,并計算得1=1.將模型修改為0,7254)2 . 02 . 08)2

23、5. 05 . 0192.21310)5 . 1346min21212121212121xxxxxxxxxxxxxx由此求得:10,3010, 02121ffxx決策者把這一結果與前一輪的解及理想值作比較,認為兩個目標值都比較滿意,則迭代結束. 目標規(guī)劃模型目標規(guī)劃模型 線性規(guī)劃問題都是處理單個目標的情況，但是在現實世界中有許多問題具有多個目標，這些目標的重要性各不相同，往往有不同的量綱，有的目標相互依賴，例如決策者既希望實現利潤最大，又希望實現產值最大；有的相互抵觸，如決策者既希望充分利用資源，又不希望超越資源限量。而決策者希望在某些限制條件下，依次實現這些目標。這就是目標規(guī)劃所要解決的問題

24、。當所有的目標函數和約束條件都是線性時，我們稱其為線性目標規(guī)劃問題。在這里我們主要討論線性目標規(guī)劃問題。一、目標規(guī)劃模型的建立一、目標規(guī)劃模型的建立 引例引例1： 對于生產計劃問題： 甲 乙 資源限額 材料 2 3 24 工時 3 2 26 單位利潤 4 3 現在工廠領導要考慮市場等一系列其他因素，提出如下目標：（1）根據市場信息，甲產品的銷量有下降的趨勢，而乙產品的銷量有上升的趨勢，故考慮乙產品的產量應大于甲產品的產量。（2）盡可能充分利用工時，不希望加班。（3）應盡可能達到并超過計劃利潤30元?，F在的問題是：在原材料不能超計劃使用的前提下，如何安排生產才能使上述目標依次實現？解：（1）決策

25、變量：仍設每天生產甲、乙兩種產品各為x1和x2 偏差變量：對于每一目標，我們引進正、負偏差變量。 如對于目標1，設d1-表示乙產品的產量低于甲產品產量的數，d1+表示乙產品的產量高于甲產品產量的數。稱它們分別為產量比較的負偏差變量和正偏差變量。則對于目標1，可將它表示為等式約束的形式 -x1+x2+ d1- d1+ =0 (目標約束) 同樣設d2-和d2+分別表示安排生產時，低于可利用工時和高于可利用工時，即加班工時的偏差變量，則對目標2，有 3x1+2x2+ d2-d2+ =26 對于目標3，設d3-和d3+分別表示安排生產時，低于計劃利潤30元和高于計劃利潤30元的偏差變量，有： 4x1+

26、3x2+ d3-d3+ =30 （2）約束條件：有資源約束和目標約束 資源約束：2x1+3x224 目標約束：為上述各目標中得出的約束 （3）目標函數：三個目標依次為： minZ1=d1- ，minZ2=d2+d2- ，minZ3=d3- 因而該問題的數學模型可表述如下： minZ1=d1- ，minZ2=d2+d2-，minZ3=d3- 2x1+3x224 st -x1+x2+ d1- d1+ =0 3x1+2x2+ d2-d2+ =26 4x1+3x2+ d3-d3+ =30 案例案例2（提級加新問題）（提級加新問題） 某公司的員工工資有四級，根據公司的業(yè)務發(fā)展情況，準備招收部分新員工，并

27、將部分員工的工資提升一級。該公司的員工工資及提級前后的編制表如下，其中提級后編制是計劃編制，允許有變化，其中1級員工中有8%要退休。公司領導的目標如下：（1）提級后在職員工的工資總額不超過550千元；（2）各級員工不要超過定編人數；（3）為調動積極性，各級員工的升級面不少于現有人數的18%；（4）總提級面不大于20%，但盡可能多提；（5）4級不足編制人數可錄用新工人。 問：應如何擬定一具滿意的方案，才能接近上述目標？ 解：（1）決策變量：設x1,x2,x3,x4分別表示提升到1，2，3級和新錄用的員工數。 偏差變量：為各目標的正、負偏差變量。 （2）約束條件：1） 提級后在職員工的工資總額不超

28、過550千元；8(10-108%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1-d1+=550 2）各級員工不要超過定編人數1級有： 10-10 8%+x1+d2-d2+=10 2級有： 20-x1+ x2+d3-d3+=22 3級有： 40-x2+ x3+d4-d4+=52 4級有： 30-x3+ x4+d5-d5+=303）各級員工的升級面不少于現有人數的18%對2級有： x1+d6-d6+=20 18%對3級有： x2+d7-d7+=40 18% 對4級有： x3+d8-d8+=30 18% 4）總提級面人數不大于20%，但盡可能多提 x1+ x2

29、+ x3+d9-d9+=100 20% （3）目標函數：minZ1=d1+minZ2=d2+d3+ d4+ d5+minZ3=d6-+ d7-+ d8-minZ4=d9+ d9-案例案例3 有三個產地向四個銷地供應物資。產地有三個產地向四個銷地供應物資。產地Ai(i=1,2,3)的供應量的供應量ai、銷地銷地Bj(j=1,2,3,4)的需要量的需要量bj、各產銷地之間各產銷地之間的單位物資運費的單位物資運費Cij如表如表2所示。表中，所示。表中，ai和和bj的單位為噸的單位為噸，Cij的單位為元的單位為元/噸。編制調運方案時要求按照相應的優(yōu)噸。編制調運方案時要求按照相應的優(yōu)先級依次考慮下列七個

30、目標：先級依次考慮下列七個目標：P1：B4是重點保證單位，其需要量應盡可能全部滿足；是重點保證單位，其需要量應盡可能全部滿足；P2：A3向向B1提供的物資不少于提供的物資不少于100噸；噸；P3：每個銷地得到的物資數量不少于其需要量的每個銷地得到的物資數量不少于其需要量的80%； P4：實際的總運費不超過當不考慮實際的總運費不超過當不考慮P1至至P6各目標時的最小各目標時的最小總運費的總運費的110%，這里的最小總費用利用第三大題中第，這里的最小總費用利用第三大題中第2小題小題求出的結果；求出的結果；P5：因路況原因，盡量避免安排因路況原因，盡量避免安排A2的物資運往的物資運往B4；P6：對對

31、B1和和B3的供應率要盡可能相同；的供應率要盡可能相同；P7：力求使總運費最省。力求使總運費最省。試建立該問題的運籌學模型。試建立該問題的運籌學模型。 解：用表上作業(yè)法可求得不考慮解：用表上作業(yè)法可求得不考慮P1至至P6各目標時的最小運各目標時的最小運費調運方案，相應的最小運費為費調運方案，相應的最小運費為2950元元（1）決策變量：設）決策變量：設Ai運往運往Bj的物資為的物資為xij噸噸（2）約束條件：）約束條件： 3141998833231331211177243141665533231344322212333121112231113424143433323124232221141312

32、1129500)(450200)(0324536080160100250400200300ijijijijijijddxcddxxxxxxddxddxcddxxxddxxxddxxxddxddxxxxxxxxxxxxxxx產量約束產量約束B4銷量要滿足銷量要滿足銷量銷量80%的限制的限制供應率盡可能相同供應率盡可能相同二、目標規(guī)劃的解法二、目標規(guī)劃的解法 由于目標規(guī)劃有多個目標，各個目標又有相對不同的重要性，求解時是首先滿足重要性權數大的目標，再滿足重要性權數次大的目標，所以并不能保證所有的目標都能達到，所求的解也不一定是最優(yōu)解，而只能求出滿意解。 （3）目標函數）目標函數dZddZdZdZd

33、ddZdZdZ97886756454332211minminminminminminmin 求解目標規(guī)劃的仍用單純形法，但是與線性規(guī)劃的單純求解目標規(guī)劃的仍用單純形法，但是與線性規(guī)劃的單純形法不同的是，此時檢驗數行不再是一行，而是變化為一形法不同的是，此時檢驗數行不再是一行，而是變化為一個檢驗數矩陣。個檢驗數矩陣。 例例4 用單純形法求解如下線性目標規(guī)劃模型 minZ1=d1-，minZ2=d2+d2-，minZ3=d3- 2x1+3x224 加入松馳變量化為標準形 2x1+3x2+ x3=24 st -x1+x2+ d1- d1+ =0 3x1+2x2+ d2-d2+ =26 4x1+3x2

34、+ d3-d3+ =30 解 （1）取x3，d1-，d2-，d3-為基變量，建立初始單純形表 -1-2-1123-13402630Z1Z2Z3000-100-100-10000010010010010003 1 232-1342402630 x3d1-d2-d3-d3+d2+d1+d3-d2-d1-x3x2x1bXB迭代的步驟完全與線性規(guī)劃的單純形法一樣。（2）滿意解的判定：檢驗數矩陣的每一列從上至下第一個非零元為負數，則解為滿意解。迭代的最優(yōu)表如下： -2-1-1-11-1020Z1Z2Z3100000-106/5-2/5-13/5-10000010-6/52/51-3/57/51/5-11

35、/50100000118/524/5224/5d3+x2d2-x1d3+d2+d1+d3-d2-d1-x3x2x1bXB因而滿意解為：x1=24/5，x2=24/5，d2-=2，d3+=18/5 其中第一、三目標已達到最優(yōu)，第二個目標未達最優(yōu)。目標利潤 Z=4x1+3x2=168/541層次分析法層次分析法一、層次分析法的基本原理一、層次分析法的基本原理 層次分析法，又稱AHP(Analytic Hirrarchy Process)方法，是美國運籌學家薩蒂(T.Saaty)提出的一種多目標、多準則的決策分析方法。該方法被廣泛應用于工程、經濟、軍事、政治、外交等領域，解決了諸如系統(tǒng)評價、資源分配

36、、價格預測、項目選擇等許多重要問題，是一種定量分析與定性分析相結合的有效方法。用層次分析法作決策分析，首先要把問題層次化。根據問題的性質和要達到的總目標，將問題分解為不同的組成因素，并按照因素間的相互影響以及隸屬關系按不同層次聚集組合，形成一個多層次的分析結構模型。最終把系統(tǒng)分析歸結為最低層（如決策方案）相對于最高層（總目標）的相對重要性權值的確定或相對優(yōu)劣次序的排序問題，從而為決策方案的選擇提供依據。 層次分析法大體分為六個步驟層次分析法大體分為六個步驟1）明確問題：為了運用AHP進行系統(tǒng)分析，首先要對問題有明確的認識，弄清問題范圍、所包含的因素及其相互關系、解決問題的目的、是否具有AHP所

37、描述的特征。2）建立層次結構模型：將問題中所包含的因素劃分為不同層次。例如，對于決策問題，通常可以劃分為下面幾個層次：最高層：表示解決問題的目的，稱為目標層。中間層：表示采取某種措施或政策實現預定目標的涉及的中間環(huán)節(jié)，一般又分為策略層、準則層等。最低層：表示解決問題的措施或方案，稱為措施層或方案層。如下圖所示。決策目標準則1準則1準則m子準則1子準則2子準則k方案1方案2方案n目標層目標層準則層準則層子準則層子準則層方案層方案層3）構造判斷矩陣針對上一層某元素，對每一層次各個元素的相對重要性進行兩兩比較，并給出判斷。這些判斷用數值表示出來，寫成矩陣形式，即所謂的判斷矩陣。nnnnnnnnkbb

38、bBbbbBbbbBBBA2122221211211121B其中bij表示對于Ak而言，Bi對Bj的相對重要性，通常bij取1,2,9及它們的倒數，其含義為：它們之間的數2，4，6，8及各數的倒數有相應的類似意義。顯然，對判斷矩陣有).,2 , 1,( , 1,1njibbbiijiij因此，對于n階判斷矩陣，我們僅需對n(n-1)/2個元素給出數值。4）層次單排序及其一致性檢驗 所謂層次單排序，即把同一層次相應元素對于上一層次某元素相對重要性的排序權值求出來。其方法是計算判斷矩陣A的滿足等式 的最大特征值 和對應的特征向量W，這個特征向量就是單排序權值。WAWmaxmax 可以證明，對于n階

39、判斷矩陣，其最大特征根 為單根，且 ， 所對應的特征向量均由正數組成。特別地，當判斷矩陣具有完全一致性時，有 ，這里，所謂完全一致性是指對于判斷矩陣來說，存在maxnmaxmaxnmax),.,2 , 1,(nkjibbbjkikij為檢驗判斷矩陣的一致性，需要計算一致性指標1maxnnCI此外，還需要判斷矩陣的平均隨機一致性指標RI。對于1至9階矩陣，RI的值如下表。 在這里，對于1,2階判斷矩陣，RI只是形式上的，因為1，2階判斷矩陣總具有完全一致性，當階數大于2時，判斷矩陣的一致性指標CI與同階平均隨機一致性指標RI之比稱謂隨機一致性比率，記為CR，CR=CI/RI0.10時，即認為判斷

40、矩陣具有滿意的一致性，否則就需要調整判斷矩陣，使其具有滿意的一致性。5）層次總排序 計算同一層次所有元素對于最高層相對重要性的排序權值，稱為層次總排序。這一過程是最高層次到最低層次逐層進行的。若上一層次A包含m個元素A1,A2,Am，其層次總排序權值分別為a1,a2,am，下一層次B包含n個元素B1,B2,Bn，它們對于元素Aj的層次單排序權值分別為b1j,b2j,bnj（當Bk與Aj無關系時,bkj=0），此時，層次總排序權值為mAAA21maaa21nBB21Bnwww21nmnnmmbbbbbbbbb212222111211nibawmjijji,.,2 , 1,16）層次總排序的一致性

41、檢驗。 這一步也是從高到低逐層進行的。如果B層次某些元素對于Aj單排序的一致性指標為CIj，相應的平均隨機一致性指標為RIj，則B層次總排序隨機一致性比率為mjjjmjjjRIaCIaCR11類似地，當CR0.10時，認為層次總排序結果具有滿意的一致性，否則需要重新調整判斷矩陣的元素取值。10.5 層次分析法的計算問題層次分析法的計算問題 層次分析法計算的根本問題是如何計算判斷矩陣的最大特征根其對應的特征向量.一般來說,計算判斷矩陣最大特征根及其對應特征向量,并不需要追求較高的精確定度.這是因為判斷矩陣本身相當的誤差范圍.應用層次分析法給出的層次中各種元素優(yōu)先排序權值從本質上來說是表達某種定性

42、的概念.因此,從實用性來看,往往希望使用較為簡單的近似算法.下面介紹二種稱之為方根法和和積法的近似算法. 1、方根法的步驟如下:(1)計算判斷矩陣B每一行元素的乘積Mi.nibMnjiji,.,2 , 1,1(2)計算Mi的n次方根ViniiMV (3)對向量V=(V1,V2,Vn)T規(guī)一化,即njjiiVVW1則W=(W1,W2,Wn)T.即為所求的特征向量(4)計算判斷矩陣的最大特征根maxniiinWBW1max)(式中(BW)i表示向量BW的第i個分量.容易證明：當正互反矩陣 為一致性矩陣時，方根法可得到精確的最大特征值與相應的特征向量。nnijaA)(證明：設 為一致性矩陣， 為其最大特征值， 為相應的特征向量，且是歸一化的。nnijaA)(maxTnuuuu),.,(21由于jiijuuan ,max令njiusnnjj, 2 , 1,/11suaMinnjjii/11顯然，歸一化后， 于是用公式Tnuuuw),(21niiiwAwn1)(1求得的最大特征值為n例題例題6 某廠準備購買一臺計算機,希望功能強,價格低,維護容易.