【正文】 了目標(biāo)規(guī)劃（ Goal Programming），這是一種求解多目標(biāo)線(xiàn)性規(guī)劃的方法。 目標(biāo)規(guī)劃分為 無(wú)優(yōu)先級(jí)的目標(biāo)規(guī)劃 和 有優(yōu)先級(jí)的目標(biāo)規(guī)劃 。 目標(biāo)規(guī)劃的圖解 設(shè)線(xiàn)性規(guī)劃問(wèn)題為 max z=2x1+3x2 . x1 x2 ≤1 x1+x2 ≥2 x2 ≤3 x1， x2 ≥0 由圖解可知，線(xiàn)性規(guī)劃的最優(yōu)解為： x1=4， x2=3 max z=17 01234 3 2 1 1 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 +n4p4 = 3 (4) x1, x2, n1, p1， n2, p2, n3, p3, n4, p4 ≥0 相應(yīng)的目標(biāo)規(guī)劃問(wèn)題為 其中 p p p p4稱(chēng)為正偏差變量， n n n n4稱(chēng)為負(fù)偏差變量。 一般形式表示為： 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)解為： min z=4， x1=3， x2=2 p1=0, p2=0, p3=3, p4=0 n1=0, n2=0, n3=0, n4=1 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 銷(xiāo)售價(jià)格（萬(wàn)元 /噸） 30 10 20 銷(xiāo)售總額不低于 100萬(wàn)元 總產(chǎn)量（噸） 1 1 1 總產(chǎn)量不低于 18噸 如果以利潤(rùn)為目標(biāo)函數(shù)，線(xiàn)性規(guī)劃模型為： max z=9x1+4x2+x3 . 4x1+ 2x2+ 5x3≤ 38 （ 1）原料總量約束 2x1+ x2+ 3x3≤ 26 （ 2）排放污染約束 30x1+10x2+20x3≥100 （ 3）銷(xiāo)售總額約束 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 銷(xiāo)售價(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。因此，對(duì)第 i個(gè)目標(biāo)，有 iiin1jjij bpnxa ?????如果各目標(biāo)無(wú)優(yōu)先級(jí)，要使所有的目標(biāo)總偏差最小，即 ???m1iii )pn(min 目標(biāo)規(guī)劃的模型為： 對(duì)于每一個(gè)目標(biāo)，正偏差變量和負(fù)偏差變量在系數(shù)矩陣中的列向量是兩個(gè)相同的單位向量，是線(xiàn)性相關(guān)的，不可能同時(shí)出現(xiàn)在基矩陣中，因此，以上問(wèn)題的任何一個(gè)基礎(chǔ)可行解，同一個(gè)目標(biāo)的正負(fù)偏差變量，不可能兩個(gè)同時(shí)大于 0。這一結(jié)果的實(shí)際意義也是很清楚的：任何一個(gè)目標(biāo)，不可能既大于理想值，又小于理想值。 0pnpnpnpnpnxxx18pnxxx100pnx20x10x3026pnx3xx238pnx5x2x4)pn()pn()pn()pn()pn(min554433221132155321443213332122321113214422335511??????????????????????????????????? 產(chǎn)品 A 產(chǎn)品 B 產(chǎn)品 C 目標(biāo)的 理想值 正偏差 變量 負(fù)偏差 變量 產(chǎn)量（噸） 0 10 0 RHS pi ni 達(dá) 到 的 目 標(biāo) 值 利潤(rùn)（萬(wàn)元） 40 77 0 37 耗用原料（噸） 30 38 0 18 排放污染（ m3） 10 26 0 16 銷(xiāo)售價(jià)格（萬(wàn)元） 100 100 0 0 總產(chǎn)量（噸） 10 18 0 8 用單純形法，得到目標(biāo)規(guī)劃的最優(yōu)解、各目標(biāo)的值以及偏差變量的值 最優(yōu)解 目標(biāo)值 偏差變量 目標(biāo)規(guī)劃的特點(diǎn) ?可以求解多目標(biāo)問(wèn)題?？朔司€(xiàn)性規(guī)劃只能求解單目標(biāo)的缺點(diǎn)。 ?用目標(biāo)（ Goal）的概念取代了線(xiàn)性規(guī)劃中的“約束條件”，用偏離各目標(biāo)的總偏差最小取代了線(xiàn)性規(guī)劃中的目標(biāo)函數(shù)，消除了線(xiàn)性規(guī)劃中目標(biāo)函數(shù)和約束條件的對(duì)立。 ?各目標(biāo)值既可以正偏差，也可以負(fù)偏差，克服了線(xiàn)性規(guī)劃約束條件的剛性。 ?目標(biāo)規(guī)劃總是有可行解的?？朔司€(xiàn)性規(guī)劃無(wú)解的問(wèn)題。 目標(biāo)有優(yōu)先級(jí)的目標(biāo)規(guī)劃 在上面的例子中，利潤(rùn)、耗用原料、排放污染、銷(xiāo)售額、總產(chǎn)量等五個(gè)目標(biāo)是一視同仁的，最優(yōu)解是使偏離五個(gè)目標(biāo)的總偏差之和最小。在實(shí)際問(wèn)題中，這些目標(biāo)往往是有輕重緩急的。 產(chǎn)品 A 產(chǎn)品 B 產(chǎn)品 C 目標(biāo)的 理想值 正偏差 變量 負(fù)偏差 變量 產(chǎn)量（噸） 0 10 0 RHS pi ni 達(dá) 到 的 目 標(biāo) 值 利潤(rùn)（萬(wàn)元） 40 77 0 37 耗用原料（噸） 30 38 0 18 排放污染（ m3） 10 26 0 16 銷(xiāo)售價(jià)格（萬(wàn)元） 100 100 0 0 總產(chǎn)量（噸） 10 18 0 8 確定五個(gè)目標(biāo)的優(yōu)先級(jí) Pi（ Pi=1， 2， 3， 4， 5），數(shù)字越小優(yōu)先級(jí)越高 目 標(biāo) 產(chǎn)品 A 產(chǎn)品 B 產(chǎn)品 C 優(yōu)先級(jí) Pi 目標(biāo)的 理想值 正偏差 變量 負(fù)偏差 變量 利潤(rùn)（萬(wàn)元 /噸） 9 4 1 1 77 p1 n1 耗用原料（噸 /噸） 4 2 5 5 38 p2 n2 排放污染（ m3/噸） 2 1 3 3 26 p3 n3 銷(xiāo)售價(jià)格（萬(wàn)元 /噸） 30 10 20 2 100 p4 n4 總產(chǎn)量（噸） 1 1 1 4 18 p5 n5 目標(biāo)有優(yōu)先級(jí)的目標(biāo)規(guī)劃解法有： ?加權(quán)法 ?字典序法 目 標(biāo) 產(chǎn)品 A 產(chǎn)品 B 產(chǎn)品 C 優(yōu)先級(jí) 權(quán)重 理想值 正偏差 負(fù)偏差 利潤(rùn)（萬(wàn)元 /噸） 9 4 1 1 10000 77 p1 n1 耗用原料（噸 /噸） 4 2 5 5 1 38 p2 n2 排放污染（ m3/噸） 2 1 3 3 100 26 p3 n3 銷(xiāo)售價(jià)格（萬(wàn)元 /噸） 30 10 20 2 1000 100 p4 n4 總產(chǎn)量（噸） 1 1 1 4 10 18 p5 n5 目標(biāo)具有優(yōu)先級(jí)的目標(biāo)規(guī)劃解法 —— 加權(quán)法 0pnpnpnpnpnxxx18pnxxx100pnx20x10x3026pnx3xx238pnx5x2x4)pn()pn(10)pn(10)pn(10)pn(10min5544332211321553214432133321223211132144222333554115????????????????????????????????????????????? 產(chǎn)品 A 產(chǎn)品 B 產(chǎn)品 C 理想值 正偏差 負(fù)偏差 產(chǎn)量（噸） 0 10 0 RHS pi ni 無(wú) 優(yōu) 先 級(jí) 利潤(rùn)（萬(wàn)元） 40 77 0 37 耗用原料（噸） 30 38 0 18 排放污染（ m3） 10 26 0 16 銷(xiāo)售價(jià)格（萬(wàn)元） 100 100 0 0 總產(chǎn)量（噸） 10 18 0 8 產(chǎn)品 A 產(chǎn)品 B 產(chǎn)品 C 理想值 正偏差 負(fù)偏差 產(chǎn)量（噸） 1 0 RHS pi ni 有 優(yōu) 先 級(jí) 1 利潤(rùn)（萬(wàn)元） 77 77 0 0 5 耗用原料（噸） 38 38 0 0 3 排放污染（ m3） 26 0 2 銷(xiāo)售價(jià)格（萬(wàn)元） 100 0 4 總產(chǎn)量（噸） 18 0 目標(biāo)具有優(yōu)先級(jí)的目標(biāo)規(guī)劃解法 — 字典序優(yōu)化（ Lexicooptimization） 字典序法的原則是： ?首先不顧其它目標(biāo)，對(duì)優(yōu)先級(jí)最高的目標(biāo)進(jìn)行優(yōu)化，得到使第一級(jí)目標(biāo)最優(yōu)的決策變量的值以及第一級(jí)目標(biāo)函數(shù)的值； ?然后在不使第一級(jí)目標(biāo)變差的前提下，優(yōu)化第二級(jí)目標(biāo)； ?用同樣的原則，按優(yōu)先級(jí)從高到低，依次優(yōu)化各級(jí)目標(biāo)，直至所有目標(biāo)都優(yōu)化完畢。 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) x2 +n4p4= 3 (4) x1， x2， ni， pi≥0 02468 8 6 4 2 x1 x2 2x1+2x2=16 x1+x2=4 x1=2 x2=3 p1 n1 p2 n2 p3 n3 p4 n4 第一優(yōu)先級(jí)最優(yōu)解 第二優(yōu)先級(jí)最優(yōu)解 第三優(yōu)先級(jí)最優(yōu)解 第四優(yōu)先級(jí)最優(yōu)解 min{(n1+p1),(n2+p2),(n3+p3),(n4+p4)} . 2x1+2x2+n1p1 =16 優(yōu)先級(jí) P1 x1+ x2 +n2p2 =4 優(yōu)先級(jí) P2 x1 +n3p3 = 2 優(yōu)先級(jí) P3 x2 +n4p4= 3 優(yōu)先級(jí) P4 x1， x2， ni， pi≥0 具有目標(biāo)優(yōu)先級(jí)的目標(biāo)規(guī)劃單純形表 x1 x2 n1 p1 n2 p2 n3 p3 n4 p4 RHS P1 1 1 0 P2 1 1 0 P3 1 1 0 P4 1 1 0 n1 2 2 1 1 16 n2 1 1 1 1 4 n3 1 0 1 1