53目標(biāo)規(guī)劃模型

1、5.3目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃模型概述1）引例目標(biāo)規(guī)劃模型是有別于線性規(guī)劃模型的一類多目標(biāo)決策問題模型，通過下面的例子，我們可看出這兩 者的區(qū)別。例1某工廠的日生產(chǎn)能力為每天500小時(shí)，該廠生產(chǎn)A、B兩種產(chǎn)品，每生產(chǎn)一件A產(chǎn)品或B產(chǎn)品均需一 小時(shí)，由于市場需求有限，每天只有300件A產(chǎn)品或400件B產(chǎn)品可賣出去，每出售一件A產(chǎn)品可獲利10 元，每出售一件B產(chǎn)品可獲利5元，廠長按重要性大小的順序列出了下列目標(biāo)，并要求按這樣的目標(biāo)進(jìn)行 相應(yīng)的生產(chǎn)。（1）盡量避免生產(chǎn)能力閑置；（2）盡可能多地賣出產(chǎn)品，但對于能否多賣出A產(chǎn)品更感興趣；（3）盡量減少加班時(shí)間。顯然，這樣的多目標(biāo)決策問題，是單目標(biāo)決策的線性

2、規(guī)劃模型所難勝任的，對這類問題，須采用新的 方法和手段來建立對應(yīng)的模型。2）相關(guān)的幾個(gè)概念 （1）正、負(fù)偏差變量d +、d -負(fù)偏差變量d -表示決策值 .d的相互關(guān)系如下：正偏差變量d+表示決策值x （i = 12n超過目標(biāo)值的部分;未達(dá)到目標(biāo)值的部分；一般而言，正負(fù)偏差變量 +n）,d + 0 d -超過規(guī)定的目標(biāo)值時(shí)，二0 ，工；當(dāng)決策值d += 0，d-0；當(dāng)決策值x（頑2.n正好x （i = 12當(dāng)決策值iXi（i = 12n）未超過規(guī)定的目標(biāo)值時(shí)，等于規(guī)定的目標(biāo)值時(shí)，d +=0 d- = 0。（2）絕對約束和目標(biāo)約束絕對約束是必須嚴(yán)格滿足的等式約束或不等式約束，前述線性規(guī)劃中的約束

3、條件一般都是絕對約束； 而目標(biāo)約束是目標(biāo)規(guī)劃所特有的，在約束條件中允許目標(biāo)值發(fā)生一定的正偏差或負(fù)偏差的一類約束，它通 過在約束條件中引入正、負(fù)偏差變量d +、d-來實(shí)現(xiàn)。（3）優(yōu)先因子（優(yōu)先級）與權(quán)系數(shù)目標(biāo)規(guī)劃問題常要求許多目標(biāo)，在這些諸多目標(biāo)中，凡決策者要求第一位達(dá)到的目標(biāo)賦予優(yōu)先因子PPP P PP1，要求第二位達(dá)到的目標(biāo)賦予優(yōu)先因子2，并規(guī)定kk+1，即k +1級目標(biāo)的討論是在k級目標(biāo)得以實(shí)現(xiàn)后才進(jìn)行的（這里k = 12）。若要考慮兩個(gè)優(yōu)先因子相同的目標(biāo)的區(qū)別，則可W通過賦予它們不同的權(quán)系數(shù)j來完成。3）目標(biāo)規(guī)劃模型的目標(biāo)函數(shù)當(dāng)決策值七（T，2,目標(biāo)規(guī)劃的目標(biāo)函數(shù)是根據(jù)各目標(biāo)約束的正、負(fù)

4、偏差變量+、d_和其優(yōu)先因子來構(gòu)造的，一般而言， 當(dāng)每一目標(biāo)值確定后，我們總要求盡可能地縮小與目標(biāo)值的偏差，故目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是 min J f / +, d-）的形式。我們可將其分為以下三種情形：,n）要求恰好等于規(guī)定的目標(biāo)值時(shí)，這時(shí)正、負(fù)偏差變量d+、d 都要盡可能小，即對應(yīng)的目標(biāo)函數(shù)為：min z f （d + + d-） ；（2）當(dāng)決策值七=1，2,，）要求不超過規(guī)定的目標(biāo)值時(shí)，這時(shí)正偏差變量d +要盡可能小，min z f （d +）即對應(yīng)的目標(biāo)函數(shù)為：f （） ；（3）當(dāng)決策值七=1，2,，）要求超過規(guī)定的目標(biāo)值時(shí)，這時(shí)負(fù)偏差變量d _要盡可能小，即對應(yīng)的目標(biāo)函數(shù)為：min

