多目標(biāo)優(yōu)化方法PPT課件

1、第二部分第二部分 多目標(biāo)優(yōu)化方法多目標(biāo)優(yōu)化方法 Multi-Objective Optimization 第一節(jié)第一節(jié) 概述概述 第三節(jié)第三節(jié) 多目標(biāo)優(yōu)化的第一類方法多目標(biāo)優(yōu)化的第一類方法 第二節(jié)第二節(jié) 多目標(biāo)優(yōu)化設(shè)計(jì)理論多目標(biāo)優(yōu)化設(shè)計(jì)理論 第四節(jié)第四節(jié) 多目標(biāo)優(yōu)化的第二類方法多目標(biāo)優(yōu)化的第二類方法 第五節(jié)第五節(jié) 多目標(biāo)優(yōu)化的第三類方法多目標(biāo)優(yōu)化的第三類方法國際上通常認(rèn)為多目標(biāo)最優(yōu)化問題最早是在國際上通常認(rèn)為多目標(biāo)最優(yōu)化問題最早是在18861886年由法國經(jīng)年由法國經(jīng)濟(jì)學(xué)家濟(jì)學(xué)家ParetoPareto從政治經(jīng)濟(jì)學(xué)的角度提出的。多目標(biāo)規(guī)劃的真從政治經(jīng)濟(jì)學(xué)的角度提出的。多目標(biāo)規(guī)劃的真正發(fā)達(dá)時(shí)期，

2、并正式作為一個(gè)數(shù)學(xué)分支進(jìn)行系統(tǒng)的研究，是正發(fā)達(dá)時(shí)期，并正式作為一個(gè)數(shù)學(xué)分支進(jìn)行系統(tǒng)的研究，是上世紀(jì)七十年代以后的事。上世紀(jì)七十年代以后的事?，F(xiàn)在，對(duì)多目標(biāo)規(guī)劃方面的研究集中在以下幾個(gè)方面現(xiàn)在，對(duì)多目標(biāo)規(guī)劃方面的研究集中在以下幾個(gè)方面: : 一、關(guān)于解的概念及其性質(zhì)的研究，一、關(guān)于解的概念及其性質(zhì)的研究， 二、關(guān)于多目標(biāo)規(guī)劃的解法研究，二、關(guān)于多目標(biāo)規(guī)劃的解法研究， 三、對(duì)偶問題的研究，三、對(duì)偶問題的研究， 四、不可微多目標(biāo)規(guī)劃的研究，四、不可微多目標(biāo)規(guī)劃的研究， 五、多目標(biāo)規(guī)劃的應(yīng)用研究。五、多目標(biāo)規(guī)劃的應(yīng)用研究。到現(xiàn)在為止，多目標(biāo)優(yōu)化不僅在理論上取得許多重要成果，到現(xiàn)在為止，多目標(biāo)優(yōu)化不僅在

3、理論上取得許多重要成果，而且在應(yīng)用上其范圍也越來越廣泛，多目標(biāo)決策作為一個(gè)工而且在應(yīng)用上其范圍也越來越廣泛，多目標(biāo)決策作為一個(gè)工具在解決工程技術(shù)、經(jīng)濟(jì)、管理、軍事和系統(tǒng)工程等眾多方具在解決工程技術(shù)、經(jīng)濟(jì)、管理、軍事和系統(tǒng)工程等眾多方面的問題也越來越顯示出它強(qiáng)大的生命力。面的問題也越來越顯示出它強(qiáng)大的生命力。 第一節(jié)第一節(jié) 概述概述1. 1. 多目標(biāo)優(yōu)化設(shè)計(jì)示例多目標(biāo)優(yōu)化設(shè)計(jì)示例11221 max()45 max()f XxxfXx目標(biāo)函數(shù)示例示例1 1：某工廠生產(chǎn)兩種產(chǎn)品：某工廠生產(chǎn)兩種產(chǎn)品A A和和B,B,每件產(chǎn)品每件產(chǎn)品A A需制造工時(shí)需制造工時(shí)和裝配工時(shí)分別為和裝配工時(shí)分別為1 1時(shí)和時(shí)

4、和1.251.25時(shí)，每件產(chǎn)品時(shí)，每件產(chǎn)品B B需制造工時(shí)和需制造工時(shí)和裝配工時(shí)分別為裝配工時(shí)分別為1 1時(shí)和時(shí)和0.750.75時(shí)，每月制造車間和裝配車間時(shí)，每月制造車間和裝配車間能夠提供的最多工時(shí)為能夠提供的最多工時(shí)為200200時(shí)，另外，每月市場對(duì)產(chǎn)品時(shí)，另外，每月市場對(duì)產(chǎn)品A A需需求量很大，而對(duì)產(chǎn)品求量很大，而對(duì)產(chǎn)品B B的最大需求量為的最大需求量為150150件，產(chǎn)品件，產(chǎn)品A A和產(chǎn)和產(chǎn)品品B B的售價(jià)分別為的售價(jià)分別為4 4元和元和5 5元，問如何安排每月的生產(chǎn)，最元，問如何安排每月的生產(chǎn)，最大限度的滿足市場需求，并產(chǎn)值最大？大限度的滿足市場需求，并產(chǎn)值最大？12ABxx設(shè)計(jì)變

5、量：產(chǎn)品 的件數(shù) ，產(chǎn)品 的件數(shù)0,1 . .*61 max* min21222122121xxxxt sxxxx示例示例2. 2. 用直徑為用直徑為1(1(單位長單位長) )的圓木制成截面為矩形的圓木制成截面為矩形的梁的梁, ,為使重量最輕為使重量最輕, ,而強(qiáng)度最大而強(qiáng)度最大, ,問截面的高與寬問截面的高與寬應(yīng)取何尺寸應(yīng)取何尺寸? ?解解: : 設(shè)矩形截面的高與寬分別設(shè)矩形截面的高與寬分別 為和為和 , , 這時(shí)這時(shí)梁的面積為梁的面積為 , ,它決定重量它決定重量, ,而梁的強(qiáng)度取而梁的強(qiáng)度取決于截面形決于截面形 。 1x2x21*xx221*61xx因此因此, ,容易列出容易列出 梁的數(shù)

