運籌學(xué)——目標(biāo)規(guī)劃ppt課件

1、OPERATIONS RESEARCH 運籌學(xué)徐 玲第五章 目的規(guī)劃要求1、了解概念2、掌握建模3、掌握圖解法和單純形解法4、了解目的規(guī)劃的靈敏度分析5.1目的規(guī)劃的概念及數(shù)學(xué)模型1多目的問題多目的線性規(guī)劃例1 產(chǎn)品資源 A B限量原材料（kg)設(shè)備（臺時） 2 1 1 2 11 10單位利潤 8 10求利潤最大的消費方案。例2：例1的要求多元化：決策者在原資料供應(yīng)受嚴(yán)厲限制的根底上： 1、首先是產(chǎn)品A的產(chǎn)量不大于產(chǎn)品B的產(chǎn)量。 2、其次是充分利用設(shè)備的有效臺時，不加班。 3、再次是使利潤額盡能夠到達(dá)并超越方案利潤目的56元。此問題即為多目的決策問題，目的規(guī)劃就是解這類問題的方法。 A B限量

2、原材料（kg)設(shè)備（臺時） 2 1 1 2 11 10單位利潤 8 10minZ=P1 d1+ +P2 (d2-+ d2+) +P3 d3-例2的解法解：問題分析：找差別、定概念與單目的規(guī)劃相比 1絕對約束：必需嚴(yán)厲滿足的等式約束和不等式約束，稱之為絕對約束。 2x1+1.5x250 (1) x1+ 2x2 40 (2) 2目的約束：那些不用嚴(yán)厲滿足的等式約束和不等式約束，稱之為目的約束軟約束。目的約束是目的規(guī)劃特有的，這些約束不一定要求嚴(yán)厲完全滿足，允許發(fā)生正或負(fù)偏向，因此在這些約束中可以參與正負(fù)偏向變量。3偏向變量：目的約束不是剛性的，而是彈性的，允許在一定范圍內(nèi)有偏向，這更接近于實踐。為

3、表達(dá)這種靈敏性，便引入了偏向變量的概念，偏向變量有正負(fù)之分，正偏向變量表示為：d+， d+表示超越目的值的部分；負(fù)偏向變量表示為： d-， d-表示缺乏目的值的部分.顯然有d- d+=0？4目的期望值：是指預(yù)先給定的某個目的的期望值。5實踐值：是指當(dāng)決策變量選定以后，目的函數(shù)的對應(yīng)值。顯然： d+實踐值目的值0 d-目的值實踐值 0盡能夠到達(dá)并超越方案利潤目的56元，此處的56元即為目的值6目的函數(shù)的優(yōu)先級與權(quán)系數(shù):目的的重要程度不同，因此目的的滿足有先有后，即有優(yōu)先級別。設(shè)最重要的為P1級，次之者為P2級 P看成實數(shù) ，且有 P1P2注：目的的優(yōu)先級是一個定性概念，不同的優(yōu)先級之間無法用數(shù)量

4、衡量，僅僅表示優(yōu)化過程中的目的思索的先后次序。對于同一優(yōu)先級的不同目的，按其重要程度可分別賦予不同的權(quán)系數(shù)。權(quán)系數(shù)是一種可以用數(shù)量表示的指數(shù)，因此，對于一個詳細(xì)的目的規(guī)劃問題，它是一個數(shù)字。7目的規(guī)劃的目的函數(shù)： 目的規(guī)劃的目的函數(shù)是按各約束的正、負(fù)偏向變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。目的函數(shù)的根本方式有三種：1、要求恰好到達(dá)目的值，即正負(fù)偏向變量都要盡能夠地小，這時， minZf(d+d-).2、要求不超越目的值，即允許達(dá)不到目的值但正偏向變量要盡能夠地小，這時， minZf(d+).3、要求超越目的值，即超越量不限但負(fù)偏向變量要盡能夠的小，這時， minZf(d-) 顯然，此標(biāo)題的函數(shù)表

