第04章目標(biāo)規(guī)劃

第四章目標(biāo)規(guī)劃OperationalResearch(OR)本章內(nèi)容目標(biāo)規(guī)劃問(wèn)題及其數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的靈敏度分析目標(biāo)規(guī)劃應(yīng)用舉例目標(biāo)規(guī)劃問(wèn)題的導(dǎo)出例4-1

某工廠(chǎng)生產(chǎn)兩種產(chǎn)品，受到原材料供應(yīng)和設(shè)備工時(shí)的限制。在單件利潤(rùn)等有關(guān)數(shù)據(jù)已知上網(wǎng)條件下，要求制訂一個(gè)獲利最大的生產(chǎn)計(jì)劃。具體數(shù)據(jù)如下：產(chǎn)品ⅠⅡ限量原材料（kg/件）51060設(shè)備工時(shí)（h/件）4440利潤(rùn)（元/件）68解得，最優(yōu)解x1=8，x2=2，maxz=64（元）目標(biāo)規(guī)劃問(wèn)題的導(dǎo)出一般來(lái)說(shuō)，一個(gè)計(jì)劃問(wèn)題可能要滿(mǎn)足多方面得要求。線(xiàn)性規(guī)劃有最優(yōu)解的必要條件是其可行解集非空，即各約束條件彼此相容。但實(shí)際問(wèn)題有時(shí)不能滿(mǎn)足這樣的要求。線(xiàn)性規(guī)劃解得可行性和最優(yōu)性具有十分明確的意義，但那都是針對(duì)特定數(shù)學(xué)模型而言的。實(shí)際中，決策者需要計(jì)劃人員提供的不是嚴(yán)格的數(shù)學(xué)上的最優(yōu)解，而是可以幫助作出最優(yōu)決策的參考性計(jì)劃，或是提供多種計(jì)劃方案，供最終決策時(shí)選擇。例4-2假設(shè)計(jì)劃人員被要求考慮如下意見(jiàn)：(1)由于產(chǎn)品Ⅱ銷(xiāo)售疲軟，故希望產(chǎn)品Ⅱ的產(chǎn)量不超過(guò)產(chǎn)品Ⅰ的一半；(2)原材料嚴(yán)重短缺，生產(chǎn)中應(yīng)避免過(guò)量消耗；(3)最好能節(jié)約4h設(shè)備工時(shí)；(4)計(jì)劃利潤(rùn)不少于48元。計(jì)劃人員需要會(huì)同有關(guān)各方作進(jìn)一步的協(xié)調(diào)，最后達(dá)成了一致意見(jiàn)：原材料使用限額不得突破；產(chǎn)品Ⅱ產(chǎn)量要求必須優(yōu)先考慮；設(shè)備工時(shí)問(wèn)題其次考慮；最后考慮計(jì)劃利潤(rùn)的要求。類(lèi)似這樣的多目標(biāo)決策問(wèn)題是典型的目標(biāo)規(guī)劃問(wèn)題。目標(biāo)規(guī)劃問(wèn)題的導(dǎo)出目標(biāo)規(guī)劃的數(shù)學(xué)模型基本概念（1）偏差變量d+≥0，d-≥0，d+·d-=0（2）絕對(duì)約束和目標(biāo)約束（3）優(yōu)先因子和權(quán)系數(shù)（4）目標(biāo)規(guī)劃的目標(biāo)函數(shù)三種基本表達(dá)式：

①要求恰好達(dá)到目標(biāo)值min{f(d++d-)}②要求不超過(guò)目標(biāo)值，但允許不足目標(biāo)值min{f(d+)}③要求不低于目標(biāo)值，但允許超過(guò)目標(biāo)值min{f(d-)}目標(biāo)規(guī)劃的數(shù)學(xué)模型例4-1的目標(biāo)規(guī)劃表達(dá)式為：min{P1d1-,P2d2+,P3d3-}絕對(duì)約束目標(biāo)約束P1為兩種產(chǎn)品產(chǎn)量要求的優(yōu)先因子；P2為節(jié)約工時(shí)要求的優(yōu)先因子；P3為計(jì)劃利潤(rùn)要求的優(yōu)先因子，它們應(yīng)滿(mǎn)足P1》P2》P3目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式：gk為第k個(gè)目標(biāo)約束的預(yù)期目標(biāo)值，Wlk-和Wlk+為Pl優(yōu)先因子對(duì)應(yīng)各目標(biāo)的權(quán)系數(shù)。目標(biāo)規(guī)劃目標(biāo)規(guī)劃問(wèn)題及其數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的靈敏度分析目標(biāo)規(guī)劃應(yīng)用舉例目標(biāo)規(guī)劃的圖解法對(duì)于只有兩個(gè)決策變量的目標(biāo)規(guī)劃問(wèn)題，可以用圖解方法來(lái)求解。在用圖解法解目標(biāo)規(guī)劃時(shí)，首先必須滿(mǎn)足所有絕對(duì)約束。在此基礎(chǔ)上，再按照優(yōu)先級(jí)從高到低的順序，逐個(gè)地考慮各個(gè)目標(biāo)約束。一般地，若優(yōu)先因子Pj對(duì)應(yīng)的解空間為Rj，則優(yōu)先因子Pj+1對(duì)應(yīng)的解空間只能在Rj中考慮，即Rj+1屬于Rj。若Rj不空，而Rj+1為空集，則Rj中的解為目標(biāo)規(guī)劃的滿(mǎn)意解，它只能保證滿(mǎn)足P1,P2,…,Pj級(jí)目標(biāo)，而不保證滿(mǎn)足其后的各級(jí)目標(biāo)。目標(biāo)規(guī)劃的圖解法例4-3

