運籌學-3、目標規(guī)劃

1、運 籌 學Operations Research1Chapter 4 目標規(guī)劃Goal Programming運籌學Operations Research4.1 目標規(guī)劃數(shù)學模型 Mathematical Model of GP4.2 目標規(guī)劃的圖解法 The graphical method of GP4.3 單純形法 Simplex Method24.1 目標規(guī)劃數(shù)學模型Mathematical Model of GP3 線性規(guī)劃模型的特征是在滿足一組約束條件下，尋求一個目標的最優(yōu)解（最大值或最小值）。 而在現(xiàn)實生活中最優(yōu)只是相對的，或者說沒有絕對意義下的最優(yōu)，只有相對意義下的滿意。 19

2、78年諾貝爾經(jīng)濟學獎獲得者.西蒙(H.A.Simon-美國卡內(nèi)基-梅隆大學,1916-)教授提出“滿意行為模型要比最大化行為模型豐富得多”，否定了企業(yè)的決策者是“經(jīng)濟人”概念和“最大化”行為準則，提出了“管理人”的概念和“令人滿意”的行為準則，對現(xiàn)代企業(yè)管理的決策科學進行了開創(chuàng)性的研究 4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP4【例4.】考慮例1.1資源消耗如表4-1所示。x1、x2、x3分別為甲、乙、丙的產(chǎn)量。使企業(yè)在計劃期內(nèi)總利潤最大的線性規(guī)劃模型為： 產(chǎn)品 資源甲乙丙現(xiàn)有資源設(shè)備A312200設(shè)備B224200材料C451360材料D235300利潤（元/

3、件）403050表4-14.1.1 引例4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP5最優(yōu)解X（50，30，10），Z34004.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP6 現(xiàn)在決策者根據(jù)企業(yè)的實際情況和市場需求，需要重新制定經(jīng)營目標，其目標的優(yōu)先順序是：（1）利潤不少于3200元（2）產(chǎn)品甲與產(chǎn)品乙的產(chǎn)量比例盡量不超過1.5（3）提高產(chǎn)品丙的產(chǎn)量使之達到30件（4）設(shè)備加工能力不足可以加班解決，能不加班最好不加班（5）受到資金的限制，只能使用現(xiàn)有材料不能再購進【解】 設(shè)甲、乙、丙產(chǎn)品的產(chǎn)量分別為x1、x2、x3。如果按線性規(guī)劃建模思路，

4、最優(yōu)解實質(zhì)是求下列一組不等式的解4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP7通過計算不等式無解，即使設(shè)備加班10小時仍然無解在實際生產(chǎn)過程中生產(chǎn)方案總是存在的，無解只能說明在現(xiàn)有資源條件下，不可能完全滿足所有經(jīng)營目標這種情形是按事先制定的目標順序逐項檢查，盡可能使得結(jié)果達到預定目標，即使不能達到目標也使得離目標的差距最小，這就是目標規(guī)劃的求解思路，對應的解稱為滿意解下面建立例4.1的目標規(guī)劃數(shù)學模型 4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP8設(shè)d為未達到目標值的差值，稱為負偏差變量（negative deviation variab

5、le）d+為超過目標值的差值，稱為正偏差變量（positive deviation variable）, d0、d0設(shè)d1-未達到利潤目標的差值, d1+ 為超過目標的差值當利潤小于3200時,d1且d10,有40 x1+30 x2+50 x3+d1=3200成立當利潤大于3200時，d1且d1，有40 x1+30 x2+50 x3-d1+=3200成立當利潤恰好等于3200時，d1=且d1+=0,有40 x1+30 x2+50 x3=3200成立實際利潤只有上述三種情形之一發(fā)生，因而可以將三個等式寫成一個等式40 x1+30 x2+50 x3+d1d1+=32004.1目標規(guī)劃的數(shù)學模型Ma