5、示為：minZ=P1 d1+ +P2 (d2-+ d2+) +P3 d3- 綜上所述，此題的數(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幾點闡明：1有時絕對約束轉(zhuǎn)化為目的約束，那么不再表示為絕對約束。2有時同級別的目的中，其重要程度又有差別，那么設(shè)置不同的權(quán)重。目的規(guī)劃問題的特點：1問題的目的函數(shù)是關(guān)于優(yōu)先等級、權(quán)系數(shù)和偏向變量的極小化函數(shù)；2約束條件

6、由絕對約束或目的約束構(gòu)成；3一切決策變量和偏向變量都遭到非負(fù)約束。例3：請建立以下問題的數(shù)學(xué)模型某建筑施工單位方案消費A,B兩種預(yù)制構(gòu)件。決策者首先思索要充分利用供電部門分配的電量限額目的62.5kw/日，其次思索完成與超額完成利潤目的10百元/日。每日可供應(yīng)予制水泥8噸。其它有關(guān)數(shù)據(jù)如下表，問應(yīng)如何確定A,B的產(chǎn)量。產(chǎn)品耗電量(kw/產(chǎn)品）水泥消耗（噸/產(chǎn)品）利潤（百元/產(chǎn)品）A1021B1212課堂練習(xí)：某工廠消費A、B兩種產(chǎn)品，知有關(guān)數(shù)據(jù)如下：要求：首先、B產(chǎn)品不超越10單位；其次，利潤不低于1600元，再次，充分利用2車間的消費才干，盡量不加班。請建立該問題的模型。 產(chǎn)品資源 A B限

7、量1車間2車間 2 1.5 1 25040單位利潤 80 100圖解法的根本步驟：1先作硬約束與決策變量的非負(fù)約束，同普通線性規(guī)劃作圖法。2作目的約束，此時，先讓di- -di+0，然后標(biāo)出di- 及di+的添加方向?qū)嵺`上是目的值減少與添加的方向。3按優(yōu)先級的次序，逐級讓目的規(guī)劃的目的函數(shù)中極小化偏向變量取0，從而逐漸減少可行域，最后找出問題的解。5.2目的規(guī)劃的圖解法5.2目的規(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+

8、 d3- -d3+ =56 x1 ，x2 ，di-，di+ 0 ,i=1,2,3例4：思索目的規(guī)劃數(shù)學(xué)模型的一些特點，作以下規(guī)定：1因目的函數(shù)為求最小化，所以要求2因非基變量檢驗數(shù)中含有不同等級的優(yōu)先因子，即 ，因p1p2pk；從每個檢驗數(shù)的整體看：檢驗數(shù)的正、負(fù)首先決議于p1的系數(shù)a1j的正負(fù)，假設(shè)a1j0， 那么此檢驗數(shù)的正、負(fù)就決議于p2的系數(shù)a2j的正負(fù)，依次類推。5.3 目的規(guī)劃的單純形解法3)目的規(guī)劃運用單純形法求解， di-，di+ 視為普通變量。P1P2 PL求解目的規(guī)劃單純形法的步驟：P1051、建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行，置k=1。2、檢查

9、該行中能否存在負(fù)數(shù)，且對應(yīng)的前k1行的系數(shù)是零。假設(shè)有負(fù)數(shù)，取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)3，假設(shè)無負(fù)數(shù)，那么轉(zhuǎn)5。3、按最小比值規(guī)那么確定換出變量，當(dāng)存在兩個和兩個以上一樣的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。4、按單純形法進(jìn)展基變換運算，建立新的計算表，前往2。5、當(dāng)k= K時，計算終了。表中的解即為稱心解。否那么置k= k 1，前往到2。例題5:用單純形法求解以下目的規(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

10、+ d3- -d3+ =56 x1 ，x2 ，di-，di+ 0 ,i=1,2,35.5 目的規(guī)劃的靈敏度分析例5：知目的規(guī)劃問題：目的函數(shù)的等級變化為：試分析原解有什么變化？CBXBbx1x22p13p1p2p3x2X1641820100100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3解:原問題的最優(yōu)單純形表為：問題1的變化情況為：CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-1000

11、01000-100P200000000302-300203-20000010000001P1P2p3p2p3000此時，檢驗數(shù)大于等于零，可見，原解仍是稱心解。p3003203002302001010CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3p12p23p2p1-320300200-230100p1級的檢驗數(shù)不是大于等于零，那么p1級目的未實現(xiàn)，繼續(xù)迭代。過程見書第108頁。某單位思索職工的晉級調(diào)資方

12、案時，依次遵守得規(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知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間地供需量和單位運費見下表，有關(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è)法得最小運費