第6章-目標(biāo)規(guī)劃-管理運籌學(xué)-

1、第6章 目標(biāo)規(guī)劃目錄4目標(biāo)規(guī)劃數(shù)學(xué)模型123目標(biāo)規(guī)劃基本解法目標(biāo)規(guī)劃應(yīng)用舉例本章小結(jié)與作業(yè)管理運籌學(xué) 第6章 目標(biāo)規(guī)劃6.1 目標(biāo)規(guī)劃的數(shù)學(xué)模型管理運籌學(xué) 第6章 目標(biāo)規(guī)劃引例與問題的提出目標(biāo)規(guī)劃的基本概念目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的建模步驟導(dǎo)入案例產(chǎn)品組合問題管理運籌學(xué) 第6章 目標(biāo)規(guī)劃現(xiàn)增加如下考慮：（1）力求使利潤指標(biāo)不低于15元；（2）據(jù)市場預(yù)測，I、II兩種產(chǎn)品需求量的比例大致是1:2；（3）A為貴重設(shè)備，嚴(yán)格禁止超時使用；（4）設(shè)備C可以適當(dāng)加班，但要控制；設(shè)備B既要求充分利用，又盡可能不加班，在重要性上設(shè)備B是C的3倍。綜合考慮上述因素，企業(yè)應(yīng)如何決策？這里本章所要討論的問題。產(chǎn)

2、品I產(chǎn)品II可用臺時設(shè)備A設(shè)備B設(shè)備C240205121615單位利潤23最優(yōu)解：x1=3x2=3z=15若僅考慮利潤目標(biāo)，其LP模型為：目標(biāo)規(guī)劃的正式提出目標(biāo)規(guī)劃（Goal Programming）:是針對線性規(guī)劃目標(biāo)單一的局限性而提出的，是線性規(guī)劃的應(yīng)用拓展，是解決實際問題的一種方法。線性規(guī)劃是研究資源有效分配和利用，其特點是在滿足一組約束條件的情況下，尋求某一個目標(biāo)的最大值或最小值。而在現(xiàn)實社會中，經(jīng)常遇到需要考慮多個目標(biāo)的優(yōu)化問題。目標(biāo)規(guī)劃與傳統(tǒng)方法不同，它強(qiáng)調(diào)了系統(tǒng)性，其方法在于尋找一個“盡可能”滿足所有目標(biāo)的解，而不是絕對滿足這些目標(biāo)的值。目標(biāo)規(guī)劃有著極大的靈活性，表現(xiàn)在它可以模擬

3、系統(tǒng)的約束和目標(biāo)優(yōu)先等級變化的各種模型，為管理決策提供眾多的信息。解決目標(biāo)規(guī)劃問題首先要根據(jù)目標(biāo)的重要性分清主次先后、輕重緩急，引入偏差變量，將目標(biāo)按等級轉(zhuǎn)化為目標(biāo)約束，最終形成可用線性規(guī)劃方法解決的問題。 管理運籌學(xué) 第6章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃的正式提出多目標(biāo)最優(yōu)化問題最早是由意大利經(jīng)濟(jì)學(xué)家L.帕雷托在1896年提出來的，他把許多本質(zhì)上是不可比較的目標(biāo)化成一個單一的最優(yōu)化目標(biāo)。1944年J.von諾伊曼和O.莫根施特恩又從對策論角度提出具有多個決策者并相互矛盾的多目標(biāo)決策問題。1951年T.C.考普曼從生產(chǎn)和分配活動分析中提出多目標(biāo)最優(yōu)化問題，并引入了帕雷托最優(yōu)的概念。1961年美國學(xué)者查納斯

4、（A.Charnes）和庫伯（W.W.Cooper）在他們合著的管理模型和線性規(guī)劃的工業(yè)應(yīng)用一書中正式提出目標(biāo)規(guī)劃，以后這種模型經(jīng)U杰斯基萊恩和Sang李不斷完善改進(jìn)，并給出了求解目標(biāo)規(guī)劃的一般方法單純形法。管理運籌學(xué) 第6章 目標(biāo)規(guī)劃6.1.1 基本概念管理運籌學(xué) 第6章 目標(biāo)規(guī)劃1.偏差變量用以表明實際值與超出或未達(dá)到目標(biāo)值的差距，用下列符號表示：d+超出目標(biāo)的差距，稱正偏差變量d-未達(dá)到目標(biāo)的差距，稱負(fù)偏差變量第一，當(dāng)實際值超出規(guī)定目標(biāo)時d-=0,d+0；第二，當(dāng)實際值未達(dá)到規(guī)定目標(biāo)時d-0,d+=0； 第三，實際值與目標(biāo)值剛好一致時d-=d+=0。故恒有d-d+=0；2.系統(tǒng)約束系統(tǒng)約

