1、目 標(biāo) 規(guī) 劃(Goal programming)目標(biāo)(mbio)規(guī)劃的數(shù)學(xué)模型目標(biāo)(mbio)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃概述共五十七頁 目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟管理中多目標(biāo)決策的需要(xyo)而逐步發(fā)展起來的一個分支。 2、線性規(guī)劃求最優(yōu)解；目標(biāo)(mbio)規(guī)劃是找到一個滿意解。 1、線性規(guī)劃只討論一個線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個目標(biāo)決策，可求得更切合實際的解。一、目標(biāo)規(guī)劃概述（一）、目標(biāo)規(guī)劃與線性規(guī)劃的比較共五十七頁 4、線性規(guī)劃的最優(yōu)解是絕對(judu)意義下的最優(yōu)，但需花去大量的人力、物力、財力才能得到；實際過程中，只要求得滿

2、意解，就能滿足需要（或更能滿足需要）。 3、線性規(guī)劃中的約束條件是同等(tngdng)重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，已經(jīng)在經(jīng)濟計劃、生產(chǎn)管理、經(jīng)營管理、市場分析、財務(wù)管理等方面得到了廣泛的應(yīng)用。共五十七頁 例一、某廠計劃在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計劃，使獲得的利潤最大？同時(tngsh)，根據(jù)市場預(yù)測，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴大生產(chǎn)。試建立此問題的數(shù)學(xué)模型。12070單件利潤3000103設(shè)備臺時200054煤炭360049鋼材資源限制乙甲 單位 產(chǎn)品資源 消耗（二）、目標(biāo)(mbio)

3、規(guī)劃的基本概念共五十七頁設(shè)：甲產(chǎn)品(chnpn) x1 ，乙產(chǎn)品 x2 一般(ybn)有：maxZ=70 x1 + 120 x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ， x2 0同時：maxZ1=70 x1 + 120 x2 maxZ2= x1 maxZ3= x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ， x2 0 顯然，這是一個多目標(biāo)規(guī)劃問題，用線性規(guī)劃方法很難找到最優(yōu)解。共五十七頁 目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。 目標(biāo)值：是

4、指預(yù)先給定的某個目標(biāo)的一個期望值。 實現(xiàn)值或決策值：是指當(dāng)決策變量xj 選定以后，目標(biāo)函數(shù)的對應(yīng)值。 偏差變量（事先無法確定的未知數(shù)）：是指實現(xiàn)值和目標(biāo)值之間的差異,記為 d 。 正偏差變量：表示(biosh)實現(xiàn)值超過目標(biāo)值的部分，記為 d。 負偏差變量：表示實現(xiàn)值未達到目標(biāo)值的部分，記為 d。1、目標(biāo)值和偏差(pinch)變量共五十七頁 當(dāng)完成(wn chng)或超額完成(wn chng)規(guī)定的指標(biāo)則表示：d0, d0 當(dāng)未完成規(guī)定的指標(biāo)則表示： d0, d0 當(dāng)恰好完成指標(biāo)時則表示： d0, d0 d d 0 成立。 引入了目標(biāo)(mbio)值和正、負偏差變量后，就對某一問題有了新的限制，

5、既目標(biāo)(mbio)約束。 目標(biāo)約束即可對原目標(biāo)函數(shù)起作用，也可對原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。在一次決策中，實現(xiàn)值不可能既超過目標(biāo)值又未達到目標(biāo)值，故有 d d 0,并規(guī)定d0, d02、目標(biāo)約束和絕對約束共五十七頁 絕對約束（系統(tǒng)約束）是指必須嚴格(yng)滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行解。所以，絕對約束是硬約束。 例如：在例一中，規(guī)定Z1 的目標(biāo)值為 50000,正、負偏差為d、d ,則目標(biāo)函數(shù)可以轉(zhuǎn)換(zhunhun)為目標(biāo)約束，既70 x1 + 120 x2 50000， 同樣，若規(guī)定 Z2200， Z3250 則有 若

