1、運籌學(xué)目標(biāo)規(guī)劃OR21第1頁，共30頁，2022年，5月20日，18點42分，星期三OR22第五章 目標(biāo)規(guī)劃要求1、理解概念2、掌握建模3、掌握圖解法和單純形解法4、理解目標(biāo)規(guī)劃的靈敏度分析第2頁，共30頁，2022年，5月20日，18點42分，星期三OR235.1目標(biāo)規(guī)劃的概念及數(shù)學(xué)模型1多目標(biāo)問題多目標(biāo)線性規(guī)劃例1 產(chǎn)品資源 A B限量原材料（kg)設(shè)備（臺時） 2 1 1 2 11 10單位利潤 8 10求利潤最大的生產(chǎn)方案。第3頁，共30頁，2022年，5月20日，18點42分，星期三OR24例2：例1的要求多元化：決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上： 1、首先是產(chǎn)品A的產(chǎn)量不大于產(chǎn)

2、品B的產(chǎn)量。 2、其次是充分利用設(shè)備的有效臺時，不加班。 3、再次是使利潤額盡可能達(dá)到并超過計劃利潤指標(biāo)56元。此問題即為多目標(biāo)決策問題，目標(biāo)規(guī)劃就是解這類問題的方法。 A B限量原材料（kg)設(shè)備（臺時） 2 1 1 2 11 10單位利潤 8 10minZ=P1 d1+ +P2 (d2-+ d2+) +P3 d3-第4頁，共30頁，2022年，5月20日，18點42分，星期三OR25例2的解法解：問題分析：找差別、定概念（與單目標(biāo)規(guī)劃相比） 1）絕對約束：必須嚴(yán)格滿足的等式約束和不等式約束，稱之為絕對約束。 2x1+1.5x250 (1) x1+ 2x2 40 (2) 2）目標(biāo)約束：那些不

3、必嚴(yán)格滿足的等式約束和不等式約束，稱之為目標(biāo)約束（軟約束）。目標(biāo)約束是目標(biāo)規(guī)劃特有的，這些約束不一定要求嚴(yán)格完全滿足，允許發(fā)生正或負(fù)偏差，因此在這些約束中可以加入正負(fù)偏差變量。第5頁，共30頁，2022年，5月20日，18點42分，星期三OR263）偏差變量：目標(biāo)約束不是剛性的，而是彈性的，允許在一定范圍內(nèi)有偏差，這更接近于實際。為表達(dá)這種靈活性，便引入了偏差變量的概念，偏差變量有正負(fù)之分，正偏差變量表示為：d+， d+表示超過目標(biāo)值的部分；負(fù)偏差變量表示為： d-， d-表示不足目標(biāo)值的部分.顯然有d- d+=0（？）第6頁，共30頁，2022年，5月20日，18點42分，星期三OR274）

4、目標(biāo)（期望）值：是指預(yù)先給定的某個目標(biāo)的期望值。5）實際值：是指當(dāng)決策變量選定以后，目標(biāo)函數(shù)的對應(yīng)值。顯然： d+實際值目標(biāo)值0 d-目標(biāo)值實際值 0盡可能達(dá)到并超過計劃利潤指標(biāo)56元，此處的56元即為目標(biāo)值第7頁，共30頁，2022年，5月20日，18點42分，星期三OR286）目標(biāo)函數(shù)的優(yōu)先級與權(quán)系數(shù):目標(biāo)的重要程度不同，因此目標(biāo)的滿足有先有后，即有優(yōu)先級別。設(shè)最重要的為P1級，次之者為P2級 P看成實數(shù) ，且有 P1P2注：目標(biāo)的優(yōu)先級是一個定性概念，不同的優(yōu)先級之間無法用數(shù)量衡量，僅僅表示優(yōu)化過程中的目標(biāo)考慮的先后次序。對于同一優(yōu)先級的不同目標(biāo)，按其重要程度可分別賦予不同的權(quán)系數(shù)。權(quán)系

