1、運籌學-第四章-目標規劃 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 2線性規劃的局限性：線性規劃的局限性：只能解決一組線性約束條件下，某一目標而且只能是一個目標的最大或最小值的問題。實際決策中，衡量方案優劣考慮多個目標。這些目標中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相補充的，也有互相對立的，LP則無能為力。約束條件不能矛盾。在實際決策中，一旦出現矛盾，人們總是力圖設法解決，或增加資源，或減少消耗，從而得到比較可行的方案。目標規劃（Goal Programming）是在LP的基礎上發展起來的解決多目標規劃問題的最有效的方法之一。美國經濟學家查恩斯

2、和庫柏在1961年出版的管理模型及線性規劃的工業應用一書中首先提出的。 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 3一、目標規劃模型的基本思想一、目標規劃模型的基本思想P110 例例3.1目標規劃的基本思想：對每一個目標函數引進一個期望值期望值（理想值），但由于種種條件的限制，這些期望值往往并不都能達到，從而我們對每個目標引進正、負偏差變量正、負偏差變量，然后將所有的目標函數并入原來的約束條件并入原來的約束條件，組成新的約束條件。在這組新的約束條件下，尋找使各種目標偏差達到最小的方案各種目標偏差達到最小的方案。二、目標規劃模型的建立二、目標規劃模型的建立1、目標函數的期望值、目標

3、函數的期望值首先要對每一個目標確定一個希望達到的期望值ei(i=1,2, ,n)。根據歷史資料、市場需求或上級部門的布置等來確定。第一節第一節 目標規劃模型目標規劃模型 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 42、正負偏差變量、正負偏差變量每個目標函數的期望值確定之后，目標的實際值和它的期望值之間就有正的或負的偏差。正偏差變量di+ 表示第i個目標超過期望值的數值；負偏差變量di- 表示第i個目標未達到期望值的數值。同一目標，它的取值不可能在超過期望值的同時，又沒有達到期望值，所以在di+ 和di- 中至少有一個必須為零。di+ di-=0引入正、負偏差變量后，對各個目標建立

4、的目標函數方程。原來的目標函數變成了約束條件的一部分，即目標約束(軟約束) ，原來的約束條件稱為系統約束(硬約束硬約束)。njkkjkjEddxc1* 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 5對約束方程引入偏差變量，使矛盾著的方程不再矛盾。當不易發現矛盾時，我們甚至可以在所有的約束方程中都加入偏差變量。3、達成函數、達成函數如何使各目標的實際值最接近于各自的期望值，構造一個新的目標函數以求得有關偏差變量的最小值。這個新的目標函數反映了各目標函數的期望值達到或實現的情況，故把這個新的目標函數稱為目標達成函數。（1）若要求盡可能達到規定的目標值，則正、負偏差變量di+、di- 都

5、盡可能最小，即minSi=di+di- ；最好等于最好等于（2）若希望盡可能不低于期望值(允許超過)，則負偏差變量di 盡可能的小，而不關心超出量di+ ，故只需將di- 列入目標函數，minSi= di- ；最好不小于最好不小于 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 6（3）若允許某個目標低于期望值，但希望不得超過期望值，則正偏差變量dk+ 盡可能地小，而不關心低于量dk- ，故只需將dk+列入目標函數，minSk= dk+ 。最好不大于最好不大于4、優先等級和目標的權系數優先等級和目標的權系數目標的重要程度不同，用優先等級因子Pk 來表示第k等級目標。優先等級因子Pk 是

6、正的常數，Pk Pk+1 ?！?”的含義是遠遠大于的意思。僅僅是個優先等級的記號，在具體計算時，它并不表示任何具體的數。在求較低級別目標的最優值時，不容許破壞已得到的較高級別的目標。一般來說，必須嚴格實現的目標和不能超過的資源約束必須嚴格實現的目標和不能超過的資源約束等均須列入等均須列入 P1級目標。級目標。同一優先等級下的目標的相對重要性，賦以不同的加權加權 系數系數w。 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 75、建立目標規劃模型的基本步驟：、建立目標規劃模型的基本步驟：1）按生產和工作要求確定各個目標及其優先等級和期望值；2）設立決策變量，建立各個約束條件方程；3）對每