6、thematical Model of GP9（2）設(shè) 分別為未達到和超過產(chǎn)品比例要求的偏差變量,則產(chǎn)量比例盡 量不超過1.5的數(shù)學表達式為： （3）設(shè)d3、d分別為品丙的產(chǎn)量未達到和超過30件的偏差變量，則產(chǎn)量丙的產(chǎn)量盡可能達到30件的數(shù)學表達式為： 利潤不少于3200理解為達到或超過3200，即使不能達到也要盡可能接近3200,可以表達成目標函數(shù)d1取最小值，則有4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP10（4） 設(shè)d4 、d4+為設(shè)備A的使用時間偏差變量, d5、d5+為設(shè)備B的使用時間偏差變量，最好不加班的含義是 d4+ 和d5+同時取最小值，等價 于d

7、4+ + d5+取最小值，則設(shè)備的目標函數(shù)和約束為： （5）材料不能購進表示不允許有正偏差，約束條件為小于等于約束由于目標是有序的并且四個目標函數(shù)非負，因此目標函數(shù)可以表達成一個函數(shù)：4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP11式中：Pj（j=1,2,3,4）稱為目標的優(yōu)先因子，第一目標優(yōu)于第二目標，第二目標優(yōu)于第三目標等等，其含義是按P1、P2、的次序分別求后面函數(shù)的最小值.則問題的目標規(guī)劃數(shù)學模型為：4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP12約束實際偏差目標1C13220=32002C22=03C330=304C4164=2

8、005C5216=2006C6242118=3607C726634=3001X1282X2203X3304d1-05d1+206d2-27d2+08d3-09d3+010d4-3611d4+012d5-013d5+16滿意解：約束分析：4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP13（1）目標規(guī)劃數(shù)學模型的形式有：線性模型、非線性模型、整數(shù)模型、交互作用模型等（2）一個目標中的兩個偏差變量di-、 di+至少一個等于零，偏差變量向量的叉積等于零：dd=0 （3）一般目標規(guī)劃是將多個目標函數(shù)寫成一個由偏差變量構(gòu)成的函數(shù)求最小值，按多個目標的重要性，確定優(yōu)先等級，順序求

9、最小值 （4）按決策者的意愿，事先給定所要達到的目標值當期望結(jié)果不超過目標值時，目標函數(shù)求正偏差變量最小;當期望結(jié)果不低于目標值時，目標函數(shù)求負偏差變量最小;當期望結(jié)果恰好等于目標值時，目標函數(shù)求正負偏差變量之和最小4.1.2 數(shù)學模型4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP14（5）由目標構(gòu)成的約束稱為目標約束，目標約束具有更大的彈性，允許結(jié)果與所制定的目標值存在正或負的偏差，如例4.1中的5個等式約束；如果決策者要求結(jié)果一定不能有正或負的偏差，這種約束稱為系統(tǒng)約束，如例4.1的材料約束；（6）目標的排序問題。多個目標之間有相互沖突時，決策者首先必須對目標排序

10、。排序的方法有兩兩比較法、專家評分等方法，構(gòu)造各目標的權(quán)系數(shù)，依據(jù)權(quán)系數(shù)的大小確定目標順序；（7）合理的確定目標數(shù)。目標規(guī)劃的目標函數(shù)中包含了多個目標，決策者對于具有相同重要性的目標可以合并為一個目標，如果同一目標中還想分出先后次序，可以賦予不同的權(quán)系數(shù)，按系數(shù)大小再排序。例如，在例4.1中要求設(shè)備B的加班時間不超過設(shè)備A的時間，目標函數(shù)可以表達為 ,表示在中先求 最小再求 最小。 4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP15（8）多目標決策問題多目標決策研究的范圍比較廣泛，在決策中，可能同時要求多個目標達到最優(yōu)例如，企業(yè)在對多個項目投資時期望收益率盡可能最大，

