1、第5章 目標(biāo)規(guī)劃 (Goal programming),第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型,第2節(jié) 目標(biāo)規(guī)劃的圖解法,第3節(jié) 目標(biāo)規(guī)劃的單純形法,目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個(gè)分支。 線性規(guī)劃只研究在滿足一定條件下，單一目標(biāo)函數(shù)取得最優(yōu)解，在實(shí)際問題中，可能會同時(shí)考慮幾個(gè)方面都達(dá)到最優(yōu)：產(chǎn)量最高，成本最低，質(zhì)量最好，利潤最大，環(huán)境達(dá)標(biāo)，運(yùn)輸滿足等。 目標(biāo)規(guī)劃能更好地兼顧統(tǒng)籌處理多種目標(biāo)的關(guān)系，求得更切合實(shí)際要求的解。,第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型,一、目標(biāo)規(guī)劃概述,目標(biāo)規(guī)劃舉例,例1. 某工廠生產(chǎn)I、II兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如表。試求獲利最大的生產(chǎn)方

2、案。,實(shí)際上，工廠在作決策時(shí)，要考慮一系列因素： (1) 產(chǎn)品I的產(chǎn)量不大于產(chǎn)品II； (2)原材料超過時(shí)，采購成本增加； (3) 設(shè)備臺時(shí)盡量用完； (4) 盡可能達(dá)到并超過計(jì)劃利潤指標(biāo)56元。,1) 線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求得更切合實(shí)際的解。 2) 線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解。,（一）、目標(biāo)規(guī)劃與線性規(guī)劃的比較,4)線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只求得滿意解，就能滿足需要（或更能滿足需要）。,3)線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃

3、中有輕重緩急和主次之分，即有優(yōu)先權(quán)。,（二）、目標(biāo)規(guī)劃的基本概念,例1. 某工廠生產(chǎn)I、II兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如表。試求獲利最大的生產(chǎn)方案。,實(shí)際上，工廠在作決策時(shí)，要考慮一系列因素： (1) 產(chǎn)品I的產(chǎn)量不大于產(chǎn)品II； (2)原材料超過時(shí)，采購成本增加； (3) 設(shè)備臺時(shí)充分用完，不加班； (4) 盡可能達(dá)到并超過計(jì)劃利潤指標(biāo)56元。,x1x2，即x1-x20；,2x1+x211；,x1+2x2=10；,8x1+10 x256；,目標(biāo)規(guī)劃通過引入目標(biāo)值g和偏差變量d，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。 目標(biāo)值gk：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。 實(shí)現(xiàn)值或決策值fk(xj)：是指當(dāng)決策

4、變量xj 選定以后，目標(biāo)函數(shù)的對應(yīng)值。 偏差變量（事先無法確定的未知數(shù)）：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異，記為d。 單詞deviation的首字母。 正偏差變量，記為d+：表示實(shí)現(xiàn)值超過目標(biāo)值的部分。 負(fù)偏差變量，記為d-：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分。,1、決策變量xj和正、負(fù)偏差變量d+，d-,在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有 dd0，并規(guī)定d0，d0,絕對約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行解。所以，絕對約束是硬約束。,引入目標(biāo)值g、正偏差變量d+、負(fù)偏差變量d-后，就對某一問題有了新的限制，即目標(biāo)

5、約束。 目標(biāo)約束既可對原目標(biāo)函數(shù)起作用，也可對原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。,2、目標(biāo)約束和絕對約束,一般表示為：f(xj) = g + d+- d-,思考：下列三種情形下，如何才算達(dá)到目標(biāo)？,若決策目標(biāo)中規(guī)定 f(xj) g，則 目標(biāo)中d+ = 0； 若決策目標(biāo)中規(guī)定 f(xj) g，則 目標(biāo)中d- = 0； 若決策目標(biāo)中規(guī)定 f(xj) = g，則 目標(biāo)中d+ = d- = 0.,準(zhǔn)則函數(shù)是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記為 min z = f (d,d-)。 對應(yīng)一個(gè)目標(biāo)約束，有以下三種情況，但只能出現(xiàn)其中之一： . 恰好達(dá)到規(guī)定的目標(biāo)值，即f(xj) = g，正

6、、負(fù)偏差變量d、 d-都要盡可能小，則min z = f (dd-)。 . 不超過目標(biāo)值，即f(xj) g ，正偏差變量d盡可能小，則min z = f (d)。 . 超過目標(biāo)值，即f(xj) g ，負(fù)偏差變量d-盡可能小，則min z = f (d-)。,3、準(zhǔn)則函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)）,為了將不同級別的目標(biāo)的重要性用數(shù)量表示，引進(jìn)P1, P2,.，用它表示一級目標(biāo)，二級目標(biāo)，.的重要程度，規(guī)定P1P2 P3 ，稱P1，P2，.,為級別系數(shù)。 優(yōu)先因子Pk是將決策目標(biāo)按其重要程度排序并表示出來。P1P2PkPk+1，k=1,2,K。 例如，四個(gè)決策目標(biāo)用四個(gè)優(yōu)先因子排序的準(zhǔn)則函數(shù)： 權(quán)