6、學(xué)模型梁的數(shù)學(xué)模型: :示例示例3 3 物資調(diào)運(yùn)問題物資調(diào)運(yùn)問題: : 某種物資寸放三個(gè)倉庫某種物資寸放三個(gè)倉庫 里里, ,存放量分別為存放量分別為 ( (單位單位:t);:t);現(xiàn)要將這些物資運(yùn)往四個(gè)銷售現(xiàn)要將這些物資運(yùn)往四個(gè)銷售點(diǎn)點(diǎn) 。其需要量分別為。其需要量分別為 且且 ，已知，已知 到到 的距離和單位的距離和單位運(yùn)價(jià)分別為運(yùn)價(jià)分別為 (km)(km)和和 ( (元元),),現(xiàn)要決定如何現(xiàn)要決定如何調(diào)運(yùn)多少調(diào)運(yùn)多少, ,才能使總的噸才能使總的噸, ,公里數(shù)和總運(yùn)費(fèi)都盡量少公里數(shù)和總運(yùn)費(fèi)都盡量少? ?123,A A A123,a a a1234,B B B B1234,b b b b34i

7、jijabiAjBijdijc解: 設(shè)變量 表示由 運(yùn)往 的貨物數(shù),于是總噸公里數(shù)為 ,總運(yùn)費(fèi)為 ,問題優(yōu)化設(shè)計(jì)模型為11ijijijxd4 , 3 , 2 , 1; 3 , 2 , 1,jixijiAjB4 , 3 , 2 , 1; 3 , 2 , 1, 04 , 3 , 2 , 1,3 , 2 , 1, . . * min* min314131413141jixjbxiaxtsxcxdijijijiiijijijijijijij11ijijijxc示例示例4 4：如圖所示，設(shè)計(jì)一苦空心階梯懸臂梁，根據(jù)結(jié)構(gòu)要如圖所示，設(shè)計(jì)一苦空心階梯懸臂梁，根據(jù)結(jié)構(gòu)要求，已確定梁的總長為求，已確定梁的總長為

8、10001000mmmm，第一段外徑為，第一段外徑為8080mmmm，第二段外經(jīng)為第二段外經(jīng)為100100mmmm，梁的端部受有集中力，梁的端部受有集中力F F12000N12000N，梁的內(nèi)徑不得小于梁的內(nèi)徑不得小于4040mmmm，梁的許用彎曲應(yīng)力為梁的許用彎曲應(yīng)力為180MPa180MPa，確定梁的內(nèi)徑和各段長度，使梁的體積和靜撓度最小。確定梁的內(nèi)徑和各段長度，使梁的體積和靜撓度最小。1 12 2D1=100D1=100D2=80D2=80L=1000L=1000 x1x2F F 多目標(biāo)優(yōu)化設(shè)計(jì)模型多目標(biāo)優(yōu)化設(shè)計(jì)模型6117422232419.78 10 . . ()18004.096

9、10()75.20()400()0 xstg XxgXxgXxgXx12xx設(shè)計(jì)變量：第一段梁的長度 ，梁的內(nèi)徑22221122112 ()()()()4f Xx DxLxDx33214444442212126411 ()()3LfXxEDxDxDx12min()(),) (TF Xf XfX 多目標(biāo)最優(yōu)化問題的一般形式為多目標(biāo)最優(yōu)化問題的一般形式為: : S.t. 或者記作:min D= 12min( (),(),( )mf xf xfx( )0,1,2.,( )0,1,2,ijg xiph xjq( )f x |( )0, ( )0nxEg xh x xD 其中: =( ) ( )f x

10、1( ),( )mf xfx1( )( )( )pg xg xgx1( )( ( )( )qh xh xh x 2. 2. 多目標(biāo)優(yōu)化設(shè)計(jì)模型多目標(biāo)優(yōu)化設(shè)計(jì)模型iGxFy為滿足所有目標(biāo)的參數(shù) 組成的參數(shù)空間為根據(jù) 按照目標(biāo)函數(shù) 映射的組成的目標(biāo)函數(shù)空間注意，這里以及注意，這里以及之后的所有講述之后的所有講述同時(shí)同時(shí)適合于線性適合于線性和非線性的多目和非線性的多目標(biāo)優(yōu)化標(biāo)優(yōu)化多目標(biāo)優(yōu)化設(shè)計(jì)幾何描述多目標(biāo)優(yōu)化設(shè)計(jì)幾何描述在單目標(biāo)優(yōu)化問題中，任何兩個(gè)解都可以比較出其優(yōu)劣，這是在單目標(biāo)優(yōu)化問題中，任何兩個(gè)解都可以比較出其優(yōu)劣，這是因?yàn)閱文繕?biāo)優(yōu)化問題是完全有序的；而在多目標(biāo)優(yōu)化設(shè)計(jì)中，因?yàn)閱文繕?biāo)優(yōu)化問題

