1、目 標 規(guī) 劃(Goal programming) 目的規(guī)劃的數(shù)學模型 目的規(guī)劃的圖解法 目的規(guī)劃的單純形法 目的規(guī)劃概述 目的規(guī)劃是在線性規(guī)劃的根底上，為順應經(jīng)濟管理中多目的決策的需求而逐漸開展起來的一個分支。 2、線性規(guī)劃求最優(yōu)解；目的規(guī)劃是找到一個稱心解。 1、線性規(guī)劃只討論一個線性目的函數(shù)在一組線性約束條件下的極值問題；而目的規(guī)劃是多個目的決策，可求得更切合實踐的解。一、目的規(guī)劃概述一、目的規(guī)劃與線性規(guī)劃的比較 4、線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人力、物力、財力才干得到；實踐過程中，只需求得稱心解，就能滿足需求或更能滿足需求。 3、線性規(guī)劃中的約束條件是同等重要的，

2、是硬約束；而目的規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，曾經(jīng)在經(jīng)濟方案、消費管理、運營管理、市場分析、財務管理等方面得到了廣泛的運用。二、目的規(guī)劃的根本概念例題線性規(guī)劃模型為： maxZ = 8x1 + 10 x2 2x1 + x2 11 x1 +2x2 10 x1, x20 X*=(4,3)T Z*=62 目的函數(shù)的位置突出，約束條件是必需嚴厲滿足的等式或不等式，是絕對化的“硬約束，此種問題假設要求太多時，很容易相互矛盾，得不到可行解。如根據(jù)市場情況再加以下要求： (1)產(chǎn)品產(chǎn)量不大于產(chǎn)品。 (2)超越方案供應原資料時，需高價采購，這使本錢添加。(3)應盡能夠充分利用設備工時，但不希望

3、加班。 (4)利潤不少于56元。 用式子表示：x1 - x2 02x1 +x2 11x1 +2x2 =108x1 +10 x2 56 左邊：決策值表示實踐執(zhí)行效果 右邊：目的值表示理想目的 實踐效果與理想目的之間能夠有偏向值缺乏或者超越，假設引入偏向變量，就可變成等式。 目的規(guī)劃經(jīng)過引入目的值和偏向變量，可以將目的函數(shù)轉(zhuǎn)化為目的約束。 目的值：是指預先給定的某個目的的一個期望值。 實現(xiàn)值或決策值：是指當決策變量xj 選定以后，目的函數(shù)的對應值。 偏向變量事先無法確定的未知數(shù)：是指實現(xiàn)值和目的值之間的差別,記為 d 。 正偏向變量:表示實現(xiàn)值超越目的值的部分,記為d+。 負偏向變量:表示實現(xiàn)值未

4、到達目的值的部分,記為d-。1、目的值和偏向變量 當完成或超額完成規(guī)定的目的那么表示：d0, d0 當未完成規(guī)定的目的那么表示： d0, d0 當恰好完成目的時那么表示： d0, d0 d d 0 成立。 引入了目的值和正、負偏向變量后，就對某一問題有了新的限制，即目的約束。 目的約束既可對原目的函數(shù)起作用，也可對原約束起作用。目的約束是目的規(guī)劃中特有的，是軟約束。絕對約束系統(tǒng)約束是指必需嚴厲滿足的等式或不等式約束。如線性規(guī)劃中的一切約束條件都是絕對約束，否那么無可行解。所以，絕對約束是硬約束。在一次決策中，實現(xiàn)值不能夠既超越目的值又未到達目的值，故有 d d 0,并規(guī)定d0, d02、目的約

