目標(biāo)規(guī)劃培訓(xùn)課程

1、第4章 目標(biāo)規(guī)劃 第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型 第2節(jié) 解目標(biāo)規(guī)劃的圖解法 第3節(jié) 解目標(biāo)規(guī)劃的單純形法 第4節(jié) 靈敏度分析 第5節(jié) 應(yīng)用舉例前 言 前幾章，所討論的都是單目標(biāo)的決策問(wèn)題，但在現(xiàn)實(shí)世界中，一個(gè)企業(yè)可能同時(shí)有多個(gè)目標(biāo)：保持比較穩(wěn)定的價(jià)格和利潤(rùn)，提高產(chǎn)品的市場(chǎng)占有率，維持比較穩(wěn)定的職工隊(duì)伍等。這些目標(biāo)很難集中到一個(gè)目標(biāo)上，而且各個(gè)目標(biāo)甚至相互矛盾，相互沖突。對(duì)于這類問(wèn)題，我們提出一種新的方案，目標(biāo)規(guī)劃。 由于目標(biāo)之間的不協(xié)調(diào)性和矛盾性，不大可能實(shí)現(xiàn)所有的目標(biāo)，只能尋求一種折中的方案。 目標(biāo)規(guī)劃的基本思想是：對(duì)于管理部門提出的每一個(gè)目標(biāo)，由決策者確定一個(gè)具體的數(shù)量目標(biāo)，并對(duì)每一個(gè)目標(biāo)建

2、立一個(gè)目標(biāo)函數(shù)；1尋求一個(gè)使目標(biāo)函數(shù)和對(duì)應(yīng)目標(biāo)間偏差和最小的解。第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型 為了具體說(shuō)明目標(biāo)規(guī)劃與線性規(guī)劃在處理問(wèn)題方法上的區(qū)別，先通過(guò)例子來(lái)介紹目標(biāo)規(guī)劃的有關(guān)概念及數(shù)學(xué)模型。 例1 某工廠生產(chǎn)，兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)見下表。試求獲利最大的生產(chǎn)方案。 擁有量 原材料(kg) 設(shè)備(hr) 2 1 1 2 11 10 利潤(rùn)(元/件) 8 10 解： 這是求獲利最大的單目標(biāo)的規(guī)劃問(wèn)題，用x1，x2分別表示，產(chǎn)品的產(chǎn)量，其線性規(guī)劃模型表述為： 0,102112108max21212121xxxxxxxxz滿足約束條件：目標(biāo)函數(shù)：用圖解法求得最優(yōu)決策方案為：x1*=4, x2*=3,

3、z*=62(元)。 (4,3)0,102112108max21212121xxxxxxxxz滿足約束條件：目標(biāo)函數(shù)：實(shí)際上工廠在作決策時(shí)，要考慮市場(chǎng)等一系列其他條件 （1) 根據(jù)市場(chǎng)信息，產(chǎn)品的銷售量有下降的趨勢(shì)，故考慮產(chǎn)品的產(chǎn)量不大于產(chǎn)品。 (2) 超過(guò)計(jì)劃供應(yīng)的原材料時(shí)，需用高價(jià)采購(gòu)，會(huì)使成本大幅度增加。 (3) 應(yīng)盡可能充分利用設(shè)備臺(tái)時(shí)，但不希望加班。 (4) 應(yīng)盡可能達(dá)到并超過(guò)計(jì)劃利潤(rùn)指標(biāo)56元。 這樣在考慮產(chǎn)品決策時(shí)，便為多目標(biāo)決策問(wèn)題。目標(biāo)規(guī)劃方法是解這類決策問(wèn)題的方法之一。下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念。 1.設(shè)x1，x2為決策變量，此外，引進(jìn)正、負(fù)偏差變量d+，d-

4、。正偏差變量d表示決策值超過(guò)目標(biāo)值的部分；負(fù)偏差變量d-表示決策值未達(dá)到目標(biāo)值的部分。因決策值不可能既超過(guò)目標(biāo)值同時(shí)又未達(dá)到目標(biāo)值，即恒有d+d-=0。2.絕對(duì)約束和目標(biāo)約束 絕對(duì)約束是指必須嚴(yán)格滿足的等式約束和不等式約束；如線性規(guī)劃問(wèn)題的所有約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。目標(biāo)約束是目標(biāo)規(guī)劃特有的，可把約束右端項(xiàng)看作要追求的目標(biāo)值。在達(dá)到此目標(biāo)值時(shí)允許發(fā)生正或負(fù)偏差，因此在這些約束中加入正、負(fù)偏差變量，它們是軟約束。線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可變換為目標(biāo)約束。也可根據(jù)問(wèn)題的需要將絕對(duì)約束變換為目標(biāo)約束。如：例1的目標(biāo)函數(shù)z=8

