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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、基本假設(shè)和符號(hào)規(guī)定二、基本假設(shè)和符號(hào)規(guī)定二、基本假設(shè)和符號(hào)規(guī)定三、模型的建立與分析三、模型的建立與分析1.總體風(fēng)險(xiǎn)用所投資的Si中最大的一個(gè)風(fēng)險(xiǎn)來(lái)衡量,即 max qixi|i=1，2,n三、模型的建立與分析三、模型的建立與分析4. 模型簡(jiǎn)化模型簡(jiǎn)化：四、模型四、模型1 1的求解的求解 由于由于a是任意給定的風(fēng)險(xiǎn)度，到底怎樣給定沒(méi)有一個(gè)準(zhǔn)是任意給定的風(fēng)險(xiǎn)度，到底怎樣給定沒(méi)有一個(gè)準(zhǔn)則，不同的投資者有不同的風(fēng)險(xiǎn)度。我們從則，不同的投資者有不同的風(fēng)險(xiǎn)度。我們從a=0開(kāi)始，以開(kāi)始，以步長(zhǎng)步長(zhǎng)a=0.001進(jìn)行循環(huán)搜索，編制程序如下進(jì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