目標規(guī)劃的圖解法

1、. 由于目標規(guī)劃是在線性規(guī)劃的基礎(chǔ)上建立，并彌由于目標規(guī)劃是在線性規(guī)劃的基礎(chǔ)上建立，并彌補了部分不足所以兩種規(guī)劃模型結(jié)構(gòu)沒有本質(zhì)區(qū)別，補了部分不足所以兩種規(guī)劃模型結(jié)構(gòu)沒有本質(zhì)區(qū)別，解法也非常類似解法也非常類似形式上的區(qū)別形式上的區(qū)別主要在于：主要在于：線性規(guī)線性規(guī)劃只能處理一個目標，而目標規(guī)劃能統(tǒng)籌兼顧地處理劃只能處理一個目標，而目標規(guī)劃能統(tǒng)籌兼顧地處理關(guān)系，以求得切合實際需求的解；關(guān)系，以求得切合實際需求的解；線性規(guī)線性規(guī)劃是求滿足所有約束條件的最優(yōu)解，而目標規(guī)劃是要劃是求滿足所有約束條件的最優(yōu)解，而目標規(guī)劃是要在多個目標或約束條件下找到在多個目標或約束條件下找到；線線性規(guī)劃的約束條件是不分

2、主次地同等對待，而目標規(guī)性規(guī)劃的約束條件是不分主次地同等對待，而目標規(guī)劃可根據(jù)實際需要劃可根據(jù)實際需要 . 線性規(guī)劃是在可行解域內(nèi)尋找某一點，線性規(guī)劃是在可行解域內(nèi)尋找某一點，使單個目標達到最優(yōu)值（最大值或最小值）而目標規(guī)使單個目標達到最優(yōu)值（最大值或最小值）而目標規(guī)劃是在可行域內(nèi)，首先劃是在可行域內(nèi)，首先尋找到一個使尋找到一個使P1級目標均滿足的級目標均滿足的區(qū)域區(qū)域R1，然后，然后R1中中尋找一個使尋找一個使P2級目標級目標均滿足或均滿足或盡盡最大可能滿足的區(qū)域最大可能滿足的區(qū)域R2（ R1），再在，再在R2中尋找一個滿中尋找一個滿足足P3的各目標的區(qū)域的各目標的區(qū)域R3（ R2 R1），

3、），,如此下去，直到如此下去，直到尋找到一個區(qū)域?qū)ふ业揭粋€區(qū)域Rk( Rk-1 R1)，滿足，滿足Pk級的各目標級的各目標，這個這個，如果，如果，它只能滿足，它只能滿足P1,，Pi 級目標，而無法進一步改進，當(dāng)然，此時或許級目標，而無法進一步改進，當(dāng)然，此時或許有低于有低于Pi級目標被滿足，這純屬巧合級目標被滿足，這純屬巧合 .類似類似 根據(jù)決策變量（當(dāng)然不能多于根據(jù)決策變量（當(dāng)然不能多于2個）繪畫所有（軟、個）繪畫所有（軟、硬）約束條件的直線圖形，偏差變量以移動（平移）直線的硬）約束條件的直線圖形，偏差變量以移動（平移）直線的方法加以考慮方法加以考慮 重復(fù)第重復(fù)第3、4步過程，直到解區(qū)域步過

4、程，直到解區(qū)域Ri 減少到一點或滿減少到一點或滿 足足了所有了所有k個級別的目標為止，此時，個級別的目標為止，此時，Rk 即為這個目標規(guī)劃的最即為這個目標規(guī)劃的最優(yōu)解區(qū)域，其中的任何一點均為目標規(guī)劃的滿意解優(yōu)解區(qū)域，其中的任何一點均為目標規(guī)劃的滿意解 對對P1級的各目標，確定解區(qū)域級的各目標，確定解區(qū)域R1對下一個優(yōu)先級別對下一個優(yōu)先級別Pi 級各目標，確定它的最優(yōu)解空間級各目標，確定它的最優(yōu)解空間Ri ，但必須是，但必須是Ri Ri-1 ( i=2,3,) 在這個過程中，如果某解區(qū)域在這個過程中，如果某解區(qū)域Ri 減小到一點，則減小到一點，則 可結(jié)束這個過程，因為此時沒有進一步改進的可能可結(jié)