11、是完全有序的；而在多目標(biāo)優(yōu)化設(shè)計(jì)中，任何兩個(gè)解不一定都可以比較出其優(yōu)劣，這是因?yàn)槎嗄繕?biāo)優(yōu)化任何兩個(gè)解不一定都可以比較出其優(yōu)劣，這是因?yàn)槎嗄繕?biāo)優(yōu)化問題是半有序的。問題是半有序的。3. 3. 多目標(biāo)優(yōu)化問題解的特點(diǎn)多目標(biāo)優(yōu)化問題解的特點(diǎn)T(1)(1)(1(1)(1)()(1)12T(2)(2)(2)(2)12(1)(2)(1)(21)( )2()(),(),() ()(),(),(), ()() (1,2,)mmllF Xf XfXfXF Xf Xff XfXfXXXlmXXXXX設(shè)為多目標(biāo)優(yōu)化問題的兩個(gè)可行解，其對(duì)應(yīng)若對(duì)于每一個(gè)分量，都則顯然，優(yōu)的目標(biāo)函數(shù)于，記為有為(1)(2)(1)(2)(2

12、)(1)(2)(1)(2)()() ()() ()()() jjllF XF XfXfXF Xf Xf XXX大多數(shù)情況下，的某幾個(gè)分量小于的對(duì)應(yīng)分量，但另外幾個(gè)分量大于的對(duì)應(yīng)分量 則顯然，與無法比較優(yōu)劣。1f2f213第一類：轉(zhuǎn)化法。這類多目標(biāo)最優(yōu)化方法的基本思想是將多目標(biāo)第一類：轉(zhuǎn)化法。這類多目標(biāo)最優(yōu)化方法的基本思想是將多目標(biāo)問題轉(zhuǎn)化為一個(gè)或一系列的單目標(biāo)優(yōu)化問題，通過求解一個(gè)或一問題轉(zhuǎn)化為一個(gè)或一系列的單目標(biāo)優(yōu)化問題，通過求解一個(gè)或一系列單目標(biāo)優(yōu)化問題來完成多目標(biāo)優(yōu)化問題的求解。系列單目標(biāo)優(yōu)化問題來完成多目標(biāo)優(yōu)化問題的求解。4. 4. 多目標(biāo)優(yōu)化方法分類多目標(biāo)優(yōu)化方法分類第二類：非劣解集

13、法。這類多目標(biāo)最優(yōu)化方法的基本思想是求第二類：非劣解集法。這類多目標(biāo)最優(yōu)化方法的基本思想是求得多目標(biāo)問題的非劣解集，然后在非劣解集中進(jìn)行協(xié)調(diào)和選擇，得多目標(biāo)問題的非劣解集，然后在非劣解集中進(jìn)行協(xié)調(diào)和選擇，確定出優(yōu)惠解。確定出優(yōu)惠解。第三類：交互協(xié)調(diào)法。這類多目標(biāo)最優(yōu)化方法的基本思想是通第三類：交互協(xié)調(diào)法。這類多目標(biāo)最優(yōu)化方法的基本思想是通過在分析者與抉擇者間的不斷交互，逐漸搞清抉擇者的選擇意過在分析者與抉擇者間的不斷交互，逐漸搞清抉擇者的選擇意圖，獲得多目標(biāo)問題的優(yōu)惠解。圖，獲得多目標(biāo)問題的優(yōu)惠解。 第二節(jié)第二節(jié) 多目標(biāo)優(yōu)化設(shè)計(jì)理論多目標(biāo)優(yōu)化設(shè)計(jì)理論 1. 1. 多目標(biāo)優(yōu)化設(shè)計(jì)模型多目標(biāo)優(yōu)化設(shè)

14、計(jì)模型 . . ()0 1,2,()0 1,2,uvstgXuph Xvq 簡記為簡記為 VOP多目標(biāo)優(yōu)化問題多目標(biāo)優(yōu)化問題( (Multi-Objective Optimization Problem) )又稱為向量優(yōu)化問題又稱為向量優(yōu)化問題( (Vector Optimization Problem) ) 。12min()(),(),()TmF Xf XfXfX() V-mi nnF XXDR 2. 2. 決策空間與目標(biāo)空間決策空間與目標(biāo)空間() 0 1,2,() 0 1,2, =uvngXupXhXvqDXR 以設(shè)計(jì)變量為坐標(biāo)的實(shí)空間以設(shè)計(jì)變量為坐標(biāo)的實(shí)空間Rn稱為決策空間。稱為決策空間

15、。 以目標(biāo)函數(shù)為坐標(biāo)的實(shí)空間以目標(biāo)函數(shù)為坐標(biāo)的實(shí)空間Rm稱為目標(biāo)空間。稱為目標(biāo)空間。決策空間可行域：決策空間可行域：目標(biāo)空間可行域目標(biāo)空間可行域12=(),(), ,() ,mTFmXDFRFfXfXfXXD 示例示例1 1112212324152 . . ()2000()200 1.250.750()1500()0()0stg XxxgXxxgXxgXxgXx決策空間決策空間可行域可行域目標(biāo)空間目標(biāo)空間可行域可行域T121max F()45 Xxxx， 示例示例2 26117422232419.78 10 . . ()18004.096 10()75.20()400()0 xstg XxgX

16、xgXxgXx22221122112 ()()()()4f Xx DxLxDx決策空間決策空間可行域可行域目標(biāo)空間目標(biāo)空間可行域可行域12min()(),()TF Xf XfX33214444442212126411()()3LfXxEDxDxDx3. 3. 解的定義解的定義（1 1） 理想解理想解(ideal solution)000012,TmFfff在目標(biāo)空間內(nèi)，以單目標(biāo)最小值為分量而形成的點(diǎn)，在目標(biāo)空間內(nèi)，以單目標(biāo)最小值為分量而形成的點(diǎn)，稱為多目標(biāo)問題的理想解稱為多目標(biāo)問題的理想解。0min()njjffXXDR其中 在多目標(biāo)優(yōu)化問題中，在多目標(biāo)優(yōu)化問題中，由于各個(gè)目標(biāo)間往往是由于各個(gè)

17、目標(biāo)間往往是矛盾的，所以一般不存矛盾的，所以一般不存在使各目標(biāo)皆達(dá)到各自在使各目標(biāo)皆達(dá)到各自最優(yōu)值的理想解最優(yōu)值的理想解。fxX(0)f1(0)f2(0)f1f2（2 2） 非劣解（非劣解（Noninferior Solution）或）或 Pareto 解解()()pF XF X對(duì)于可行點(diǎn)對(duì)于可行點(diǎn)XP D，若不若不存在另一個(gè)可行點(diǎn)存在另一個(gè)可行點(diǎn)X D，使使()() 1,2,()()ppjjllfXfXjmfXfX 但至少有一個(gè) 成立，則稱成立，則稱Xp為多目標(biāo)問題的非劣解。為多目標(biāo)問題的非劣解。向量不等式的含義為向量不等式的含義為決策空間決策空間非劣解集非劣解集目標(biāo)空間目標(biāo)空間非劣解集非劣

18、解集7.1 模型舉例0,1 . .*61 max* min21222122121xxxxt sxxxx例7.1. 用直徑為1(單位長)的圓木制成截面為矩形的梁,為使重量最輕,而強(qiáng)度最大,問截面的高與寬應(yīng)取何尺寸?解: 設(shè)矩形截面的高與寬分別 為和 , 這時(shí)梁的面積為 ,它決定重量,而梁的重量取決于截面矩形 。 1x2x21*xx221*61xx因此,容易列出 梁的數(shù)學(xué)模型:例7.2 物資調(diào)運(yùn)問題: 某種物資寸放三個(gè)倉庫 里,存放量分別為 (單位:t);現(xiàn)要將這些物資運(yùn)往四個(gè)銷售點(diǎn) .其需要量分別為 且 ，已知 到 的距離和單位運(yùn)價(jià)分別為 (km)和 (元),現(xiàn)要決定如何調(diào)運(yùn)多少,才能使總的噸,

19、公里數(shù)和總運(yùn)費(fèi)都盡量少?123,A A A123,a a a1234,B B B B1234,b b b b34ijijabiAjBijdijc解: 設(shè)變量 表示由 運(yùn)往 的貨物數(shù),于是總噸公里數(shù)為 ,總運(yùn)費(fèi)為 ,問題優(yōu)化為求解11ijijijxd4 , 3 , 2 , 1; 3 , 2 , 1,jixijiAjB4 , 3 , 2 , 1; 3 , 2 , 1, 04 , 3 , 2 , 1,3 , 2 , 1, . . * min* min314131413141jixjbxiaxtsxcxdijijijiiijijijijijijij11ijijijxc由于求最大都可以轉(zhuǎn)化為求最小由于求

20、最大都可以轉(zhuǎn)化為求最小,所以多目標(biāo)最優(yōu)化問所以多目標(biāo)最優(yōu)化問題的一般形式為題的一般形式為: S.t. 或者記作:min D= 12min( (),(),( )pf xf xfxljxhmixgji, 2 , 1, 0)(,. 2 , 1, 0)( )f x |( )0, ( )0pxEg xh x xD 其中: =( ) ( )f x 1( ),( )pf xfx1( )( )( )mg xg xgx1( )( ( )( )mh xh xhx 當(dāng)P=1時(shí),(VP)就是非線性規(guī)劃, 稱為單目標(biāo)規(guī)劃。對(duì)于單目標(biāo)問題Min , 總可比較 與 的大小.對(duì)于多目標(biāo)規(guī)劃(VP),對(duì)于 ， 與 都是P 維向

21、量,如何比較兩個(gè)向量的大小?( )f x 12,x xD1()f x2()f x12,x xD1()f x2()f x可以看到：可以看到：多目標(biāo)優(yōu)化的非劣解集Noninferior solution for the model*xxx(xx)x若，且對(duì)于 不存在，使得：與能同時(shí)成立，那么則定義 為多目標(biāo)優(yōu)化問題的非劣解。例如：A,B點(diǎn)屬于非劣解，因?yàn)椴粷M足定義條件（3 3） 滿意解（最佳協(xié)調(diào)解或優(yōu)惠滿意解（最佳協(xié)調(diào)解或優(yōu)惠解）解）11(),(),()mUU f Xf XfX效用函數(shù)值的大小反映決策者對(duì)多目標(biāo)值的喜愛程度，效用函數(shù)值的大小反映決策者對(duì)多目標(biāo)值的喜愛程度，一般來說，決策者希望效用函

22、數(shù)的值越大越好。一般來說，決策者希望效用函數(shù)的值越大越好。效用函數(shù)：效用函數(shù)：決策者對(duì)多目標(biāo)函數(shù)優(yōu)化解進(jìn)行評(píng)價(jià)的函數(shù)，記為決策者對(duì)多目標(biāo)函數(shù)優(yōu)化解進(jìn)行評(píng)價(jià)的函數(shù)，記為使效用函數(shù)取最大值的非劣解稱為最佳協(xié)調(diào)解。使效用函數(shù)取最大值的非劣解稱為最佳協(xié)調(diào)解。對(duì)于效用函數(shù)未知對(duì)于效用函數(shù)未知的情況，無法直接的情況，無法直接求得最佳協(xié)調(diào)解。求得最佳協(xié)調(diào)解。我們把多目標(biāo)優(yōu)化我們把多目標(biāo)優(yōu)化過程滿意結(jié)束的解過程滿意結(jié)束的解稱為優(yōu)惠解。稱為優(yōu)惠解。滿意解滿意解4 4 多目標(biāo)優(yōu)化問題的多目標(biāo)優(yōu)化問題的K KT T條件條件對(duì)于多目標(biāo)優(yōu)化問題對(duì)于多目標(biāo)優(yōu)化問題 . . ()0 1,2,()0 1,2,uvstgXup

23、h Xvq VOP(),1,2,;(),1,2, ;(),1,2, ;juvfXjm gXup h Xvq設(shè) *VOPjuvXXw皆為連續(xù)可微函數(shù)，為可行點(diǎn)，則為（）的非劣解的必要條件為：存在、與使*1*1()()()02()01,2,301,2,401,2,pqmjjuuvvjuvuuujwfXgXh XgX up up w jm （ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）12min()(),(),()TmF Xf XfXfX7.4 求解多目標(biāo)規(guī)劃的評(píng)價(jià)函數(shù)法求解多目標(biāo)規(guī)劃的評(píng)價(jià)函數(shù)法 盡管多目標(biāo)優(yōu)化問題有各種意義下的最優(yōu)解.但在應(yīng)用中,需要的還是有效解和弱有效解.本節(jié)介紹求有效解和弱

24、有效解最基本的方法-評(píng)價(jià)函數(shù)法. 評(píng)價(jià)函數(shù)法的基本思想是:借助于幾何或應(yīng)用中的直觀效果.構(gòu)造所謂的評(píng)價(jià)函數(shù).從而將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題.然后利用單目標(biāo)優(yōu)化問題的求解方法求出最優(yōu)解.并把這種最優(yōu)解當(dāng)作多目標(biāo)優(yōu)化問題的最優(yōu)解.這里關(guān)鍵的問題是轉(zhuǎn)化后的單目標(biāo)優(yōu)化問題的最優(yōu)解必須是多目標(biāo)問題的有效解和弱有效解.否則是不能接受的. 所謂評(píng)價(jià)函數(shù),是利用(VP)的目標(biāo)函數(shù) ,構(gòu)造一個(gè)復(fù)合函數(shù) .然后在(VP)的約束集D上極小化 , 的構(gòu)造必須保證在一定條件下, min 的最優(yōu)解是(VP)的有效解或弱有效解. 下面先討論在什么條件下, min 的最優(yōu)解才能是(VP) min 的有效解or弱有效

25、解. ( )f x( ( )f x( ( )f x( ( )f x( ( )f x()f x定義6. 設(shè) : 1.若 ,總有 ,則稱 為 的嚴(yán)格單增函數(shù). 2 若 時(shí),總有 ,則稱 為 的單增函數(shù).,:pnPEEfDEE12ZZ12()()ZZ( )ZZ12ZZ12()()ZZ( )ZZ定理1 . 設(shè)：: ,又設(shè) ，是問題min 的極小點(diǎn),那么: 若 為Z的嚴(yán)格單增函數(shù),則 是min 有效解. 若 為Z的單增函數(shù),則 是min 的弱有效解.pEE:nPfDEE*x( ( )f x*x*x( )f x( )f x重要定理幾種常用的構(gòu)造評(píng)價(jià)函數(shù)的方法一. 理想點(diǎn)法: 在(VP)中,先求解P個(gè)單目標(biāo)

26、問題 j=1，2，p xD 設(shè)其最優(yōu)值為 ,我們稱 為值域中的一個(gè)理想點(diǎn) 。min( )jfx*jf*12(,)Tpffff 因?yàn)橐话愫茈y達(dá)到它,這樣,就期望在某種等量下,尋求距最近的f作為近似值,一種最直接的想法是構(gòu)造評(píng)價(jià)函數(shù) = （7.2） ( )Z2*1()piiiZf 然后極小化即求解：并將它的最優(yōu)解 作為(VP)在這種意義下的“最優(yōu)解”,由于 ,因此由7.2構(gòu)造的 是嚴(yán)格單增的,從而 是(VP)的有效解.* 21min( )( )piiif xf xf*x*( )iiiZf xf( )Z*x二. 線性加權(quán)和法. 在具有多個(gè)指標(biāo)的問題中,人們總希望對(duì)那些相對(duì)重要的指標(biāo)給予較大的權(quán)系數(shù),

27、基于這種現(xiàn)實(shí),自然如下的構(gòu)造評(píng)價(jià)函數(shù),令 12,1(,) |01pTpiii 且12,1(,) |01pTpiii 且稱之為權(quán)向量集,令 再求解而將它的最優(yōu)解, 作為(VP)在該意義下的最優(yōu)解.1( )*,pTiiiP ZZZormin ( ( )*( )Tf xf x*x三. 極大極小法 在決策時(shí)，采取保守策略是穩(wěn)妥的。即在最壞的情況下，尋求最好的結(jié)果。按照這種想法，可以構(gòu)造如下評(píng)價(jià)函數(shù) 然后求解 并將它的最優(yōu)解 作為（VP）在這種意義下的最優(yōu)解。ipizz1max)()(maxmin)(min1xfxfipiDxDxx 1. 1. 主目標(biāo)法主目標(biāo)法 轉(zhuǎn)化為轉(zhuǎn)化為 第三節(jié)第三節(jié) 多目標(biāo)優(yōu)化的

28、第一類方法多目標(biāo)優(yōu)化的第一類方法主目標(biāo)法就是從多目標(biāo)中依據(jù)重要程度選擇一個(gè)目標(biāo)主目標(biāo)法就是從多目標(biāo)中依據(jù)重要程度選擇一個(gè)目標(biāo)作為主目標(biāo)，而將其它目標(biāo)轉(zhuǎn)化為約束，即將多目標(biāo)作為主目標(biāo)，而將其它目標(biāo)轉(zhuǎn)化為約束，即將多目標(biāo)優(yōu)化問題優(yōu)化問題12min()(),(),() s.t. ()01,2, ()01,2,TmuvF Xf XfXfXgXuph Xvq0min () s.t. ()01,2, ()01,2, ()1,2,kuvllfXgXuph Xvqf Xflm lk主目標(biāo)法中約束目標(biāo)的約束值選取主目標(biāo)法中約束目標(biāo)的約束值選取0* 1,2,lllfflm lk* () min() 1,2,Xll

29、llXDff Xff Xlm lk式中為目標(biāo)函數(shù)的單目標(biāo)極小值， 即 * () 0.010.02) 1, ,2,llllf Xflm lk式中為對(duì)目標(biāo)函數(shù)的單目標(biāo)極小值的放大值，一般可取 （ 2. 2. 線性加權(quán)法線性加權(quán)法 轉(zhuǎn)化為轉(zhuǎn)化為線性加權(quán)法就是將多目標(biāo)的加權(quán)和作為單目標(biāo)，即將線性加權(quán)法就是將多目標(biāo)的加權(quán)和作為單目標(biāo)，即將多目標(biāo)優(yōu)化問題多目標(biāo)優(yōu)化問題12min()(),(),() s.t. ()01,2, ()01,2,TmuvF Xf XfXfXgXuph Xvqmin()() s.t. ()01,2, ()01,2, mllluvF Xw f XgXuph Xvq(2(2）對(duì)權(quán)系數(shù)的

30、要求）對(duì)權(quán)系數(shù)的要求 (3) (3) 權(quán)系數(shù)的確定權(quán)系數(shù)的確定 0 1,2,lwlm非負(fù)要求1 1mllw歸一化要求 老手法老手法*1 min()lllXDlwff Xf線性加權(quán)法的有關(guān)說明：線性加權(quán)法的有關(guān)說明：（1) 1) 線性加權(quán)之前，各目標(biāo)應(yīng)進(jìn)行無量綱化處理。線性加權(quán)之前，各目標(biāo)應(yīng)進(jìn)行無量綱化處理。 3. 3. 極小極大法極小極大法 轉(zhuǎn)化為轉(zhuǎn)化為極小極大法就是求取多目標(biāo)函數(shù)中的最大值，然后使極小極大法就是求取多目標(biāo)函數(shù)中的最大值，然后使最大值函數(shù)在可行域內(nèi)極小化，即將多目標(biāo)優(yōu)化問題最大值函數(shù)在可行域內(nèi)極小化，即將多目標(biāo)優(yōu)化問題12min()(),(),() s.t. ()01,2, (

31、)01 ,2,TmuvF Xf XfXfXgXuph Xvq1min max () s.t. ()01,2, ()01,2, ll muvf XgXuph Xvq (2) (2)極小極大法也可以引入一個(gè)變量極小極大法也可以引入一個(gè)變量 和和m個(gè)約束，即個(gè)約束，即極小極大法的有關(guān)說明：極小極大法的有關(guān)說明：（1) 1) 考慮到各目標(biāo)的重要程度差別，可以對(duì)各目標(biāo)考慮到各目標(biāo)的重要程度差別，可以對(duì)各目標(biāo)乘以權(quán)系數(shù)，然后再求最大值函數(shù)，即乘以權(quán)系數(shù)，然后再求最大值函數(shù)，即1min max () s.t. ()01,2, ()01,2, lll muvw f XgXuph Xvq min s.t. ()

32、01,2, ()01,2, () 1,2,uvllgXuph Xvqw f Xjm 4. 4. 理想點(diǎn)法理想點(diǎn)法 轉(zhuǎn)化為轉(zhuǎn)化為理想點(diǎn)法就是將距理想點(diǎn)最近的點(diǎn)作為多目標(biāo)問題的理想點(diǎn)法就是將距理想點(diǎn)最近的點(diǎn)作為多目標(biāo)問題的優(yōu)惠解，即將多目標(biāo)優(yōu)化問題優(yōu)惠解，即將多目標(biāo)優(yōu)化問題12min()(),(),() s.t. ()01,2, ()01 ,2,TmuvF Xf XfXfXgXuph Xvq200()min() s.t. ()01,2, ()01,2,mlllluvf XfU XfgXuph Xvq00012mfff其中，為多目標(biāo)問題在目標(biāo)空間中的理想點(diǎn)。理想點(diǎn)法的有關(guān)說明：理想點(diǎn)法的有關(guān)說明：考

33、慮到各目標(biāo)的重要程度差別，可以對(duì)各目標(biāo)乘以權(quán)考慮到各目標(biāo)的重要程度差別，可以對(duì)各目標(biāo)乘以權(quán)系數(shù)，即系數(shù)，即權(quán)系數(shù)的選取可以參閱線性加權(quán)法。權(quán)系數(shù)的選取可以參閱線性加權(quán)法。200()min() s.t. ()01,2, ()01,2,mllllluvf XfU XwfgXuph Xvq 5. 5. 功效系數(shù)法功效系數(shù)法在多目標(biāo)優(yōu)化問題，各目標(biāo)的要求不全相同，有的要在多目標(biāo)優(yōu)化問題，各目標(biāo)的要求不全相同，有的要求極小化，有的要求極大化，有的要求有一個(gè)合適的求極小化，有的要求極大化，有的要求有一個(gè)合適的數(shù)值。為了反映這些不同的要求，故引入如下的功效數(shù)值。為了反映這些不同的要求，故引入如下的功效函數(shù)：

34、函數(shù)： 0110jjjjjccfcf的取值為 ， 表示目標(biāo) 的值最滿意； 表示目標(biāo) 的值最不滿意。() 1,2,jjcF fjm1 2 maxUjmmcc cc取所有 的幾何平均值為多目標(biāo)問題的評(píng)價(jià)函數(shù)，即功效系數(shù)的確定：功效系數(shù)的確定：1.1.直線法直線法 2.2.折線法折線法 3.3.指數(shù)法指數(shù)法 6. 6. 分層序列法分層序列法將多目標(biāo)優(yōu)化問題的各目標(biāo)分清主次，按其重要程度將多目標(biāo)優(yōu)化問題的各目標(biāo)分清主次，按其重要程度逐一排序，然后依次對(duì)各目標(biāo)函數(shù)求最優(yōu)解，但應(yīng)注逐一排序，然后依次對(duì)各目標(biāo)函數(shù)求最優(yōu)解，但應(yīng)注意后一目標(biāo)應(yīng)在前一目標(biāo)的最優(yōu)解域內(nèi)進(jìn)行尋優(yōu)。意后一目標(biāo)應(yīng)在前一目標(biāo)的最優(yōu)解域內(nèi)進(jìn)

35、行尋優(yōu)。() 1,2 ,jfXjm設(shè)目標(biāo)函數(shù)的重要程度排序?yàn)?11 min() f XfXD首先對(duì)第一個(gè)目標(biāo)函數(shù)求最優(yōu)值*22*11 min() ()fXfXDX f Xf在第一個(gè)目標(biāo)函數(shù)的最優(yōu)解域中，求第二個(gè)目標(biāo)函數(shù)的最優(yōu)解，即照此繼續(xù)下去，最后求得第照此繼續(xù)下去，最后求得第mm個(gè)目標(biāo)函數(shù)得最優(yōu)解，個(gè)目標(biāo)函數(shù)得最優(yōu)解，真?zhèn)€解即為多目標(biāo)優(yōu)化問題的最終解。真?zhèn)€解即為多目標(biāo)優(yōu)化問題的最終解。在分層序列法中，當(dāng)前面有某個(gè)目標(biāo)函數(shù)的最優(yōu)解唯一在分層序列法中，當(dāng)前面有某個(gè)目標(biāo)函數(shù)的最優(yōu)解唯一時(shí)，該方法就發(fā)生中斷現(xiàn)象，因此需要引入目標(biāo)容差。時(shí)，該方法就發(fā)生中斷現(xiàn)象，因此需要引入目標(biāo)容差。*11 min()

