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

《解答-運籌學-第一章-線性規(guī)劃及其單純形法習題》由會員分享，可在線閱讀，更多相關《解答-運籌學-第一章-線性規(guī)劃及其單純形法習題（37頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,課后練習（一）,1,用圖解法求下列線性規(guī)劃問題，并指出問題具有唯一最優(yōu)解、無窮多最優(yōu)解、無界界還是無可行解。,無可行解,X*=(10,6),無界解,無窮多最優(yōu)解,唯一解,2,、將下述線性規(guī)劃問題化成標準形式,解：,3,對下述線性規(guī)劃問題找出所有基解，指出那些是基可行,解，并確定最優(yōu)值。,關鍵：判斷,2,個列向量線性相關性，若線性無關，則成為基,序號,向量組,是否線性無關,是否為基,1,p1 p2,2,p1 p3,3,p1

2、 p4,4,p2 p3,5,p2 p4,6,p3 p4,p,1,p,2,p,3,p,4,序號,基,基解,是否為基可行解,1,p1 p2,(-4,11/2,0,0),2,p1 p3,(2/5,0,11/5,0),3,p1 p4,(-1/3,0,0,11/6),4,p2 p3,(0,1/2,2,0),5,p2 p4,(0,-1/2,0,2),6,p3 p4,(0,0,1,1),4,、已知線性規(guī)劃問題,:,序號,X1,X2,X3,X4,X5,A,2,4,3,0,0,B,10,0,-5,0,4,C,3,0,2,7,4,D,1,4.5,4,0,-0.5,E,0,2,5,6,2,F,0,4,5,2,0,下

3、表中所列的解均滿足約束條件,1-3,，試指出表中哪些是可行解，哪些是基解，哪些是基可行解。,12,34,p,1,p,2,p,3,p,4,p,5,是基,是基,是基,基解有,(a),(b),(f);,基可行解有,(a)(f).,可行解有,(a),(c),(e),(f);,5,已知某線性規(guī)劃問題的約束條件為,判斷下列各點是否為該線性規(guī)劃問題可行域上的頂點：,不是基，故,不是基解，更不可能是基可行解,是基，故,是基解,又由于其每個分量非負，故為基可行解,為非可行域上的點，故不是,不是基，故,不是基解，更不可能是基可行解,課后練習（二）,1,、分別用圖解法和單純形法求解下述線性規(guī)劃問題，并指出單純形法迭

4、代的每一步相當于圖解法可行域中的哪一個頂點,C,j,比,值,C,B,X,B,b,檢驗數(shù),j,x,1,x,2,x,3,x,4,10,5,0,0,9,3,4,1,0,8,5,2,0,1,x,3,x,4,0,0,9/3=3,8/5,0 10 5 0 0,檢驗數(shù),j,8/5,1,2/5,0,1/5,21/5,0,14/5,1,-3/5,-80/5,0,1,0,-2,x,3,x,1,0,10,3/2,4,檢驗數(shù),j,3/2,0,1,5/14,-3/14,x,2,x,1,5,10,1,1,0,-1/7,2/7,-175/10,0,0,-5/14,-25/14,同理：,（,2,）,X*=(3.5,1.5,7

5、.5,0,0)Z*=8.5,2,用單純形法求解下列線性規(guī)劃問題,C,j,比,值,C,B,X,B,b,檢驗數(shù),j,2,-1,1,0,0,0,x,1,x,2,x,3,x,4,x,5,x,6,60,3,1,1,1,0,0,10,1,-1,2,0,1,0,20,1,1,-1,0,0,1,x,4,x,5,x,6,0,0,0,0,2,-1,1,0,0,0,60/3=20,10/1=10,20/1=20,檢驗數(shù),j,x,4,x,1,x,6,0,2,0,10,1,-1,2,0,1,0,30,0,4,-5,1,-3,0,10,0,2,-3,0,-1,1,-20,0,1,-3,0,-2,0,30/4=7.5,-,

6、10/2=5,檢驗數(shù),j,x,4,x,1,x,6,0,2,0,10,1,-1,2,0,1,0,30,0,4,-5,1,-3,0,10,0,2,-3,0,-1,1,-20,0,1,-3,0,-2,0,30/4=7.5,-,10/2=5,檢驗數(shù),j,5,0,1,-3/2,0,-1/2,1/2,x,4,x,1,x,2,0,2,-1,15,1,0,1/2,0,1/2,1/2,10,0,0,1,1,-1,-2,-25,0,0,-3/2,0,-3/2,-1/2,同理：,（,2,）為無界解,3,用單純形法中的大,M,法求解下列線性規(guī)劃問題，并指出屬那一類解,化為標準式有,C,j,比,值,C,B,X,B,b,

7、檢驗數(shù),j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,8 1 4 2 -1 0 1 0,0 -2 -3 -1 0 0 -M -M,x,6,x,7,-M,-M,6 3 2 0 0 -1 0 1,C,j,比,值,C,B,X,B,b,檢驗數(shù),j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,8 1 4 2 -1 0 1 0,14M 4M-2 6M-3 2M-1-M -M 0 0,x,6,x,7,-M,-M,6 3 2 0 0 -1 0 1,C,j,比,值,C,B,X,B,b,檢驗數(shù),j,x,1,x,2

8、,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,8 1 4 2 -1 0 1 0,14M 4M-2 6M-3 2M-1-M -M 0 0,x,6,x,7,-M,-M,6 3 2 0 0 -1 0 1,2,3,C,j,比,值,C,B,X,B,b,檢驗數(shù),j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,x,2,x,7,-3,-M,2 1/4 1 1/2 -1/4 0 1/4 0,2 5/2 0 -1 1/2 -1 -1/2 1,8,4/5,C,j,比,值,C,B,X,B,b,檢驗數(shù),j,x,1,x,2,x,3,x,4

