【正文】 x3進基， x1離基， z1會變差， z2會改善，進到 Pareto解 D。 多目標線性規(guī)劃單純形表 (4) 2 2 4 6 14 RHS 1 1 3 0 0 0 0 x4 1 0 2 0 1 0 0 x1 1 0 1 1 0 0 0 x2 3 0 4 0 0 1 0 z2 1 0 4 0 0 0 1 z1 x5 x4 x3 x2 x1 z2 z1 當前的解 (x1,x2,x3,x4,x5)=(2,4,0,2,0), z1=14, z2=6是Pareto解。 x3進基， x2離基，兩個目標同時會變差，回到劣解 A。 多目標線性規(guī)劃單純形表 (3) 2 4 2 0 16 RHS 1 1 3 0 0 0 0 x5 0 1 1 0 1 0 0 x1 0 1 2 1 0 0 0 x2 0 3 5 0 0 1 0 z2 0 1 1 0 0 0 1 z1 x5 x4 x3 x2 x1 z2 z1 當前的解 (x1,x2,x3,x4,x5)=(2,4,0,0,2), z1=16, z2=0是Pareto解。 x2進基， x3離基， z1， z2同時改善，進到 Pareto解 B。 多目標線性規(guī)劃單純形表 (2) 5 5 1 5 15 RHS 1 1/2 0 3/2 0 0 0 x5 0 1/2 0 1/2 1 0 0 x1 0 1/2 1 1/2 0 0 0 x3 0 1/2 0 5/2 0 1 0 z2 0 3/2 0 1/2 0 0 1 z1 x5 x4 x3 x2 x1 z2 z1 當前的解 (x1,x2,x3,x4,x5)=(5,0,1,0,5), z1=15, z2=5是劣解。 x1進基， x4離基， z1會改善， z2將會變差，進到劣解 A。 ?如果任何一個非基變量在兩個目標中的檢驗數(shù)不同時大于 0，這個基礎可行解是 Pareto解，任何一個非基變量進基，一個目標將會改善，而另一個目標將會變差。 6 5 4 3 2 1 0 1 2 3 4 5 6 z2 z1 O A B C D 多目標規(guī)劃的圖形 目標 z1的最優(yōu)解 目標 z2的最優(yōu)解 多目標規(guī)劃的 Pareto解集 x3=0 x4=0 x5=0 x2=0 x1=0 max z1=3x1+2x2 max z2=x1+2x2 . x1+ x2 ≤6 2x1+ x2 ≤10 x1+2x2 ≤10 x1， x2≥0 10 10 6 0 0 RHS 1 0 0 2 1 0 0 x5 0 1 0 1 2 0 0 x4 0 0 1 1 1 0 0 x3 0 0 0 2 1 1 0 z2 0 0 0 2 3 0 1 z1 x5 x4 x3 x2 x1 z2 z1 多目標線性規(guī)劃單純形表 (1) ?如果非基變量在兩個目標中的檢驗數(shù)都大于 0，當前的基礎可行解是劣解。 Pareto解集為折線 BCD。這樣的可行解是多目標規(guī)劃的 Pareto解。 目標函數(shù) z1改善的方向 目標函數(shù) z1和 z2同時改善的方向 z2 目標函數(shù) z2改善的方向 O A B E D C F 當一個可行解的優(yōu)化方向集合和可行域的交集為非空時，兩個目標 z1， z2可以同時改善，即這樣的可行解是劣解。 O A B E D C z1 z2 F z1 z2 O A B E D C z1 z2 z1 F 對于多目標規(guī)劃可行域中的點，根據(jù)兩個目標函數(shù)的法線方向，可以確定兩個目標同時可以改進的方向。 多目標規(guī)劃問題的非劣解和非劣解集 f1(X) f2(X) f(x) x Pareto 集 x1 x2 x4 x5 x3 圖中 x x5為劣解， x x x4為 Pareto解 劣解 劣解 Pareto解集的圖解 多目標線性規(guī)劃的 Pareto解集 (1) 設兩個目標的線性規(guī)劃為 min z1=c11x1+c12x2 min z2=c21x1+c22x2 . a11x1+a12x2≤b1 a21x1+a22x2≤b2 x1, x2≥0 設以 z1為單目標的線性規(guī)劃最優(yōu)解為 B，以 z2為單目標的線性規(guī)劃最優(yōu)解為 D。 設多目標規(guī)劃的可行域為 ?，設其中的一個可行解 X*∈ ?，它的 K個目標值分別 f1(X*) ， f2(X*)， …… ， fk(X*) 如果對于任意的可行解 X ∈ ?，都至少有一個目標 i，使得 fi(X)fi(X*) 則稱 X*為這個多目標規(guī)劃的一個 Pareto解（也稱為非劣解、有效解）。 區(qū)域內(nèi)部的點 N和 M稱為“劣解 ”，劣解的兩個目標同時可以改進。 ……用同樣的方法得到 B點。第五章 多目標規(guī)劃 ? 多目標線性規(guī)劃問題 ?多目標規(guī)劃問題的非劣解和非劣解集 ?求解多目標規(guī)劃的目標線性加權法 ?層次分析法 ?目標規(guī)劃 多目標規(guī)劃的例子 (1) 產(chǎn) 品 A B C 條件 利潤（萬元 /噸） 9 4 1 目標函數(shù)，最大化 耗用原料（噸 /噸） 4 2 5 耗用原料不超過 38噸 排放污染（ m3/噸） 2 1 3 排放污染不超過 25m3 銷售價格（萬元 /噸） 30 10 20 銷售總額不低于 100萬元 產(chǎn)量（噸） 1 1 1 總產(chǎn)量不低于 12噸 利潤最大化的線性規(guī)劃模型為： max z=9x1+4x2+x3 . 4x1+ 2x2+ 5x3≤38 耗用原料約束 2x1+ x2+ 3x3≤25 排放污染約束 30x1+10x2+20x3≥100 銷售總額約束 x1+ x2+ x3≥12 產(chǎn)量約束 x1, x2, x3≥0 最優(yōu)解如下表： 產(chǎn) 品 條件 最優(yōu)解 利潤（萬元 /噸） 目標函數(shù)，最大化 總利潤 83萬元 耗用原料（噸 /噸） 耗用原料不超過 38噸 耗用原料 38噸 排放污染（ m3/噸） 排放污染不超過 25m3 排放污染 19m3 銷售價格（萬元 /噸） 銷售總額不低于 100萬元 銷售總額 260萬元 產(chǎn)量（噸） 總產(chǎn)量不低于 12噸 總產(chǎn)量 12噸 如果允許排放的污染量從 25立方米逐步減少，最優(yōu)解也將發(fā)生變化。變化情況如下表：： 多目標規(guī)劃的例子 (2) 允許排放的 污染 (m3) 產(chǎn)品 A產(chǎn)量 （噸） 產(chǎn)品 B產(chǎn)量 （噸） 產(chǎn)品 C產(chǎn)量 （噸） 最大利潤 （萬元） 25 7 5 0 83 19 7 5 0 83 18 6 6 0 78 17 5 7 0 73 16 4 8 0 68 15 3 9 0 63 14 2 10 0 58 13 1 11 0 53 12 0 12 0 48 11 沒有可行解 多目標規(guī)劃的例子 (3) 25 24 23 22 21 19 18 17 16 15 14 13 12 允許排放的污染（ m3） 83 78 73 68 63 58 53 48 最大利潤（萬元） 允許排放的污染和最大利潤之間的關系 排放污染最小和利潤最大兩個目標可以同時實現(xiàn)的區(qū)域 利潤最大化和排放污染最小化雙目標問題的圖示 兩個目標的規(guī)劃問題的劣解和非劣解 第一個目標 第一個目標 z1A z1B z2A z2B N M P P’ A B 劣解 劣解 非劣解 (Pareto解 ) 非劣解 (Pareto解 ) 非劣解集 (Pareto解集 ) 兩個目標都可能實現(xiàn)的區(qū)域 第一個目標取定一個值 z1A，作為約束條件，優(yōu)化第二個目標，得到第二個目標的最優(yōu)值 Z2A，得到 A點。依次進行，得到兩個目標之間關系的曲線 AB和相應的區(qū)域。曲線AB上的點稱為 “非劣解 ”或 “Pareto”解，非劣解的兩個目標不可能同時改進。 如果一個多目標規(guī)劃問題有一個以上的 Pareto解，這些Pareto解組成的集合稱為 Pareto解集?？尚杏騼?nèi)部（不包括邊界）的可行解都是劣解。這是一個錐體，錐體內(nèi)的方向稱為多目標規(guī)劃的優(yōu)化方向集合。優(yōu)化方向集合和可行域的交集為空集時，兩個目標函數(shù)不可能同時改善。圖中的可行解B,C,D是多目標規(guī)劃的 Pareto解。 多目標線性規(guī)劃的 Pareto解集 (2) 用單純形表求解多目標線性規(guī)劃 Pareto解集 雙目標線性規(guī)劃問題為 max z1=3x1+2x2 max z2=x1+2x2 . x1+ x2 ≤6 2x1+ x2 ≤10 x1+2x2 ≤10 x1， x2≥0 標準化問題為 min z1=3x12x2 min z2= x12x2 . x1+ x2+x3 =6 2x1+ x2 +x4 =10 x1+2x2 +x5=10 x1, x2, x3, x4, x5≥0 多目標線性規(guī)劃問題的圖解。這個非基變量進基，兩個目標都會改善。 10 10 6 0 0 RHS 1 0 0 2 1 0 0 x5 0 1 0 1 2 0 0 x4 0 0 1 1 1 0 0 x3 0 0 0 2 1 1 0 z2 0 0 0 2 3 0 1 z1 x5 x4 x3 x2 x1 z2 z1 當前的解 (x1,x2,x3,x4,x5)=(0,0,6,10,10), z1=0, z2=0是劣解，對應于圖中的 O點。 x2進基， x5離基， z1， z2可以同時改善，進到 Pareto解 D。對應于 A點。 x4進基， x1離基， z1會變差， z2會改善，回到劣解 O。對應于 B點。 x4進基， x5離基， z1會變差， z2會改善，進到 Pareto解 C。對應于 C點。 x5進基， x4離基， z1會改善， z2會變差，回到 Pareto解 B。對應于 D點。 x5進基， x2離基， z1會變差， z2會變差，將回到劣解 O。 多目標線性規(guī)劃單純形表 (6) max z1=3x1+2x2 max z2=x1+2x2 . x1+ x2 ≤6 2x1+ x2 ≤10 x1+2x2 ≤10 x1， x2≥0 目標函數(shù)線性加權： z=?1z1+ ?2z2 0≤?1 ,?2≤1 ?1+ ?2＝ 1 由圖解可以看出，加權以后的單目標問題的最優(yōu)解必定是多目標規(guī)劃的一個 Pareto解。最簡單的評價函數(shù)是線性加權。 面積 (m2） 單價（元 /m2） 朝向 地段 樓層 住房 A 200 4800 南 丙 四層 住房 B 180 5500 西 甲 七層 住房 C 150 4000 東 乙 三層 例 1：住房選擇（決策空間是離散的） 確定各目標最理想和最不理想的值，將各目標進行歸一化處理。 面積（ m2） 單價（元 /m2） 朝向 地段 樓層 最好 200 () 3000 () 南 () 甲 () 三層 () 最差 75 () 6000 () 北 () 丁 () 一層 () 實際指標 A 200 4800 南 丙 四層 B 180 5500 西 甲 七層 C 150 4000 東 乙 三層 歸一化 A B C 確定各目標的權重 設目標重要性由大到小依次為：單價 — 面積 — 地段 —朝向 — 樓層確定目標權重 ?1 +?2 + ?3 + ?4 + ?5=1， 1 ?1 ?2 ?3 ?4 ?50 計算各方案的評價指標 F(X)=? ?4fi(X)，評價指標最高的為最優(yōu)決策。線性加權法的缺點是各目標的權重完全由主觀確定，而權重的選取對決策結果起著十分關鍵的作用。 在多目標決策中，各目標的權重對分析結果具有重