36、 f XfXD首先對(duì)第一個(gè)目標(biāo)函數(shù)求最優(yōu)值*22*111 min() ()fXfXDX f Xf在第一個(gè)目標(biāo)函數(shù)的最優(yōu)解容差域中，求第二個(gè)目標(biāo)函數(shù)的最優(yōu)解，即 7. 7. 協(xié)調(diào)曲線法協(xié)調(diào)曲線法協(xié)調(diào)曲線法主要用于求解兩個(gè)目標(biāo)函數(shù)的多目標(biāo)優(yōu)協(xié)調(diào)曲線法主要用于求解兩個(gè)目標(biāo)函數(shù)的多目標(biāo)優(yōu)化設(shè)計(jì)問題?；O(shè)計(jì)問題。目標(biāo)規(guī)劃法目標(biāo)規(guī)劃法Goal Attainment Method 引入目標(biāo)概念：引入目標(biāo)概念：F*，令非劣解集到目標(biāo)的，令非劣解集到目標(biāo)的距離（或稱范數(shù)）最小，選出一個(gè)非劣解。距離（或稱范數(shù)）最小，選出一個(gè)非劣解。Wi引入了一個(gè)松弛度的概念，松弛度最小引入了一個(gè)松弛度的概念，松弛度最小的一個(gè)非劣

