目標規(guī)劃演示教案

1、目標規(guī)劃目標規(guī)劃1. 目標規(guī)劃的數學模型目標規(guī)劃的數學模型一一. 引例引例 某工廠生產兩種產品、某工廠生產兩種產品、,已知有關數據如下表已知有關數據如下表:產品產品I和和II的產量分別是的產量分別是X1和和X2則模型則模型0,404460105. .86)(21212121xxxxxxtsxxZMaxLP其最優(yōu)解，即最其最優(yōu)解，即最優(yōu)生產計劃為優(yōu)生產計劃為X1=8件件,X2=2件件Max Z=64件件試求獲利最大的生產方案試求獲利最大的生產方案.解解1. 目標規(guī)劃的數學模型目標規(guī)劃的數學模型(2)但在實際中工廠作決策時但在實際中工廠作決策時,要考慮市場等一系列其它條件要考慮市場等一系列其它條件

2、如如(1)根據市場信息根據市場信息,產品產品II的銷售量有下降的趨勢的銷售量有下降的趨勢, 故考慮故考慮 產品產品I的產量不少于產品的產量不少于產品II的一半的一半.(3)最好能節(jié)約最好能節(jié)約4小時設備工時；小時設備工時；(2)原材料嚴重短缺原材料嚴重短缺,生產中應避免過量消耗生產中應避免過量消耗.(4)計劃利潤不少于計劃利潤不少于48元；元；(5)應盡可能達到并超過計劃利潤指標應盡可能達到并超過計劃利潤指標56元元.這樣在考慮產品決策時這樣在考慮產品決策時,便為多目標決策問題便為多目標決策問題. 1961年，查恩斯年，查恩斯(A.charnes)和庫柏和庫柏(W.W.Cooper)提提出目標

3、規(guī)劃出目標規(guī)劃(goal programming)方法方法,它是解決這類決策它是解決這類決策問題的方法之一問題的方法之一.1. 目標規(guī)劃的數學模型目標規(guī)劃的數學模型(3)決策變量決策變量是代表一個決策方案的變量是代表一個決策方案的變量, 如上例的如上例的X1和和X2對每一個決策目標對每一個決策目標,引入引入兩個變量兩個變量d+和和d-, 二、與目標規(guī)劃數學模型有關的概念二、與目標規(guī)劃數學模型有關的概念分別表示決策值超過或不足目標值的部分分別表示決策值超過或不足目標值的部分稱為稱為偏差變量偏差變量故故 正負偏差變量是表示偏離一個目標的偏離量正負偏差變量是表示偏離一個目標的偏離量正偏差變量正偏差變

4、量d+表示決策值超過目標值的部分表示決策值超過目標值的部分.負偏差變量負偏差變量d-表示決策值未達到目標值的部分表示決策值未達到目標值的部分.顯然顯然,d-,d+ 0 由由 于一個決策值不可能即超過目標值同時又未達于一個決策值不可能即超過目標值同時又未達到目標值，到目標值，故有故有:d-*d+ =01. 目標規(guī)劃的數學模型目標規(guī)劃的數學模型(4)2、絕對約束和目標約束、絕對約束和目標約束絕對約束絕對約束是指必須嚴格滿足的等式約束或不等式約束是指必須嚴格滿足的等式約束或不等式約束也稱也稱硬約束硬約束目標約束目標約束就是把一個目標加上負偏差變量減去正偏差就是把一個目標加上負偏差變量減去正偏差 變量

5、等于目標值的一個約束條件變量等于目標值的一個約束條件. 也稱也稱軟約束軟約束3. 優(yōu)先因子優(yōu)先因子(優(yōu)先等級優(yōu)先等級)與權系數與權系數把目標規(guī)劃中的目標分為不同的優(yōu)先級把目標規(guī)劃中的目標分為不同的優(yōu)先級,優(yōu)先級的高低分別用優(yōu)先因子優(yōu)先級的高低分別用優(yōu)先因子P1,P2,表示表示優(yōu)先因子優(yōu)先因子P1表示第一優(yōu)先級目標表示第一優(yōu)先級目標,P2表示第二優(yōu)先級表示第二優(yōu)先級 目標目標,其余類推其余類推. 優(yōu)先因子間的關系：優(yōu)先因子間的關系：PkPk+1權系數權系數是表示同一優(yōu)先級的不同目標的重要程度是表示同一優(yōu)先級的不同目標的重要程度.1. 目標規(guī)劃的數學模型目標規(guī)劃的數學模型(5)當一目標值確定后當一

6、目標值確定后,決策者的要求是盡可能縮小偏離決策者的要求是盡可能縮小偏離目標值目標值，則目標函數一般形式有，則目標函數一般形式有 是按各目標約束的正、負是按各目標約束的正、負偏差變量和賦于相應的優(yōu)先因子而構造的。偏差變量和賦于相應的優(yōu)先因子而構造的。min Z=f(d-,d+) 應用時應用時,有三種基本形式有三種基本形式(1)要求恰好達到目標值要求恰好達到目標值.這時決策值超過或不足目標值這時決策值超過或不足目標值 都是不希望的都是不希望的,因此有因此有 min f(d-+d+)(3) 要求不低于目標值要求不低于目標值,但允許超過目標值但允許超過目標值.這時這時,不不 希望決策值低于目標值希望決

7、策值低于目標值,(2) 要求不超過目標值，但允許不足目標值要求不超過目標值，但允許不足目標值.這時，不這時，不 希望決策值不超過目標值希望決策值不超過目標值, 因此有因此有 min f(d+)因此有因此有 min f(d-)4、目標規(guī)劃的目標函數：、目標規(guī)劃的目標函數：1. 目標規(guī)劃的數學模型目標規(guī)劃的數學模型(6)前面例前面例1的目標規(guī)劃數學模型的目標規(guī)劃數學模型:第一第一 考慮到原材料嚴重短缺考慮到原材料嚴重短缺,生產中應避免過量消耗生產中應避免過量消耗 故故5X1+10X26060第二第二 根據市場信息根據市場信息,產品產品II的銷售量有下降的趨勢的銷售量有下降的趨勢,故故考慮產品考慮產

8、品I的產量不少于產品的產量不少于產品II的一半的一半.021121ddxx第三第三 最好能節(jié)約最好能節(jié)約4小時設備工時小時設備工時第四第四 計劃利潤不少于計劃利潤不少于48元元36442221ddxx48863321ddxx目標函數目標函數min,11dP,22dP33dP1. 目標規(guī)劃的數學模型目標規(guī)劃的數學模型(7)故該問題的數學模型為故該問題的數學模型為3 , 2 , 1, 0, 0,488636440260105. .,min2133212221112121332211kddXXddXXddXXddXXXXtsdPdPdPkk絕對約束絕對約束目目標標約約束束1. 目標規(guī)劃的數學模型目標

9、規(guī)劃的數學模型(8)目標規(guī)劃數學模型的一般形式為目標規(guī)劃數學模型的一般形式為KkddnjxmibxaKkgddxCIidwdwPkkjnjijijkkknjjkjKkkikkiki,.,2 , 1,0,.,2 , 1,0,.,2 , 1),(,.,2 , 1,.,2 , 1),)(min111絕對約束絕對約束目標約束目標約束目標函數目標函數非負約束非負約束正負偏差變量正負偏差變量1. 目標規(guī)劃的數學模型目標規(guī)劃的數學模型(9)例例2. 某織布廠生產甲某織布廠生產甲,乙兩種布料乙兩種布料,平均生產能力都是平均生產能力都是1千千米米/小時。這個工廠的正常生產能力是每周小時。這個工廠的正常生產能力是

10、每周80小時。甲小時。甲種衣料每千米可獲利種衣料每千米可獲利2500元元,乙種布料每千米可獲利乙種布料每千米可獲利1500元。已知下一個星期甲種衣料的需求量最多為元。已知下一個星期甲種衣料的需求量最多為70千千米米,乙種衣料下一個星期的需求量最多為乙種衣料下一個星期的需求量最多為45千米千米.該廠確該廠確定的目標依次為定的目標依次為:試建立該問題的目標規(guī)劃模型試建立該問題的目標規(guī)劃模型.(1)避免開工不足避免開工不足,使職工的正常工作保持穩(wěn)定使職工的正常工作保持穩(wěn)定;(3)努力達到最大需求量努力達到最大需求量;(2)允許加班允許加班;但加班時間不超過但加班時間不超過10小時小時;(4)盡量減少

11、加班時間盡量減少加班時間;解解:設生產甲設生產甲,乙兩種布料的時間分別為乙兩種布料的時間分別為X1和和X21. 目標規(guī)劃的數學模型目標規(guī)劃的數學模型(10)避免開工不足避免開工不足,使職工的正常工作保持穩(wěn)定使職工的正常工作保持穩(wěn)定努力達到最大需求量努力達到最大需求量允許加班允許加班;但加班時間不超過但加班時間不超過10小時小時盡量減少加班時間盡量減少加班時間第一目標第一目標801121ddXX第二目標第二目標 901121ddXX第三目標第三目標70331ddX45442ddX第四目標第四目標801121ddXX目標目標函數函數),35(,min144332211dPddPdPdP例例1 用圖

12、解法求解下列目標規(guī)劃問題用圖解法求解下列目標規(guī)劃問題:2. 目標規(guī)劃的圖解法（例目標規(guī)劃的圖解法（例11）3 , 2 , 1, 0, 0,488636440260105,min2133212221112121332211kddXXddXXddXXddXXXXdPdPdPkkA AB BD DE EC CF F2.目標規(guī)劃的圖解法目標規(guī)劃的圖解法(例例12)0 05x5x1 1+10 x+10 x2 2=60=60 x2x2x1x1x x1 1-2x-2x2 2=0=01d1d4x4x1 1+4x+4x2 2=36=362d6x6x1 1+8x+8x2 2=48=483d2.目標規(guī)劃的圖解法目標

13、規(guī)劃的圖解法(例例21)(1)充分利用裝配線每周計劃開動充分利用裝配線每周計劃開動40小時小時; 例、例、某電視機廠裝配黑白和彩電兩種電視機某電視機廠裝配黑白和彩電兩種電視機,每裝配一每裝配一 臺電視機需占用裝配線臺電視機需占用裝配線1小時小時,裝配線每周計劃開動裝配線每周計劃開動 40小時小時,預計市場每周彩色電視機的銷量是預計市場每周彩色電視機的銷量是24臺臺,每每 臺可獲利臺可獲利80元元;黑白電視機的銷量是黑白電視機的銷量是30臺臺,每臺可獲每臺可獲 利利40元元.該廠確定的目標依次為該廠確定的目標依次為:(2)允許裝配線加班允許裝配線加班;但加班時間每周盡量不超過但加班時間每周盡量不

14、超過10小時小時(3)裝配電視機的數量盡量滿足市場需要裝配電視機的數量盡量滿足市場需要,因彩色因彩色電視機的利潤高電視機的利潤高,取其權系數為取其權系數為2.試建立該問題的目標規(guī)劃模型試建立該問題的目標規(guī)劃模型.解：解： 設設X1,X2分別表示彩色和黑白電視機的產量分別表示彩色和黑白電視機的產量2.目標規(guī)劃的圖解法目標規(guī)劃的圖解法(例例22)第一目標第一目標第二目標第二目標第三目標第三目標401121ddxx)2(,min4332211ddPdPdPZ24331ddx502221ddxx30442ddx4 , 3 , 2 , 1, 0,21jddxxjj充分利用裝配線每周計劃開動充分利用裝配線

15、每周計劃開動40小時小時允許裝配線加班允許裝配線加班;但加班時間每周盡量不超但加班時間每周盡量不超過過10小時小時裝配電視機的數量盡量滿足市場需要裝配電視機的數量盡量滿足市場需要,因彩色因彩色電視機的利潤高電視機的利潤高,取其權系數為取其權系數為2.目標函數目標函數2.目標規(guī)劃的圖解法目標規(guī)劃的圖解法(例例23)4 , 3 , 2 , 1, 0,30245040. .)2(min21442331222111214332211jddxxddxddxddxxddxxtsddPdPdPZjj2.目標規(guī)劃的圖解法（例目標規(guī)劃的圖解法（例24）X X1 1 X X2 2 0 0 X X1 1+X+X2

16、2=40=401dX X1 1+X+X2 2=50=502dX X1 1=24=243dX X2 2=30=304d)2(,min4332211ddPdPdPZ目標函數目標函數A AB BC CD DG GH HE EF F最優(yōu)解在最優(yōu)解在E E點取得點取得3.目標規(guī)劃的單純形法目標規(guī)劃的單純形法(1) 目標規(guī)劃的數學模型結構與線性規(guī)劃的數學模型結目標規(guī)劃的數學模型結構與線性規(guī)劃的數學模型結構沒有本質的區(qū)別構沒有本質的區(qū)別.故可用單純形法求解故可用單純形法求解.二是二是判別最優(yōu)解的準則要考慮到優(yōu)先級的因素判別最優(yōu)解的準則要考慮到優(yōu)先級的因素不同之處不同之處一是一是初始單純形表中的檢驗數行按優(yōu)先

17、級初始單純形表中的檢驗數行按優(yōu)先級P 列成一個矩陣列成一個矩陣;解目標規(guī)劃問題的單純形法的計算步驟：解目標規(guī)劃問題的單純形法的計算步驟：第一步：建立初始單純形表第一步：建立初始單純形表在表中將檢驗數行按優(yōu)先因子個數分別列成在表中將檢驗數行按優(yōu)先因子個數分別列成K行。行。令令i=13.目標規(guī)劃的單純形法目標規(guī)劃的單純形法(2)例：例：初始基為單位矩陣初始基為單位矩陣(1)取初始基變量取初始基變量單純形表為單純形表為3 , 2 , 1, 0,561081020112. .)()(min213321222111213213322211jddxxddxxddxxddxxxxxtsdPddPdPZjj3

18、213,dddxABCCbBCABbBBB11113.目標規(guī)劃的單純形法目標規(guī)劃的單純形法(3)P1的檢驗數：的檢驗數：C=（0，0，0，0，1，0，0，0，0），），CB=（0，0，0，0） P2的檢驗數：的檢驗數：C=(0,0,0,0,0,1,1,0,0)P3的檢驗數的檢驗數:C=(0,0,0,0,0,0,0,1,0)CB=（0，0，1，0）CB=（0,0,0,1）3.目標規(guī)劃的單純形法目標規(guī)劃的單純形法(4)第二步第二步檢驗時檢驗時,要依照優(yōu)先級的順序要依照優(yōu)先級的順序,由檢驗數矩陣的上邊行開由檢驗數矩陣的上邊行開始始,首先滿足前邊優(yōu)先級首先滿足前邊優(yōu)先級. 判別最優(yōu)解的準則有二條判別最

19、優(yōu)解的準則有二條:檢驗第檢驗第i行中是否存在負數行中是否存在負數,且對應的前且對應的前 i-1行的行的系數是零，若有取其中最小者對應的變量為入系數是零，若有取其中最小者對應的變量為入基變量，基變量，轉第三步轉第三步。若無負數，則轉第五步。若無負數，則轉第五步。 i)如行優(yōu)先級如行優(yōu)先級P1,P2,Pk行的全體檢驗數均非負行的全體檢驗數均非負,則則 相應的單純形表的解為最優(yōu)解相應的單純形表的解為最優(yōu)解;ii )前前P1,P2,Pi行的檢驗數均非負行的檢驗數均非負,而第而第Pi+1行的檢驗行的檢驗 數中有負數數中有負數,如在這個負檢驗數所在列上的前幾行如在這個負檢驗數所在列上的前幾行 中有正檢驗數

