目標規(guī)劃02-圖解法、單純形法

1、1目標規(guī)劃目標規(guī)劃 Goal Programming（GP）第2節(jié) 目標規(guī)劃的圖解法 如何求解多目標線性規(guī)劃問題，其方法與求解線性規(guī)劃問如何求解多目標線性規(guī)劃問題，其方法與求解線性規(guī)劃問題的方法相似題的方法相似目標線性規(guī)劃目標線性規(guī)劃單純形法單純形法。但是，對于只有。但是，對于只有兩兩個決策變量個決策變量的的目標線性規(guī)劃問題同樣可以采用目標線性規(guī)劃問題同樣可以采用圖解的方法圖解的方法來揭來揭示問題的解的某種特征。示問題的解的某種特征。 在用圖解法解目標規(guī)劃時，首先必須滿足所有絕對約束條在用圖解法解目標規(guī)劃時，首先必須滿足所有絕對約束條件。在此基礎上，再按照目標優(yōu)先級別從高到低的順序，逐個件。在

2、此基礎上，再按照目標優(yōu)先級別從高到低的順序，逐個地考慮各個目標約束條件。地考慮各個目標約束條件。2目標規(guī)劃目標規(guī)劃 Goal Programming（GP）王老板的目標規(guī)劃問題圖解：王老板的目標規(guī)劃問題圖解：min Z = P1 d1+ P2（ d2-+ d2+）+ P3 d3- s.t. 2x1+ x2 11 x1 - x2 + d1- - d1+= 0 x1 + 2x2 + d2- - d2+= 10 8x1 +10 x2 + d3- - d3+= 56 x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 08x1 +10 x2 = 56 x1 - x2 = 0 x1 + 2

3、x2 = 102x1+ x2 =11 絕對約束域絕對約束域d2+ d3+ d3- d2- d1- d1+ （10/3，10/3）（2，4）3目標規(guī)劃目標規(guī)劃 Goal Programming（GP）案例案例 電視機廠裝配彩色和黑白兩種電視機，每裝配一臺電視機需占電視機廠裝配彩色和黑白兩種電視機，每裝配一臺電視機需占用裝配線用裝配線1 1小時，裝配線每周計劃開動小時，裝配線每周計劃開動40小時。預計市場每周彩色小時。預計市場每周彩色電視機的銷量是電視機的銷量是24臺，每臺可獲利臺，每臺可獲利80元；元；每周黑白電視機的銷量是每周黑白電視機的銷量是30臺，每臺可獲利臺，每臺可獲利40元。決策者的目

4、標為：元。決策者的目標為： 第一優(yōu)先級目標：第一優(yōu)先級目標：充分利用充分利用裝配線每周計劃開動的裝配線每周計劃開動的40小時；小時； 第二優(yōu)先級目標：第二優(yōu)先級目標：允許允許裝配線裝配線加班；但加班時間加班；但加班時間每周盡量不超過每周盡量不超過10小時；小時； 第三優(yōu)先級目標：第三優(yōu)先級目標：裝配電視機的數(shù)量盡量滿足市場需求。因為彩裝配電視機的數(shù)量盡量滿足市場需求。因為彩色電視機的利潤更高（是黑白電視機利潤的色電視機的利潤更高（是黑白電視機利潤的2倍），取其市場需求倍），取其市場需求滿足權(quán)系數(shù)為滿足權(quán)系數(shù)為2。4目標規(guī)劃目標規(guī)劃 Goal Programming（GP）解：解：建立目標規(guī)劃模

5、型：建立目標規(guī)劃模型： x1 彩色彩色電視機的生產(chǎn)量電視機的生產(chǎn)量 x2 黑白黑白電視機的生產(chǎn)量電視機的生產(chǎn)量x1 + x2 + d1- - d1+= 40 x1 + x2 + d2- - d2+= 40+10=50 x1 + d3- - d3+= 24 x2 + d4- - d4+= 30 x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- 0 min Z = P1 d1-+ P2 d2+ P3（2d3- +d4-）s.t.5目標規(guī)劃目標規(guī)劃 Goal Programming（GP）利用利用圖解圖解法求解法求解：d3- d1- d3+ d4+ d2+ d1+

6、d4- d2- x2x1x1 + x2 = 40 x1 + x2 = 50 x1 = 24x2 = 30 滿意解（滿意解（24，26）6目標規(guī)劃目標規(guī)劃 Goal Programming（GP）第3節(jié) 目標規(guī)劃的單純形法 目標規(guī)劃的模型實際上是求目標規(guī)劃的模型實際上是求 min 型的線性規(guī)劃，因此，也型的線性規(guī)劃，因此，也可以采用可以采用單純形法單純形法求解。求解。 在采用單純形法求解目標規(guī)劃時，檢驗數(shù)是各優(yōu)先因子的在采用單純形法求解目標規(guī)劃時，檢驗數(shù)是各優(yōu)先因子的線性組合。因此，在判別各檢驗數(shù)的正負及大小時，關鍵是要線性組合。因此，在判別各檢驗數(shù)的正負及大小時，關鍵是要注意到優(yōu)先因子的級別。