37、解就是對(duì)于目標(biāo)的一個(gè)非劣解就是對(duì)于目標(biāo)F*的最可行解。的最可行解。優(yōu)點(diǎn)：不漏解，目標(biāo)明確，計(jì)算量小。優(yōu)點(diǎn)：不漏解，目標(biāo)明確，計(jì)算量小。缺點(diǎn)：對(duì)于非線性規(guī)劃設(shè)計(jì)：缺點(diǎn)：對(duì)于非線性規(guī)劃設(shè)計(jì)：運(yùn)用連續(xù)運(yùn)用連續(xù)二次形規(guī)劃二次形規(guī)劃(SQP - sequential quadratic programming)，線性的權(quán)值松弛在局部，線性的權(quán)值松弛在局部搜索范圍內(nèi)，會(huì)導(dǎo)致拒絕可大幅改進(jìn)總體搜索范圍內(nèi)，會(huì)導(dǎo)致拒絕可大幅改進(jìn)總體目標(biāo)的小步搜索。目標(biāo)的小步搜索。只針對(duì)連續(xù)問題，可只針對(duì)連續(xù)問題，可能只能給出局部最優(yōu)解。能只能給出局部最優(yōu)解。改進(jìn)：閱讀改進(jìn)：閱讀Matlab Optimization Toolb

