解答-運籌學(xué)-第一章-線性規(guī)劃及其單純形法習(xí)題

1、整理ppt1課后練習(xí)（一）1 用圖解法求下列線性規(guī)劃問題，并指出問題具有唯一最優(yōu)解、無窮多最優(yōu)解、無界界還是無可行解。12121212max3222. . 3412,0Zxxxxstxxx x121212max610120. .51038Zxxxxstxx12121212max5622. .232,0Zxxxxs txxxx12121212min23466.424,0Zxxxxs txxxx無可行解X*=(10, 6)無界解無窮多最優(yōu)解唯一解整理ppt22、將下述線性規(guī)劃問題化成標(biāo)準(zhǔn)形式123123123123min2234.260,0,Zxxxxxxstxxxxxx無約束1233412331

2、233412334max223()0()4.2()600,00Zxxxxxxxxxstxxxxxxxxxx解：整理ppt33 對下述線性規(guī)劃問題找出所有基解，指出那些是基可行解，并確定最優(yōu)值。234123412341min52322347. 22230(1,.,4)jZxxxxxxxxstxxxxxj關(guān)鍵：判斷2個列向量線性相關(guān)性，若線性無關(guān)，則成為基12342212A整理ppt412342212A序號向量組是否線性無關(guān)是否為基1p1 p22p1 p33p1 p44p2 p35p2 p46p3 p4p1 p2 p3 p4序號基基解是否為基可行解1p1 p2(-4, 11/2, 0 , 0)2p

3、1 p3(2/5, 0, 11/5 , 0)3p1 p4(-1/3, 0, 0, 11/6)4p2 p3(0, 1/2, 2, 0)5p2 p4(0, -1/2, 0, 2)6p3 p4(0, 0, 1, 1)整理ppt54、已知線性規(guī)劃問題 : 12131242515max35210.4.0Zxxxxxxxstxxxx序號X1X2X3X4X5A24300B100-504C30274D14.540-0.5E02562F04520下表中所列的解均滿足約束條件1-3，試指出表中哪些是可行解，哪些是基解，哪些是基可行解。1234整理ppt6101001201001001Ap1 p2 p3 p4 p5

4、101120010是基110100001是基010201100是基基解有(a), (b), (f); 基可行解有(a) (f). 可行解有(a), (c), (e), (f);整理ppt75 已知某線性規(guī)劃問題的約束條件為 1231241234512345225330.472850 xxxxxxstxxxxxxxxxx判斷下列各點是否為該線性規(guī)劃問題可行域上的頂點：(5,15,0,20,0)X (9,7,0,0,8)X (15,5,10,0,0)X 整理ppt82 11 001 3 01 04 7121A210131472不是基，故不是基解，更不可能是基可行解210130471是基，故(9,7

5、,0,0,8)X 是基解又由于其每個分量非負(fù)，故為基可行解(5,15,0,20,0)X 為非可行域上的點，故不是(9,7,0,0,0)X 整理ppt92 11 001 3 01 04 7121A211130471不是基，故不是基解，更不可能是基可行解(15,5,10,0,0)X 整理ppt10課后練習(xí)（二）1、分別用圖解法和單純形法求解下述線性規(guī)劃問題，并指出單純形法迭代的每一步相當(dāng)于圖解法可行域中的哪一個頂點12121212max105349. 528,0Zxxxxstxxx x122121212max25156224.5,0Zxxxxxstxxxx整理ppt11Cj比值CBXBb檢驗數(shù)jx

6、1x2x3x4105009341085201x3x4009/3=38/5 0 10 5 0 0檢驗數(shù)檢驗數(shù) j8/512/501/521/5014/51-3/5-80/5 010-2x3x10103/24檢驗數(shù)檢驗數(shù) j3/2015/14 -3/14x2x1510110-1/72/7-175/1000-5/14-25/14整理ppt12同理：（2） X*=(3.5, 1.5, 7.5, 0, 0) Z*=8.5整理ppt132 用單純形法求解下列線性規(guī)劃問題123123123123max2360210.200(1,2,3)jZxxxxxxxxxstxxxxj1234123412341234ma

7、x62108564420332825.423100(1,2,3,4)jZxxxxxxxxxxxxstxxxxxj整理ppt14Cj比比值值CBXBb檢驗數(shù)檢驗數(shù) j2-11000 x1x2x3x4x5x660311100101-120102011-1001x4x5x600002-1100060/3=2010/1=1020/1=20檢驗數(shù)檢驗數(shù) jx4x1x6020101-120103004-51-301002-30-11-2001-30-2030/4=7.5-10/2=5整理ppt15檢驗數(shù)檢驗數(shù) jx4x1x6020101-120103004-51-301002-30-11-2001-30-

8、2030/4=7.5-10/2=5檢驗數(shù)檢驗數(shù) j501-3/20-1/21/2x4x1x202-115101/201/21/2100011-1-2-2500-3/20-3/2-1/2整理ppt16同理：（2）為無界解整理ppt173 用單純形法中的大M法求解下列線性規(guī)劃問題，并指出屬那一類解化為標(biāo)準(zhǔn)式有12312312123min23428. 326,0Zxxxxxxstxxxxx123456712346125717max2300428. 3260ZxxxxxMxMxxxxxxstxxxxx 整理ppt18Cj比值CBXBb檢驗數(shù)jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0

9、 0 -M -M8 1 4 2 -1 0 1 00 -2 -3 -1 0 0 -M -Mx6x7-M-M6 3 2 0 0 -1 0 1Cj比值CBXBb檢驗數(shù)jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -M8 1 4 2 -1 0 1 014M 4M-2 6M-3 2M-1 -M -M 0 0 x6x7-M-M6 3 2 0 0 -1 0 1整理ppt19Cj比值CBXBb檢驗數(shù)jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -M8 1 4 2 -1 0 1 014M 4M-2 6M-3 2M-1 -M -M 0 0 x6x7-M-M6