7、個目標引進正、負偏差變量，建立目標約束條件，并入已有的約束條件；4）如果各約束條件之間有矛盾，也可適當引入偏差變量；5）根據各目標的優先等級和權系數寫出達成函數。P110-113 例例3.1 ,P117 例例3.4【課堂作業課堂作業】：某工廠計劃生產甲、乙兩種產品，現有的設備資源、每種產品的技術消耗定額及單位產品的利潤如下表所示。 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 8產品產品資源資源甲甲乙乙現有資源現有資源 設備設備4324單位產品利潤單位產品利潤 54管理部門提出新要求：第一個目標是實現利潤最大，計劃部門規定利潤目標是20；第二個目標是充分利用設備臺時，但盡量少加班；第

8、三個目標做如下規定，甲產品產量希望不少于3單位，乙產品產量比甲產品至少多2單位。假設：甲產品產量希望不少于3單位的權數為3，乙產品產量比甲產品多2單位的權數為5。 minf= P1 d1- + P2(d2- + d2+ ) + P3(3d3- +5 d4- ) s.t. 5x1+4x2 +d1- d1+ = 20 4x1+3x2 +d2- - d2+ = 24 x1 +d3- - d3+ = 3 - x1 + x2 +d4- - d4+ = 2 x1 , x2 ,dk- , dk+ 0三、目標規劃模型的標準形式三、目標規劃模型的標準形式middniximiEddxclibxadwdwPfiii