38、ox 3.0.1 Users Guide中中Algorithm Improvements for Goal Attainment Method一節(jié)內(nèi)容。一節(jié)內(nèi)容。 1. 1. 變權(quán)系數(shù)法變權(quán)系數(shù)法 對(duì)于非負(fù)的權(quán)系數(shù)，若線性加權(quán)函數(shù)對(duì)于非負(fù)的權(quán)系數(shù)，若線性加權(quán)函數(shù)在線性加權(quán)法中，系列地改變權(quán)系數(shù)值，可獲得大量在線性加權(quán)法中，系列地改變權(quán)系數(shù)值，可獲得大量的非劣解，形成非劣解集。的非劣解，形成非劣解集。 第四節(jié)第四節(jié) 多目標(biāo)優(yōu)化的第二類方法多目標(biāo)優(yōu)化的第二類方法存在唯一的最優(yōu)解，則該最優(yōu)解是多目標(biāo)問題的存在唯一的最優(yōu)解，則該最優(yōu)解是多目標(biāo)問題的非劣解。非劣解。min()() s.t. ()01,2

39、, ()01,2, mllluvF Xw f XgXuph Xvq 2. 2. 約束法約束法 轉(zhuǎn)化為轉(zhuǎn)化為從多目標(biāo)中依據(jù)重要程度選擇一個(gè)目標(biāo)作為主目標(biāo)，從多目標(biāo)中依據(jù)重要程度選擇一個(gè)目標(biāo)作為主目標(biāo)，而將其它目標(biāo)轉(zhuǎn)化為約束，即將多目標(biāo)優(yōu)化問題而將其它目標(biāo)轉(zhuǎn)化為約束，即將多目標(biāo)優(yōu)化問題12min()(),(),() s.t. ()01,2, ()01,2,TmuvF Xf XfXfXgXuph Xvqmin () s.t. ()01,2, ()01,2, ()1,2, kuvllfXgXuph Xvqf Xlm lk可以證明，對(duì)于一組可以證明，對(duì)于一組 值，值，若若X*為為 約束問題的約束問題的唯