11、投資風險盡可能最小，屬于多目標決策問題，本章的目標規(guī)劃盡管包含有多個目標，但還是按單個目標求偏差變量的最小值，目標函數(shù)中不含有決策變量，目標規(guī)劃只是多目標決策的一種特殊情形本章不討論多目標規(guī)劃的求解方法，只給出WinQSB軟件求解線性多目標規(guī)劃的操作步驟，參看例4.3和4.94.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP16（9）目標規(guī)劃的一般模型設(shè)xj（j=1,2,n）為決策變量4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP 式中p k 為第k 級優(yōu)先因子, k=1 、2、 K；wkl- 、wkl+，為分別賦予第l個目標約束的正負偏差變量的

12、權(quán)系數(shù)；gl為目標的預期目標值，l=1,L (4.1b)為系統(tǒng)約束,（4.1c）為目標約束17【例4.2】某企業(yè)集團計劃用1000萬元對下屬5個企業(yè)進行技術(shù)改造，各企業(yè)單位的投資額已知，考慮2種市場需求變化、現(xiàn)有競爭對手、替代品的威脅等影響收益的4個因素，技術(shù)改造完成后預測單位投資收益率(（單位投資獲得利潤/單位投資額）100)如表42所示4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP集團制定的目標是：（1）希望完成總投資額又不超過預算；（2）總期望收益率達到總投資的30%；（3）投資風險盡可能最小；（4）保證企業(yè)5的投資額占20%左右集團應如何作出投資決策18企業(yè)1

13、企業(yè)2企業(yè)3企業(yè)4企業(yè)5單位投資額(萬元)1210151320單位投資收益率預測rij市場需求14.3255.845.26.56市場需求23.523.045.084.26.24現(xiàn)有競爭對手3.162.23.563.284.08替代品的威脅2.243.122.62.23.24期望(平均)收益率3.313.344.273.725.03表424.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP19【解】設(shè)xj（j=1,2,5）為集團對第 j 個企業(yè)投資的單位數(shù)（1）總投資約束：4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP（2）期望利潤率約束：整理得20