9、njiijijinjjijjijmjjijKii,.,.,.,.,)(min*2102102121),(1111非負性約束目標約束絕對約束 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 10只含有兩個決策變量的目標規劃模型。線性規劃是在可行域中尋找一點，使單個目標極大或極??；目標規劃則是尋找一個區域，這個區域提供了相互矛盾的目標集的折衷方案。目標規劃的圖解法的思路：目標規劃的圖解法的思路：首先在可行域內尋找一個使P1級各目標均滿足的區域R1；然后再在R1中尋找一個使P2級各目標均滿足的區域R2(R2R1)；接著再在R2中尋找一個滿足P3級各目標的區域R3(R3 R2 R1)；如此繼續

10、，直到尋找到一個區域RK(RK RK-1 R3 R2 R1)，滿足PK級各目標，這時RK即為這個目標規劃的最優解 空間，其中的任一點均為這個目標規劃的滿意解。第二節第二節 目標規劃的圖解法目標規劃的圖解法 目標規劃的圖解法的步驟：目標規劃的圖解法的步驟：p首先，按照絕對約束畫出可行域；p其次，不考慮正負偏差變量，畫出目標約束的邊界線,標出正負偏差的方向；p最后，按優先級別和權重依次分析各級目標。P118例例3.5【作業】:minf= P1 d1- + P2(d2- + d2+ ) + P3(3d3- +5 d4- )s.t. 5x1+4x2 +d1-d1+ = 20 4x1+3x2 +d2-

11、d2+ = 24 x1 +d3- d3+ = 3 -x1 + x2 +d4- d4+ = 2 x1 , x2 ,dk- , dk+ 0 x1x2d1+d1-d2+d2-d3+d3-d4-d4+ABCD滿意解：滿意解：x1=18/7, x2=32/7由圖可知P1、P2都滿足。滿意解代入約束方程 后可得minf=9/7P3 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 12目標規劃與線性規劃的數學模型的結構相似。可用前述單純形算法求解目標規劃模型：v將優先等級Pk視為不同數量級很大的正常數；v正負偏差變量dk+、dk-視為松弛變量，以負偏差變量dk-為初始基變量，建立初始單純形表；v在表

12、中按優先級別分別列出目標函數行；v最優性判別準則類似于LP的單純形算法：檢驗數一般是判斷各優先等級因子系數的正負和大小；v迭代時，先從最高級優先等級系數P1行中挑選調入變量。如果P1行的系數已全部非正，則從下一個優先等級系數P2行中挑選調入變量。以此類推。第三節第三節 目標規劃的單純形法目標規劃的單純形法 P120 例例3.6 序貫法，序貫法， P122 例例3.7 【課堂作業課堂作業】： minZ=P1 d1-+P2(d2-+d2+)+P3(3d3-+5d4-) 5x1+4x2 +d1- d1+ = 20 4x1+3x2 +d2- - d2+= 24 x1 +d3- - d3+ = 3 -

13、x1 + x2 +d4- - d4+ = 2 x1 , x2 ,dk- , dk+ 0 劃為標準型劃為標準型 maxZ=-P1 d1-P2(d2-+d2+)-P3(3d3-+5d4-) 5x1+4x2 +d1- d1+ = 20 4x1+3x2 +d2- - d2+ = 24 x1 +d3- - d3+ = 3 - x1 + x2 +d4- - d4+ = 2 x1 , x2 ,dk- , dk+ 0cj 值值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗數檢驗數 j00-P10- P2- P2-3P30-5P302054-1000000244300-100003100

14、000-1002-11000000 -1d1-d2-d3-d4- P1- P2- 3P3- 5P3+5 P1 +4 P2 -2 P3+4 P1 +3 P2 +5 P30-P10-2P20-3P30-5P3463-檢驗數檢驗數 j jd1-d2-x1d4- P1- P20- 5P33000001-100504-100-5500120300-1-440050100001-1-10+4 P1 +3 P2 +5 P30-P10-2P2-5 P1 -4 P2 +2 P3+5 P1 +4 P2 -5 P30-5P313-cj00- P10- P2- P2- 3P30- 5P30 值值CBXBbx1x2d1

15、-d1+d2-d2+d3-d3+d4-d4+檢驗數檢驗數 j jd3+d2-x1d4-0- P20- 5P3104/5 1/5 -1/500-10080-1/5 -4/5 4/5-1000044/5 1/5 -1/5000000609/5 1/5 -1/50000-1 0- P1000-1/5P2-4/5P2+4/5P2-2P2+9P3+P3-P3-3P3-5P3-10-檢驗數檢驗數 j jd3+d1+x1d4-000- 5P3100-1/4 -15/4 -5/40000303/4001/4 -1/4 -10063/4001/4 -1/40000807/4001/4 -1/400-10- P1

16、000-P2-P235/4P3+5/4P3-5/4P3-3P3-5P34-832/7c cj j00- P10- P2- P2- 3P30- 5P30 值值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+檢驗數檢驗數 j jx2d1+x1d4-000- 5P340001/3 -1/3 -4/3 4/3001100-14/3 -4/3 -1/3 1/300300000-110010000-1/3 1/3 7/3 -7/3 -100- P10 0-P2-P2-5/3P3+5/3P326/3P3-35/3P3-5P3-3檢驗數檢驗數 j jx2d1+x1d3-000- 3P33/7

17、0000-1/7 1/7-13/7 -3/732/70001/7 -1/7004/7 -4/778/700-19/7 -9/7001/7 -1/718/7 0001/7 -1/700-3/7 3/700- P100 0-P2-P2-3/7P3+3/7P3-3P3-26/7P3-9/7P3P3行中d2+的系數是3/7，但它在P2行中的系數為-1，故不能調入。所有檢驗數均小于等于零，已得最優解：X1=18/7,X2=32/7，d1-=d2+=d2-=d3+=d4+=d4-=0,d1+=78/7，d3-=3/7,minf=9/7P3。這說明最優解能完全實現P1、P2級目標，而P3級目標不能完全實現，

18、還相差9/7。第四節第四節 目標規劃的應用目標規劃的應用P124 例例3.8，P125 例例3.9在目標管理中的應用在目標管理中的應用 產品產品資源資源甲甲乙乙現有資源現有資源設備設備2010140售價售價108成本成本56最大需求量最大需求量610經營目標經營目標P1：總利潤不低于40，P2：充分利用設備能力，且盡量不超過140如何安排生產？如何安排生產？minf= P1 d1- + P2 (d2-+d2+ ) x1 6 x2 10 5x1 + 2 x2 +d1- -d1+ =40 20 x1 +10 x2 +d2- -d2+ = 140 x1 , x2, d1-, d1+ , d2-, d

19、2+ 0 x1x2x1 =6x2 =10d1+d1-d2+d2-CBD(6,5)滿意解：x1 =6, x2 = 5設備能力：需求：206+10 5=170，實際：140實現目標P1和P2，降低甲乙產品的設備消耗:降低率(170-140)/170=18%， 甲產品的設備消耗降為20 (1-18%)=16.4, 乙產品的設備消耗降為10 (1-18%)=8.2?？偫麧櫍嚎偫麧櫍?0單位甲：單位甲：5單位乙：單位乙：2生產部目標生產部目標甲產品的產量：甲產品的產量：6，成本：，成本：5乙產品的產量：乙產品的產量：5，成本：，成本：6技術部目標技術部目標甲產品的設備單耗：甲產品的設備單耗：16.4乙產

20、品的設備單耗：乙產品的設備單耗： 8.2銷售部目標銷售部目標甲產品的銷量：甲產品的銷量：6，單價：，單價：10乙產品的銷量：乙產品的銷量：5，單價：，單價： 8minf= P2 d1- + P1 (d2-+d2+ ) x1 6 x2 10 5x1 + 2 x2 +d1- -d1+ =40 20 x1 +10 x2 +d2- -d2+ = 140 x1 , x2, d1-, d1+ , d2-, d2+ 0 x1x2x1 =6x2 =10A(6,2)d1+d1-d2+d2-E產品產品資源資源甲甲乙乙現有資源現有資源設備設備2010140售價售價108成本成本56最大需求量最大需求量610 降低設

21、備消耗很困難，則調整經營目標的次序降低設備消耗很困難，則調整經營目標的次序P1：充分利用設備能力，且盡量不超過140，P2：總利潤不低于40如何安排生產？滿意解：滿意解：x1 =6, x2 = 2利潤指標：利潤指標：實際：56+2 2=34，期望： 40實現實現目標目標P1和和P2，增加甲乙產品的單位利潤，增加甲乙產品的單位利潤:增長率(40-34)/34=18%產品售價由市場決定，為提高利潤，應從降低成本入手：產品售價由市場決定，為提高利潤，應從降低成本入手： 甲產品的成本由5降為10 -5 (1+18%)=4.12, 乙產品的成本由6降為 8 -2 (1+18%)=5.63?？偫麧櫍嚎偫麧?/p>

22、：40單位甲：單位甲：5.88單位乙：單位乙：2.26生產部目標生產部目標甲產品的產量：6，成本：4.12乙產品的產量：2，成本：5.63技術部目標技術部目標甲產品的設備單耗：20乙產品的設備單耗：10銷售部目標銷售部目標甲產品的銷量：6，單價：10乙產品的銷量：2，單價： 8 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 22某副食品批發店預測某商品今后4月的購進與售出價格如表： 在庫存管理中的應用在庫存管理中的應用 月份月份1234成本成本(購價購價+庫存庫存)2.62.52.72.8售價售價2.92.73.13.3假設假設：該商品供不應求，最大銷量受倉庫容量限制； 正常庫容3噸

23、，機動庫容2噸； 月初批發銷貨，月中采購進貨，進貨所需資金完全來自銷售收入； 1月初庫存量2噸，成本2.5千元/噸，該月初無現金。 經營目標：經營目標：(1) 每月都使用正常庫容，盡量不超容； (2) 每月下旬都應儲備1千元以備急用； (3) 4個月總盈利最大。決策變量：決策變量：xj 第j 月的采購量， yj 第j 月的銷售量絕對約束條件絕對約束條件各月銷量約束各月銷量約束:月初售貨，各月銷量不能多于其期初庫存量。 1月 y1 2 2月 y2 2 y1 + x1 y1 + y2 x1 2 3月 y3 2 y1 + x1 y2 + x2 y1 + y2 + y3 x1 x2 2 4月 y42

24、y1 + x1 y2 + x2 y3 + x3 y1 + y2 + y3 + y4 x1 x2 x3 2各月采購量約束各月采購量約束：每月采購量依賴月初的售貨收入。 1月 2.6x1 2.9y1 2.9y1 + 2.6x1 0 2月 2.9y1 2.7y2 + 2.6x1 +2.5x2 0 3月 2.9y1 2.7y2 3.1y3 + 2.6x1+2.5x2+2.7x3 0 4月 2.9y1 2.7y2 3.1y3 3.3y4 + 2.6x1 +2.5x2+2.7x3+2.8x40目標約束條件目標約束條件正常庫容約束正常庫容約束 1月 2 y1 + x1 3y1 + x1 + d1- d1+

25、=1 2月 y1 y2 + x1+ x2 + d2- d2+ = 1 3月 y1 y2 y3 + x1+ x2+ x3 + d3- d3+ = 1 4月 y1 y2 y3 y4 + x1+ x2+ x3 + x4 + d4- d4+ = 1各月儲備金約束各月儲備金約束 1月 2.9y1 -2.6x1 + d5- d5+ = 1 2月 2.9y1 +2.7y2 - 2.6x1 -2.5x2 + d6- d6+ = 1 3月 2.9y1 +2.7y2 +3.1y3 - 2.6x1-2.5x2-2.7x3 + d7- d7+ = 1 4月 2.9y1 +2.7y2 +3.1y3 +3.3y4- 2.

26、6x1 -2.5x2-2.7x3-2.8x4 + d8- d8+ = 1總盈利約束：總盈利約束：期望利潤期望利潤 (3.3-2.5)(3+2) 4=16 銷售收入銷售收入: 2.9y1 +2.7y2 +3.1y3 +3.3y4 銷售成本銷售成本: 2.52+2.6x1 +2.5x2+2.7x3+2.8x4 2.9y1 +2.7y2 +3.1y3 +3.3y4 -2.6x1 -2.5x2-2.7x3 - 2.8x4+ d9- d9+ = 21目標達成函數目標達成函數:minf=P1 (d1+ + d2+ + d3+ + d4+ ) + P2 ( d5- + d6- + d7- + d8- ) +

27、 P3 d9- 運籌學運籌學 第四章第四章 目標規劃目標規劃Slide 25目前的有關目標規劃的文獻往往給人們這樣一種印象，似乎模型中目標約束中的正負偏差變量要成對出現。而實際上決策者在解決實際多目標決策問題時，模型中目標約束中的正負偏差變量可能只出現一個(正偏變量或負偏差變量)或成對出現。目標約束中偏差變量的正確選擇對于多目標決策問題的求解結果有很大的影響，決策者應該根據實際決策情況選擇目標約束中的偏差變量。【例子例子】：某企業在計劃期內生產兩種產品。每生產一件產品1可以獲利12元，每生產一件產品2可以獲利14元，生產一件產品1所需設備A和設備B的臺時分別為8臺時和10臺時，生產一件產品2所

28、需設備A和設備B的臺時分別為10臺時和6臺時。設備A和設備B的有效臺時分別為1500臺時和1000臺時，該企業決策者確定的目標優先級為：【補充補充】：目標約束中偏差變量的選擇：目標約束中偏差變量的選擇第一優先級：實現利潤不低于第一優先級：實現利潤不低于5000元；元；第二優先級：充分利用設備第二優先級：充分利用設備A和設備和設備B的有效臺時的有效臺時 。問問:如何安排產品如何安排產品1和產品和產品2的生產。的生產。建立目標規劃模型時，企業決策者需要從兩個方面進行考慮：首先要考慮現有的設備資源在短期內能否滿足所提出的目標，短期內設備的生產能力難以改變，所以這屬于短期規劃決策問題。其次是如果現有設備的生產能力不能滿足既定的目標，那么要實現上述目標，在長期內又應該如何決策，因為設備的生產能力在長期可以改變，所以這屬于長期規劃決策問題。 設產品設產品1的產量為的產量為X1，產品，產品2的產量為的產量為X2，短期規劃決策目，短期規劃決策目標規劃