40、一最優(yōu)解，則其一定為多目標(biāo)問題的一個(gè)非劣唯一最優(yōu)解，則其一定為多目標(biāo)問題的一個(gè)非劣解。解。通過系列地改變通過系列地改變 值值，可獲得大量的非劣解，形成非，可獲得大量的非劣解，形成非劣解集。劣解集。 值應(yīng)大于值應(yīng)大于各單目標(biāo)函數(shù)的最優(yōu)值，可依據(jù)實(shí)際情況各單目標(biāo)函數(shù)的最優(yōu)值，可依據(jù)實(shí)際情況在下列范圍中變化：在下列范圍中變化： 約束法有關(guān)說明約束法有關(guān)說明00(0.001 0.01) 1,2,jjjffjm jk 1. 1. 逐步法逐步法在迭代過程中，分析者向決策者不斷提供試驗(yàn)解及在迭代過程中，分析者向決策者不斷提供試驗(yàn)解及其相應(yīng)的目標(biāo)函數(shù)值，請決策者指出哪一個(gè)目標(biāo)值其相應(yīng)的目標(biāo)函數(shù)值，請決策者指出

41、哪一個(gè)目標(biāo)值可以增加，哪一個(gè)目標(biāo)值應(yīng)減少。分析者根據(jù)決策可以增加，哪一個(gè)目標(biāo)值應(yīng)減少。分析者根據(jù)決策者的意圖，增添新的約束，求得新的試驗(yàn)解，進(jìn)入者的意圖，增添新的約束，求得新的試驗(yàn)解，進(jìn)入下一步迭代。直到求出使決策者滿意的優(yōu)惠解。下一步迭代。直到求出使決策者滿意的優(yōu)惠解。逐步法逐步法(Step Method)是是1971年由年由Benayoun等人提出的等人提出的求解線性多目標(biāo)優(yōu)化問題的一種交互式方法，此方法求解線性多目標(biāo)優(yōu)化問題的一種交互式方法，此方法本質(zhì)是在某種范數(shù)下求距理想點(diǎn)最近的點(diǎn)。本質(zhì)是在某種范數(shù)下求距理想點(diǎn)最近的點(diǎn)。 第五節(jié)第五節(jié) 多目標(biāo)優(yōu)化的第三類方法多目標(biāo)優(yōu)化的第三類方法 對(duì)于

