線性目標規(guī)劃教材(PPT 55頁).ppt

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

2、束條件是同等重要的，是硬約束；而目標規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。,目前，目標規(guī)劃已經(jīng)在經(jīng)濟計劃、生產(chǎn)管理、物流管理、市場分析、財務管理等方面得到了廣泛的應用。,例1:某廠計劃在下一個生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知資料如表所示。試制定生產(chǎn)計劃，使獲得的利潤最大？同時，根據(jù)市場預測，甲的銷路不是太好，應盡可能少生產(chǎn)；乙的銷路較好，可以擴大生產(chǎn)。試建立此問題的數(shù)學模型。,（二）目標規(guī)劃的基本概念,設(shè)：甲產(chǎn)品 x1 ，乙產(chǎn)品 x2,一般有：,maxZ=70 x1 + 120 x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ，

3、 x2 0,同時：,maxZ1=70 x1 + 120 x2 minZ2= x1 maxZ3= x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ， x2 0,顯然，這是一個多目標規(guī)劃問題，用線性規(guī)劃方法很難找到最優(yōu)解。,目標規(guī)劃通過引入目標值和偏差變量，可以將目標函數(shù)轉(zhuǎn)化為目標約束。 目標值：是指預先給定的某個目標的一個期望值。 實現(xiàn)值或決策值：是指當決策變量xj 選定以后，目標函數(shù)的對應值。 偏差變量（事先無法確定的未知數(shù)）：是指實現(xiàn)值和目標值之間的差異,記為 d 。 正偏差變量：表示實現(xiàn)值超過目標值的部分，記為 d。 負偏差變量

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

5、行解。所以，絕對約束是硬約束。,例如：在例一中，規(guī)定Z1 的目標值為 50000,正、負偏差為d、d ,則目標函數(shù)可以轉(zhuǎn)換為目標約束，既 70 x1 + 120 x2 50000， 同樣，若規(guī)定 Z2200， Z3250 則有,若規(guī)定3600的鋼材必須用完，原式9 x1 +4 x2 3600 則變?yōu)?達成函數(shù)是一個使總偏差量為最小的目標函數(shù)，記為 minZ = f（d、d）。 一般說來，有以下三種情況，但只能出現(xiàn)其中之一： .要求恰好達到規(guī)定的目標值，即正、負偏差變量要盡可能小，則minZ = f（d d）。 .要求不超過目標值，即允許達不到目標值，也就是正偏差變量盡可能小，則minZ = f

6、（d）。 .要求超過目標值，即超過量不限，但不低于目標值，也就是負偏差變量盡可能小，則minZ = f（d）。,3、達成函數(shù)（即目標規(guī)劃中的目標函數(shù)）,優(yōu)先因子Pk 是將決策目標按其重要程度排序并表示出來。P1P2PkPk+1PK ，k=1.2K。 權(quán)系數(shù)k 區(qū)別具有相同優(yōu)先因子的兩個目標的差別，決策者可視具體情況而定。,對于這種解來說，前面的目標可以保證實現(xiàn)或部分實現(xiàn)，而后面的目標就不一定能保證實現(xiàn)或部分實現(xiàn)，有些可能就不能實現(xiàn)。,4、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù),5、滿意解（具有層次意義的解）,若在例一中提出下列要求： 1、超額完成利潤指標 50000元； 2、產(chǎn)品甲不超過 200件，

7、產(chǎn)品乙不低于 250件； 3、現(xiàn)有鋼材 3600噸必須用完。 試建立目標規(guī)劃模型。,分析：題目有三個目標層次，包含四個目標值。 第一目標： 第二目標：有兩個要求即甲 ，乙 ，兩者具有相同的優(yōu)先因子，為區(qū)分兩者的差別（或重要程度），需要確定權(quán)系數(shù)。本題可用單件利潤比作為權(quán)系數(shù)即 70 :120，化簡為7:12。,例2:,第三目標：,目標規(guī)劃模型為：,某廠生產(chǎn)、兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？,在此基礎(chǔ)上考慮： 1、產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量； 2、充分利用設(shè)備有效臺時，不加班； 3、利潤不小于 56 元。,解: 分析 第一目標： 即產(chǎn)品的產(chǎn)量不大于的產(chǎn)量。,第二目標：,例3：