5、束指某種資源的使用上受到嚴(yán)格限制。這種限制如同在線性規(guī)劃中的約束一樣，不允許有絲毫超差，故稱為剛性約束。3.目標(biāo)約束與目標(biāo)要求目標(biāo)規(guī)劃處理問題的方法是將多目標(biāo)轉(zhuǎn)化為多個目標(biāo)約束。如目標(biāo)利潤的約束：甲產(chǎn)品單位利潤2元乙產(chǎn)品單位利潤3元，目標(biāo)要求利潤不小于15元，即有目標(biāo)約束不等式：2x1+3x215添加正負(fù)偏差變量，將其變?yōu)榈仁剑?x1+3x2+d-1-d+1=15當(dāng)d-1=0,d+10時，表明2x1+3x215，達(dá)到了目標(biāo)；當(dāng)d-10,d+1=0時，表明2x1+3x2Pk+1。5.權(quán)系數(shù)在同一優(yōu)先級內(nèi)，根據(jù)重要程度不同，用權(quán)系數(shù)確定其優(yōu)先順序。權(quán)系數(shù)是一個具體的數(shù)字，通常以“罰款額”、“損失額

6、”作為權(quán)系數(shù)，對重大的戰(zhàn)略性問題，應(yīng)采取“專家意見法”進(jìn)行綜合評價.設(shè)：P1:目標(biāo)利潤；P2:產(chǎn)品比例；P3:設(shè)備B的利用與加班，設(shè)備C的加班。在P3中設(shè)備B的重要性為C的3倍，則目標(biāo)函數(shù)為：6.1.1 基本概念管理運籌學(xué) 第6章 目標(biāo)規(guī)劃6.1.2 目標(biāo)規(guī)劃的數(shù)學(xué)模型將上述目標(biāo)規(guī)劃的目標(biāo)約束、目標(biāo)函數(shù)再加上系統(tǒng)約束和變量非負(fù)約束，即構(gòu)成了引例中的目標(biāo)規(guī)劃數(shù)學(xué)模型如下：管理運籌學(xué) 第6章 目標(biāo)規(guī)劃6.1.2 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式：管理運籌學(xué) 第6章 目標(biāo)規(guī)劃 優(yōu)先因子正偏差權(quán)系數(shù)負(fù)偏差權(quán)系數(shù)目標(biāo)約束系統(tǒng)約束變量非負(fù)目標(biāo)規(guī)劃建模步驟根據(jù)背景材料列出全部約束不等式目標(biāo)約束系

7、統(tǒng)約束xj 0d0“”mind-“”mind+“=”mind-+d+左端+ dd+=右端確定優(yōu)先級和權(quán)系數(shù),構(gòu)造目標(biāo)偏差最小的目標(biāo)函數(shù)約束條件目標(biāo)規(guī)劃數(shù)學(xué)模型管理運籌學(xué) 第6章 目標(biāo)規(guī)劃例6-1管理運籌學(xué) 第6章 目標(biāo)規(guī)劃已知某實際問題的線性規(guī)劃模型為：假定重新確定這個問題的目標(biāo)為：P1：z的值應(yīng)不低于1900；P2：資源1盡可能全部利用。將此問題轉(zhuǎn)換為目標(biāo)規(guī)劃問題，列出數(shù)學(xué)模型。 P1：第4用戶需求量全部滿足；P2：每用戶滿足率80%；P3：總運費原方案的110%；P4：從工廠2到用戶4的路線應(yīng)盡量避免分配運輸任務(wù).例6-2管理運籌學(xué) 第6章 目標(biāo)規(guī)劃1234生產(chǎn)量1235342556427