5、Z = f以-）。目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式為:min z -P(另叩+叩;)Ec x + dj d + = g , (k = 1,2,.,k,g 為相應(yīng)的目標(biāo)值.). kj j k k kkj=1xjd -, 且滿足：k La x.b , (i = 1,2,.,m) 0,(j =1,2,.,n)d + 0, (k =1,2,.,K)kx , xd -有了以上的討論，在例1中，設(shè)1 2分別表示產(chǎn)品A、B的生產(chǎn)數(shù)量，1表示生產(chǎn)能力閑置的時(shí) 、 d + 工一，,、 d ,.一、. 、. , , ,d _, , ，一，間，1表示加班時(shí)間，2表示產(chǎn)品A沒能達(dá)到銷售目標(biāo)的數(shù)目，3表示產(chǎn)品B沒能達(dá)到銷售目

6、標(biāo)的數(shù) 目。因要求盡量避免生產(chǎn)能力閑置及盡量減少加班時(shí)間，故有目標(biāo)約束條件為：x + x + d d + = 500 d d +一 ， 一， ，、,211（ 1、1要盡可能?。?，又要求盡可能多地賣出產(chǎn)品，故有目標(biāo)約束條件x + d - = 300, x + d - = 400 d- d-多賣出A產(chǎn)品的要求可體現(xiàn)在目標(biāo)函為：1223（ 2、3要盡可能?。瑪?shù)的權(quán)系數(shù)中，于是可得到例1的目標(biāo)規(guī)劃模型為：min z = Pd- + 2P d- + P d- + Pd + TOC o 1-5 h z 11222331C.7, ECx + x + d d + 5001211x + d-= 300 x2

7、+ d-= 400 x , x , d, d , d , d + 0且滿足目標(biāo)約束： 121231應(yīng)用實(shí)例例1.職工的調(diào)資方案問題問題的提出某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時(shí)，要求相關(guān)部門遵守以下的規(guī)定:年工資總額不超過60000元；每級的人數(shù)不超過定編規(guī)定的人數(shù)；n、山級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%；山級不足編制的人數(shù)可錄用新職工，又I級的職工中有10%的人要退休。相關(guān)資料匯總于下表中，試為單位領(lǐng)導(dǎo)擬定一個(gè)滿足要求的調(diào)資方案。等級工資額(元/年)現(xiàn)有人數(shù)編制人數(shù)I20001012n15001215山1000155合計(jì)3742模型分析與變量假設(shè)顯然這是一個(gè)多目標(biāo)規(guī)劃的決策問題，適

8、于用目標(biāo)規(guī)劃模型求解，故需要確定該問題與之對應(yīng)的決策變 量、目標(biāo)值、優(yōu)先等級及權(quán)系數(shù)等。設(shè)氣、*2、%分別表示提升到I、n級和錄用到山級的新職工人數(shù)， 由題設(shè)要求可確定各目標(biāo)的優(yōu)先因子為：P一年工資總額不超過60000元；P每級的人數(shù)不超過定編規(guī)定的人數(shù)；Pn、山級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%；下面再確定目標(biāo)約束，因要求年工資總額不超過60000元，所以有：* * *d - - d += 60000 TOC o 1-5 h z 20000 (10-10X10%+ 1 ) +1500 (12- 1 + 2 ) +1000 (15- 2 + 3 ) + 11目d +且正偏差變量1要盡可能小，