5、束和絕對約束 達成函數(shù)是一個使總偏向量為最小的目的函數(shù)，記為 minZ = fd,d。 普通說來，有以下三種情況，但只能出現(xiàn)其中之一： .要求恰好到達規(guī)定的目的值，即正、負偏向變量要盡能夠小，那么minZ = fd d。 .要求不超越目的值，即允許達不到目的值，也就是正偏向變量盡能夠小，那么minZ = fd。 .要求超越目的值，即超越量不限，但不低于目的值，也就是負偏向變量盡能夠小，那么minZ = fd。 對于由絕對約束轉(zhuǎn)化而來的目的函數(shù)，也照上述處置即可。3、達成函數(shù)即目的規(guī)劃中的目的函數(shù) 優(yōu)先因子Pk 是將決策目的按其重要程度排序并表示出來。P1P2PiPi+1PL ,i=1,2,L后

6、面乘恣意大的數(shù)還是小。必需“滿足第一級才干“滿足第二級，依次類推。 權(quán)系數(shù)lk ：區(qū)別具有一樣優(yōu)先因子的兩個目的的重要性差別，決策者可視詳細情況而定。優(yōu)先因子和權(quán)系數(shù)的大小具有客觀性和模糊性，它不是運籌學本身的問題，主要是決策人本身的閱歷，可用專家評定法給以量化。 對于這種解來說，前面的目的可以保證明現(xiàn)或部分實現(xiàn)，而后面的目的就不一定能保證明現(xiàn)或部分實現(xiàn)，有些能夠就不能實現(xiàn)。4、優(yōu)先因子優(yōu)先等級與優(yōu)先權(quán)系數(shù) 5、稱心解具有層次意義的解例題2：解：確定優(yōu)先因子后得數(shù)學模型： min Z =P1 d1+ +P2 (d2- +d2+ )+P3 d3- 2x1 +x2 11 在絕對約束根底上進展目的規(guī)

7、劃 x1 - x2 + d1- - d1+ = 0 (要求： d1+ 盡能夠小，最好是0才干滿足 ) x1 +2x2 + d2- - d2+ =10 要求：d2- 和 d2+ 都盡能夠小，最好等于0 8x1 +10 x2 + d3- - d3+ =56 要求：d3- 盡能夠小，最好是0才干滿足 x1 , x2 , di- ,di+ 0 規(guī)劃模型：一、模型的普通方式二、目的規(guī)劃的數(shù)學模型二、建模的步驟 1、根據(jù)要研討的問題所提出的各目的與條件，確定目的值，列出目的約束與絕對約束； 4、對同一優(yōu)先等級中的各偏向變量，假設需求可按其重要程度的不同，賦予相應的權(quán)系數(shù) 。 3、給各目的賦予相應的優(yōu)先因子

8、 Pii=1,2,L。 2、可根據(jù)決策者的需求，將某些或全部絕對約束轉(zhuǎn)化為目的約束。這時只需求給絕對約束加上負偏向變量和減去正偏向變量即可。 5、根據(jù)決策者的要求，按以下情況之一構(gòu)造一個由 優(yōu)先因子和權(quán)系數(shù)相對應的偏向變量組成的，要務虛現(xiàn)極小化的目的函數(shù)，即達成函數(shù)。.恰好到達目的值，取 。.允許超越目的值，取 。.不允許超越目的值，取 。三、小結(jié)線性規(guī)劃LP目標規(guī)劃GP目標函數(shù)min , max系數(shù)可正負min , 偏差變量系數(shù)0變量xi, xs xa xi xs xa d約束條件系統(tǒng)約束（絕對約束）目標約束系統(tǒng)約束解最優(yōu)最滿意 圖解法同樣適用兩個變量的目的規(guī)劃問題，但其操作簡單，原理一目了

9、然。同時，也有助于了解普通目的規(guī)劃的求解原理和過程。 圖解法解題步驟如下： 1、確定各約束條件的可行域，即將一切約束條件包括目的約束和絕對約束，暫不思索正負偏向變量在坐標平面上表示出來； 2、在目的約束所代表的邊境限上，用箭頭標出正、負偏向變量值增大的方向；三、目的規(guī)劃的圖解法 3、求滿足最高優(yōu)先等級目的的解； 4、轉(zhuǎn)到下一個優(yōu)先等級的目的，在不破壞一切較高優(yōu)先等級目的的前提下，求出該優(yōu)先等級目的的解； 5、反復4，直到一切優(yōu)先等級的目的都已審查終了為止； 6、確定最優(yōu)解和稱心解。例1、用圖解法求解目的規(guī)劃問題min Z =P1 d1+ +P2 (d2- +d2+ )+P3 d3- 2x1 +