6、規(guī)定3600的鋼材必須用完，原式9 x1 +4 x2 3600則變?yōu)楣参迨唔?達成函數(shù)是一個使總偏差量為最小的目標(biāo)函數(shù)，記為 minZ = f（d、d）。 一般說來，有以下三種情況，但只能出現(xiàn)其中之一： .要求恰好達到規(guī)定的目標(biāo)值，即正、負偏差變量要盡可能小，則minZ = f（d d）。 .要求不超過(chogu)目標(biāo)值，即允許達不到目標(biāo)值，也就是正偏差變量盡可能小，則minZ = f（d）。 .要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，也就是負偏差變量盡可能小，則minZ = f（d）。 對于由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。3、達成函數(shù)(hnsh)（即目標(biāo)規(guī)劃中的目標(biāo)

7、函數(shù)(hnsh)）共五十七頁 優(yōu)先因子Pk 是將決策目標(biāo)按其重要程度排序并表示出來。P1P2PkPk+1PK ，k=1.2K。 權(quán)系數(shù)k 區(qū)別具有相同(xin tn)優(yōu)先因子的兩個目標(biāo)的差別，決策者可視具體情況而定。 對于這種解來說，前面的目標(biāo)可以保證(bozhng)實現(xiàn)或部分實現(xiàn)，而后面的目標(biāo)就不一定能保證(bozhng)實現(xiàn)或部分實現(xiàn)，有些可能就不能實現(xiàn)。4、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù) 5、滿意解（具有層次意義的解）共五十七頁 若在例一中提出下列要求： 1、完成或超額完成利潤指標(biāo)(zhbio) 50000元； 2、產(chǎn)品甲不超過 200件，產(chǎn)品乙不低于 250件； 3、現(xiàn)有鋼材 360

8、0噸必須用完。試建立目標(biāo)規(guī)劃模型。 分析：題目有三個目標(biāo)層次，包含四個目標(biāo)值。 第一目標(biāo)： 第二目標(biāo)：有兩個要求即甲 ，乙 ，但兩個具有相同的優(yōu)先因子(ynz)，因此需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即 70 :120，化簡為7:12。例二、共五十七頁第三(d sn)目標(biāo)：目標(biāo)(mbio)規(guī)劃模型為：共五十七頁 某廠生產(chǎn)、兩種產(chǎn)品(chnpn)，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？擁有量原材料2111設(shè)備(臺時)1210單件利潤810 在此基礎(chǔ)上考慮： 1、產(chǎn)品的產(chǎn)量(chnling)不低于產(chǎn)品的產(chǎn)量(chnling)； 2、充分利用設(shè)備有效臺時，不加班； 3、利潤不小于 56

9、 元。解: 分析 第一目標(biāo)： 即產(chǎn)品的產(chǎn)量不大于的產(chǎn)量。 第二目標(biāo)：例三：共五十七頁第三(d sn)目標(biāo)：規(guī)劃(guhu)模型：共五十七頁（一）、模型的一般(ybn)形式二、目標(biāo)(mbio)規(guī)劃的數(shù)學(xué)模型共五十七頁（二）、建模的步驟(bzhu) 1、根據(jù)(gnj)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束； 4、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù) 。 3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子 Pk（k=1.2K）。 2、可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時只需要給絕對約束加上負偏差變量和減去正偏差變量即可。共五十七

10、頁 5、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個由 優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量(binling)組成的，要求實現(xiàn)極小化的目標(biāo)函數(shù)，即達成函數(shù)。.恰好(qiho)達到目標(biāo)值，取 。.允許超過目標(biāo)值，取 。.不允許超過目標(biāo)值，取 。共五十七頁（三）、小結(jié)(xioji)線性規(guī)劃LP目標(biāo)規(guī)劃GP目標(biāo)函數(shù)min , max系數(shù)可正負min , 偏差變量系數(shù)0變量xi, xs xa xi xs xa d約束條件系統(tǒng)約束（絕對約束）目標(biāo)約束系統(tǒng)約束解最優(yōu)最滿意共五十七頁 圖解法同樣適用兩個(lin )變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。 圖解