9、,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,x,2,x,7,-3,-M,2 1/4 1 1/2 -1/4 0 1/4 0,2 5/2 0 -1 1/2 -1 -1/2 1,8,4/5,C,j,比,值,C,B,X,B,b,檢驗數(shù),j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,x,2,x,1,-3,-2,9/5 0 1,3/5-3/10 1/10 3/10 -1/10,4/5 1 0 -2/5 1/5-2/5 -1/5 2/5,4,、求解線性規(guī)劃問題當某一變量的取值無約束時，通常用 來替換，其中 ，。試說明，能否在基變量中同時

10、出現(xiàn)，為什么？,不可能,。因為,故,5,、下表為用單純形法計算時某一步的表格。已知該線性規(guī)劃的目標函數(shù)為 約束形式為,x,3,、,x,4,為松弛變量，表中解代入目標函數(shù)后得,Z=10,X,1,X,2,X,3,x,4,X,3,2,X,1,a,c,d,0,e,1,0,1/5,1,C,j,-Z,j,b,-1,f,g,ag,的值,表中給出的解是否為最優(yōu)解,因為目標函數(shù)值為,10,，而,Z=5x,1,+3x,2,由單純形表可知,x,1,=a,x,2,=0,，故,a=2,因為,x1,、,x2,為基變量，所以因當滿足高斯消元的形式,(proper form from Gaussian elimination

11、),故,c=0,d=1,b=0;f=0,由檢驗數(shù)的定義可知：,1,3,（,00,e5,）,e=4/5,g=0,（,01/5,15,）,g=,5,a=2,b=0,c=0,d=1,e=4/5,f=0,g=-5,由于所有檢驗非正，故該解是最優(yōu)解,這個表格為最終單純形表,綜上所述：,6,、已知某線性規(guī)劃問題的初始單純形表和用單純刑法迭代后得到的表如下所示，試求括弧中未知數(shù),al,的值,項目,C,j,-Z,J,X,1,X,2,X,3,X,4,X,5,X,4,X,5,6,1,(b)(c)(d)1 0,-1 3 (e)0 1,C,j,-Z,J,X,1,X,5,(f),4,(g)2 -1 1/2 0,(h)(

12、i)1 1/2 1,(a)-12 0 0,0-7(j)(k)(l),首先由于,x,1,、,x,5,為基變量，故,g=1,h=0,l=0,再有,那么,b=1,c=2,d=-1,c+3=i,d+e=1,b=2,c=4,d=-2,i=5,e=2,又有,f=3,還剩下檢驗數(shù),a,、,j,、,k,檢驗數(shù)的定義為,如何求得,c,呢？,對初始單純形表的檢驗數(shù)行即為目標函數(shù)中的系數(shù),C,。,對迭代后的單純形表有：,a=c1=3,至此我們已獲得所有的目標函數(shù)的系數(shù),j=2,（,3,1,01,）,5,k=0,（,31/2,01/2,）,3/2,a=3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=

13、5,j=5,k=-3/2,l=0,綜上所述：,7,、設 是線性規(guī)劃問題,的最優(yōu)解。若目標函數(shù)中用 代替,C,后，問題的最,優(yōu)解變?yōu)?求證：,證明：因為,（,1,）,（,2,）,將（,2,）（,1,）有,某廠生產(chǎn),I,、,II,、,III,三種產(chǎn)品，都分別經(jīng),A,、,B,兩道工序加工。設,A,工序可分別在設備,A1,或,A2,上完成，有,B1,、,B2,、,B3,三種設備可用于完成,B,工序。,已知,產(chǎn)品,I,可在,A,、,B,任何一種設備上加工；,產(chǎn)品,II,可在任何規(guī)格的,A,設備上加工，但完成,B,工序時，,只能在,B1,設備上加工；,產(chǎn)品,III,只能在,A2,和,B2,設備上加工。,設

14、備,產(chǎn)品,設備有效臺時,設備加工費,I,II,III,A1,5,10,6000,0.05,A2,7,9,12,10000,0.03,B1,6,8,4000,0.06,B2,4,11,7000,0.11,B3,7,4000,0.05,原料費,0.25,0.35,0.50,售價,1.25,2.00,2.80,設備,產(chǎn)品,設備有效臺時,設備加工費,I,II,III,A1,5,10,6000,0.05,A2,7,9,12,10000,0.03,B1,6,8,4000,0.06,B2,4,11,7000,0.11,B3,7,4000,0.05,原料費,0.25,0.35,0.50,售價,1.25,2.0

15、0,2.80,產(chǎn)品,I,有,6,種加工方案（,A1,B1,）、,(A1,，,B2),、,(A1,，,B3),（,A2,B1,）、,(A2,，,B2),、,(A2,，,B3),其各自產(chǎn)量分別用,設備,產(chǎn)品,設備有效臺時,設備加工費,I,II,III,A1,5,10,6000,0.05,A2,7,9,12,10000,0.03,B1,6,8,4000,0.06,B2,4,11,7000,0.11,B3,7,4000,0.05,原料費,0.25,0.35,0.50,售價,1.25,2.00,2.80,產(chǎn)品,II,有,6,種加工方案（,A1,B1,）、,(A2,，,B1),其各自產(chǎn)量分別用 代表,設備,產(chǎn)品,設備有效臺時,設備加工費,I,II,III,A1,5,10,6000,0.05,A2,7,9,12,10000,0.03,B1,6,8,4000,0.06,B2,4,11,7000,0.11,B3,7,4000,0.05,原料費,0.25,0.35,0.50,售價,1.25,2.00,2.80,產(chǎn)品,III,只有,1,種加工方案（,A2,B2,）,其各自產(chǎn)量用 代表,