7、當檢驗數(shù)按優(yōu)先級別從高到低已滿足注意到優(yōu)先因子的級別。當檢驗數(shù)按優(yōu)先級別從高到低已滿足最優(yōu)性條件時，且無法進一步優(yōu)化時，從單純形表上就可以得最優(yōu)性條件時，且無法進一步優(yōu)化時，從單純形表上就可以得到目標規(guī)劃的最優(yōu)解或滿意解。到目標規(guī)劃的最優(yōu)解或滿意解。7目標規(guī)劃目標規(guī)劃 Goal Programming（GP）例：例：現(xiàn)有如下目標規(guī)劃問題現(xiàn)有如下目標規(guī)劃問題Min Z = P1d1- +P2d2+ +P3d3- 5x1 + 10 x2 + x3 = 60 x1 2x2 + d1- d1+ = 0 4x1 + 4x2 + d2- d2+ = 36 6x1 + 8x2 + d3- d3+ = 48

8、xj ， di- ，di+ 0當前基變量：當前基變量： x3 ，d1- ， d2- ， d3- 。8目標規(guī)劃目標規(guī)劃 Goal Programming（GP）目標規(guī)劃問題的單純形表：目標規(guī)劃問題的單純形表：cj000P100P2P30CB基基解解x1x2x3d1-d1+d2-d2+d3-d3+0 x3605101000000P1d1-01-201-100000d2-36440001-100P3d3-4868000001-1 j P11P21P31P1-121P3-6-819目標規(guī)劃目標規(guī)劃 Goal Programming（GP）cj000P100P2P30CB基基解解x1x2x3d1-d1+

9、d2-d2+d3-d3+0 x3605101000000P1d1-01-201-100000d2-36440001-100P3d3-4868000001-1 j P1-121P21P3-6-81cj000P100P2P30CB基基解解x1x2x3d1-d1+d2-d2+d3-d3+0 x3600201-5500000 x101-201-100000d2-360120-441-100P3d3-480200-66001-1 j P11P21P3-206-6110目標規(guī)劃目標規(guī)劃 Goal Programming（GP）cj000P100P2P30CB基基解解x1x2x3d1-d1+d2-d2+d3

10、-d3+0 x3600201-5500000 x101-201-100000d2-360120-441-100P3d3-480200-66001-1 j P11P21P3-206-61cj000P100P2P30CB基基解解x1x2x3d1-d1+d2-d2+d3-d3+0 x3120011-100-110 x124/51002/5-2/5001/10-1/100d2-36/5000-2/52/51-1-3/53/50 x212/5010-3/103/10001/20-1/20 j P11P21P3111目標規(guī)劃目標規(guī)劃 Goal Programming（GP）第第5 5節(jié)節(jié) 目標規(guī)劃應用問題

11、目標規(guī)劃應用問題 例6： 某單位領導在考慮本單位職工的升級調(diào)資方案時，依次遵守以下規(guī)定：(1) 不超過年工資總額60000元；(2) 每級的人數(shù)不超過定編規(guī)定的人數(shù)；(3) ，級的升級面盡可能達到現(xiàn)有人數(shù)的20%，且無越級 提升；(4) 級不足編制的人數(shù)可錄用新職工，又級的職工中有 10%要退休。 有關資料匯總于表有關資料匯總于表4-84-8中，問該領導應如何擬訂一個滿中，問該領導應如何擬訂一個滿意的方案。意的方案。12表4-8：13解解：設x1、x2、x3分別表示提升到、級和錄用到級的新職工人數(shù)。對各目標確定的優(yōu)先因子為：nP1不超過年工資總額60000元；nP2每級的人數(shù)不超過定編規(guī)定的人

12、數(shù)；nP3、級的升級面盡可能達到現(xiàn)有人數(shù)的20%。先分別建立各目標約束：（具體如下頁所示）（具體如下頁所示）14P1：年工資總額不超過年工資總額不超過60000元元 2000(10-100.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1-d1+ =60000P P2 2：每級的人數(shù)不超過定編規(guī)定的人數(shù)每級的人數(shù)不超過定編規(guī)定的人數(shù) 對級有 10(1-0.1)+x1+d2-d2+=12 對級有 12-x1+x2+d3-d3+=15 對級有 15-x2+x3+d4-d4+=15P P3 3：，級的升級面不大于現(xiàn)有人數(shù)的級的升級面不大于現(xiàn)有人數(shù)的20%20%，但盡可能，但盡可能多提多