14、（4）企業(yè)5占20%的投資的目標函數(shù)為 ,約束條件即4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP(3）投資風險約束投資風險值的大小一般用期望收益率的方差表示，但方差是x的非線性函數(shù)這里用離差（rijE(rj)）近似表示風險值，例如，集團投資5個企業(yè)后對于市場需求變化第一情形的風險是： 則4種因素風險最小的目標函數(shù)為： ，約束條件為214.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP根據(jù)目標重要性依次寫出目標函數(shù)，整理后得到投資決策的目標規(guī)劃數(shù)學模型：22【例4.3】車間計劃生產(chǎn)I、II 兩種產(chǎn)品，每種產(chǎn)品均需經(jīng)過A、B兩道工序加工工藝資料如表

15、43所示 產(chǎn)品工序產(chǎn)品甲產(chǎn)品乙每天加工能力(小時)A22120B12100C2.20.890產(chǎn)品售價(元/件)5070產(chǎn)品利潤(元/件)108（1）車間如何安排生產(chǎn)計劃，使產(chǎn)值和利潤都盡可能高（2）如果認為利潤比產(chǎn)值重要，怎樣決策表434.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP23【解】設(shè)x1、x2分別為產(chǎn)品甲和產(chǎn)品乙的日產(chǎn)量，得到線性多目標規(guī)劃模型：4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP24（1）將模型化為目標規(guī)劃問題首先，通過分別求產(chǎn)值最大和利潤最大的線性規(guī)劃最優(yōu)解產(chǎn)值最大的最優(yōu)解：X(1)（20，40），Z13800利潤最大

16、的最優(yōu)解：X (2) （30，30），Z2540目標確定為產(chǎn)值和利潤盡可能達到3800和540，得到目標規(guī)劃數(shù)學模型：4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP254.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP,等價于（2）給 d2- 賦予一個比d1-的系數(shù)大的權(quán)系數(shù),如 ，約束條件不變.權(quán)系數(shù)的大小依據(jù)重要程度給定，或者根據(jù)同一優(yōu)先級的偏差變量的關(guān)系給定，例如，當利潤d2-減少一個單位時，產(chǎn)值d1-減少3個單位，則賦予d2-權(quán)系數(shù)3，則目標函數(shù)為 26本節(jié)介紹了如何建立目標規(guī)劃的數(shù)學模型及有關(guān)概念1.目標規(guī)劃由哪些要素構(gòu)成，與線性規(guī)劃有

17、哪些不同之處2.偏差變量的含義及其作用3.目標函數(shù)的表達方法4.優(yōu)先級別的含義4.1目標規(guī)劃的數(shù)學模型Mathematical Model of GP274.2 目標規(guī)劃的圖解法The graphical method of GP284.2目標規(guī)劃的圖解法The graphical method of GP當目標規(guī)劃模型中只含兩個決策變量（不包含偏差變量）時，可以用圖解法求出滿意解【例4.4】企業(yè)計劃生產(chǎn)I 、 II 兩種產(chǎn)品，這些產(chǎn)品需要使用兩種材料，要在兩種不同設(shè)備上加工工藝資料如表44所示產(chǎn)品 資源產(chǎn)品甲產(chǎn)品乙現(xiàn)有資源材料I3012(kg)材料II0414(kg)設(shè)備A2212(h)設(shè)備

18、B5315(h)產(chǎn)品利潤(元/件)2040表4429【解】設(shè)x1、x2分別為產(chǎn)品甲和產(chǎn)品乙的產(chǎn)量，目標規(guī)劃數(shù)學模型為：企業(yè)怎樣安排生產(chǎn)計劃，盡可能滿足下列目標：(1)力求使利潤指標不低于80元(2)考慮到市場需求,、II兩種產(chǎn)品的生產(chǎn)量需保持1:1的比例(3)設(shè)備A既要求充分利用，又盡可能不加班(4) 設(shè)備B必要時可以加班，但加班時間盡可能少(5)材料不能超用。4.2目標規(guī)劃的圖解法The graphical method of GP30(2)(1)(3)(4 )x2x1(6)(5)o46462 2圖41ABC滿意解C(3,3)滿意解X(3,3)31(3)x1x2204060801002040

19、6080100(2)(1)(4)圖53BC滿意解是線段 上任意點，端點的解是 B(100/3，80/3)，C(60，0)決策者根據(jù)實際情形進行二次選擇A32(3)x1x22040608010020406080100(2)(1)(4)圖53BC滿意解是點 B，X=(100/3，80/3) A33(3)x1x22040608010020406080100(2)(1)(4)圖53滿意解是點 A，X=(20，40) A34本節(jié)介紹了目標規(guī)劃的圖解法1.畫出系統(tǒng)約束和目標約束直線2. 標明偏差變量大于零的變量X的取值區(qū)域3.按優(yōu)先次序分別求各目標的最小值4.2目標規(guī)劃的圖解法The graphical

20、method of GP354.3 單純形法Simplex Method36單純形法求解目標規(guī)劃可參照第一章的步驟，只是目標規(guī)劃的檢驗要按優(yōu)先級順序逐級進行，不同的是：（1）首先使得檢驗數(shù)中P1的系數(shù)非負，再使得P2的系數(shù)非負，依次進行；（2）當P1、P2、Pk對應的系數(shù)全部非負時得到滿意解；（3）如果P1，Pi行系數(shù)非負，而Pi+1行存在負數(shù)，并且負數(shù)所在列上面P1，Pi行中存在正數(shù)時，得到滿意解，計算結(jié)束4.3 單純形法Simplex Method37【例4.6】用單純形法求解下述目標規(guī)劃問題【解】以d1、d2、d3為基變量，求出檢驗數(shù)，將檢驗數(shù)中優(yōu)先因子分離出來，每一優(yōu)先級做一行，列出初

21、始單純形表4-5 4.3 單純形法Simplex Method38Cj00P100P1P20bCB基x1x2d1d1+d2d2+d3d3+P1d11211500d2211140P2d3221180CjZjP112 11P2221表454.3 單純形法Simplex Method39表45中，P1行中(2)最小，則x2進基，求最小比值易知d1出基，將第二列主元素化為1，其余元素化為零，得到表4-6Cj00P100P1P20bCB基x1x2d1d1+d2d2+d3d3+0 x21/211/21/2250d23/21/21115P2d3111130CjZjP111P21111表464.3 單純形法S

22、implex Method40表4-6中P1行全部檢驗數(shù)非負，表明第一目標已經(jīng)得到優(yōu)化P2行存在負數(shù)，x1的檢驗數(shù)為P20，選x1進基（也可以選d1+進基），則d3出基，迭代得到表4-7Cj00P100P1P20bCB基x1x2d1d1+d2d2+d3d3+0 x212/32/31/3200 x111/32/310P2d32/32/31120CjZjP111P22/3-2/32/3-2/314.3 單純形法Simplex Method 表4-741在表4-7中，P1行的系數(shù)全部非負，P2行存在負數(shù)，d1+的檢驗數(shù)2/3P20,所有檢驗數(shù)非負，得到滿意解X（0，40）【例4.7】(1)用單純形法

23、求解例4.5 （2）當目標函數(shù)變?yōu)椤窘狻浚?）初始單純形表見表4-9，最終單純形表見表4-12滿意解X(100/3，80/3)T，對應于圖4-6點B不難看出有多重解，將d4進基x2出基 ，得到另一滿意解X(60，0)T，對應于圖4-6點C，見表4-134.3 單純形法Simplex Method求滿意解43Cj00P100P1P2P20P3bCB基x1x2d1d1+d2d2+d3d3+d4d4+P1d1105114000d27811560P2d322111200d412.511100CjZjP1 11P222P31表4-94.3 單純形法Simplex Method44Cj00P100P1P2