8、63300200400需求量200100450250設(shè)：xij產(chǎn)地i到銷地j運送量，原方案最優(yōu)值：2950例6-2管理運籌學(xué) 第6章 目標(biāo)規(guī)劃6.2 目標(biāo)規(guī)劃的基本解法管理運籌學(xué) 第6章 目標(biāo)規(guī)劃求解流程圖解法單純形法序貫算法目標(biāo)規(guī)劃求解流程管理運籌學(xué) 第6章 目標(biāo)規(guī)劃用目標(biāo)規(guī)劃處理問題的難點在于構(gòu)造模型時需要事先確定優(yōu)先級和權(quán)系數(shù)。而這些信息往往來自人們的主觀判斷，很難給出一個絕對的數(shù)值。通常根據(jù)求解結(jié)果的各項目標(biāo)滿意程度來修改優(yōu)先級和權(quán)系數(shù)，直至滿意為止。其流程如右圖。明確問題，列出（或修改）目標(biāo)的優(yōu)先級和權(quán)系數(shù)no構(gòu)造目標(biāo)規(guī)劃模型求出滿意解分析各項目標(biāo)完成情況據(jù)此制訂決策方案滿意否？ye

9、s6.2.1 圖解法管理運籌學(xué) 第6章 目標(biāo)規(guī)劃x1x2o662x1+2x2=122x1+3x2=157.552x1-x2=04x1=165x2=15（1）繪出直角坐標(biāo)（2）圖示系統(tǒng)約束，確定可行域（3）按優(yōu)先級高低，依次圖示目標(biāo)約束，縮小滿意解范圍。6.2.2 單純形法管理運籌學(xué) 第6章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃與線性規(guī)劃初始單純形表的不同（1）由于目標(biāo)函數(shù)均為最小，為方便起見，不轉(zhuǎn)換為極大；（2）以系統(tǒng)約束的松馳變量、人工變量、目標(biāo)約束的負(fù)偏差變量為初始基變量；（3）檢驗數(shù)行按優(yōu)先因子分別列出。目標(biāo)規(guī)劃與線性規(guī)劃計算檢驗數(shù)的不同（1）從第一級優(yōu)級開始，若檢驗數(shù)存在負(fù)數(shù)，最小檢驗數(shù)所對應(yīng)的變量為換入

10、變量。當(dāng)高級優(yōu)先級得到優(yōu)化，轉(zhuǎn)向下一級；（2）在第k優(yōu)先級優(yōu)化過程中，如果破壞了上級優(yōu)化結(jié)果，則迭代停止，k-1以上級目標(biāo)得到優(yōu)化，k級以下未得到優(yōu)化，所得結(jié)果為滿意解；（3）若所有檢驗數(shù)均非負(fù)，所有目標(biāo)均得到優(yōu)化，所得結(jié)果可稱為最優(yōu)解?！纠?.4】用單純形法求目標(biāo)規(guī)劃滿意解滿意解：x1=0,x2=40目標(biāo)完成情況：目標(biāo)1產(chǎn)生30個單位的正偏差，其余均無偏差。單純形法例題管理運籌學(xué) 第6章 目標(biāo)規(guī)劃6.2.3 序貫算法序貫是數(shù)理統(tǒng)計學(xué)的一個分支，源于A瓦爾德在1947年發(fā)表的一本同名著作，研究的對象是所謂“序貫抽樣方案”，其基本思想是：先抽少量樣本，根據(jù)結(jié)果再決定繼續(xù)抽樣，直到?jīng)Q定停止為止。

11、依據(jù)這一思想，先考慮只有系統(tǒng)約束和最高優(yōu)先級的目標(biāo)約束，目標(biāo)函數(shù)中的優(yōu)先因子取“1”，求得其目標(biāo)要求的偏差變量的值，將其固定，再按優(yōu)先次序逐級添加目標(biāo)約束并進(jìn)行優(yōu)化，直到全部目標(biāo)優(yōu)化完畢為止。管理運籌學(xué) 第6章 目標(biāo)規(guī)劃【例6.5】用序貫算法求解目標(biāo)規(guī)劃問題管理運籌學(xué) 第6章 目標(biāo)規(guī)劃6.3 目標(biāo)規(guī)劃應(yīng)用舉例管理運籌學(xué) 第6章 目標(biāo)規(guī)劃Burnit 公司廣告策劃產(chǎn)品決策問題 Fruit公司芯片購買決策Burnit公司準(zhǔn)備通過電視媒體做廣告,在“足球”和“肥皂劇”中插播，相關(guān)資料如右表。表中：HIM高收入男士;LIP低收入人群;HIW高收入女士6.3.1 Burnit公司廣告策劃管理運籌學(xué) 第6