用圖解法解例4-2。R1R2△OAB區(qū)域是滿(mǎn)足絕對(duì)約束和非負(fù)條件的解空間。對(duì)于所有目標(biāo)約束，去掉偏差變量，畫(huà)出相應(yīng)直線(xiàn)，然后標(biāo)出偏差變量變化時(shí)直線(xiàn)平移方向，見(jiàn)圖所示。首先考慮P1，此時(shí)要求mind-1，因而解空間R1為△OAC區(qū)域；再考慮P2，此時(shí)要求mind2+，因而解空間R2為△ODC區(qū)域；最后考慮P3，此時(shí)要求mind3-，因而解空間R3為四邊形EDCF區(qū)域。容易求得E，D，C，F(xiàn)四點(diǎn)的坐標(biāo)分別為(8,0)、(9,0)、(6,3)、(4.8,2.4)，故問(wèn)題的解可表示為：α1(8,0)+α2(9,0)+α3(6,3)+α4(4.8,2.4)=(8α1+9α2+6α3+4.8α4,3α3+2.4α4)其中，α1，α2，α3，α4≥0，

α1+α2+α3+α4=1目標(biāo)規(guī)劃的圖解法例4-3最后一級(jí)目標(biāo)的解空間非空。這時(shí)得到的解能滿(mǎn)足所有目標(biāo)的要求。當(dāng)解不惟一時(shí)(如例4-3，R3為四邊形EDCF區(qū)域)，決策者在作實(shí)際決策時(shí)究竟選擇哪一個(gè)解，完全取決于決策者自身的考慮。目標(biāo)規(guī)劃的圖解法例4-4

用圖解法解下面的目標(biāo)規(guī)劃min{P1d1-,P2d2+,P3(5d3-+3d4-),P4d1+}目標(biāo)規(guī)劃的圖解法所以滿(mǎn)意解為：x1=6.5，x2=1.25目標(biāo)規(guī)劃的圖解法例4-4得到的解不能滿(mǎn)足所有目標(biāo)。這時(shí)，我們要做的是尋找滿(mǎn)意解，使它盡可能滿(mǎn)足高級(jí)別的目標(biāo)，同時(shí)又使它對(duì)那些不能滿(mǎn)足的較低級(jí)別目標(biāo)的偏離程度盡可能的小。必須注意的是，在考慮低級(jí)別目標(biāo)時(shí)，不能破壞已經(jīng)滿(mǎn)足的高級(jí)別目標(biāo)，這是目標(biāo)規(guī)劃的基本原則。但是，也不能因此而以為，當(dāng)高級(jí)別目標(biāo)不能滿(mǎn)足時(shí)，其后的低級(jí)別目標(biāo)也一定不能被滿(mǎn)足。事實(shí)上，在有些目標(biāo)規(guī)劃中，當(dāng)某一優(yōu)先級(jí)的目標(biāo)不能滿(mǎn)足時(shí)，其后的某些低級(jí)別目標(biāo)仍有可能被滿(mǎn)足。目標(biāo)規(guī)劃目標(biāo)規(guī)劃問(wèn)題及其數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的靈敏度分析目標(biāo)規(guī)劃應(yīng)用舉例解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型實(shí)際上是最小化形的線(xiàn)性規(guī)劃，可以用單純形法求解。在用單純形法解目標(biāo)規(guī)劃時(shí)，檢驗(yàn)數(shù)是各優(yōu)先因子的線(xiàn)性組合。因此，在判別各檢驗(yàn)數(shù)的正負(fù)及大小時(shí)，必須注意P1?P2?P3?…。當(dāng)所有檢驗(yàn)數(shù)都已滿(mǎn)足最優(yōu)性條件(cj-zj≥0)時(shí)，從最終單純形表上就可以得到目標(biāo)規(guī)劃的解。解目標(biāo)規(guī)劃的單純形法例4-5