7、系數(shù)k 區(qū)別具有同一個(gè)優(yōu)先因子的兩個(gè)目標(biāo)的差別的情況。 例如，目標(biāo)i和目標(biāo)j具有相同的優(yōu)先因子Pk準(zhǔn)則函數(shù)：,4、優(yōu)先因子(優(yōu)先等級)Pk與優(yōu)先權(quán)系數(shù)k,對于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。,5、滿意解（具有層次意義的解）,例1.,(1) 產(chǎn)品I的產(chǎn)量不大于產(chǎn)品II； (2)原材料超過時(shí)，采購成本增加； (3)設(shè)備臺時(shí)充分用完，不加班； (4) 盡可能達(dá)到并超過計(jì)劃利潤指標(biāo)56元。,x1x2，即x1-x20；,2x1+x211；,x1+2x2=10；,8x1+10 x256；,引入優(yōu)先因子 P1： x1-x20 ； P

8、2： 2x1+x211 ； P3： x1+2x2=10 ； P4： 8x1+10 x256 ；,目標(biāo)約束： x1-x2= 0+d1+-d1- ； 2x1+x2=11+d2+-d2- ； x1+2x2=10+d3+-d3- ； 8x1+10 x2=56+d4+-d4- ；,例1.,(1) 產(chǎn)品I的產(chǎn)量不大于產(chǎn)品II； (2)原材料超過時(shí)，采購成本增加； (3) 設(shè)備臺時(shí)盡量用完； (4) 盡可能達(dá)到并超過計(jì)劃利潤指標(biāo)56元。,x1x2，即x1-x20；,2x1+x211；,x1+2x2=10；,8x1+10 x256；,目標(biāo)函數(shù) min P1d1+ ； min P2d2+ ； min P3(d3

9、+d3-)； min P4d4- ；,min z =P1d1+P2d2+ +P3(d3+d3-)+P4d4-,目標(biāo)約束： x1-x2= 0+d1+-d1- ； 2x1+x2=11+d2+-d2- ； x1+2x2=10+d3+-d3- ； 8x1+10 x2=56+d4+-d4- ；,例a. 某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計(jì)劃，使獲得的利潤最大？同時(shí)，根據(jù)市場預(yù)測，甲的銷路不是太好，應(yīng)盡可能少生產(chǎn)；乙的銷路較好，可以擴(kuò)大生產(chǎn)。試建立此問題的目標(biāo)規(guī)劃模型。,若在例a中提出下列要求： (1) 首先完成或超額完成利潤指標(biāo) 50000元； (2) 其次，產(chǎn)品

10、甲不超過 200件，產(chǎn)品乙不低于 250件； (3) 再次，現(xiàn)有鋼材 3600噸必須用完。,若在例a中提出下列要求： (1) 首先，完成或超額完成利潤指標(biāo) 50000元； (2) 其次，產(chǎn)品甲不超過 200件，產(chǎn)品乙不低于 250件； (3)再次， 現(xiàn)有鋼材 3600噸必須用完。 試建立目標(biāo)規(guī)劃模型。 分析：本例引入3個(gè)優(yōu)先因子P1, P2, P3；,分析：題目有三個(gè)目標(biāo)層次，包含四個(gè)目標(biāo)值。 第一目標(biāo)： 第二目標(biāo)：有兩個(gè)要求即甲 ，乙 ，但兩個(gè)具有相同的優(yōu)先因子P2，因此需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即 70 :120，化簡為7:12。,第三目標(biāo)：,目標(biāo)規(guī)劃模型為：,某廠生產(chǎn)、

11、兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？,在此基礎(chǔ)上考慮： (1) 產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量； (2) 充分利用設(shè)備有效臺時(shí)，不加班； (3) 利潤不小于 56 元。,解: 分析 第一目標(biāo)：min z1=,第二目標(biāo)：min z2=,例2：,第三目標(biāo)：min z3=,x1x2，即x1-x20；,x1+2x2=10；,8x1+10 x256；,規(guī)劃模型：,（一）、模型的一般形式,二、 目標(biāo)規(guī)劃的數(shù)學(xué)模型,其中，gk為目標(biāo)約束的目標(biāo)值； bi為絕對約束的資源值。,約束,目標(biāo)函數(shù),目標(biāo)約束,資源約束,（二）、建模的步驟,1、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與