5、數(shù)是一種可以用數(shù)量表示的指數(shù)，因此，對于一個具體的目標(biāo)規(guī)劃問題，它是一個數(shù)字。第8頁，共30頁，2022年，5月20日，18點42分，星期三OR297）目標(biāo)規(guī)劃的目標(biāo)函數(shù)： 目標(biāo)規(guī)劃的目標(biāo)函數(shù)是按各約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。目標(biāo)函數(shù)的基本形式有三種：1、要求恰好達(dá)到目標(biāo)值，即正負(fù)偏差變量都要盡可能地小，這時， minZf(d+d-).2、要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值但正偏差變量要盡可能地小，這時， minZf(d+).3、要求超過目標(biāo)值，即超過量不限但負(fù)偏差變量要盡可能的小，這時， minZf(d-) 顯然，本題目標(biāo)函數(shù)表示為：minZ=P1 d1+ +P2 (

6、d2-+ d2+) +P3 d3- 第9頁，共30頁，2022年，5月20日，18點42分，星期三OR210綜上所述，本題的數(shù)學(xué)模型為： minZ=P1 d1+ +P2 (d2-+ d2+) +P3 d3- 2x1+x2 11 x1 - x2+ d1- -d1+=0 x1+2x2+ d2- -d2+ =10 8x1 + 10 x2+ d3- -d3+ =56 x1 ，x2 ，di-，di+ 0 ,i=1,2,3第10頁，共30頁，2022年，5月20日，18點42分，星期三OR211幾點說明：1）有時絕對約束轉(zhuǎn)化為目標(biāo)約束，則不再表示為絕對約束。2）有時同級別的目標(biāo)中，其重要程度又有差別，則設(shè)

7、置不同的權(quán)重。第11頁，共30頁，2022年，5月20日，18點42分，星期三OR212目標(biāo)規(guī)劃問題的特點：1）問題的目標(biāo)函數(shù)是關(guān)于優(yōu)先等級、權(quán)系數(shù)和偏差變量的極小化函數(shù)；2）約束條件由絕對約束或目標(biāo)約束構(gòu)成；3）所有決策變量和偏差變量都受到非負(fù)約束。第12頁，共30頁，2022年，5月20日，18點42分，星期三OR213例3：請建立以下問題的數(shù)學(xué)模型某建筑施工單位計劃生產(chǎn)A,B兩種預(yù)制構(gòu)件。決策者首先考慮要充分利用供電部門分配的電量限額指標(biāo)62.5kw/日，其次考慮完成與超額完成利潤指標(biāo)10百元/日。每日可供給予制水泥8噸。其它有關(guān)數(shù)據(jù)如下表，問應(yīng)如何確定A,B的產(chǎn)量。產(chǎn)品耗電量(kw/產(chǎn)

8、品）水泥消耗（噸/產(chǎn)品）利潤（百元/產(chǎn)品）A1021B1212第13頁，共30頁，2022年，5月20日，18點42分，星期三OR214課堂練習(xí)：某工廠生產(chǎn)A、B兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下：要求：首先、B產(chǎn)品不超過10單位；其次，利潤不低于1600元，再次，充分利用2車間的生產(chǎn)能力，盡量不加班。請建立該問題的模型。 產(chǎn)品資源 A B限量1車間2車間 2 1.5 1 25040單位利潤 80 100第14頁，共30頁，2022年，5月20日，18點42分，星期三OR215圖解法的基本步驟：（1）先作硬約束與決策變量的非負(fù)約束，同一般線性規(guī)劃作圖法。（2）作目標(biāo)約束，此時，先讓di- -di+0，

9、然后標(biāo)出di- 及di+的增加方向（實際上是目標(biāo)值減少與增加的方向）。（3）按優(yōu)先級的次序，逐級讓目標(biāo)規(guī)劃的目標(biāo)函數(shù)中極小化偏差變量取0，從而逐步縮小可行域，最后找出問題的解。5.2目標(biāo)規(guī)劃的圖解法第15頁，共30頁，2022年，5月20日，18點42分，星期三OR2165.2目標(biāo)規(guī)劃的圖解法圖解例2:minZ=P1 d1+ +P2 (d2-+ d2+) +P3 d3- 2x1+x2 11 x1 - x2+ d1- -d1+=0 x1+2x2+ d2- -d2+ =10 8x1 + 10 x2+ d3- -d3+ =56 x1 ，x2 ，di-，di+ 0 ,i=1,2,3第16頁，共30頁，

10、2022年，5月20日，18點42分，星期三OR217例4：第17頁，共30頁，2022年，5月20日，18點42分，星期三OR218考慮目標(biāo)規(guī)劃數(shù)學(xué)模型的一些特點，作以下規(guī)定：1）因目標(biāo)函數(shù)為求最小化，所以要求2）因非基變量檢驗數(shù)中含有不同等級的優(yōu)先因子，即 ，因p1p2pk；從每個檢驗數(shù)的整體看：檢驗數(shù)的正、負(fù)首先決定于p1的系數(shù)a1j的正負(fù)，若a1j0， 則此檢驗數(shù)的正、負(fù)就決定于p2的系數(shù)a2j的正負(fù)，依次類推。5.3 目標(biāo)規(guī)劃的單純形解法第18頁，共30頁，2022年，5月20日，18點42分，星期三OR2193)目標(biāo)規(guī)劃使用單純形法求解， di-，di+ 視為普通變量。P1P2 P