10、x2 11 x1 - x2 + d1- - d1+ = 0 x1 +2x2 + d2- - d2+ =10 8x1 +10 x2 + d3- - d3+ =56 x1 , x2 , di- ,di+ 0 例2、知一個消費方案的線性規(guī)劃模型為 其中目的函數(shù)為總利潤，x1,x2 為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有以下目的： 1、要求總利潤必需超越 2500 元； 2、思索產(chǎn)品受市場影響，為防止積壓，A、B的消費量不超越 60 件和 100 件； 3、由于甲資源供應比較緊張，不要超越現(xiàn)有量140。試建立目的規(guī)劃模型，并用圖解法求解。 解：以產(chǎn)品 A、B 的單件利潤比 2.5 ：1 為權(quán)系數(shù)，模型如下：0 x2

11、0 x11401201008060402020 40 60 80 100ABCD 結(jié)論：C(60 ,58.3)為所求的稱心解。作圖： 檢驗：將上述結(jié)果帶入模型，因 0； 0； 0， 存在； 0， 存在。所以，有下式： minZ=P3 將 x160， x2 58.3 帶入約束條件，得30601258.32499.62500；260+58.3=178.3 140；16060158.358.3 P2 P3 Pk ，所以檢驗數(shù)的正負首先取決于P1 的系數(shù)的正負，假設P1 的系數(shù)為0，再由P2 的系數(shù)的正負決議檢驗數(shù)的正負，然后依次類推。 1、建立初始單純形表。 普通假定初始解在原點，即以約束條件中的一

12、切負偏向變量或松弛變量為初始基變量，按目的優(yōu)先等級從左至右分別計算出各列的檢驗數(shù)，填入表的下半部 。 2、檢驗能否為稱心解。判別準那么如下： .首先檢查k (k=1.2K)能否全部為零？假設全部為零，那么表示目的均已全部到達，獲得稱心解，停頓計算轉(zhuǎn)到第6步；否那么轉(zhuǎn)入。 二、單純形法的計算步驟 .假設某一個k 0。闡明第k個優(yōu)先等級的目的尚未到達,必需檢查Pk這一行的檢驗數(shù)kj(j=1.2n+2m).假設Pk這一行某些負檢驗數(shù)的同列上面較高優(yōu)先等級沒有正檢驗數(shù)，闡明未得到稱心解，應繼續(xù)改良，轉(zhuǎn)到第3步；假設Pk這一行全部負檢驗數(shù)的同列上面較高優(yōu)先等級都有正檢驗數(shù)，闡明目的雖沒到達，但已不能改良

13、，故得稱心解，轉(zhuǎn)到第6步。 3、確定進基變量。 在Pk行，從那些上面沒有正檢驗數(shù)的負檢驗數(shù)中，選絕對值最大者，對應的變量xs就是進基變量。假設Pk行中有幾個一樣的絕對值最大者，那么依次比較它們各列下部的檢驗數(shù)，取其絕對值最大的負檢驗數(shù)的所在列的xs為進基變量。假設仍無法確定，那么選最左邊的變量變量下標小者為進基變量。 4、確定出基變量 其方法同線性規(guī)劃，即根據(jù)最小比值法那么故確定xr為出基變量，ers為主元素。假設有幾個一樣的行可供選擇時，選最上面那一行所對應得變量為xr 。 5、旋轉(zhuǎn)變換變量迭代。 以為主元素進展變換，得到新的單純形表，獲得一組新解，前往到第2步。 6、對求得的解進展分析 假