12、章 目標(biāo)規(guī)劃廣告預(yù)期觀眾數(shù)(百萬)費用(萬美元)HIMLIPHIW足球肥皂劇7310554106目標(biāo)40603560單位損失20105解 設(shè)：x1:足球期間插播廣告時間, x2:肥皂劇插播廣告時間HIM目標(biāo)約束LIP目標(biāo)約束HIW目標(biāo)約束預(yù)算限制綜上所述：6.3.1 Burnit公司廣告策劃管理運籌學(xué) 第6章 目標(biāo)規(guī)劃6.3.2 產(chǎn)品決策問題 管理運籌學(xué) 第6章 目標(biāo)規(guī)劃數(shù)據(jù)/萬件目標(biāo)權(quán)數(shù)IIIIII長期利潤（百萬元）雇用水平（百人）資本投資（百萬元）12559371548125=40555(-)2(+),4(-)3(+)解 設(shè)：x1:產(chǎn)品I產(chǎn)量；x2:產(chǎn)品II產(chǎn)量；x3:產(chǎn)品III產(chǎn)量長期利

13、潤雇用水平資本投資綜上所述：優(yōu)化結(jié)果：產(chǎn)品I生產(chǎn)8.33，產(chǎn)品III生產(chǎn)1.67，目標(biāo)1和目標(biāo)3均得到滿足，但目標(biāo)2超出833人。對此人事部門認(rèn)為：超員是短期行為，將產(chǎn)生嚴(yán)重后果；財務(wù)部門認(rèn)為：5500萬投資也不能突破，故采取帶優(yōu)先權(quán)的目標(biāo)規(guī)劃，對員工雇用和投資給一個高優(yōu)先權(quán)。優(yōu)化結(jié)果：x1=5,x3=3.75目標(biāo)達(dá)成情況：d1_=8.75，其余=06.3.2 產(chǎn)品決策問題 管理運籌學(xué) 第6章 目標(biāo)規(guī)劃6.3.3 Fruit公司芯片購買決策 管理運籌學(xué) 第6章 目標(biāo)規(guī)劃供應(yīng)商一套（100個）芯片每套價格（美元）優(yōu)等良好級中等123605040203520201540400300250單個購價需

14、求量1050006300041000問題：1.超預(yù)算1美元，1美元罰款；2.預(yù)算、優(yōu)等、良好級、中等分屬4個優(yōu)先級。設(shè)：x1,x2,x3為從供應(yīng)商1、2、3購買的套數(shù)； x4,x5,x6單獨購買優(yōu)、良、中芯片的個數(shù)問題1：系統(tǒng)約束目標(biāo)約束約束轉(zhuǎn)換數(shù)學(xué)模型：優(yōu)化結(jié)果：6.3.3 Fruit公司芯片購買決策 管理運籌學(xué) 第6章 目標(biāo)規(guī)劃6.3.3 Fruit公司芯片購買決策 管理運籌學(xué) 第6章 目標(biāo)規(guī)劃供應(yīng)商一套（100個）芯片每套價格（美元）優(yōu)等良好級中等123605040203520201540400300250單個購價需求量1050006300041000問題2：預(yù)算、優(yōu)等、良好級、中等分屬4個優(yōu)先級。優(yōu)化結(jié)果：x2=93x4=10d2_=340d3=255d4=395其余=0本章小結(jié)1.概念：目標(biāo)規(guī)劃是對多目標(biāo)或相互矛盾的多重目標(biāo)進(jìn)行擇優(yōu)的一種方法。它是線性規(guī)劃的應(yīng)用拓展，它強(qiáng)調(diào)了系統(tǒng)性，是解決實際問題的一種有效方法。2.建模步驟1)根據(jù)背景材料列出所有約束不等式；2)對目標(biāo)約束不等式左端加