20、中有正檢驗數,則相應的單純形表的解為滿意解則相應的單純形表的解為滿意解.3.目標規(guī)劃的單純形法目標規(guī)劃的單純形法(5)第四步第四步：按單純形法進行換基迭代，建立新的單純形：按單純形法進行換基迭代，建立新的單純形 表，轉第二步。表，轉第二步。第五步第五步：當：當i=K 時，計算結束，表中的解即為滿意解。時，計算結束，表中的解即為滿意解。否則令否則令i=i+1, 轉第二步。轉第二步。第三步第三步按最小比值規(guī)則確定出基變量，當存在兩個和兩按最小比值規(guī)則確定出基變量，當存在兩個和兩 個以上相同的最小比值時，具有較高優(yōu)先級別的個以上相同的最小比值時，具有較高優(yōu)先級別的 變量為出基變量。變量為出基變量。3

21、.目標規(guī)劃的單純形法目標規(guī)劃的單純形法(例例1)3.目標規(guī)劃的單純形法目標規(guī)劃的單純形法(例例1-2)上所有的檢驗數都為非負，上所有的檢驗數都為非負，則則X1=2，X2=4即為滿即為滿意解意解。但非基變量。但非基變量d3+的檢驗數為的檢驗數為0，這表示存在，這表示存在多組解。多組解。3.目標規(guī)劃的單純形法目標規(guī)劃的單純形法(例例2)例例2. 2. 3 , 2 , 1, 0, 0,488636440260105,min21332122211121321332211kddXXddXXddXXddXXXXXdPdPdPkk5.目標規(guī)劃應用舉例目標規(guī)劃應用舉例(例例1)例例1 1：某單位領導在考慮本單