用單純形法解例4-4。引入松弛變量x3，

min{P1d1-,P2d2+,P3d3-}cj→000P100P2P30CBxBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000P1d1-0[1]-201-100000d2-36440001-100P3d3-4868000001-1zj-cjP1-120010000P2000000100P3-6-800000010x3600201-5500000x101-201-100000d2-360120-441-100P3d3-480[20]0-66001-1zj-cjP1000100000P2000000100P30-2006-600010x3120011-100-110x124/51002/5-2/5001/10-1/100d2-36/5000-2/52/51-1-3/53/5P3x212/5010-3/103/10001/20-1/20zj-cjP1000100000P2000000100P3000000010解目標(biāo)規(guī)劃的單純形法在單純形表Ⅲ中，由于非基變量d1+和d3+的檢驗(yàn)數(shù)都是零，故知例4-4有多重最優(yōu)解(滿(mǎn)意解)。以d1+為換入變量繼續(xù)迭代，可得如下單純形表Ⅳcj→000P100P2P30CBxBbx1x2x3d1-d1+d2-d2+d3-d3+0x320010/310000-5/65/6P1x1814/3000001/6-1/60d2-40-4/30001-1-2/32/3P3d1+8010/30-11001/6-1/6cj-zjP1000100000P2000000100P3000000010Ⅳ解目標(biāo)規(guī)劃的單純形法以d3+為換入變量繼續(xù)迭代，可得如下單純形表Ⅴcj→000P100P2P30CBCBbx1x2x3d1-d1+d2-d2+d3-d3+0d3+120011-100-11P1x16101/101/2-1/200000d2-000-3/5-111-100P3x23011/20-1/41/40000cj-zjP1000100000P2000000100P3000000010解目標(biāo)規(guī)劃的單純形法解目標(biāo)規(guī)劃的單純形法結(jié)論：

例4-5的解為以上四個(gè)滿(mǎn)意解(即C，D，E，F(xiàn)四點(diǎn))的凸組合。而且，從單純形表Ⅲ，Ⅳ，Ⅴ，Ⅵ中可知，各非基變量檢驗(yàn)數(shù)中三個(gè)優(yōu)先因子的系數(shù)全部非負(fù)，這表示任何一個(gè)滿(mǎn)意解都能滿(mǎn)足所有目標(biāo)的要求。單純形法和圖解法的解題結(jié)果完全一致。目標(biāo)規(guī)劃目標(biāo)規(guī)劃問(wèn)題及其數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的靈敏度分析目標(biāo)規(guī)劃應(yīng)用舉例目標(biāo)規(guī)劃的靈敏度分析在目標(biāo)規(guī)劃建模時(shí)，目標(biāo)優(yōu)先級(jí)和權(quán)系數(shù)的確定往往帶有一定的主觀性，因此，對(duì)它們的靈敏度分析是目標(biāo)規(guī)劃靈敏度分析的主要內(nèi)容。目標(biāo)規(guī)劃靈敏度分析的方法、原理同線(xiàn)性規(guī)劃的靈敏度分析本質(zhì)上相同。

例4-6