5、束這個過程，因為此時沒有進一步改進的可能. 求解下面目標規(guī)劃求解下面目標規(guī)劃: 112233121121121222Min 51060 ( )2 0 ( )s.t4 4 36 ZPdP dPdxxlxxddlxxdd31233412 ( )68 48 ( ),0,0,(1, 2, 3)iilxxddlx xddi將約束方程以直線形式畫在圖上，這里只使用決策變將約束方程以直線形式畫在圖上，這里只使用決策變量（即量（即 ），偏差變量在畫直線時被去掉，直線畫好后，），偏差變量在畫直線時被去掉，直線畫好后，在該直線上標出目標函數(shù)中與該直線相關(guān)的偏差變量增大時在該直線上標出目標函數(shù)中與該直線相關(guān)的偏差變

6、量增大時直線的平移方向（用垂直于直線的箭頭來反映）如圖直線的平移方向（用垂直于直線的箭頭來反映）如圖3-2 xx ,.1d2d3dl1l2l3l4oABCDEFx1x2圖圖3-2 圖解法示意圖圖解法示意圖112233121121121222Min 51060 ( )2 0 ( )s.t4 4 36 ZPdP dPdxxlxxddlxxdd31233412 ( )68 48 ( ),0,0,(1, 2, 3)iilxxddlx xddi. 這個區(qū)域內(nèi)的任一點均是該問題的滿意解，這個區(qū)域內(nèi)的任一點均是該問題的滿意解，可使目標函數(shù)可使目標函數(shù) zmin 由于由于C、D、E、F 坐標分別為坐標分別為(

7、6, 3)、(9, 0)、(8，0)、(4.8 , 2.4)， 故滿意解可表示為：故滿意解可表示為：).,.( ).,.(),(),(),(),(xx其中：其中：),(,ii 這種滿足所有目標要求的情況，即：這種滿足所有目標要求的情況，即： ，在實際中并不多見，很多目標規(guī)劃問題只能滿足前在實際中并不多見，很多目標規(guī)劃問題只能滿足前面幾級目標要求面幾級目標要求 0minz. 用圖解法求解下面目標規(guī)劃問題：用圖解法求解下面目標規(guī)劃問題：11223312111122221233Min 10 ( )2 26 ( ) 2 6 ZPdPdPdxxddlxxddlxxdd312 ( ),0,0,(1,2,3

8、)iilx xddi作圖作圖3-3： .l1x1x2o1d2d3dl2l3(10, 0) 圖圖3-3 圖解法示意圖圖解法示意圖AB考慮考慮P2 級目標，由于直線級目標，由于直線 l2 與與R1不相不相交，所以在交，所以在R1 內(nèi)無法使內(nèi)無法使 因此因此在不退化在不退化P1 級目標時，不可能使級目標時，不可能使P2 級級目標完全滿足這樣目標完全滿足這樣R2 就縮為一點，就縮為一點，因為在因為在R1中，使中，使 達到最小的為達到最小的為A點，點，所以：所以：x* = (10 ,0), 02ddd11223312111122221233Min 10 ( )2 26 ( ) 2 6 ZPdPdPdxx

9、ddlxxddlxxdd312 ( ),0,0,(1,2,3)iilx xddi.由于由于R2僅含有一個點，所以對僅含有一個點，所以對P3級目標，我們已級目標，我們已經(jīng)無法進一步的選擇與考慮，可求得經(jīng)無法進一步的選擇與考慮，可求得 ，即目標函數(shù)為：即目標函數(shù)為：dPPzmin 此例中，之所以產(chǎn)生解域此例中，之所以產(chǎn)生解域R2退縮為一個點，退縮為一個點，從而無法使從而無法使P2，P3級目標達成，是因為級目標達成，是因為P2級目標級目標的期望值定得過高如果將它的目標值從的期望值定得過高如果將它的目標值從26降到降到14，則可考慮到，則可考慮到P3級目標，見圖級目標，見圖3-4. 滿足滿足P1、P2

10、級目標的可行解域為級目標的可行解域為R2，l1x1x2o1d2d3dl2l3(10, 0)使使P1,P2,P3級目標完全滿足，這時問題的滿意解不唯一一級目標完全滿足，這時問題的滿意解不唯一一般地，目標要求確定得越低，可供選擇的解越多，目標定般地，目標要求確定得越低，可供選擇的解越多，目標定得太高，滿意解的選擇余地也越小，甚至一些低級別的目得太高，滿意解的選擇余地也越小，甚至一些低級別的目標無法實現(xiàn)標無法實現(xiàn)進一步考察進一步考察P3級目級目 標可得最優(yōu)解區(qū)域標可得最優(yōu)解區(qū)域R3，對該區(qū)域中任意一點，均同時能對該區(qū)域中任意一點，均同時能圖圖3-4.4 , 3 , 2 , 1, 0,30245040

11、)2(min21442331222111214332211iddxxddxddxddxxddxxddPdPdPzii滿足約束條件：目標函數(shù)： 求解下面目標規(guī)劃求解下面目標規(guī)劃: .用圖解法求解，見圖4.2。4 , 3 , 2 , 1, 0,30245040)2(min21442331222111214332211iddxxddxddxddxxddxxddPdPdPzii.從圖4.2中看到 在考慮具有P1、P2的目標實現(xiàn)后，x1、x2的取值范圍為ABCD?？紤]P3的目標要求時，因d3的權(quán)系數(shù)大于d4，故先考慮min d3；這時x1、x2的取值范圍縮小為ABEF區(qū)域。然后考慮d4。在ABEF中無法

