最優(yōu)化之多目標規(guī)劃

1、曲阜師范大學數(shù)學系曲阜師范大學數(shù)學系Qufu Normal University 主講人：呂迪迪主講人：呂迪迪最優(yōu)化模型最優(yōu)化模型 -多目標規(guī)劃多目標規(guī)劃l多目標規(guī)劃解的討論多目標規(guī)劃解的討論非劣解非劣解l多目標規(guī)劃及其求解技術(shù)簡介多目標規(guī)劃及其求解技術(shù)簡介效用最優(yōu)化模型效用最優(yōu)化模型 罰款模型罰款模型約束模型約束模型 目標規(guī)劃模型目標規(guī)劃模型目標達到法目標達到法l多目標規(guī)劃應(yīng)用實例多目標規(guī)劃應(yīng)用實例多目標規(guī)劃是數(shù)學規(guī)劃的一個分支。多目標規(guī)劃是數(shù)學規(guī)劃的一個分支。研究研究多于一個的目標函數(shù)多于一個的目標函數(shù)在在給定區(qū)域給定區(qū)域上的最優(yōu)化。又稱多上的最優(yōu)化。又稱多目標最優(yōu)化。通常記為目標最優(yōu)化。

2、通常記為 MOP(multi-objective programming)。在很多實際問題中，例如經(jīng)濟、管理、軍事、科學和工程在很多實際問題中，例如經(jīng)濟、管理、軍事、科學和工程設(shè)計等領(lǐng)域，衡量一個方案的好壞往往難以用一個指標來設(shè)計等領(lǐng)域，衡量一個方案的好壞往往難以用一個指標來判斷，而需要用多個目標來比較，而這些目標有時不甚協(xié)判斷，而需要用多個目標來比較，而這些目標有時不甚協(xié)調(diào)，甚至是矛盾的。因此有許多學者致力于這方面的研究。調(diào)，甚至是矛盾的。因此有許多學者致力于這方面的研究。1896年法國年法國經(jīng)濟學家經(jīng)濟學家 V. 帕雷托最早研究帕雷托最早研究不可比較目標的優(yōu)不可比較目標的優(yōu)化問題，之后，化

3、問題，之后，J.馮馮諾伊曼、諾伊曼、H.W.庫恩、庫恩、A.W.塔克、塔克、A.M.日夫里翁等日夫里翁等數(shù)學家做了深入的探討數(shù)學家做了深入的探討，但是，但是尚未有一個完全尚未有一個完全令人滿意的定義令人滿意的定義。求解多目標規(guī)劃的方法大體上有以下幾種：求解多目標規(guī)劃的方法大體上有以下幾種：一種是一種是化多為少的方法化多為少的方法 ， 即把多目標化為比較容易求解的即把多目標化為比較容易求解的單目標或雙目標，如主要目標法、線性加權(quán)法、理想點法單目標或雙目標，如主要目標法、線性加權(quán)法、理想點法等；等；另一種叫另一種叫分層序列法分層序列法，即把目標按其重要性給出一個序列，即把目標按其重要性給出一個序列

4、，每次都在前一目標最優(yōu)解集內(nèi)求下一個目標最優(yōu)解，直到每次都在前一目標最優(yōu)解集內(nèi)求下一個目標最優(yōu)解，直到求出共同的最優(yōu)解。求出共同的最優(yōu)解。對多目標的線性規(guī)劃除以上方法外還可以適當對多目標的線性規(guī)劃除以上方法外還可以適當修正單純形修正單純形法法來求解；還有一種稱為來求解；還有一種稱為層次分析法層次分析法，是由美國運籌學家，是由美國運籌學家沙旦于沙旦于70年代提出的，這是一種定性與定量相結(jié)合的多目年代提出的，這是一種定性與定量相結(jié)合的多目標決策與分析方法，對于目標結(jié)構(gòu)復雜且缺乏必要的數(shù)據(jù)標決策與分析方法，對于目標結(jié)構(gòu)復雜且缺乏必要的數(shù)據(jù)的情況更為實用。的情況更為實用。 多目標規(guī)劃模型多目標規(guī)劃模型