對(duì)例4-4的目標(biāo)規(guī)劃問(wèn)題，已求得滿(mǎn)意解為x1=13/2,x2=5/4?，F(xiàn)決策者想知道，目標(biāo)函數(shù)中各目標(biāo)的優(yōu)先因子和權(quán)系數(shù)對(duì)最終解的影響。為此，提出了下面兩個(gè)靈敏度分析問(wèn)題，即目標(biāo)函數(shù)分別變?yōu)椋?1)min{P1d1-,P2d2+,P3d1+,P4(5d3-+3d4-)}(2)min{P1d1-,P2d2+,P3(W1d3-+W2d4-),P4d1+}(W1,W2>0)目標(biāo)規(guī)劃的靈敏度分析解目標(biāo)函數(shù)的變化僅影響原解的最優(yōu)性，即各變量的檢驗(yàn)數(shù)。因此，應(yīng)當(dāng)先考察檢驗(yàn)數(shù)的變化，然后再作適當(dāng)?shù)奶幚怼?.當(dāng)目標(biāo)函數(shù)變?yōu)椋?），就是要了解交換第三和第四優(yōu)先級(jí)目標(biāo)對(duì)原解的影響。此時(shí)，單純形表變?yōu)橄卤恚篶j→00P1P30P25P403P40CBxBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x113/210001/2-1/21/2-1/200P3d1+300-111-100003P4d4-3/40000-1/41/41/4-1/41-10x25/401001/4-1/4-1/41/400cj-zjP10010000000P20000000000P30010-110000P400003/4-3/417/43/403目標(biāo)規(guī)劃的靈敏度分析可見(jiàn)，原解最優(yōu)性已被破壞(d2-的檢驗(yàn)數(shù)-P3+3/4P4<0)，故應(yīng)用單純形法繼續(xù)求解。目標(biāo)規(guī)劃的靈敏度分析cj→00P1P30P25P403P40CBxBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x15101/2-1/2001/2-1/2000d2-300-111-100003P4d4-3/200-1/41/4001/4-1/41-10x21/2011/4-1/400-1/41/400cj-zjP10010000000P20000000000P30001010000P4003/4-3/40017/43/403可知，第三和第四優(yōu)先級(jí)目標(biāo)交換后，原滿(mǎn)意解已失去了最優(yōu)性。新的滿(mǎn)意解為x1=5,x2=1/2當(dāng)目標(biāo)函數(shù)變?yōu)?2)，就是要了解第三優(yōu)先級(jí)中兩目標(biāo)權(quán)系數(shù)取值對(duì)原解的影響。此時(shí)，單純形表變?yōu)?目標(biāo)規(guī)劃的靈敏度分析cj→00P1P40P2W1P30W2P30CBxBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x113/210001/2-1/21/2-1/200P4d1+300-111-10000W2P3d4-3/40000-1/41/41/4-1/41-10x25/401001/4-1/4-1/41/400cj-zjP10010000000P20000010000P30000W2/4-W2/4-W2/4W2/40W2P40010-1117/43/403可知，原解是否改變?nèi)Q于d3-的檢驗(yàn)數(shù)W1-W2/4。因此：當(dāng)W1-W2/4>0，即W1/W2>1/4時(shí)，原解不變，仍為x1=13/2,x2=5/4當(dāng)W1/W2<1/4時(shí)，原解改變。用單純形法繼續(xù)求解，可得新的滿(mǎn)意解x1=5,x2=2(此時(shí)，d3-=3,d4-=0)

當(dāng)W1/W2=1/4時(shí)，兩個(gè)解均為滿(mǎn)意解。目標(biāo)規(guī)劃的靈敏度分析第三優(yōu)先級(jí)兩目標(biāo)權(quán)系數(shù)的改變有可能會(huì)影響所得的滿(mǎn)意解。解的變化取決于兩目標(biāo)權(quán)系數(shù)的比值W1/W2，其臨界點(diǎn)為1/4。事實(shí)上，在前兩優(yōu)先級(jí)目標(biāo)均已被滿(mǎn)足的條件下，如滿(mǎn)足d3-=0，則使d4-=3/4；如滿(mǎn)足d4-=0，則使d3-=3。d4-/d3-=1/4。如將W1/W2看作同一優(yōu)先級(jí)下兩目標(biāo)重要程度的比較，而將d4-/d3-看作因此而引起的不滿(mǎn)足程度的比較，則兩者的一致恰好說(shuō)明了目標(biāo)規(guī)劃中權(quán)系數(shù)的作用和意義。目標(biāo)規(guī)劃目標(biāo)規(guī)劃問(wèn)題及其數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的靈敏度分析目標(biāo)規(guī)劃應(yīng)用舉例目標(biāo)規(guī)劃應(yīng)用舉例例8

有三個(gè)產(chǎn)地向四個(gè)銷(xiāo)地供應(yīng)物資。產(chǎn)地Ai(i=1,2,3)的供應(yīng)量ai、銷(xiāo)地Bj(j=1,2,3,4)的需要量bj、各產(chǎn)銷(xiāo)地之間的單位物資運(yùn)費(fèi)cij見(jiàn)表。表中，ai和bj的單位為t，cij的單位為元／t。編制調(diào)運(yùn)方案時(shí)要求按照相應(yīng)的優(yōu)先級(jí)依次考慮下列7項(xiàng)目標(biāo)：P1:B4是重點(diǎn)保證單位，其需要量應(yīng)盡可能全部滿(mǎn)足；P2:A3向B1提供的物資不少于100t；P3:每個(gè)銷(xiāo)地得到的物資數(shù)量不少于其需要量的80%；P4:實(shí)際的總運(yùn)費(fèi)不超過(guò)當(dāng)不考慮P1至P6各目標(biāo)時(shí)的最小總運(yùn)費(fèi)的110%；P5:因路況原因，盡量避免安排A2的物資運(yùn)往B4；P6:對(duì)B1和B3的供應(yīng)率要盡可能相同；P7:力求使總運(yùn)費(fèi)最省。試求滿(mǎn)意的調(diào)運(yùn)方案。目標(biāo)規(guī)劃應(yīng)用舉例B1B2B3B4aiA15267300A23546200A34523400bj200100450250解用表上作業(yè)法可以求得不考慮P1至P6各目標(biāo)時(shí)的最小運(yùn)費(fèi)調(diào)運(yùn)方案，相應(yīng)的最小運(yùn)費(fèi)為2950元?，F(xiàn)在建立問(wèn)題的目標(biāo)