22、位職工的升級調資方案時某單位領導在考慮本單位職工的升級調資方案時, , 依次遵守以下規(guī)定依次遵守以下規(guī)定: :(2)(2)每級的人數不超過定編規(guī)定的人數每級的人數不超過定編規(guī)定的人數; ;(1)(1)不超過年工資總額不超過年工資總額6000060000元元; ;(3)(3) 二，三級的升級面盡可能達到現(xiàn)有人數的二，三級的升級面盡可能達到現(xiàn)有人數的20%;20%;注注: :三級不足編制的人數可錄用新職工三級不足編制的人數可錄用新職工, ,又一級的職又一級的職 工中有工中有10%10%要退休要退休; ;有關資料匯總如有關資料匯總如右表右表等等級級 工工資資額額( (元元/ /年年) ) 現(xiàn)現(xiàn)有有人

23、人數數 編編制制人人數數 一一 二二 三三 2 20 00 00 0 1 15 50 00 0 1 10 00 00 0 1 10 0 1 12 2 1 15 5 1 12 2 1 15 5 1 15 5合合計計 3 37 7 4 42 2 試建立該問題的目標規(guī)劃模型試建立該問題的目標規(guī)劃模型5.目標規(guī)劃應用舉例目標規(guī)劃應用舉例(例例1-2)解：解：設設X X1 1，X X2 2，X X3 3分別表示提升到一、二級和錄用到三分別表示提升到一、二級和錄用到三 級的新職工人數級的新職工人數 對各目標確定的優(yōu)先因子為：對各目標確定的優(yōu)先因子為：P P1 1-不超過年工資總額不超過年工資總額60000