11、L第19頁，共30頁，2022年，5月20日，18點42分，星期三OR220求解目標(biāo)規(guī)劃單純形法的步驟：P1051、建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行，置k=1。2、檢查該行中是否存在負(fù)數(shù)，且對應(yīng)的前k1行的系數(shù)是零。若有負(fù)數(shù)，取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)（3），若無負(fù)數(shù)，則轉(zhuǎn)（5）。3、按最小比值規(guī)則確定換出變量，當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。4、按單純形法進(jìn)行基變換運算，建立新的計算表，返回（2）。5、當(dāng)k= K時，計算結(jié)束。表中的解即為滿意解。否則置k= k 1，返回到（2）。第20頁，共30頁，2022年，

12、5月20日，18點42分，星期三OR221例題5:用單純形法求解下列目標(biāo)規(guī)劃問題 minZ=P1 d1+ +P2 (d2-+ d2+) +P3 d3- 2x1+x2 11 x1 - x2+ d1- -d1+=0 x1+2x2+ d2- -d2+ =10 8x1 + 10 x2+ d3- -d3+ =56 x1 ，x2 ，di-，di+ 0 ,i=1,2,3第21頁，共30頁，2022年，5月20日，18點42分，星期三OR2225.5 目標(biāo)規(guī)劃的靈敏度分析例5：已知目標(biāo)規(guī)劃問題：目標(biāo)函數(shù)的等級變化為：試分析原解有什么變化？第22頁，共30頁，2022年，5月20日，18點42分，星期三OR22

13、3CBXBbx1x22p13p1p2p3x2X1641820100100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3解:原問題的最優(yōu)單純形表為：第23頁，共30頁，2022年，5月20日，18點42分，星期三OR224問題1的變化情況為：第24頁，共30頁，2022年，5月20日，18點42分，星期三OR225CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-100001000-100P200

14、000000302-300203-20000010000001P1P2p3p2p3000此時，檢驗數(shù)大于等于零，可見，原解仍是滿意解。p3003203002302001010第25頁，共30頁，2022年，5月20日，18點42分，星期三OR226CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3p12p23p2p1-320300200-230100p1級的檢驗數(shù)不是大于等于零，則p1級目標(biāo)未實現(xiàn)，繼續(xù)迭代。

15、過程見書第108頁。第26頁，共30頁，2022年，5月20日，18點42分，星期三OR227某單位考慮職工的升級調(diào)資方案時，依次遵守得規(guī)定：1、不超過年工資總額60000元；2、每級的人數(shù)不超過定編規(guī)定的人數(shù)；3、二、三級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20，且無越級提升；4、三級不足編制的人數(shù)可錄用新職工，又一級的職工中有10要退休。有關(guān)資料如下，問應(yīng)如何擬定一個滿意的方案。等級工資額（元/年）現(xiàn)有人數(shù)編制人數(shù)123200015001000101215121515合計3742第27頁，共30頁，2022年，5月20日，18點42分，星期三OR228已知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之

16、間地供需量和單位運費見下表，有關(guān)部門在研究調(diào)運方案時依次考慮以下七項目標(biāo)，并規(guī)定其相應(yīng)地優(yōu)先等級：P1：B4是重點保證單位，必須全部滿足其需要；P2：A3向B1提供地產(chǎn)量不少于100；P3：每個銷地地供應(yīng)量不小于其需求量地80；P4：所定調(diào)運方案的總運費不超過最小運費調(diào)運方案的10。P5：因路段的問題，盡量避免安排將A2的產(chǎn)品往B4；P6：給B1和B3的供應(yīng)率要相同；P7：力求總運費最省。試求滿意的調(diào)運方案。 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3534255642763300200400銷量200100450250900/1000其它條件不考慮，用表上作業(yè)法得最小運費為2950。第28頁，共30頁，2022年，5月20日，18點42分，星期三OR229習(xí)題： 某工廠計劃期內(nèi)要安排生產(chǎn)A,B兩種產(chǎn)品。