運籌學(xué)課件：第4章 目標(biāo)規(guī)劃

1、Chapter4 目標(biāo)規(guī)劃 ( Goal programming )目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法靈敏度分析（選講）目標(biāo)規(guī)劃應(yīng)用舉例 本章主要內(nèi)容：學(xué)習(xí)要點：1. 理解目標(biāo)規(guī)劃概念； 2. 掌握目標(biāo)規(guī)劃建模技巧； 3. 能夠運用單純形法求解模型。 4.1 目標(biāo)規(guī)劃的數(shù)學(xué)模型問題的提出引例 產(chǎn)品資源甲乙資源量設(shè)備/臺時3218原料A/噸104原料B/噸0212單位贏利/萬元35這是一個單目標(biāo)的規(guī)劃問題,模型為：最優(yōu)方案：最優(yōu)值：目標(biāo)規(guī)劃的數(shù)學(xué)模型線性規(guī)劃模型存在的局限性：1）要求問題的解必須滿足全部約束條件，實際問題中并非所有約束都需要嚴格滿足。2）只能處理單目標(biāo)的優(yōu)化問題

2、。實際問題中，目標(biāo)和約束可以相互轉(zhuǎn)化。3）線性規(guī)劃中各個約束條件都處于同等重要地位，但現(xiàn)實問題中，各目標(biāo)的重要性即有層次上的差別，同一層次中又可以有權(quán)重上的區(qū)分。4）線性規(guī)劃尋求最優(yōu)解，但很多實際問題中只需找出滿意解就可以。目標(biāo)規(guī)劃的數(shù)學(xué)模型 產(chǎn)品資源甲乙資源量設(shè)備/臺時3218原料A/噸104原料B/噸0212單位贏利/萬元35但企業(yè)的經(jīng)營目標(biāo)不僅僅是利潤，而且要考慮多個方面，如（1）由市場信息，在生產(chǎn)計劃期內(nèi)，甲產(chǎn)品的銷量有下降趨勢，作計劃目標(biāo)要求甲產(chǎn)品的產(chǎn)量不大于乙產(chǎn)品的產(chǎn)量；（2）盡可能充分利用設(shè)備臺時，不希望加班生產(chǎn)；（3）計劃利潤指標(biāo)32，并且盡可能達到或超過這個利潤指標(biāo)。類似這樣

3、的多目標(biāo)決策問題就是目標(biāo)規(guī)劃問題目標(biāo)規(guī)劃的數(shù)學(xué)模型 目標(biāo)規(guī)劃是由線性規(guī)劃演變而來的。 1961年美國的查恩斯和庫珀提出了目標(biāo)規(guī)劃的有關(guān)概念和模型，以后這種模型得到不斷完善和改進。 線性規(guī)劃是研究資源的有效分配和利用的，其模型的特點是在滿足一組約束條件的情況下尋求某一線性目標(biāo)的極值。 目標(biāo)規(guī)劃是實現(xiàn)目標(biāo)管理的有效工具，它根據(jù)企業(yè)制訂的經(jīng)營目標(biāo)以及這些經(jīng)營目標(biāo)的輕重緩急，考慮到現(xiàn)有資源情況，確定一個滿意方案，使得工作結(jié)果達到規(guī)定目標(biāo)或使差距最小。彌補了線性規(guī)劃的不足。目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃怎樣解決上述線性規(guī)劃模型建模中的局限性？1. 設(shè)置偏差變量，用來表明實際值同目標(biāo)值之間的差異。產(chǎn)生原因：對

4、于企業(yè)給定的目標(biāo)值，可能在實際的決策過程中會出現(xiàn)達不到或者超出的情況，但是具體的數(shù)值事先沒有辦法知道，因此是一個變量，把這種變量記做目標(biāo)的偏差變量。目標(biāo)規(guī)劃的數(shù)學(xué)模型偏差變量用下列符號表示：d+超出目標(biāo)的偏差，稱正偏差變量d-未達到目標(biāo)的偏差，稱負偏差變量正負偏差變量兩者必有一個為0。 當(dāng)實際值超出目標(biāo)值時： d+0, d-=0; 當(dāng)實際值未達到目標(biāo)值時： d+=0, d-0; 當(dāng)實際值同目標(biāo)值恰好一致時： d+=0, d-=0; 故恒有d+d-=0由于在實際決策中，不可能同時出現(xiàn)正負兩個偏差，所以應(yīng)該有一個變量的值為0，即：目標(biāo)規(guī)劃的數(shù)學(xué)模型如：在引例中，利潤的目標(biāo)值為32，可能目標(biāo)值會達不