24、60000元元; ;P P2 2-每級的人數不超過定編規(guī)定的人數每級的人數不超過定編規(guī)定的人數P P3 3-二，三級的升級面盡可能達到現(xiàn)有人數的二，三級的升級面盡可能達到現(xiàn)有人數的20%;20%;分別建立目標約束：分別建立目標約束：第一目標：年工資總額不超過第一目標：年工資總額不超過6000060000元：元：20002000（10-1010-10* *0.1+X0.1+X1 1) )+1500(12-X+1500(12-X1 1+X+X2 2) )+1000(15-X+1000(15-X2 2+X+X3 3) )=6000011dd5.目標規(guī)劃應用舉例目標規(guī)劃應用舉例(例例1-3)第二目標：

25、第二目標：每級的人數不超過定編規(guī)定的人數每級的人數不超過定編規(guī)定的人數對對I I級有級有10(1-0.1)+X10(1-0.1)+X1 1+ + =12對對IIII級有級有 12-X12-X1 1+X+X2 2+ + =15對對IIIIII級有級有15-X15-X2 2+X+X3 3+ + =1522dd33dd44dd第二目標第二目標：二、三級的升級面盡可能達到現(xiàn)有人數的二、三級的升級面盡可能達到現(xiàn)有人數的20%20%對對IIII級有級有 X X1 1+ + =12*0.255dd對對IIIIII級有級有X X2 2+ + =15*0.266dd目標函數目標函數: )(),(,min653432211ddPdddPdPZ5.目標規(guī)劃應用舉例目標規(guī)劃應用舉例(例例1-4)該問題的數學模型該問題的數學模型: )(),(,min653432211ddPdddPdPZS.T. 20002000（10-1010-10* *0.1+X0.1+X1 1) )+1500(12-X+1500(12-X1 1+X+X2 2) )+1000(15-X+1000