12、絕對約束；,4、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù) 。,3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子 Pl (l =1,2,L)。,2、可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時(shí)只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可。,5、根據(jù)決策者的要求，按下列情況之一 構(gòu)造一個(gè)由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即準(zhǔn)則函數(shù)。,.恰好達(dá)到目標(biāo)值，取 。,.允許超過目標(biāo)值，取 。,.不允許超過目標(biāo)值，取 。,練習(xí)1： 1. 已知條件如表所示,如果工廠經(jīng)營目標(biāo)的期望值和優(yōu)先等級如下： P1: 每周總利潤不得低于10000元；

13、 P2: 因合同要求，A型機(jī)每周至少生產(chǎn)10臺，B型機(jī)每周至少 生產(chǎn)15臺； P3: 希望工序的每周生產(chǎn)時(shí)間正好為150小時(shí)，工序的生產(chǎn)時(shí)間最好用足，甚至可適當(dāng)加班。 試建立這個(gè)問題的目標(biāo)規(guī)劃模型。,練習(xí)2、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為,其中目標(biāo)函數(shù)為總利潤，x1,x2 為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標(biāo)： 1、要求總利潤必須超過 2500 元； 2、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140； 3、考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過 60 件和 100 件。 試建立目標(biāo)規(guī)劃模型。,解：以產(chǎn)品 A、B 的單件利潤比 2.5 ：1 為權(quán)系數(shù)，模型如下：,（三）、小結(jié),建立目標(biāo)

14、規(guī)劃的數(shù)學(xué)模型時(shí)，需要確定目標(biāo)值gk、優(yōu)先因子Pl 、權(quán)系數(shù)j等，它都具有一定的主觀性和模糊性，可以用專家評定法給以量化。,圖解法同樣適用兩個(gè)變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時(shí)，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。,圖解法解題步驟如下： (1) 確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表示出來； (2) 在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；,第2節(jié) 目標(biāo)規(guī)劃的圖解法,(3) 求滿足最高優(yōu)先等級目標(biāo)的解； (4) 轉(zhuǎn)到下一個(gè)優(yōu)先等級的目標(biāo)，在不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該

15、優(yōu)先等級目標(biāo)的解； (5) 重復(fù)4，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止； (6) 確定最優(yōu)解和滿意解。 例2：用圖解法求解目標(biāo)規(guī)劃問題。,G,D,結(jié)論：有無窮多滿意解，G(2,4)D(10/3,10/3),x2,x1,用圖解法求解例2的目標(biāo)規(guī)劃,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,A,x2,x1,B,C,B (0.6250, 4.6875) C (0, 5.2083)，B、C 線段上的所有點(diǎn)均是該問題的解（無窮多滿意解）。,例b. 用圖解法求解目標(biāo)規(guī)劃問題,在例2的圖解法求解時(shí)，把絕對約束作最高級考慮。 在例2中依先后次序都能滿足d1+=0、d2+d2-=0、d3-

16、=0，因而z*=0。 在例b中d1+d1-=0、d2-=0，因而z*=0。 但在大多數(shù)問題中并非如此，會出現(xiàn)某些約束得不到滿足，僅僅得到滿意解。,例3.,該廠目標(biāo)為： P1：充分利用裝配線每周開動(dòng)超過40小時(shí)； P2：加班時(shí)間每周盡量不超過10小時(shí)； P3：彩色、黑白電視銷量盡量超過24、30臺。同優(yōu)先因子下兩個(gè)目標(biāo)的權(quán)系數(shù)可用單件利潤比作為權(quán)系數(shù)即 80 :40，化簡為2:1。 設(shè)x1，x2分別表示彩色和黑白電視機(jī)的產(chǎn)量。,以上問題的目標(biāo)規(guī)劃模型,10,20,30,40,50,10,20,30,40,50,x2,x1,(1),(2),(3),(4),E,F,B,A,ABEF區(qū)域中無法滿足d4

17、-=0，只能取一點(diǎn)使d4-盡可能小，即E點(diǎn)。 E點(diǎn)為滿意解，其坐標(biāo)(24,26)。,作業(yè)： P127，T5.2（2）,練習(xí)： P127，T5.2（1）,第3節(jié) 目標(biāo)規(guī)劃的單純形法,（一）、一般形式：,（二）、單純形法的計(jì)算準(zhǔn)則,1) min z ，所有cj-zj0為最優(yōu)準(zhǔn)則。 2) 檢驗(yàn)是否為滿意解。 非基變量的檢驗(yàn)數(shù)含Pk，即cj-zj=kjPk， (k=1,2,k；j=1,2,n) 首先檢查kj 是否全部為零？ 如果kj 全部為零，則表示目標(biāo)均已全部達(dá)到，獲得滿意解，停止計(jì)算轉(zhuǎn)到第(5)步；否則轉(zhuǎn)入(2)。,(1) 建立初始單純形表。 一般假定初始解在原點(diǎn)，即以約束條件中的所有負(fù)偏差變量或