5、到，所以加上一個負偏差變量d3-0，把目標(biāo)函數(shù)變成但是同樣，目標(biāo)值也有可能會超出，所以減去一個正偏差變量d3+0，把目標(biāo)函數(shù)變成綜合考慮后，得到結(jié)果其中目標(biāo)規(guī)劃的數(shù)學(xué)模型 產(chǎn)品資源甲乙資源量設(shè)備/臺時3218原料A/噸104原料B/噸0212單位贏利/萬元35可以用同樣的方式來處理其它提出的決策要求：（1）要求甲產(chǎn)品產(chǎn)量不大于乙產(chǎn)品產(chǎn)量。（2）盡可能利用設(shè)備臺時，不希望加班。目標(biāo)值是現(xiàn)擁有的18臺時，0是目標(biāo)值，是決策值，則目標(biāo)規(guī)劃的數(shù)學(xué)模型 產(chǎn)品資源甲乙資源量設(shè)備/臺時3218原料A/噸104原料B/噸0212單位贏利/萬元35絕對約束：決策變量必須滿足的約束，也稱為硬約束。目標(biāo)約束：決策過

6、程中決策值和目標(biāo)值可能出現(xiàn)偏差的約束，也稱軟約束。目標(biāo)約束是目標(biāo)規(guī)劃特有的約束。如，引例中的是絕對約束.是目標(biāo)約束.但是問題不同時，軟硬約束也會發(fā)生變化，要因地制宜.2. 統(tǒng)一處理軟硬約束。目標(biāo)規(guī)劃的數(shù)學(xué)模型不同目標(biāo)的主次輕重有兩種差別：一種差別是絕對的，可用優(yōu)先因子Pj來表示。只有在高級優(yōu)先因子對應(yīng)的目標(biāo)已滿足的基礎(chǔ)上，才能考慮較低級優(yōu)先因子對應(yīng)的目標(biāo)；在考慮低級優(yōu)先因子對應(yīng)的目標(biāo)時，絕不允許違背已滿足的高級優(yōu)先因子對應(yīng)的目標(biāo)。優(yōu)先因子間的關(guān)系為Pj Pj+1 ，即Pj對應(yīng)的目標(biāo)比Pj+1對應(yīng)的目標(biāo)有絕對的優(yōu)先性。另一種差別是相對的，這些目標(biāo)具有相同的優(yōu)先因子，它們的重要程度可用權(quán)系數(shù)wj的

7、不同來表示。3. 目標(biāo)的優(yōu)先級與權(quán)系數(shù)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)函數(shù)由于偏差變量、優(yōu)先因子和權(quán)系數(shù)的出現(xiàn)，顯然其構(gòu)造與線性規(guī)劃時的構(gòu)造要有所不同.決策者的目標(biāo)是要做到?jīng)Q策值與目標(biāo)值的偏差能夠盡可能的小，因此目標(biāo)函數(shù)應(yīng)該是一個與偏差有關(guān)的函數(shù)：在這里，目標(biāo)函數(shù)的構(gòu)造根據(jù)實際決策與目標(biāo)的情況，具有下面的3種基本形式。4. 目標(biāo)函數(shù)目標(biāo)規(guī)劃的數(shù)學(xué)模型（1）要求決策值恰好能夠達到目標(biāo)值，即正負偏差都盡可能的小，構(gòu)造形式為：（2）要求決策值不超過目標(biāo)值，即正偏差盡可能的小，其構(gòu)造形式為：（3）要求決策值可以超過目標(biāo)值，即負偏差盡可能的小，其構(gòu)造形式為：目標(biāo)規(guī)劃的數(shù)學(xué)模型 產(chǎn)品資源甲乙資源量設(shè)備/臺時3218

