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

1、5.3目標(biāo)規(guī)劃模型1.目標(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)決策的線性規(guī)劃模型所難勝任的

2、,對這類問題,須采用新的方法和手段來建立對應(yīng)的模型.2相關(guān)的幾個(gè)概念1正、負(fù)偏差變量d、d正偏差變量d表示決策值xii1,2,n超過目標(biāo)值的局部；負(fù)偏差變量d表示決策值xii1,2,n未到達(dá)目標(biāo)值的局部；一般而言,正負(fù)偏差變量d、d的相互關(guān)系如下：當(dāng)決策值xii1,2,n超過規(guī)定的目標(biāo)值時(shí),d0,d0；當(dāng)決策值xii1,2,n未超過規(guī)定的目標(biāo)值時(shí),d,d；當(dāng)決策值為1,2,n正好等于規(guī)定的目標(biāo)值時(shí),d0,d0.2絕對約束和目標(biāo)約束絕對約束是必須嚴(yán)格滿足的等式約束或不等式約束,前述線性規(guī)劃中的約束條件一般都是絕對約束；而目標(biāo)約束是目標(biāo)規(guī)劃所特有的,在約束條件中允許目標(biāo)值發(fā)生一定的正偏差或負(fù)偏差的

3、一類約束,它通過在約束條件中引入正、負(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)先因子P,要求第二位到達(dá)的目標(biāo)賦予優(yōu)先因子P2,并規(guī)定PkPk1,即Pk1級目標(biāo)的討論是在Pk級目標(biāo)得以實(shí)現(xiàn)后才進(jìn)行的(這里 k1,2,n)o假設(shè)要考慮兩個(gè)優(yōu)先因子相同的目標(biāo)的區(qū)別,那么可通過賦予它們不同的權(quán)系數(shù)wj來完成.3)目標(biāo)規(guī)劃模型的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)是根據(jù)各目標(biāo)約束的正、負(fù)偏差變量d、d和其優(yōu)先因子來構(gòu)造的,一般而言,當(dāng)每一目標(biāo)值確定后,我們總要求盡可能地縮小與目標(biāo)值的偏差,故目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是minzf(d

4、,d)的形式.我們可將其分為以下三種情形：(1)當(dāng)決策值xi(i1,2,n)要求恰好等于規(guī)定的目標(biāo)值時(shí),這時(shí)正、負(fù)偏差變量 d、d 都要盡可能小,即對應(yīng)的目標(biāo)函數(shù)為：minzf(dd)；(2)當(dāng)決策值xi(i1,2,n)要求不超過規(guī)定的目標(biāo)值時(shí),這時(shí)正偏差變量d要盡可能小,即對應(yīng)的目標(biāo)函數(shù)為：minzf(d)；(3)當(dāng)決策值xi(i1,2,n)要求超過規(guī)定的目標(biāo)值時(shí),這時(shí)負(fù)偏差變量 d 要盡可能小,即對應(yīng)的目標(biāo)函數(shù)為：minzf(d).目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式為：有了以上的討論,在例1中,設(shè)“,x2分別表示產(chǎn)品A、B的生產(chǎn)數(shù)量,或表示生產(chǎn)能力閑置的時(shí)間,屆表示加班時(shí)間,d2表示產(chǎn)品A沒能到達(dá)

5、銷售目標(biāo)的數(shù)目,d3表示產(chǎn)品B沒能到達(dá)銷售目標(biāo)的數(shù)目.因要求盡量防止生產(chǎn)水平閑置及盡量減少加班時(shí)間,故有目標(biāo)約束條件為：x1x2d1d1500(d1、d1要盡可能小),又要求盡可能多地賣出產(chǎn)品,故有目標(biāo)約束條件為：x1d2300,x2d3400(d2、d3要盡可能小),多賣出A產(chǎn)品的要求可表達(dá)在目標(biāo)函數(shù)的權(quán)系數(shù)中,于是可得到例1的目標(biāo)規(guī)劃模型為：滿足的約束條件為：2應(yīng)用實(shí)例例1.職工的調(diào)資方案問題1)問題的提出某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時(shí),要求相關(guān)部門遵守以下的規(guī)定：(1)年工資總額不超過60000元；(2)每級的人數(shù)不超過定編規(guī)定的人數(shù)；(3)口、山級的升級面盡可能到達(dá)現(xiàn)有人數(shù)