24、P20P3bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x111/21/101/10400d29/2-7/107/1011280P2d311/51/511400d42-1/101/101160CjZjP111P2-11/51/52P31表4-104.3 單純形法Simplex Method45Cj00P100P1P2P20P3bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x115/405/401/41/4250d2-19/4019/40119/49/4145P2d33/203/20111/21/2100 x211/201/201/21/230CjZjP11P23/2

25、03/2021/21/2P31表4114.3 單純形法Simplex Method46Cj00P100P1P2P20P3bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x115/65/62/32/3100/30d21119/619/62/32/3340/30d1+1120/320/310/310/3200/30 x211/31/32/32/3CjZjP11P211P31表4-124.3 單純形法Simplex Method47Cj00P100P1P2P20P3bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x1111/21/2600d21117/27/21400d1+5

26、11552000d43/21/21/213/440CjZjP11P211P31表4134.3 單純形法Simplex Method48（2）將目標函數(shù) 改寫成 以表4-12為基礎(chǔ)，計算出檢驗數(shù)得到表4-14表4-14Cj00P1P1P300P20P4bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x115/65/62/32/3100/3P3d211-19/619/62/32/3340/3 P1d1+1120/3-20/3-10/310/3200/30 x211/31/32/32/380/3CjZjP12-20/320/310/3-10/3P219/67/62/32/3P3119/61P414.3 單純形法Simplex Method49Cj 00P1P1P300P20P4bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x111/81/81/41/425P3d219/4019/401-19/49/4145 0d33/203/201-11/21/2100 x211/201/201/21/230CjZjP111P21P319/4019/4019/49/4P41表4-154.3 單純形法Simplex Method50Cj00P1P1P300P20P4bCB基x1x2d1d1+d2d2+d