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

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

2、此基礎(chǔ)上，再按照目標(biāo)優(yōu)先級(jí)別從高到低的順序，逐個(gè)地考慮各個(gè)目標(biāo)約束條件。地考慮各個(gè)目標(biāo)約束條件。2目標(biāo)規(guī)劃目標(biāo)規(guī)劃 Goal Programming（GP）王老板的目標(biāo)規(guī)劃問(wèn)題圖解：王老板的目標(biāo)規(guī)劃問(wèn)題圖解：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 絕對(duì)約束域絕對(duì)約束域d2+ d3+ d3- d2- d1- d1+ （10/3，10/3）（2，4）3目標(biāo)規(guī)劃目標(biāo)規(guī)劃 Goal Programming（GP）案例案例 電視機(jī)廠裝配彩色和黑白兩種電視機(jī)，每裝配一臺(tái)電視機(jī)需占電視機(jī)廠裝配彩色和黑白兩種電視機(jī)，每裝配一臺(tái)電視機(jī)需占用裝配線用裝配線1 1小時(shí)，裝配線每周計(jì)劃開動(dòng)小時(shí)，裝配線每周計(jì)劃開動(dòng)40小時(shí)。預(yù)計(jì)市場(chǎng)每周彩色小時(shí)。預(yù)計(jì)市場(chǎng)每周彩色電視機(jī)的銷量是電視機(jī)的銷量是24臺(tái)，每臺(tái)可獲利臺(tái)，每臺(tái)可獲利80元；元；每周黑白電視機(jī)的銷量是每周黑白電視機(jī)的銷量是30臺(tái)，每臺(tái)可獲利臺(tái)，每臺(tái)可獲利40元。決策者的目

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

5、型：建立目標(biāo)規(guī)劃模型： x1 彩色彩色電視機(jī)的生產(chǎn)量電視機(jī)的生產(chǎn)量 x2 黑白黑白電視機(jī)的生產(chǎn)量電視機(jī)的生產(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目標(biāo)規(guī)劃目標(biāo)規(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目標(biāo)規(guī)劃目標(biāo)規(guī)劃 Goal Programming（GP）第3節(jié) 目標(biāo)規(guī)劃的單純形法 目標(biāo)規(guī)劃的模型實(shí)際上是求目標(biāo)規(guī)劃的模型實(shí)際上是求 min 型的線性規(guī)劃，因此，也型的線性規(guī)劃，因此，也可以采用可以采用單純形法單純形法求解。求解。 在采用單純形法求解目標(biāo)規(guī)劃時(shí)，檢驗(yàn)數(shù)是各優(yōu)先因子的在采用單純形法求解目標(biāo)規(guī)劃時(shí)，檢驗(yàn)數(shù)是各優(yōu)先因子的線性組合。因此，在判別各檢驗(yàn)數(shù)的正負(fù)及大小時(shí)，關(guān)鍵是要線性組合。因此，在判別各檢驗(yàn)數(shù)的正負(fù)及大小時(shí)，關(guān)鍵是要注意到優(yōu)先因子的級(jí)別。

7、當(dāng)檢驗(yàn)數(shù)按優(yōu)先級(jí)別從高到低已滿足注意到優(yōu)先因子的級(jí)別。當(dāng)檢驗(yàn)數(shù)按優(yōu)先級(jí)別從高到低已滿足最優(yōu)性條件時(shí)，且無(wú)法進(jìn)一步優(yōu)化時(shí)，從單純形表上就可以得最優(yōu)性條件時(shí)，且無(wú)法進(jìn)一步優(yōu)化時(shí)，從單純形表上就可以得到目標(biāo)規(guī)劃的最優(yōu)解或滿意解。到目標(biāo)規(guī)劃的最優(yōu)解或滿意解。7目標(biāo)規(guī)劃目標(biāo)規(guī)劃 Goal Programming（GP）例：例：現(xiàn)有如下目標(biāo)規(guī)劃問(wèn)題現(xiàn)有如下目標(biāo)規(guī)劃問(wèn)題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當(dāng)前基變量：當(dāng)前基變量： x3 ，d1- ， d2- ， d3- 。8目標(biāo)規(guī)劃目標(biāo)規(guī)劃 Goal Programming（GP）目標(biāo)規(guī)劃問(wèn)題的單純形表：目標(biāo)規(guī)劃問(wèn)題的單純形表：cj000P100P2P30CB基基解解x1x2x3d1-d1+d2-d2+d3-d3+0 x3605101000000P1d1-01-201-100000d2-36440001-100P3d3-4868000001-1 j P11P21P31P1-121P3-6-819目標(biāo)規(guī)劃目標(biāo)規(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目標(biāo)規(guī)劃目標(biāo)規(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目標(biāo)規(guī)劃目標(biāo)規(guī)劃 Goal Programming（GP）第第5 5節(jié)節(jié) 目標(biāo)規(guī)劃應(yīng)用問(wèn)題

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

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