6、的20%;(4)山級缺乏編制的人數(shù)可錄用新職工,又I級的職工中有10%的人要退休相關(guān)資料匯總于下表中,試為單位領(lǐng)導(dǎo)擬定一個(gè)滿足要求的調(diào)資方案.等級 二資額(元/現(xiàn)有人數(shù)編制人數(shù)I20001012n15001215m10001515合計(jì)37422)模型分析與變量假設(shè)顯然這是一個(gè)多目標(biāo)規(guī)劃的決策問題,適于用目標(biāo)規(guī)劃模型求解,故需要確定該問題與之對應(yīng)的決策變量、目標(biāo)值、優(yōu)先等級及權(quán)系數(shù)等.設(shè)為、x2、X3分別表示提升到I、n級和錄用到山級的新職工人數(shù),由題設(shè)要求可確定各目標(biāo)的優(yōu)先因子為：P年工資總額不超過60000元；P2每級的人數(shù)不超過定編規(guī)定的人數(shù)；P3“、山級的升級面盡可能到達(dá)現(xiàn)有人數(shù)的20%

7、;下面再確定目標(biāo)約束,因要求年工資總額不超過60000元,所以有：2000(10-10X10%+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1d160000且正偏差變量 d1要盡可能小,又第二目標(biāo)要求每級的人數(shù)不超過定編規(guī)定的人數(shù),所以,對I級有：10(10)x1d2d212,且正偏差變量 d2要盡可能小；對 n 級有：12x1x2d3d315,且正偏差變量 d3要盡可能??；對山級有：15x2x3d4d415,且正偏差變量 d4要盡可能小；對第三目標(biāo)一一口、山級的升級面盡可能到達(dá)現(xiàn)有人數(shù)的20%,我們有：x1d5d51220%,且負(fù)偏差變量 d5要盡可能小；變量含義解

8、1解2解3解4晉升到I級的人數(shù)2.42.433晉升到n級的人數(shù)3335晉升到山級的人數(shù)0335工資總額的節(jié)余數(shù)6300330030000I級缺編人數(shù)0.60.600n級缺編人數(shù)2.42.431山級缺編人數(shù)300.60n級超編人數(shù)0000.6山級超編人數(shù)0002例2.物資的調(diào)運(yùn)安排問題1問題的提出有一供需不平衡供給量需求量的物資調(diào)運(yùn)問題如下表所示：請為其制訂物資調(diào)運(yùn)方案,使之滿足以下的目標(biāo)要求：P盡量保證?f足重點(diǎn)客戶 B3的需求指標(biāo)；P2要求總運(yùn)費(fèi)不超過預(yù)算指標(biāo)66104元；P3至少?f足客戶 B1,B2,B3需求指標(biāo)的80%;X2d6d61520%,6要盡可能小;且負(fù)偏差變量d3模型的建立由

9、此,我們可得到該問題的目標(biāo)規(guī)劃模型為：滿足約束條件求解后可得到該問題的一個(gè)多重解,并將這些解匯總于下表中,以供領(lǐng)導(dǎo)根據(jù)具體情況進(jìn)行決策：P4由A3至B1的運(yùn)輸量按合同規(guī)定不少于1萬噸;P5A1至B3的道路危險(xiǎn),運(yùn)量要減少到最低點(diǎn).W 價(jià)B1B2B3供給量(萬噸)A1C11C12C135A2C21C22C238A3C31C32C337需求量(萬噸)86102)模型分析與變量假設(shè)這仍然是一個(gè)多目標(biāo)決策規(guī)劃問題,雖然未給出給出倉庫到客戶之間的單位運(yùn)價(jià),但這并不影響我們的分析與建模.設(shè)從倉庫A(i1,2,3)調(diào)撥到客戶Bj(j1,2,3)的貨運(yùn)量為xij,因該問題的供給量小于需求量,故從倉庫Ai(i1

10、23)調(diào)撥到客戶Bj的貨運(yùn)量X1jX2jX3j(j的需求量,因此,di0,di0(i1,2,3),于是有:又目標(biāo)P1為：盡量保證滿足重點(diǎn)客戶 B3的需求指標(biāo),故有:x13X23x33d4d410且 d4,d4都要盡可能??；對目標(biāo)巳：因要求總運(yùn)費(fèi)不超過預(yù)算指標(biāo) 66104元,故有：334Cjxijd5d56610i1j1且 d5應(yīng)盡可能小；對目標(biāo)P3:因要求至少滿足客戶 B1,B2,B3需求指標(biāo)的80%,故有:XIIX21X31d6d68 80%X12X22X32d7d76 80%X13X23X33d8d810 80%且 di(i6,7,8)應(yīng)盡可能小;1,2不可能超過所要求對目標(biāo)P4因要求由A3至B1的運(yùn)輸量按合同規(guī)定不少于1萬噸,故有:x31d9d91,且d9應(yīng)盡可能小；對目標(biāo)P5因A至B3