9、又第二目標(biāo)要求每級的人數(shù)不超過定編規(guī)定的人數(shù)，所以，10(1 0.1) + * + d - d + = 1d +對I級有：122，且正偏差變量2要盡可能??；12 - * + * + d d + = 15d +對n級有：1233，且正偏差變量3要盡可能?。?5 一 x + x + d d + = 15d +對山級有：2344 ，且正偏差變量4要盡可能小;對第三目標(biāo)一一n、山級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%,我們有:X1 + d - - d + = 12 X 20%,且負(fù)偏差變量d 5要盡可能小;+ d - - d + = 15 x 20%,d -66且負(fù)偏差變量6要盡可能小;模型的建立由此，

10、我們可得到該問題的目標(biāo)規(guī)劃模型為：min z = Pd + + P (d + + d + + d +) + P (d- + d-)1 12234356且滿足:2000(9 + X ) +1500(12 一 x + X ) +1000(15 一 X1122X1+ d 項(xiàng)一 d 2x + x + d - d +1233 , 0(i = 1,2,3; j = 1,2,3,4,5,6)l i j j+ x ) + d d +=60000=3=3=0=2.4=3求解后可得到該問題的一個(gè)多重解，并將這些解匯總于下表中，以供領(lǐng)導(dǎo)根據(jù)具體情況進(jìn)行決策:變量含義解1解2解3解4X1晉升到I級的人數(shù)2. 42.

11、433X2晉升到n級的人數(shù)3335X3晉升到山級的人數(shù)0335d -工資總額的節(jié)余數(shù)6300330030000Td -I級缺編人數(shù)0. 60. 6002d -n級缺編人數(shù)2. 42. 4313d -山級缺編人數(shù)300. 604d +n級超編人數(shù)0000. 65d +山級超編人數(shù)0002O例2.物資的調(diào)運(yùn)安排問題問題的提出有一供需不平衡(供應(yīng)量需求量)的物資調(diào)運(yùn)問題如下表所示：請為其制訂物資調(diào)運(yùn)方案，使之滿足 以下的目標(biāo)要求：。盡量保證滿足重點(diǎn)客戶3的需求指標(biāo)；P2 要求總運(yùn)費(fèi)不超過預(yù)算指標(biāo)66 * 104元；3 至少滿足客戶123需求指標(biāo)的80%；P4 由A3至1的運(yùn)輸量按合同規(guī)定不少于1萬噸

12、；5 1至B3的道路危險(xiǎn)，運(yùn)量要減少到最低點(diǎn)?？瓦\(yùn)價(jià)倉庫B1B2B3供應(yīng)量(萬噸)A1CC12C135A2C21228A3C32C337需求量(萬噸)610模型分析與變量假設(shè)這仍然是一個(gè)多目標(biāo)決策規(guī)劃問題，雖然未給出給出倉庫到客戶之間的單位運(yùn)價(jià)，但這并不影響我們的 分析與建模。A (i = 1,2,3)B (j = 1,2,3)x設(shè)從倉庫i調(diào)撥到客戶的貨運(yùn)量為，因該問題的供應(yīng)量小于需求量，A (i = 1,2,3)B x + x + x故從倉庫i調(diào)撥到客戶的貨運(yùn)量1 j2 jd + = 0, d - 0 (i = 1,2,3) i3j 1，2,3)不可能超過所要求的需求量，因此，于是有:x +

13、 x + x + d - = 821311x + x+ x + d - = 6x + x + x + d- = 10又目標(biāo)P1為：盡量保證滿足重點(diǎn)客戶B3的需求指標(biāo)，故有:x + x + x + d - d+ = 10 d -. d +13233344 ，且4 4都要盡可能小;對目標(biāo)P2 :因要求總運(yùn)費(fèi)不超過預(yù)算指標(biāo)66 乂 104元，故有: TOC o 1-5 h z 咨 c x + d d += 66 x 104 ij ij 55d +1=1 j=1，且5應(yīng)盡可能小;對目標(biāo)七：因要求至少滿足客戶1 2 3需求指標(biāo)的80%，故有:x + x + x + d d + = 8 x 80%213166x + x + x + d d + = 6 x 80%223277x + x + x + d - - d + = 10 x 80%d - (i = 6,7,8)233388，且i應(yīng)盡可能小;對目標(biāo)P4 因要求由A3至1的運(yùn)輸量按合同規(guī)定不少