5、x1+10 x2可變換為目標(biāo)約束8x1+10 x2+d1-d1+=56。約束條件2x1+x211可變換為目標(biāo)約束2x1+x2+d2-d2+=11。3.優(yōu)先因子(優(yōu)先等級(jí))與權(quán)系數(shù) 一個(gè)規(guī)劃問(wèn)題常常有若干目標(biāo)。但決策者在要求達(dá)到這些目標(biāo)時(shí)，是有主次或輕重緩急的不同。要求第一位達(dá)到的目標(biāo)賦予優(yōu)先因子P1，次位的目標(biāo)賦予優(yōu)先因子P2，并規(guī)定PkPk+1,k=1,2,，K。表示Pk比Pk+1有更大的優(yōu)先權(quán)。即首先保證P1級(jí)目標(biāo)的實(shí)現(xiàn)，這時(shí)可不考慮次級(jí)目標(biāo)；而P2級(jí)目標(biāo)是在實(shí)現(xiàn)P1級(jí)目標(biāo)的基礎(chǔ)上考慮的；依此類推。若要區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，這時(shí)可分別賦予它們不同的權(quán)系數(shù)j,這些都由決策者按

6、具體情況而定。 4.目標(biāo)規(guī)劃的目標(biāo)函數(shù) 目標(biāo)規(guī)劃的目標(biāo)函數(shù)(準(zhǔn)則函數(shù))是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是 min z=f(d+,d-)。其基本形式有三種： (1) 要求恰好達(dá)到目標(biāo)值，即正、負(fù)偏差變量都要盡可能地小，這時(shí) min z=f(d+d-) (2) 要求不超過(guò)目標(biāo)值，即允許達(dá)不到目標(biāo)值，就是正偏差變量要盡可能地小。這時(shí)min z=f(d+) (3) 要求超過(guò)目標(biāo)值，即超過(guò)量不限，但必須是負(fù)偏差變量要盡可能地小，這時(shí)min z=f(d-) 對(duì)每一個(gè)具體目標(biāo)規(guī)劃問(wèn)題，可根據(jù)