42、線性多目標(biāo)優(yōu)化問題對(duì)于線性多目標(biāo)優(yōu)化問題 定義定義1211min()(),(),() s.t. 1,2, 01,2, () 1,2, TmnuiiiiinjjiiiF Xf XfXfXa xbupxinfXc x jm其中12121,12 , max,mmwjjjjmmFfffPp ppFPwfpWw ww兩點(diǎn)和間的距離為 其中為給定非負(fù)的權(quán)系數(shù)。 逐步法的計(jì)算步驟逐步法的計(jì)算步驟 （1 1）建立支付表）建立支付表 min() ,1,2,jjfXXDXjm求解得每個(gè)單目標(biāo)的極小點(diǎn)f1 f2 fm 1 2 m 11()f X12()fX1()mfX1()mf X2()mfX()mmfX21()f

43、 X22()fX2()mfX1,min(),1,2,ijjimmfXjm各列的最小值為，為理想點(diǎn)。(1)1,max(),1,2,;,12ijjimMfXjm DD k各列的最大值為轉(zhuǎn)（ ）。 （2 2）求第）求第k次迭代點(diǎn)次迭代點(diǎn)( )1,( )( ) min max() (),1,2,kjjjXjmkkjwfXmXDXfXjm求解得每個(gè)單目標(biāo)的極小點(diǎn)和相應(yīng)的目標(biāo)函數(shù)值1/,1, 2,mjjllwjm這 里12211221,0,0mjjjljljjmjjjljljMmcMMmMcMm當(dāng)其中 當(dāng) （3 3）與決策者對(duì)話）與決策者對(duì)話將目標(biāo)函數(shù)值提供給決策者，若決策者對(duì)所有目標(biāo)將目標(biāo)函數(shù)值提供給決

44、策者，若決策者對(duì)所有目標(biāo)值皆滿意，則獲得優(yōu)惠解，停止計(jì)算；若決策者對(duì)值皆滿意，則獲得優(yōu)惠解，停止計(jì)算；若決策者對(duì)所有目標(biāo)值皆不滿意，則計(jì)算失敗，停止計(jì)算；若所有目標(biāo)值皆不滿意，則計(jì)算失敗，停止計(jì)算；若決策者對(duì)部分目標(biāo)值滿意，對(duì)部分目標(biāo)值不滿意，決策者對(duì)部分目標(biāo)值滿意，對(duì)部分目標(biāo)值不滿意，則繼續(xù)計(jì)算。則繼續(xù)計(jì)算。在滿意的目標(biāo)中選一個(gè)目標(biāo)在滿意的目標(biāo)中選一個(gè)目標(biāo)fj*，并給出一個(gè)可以犧牲，并給出一個(gè)可以犧牲的量的量 fj*，意思是愿意讓，意思是愿意讓目標(biāo)目標(biāo)fj*增大增大 fj*，以換取，以換取其它其它不滿意目標(biāo)值的減小。并進(jìn)行如下計(jì)算：不滿意目標(biāo)值的減小。并進(jìn)行如下計(jì)算：*(1)( )( )(

45、)*(), (),1,2, kkkjjjkjjDXDffXfffXjm jj* 0,1,jkkkm令若此法失??；否則轉(zhuǎn)(2). 2. 2.代替價(jià)值交換法代替價(jià)值交換法代替價(jià)值交換法代替價(jià)值交換法(Surrogate Worth Trade-off Method)是是1971年由年由Haimes等人提出的求解非線性多目標(biāo)優(yōu)化問等人提出的求解非線性多目標(biāo)優(yōu)化問題的一種交互式方法。題的一種交互式方法。其其 約束問題為約束問題為對(duì)于多目標(biāo)優(yōu)化問題對(duì)于多目標(biāo)優(yōu)化問題12min()(),(),() s.t. ()01,2, ()01 ,2,TmuvF Xf XfXfXgXuph Xvqmin () s.t. ()01,2, ()01,2, ()1,2, kuvllfXgXuph Xvqf Xlm lk 約束問題的約束問題的K KT T條件條件 可以證明，約束目標(biāo)函數(shù)對(duì)應(yīng)的可以證明，約束目標(biāo)函數(shù)對(duì)應(yīng)的LagrangeLagrange乘子乘子pqmkjjuuvvjj kuvjjjjuuufXwfXgXh XwfX w jm jk gX up*1,*1()()()()02()001,2,3(