14、設計算結(jié)果稱心，停頓運算；假設不稱心，需修正模型，即調(diào)整目的優(yōu)先等級和權(quán)系數(shù)，或者改動目的值，重新進展第1步。例1、用單純形法求解以下目的規(guī)劃問題Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011kjP1 -2500301201000000P2 000000002.501P3 00000010000= min2500/30,140/2,60/1=60 ,故 為換出變量。Cj 00P100P302.5P20P2CBXBbx1x2P17

15、00012110030300002001001122000 x160100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 00000010000= min700/30,20/2, =10 ,故 為換出變量。Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1 -400030115-150000P2 -250-5/400-5/45/45/2001

16、P3 00000010000= min400/15, =10 ,故 為換出變量。Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 00010000000P2 -175/30-1-1/121/12002/5001P3 -80/301/5-1/151/15100000= min,350/6,1250/6,100/1=75 ,故 為換出變量。Cj 00P100P302.5P20P2CBXB

17、bx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211kjP1 00010000000P2 000000005/201P3 -115/300-1/121/12101/2-1/200表中3115/30，闡明P3 優(yōu)先等級目的沒有實現(xiàn)，但已無法改良，得到稱心解 x1 60， x2 175/3， 115/3， 125/3。 結(jié)果分析：計算結(jié)果闡明，工廠應消費A產(chǎn)品60件，B產(chǎn)品175/3件，2500元的利潤目的剛好到達。 125/3，

18、闡明產(chǎn)品比最高限額少125/3件，滿足要求。 115/3 闡明甲資源超越庫存115/3公斤，該目的沒有到達。 從表中還可以看到，P3 的檢驗數(shù)還有負數(shù)，但其高等級的檢驗數(shù)卻是正數(shù)，要保證 P1目的實現(xiàn)，P3等級目的那么無法實現(xiàn)。所以，按現(xiàn)有耗費程度和資源庫存量，無法實現(xiàn)2500元的利潤目的。 可思索如下措施：降低A、B產(chǎn)品對甲資源的耗費量，以滿足現(xiàn)有甲資源庫存量的目的；或改動P3等級目的的目的值，添加甲資源115/3公斤。 假設很難實現(xiàn)上述措施，那么需改動現(xiàn)有目的的優(yōu)先等級，以獲得可行的稱心結(jié)果。練習：用單純形法求解以下目的規(guī)劃問題Cj 000P1 P2 P2P3 00CBXBbx1x2 x3

19、 00111100000P210120011000 P3 5681000001100 x3 11210000001kjP1 0000100000P2 10120002000P3 568100000010= min,10/2,56/10,11/1= 5,故 為換出變量。Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 023/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-1/21/2001kjP1 0000100000P2 0000011000P3 630005-5010= min10/3,10,6/3

20、,12/3= 2,故 為換出變量。Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1/21/200 x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002-2-1/21/21kjP1 0000100000P2 0000011000P3 0000000100 最優(yōu)解為x12， x2 4。 但非基變量 的檢驗數(shù)為零，故此題有無窮多最優(yōu)解。= min4 , 24 , 6= 4,故 為換出變量。Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 04002-26-6-1100 x210/301-

21、1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-11-11001kjP1 0000100000P2 0000011000P3 0000000100 最優(yōu)解為x110/3,，x2 =10/3。 1、某廠消費A、B、C三種產(chǎn)品，裝配任務在同一消費線上完成，三種產(chǎn)品時的工時耗費分別為6、8、10小時，消費線每月正常任務時間為200小時；三種產(chǎn)品銷售后，每臺可獲利分別為500、650和800元；每月銷售量估計為12、10和6臺。 該廠運營目的如下：1、利潤目的為每月16000元，爭取超額完成；2、充分利用現(xiàn)有消費才干；3、可以適當加班，但加班時間不得超越24小時；4、產(chǎn)量以估計銷售量為準。試建立目的規(guī)劃模型。 作業(yè)：2、用圖解法求解以下目的規(guī)劃問題：稱心解為由x1 =3， 3, x2 =3.5，1.5 所連線段。 3、用圖解法解以下目的規(guī)劃模型。 x1=400, x2=0, Z=80p30 100 200 300 400 500 100 200 300 400 x