11、法解題步驟如下： 1、確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對(judu)約束，暫不考慮正負偏差變量）在坐標(biāo)平面上表示出來； 2、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負偏差變量值增大的方向；三、目標(biāo)規(guī)劃的圖解法共五十七頁 3、求滿足最高優(yōu)先等級目標(biāo)的解； 4、轉(zhuǎn)到下一個(y )優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解； 5、重復(fù)4，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止； 6、確定最優(yōu)解和滿意解。例一、用圖解法求解(qi ji)目標(biāo)規(guī)劃問題共五十七頁01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1BC B (0

12、.6250 , 4.6875) C (0 , 5.2083) ， B、C 線段(xindun)上的所有點均是該問題的解（無窮多最優(yōu)解）。共五十七頁 例二、已知一個(y )生產(chǎn)計劃的線性規(guī)劃模型為 其中目標(biāo)函數(shù)為總利潤，x1,x2 為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標(biāo)： 1、要求總利潤必須超過 2500 元； 2、考慮產(chǎn)品受市場影響，為避免(bmin)積壓，A、B的生產(chǎn)量不超過 60 件和 100 件； 3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。共五十七頁 解：以產(chǎn)品 A、B 的單件利潤比 2.5 ：1 為權(quán)系數(shù)，模型(mxng)如下：共五十七頁0 x2 0

13、 x11401201008060402020 40 60 80 100ABCD 結(jié)論(jiln)：C(60 ,58.3)為所求的滿意解。作圖：共五十七頁 檢驗(jinyn)：將上述結(jié)果帶入模型，因 0； 0； 0， 存在； 0， 存在。所以，有下式： minZ=P3 將 x160， x2 58.3 帶入約束條件，得30601258.32499.62500；260+58.3=178.3 140；16060158.358.3 0。說明第k個優(yōu)先等級的目標(biāo)尚未達到,必須檢查Pk這一的檢驗數(shù)kj(j=1.2n+2m).若Pk這一行某些負檢驗數(shù)的同列上面（較高優(yōu)先等級）沒有正檢驗數(shù)，說明未得到滿意解，應(yīng)

14、繼續(xù)改進，轉(zhuǎn)到第3步；若Pk這一行全部負檢驗數(shù)的同列上面（較高優(yōu)先等級）都有正檢驗數(shù)，說明目標(biāo)雖沒達到，但已不能改進，故得滿意解，轉(zhuǎn)到第6步。 3、確定進基變量。 在Pk行，從那些上面沒有正檢驗數(shù)的負檢驗數(shù)中，選絕對值最大者，對應(yīng)的變量xs就是進基變量。若Pk行中有幾個相同的絕對值最大者，則依次比較它們各列下部的檢驗數(shù)，取其絕對值最大的負檢驗數(shù)的所在列的xs為進基變量。假如(jir)仍無法確定，則選最左邊的變量（變量下標(biāo)小者）為進基變量。共五十七頁 4、確定出基變量 其方法同線性規(guī)劃，即依據(jù)最小比值法則(fz)故確定xr為出基變量，ers為主元素。若有幾個相同的行可供選擇時，選最上面那一行所對

15、應(yīng)得變量為xr 。 5、旋轉(zhuǎn)變換（變量迭代）。 以為主元素進行(jnxng)變換，得到新的單純形表，獲得一組新解，返回到第2步。 6、對求得的解進行分析 若計算結(jié)果滿意，停止運算；若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，重新進行第1步。共五十七頁例一、用單純形法求解(qi ji)下列目標(biāo)規(guī)劃問題共五十七頁Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011kjP1 -2500301201000000P2 00

16、0000002.501P3 00000010000= min2500/30,140/2,60/1=60 ,故 為換出變量(binling)。共五十七頁Cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 00000010000= min700/30,20/2, =10 ,故 為換出變量(binling)。共五十七頁Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-

17、1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1 -400030115-150000P2 -250-5/400-5/45/45/2001P3 00000010000= min400/15, =10 ,故 為換出變量(binling)。共五十七頁Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/30000000010001000000

18、11kjP1 00010000000P2 -175/30-1-1/121/12002/5001P3 -80/301/5-1/151/15100000= min,350/6,1250/6,100/1=75 ,故 為換出變量(binling)。共五十七頁Cj 00P100P302.5P20P2CBXBbx1x2P3115/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/