18、松弛變量為初始基變量，按目標(biāo)優(yōu)先等級從左至右分別計(jì)算出各列的檢驗(yàn)數(shù)，填入表的下半部。,（三）、單純形法的計(jì)算步驟,在Pk行，從負(fù)檢驗(yàn)數(shù)中，選絕對值最大者，對應(yīng)的變量xs就是進(jìn)基變量。若Pk行中有幾個(gè)相同的絕對值最大者，則依次比較它們各列下部的檢驗(yàn)數(shù)，取其絕對值最大的負(fù)檢驗(yàn)數(shù)的所在列的xs為進(jìn)基變量。假如仍無法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。,(2) 檢驗(yàn)是否為滿意解。 首先檢查檢驗(yàn)數(shù)kj (k=1,2,k)是否全部為零？如果全部為零，則表示目標(biāo)均已全部達(dá)到，獲得滿意解，停止計(jì)算轉(zhuǎn)到第(5)步； 某一個(gè)kj 0，并且Pk這一行的檢驗(yàn)數(shù)kj0 (j=1,2,n+2m)，應(yīng)繼續(xù)改進(jìn)

19、，轉(zhuǎn)到第(3)步。,(3) 確定出基變量 其方法同線性規(guī)劃，即依據(jù)最小比值法則 故確定xr為出基變量，ers為主元素。若有幾個(gè)相同的行可供選擇時(shí)，選最上面那一行所對應(yīng)得變量為xr 。,(4) 旋轉(zhuǎn)變換（變量迭代）。 以為主元素進(jìn)行變換，得到新的單純形表，獲得一組新解，返回到第(2)步。,(5) 對求得的解進(jìn)行分析 若計(jì)算結(jié)果滿意，停止運(yùn)算；若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，重新進(jìn)行第(2)步。,例4：用單純形法求解例2的目標(biāo)規(guī)劃問題,例4：用單純形法求解例2的目標(biāo)規(guī)劃問題解：將例2化為標(biāo)準(zhǔn)型,= min,10/2,56/10,11/1= 5，故 為換出變量。,表

20、4-1,= min10/3,10,6/3,12/3= 2,故 為換出變量。,表4-2,最優(yōu)解為x12， x2 4。 圖4-1的G(2,4)點(diǎn)，但非基變量 的檢驗(yàn)數(shù)為零，故此題有無窮多最優(yōu)解。 = min4 , 24 , 6= 4,故 為換出變量。,表4-3,G,D,結(jié)論：有無窮多最優(yōu)解，G(2,4)D(10/3,10/3),x2,x1,最優(yōu)解為x110/3,，x2 =10/3。圖4-1的D(10/3,10/3)點(diǎn)。,表4-4,例d、用單純形法求解下列目標(biāo)規(guī)劃問題,= min2500/30,140/2,60/1=60 ,故 為換出變量。,= min700/30,20/2, =10 ,故 為換出變

21、量。,= min400/15, =10 ,故 為換出變量。,= min,350/6,1250/6,100/1=75 ,故 為換出變量。,表中3115/30，說明P3 優(yōu)先等級目標(biāo)沒有實(shí)現(xiàn)，但已無法改進(jìn)，得到滿意解 x1 60， x2 175/3， 115/3， 125/3。,結(jié)果分析：計(jì)算結(jié)果表明，工廠應(yīng)生產(chǎn)A產(chǎn)品60件，B產(chǎn)品175/3件，2500元的利潤目標(biāo)剛好達(dá)到。 125/3，表明產(chǎn)品比最高限額少125/3件，滿足要求。 115/3 表明甲資源超過庫存115/3公斤，該目標(biāo)沒有達(dá)到。 從表中還可以看到，P3 的檢驗(yàn)數(shù)還有負(fù)數(shù)，但其高等級的檢驗(yàn)數(shù)卻是正數(shù)，要保證 P1目標(biāo)實(shí)現(xiàn)，P3等級目標(biāo)則無法實(shí)現(xiàn)。所以，按現(xiàn)有消耗水平和資源庫存量，無法實(shí)現(xiàn)2500元的利潤目標(biāo)。 可考慮如下措施：降低A、B產(chǎn)品對甲資源的消耗量，以滿足現(xiàn)有甲資源庫存量的目標(biāo)；或改變P3等級目標(biāo)的指標(biāo)值，增加甲資源115/3公斤。 若很難實(shí)現(xiàn)上述措施，則需改變現(xiàn)有目標(biāo)的優(yōu)先等級，以取得可