7、決策者的要求和賦予各目標(biāo)的優(yōu)先因子來(lái)構(gòu)造目標(biāo)函數(shù)，以下用例子說(shuō)明。 例例2 例1的決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮：首先是產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備有效臺(tái)時(shí)，不加班；再次是利潤(rùn)額不小于56元。求決策方案 。解解 按決策者所要求的，分別賦予這三個(gè)目標(biāo)P1，P2，P3優(yōu)先因子。這問(wèn)題的數(shù)學(xué)模型是： 3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii滿足約束條件：目標(biāo)函數(shù)：目標(biāo)規(guī)劃的一般數(shù)學(xué)模型為)54(3 , 2 , 1, 0,)44(, 1, 0) 34(

8、, 1,),()24(, 1,) 14()(min1111kddnjxmibxaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLll滿足約束條件：目標(biāo)函數(shù)： 為權(quán)系數(shù)。 lklk,目標(biāo)規(guī)劃的建模技巧 1 列出全部約束條件 2 把要達(dá)到指標(biāo)的約束不等式加上正負(fù)偏差量后化為目標(biāo)約束等式 3對(duì)目標(biāo)賦予相應(yīng)的優(yōu)先因子 4對(duì)同級(jí)目標(biāo)賦予不同的權(quán)系數(shù) 5構(gòu)造一個(gè)按優(yōu)先因子及權(quán)系數(shù)和對(duì)應(yīng)的目標(biāo)偏差量所要實(shí)現(xiàn)最小化的目標(biāo)函數(shù) 例 某單位領(lǐng)導(dǎo)在考慮本單位職工的升級(jí)調(diào)資方案時(shí)，依次遵守以下規(guī)定： (1) 不超過(guò)年工資總額60000元； (2) 每級(jí)的人數(shù)不超過(guò)定編規(guī)定的人數(shù)； (3) ，

9、級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%，且無(wú)越級(jí)提升； (4) 級(jí)不足編制的人數(shù)可錄用新職工，又級(jí)的職工中有10%要退休。 有關(guān)資料匯總于表4-8中，問(wèn)該領(lǐng)導(dǎo)應(yīng)如何擬訂一個(gè)滿意的方案。 解解 設(shè)x1、x2、x3分別表示提升到、級(jí)和錄用到級(jí)的新職工人數(shù)。對(duì)各目標(biāo)確定的優(yōu)先因子為：建模舉例表4-8等級(jí) 工資額(元/年) 現(xiàn)有人數(shù) 編制人數(shù) 2000 1500 1000 10 12 15 12 15 15 合計(jì) 37 42 解解 設(shè)x1、x2、x3分別表示提升到、級(jí)和錄用到級(jí)的新職工人數(shù)。對(duì)各目標(biāo)確定的優(yōu)先因子為： P1不超過(guò)年工資總額60000元； P2每級(jí)的人數(shù)不超過(guò)定編規(guī)定的人數(shù)； P3、級(jí)的升

10、級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%。先分別建立各目標(biāo)約束。年工資總額不超過(guò)60000元 2000(10-100.1+x1)+ 1500(12-x1+x2)+1000(15-x2+x3)+ d1-d1+ =60000 每級(jí)的人數(shù)不超過(guò)定編規(guī)定的人數(shù)： 對(duì)級(jí)有 10(1-0.1)+x1+d2-d2+=12 對(duì)級(jí)有 12-x1+x2+d3-d3+=15 對(duì)級(jí)有 15-x2+x3+d4-d4+=15 ，級(jí)的升級(jí)面不大于現(xiàn)有人數(shù)的20%，但盡可能多提； 對(duì)級(jí)有 x1+d5-d5+=120.2 對(duì)級(jí)有 x2+d6-d6+=150.2 目標(biāo)函數(shù)：min z=P1d1+P2(d2+d3+d4+)+P3(d5-+d

11、6-) 以上目標(biāo)規(guī)劃模型可用單純形法求解，得到多重解?，F(xiàn)將這些解匯總于表4-9，這單位的領(lǐng)導(dǎo)再按具體情況，從表4-9中選一個(gè)執(zhí)行方案 變 量 含義 解 1 解 2 解 3 解 4 x1 x2 x3 d1- d2- d3- d4- d5+ d6+ 晉升到級(jí)的人數(shù) 晉升到級(jí)的人數(shù) 新招收級(jí)的人數(shù) 工資總額的結(jié)余額 級(jí)缺編人數(shù) 級(jí)缺編人數(shù) 級(jí)缺編人數(shù) 級(jí)超編人數(shù) 級(jí)超編人數(shù) 2.4 3 0 6300 0.6 2.4 3 0 0 2.4 3 3 3300 0.6 2.4 0 0 0 3 3 3 3000 0 3 0.6 0 0 3 5 5 0 0 1 0 0.6 2 例7 已知有三個(gè)產(chǎn)地給四個(gè)銷地供應(yīng)

12、某種產(chǎn)品，產(chǎn)銷地之間的供需量和單位運(yùn)價(jià)見表4-10。有關(guān)部門在研究調(diào)運(yùn)方案時(shí)依次考慮以下七項(xiàng)目標(biāo)，并規(guī)定其相應(yīng)的優(yōu)先等級(jí)： P1B4是重點(diǎn)保證單位，必須全部滿足其需要； P2A3向B1提供的產(chǎn)量不少于100； P3每個(gè)銷地的供應(yīng)量不小于其需要量的80%； P4所定調(diào)運(yùn)方案的總運(yùn)費(fèi)不超過(guò)最小運(yùn)費(fèi)調(diào)運(yùn)方案的10%； P5因路段的問(wèn)題，盡量避免安排將A2的產(chǎn)品往B4； P6給B1和B3的供應(yīng)率要相同； P7力求總運(yùn)費(fèi)最省。 試求滿意的調(diào)運(yùn)方案。表4-10銷 地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 5 3 4 2 5 5 6 4 2 7 6 3 300 200 400 銷 量 200

13、100 450 250 900/1000 解解 上作業(yè)法求得最小運(yùn)費(fèi)的調(diào)運(yùn)方案見表4-11。這時(shí)得最小運(yùn)費(fèi)為2950元，再根據(jù)提出的各項(xiàng)目標(biāo)的要求建立目標(biāo)規(guī)劃的模型。銷 地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 虛設(shè)點(diǎn) 200 100 200 250 150 100 300 200 400 100 銷 量 200 100 450 250 1000/1000 表4-11 供應(yīng)約束 x11+x12+x13+x14300 x21+x22+x23+x24200 x31+x32+x33+x34400 需求約束：x11+x21+x31+d1-d1+=200 x12+x22+x32+d2-d2

14、+=100 x13+x23+x33+d3-d3+=450 x14+x24+x34+d4-d4+=250 A3向B1提供的產(chǎn)品量不少于100 x31+d5-d5+=100 每個(gè)銷地的供應(yīng)量不小于其需要量的80% x11+x21+x31+d6-d6+=2000.8 x12+x22+x32+d7-d7+=1000.8 x13+x23+x33+d8-d8+=4500.8 x14+x24+x34+d9-d9+=2500.8調(diào)運(yùn)方案的總運(yùn)費(fèi)不超過(guò)最小運(yùn)費(fèi)調(diào)運(yùn)方案的10%31411010%)101 (2950ijijijddxc 因路段的問(wèn)題，盡量避免安排將A2的產(chǎn)品運(yùn)往B4 x24+d11-d11+=0

15、給B1和B3的供應(yīng)率要相同 (x11+x21+x31)-(200/450)(x13+x23+x33)+d12-d12+=0力求總運(yùn)費(fèi)最省314113132950ijijijddxc目標(biāo)函數(shù)為：13712126115104987635241)()(mindPddPdPdPddddPdPdPz計(jì)算結(jié)果，得到滿意調(diào)運(yùn)方案見表4-12。銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 虛設(shè)點(diǎn) 90 100 10 100 110 250 90 200 50 300 200 400 100 銷 量 200 100 450 250 1000 總運(yùn)費(fèi)為3360元。元336050320072502110

16、410021004903C 第第2節(jié)節(jié) 解目標(biāo)規(guī)劃的圖解法解目標(biāo)規(guī)劃的圖解法 對(duì)只具有兩個(gè)決策變量的目標(biāo)規(guī)劃的數(shù)學(xué)模型，可以用圖解法來(lái)分析求解。用例2來(lái)說(shuō)明（圖4-1） 。3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii 注意目標(biāo)規(guī)劃問(wèn)題求解時(shí)，把絕對(duì)約束作最高優(yōu)先級(jí)考慮。在本例中能依先后次序都滿足d1+=1，d2+d2-=0，d-3=0，因而z*=0。但在大多數(shù)問(wèn)題中并非如此，會(huì)出現(xiàn)某些約束得不到滿足，故將目標(biāo)規(guī)劃問(wèn)題的最優(yōu)解稱為滿意解。 例3 某電視機(jī)廠裝配黑白和彩色兩種電視

17、機(jī)，每裝配一臺(tái)電視機(jī)需占用裝配線1小時(shí)，裝配線每周計(jì)劃開動(dòng)40小時(shí)。預(yù)計(jì)市場(chǎng)每周彩色電視機(jī)的銷量是24臺(tái)，每臺(tái)可獲利80元；黑白電視機(jī)的銷量是30臺(tái)，每臺(tái)可獲利40元。該廠確定的目標(biāo)為： 第一優(yōu)先級(jí)：充分利用裝配線每周計(jì)劃開動(dòng)40小時(shí)； 第二優(yōu)先級(jí)：允許裝配線加班；但加班時(shí)間每周盡量不超過(guò)10小時(shí)； 第三優(yōu)先級(jí)：裝配電視機(jī)的數(shù)量盡量滿足市場(chǎng)需要。因彩色電視機(jī)的利潤(rùn)高，取其權(quán)系數(shù)為2。 試建立這問(wèn)題的目標(biāo)規(guī)劃模型，并求解黑白和彩色電視機(jī)的產(chǎn)量。 解 設(shè)x1，x2分別表示黑白和彩色電視機(jī)的產(chǎn)量。這個(gè)問(wèn)題的目標(biāo)規(guī)劃模型為11223341211122213324412min(2)40502430,0,

18、1,2,3,4iizPdP dPddxxddxxddxddxddx x ddi目標(biāo)函數(shù)：滿足約束條件：用圖解法求解，見圖4.2。從圖4.2中看到 在考慮具有P1、P2的目標(biāo)實(shí)現(xiàn)后，x1、x2的取值范圍為ABCD?？紤]P3的目標(biāo)要求時(shí)，因d3的權(quán)系數(shù)大于d4，故先考慮min d3；這時(shí)x1、x2的取值范圍縮小為ABEF區(qū)域。然后考慮d4。在ABEF中無(wú)法滿足d4=0，因此只能在ABEF中取一點(diǎn)，使d4盡可能小，這就是E點(diǎn)。故E點(diǎn)為滿意解。其坐標(biāo)為(24，26)，即該廠每周應(yīng)裝配彩色電視機(jī)24臺(tái)，黑白電視機(jī)26臺(tái)。第第3節(jié)節(jié) 解目標(biāo)規(guī)劃的單純形法解目標(biāo)規(guī)劃的單純形法 目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)