19、300-1/121/12101/2-1/200表中3115/30，說明P3 優(yōu)先等級目標(biāo)沒有實現(xiàn)(shxin)，但已無法改進，得到滿意解 x1 60， x2 175/3， 115/3， 125/3。共五十七頁 結(jié)果分析：計算結(jié)果表明，工廠應(yīng)生產(chǎn)A產(chǎn)品60件，B產(chǎn)品175/3件，2500元的利潤(lrn)目標(biāo)剛好達到。 125/3，表明產(chǎn)品比最高限額少125/3件，滿足要求。 115/3 表明甲資源超過庫存115/3公斤，該目標(biāo)沒有達到。 從表中還可以看到，P3 的檢驗數(shù)還有負數(shù)，但其高等級的檢驗數(shù)卻是正數(shù)，要保證 P1目標(biāo)實現(xiàn)，P3等級目標(biāo)則無法實現(xiàn)。所以，按現(xiàn)有消耗水平和資源庫存量，無法實現(xiàn)

20、2500元的利潤目標(biāo)。 可考慮如下措施：降低A、B產(chǎn)品對甲資源的消耗量，以滿足現(xiàn)有甲資源庫存量的目標(biāo)；或改變P3等級目標(biāo)的指標(biāo)值，增加甲資源115/3公斤。 若很難實現(xiàn)上述措施，則需改變現(xiàn)有目標(biāo)的優(yōu)先等級，以取得可行的滿意解果。共五十七頁練習(xí)：用單純形法求解下列目標(biāo)規(guī)劃(guhu)問題共五十七頁Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001kjP1 0000100000P2 10120002000P3 568100000010= min,10/2,56/10,11/

21、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,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

22、/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-1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-11-11001kjP1 0000100000P2 0000011000P3 0000000100 最優(yōu)解為

23、x110/3,，x2 =10/3。共五十七頁 1、某廠生產(chǎn)(shngchn)A、B、C三種產(chǎn)品，裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品時的工時消耗分別為6、8、10小時，生產(chǎn)線每月正常工作時間為200小時；三種產(chǎn)品銷售后，每臺可獲利分別為500、650和800元；每月銷售量預(yù)計為12、10和6臺。 該廠經(jīng)營目標(biāo)如下：1、利潤指標(biāo)為每月16000元，爭取超額完成；2、充分利用現(xiàn)有生產(chǎn)能力；3、可以適當(dāng)加班，但加班時間不得超過24小時；4、產(chǎn)量以預(yù)計銷售量為準。試建立目標(biāo)規(guī)劃模型。 作業(yè)(zuy)：共五十七頁2、用圖解法求解(qi ji)下列目標(biāo)規(guī)劃問題：滿意(mny)解為由x1 =（3， 3）,

24、x2 =（3.5，1.5） 所連線段。共五十七頁 3、用圖解法解下列目標(biāo)規(guī)劃(guhu)模型。 x1=400, x2=0, Z=80p3共五十七頁0 100 200 300 400 500 100 200 300 400 x2 x14共五十七頁4、用單純形法求解(qi ji)下列目標(biāo)規(guī)劃問題：x =（10，20，10）共五十七頁 5、用目標(biāo)規(guī)劃(guhu)的單純形方法解以下目標(biāo)規(guī)劃(guhu)模型。 5、x1=12, x2=10, =14, Z=14p4 共五十七頁答案(d n)：共五十七頁習(xí) 題1.已知條件(tiojin)如表所示工序型號每周最大加工能力AB（小時/臺）（小時/臺）436215070利潤（元/臺）300450如果工廠經(jīng)營目標(biāo)的期望值和優(yōu)先等級如下：p1: 每周總利潤不得低于10000元；p2: 因合同要求，A型機每周至少生產(chǎn)10臺，B型機每周至少 生產(chǎn)15臺；p3: 希望工序的每周生產(chǎn)時間正好為150小時，工序的生產(chǎn)時間最好用足，甚至(shnzh)可適當(dāng)加班。試建立這個問題的目標(biāo)規(guī)