12、滿足d4=0，因此只能在ABEF中取一點，使d4盡可能小，這就是E點。故E點為滿意解。其坐標為(24，26)，.在目標規(guī)劃中，考慮低級別目標時，不能在目標規(guī)劃中，考慮低級別目標時，不能破壞已經(jīng)滿足的高級別目標，這是基本原則但它并不破壞已經(jīng)滿足的高級別目標，這是基本原則但它并不是說，當(dāng)某一高級別目標不可能滿足時，其后的低級別是說，當(dāng)某一高級別目標不可能滿足時，其后的低級別目標就一定不能滿足而是在有些目標規(guī)劃中，當(dāng)某一目標就一定不能滿足而是在有些目標規(guī)劃中，當(dāng)某一優(yōu)先級的目標不能優(yōu)先級的目標不能滿足時，其后的某滿足時，其后的某些低級別目標仍可些低級別目標仍可能被滿足能被滿足#.例例3.5 用圖解法

13、求解目標規(guī)劃用圖解法求解目標規(guī)劃)3()()(min323322111ddpddpddpf)3 , 2 , 1(0,40603750251521332122211121iddxxddxxddxxddxxii S , t(利潤利潤)(裝配裝配)(檢驗檢驗).X2X1102030400102030405060750251521xxAB1d1dFE2d2d60321xxCG3d3d4021 xxHIDP1級目標：級目標： 線段線段AB：P1P2級目標：級目標： 線段線段 HI：故故I點為最優(yōu)解。點為最優(yōu)解。P1P2+P3級目標：級目標：H點：點：(25,15)3230min.10pfdI點：點：(37.5,7.5)335min. 5pfdI)3 ()()(min323322111ddpddpddpf) 3 , 2 , 1( 0,40603750251521332122211121iddxxddxxddxxddxxii.210100012100180512 30032 )(min 21422213112