8、原料A/噸104原料B/噸0212單位贏利/萬元35并要求（1）要求甲產(chǎn)品的產(chǎn)量不大于乙產(chǎn)品的產(chǎn)量；（2）盡可能充分利用設(shè)備臺時，不希望加班生產(chǎn)；（3）計劃利潤指標(biāo)32，并且盡可能達到或超過這個利潤指標(biāo).問：如何安排生產(chǎn)可以使得獲利最大？目標(biāo)規(guī)劃的數(shù)學(xué)模型例1（1）要求甲產(chǎn)品的產(chǎn)量不大于乙產(chǎn)品的產(chǎn)量；（2）盡可能充分利用設(shè)備臺時，不希望加班生產(chǎn)；（3）計劃利潤指標(biāo)32，并且盡可能達到或超過這個利潤指標(biāo).（1）產(chǎn)量偏差變量（2）臺時偏差變量（3）利潤偏差變量分析： 產(chǎn)品資源甲乙資源量設(shè)備/臺時3218原料A/噸104原料B/噸0212單位贏利/萬元35解：給各個目標(biāo)約束制訂偏差變量：（1）產(chǎn)量偏

9、差變量（2）臺時偏差變量（3）利潤偏差變量約束條件中，首先是資源的利用不可能超過現(xiàn)有資源量，所以為絕對約束變量在決策過程中對目標(biāo)的作用為目標(biāo)約束目標(biāo)規(guī)劃的數(shù)學(xué)模型 產(chǎn)品資源甲乙資源量設(shè)備/臺時3218原料A/噸104原料B/噸0212單位贏利/萬元35產(chǎn)量希望甲比乙少，故臺時希望能夠不浪費，故：利潤希望比較高，故：綜合上面的3個目標(biāo)，得到本問題的目標(biāo)函數(shù)：目標(biāo)規(guī)劃的數(shù)學(xué)模型綜合得到本問題的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式達成函數(shù)目標(biāo)約束其中：gk為第k個目標(biāo)約束的預(yù)期目標(biāo)值， 和 為pl 優(yōu)先因子對應(yīng)各目標(biāo)的權(quán)系數(shù)。目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃問題建立模型的步驟：1. 根據(jù)要

10、研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束；2. 根據(jù)決策者的需要將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束，只需給絕對約束加上負偏差和減去正偏差變量即可；3. 給各目標(biāo)賦予相應(yīng)的優(yōu)先因子pk；4. 對同一優(yōu)先級中的各偏差變量，若需要，賦予相應(yīng)的權(quán)系數(shù).目標(biāo)規(guī)劃的數(shù)學(xué)模型5. 根據(jù)決策者的要求，按下列三種情況： A）恰好達到目標(biāo)值 B）允許超過目標(biāo)值 C）不允許超過目標(biāo)值構(gòu)造一個由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實現(xiàn)極小化的目標(biāo)函數(shù).用目標(biāo)規(guī)劃求解問題的過程：明確問題，列出目標(biāo)的優(yōu)先級和權(quán)系數(shù)構(gòu)造目標(biāo)規(guī)劃模型求出滿意解滿意否？分析各項目標(biāo)完成情況據(jù)此制定出決策方案N

11、Y目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型：目標(biāo)規(guī)劃的數(shù)學(xué)模型某廠計劃在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲乙兩種產(chǎn)品，已知資源消耗、利潤如下：單位 產(chǎn)品 消耗資源甲乙資源限制鋼材943600煤炭452000設(shè)備臺時3103000單位利潤70120制定生產(chǎn)計劃，使總利潤最大.目標(biāo)規(guī)劃的數(shù)學(xué)模型例2若提出下列要求：第1級目標(biāo)：完成或超額完成利潤指標(biāo)50000元；第2級目標(biāo)：甲的產(chǎn)量不超過200件；乙的產(chǎn)量不低于250件；并依照利潤確定權(quán)系數(shù) 第3級目標(biāo)：現(xiàn)有鋼材3600噸必須用完目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型P1：充分利用現(xiàn)有工時，必要時可以加班；P2：A，B，C的最低產(chǎn)量分別為5，5，8臺，并依單位工時的

12、利潤比例確定權(quán)系數(shù)；P3：生產(chǎn)線加班時每月不超過20小時；P4：A，B，C的月銷售指標(biāo)分別定為10，12，10臺，依單位工時利潤比例確定權(quán)系數(shù).試建立目標(biāo)規(guī)劃模型.練習(xí)： A、B、C三種計算機，在一條生產(chǎn)線上裝配。裝配時間分別為5，8，12小時；利潤分別為每臺1000元，1440元，2520元。生產(chǎn)線每月正常運轉(zhuǎn)170小時。該廠的經(jīng)營目標(biāo)為：答案目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型4.2 目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法：適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。圖解法解題步驟：1. 將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮

13、正負偏差變量）的直線方程分別標(biāo)示于坐標(biāo)平面上。2. 確定系統(tǒng)約束的可行域。3. 在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負偏差變量值增大的方向。目標(biāo)規(guī)劃的圖解法4. 求滿足最高優(yōu)先等級目標(biāo)的解；5. 轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解；6. 重復(fù)5，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止；7. 確定最優(yōu)解和滿意解。目標(biāo)規(guī)劃的圖解法用圖解法求解下列目標(biāo)規(guī)劃問題例1目標(biāo)規(guī)劃的圖解法(a)(b)(c)(d )x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+滿意解(3,3)04683462 2目標(biāo)規(guī)劃的圖解法x1x2(a)(b)

14、d1+d1-(c)d2-d2+(d)d3-d3+GD滿意解是線段GD上任意點其中G點X(2,4),D點X(10/3,10/3)05.51055.6112,410/3,10/35107例2目標(biāo)規(guī)劃的圖解法Ox1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)滿意解X=(24，26)例3目標(biāo)規(guī)劃的圖解法 已知一個生產(chǎn)計劃的線性規(guī)劃模型如下，其中目標(biāo)函數(shù)為總利潤，x1,x2 為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標(biāo)：1. 要求總利潤必須超過 2500 元；2. 考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過 60 件和 100 件；3. 由于甲資

15、源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。例4目標(biāo)規(guī)劃的圖解法解：以產(chǎn)品 A,B 的單件利潤比 2.5 :1 為權(quán)系數(shù)，模型如下：目標(biāo)規(guī)劃的圖解法0 x2 0 x114012010080604020 20 40 60 80 100ABCDC(60 ,58.3)為所求的滿意解。(24,26)目標(biāo)規(guī)劃的圖解法4.3 目標(biāo)規(guī)劃的單純形算法一、目標(biāo)規(guī)劃求解思路目標(biāo)規(guī)劃與線性規(guī)劃的數(shù)學(xué)模型基本相同，可以利用單純形法求解目標(biāo)規(guī)劃問題。求解的思路是：先使最高優(yōu)先級p1的目標(biāo)達到最優(yōu)；當(dāng)p1級的目標(biāo)達到最優(yōu)后轉(zhuǎn)向p2級的目標(biāo)；當(dāng)p2級的目標(biāo)達到最優(yōu)后轉(zhuǎn)向p3級目標(biāo)；依次類推。這

16、樣可以保證不會出現(xiàn)為滿足較低級目標(biāo)的要求而犧牲較高級目標(biāo)的要求。目標(biāo)規(guī)劃的單純形算法給定目標(biāo)規(guī)劃問題的一個基可行解后，其非基變量的檢驗數(shù)中含有優(yōu)先因子由于因此，檢驗數(shù)的正負首先取決于p1的系數(shù)的正負，當(dāng)p1的系數(shù)為0時，檢驗數(shù)的正負取決于p2的系數(shù)的正負。依次類推。目標(biāo)規(guī)劃的單純形算法二、單純形表求解目標(biāo)規(guī)劃的步驟1、建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子數(shù)分別列成行，令k=1；2、檢查檢驗數(shù)的第k行是否有負數(shù)，且對應(yīng)的前k-1行的系數(shù)為0。若有，取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)3；若無負數(shù)，則轉(zhuǎn)5；3、按最小比值規(guī)則確定換出變量。當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)

17、先因子的變量為換出變量，轉(zhuǎn)4；4、按單純形法進行基變換,建立新的單純形表,轉(zhuǎn)25、當(dāng)k=K時，計算結(jié)束；否則令k=k+1，返回2.目標(biāo)規(guī)劃的單純形算法例1解：將問題轉(zhuǎn)化為標(biāo)準(zhǔn)型：取為初始基變量,建立單純形表并計算。目標(biāo)規(guī)劃的單純形算法p1p2p2p3x1x2x3x4d-1d+1d-2d+2d-3d+30 x34110 x412210d-101-11-1p2d-218321-1p3d-332351-1 jp11p2-3-22p3-3-514-0632/3目標(biāo)規(guī)劃的單純形算法p1p2p2p3x1x2x3x4d-1d+1d-2d+2d-3d+30 x3411-110 x412210 x101-11-