19、劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒(méi)有本質(zhì)的區(qū)別，所以可用單純形法求解。但要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定： (1) 因目標(biāo)規(guī)劃問(wèn)題的目標(biāo)函數(shù)都是求最小化，所以以cj-zj0，j=1,2,，n為最優(yōu)準(zhǔn)則。 (2) 因非基變量的檢驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子，即 因P1P2PK；從每個(gè)檢驗(yàn)數(shù)的整體來(lái)看：檢驗(yàn)數(shù)的正、負(fù)首先決定于P1的系數(shù)1j的正、負(fù)。若1j=0，這時(shí)此檢驗(yàn)數(shù)的正、負(fù)就決定于P2的系數(shù)2j的正、負(fù)，下面可依此類推。 解目標(biāo)規(guī)劃問(wèn)題的單純形法的計(jì)算步驟： (1) 建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成K行，置k=1。 (2) 檢查該行中是否存在負(fù)數(shù)，且對(duì)應(yīng)的前k-1

20、行的系數(shù)是零。若有負(fù)數(shù)取其中最小者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)(3)。若無(wú)負(fù)數(shù)，則轉(zhuǎn)(5)。 (3) 按最小比值規(guī)則確定換出變量，當(dāng)存在兩個(gè)和兩個(gè)以上相同的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量。 (4) 按單純形法進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回(2)。 (5) 當(dāng)k=K時(shí)，計(jì)算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回到(2)。例例4 4 試用單純形法來(lái)求解例2。將例2的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型： 3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxxddxxddxxddxxxxxdPddPdPziiss滿足約束條件

