1、第二節(jié) 目的規(guī)劃問題的圖解法 minZ= d- 100X1+80X2 -d+d- =100004X1+2X2 4002X1+4X2 500X1 , X2 , d- , d+ 0 d+.d- =0例11.X2X1O50100501001252X1+4X2 = 5004X1+2X2 = 400CEB絕對約束可行域OBEC2.X2X1O50100501001252X1+4X2 = 500100X1+80X2 = 100004X1+2X2 = 400CEBd+目的約束稱心域BEC3.(1) 絕對約束可行域OBEC(2) 目的約束稱心域BEC(3) 多個可行稱心解： (60,50),10000; (70

2、,50),11000; E(50,100),13000。(4) Zmin =04.例2minZ=P1d1+P2(d2-+d2+)+P3(d3-)2X1+X2 11X1 -X2+d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 05.111057X2X1AB2X1+X2 =11O可行域OAB6.111010557X2X1ABCDEFd2+d1-d3+X1+2X2 = 10X1 -X2=08X1+10X2=562X1+X2 =11O可行域OAB 目的1： OBC 目的2：ED線段 目的3：GD線段G7.解

3、： 可行域OAB 目的1： OBC 目的2：ED線段 目的3：GD線段 用 8X1+10X2=56 X1+ 2X2=10求G=(2,4)利潤=568. X1 -X2=0 X1+2X2=10D=(10/3,10/3)利潤=60解為X= = + (1-) (0 1)X1 2 10/3 X2 4 10/3 Zmin =09.例3minZ=P1d1-+P2d2+P3(2d3-+d4-)X1+X2 +d1- -d1+=40 X1 +X2+d2- -d2+=50 X1 +d3- -d3+=24 X2+d4- -d4+=30 10.X230304050X1OBACDEFd3+d4+d1+d2-X1+X2 =

4、40X1+X2 =50X2 =30X1 =24解：G11.(1)、滿足目的、的稱心域為ABCD(2)、先思索的稱心域為ABEF再思索，無公共稱心域。(3)、EX1+X2=50X1=24E(24,26)GX1+X2=50X2=30G(20,30)12.(4)、d4- =30 - X2 + d4+=30-26=40由于 X2+d4- - d4+=30所以 d4- =30 X2 + d4+ZE= P3d4- =P3 (30-x2+d4+)=P3( 30-26)=4P3而由于 x1+d3- - d3+ =24ZG= P3*2d3- =P3*2(24-20)=8P3所以，取E點13.6.3 目的規(guī)劃問題

5、的單純形法 目的規(guī)劃的數(shù)學(xué)模型，特別是約束的構(gòu)造與線性規(guī)劃模型沒有本質(zhì)的區(qū)別，只是它的目的不止是一個，雖然其利用優(yōu)先因子和權(quán)系數(shù)把目的寫成一個函數(shù)的方式，但在計算中無法按單目的處置，所以可用單純形法進展適當(dāng)改良后求解。在組織、構(gòu)造算法時，我們要思索目的規(guī)劃的數(shù)學(xué)模型一些特點，作以下規(guī)定： (1) 由于目的規(guī)劃問題的目的函數(shù)都是求最小化，所以檢驗數(shù)的最優(yōu)準(zhǔn)那么與線性規(guī)劃是相反的；一、目的規(guī)劃問題單純形法的特點 14. (2) 由于非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子， Pi Pi+1，i = 1,2,L-1. 于是從每個檢驗數(shù)的整體來看： Pi+1i = 1,2,L-1優(yōu)先級第k個檢驗數(shù)的正

6、、負首先決議于 P1 ，P2 ， ，Pi 優(yōu)先級第k個檢驗數(shù)的正、負。假設(shè)P1 級第k個檢驗數(shù)為0，那么此檢驗數(shù)的正、負取決于P2級第k個檢驗數(shù)；假設(shè)P2 級第k個檢驗數(shù)仍為0，那么此檢驗數(shù)的正、負取決于P3級第k個檢驗數(shù)，依次類推。換一句話說，當(dāng)某Pi 級第k個檢驗數(shù)為負數(shù)時，計算中不用再調(diào)查Pj j i 級第k個檢驗數(shù)的正、負情況； 15.3根據(jù)LGP模型特征，當(dāng)不含絕對約束時，di- i=1,2, ,K構(gòu)成了一組根本可行解。在尋覓單純形法初始可行點時，這個特點是很有用。16. 二、目的規(guī)劃問題單純形法的計算步驟 (1)建立初始單純形表在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行。初始的檢驗

7、數(shù)需根據(jù)初始可行解計算出來，方法同根本單純形法。當(dāng)不含絕對約束時，di- i=1,2, ,K構(gòu)成了一組根本可行解，即可得到初始單純形表。17. (2)確定換入變量：按優(yōu)先級順序，檢查檢驗數(shù)能否存在負值，選取優(yōu)先級最高的最小負值對應(yīng)的變量入基； (3)按單純形法中的最小比值規(guī)那么確定換出變量，當(dāng)存在兩個和兩個以上一樣的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量； 18. (4)按單純形法進展基變換運算，建立新的單純形表； (5)迭代計算停頓判別準(zhǔn)那么：假設(shè)各優(yōu)先級的檢驗數(shù)均為非負；某一優(yōu)先級有負檢驗數(shù)，但是該負檢驗數(shù)對應(yīng)的上一級優(yōu)先級的檢驗數(shù)為正檢驗數(shù)。 19.三、運用實例 Min P1(

8、d1-+d2+), P2d3- x1 +d1- -d1+=10 2x1+ x2 +d2- -d2+ =40 3x1+2x2 +d3- -d3+=100 x1 , x2 , di- ,di+ 020.例 Min P1d1-, P2d2+, P3d3- 5x1+10 x2 60 x1- 2x2 +d1- -d1+=0 4x1+4x2 +d2- -d2+ =36 6x1+8x2 +d3- -d3+=48 x1 , x2 , di- ,di+ 0+x3=6021.000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0 x3605101000000p1d1-01-201-1

9、00000d2-36440001-100p3d3-4868000001-1p1-120010000p2000000100p3-6-8000000122.000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0 x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1p1-120010000p2000000100p3-6-8000000123.000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0 x3600201-5500000 x101-201-100000d2-

10、360120-441-100p3d3-480200-66001-1p1000100000p2000000100p30-2006-6000124.000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0 x3600201-5500000 x101-201-100000d2-360120-441-100p3d3-480200-66001-1p1000100000p2000000100p30-2006-6000125.000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0 x3120011-100-110 x124/51002/5-0.400

11、0.1-0.10d2-36/5000-2/50.41-1-0.60.60 x212/5010-0.30.3000.05-0.05p1000100000p2000000100p300000001026.因有兩個非基變量的檢驗數(shù)為0，所以，有無窮多解。27.例 試用單純形法來求解Min z= P1d1+ + d2+ ) + P2 d3+ + P3 d4- + P4d1- + 2d2- )x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 12x1 + 18x2 +d4- -d4+ =252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4. 28.解: 由于P1 , P2 優(yōu)先級對應(yīng)的目的函數(shù)中不含di- , 所以其檢驗數(shù)只需取系數(shù)。分別為 ( 0，0，0，1，0，1，0，0，0，0)和 ( 0，0，0， 0，0，0，0，1，0，0) 29.x1x2d1-d1+d2-d2+d3-d3+d4-d4+bP10001010000P20000000100P3-12-1800000001P4-1-201020000d1-101-10000