18、1p2d-2185-331-1p3d-3328-331-1 jp11p2-53-32p3-83-3146-18/54目標(biāo)規(guī)劃的單純形算法p1p2p2p3x1x2x3x4d-1d+1d-2d+2d-3d+30 x32/51-2/52/5-1/51/50 x424/516/5-6/5-2/52/50 x118/512/5- 2/51/5-1/50 x218/51-3/53/51/5-1/5p3d-316/59/5-9/5-8/58/51-1 jp11p211p3-9/59/58/5-8/51-49-16/9目標(biāo)規(guī)劃的單純形算法p1p2p2p3x1x2x3x4d-1d+1d-2d+2d-3d+30

19、x310/91- 5/95/92/9-2/90 x48/312/3-2/3-2/32/30 x126/915/9-5/9-2/92/90 x214/31-1/31/31/3-1/30d-116/91-1-8/98/95/9-5/9 jp11p211p31目標(biāo)規(guī)劃的單純形算法最后可以得出滿意解決策值恰好達到利潤的目標(biāo)值，比原問題中的最大利潤少了4個單位。目標(biāo)規(guī)劃的單純形算法例2解：轉(zhuǎn)成標(biāo)準(zhǔn)形目標(biāo)規(guī)劃的單純形算法000p1p10p2x1x2x3d1-d1+d2-d2+0 x361010000p1d1-22-101-1000d2-62-30001-1p1-212p210 x3501/21-1/21/

20、2000 x111-1/201/2-1/2000d2-40-20-111-1p1011p21613目標(biāo)規(guī)劃的單純形算法4.4 目標(biāo)規(guī)劃應(yīng)用實例某種牌號的酒系是用3種等級的酒勾兌而成。已知各種等級酒的每天供應(yīng)量和單位成本如下：等級1：供應(yīng)量1500單位/天，成本6元/單位等級2：供應(yīng)量2000單位/天，成本4.5元/單位等級3：供應(yīng)量1000單位/天，成本3元/單位這種牌號的酒有3種商標(biāo)（紅、黃、藍），各種酒的勾兌配比與售價如下：商標(biāo)配比售價紅(1)等級3少于10%等級1多于50%5.5黃(2)等級3少于70%等級1少于20%5.0藍(3)等級3少于50%等級1多于10%4.8為保持聲譽，確定經(jīng)

21、營目標(biāo)為：1、勾兌配比必須嚴格按照要求2、企業(yè)獲取盡可能多的利潤3、紅色商標(biāo)的酒每天產(chǎn)量不得少于2000單位試建立問題的規(guī)劃模型。目標(biāo)規(guī)劃的應(yīng)用舉例解：設(shè)i，j=1，2，3分別表示序號xij: 第i等級的酒在第j種商標(biāo)酒中的數(shù)量yj: 第j商標(biāo)的酒產(chǎn)量產(chǎn)量約束條件（絕對）原料約束條件（絕對）目標(biāo)規(guī)劃的應(yīng)用舉例配比約束條件（目標(biāo)）目標(biāo)規(guī)劃的應(yīng)用舉例利潤約束條件（目標(biāo)）紅色商標(biāo)酒產(chǎn)量約束條件（目標(biāo)）目標(biāo)函數(shù)：目標(biāo)規(guī)劃的應(yīng)用舉例已知某實際問題的線性規(guī)劃模型為假定重新確定這個問題的目標(biāo)為：p1: z的值應(yīng)不低于1900；p2: 資源1必須全部利用。將此問題轉(zhuǎn)換為目標(biāo)規(guī)劃問題，列出數(shù)學(xué)模型。目標(biāo)規(guī)劃的應(yīng)用舉例目標(biāo)規(guī)劃的應(yīng)用舉例 一位投資商有一筆資金準(zhǔn)備購買股票。資金總額為90000元，目前可選的股票有A和B兩種（可以同時投資于兩種股票）。其價格以及年收益率和風(fēng)險系數(shù)如下表： 從上表可知，A股票的收益率為（320）10015，股票B的收益率為4501008，A的收益率比B大，但同時A的風(fēng)險也比B大。這也符合高風(fēng)險高收益的規(guī)律。 試求一種投資方案，使得一年的總投資風(fēng)險不高于700，且投資收益不低于10000元。股