21、：目標(biāo)函數(shù)： 取xs，d1-，d2-，d3-為初始基變量，列初始單純形表，見表4-1。 cj P1 P2 P3 P4 CB XB b x1 x2 xs d1- d1+ d2- d2+ d3- d3+ P2 P3 xs d1- d2- d3- 11 0 10 56 2 1 1 8 1 -1 2 10 1 1 -1 1 -1 1 -1 11/1 / 10/2 56/10 cj-zj P1 P2 P3 -1 -8 -2 -10 1 2 1 取k=1，檢查檢驗(yàn)數(shù)的P1行，因該行無(wú)負(fù)檢驗(yàn)數(shù)，故轉(zhuǎn)(5)。 因k(=2)K(=3)，置k=k+1=3，返回到(2)。 查出檢驗(yàn)數(shù)P2行中有-1、-2；取min(

22、-1,-2)=-2。 它對(duì)應(yīng)的變量x2為換入變量， 轉(zhuǎn)入(3)。在表4-1上計(jì)算最小比值=min(11/1，0，10/2，56/10)=10/2它對(duì)應(yīng)的變量d2-為換出變量，轉(zhuǎn)入(4)計(jì)算結(jié)果見表4-2。 表4-3返回到(2)。依此類推，直至得到最終表為止。見表4-3。表4-3所示的解x1*=2，x2*=4為例1的滿意解。此解相當(dāng)于圖4-1的G點(diǎn)。檢查表4-3的檢驗(yàn)數(shù)行，發(fā)現(xiàn)非基變量d3+的檢驗(yàn)數(shù)為0，這表示存在多重解。在表4-3中以非基變量d3+為換入變量，d1-為換出變量，經(jīng)迭代得到表4-4。 cj P1 P2 P3 P4 CB XB b x1 x2 xs d1- d1+ d2- d2+ d3- d3+ xs d3+ x2 x1 1 4 10/3 10/3 1 1 1 -1 2 -1/3 2/3 1 -2 1/3 -2/3 -1 6 1/3 1/3 1 -6 -1/3 -1/3 -1 1 cj-zj P1 P2 P3 1 1 1 1 由表4-4得到解x1*=10/3，x2*=10/3，此解相當(dāng)于圖4-1的D點(diǎn)，G、D兩點(diǎn)的凸線性組合都是例1的滿意解第第4 4節(jié)節(jié) 靈敏度分析靈敏度分析 目標(biāo)規(guī)劃的靈敏度分析方法與線性規(guī)劃相似，這里除分析各項(xiàng)系數(shù)的變化外，還有優(yōu)先因子的變化問(wèn)題，下