5、（一）任何多目標規(guī)劃問題，都由兩個基本部分組成：（一）任何多目標規(guī)劃問題，都由兩個基本部分組成： （1 1）兩個以上的目標函數(shù)；）兩個以上的目標函數(shù)； （2 2）若干個約束條件。）若干個約束條件。 （二）對于多目標規(guī)劃問題，可以將其數(shù)學模型一般地描（二）對于多目標規(guī)劃問題，可以將其數(shù)學模型一般地描寫為如下形式：寫為如下形式： )(max(min)(max(min)(max(min)(XfXfXfXFZk21 mmgggGXXXX2121)()()()( s.t. 式中： 為決策變量向量。 TnxxxX,21 )(max(min)XFZ GXts )(.縮寫形式：縮寫形式：有有n個決策變量，個決

6、策變量，k個目標函數(shù)，個目標函數(shù)， m個約束方程，個約束方程，則：則： Z=F(X) 是是k維函數(shù)向量，維函數(shù)向量， (X)是是m維函數(shù)向量；維函數(shù)向量； G是是m維常數(shù)向量；維常數(shù)向量； （1）（2） 對于線性多目標規(guī)劃線性多目標規(guī)劃問題，可以進一步用矩陣表示：CXZ max(min)bAX s.t. 式中：式中： X X 為為n n 維決策變量向量；維決策變量向量； C C 為為k kn n 矩陣，即目標函數(shù)系數(shù)矩陣；矩陣，即目標函數(shù)系數(shù)矩陣； A A 為為m mn n 矩陣，即約束方程系數(shù)矩陣；矩陣，即約束方程系數(shù)矩陣； b b 為為m m 維的向量，即約束向量。維的向量，即約束向量。

7、多目標規(guī)劃問題的求解不能只追求一個目標的最優(yōu)化（最大或最?。?，而不顧其它目標。對于上述多目標規(guī)劃問題，求解就意味著需要做出如下的復合選擇： 每一個目標函數(shù)取什么值，原問題可以得到最滿意的解決？ 每一個決策變量取什么值，原問題可以得到最滿意的解決 ？)(max(min)XFZ GX )(s.t. 在圖在圖1中，中，max(f1, f2) .就就方案和來說，的方案和來說，的 f2 目標值比大，但其目目標值比大，但其目標值標值 f1 比小，因此無比小，因此無法確定這兩個方案的優(yōu)法確定這兩個方案的優(yōu)與劣。與劣。 在各個方案之間，在各個方案之間，顯然：顯然：比好，比比好，比好好, , 比好比好, , 比

8、比好好。 非劣解非劣解可以用圖1說明。圖圖1 多目標規(guī)劃的劣解與非劣解多目標規(guī)劃的劣解與非劣解 而對于方案、而對于方案、之間則無法確、之間則無法確定優(yōu)劣，而且又沒有定優(yōu)劣，而且又沒有比它們更好的其他方比它們更好的其他方案，所以它們就被稱案，所以它們就被稱為多目標規(guī)劃問題的為多目標規(guī)劃問題的非劣解非劣解或或有效解有效解，其余方案都稱為其余方案都稱為劣解劣解。所有非劣解構(gòu)成的集所有非劣解構(gòu)成的集合稱為合稱為非劣解集非劣解集。 當目標函數(shù)處于當目標函數(shù)處于沖突狀態(tài)沖突狀態(tài)時，就不會存在使所有時，就不會存在使所有目標函數(shù)同時達到最大或最小值的最優(yōu)解，于是我們只目標函數(shù)同時達到最大或最小值的最優(yōu)解，于是

9、我們只能尋求非劣解（又稱能尋求非劣解（又稱非支配解或帕累托解非支配解或帕累托解）。）。 效用最優(yōu)化模型效用最優(yōu)化模型 罰款模型罰款模型 約束模型約束模型 目標達到法目標達到法 目標規(guī)劃模型目標規(guī)劃模型 為了求得多目標規(guī)劃問題的非劣解，常常需要將為了求得多目標規(guī)劃問題的非劣解，常常需要將多目標規(guī)劃問題轉(zhuǎn)化為單目標規(guī)劃問題多目標規(guī)劃問題轉(zhuǎn)化為單目標規(guī)劃問題去處理。實現(xiàn)去處理。實現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。這種轉(zhuǎn)化，有如下幾種建模方法。)(maxXZ GXts )(. 是與各目標函數(shù)相關(guān)的是與各目標函數(shù)相關(guān)的效用函數(shù)效用函數(shù)的的和函數(shù)和函數(shù)。 方法一方法一 效用最優(yōu)化模型效用最優(yōu)化模型（線性加權(quán)

10、法線性加權(quán)法） （1 1） （2 2） 思想思想：規(guī)劃問題的各個目標函數(shù)可以通過：規(guī)劃問題的各個目標函數(shù)可以通過一定一定的的方式方式進行進行求和求和運算。這種方法將一系列的運算。這種方法將一系列的目標函數(shù)目標函數(shù)與與效效用函數(shù)用函數(shù)建立相關(guān)關(guān)系，各目標之間通過效用函數(shù)協(xié)調(diào)，建立相關(guān)關(guān)系，各目標之間通過效用函數(shù)協(xié)調(diào)，使多目標規(guī)劃問題轉(zhuǎn)化為傳統(tǒng)的單目標規(guī)劃問題：使多目標規(guī)劃問題轉(zhuǎn)化為傳統(tǒng)的單目標規(guī)劃問題： 在在用效用函數(shù)作為規(guī)劃目標用效用函數(shù)作為規(guī)劃目標時，需要確定一組時，需要確定一組權(quán)值權(quán)值 i 來反映原問題中各目標函數(shù)在總體目標中的權(quán)重，即來反映原問題中各目標函數(shù)在總體目標中的權(quán)重，即： ki

11、ii1max ), 2 , 1(),(21migxxxini kii11 T maxGXts )(.式中， i 應(yīng)滿足：向量形式：思想思想: 規(guī)劃決策者對每一個目標函數(shù)都能提出所規(guī)劃決策者對每一個目標函數(shù)都能提出所期望的值期望的值（或稱（或稱滿意值滿意值）；）；通過比較實際值通過比較實際值 fi 與期望值與期望值 fi* 之間的偏差來選擇問題的之間的偏差來選擇問題的解，其數(shù)學表達式如下：解，其數(shù)學表達式如下：i 21)(min kiiiiffZ ), 2 , 1(),(21migxxxini 或?qū)懗删仃囆问剑?()(min FFAFFZTGX )(式中，式中， 是與第是與第i個目標函數(shù)相關(guān)的個

12、目標函數(shù)相關(guān)的權(quán)重權(quán)重； A是由是由 (i=1,2,k )組成的組成的mm對角矩陣。對角矩陣。i 理論依據(jù)理論依據(jù) ：若規(guī)劃問題的：若規(guī)劃問題的某一目標某一目標可以給出一個可供選可以給出一個可供選擇的范圍，則該目標就可以擇的范圍，則該目標就可以作為約束條件作為約束條件而被而被排除排除出目出目標組，進入約束條件組中。標組，進入約束條件組中。假如，除第一個目標外，其余目標都可以提出一個可供選假如，除第一個目標外，其余目標都可以提出一個可供選擇的范圍，則該多目標規(guī)劃問題就可以轉(zhuǎn)化為單目標規(guī)劃擇的范圍，則該多目標規(guī)劃問題就可以轉(zhuǎn)化為單目標規(guī)劃問題：問題： 方法三方法三 約束模型約束模型（極大極小法極大

13、極小法） ),(max(min)211nxxxfZ), 2 , 1(),(21migxxxini), 3 , 2(maxminkjfffjjj方法四方法四 目標達到法目標達到法 首先將多目標規(guī)劃模型化為如下首先將多目標規(guī)劃模型化為如下標準形式標準形式： )()()(min)(min21XfXfXfxFk00021(X)(X)(X)(X)m在求解之前，先設(shè)計與目標函數(shù)相應(yīng)的一組目標值理想在求解之前，先設(shè)計與目標函數(shù)相應(yīng)的一組目標值理想化的期望目標化的期望目標 fi* ( i=1,2,k ) ,每一個目標對應(yīng)的權(quán)重系數(shù)為每一個目標對應(yīng)的權(quán)重系數(shù)為 i* ( i=1,2,k ) ，再設(shè)再設(shè) 為一為一

14、松弛因子松弛因子。那么，多目標規(guī)劃問題就轉(zhuǎn)化為：那么，多目標規(guī)劃問題就轉(zhuǎn)化為： ,minX), 2 , 1(,)(*kifXfiii), 2 , 1(0)(miXi)()()(min)(min21XfXfXfxFk000)()()()(21XXXXml 由于流體力學中要求解非線性的方程由于流體力學中要求解非線性的方程,在求解過程中在求解過程中,控制變量的變控制變量的變化是很必要的化是很必要的,這就通過松弛因子來實現(xiàn)的這就通過松弛因子來實現(xiàn)的.它控制變量在每次迭代中的變它控制變量在每次迭代中的變化化.也就是說也就是說,變量的新值為原值加上變化量乘以松弛因子變量的新值為原值加上變化量乘以松弛因子.

15、l如如:A1=A0+B*DETAlA1 ：新值：新值 A0 ：原值：原值： B：松弛因子：松弛因子 DETA ：變化量：變化量l松弛因子可控制收斂的速度和改善收斂的狀況松弛因子可控制收斂的速度和改善收斂的狀況!l為為1,相當于不用松弛因子相當于不用松弛因子l大于大于1,為超松弛因子為超松弛因子,加快收斂速度加快收斂速度l小于小于1,欠松弛因子欠松弛因子,改善收斂的條件改善收斂的條件l一般來講一般來講,大家都是在收斂不好的時候，采用一個較小的欠松弛因大家都是在收斂不好的時候，采用一個較小的欠松弛因子。子。 Fluent里面用的是欠松弛，主要防止兩次迭代值相差太大引起發(fā)散。里面用的是欠松弛，主要防

16、止兩次迭代值相差太大引起發(fā)散。l松弛因子的值在松弛因子的值在01之間，越小表示兩次迭代值之間變化越小，之間，越小表示兩次迭代值之間變化越小，也就越穩(wěn)定，但收斂也就越慢。也就越穩(wěn)定，但收斂也就越慢。l l 方法五方法五 目標規(guī)劃模型（目標規(guī)劃法）目標規(guī)劃模型（目標規(guī)劃法） 需要預(yù)先確定各個目標的期望值需要預(yù)先確定各個目標的期望值 fi* ，同時給每一個，同時給每一個目標賦予一個目標賦予一個優(yōu)先因子優(yōu)先因子和和權(quán)系數(shù)權(quán)系數(shù)，假定有，假定有K個目標，個目標，L個個優(yōu)先級優(yōu)先級( LK)，目標規(guī)劃模型的數(shù)學形式為：，目標規(guī)劃模型的數(shù)學形式為： LlKkklkklklddpZ11)(min ),(),(

17、migxxxini2121 ),(Kifddfiiii21 LlKkklkklklddpZ11)(min ), 2 , 1(),(21migxxxini ), 2 , 1(Kifddfiiii 式中：式中： di+ 和和 di分別表示與分別表示與 fi 相應(yīng)的與相應(yīng)的與fi* 相比的目標超相比的目標超過值和不足值，即正、負偏差變量；過值和不足值，即正、負偏差變量； pl表示第表示第l個優(yōu)先級；個優(yōu)先級； lk+、 lk-表示在同一優(yōu)先級表示在同一優(yōu)先級 pl 中，不同目標的正、中，不同目標的正、負偏差變量的權(quán)系數(shù)。負偏差變量的權(quán)系數(shù)。 投資的收益和風險投資的收益和風險二、基本假設(shè)和符號規(guī)定二、

18、基本假設(shè)和符號規(guī)定二、基本假設(shè)和符號規(guī)定二、基本假設(shè)和符號規(guī)定三、模型的建立與分析三、模型的建立與分析1.總體風險用所投資的Si中最大的一個風險來衡量,即 max qixi|i=1，2,n三、模型的建立與分析三、模型的建立與分析4. 模型簡化模型簡化：四、模型四、模型1 1的求解的求解 由于由于a是任意給定的風險度，到底怎樣給定沒有一個準是任意給定的風險度，到底怎樣給定沒有一個準則，不同的投資者有不同的風險度。我們從則，不同的投資者有不同的風險度。我們從a=0開始，以開始，以步長步長a=0.001進行循環(huán)搜索，編制程序如下進行循環(huán)搜索，編制程序如下：a=0;while(1.1-a)1 c=-0

19、.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)To Matlab（xxgh5）a = 0.0030 x = 0.4949 0.1200 0.2000 0.0545 0.1154 Q = 0.126