8、,第三目標：,規(guī)劃模型：,（三）目標規(guī)劃數(shù)學模型,1、目標規(guī)劃數(shù)學模型的一般形式,達成函數(shù),目標約束,其中：gk為第k個目標約束的預期目標值， 和 為pl 優(yōu)先因子對應各目標的權(quán)系數(shù)。,2、建模的步驟,（1）根據(jù)要研究的問題所提出的各目標與條件，確定目標值，列出目標約束與絕對約束。,（4）對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應的權(quán)系數(shù) 。,（3）給各目標賦予相應的優(yōu)先因子 Pk（k=1.2K）。,（2）可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標約束。這時只需要給絕對約束加上負偏差變量和減去正偏差變量即可。,（5）根據(jù)決策者的要求，按下列情況之一構(gòu)造一個由優(yōu)先

9、因子和權(quán)系數(shù)相對應的偏差變量組成的，要求實 現(xiàn)極小化的目標函數(shù)，即達成函數(shù)。,1.恰好達到目標值，即取正、負偏差變量都要盡可能地小，這時,2.要求超過目標值，即超過量不限，但必須是負偏量要盡可能小，這時,3.要求不超過目標值，即允許達不到目標函數(shù)值，即正偏量要盡可能小，這時,3、小結(jié),第二節(jié) 目標規(guī)劃圖解法,目標規(guī)劃的圖解法：,適用兩個變量的目標規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標規(guī)劃的求解原理和過程。,圖解法解題步驟：,1. 將所有約束條件（包括目標約束和絕對約束，暫不考慮正負偏差變量，令其等于0）的直線方程分別標示于坐標平面上。 2. 確定系統(tǒng)約束的可行域。 3

10、. 在目標約束所代表的邊界線上，用箭頭標出正、負偏差變量值增大的方向。,目標規(guī)劃的圖解法,4. 求滿足最高優(yōu)先等級目標的解 5. 轉(zhuǎn)到下一個優(yōu)先等級的目標，再不破壞所有較高優(yōu)先等級目標的前提下，求出該優(yōu)先等級目標的解 6. 重復5，直到所有優(yōu)先等級的目標都已審查完畢為止，確定最優(yōu)解和滿意解。,目標規(guī)劃的圖解法,例4 用圖解法求解下列目標規(guī)劃問題,目標規(guī)劃的圖解法,(a),(b),(c),(d ),x2,x1,(e),(f),d1-,d1+,d2+,d2-,d3-,d3+,d4-,d4+,滿意解(3,3),0,4,6,8,3,4,6,2,2,目標規(guī)劃的圖解法,x1,x2,(a),(b),d1+,

11、d1-,(c),d2-,d2+,(d),d3-,d3+,G,D,滿意解是線段GD上任意點,其中G點X(2,4),D點X(10/3,10/3),0,5.5,10,5,5.6,11,2,4,10/3,10/3,5,10,7,例5,目標規(guī)劃的圖解分析法,O,x1,x2,20,40,60,50,20,40,60,50,a,b,d1-,d1+,d2-,d2+,c,d,d3-,d3+,d4-,d4+,(24,26),滿意解X=(24，26),例6,目標規(guī)劃應用舉例,例7 已知一個生產(chǎn)計劃的線性規(guī)劃模型如下，其中目標函數(shù)為總利潤，x1,x2 為產(chǎn)品A、B產(chǎn)量。,現(xiàn)有下列目標： 1. 要求總利潤必須超過 25

12、00 元； 2. 考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過 60 件和 100 件； 3. 由于甲資源供應比較緊張，不要超過現(xiàn)有量140。 試建立目標規(guī)劃模型，并用圖解法求解。,目標規(guī)劃應用舉例,解：以產(chǎn)品 A,B 的單件利潤比 2.5 :1 為權(quán)系數(shù)，模型如下：,目標規(guī)劃應用舉例,0,x2,0,x1,140 120 100 80 60 40 20,20 40 60 80 100,A,B,C,D,C(60 ,58.3)為所求的滿意解。,(24,26),1、建立初始單純形表。 一般假定初始解在原點，即以約束條件中的所有負偏差變量或松弛變量為初始基變量，按目標優(yōu)先等級從左至右分別計算出

13、各列的檢驗數(shù)（有幾個優(yōu)先因子，檢驗數(shù)就有幾行），填入表的下半部 。,2、檢驗是否為滿意解。判別準則如下： 按優(yōu)先級順序依次檢查P1,P2,.Pk行的檢驗數(shù)（cj-zj）,如果全部為非負，則表示目標均已全部達到，獲得滿意解，停止計算轉(zhuǎn)到第6步；否則轉(zhuǎn)入。,（一）、單純形法的計算步驟,.如果Pk行有負的檢驗數(shù)。說明第k個優(yōu)先等級的目標尚未達到,必須檢查Pk這一行的檢驗數(shù)。若Pk這一行某些負檢驗數(shù)的同列上面（較高優(yōu)先等級）沒有正檢驗數(shù)，說明未得到滿意解，應繼續(xù)改進，轉(zhuǎn)到第3步；若Pk這一行全部負檢驗數(shù)的同列上面（較高優(yōu)先等級）都有正檢驗數(shù)，說明第K個目標雖沒達到，但已不能改進，故得滿意解，轉(zhuǎn)到第6步