10、 3 2 0 0 -1 0 123Cj比值CBXBb檢驗數(shù)jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -Mx2x7-3-M2 1/4 1 1/2 -1/4 0 1/4 02 5/2 0 -1 1/2 -1 -1/2 155133326002422424MMMMMM84/5整理ppt20Cj比值CBXBb檢驗數(shù)jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -Mx2x7-3-M2 1/4 1 1/2 -1/4 0 1/4 02 5/2 0 -1 1/2 -1 -1/2 155133326002422424MMMMMM84/5Cj比值CBXB

11、b檢驗數(shù)jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -Mx2x1-3-29/5 0 1 3/5 -3/10 1/10 3/10 -1/104/5 1 0 -2/5 1/5 -2/5 -1/5 2/5111170002222MM整理ppt214、求解線性規(guī)劃問題當(dāng)某一變量的取值無約束時，通常用 來替換，其中 ， 。試說明，能否在基變量中同時出現(xiàn)，為什么？ jjjxxx0jx 0jx不可能。因為jjPP 故0jjPP整理ppt225、 下表為用單純形法計算時某一步的表格。已知該線性規(guī)劃的目標(biāo)函數(shù)為 約束形式為 x3、x4為松弛變量，表中解代入目標(biāo)函數(shù)后得Z=1012m

12、ax53ZxxX1X2X3x4X3 2X1 acd0e101/51Cj-Zjb-1fg ag的值 表中給出的解是否為最優(yōu)解整理ppt23因為目標(biāo)函數(shù)值為10，而Z=5x1+3x2,由單純形表可知x1=a, x2=0， 故a = 2因為x1、x2為基變量，所以因當(dāng)滿足高斯消元的形式(proper form from Gaussian elimination), 故c=0, d=1, b=0; f=0由檢驗數(shù)的定義可知：1mjjiijicc a13 （00 e5）e=4/5 g=0（01/515）g=5整理ppt24a=2, b=0, c=0, d=1, e=4/5, f=0, g=-5由于所有檢

13、驗非正，故該解是最優(yōu)解這個表格為最終單純形表綜上所述：整理ppt256、已知某線性規(guī)劃問題的初始單純形表和用單純刑法迭代后得到的表如下所示，試求括弧中未知數(shù)al的值項目Cj-ZJX1 X2 X3 X4 X5X4X561(b) (c) (d) 1 0-1 3 (e) 0 1Cj-ZJX1X5(f)4(g) 2 -1 1/2 0(h) (i) 1 1/2 1(a)-12 0 00 -7 (j)(k) (l)整理ppt26首先由于x1、x5為基變量，故g=1, h=0, l = 0再有11/201/21B1/201211/211301bcdei那么 b=1 c=2 d=-1 c+3=i d+e=1b

14、=2c=4d=-2i=5e=2整理ppt27又有11/2061/2114fB b f=3還剩下檢驗數(shù) a、j、k1mjjiijicc a檢驗數(shù)的定義為如何求得c呢？整理ppt28對初始單純形表的檢驗數(shù)行即為目標(biāo)函數(shù)中的系數(shù)C。12345,1,2,0ca cccc 對迭代后的單純形表有：2217(2*0* )cci a=c1=3至此我們已獲得所有的目標(biāo)函數(shù)的系數(shù)j=2（3101）51mjjiijicc ak=0（31/201/2）3/2整理ppt29a=3, b=2, c=4, d=-2, e=2, f=3, g=1, h=0i=5, j=5, k=-3/2, l=0綜上所述：整理ppt307、

15、設(shè) 是線性規(guī)劃問題的最優(yōu)解。若目標(biāo)函數(shù)中用 代替 C后，問題的最優(yōu)解變?yōu)?0X0,maxXbAXCXzCX求證： 0)(0XXCC證明：因為0*0*0*0()0,()0CXCXC XXC XC XCXX故又有（1）（2）將（2）（1）有0)(0XXCC整理ppt31某廠生產(chǎn)I、II、III三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。設(shè)A工序可分別在設(shè)備A1或A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序。已知產(chǎn)品產(chǎn)品I可在A、B任何一種設(shè)備上加工； 產(chǎn)品產(chǎn)品II可在任何規(guī)格的A設(shè)備上加工，但完成B工序時， 只能在B1設(shè)備上加工； 產(chǎn)品產(chǎn)品III只能在A2和B2設(shè)備上加工。整理ppt32 設(shè)備

16、產(chǎn)品設(shè)備有效臺時設(shè)備加工費 I II IIIA151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料費0.250.350.50售價1.252.002.80整理ppt33 設(shè)備產(chǎn)品設(shè)備有效臺時設(shè)備加工費 I II IIIA151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料費0.250.350.50售價1.252.002.80產(chǎn)品I有6種加工方案（A1, B1）、(A1，B2)、(A1， B3) （A2, B1）、(A2，B2)、(A2， B3

17、)其各自產(chǎn)量分別用111213,xxx212223,xxx整理ppt34 設(shè)備產(chǎn)品設(shè)備有效臺時設(shè)備加工費 I II IIIA151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料費0.250.350.50售價1.252.002.80產(chǎn)品II有6種加工方案（A1, B1）、(A2，B1)其各自產(chǎn)量分別用 代表1121,yy整理ppt35 設(shè)備產(chǎn)品設(shè)備有效臺時設(shè)備加工費 I II IIIA151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料費0.250.350.50售價1.252.002.80產(chǎn)品III只有1種加工方案（A2, B2）其各自產(chǎn)量用 代表22z整理ppt36111213212221