【正文】 . x1+ x2+x3 =6 2x1+ x2 +x4 =10 x1+2x2 +x5=10 x1, x2, x3, x4, x5≥0 多目標(biāo)線性規(guī)劃問(wèn)題的圖解。優(yōu)化方向集合和可行域的交集為空集時(shí)，兩個(gè)目標(biāo)函數(shù)不可能同時(shí)改善?？尚杏騼?nèi)部（不包括邊界）的可行解都是劣解。曲線AB上的點(diǎn)稱為 “非劣解 ”或 “Pareto”解，非劣解的兩個(gè)目標(biāo)不可能同時(shí)改進(jìn)。變化情況如下表：： 多目標(biāo)規(guī)劃的例子 (2) 允許排放的 污染 (m3) 產(chǎn)品 A產(chǎn)量 （噸） 產(chǎn)品 B產(chǎn)量 （噸） 產(chǎn)品 C產(chǎn)量 （噸） 最大利潤(rùn) （萬(wà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 沒(méi)有可行解 多目標(biāo)規(guī)劃的例子 (3) 25 24 23 22 21 19 18 17 16 15 14 13 12 允許排放的污染（ m3） 83 78 73 68 63 58 53 48 最大利潤(rùn)（萬(wàn)元） 允許排放的污染和最大利潤(rùn)之間的關(guān)系 排放污染最小和利潤(rùn)最大兩個(gè)目標(biāo)可以同時(shí)實(shí)現(xiàn)的區(qū)域 利潤(rùn)最大化和排放污染最小化雙目標(biāo)問(wèn)題的圖示 兩個(gè)目標(biāo)的規(guī)劃問(wèn)題的劣解和非劣解 第一個(gè)目標(biāo) 第一個(gè)目標(biāo) z1A z1B z2A z2B N M P P’ A B 劣解 劣解 非劣解 (Pareto解 ) 非劣解 (Pareto解 ) 非劣解集 (Pareto解集 ) 兩個(gè)目標(biāo)都可能實(shí)現(xiàn)的區(qū)域 第一個(gè)目標(biāo)取定一個(gè)值 z1A，作為約束條件，優(yōu)化第二個(gè)目標(biāo)，得到第二個(gè)目標(biāo)的最優(yōu)值 Z2A，得到 A點(diǎn)。 ……用同樣的方法得到 B點(diǎn)。 設(shè)多目標(biāo)規(guī)劃的可行域?yàn)??，設(shè)其中的一個(gè)可行解 X*∈ ?，它的 K個(gè)目標(biāo)值分別 f1(X*) ， f2(X*)， …… ， fk(X*) 如果對(duì)于任意的可行解 X ∈ ?，都至少有一個(gè)目標(biāo) i，使得 fi(X)fi(X*) 則稱 X*為這個(gè)多目標(biāo)規(guī)劃的一個(gè) Pareto解（也稱為非劣解、有效解）。 O A B E D C z1 z2 F z1 z2 O A B E D C z1 z2 z1 F 對(duì)于多目標(biāo)規(guī)劃可行域中的點(diǎn)，根據(jù)兩個(gè)目標(biāo)函數(shù)的法線方向，可以確定兩個(gè)目標(biāo)同時(shí)可以改進(jìn)的方向。這樣的可行解是多目標(biāo)規(guī)劃的 Pareto解。 6 5 4 3 2 1 0 1 2 3 4 5 6 z2 z1 O A B C D 多目標(biāo)規(guī)劃的圖形 目標(biāo) z1的最優(yōu)解 目標(biāo) z2的最優(yōu)解 多目標(biāo)規(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 多目標(biāo)線性規(guī)劃單純形表 (1) ?如果非基變量在兩個(gè)目標(biāo)中的檢驗(yàn)數(shù)都大于 0，當(dāng)前的基礎(chǔ)可行解是劣解。 x1進(jìn)基， x4離基， z1會(huì)改善， z2將會(huì)變差，進(jìn)到劣解 A。 x2進(jìn)基， x3離基， z1， z2同時(shí)改善，進(jìn)到 Pareto解 B。 x3進(jìn)基， x2離基，兩個(gè)目標(biāo)同時(shí)會(huì)變差，回到劣解 A。 x3進(jìn)基， x1離基， z1會(huì)變差， z2會(huì)改善，進(jìn)到 Pareto解 D。 x1進(jìn)基， x3離基， z1會(huì)改善， z2會(huì)變差，回到 Pareto解 C。 5 4 3 2 1 012345 z2 z1 ?1z1+ ?2z2 求解多目標(biāo)線性規(guī)劃的線性加權(quán)法 多目標(biāo)的線性加權(quán)轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題 一、多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題 評(píng)價(jià)函數(shù)法 F(X)=U{f1(X)， f2(X)， … ， fK(X)} 將多目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題。最理想的值為 1，最不理想的值為 0，將各決策方案的實(shí)際目標(biāo)值轉(zhuǎn)化為 0～ 1之間的值。 優(yōu)點(diǎn) ?方便直觀，簡(jiǎn)單易行 ?可以利用豐富的單目標(biāo)決策方法和軟件 缺點(diǎn) ?權(quán)重的確定完全靠決策者主觀判斷 ?對(duì)不同量綱的目標(biāo)，合成以后的目標(biāo)實(shí)際意義不明 線性加權(quán)法的優(yōu)缺點(diǎn) 層次分析法 （ AHP） 層次分析法是由 T. L. Saaty提出的一種確定多目標(biāo)決策中各目標(biāo)的權(quán)重的方法，不僅在多目標(biāo)決策中有重要作用，在管理以外的其它學(xué)科也有許多應(yīng)用。 ?????????3254A的特征根。 ?????? ???3254A 0325410013254|IA| ???????????????矩陣特征根的計(jì)算 判斷矩陣特征向量和特征根的疊代算法 ??????????????????????????13/4424/3132/34/13/112/12/13/221A??????????????????????????4/14/14/14/1W 0???????????????????????????????????????????????????AW 01 歸一化為任取一個(gè)初始 n1向量 計(jì)算 112 WAWW ????????????????????????????????????????已經(jīng)收斂。 Wnwwwnwnwnwnwwww/ww/ww/ww/ww/ww/ww/ww/ww/wWAnnnnnnnnn??????????????????????????????????????????????????????????????????????212121212221212111因此，只要給出判斷矩陣，就可以求出 n個(gè)物體的歸一化重量。即可能出現(xiàn) A1比 A2重要， A2比 A3重要， A3又比 A1重要這樣的判斷。這個(gè)指標(biāo)是隨機(jī)產(chǎn)生的不同維數(shù)的判斷矩陣的特征根的平均值 計(jì)算一致性指標(biāo) .（ Consistency Index） 計(jì)算一致性比例 .（ Consistency Ratio） .. ?當(dāng) . ，認(rèn)為判斷矩陣的一致性是可以接受的。 如果 約束條件互不相容 ，則線性規(guī)劃無(wú)可行解。 一般形式表示為： m,2,1ibpnxa)pn(miniiin1jjijm1iii??????????01234 4 3 2 1 1 p3=3 n4=1 2x1+3x2=12 (1) x2=3 (4) x1x2=1 (2) x1+x2=2 (3) n1=4 n2=2 p3=1 n4=1 用 LINDO求解以上問(wèn)題，得到目標(biāo)規(guī)劃的最優(yōu)解為： x1=3， x2=2 p1=0, p2=0, p3=3, p4=0 n1=0, n2=0, n3=0, n4=1 min z=4 min z=n1+p1+n2+p2+n3+p3+n4+p4 . 2x1+3x2+n1p1 =12 (1) x1 x2 +n2p2 = 1 (2) x1+ x2 +n3p3= 2 (3) x2+n4 p4 = 3 (4) x1, x2, ni, pi ≥0 產(chǎn)品 A 產(chǎn)品 B 產(chǎn)品 C 條件 利潤(rùn)（萬(wàn)元 /噸） 9 4 1 總利潤(rùn)最大化 耗用原料（噸 /噸） 4 2 5 耗用原料總量不超過(guò) 38噸 排放污染（ m3/噸） 2 1 3 排放污染總量不超過(guò)26m3 銷售價(jià)格（萬(wàn)元 /噸） 30 10 20 銷售總額不低于 100萬(wàn)元 總產(chǎn)量（噸） 1 1 1 總產(chǎn)量不低于 18噸 如果以利潤(rùn)為目標(biāo)函數(shù)，線性規(guī)劃模型為： max z=9x1+4x2+x3 . 4x1+ 2x2+ 5x3≤ 38 （ 1）原料總量約束 2x1+ x2+ 3x3≤ 26 （ 2）排放污染約束 30x1+10x2+20x3≥100 （ 3）銷售總額約束 x1+ x2+ x3≥ 18 （ 4）總產(chǎn)量約束 x1, x2, x3 ≥0 目 標(biāo) 產(chǎn)品 A 產(chǎn)品 B 產(chǎn)品 C 目標(biāo)的 理想值 正偏差 變量 負(fù)偏差 變量 利潤(rùn)（萬(wàn)元 /噸） 9 4 1 77 p1 n1 耗用原料（噸 /噸） 4 2 5 38 p2 n2 排放污染（ m3/噸） 2 1 3 26 p3 n3 銷售價(jià)格（萬(wàn)元 /噸） 30 10 20 100 p4 n4 總產(chǎn)量（噸） 1 1 1 18 p5 n5 如果將利潤(rùn)、耗用原料等五個(gè)因素作為目標(biāo)，確定各目標(biāo)的理想值以及偏差變量如下： 如果目標(biāo)大于理想值，正偏差變量大于 0，小于理想值，負(fù)偏差變量大于 0。克服了線性規(guī)劃只能求解單目標(biāo)的缺點(diǎn)?？朔司€性規(guī)劃無(wú)解的問(wèn)題。 min{(n1+p1)， (n2+p2)， (n3+p3)， (n4+p4)} . 2x1+2x2+n1p1 =20 優(yōu)先級(jí) 1 x1+ x2 +n2p2 =20 優(yōu)先級(jí) 2 x1 +n3p3 = 5 優(yōu)先級(jí) 3 x2 +n4p4= 3 優(yōu)先級(jí) 4 x1， x2， n1， n2， n3， n4， p1， p2， p3， p4≥0 字典序優(yōu)化的圖解法 min{(n1+p1),(n2+p2),(n3+p3),(n4+p4)} . 2x1+2x2+n1p1 =16 (1) x1+ x2 +n2p2 =4 (2) x1 +n3p3 = 2 (3)