14、。,3、確定進基變量。 在Pk行，從那些上面沒有正檢驗數(shù)的負檢驗數(shù)中，選絕對值最大者，對應的變量xs就是進基變量。若Pk行中絕對值最大的負檢驗數(shù)有多個（相等），則選最左邊的變量（變量下標小者）為進基變量。,4、確定出基變量 其方法同線性規(guī)劃，即依據(jù)最小比值法則 故確定xr為出基變量，ers為主元素。若有幾個相同的行可供選擇時，選最上面那一行所對應得變量為xr 。,5、旋轉(zhuǎn)變換（變量迭代）。 以為主元素進行變換，得到新的單純形表，獲得一組新解，返回到第2步。,6、對求得的解進行分析 若計算結(jié)果滿意，停止運算；若不滿意，需修改模型，即調(diào)整目標優(yōu)先等級和權(quán)系數(shù)，或者改變目標值，重新進行第1步。,第一

15、步，列出初始單純形表，目標約束中負偏差變量系數(shù)均為單位向量，故它們的系數(shù)列向量構(gòu)成初始基。目標函數(shù)中偏差變量分別乘以不同的優(yōu)先因子，因此表中的檢驗數(shù)（cj-zj）按優(yōu)先因子P1，P2分成兩行，分別計算。按優(yōu)先級依次檢查，確定入基、出基變量,用換入變量替換基變量中的換出變量，進行迭代運算，得下表。,因檢驗數(shù)中p2行中仍有負數(shù)，可以繼續(xù)優(yōu)化，重復迭代，得最終單純形表,P2行中雖有負檢驗數(shù)，但負檢驗數(shù)同列較高優(yōu)先級的行中存在正檢驗數(shù)，計算應停止，得到滿意解。,說明： 對目標函數(shù)的優(yōu)化是按優(yōu)先等級順序逐級進行的。當P1行所有檢驗數(shù)均為非負時，再考察P2行的檢驗數(shù)是否存在負值，依次類推。 判斷迭代計算是

16、否應停止的準則為： （1）檢驗數(shù)P1，P2,.,Pk行的所有值均為非負。 （2）若P1,.,Pi 行所有檢驗數(shù)為非負，第Pi+1 行存在負檢驗數(shù)，但在負檢驗數(shù)所在列的上面行中有正檢驗數(shù)。如上題中，P2行中雖有負檢驗數(shù)，但負檢驗數(shù)同列較高優(yōu)先級的行中存在正檢驗數(shù)，計算應停止。,例9.用單純形法求解 已知一個生產(chǎn)計劃的線性規(guī)劃模型為,其中目標函數(shù)為總利潤，x1,x2 為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標： 1、要求總利潤必須超過 2500 元； 2、考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過 60 件和 100 件； 3、由于甲資源供應比較緊張，不要超過現(xiàn)有量140。,解：以產(chǎn)品 A、B 的單

17、件利潤比 2.5 ：1 為A、B產(chǎn)品產(chǎn)量權(quán)系數(shù)，模型如下：,= min2500/30,140/2,60/1=60 ,故 為換出變量。,= min700/30,20/2, =10 ,故 為換出變量。,= min400/15, ,故 為換出變量。,= min,350/6,1250/6,100/1=75/3 ,故 為換出變量。,表中P3行存在負數(shù)，說明P3 優(yōu)先等級目標沒有實現(xiàn)，但已無法改進，得到滿意解 x1 60， x2 175/3， 115/3， 125/3。,結(jié)果分析：計算結(jié)果表明，工廠應生產(chǎn)A產(chǎn)品60件，B產(chǎn)品175/3件，2500元的利潤目標剛好達到。 125/3，表明產(chǎn)品比最高限額少125/3件，滿足要求。 115/3 表明甲資源超過庫存115/3公斤，該目標沒有達到。 從表中還可以看到，P3 的檢驗數(shù)還有負數(shù)，但其高等級的檢驗數(shù)卻是正數(shù)，要保證 P1目標實現(xiàn)，P3等級目標則無法實現(xiàn)。 可考慮如下措施：降低A、B產(chǎn)品對甲