運籌學(xué)試題01答案

1、一、有如下線性規(guī)劃問題，令x6，x7分別為約束條件（1）和（2）的松弛變量，指出下表各組解的類型（1、可行解，2、非可行解，3、基礎(chǔ)可行解，4、基礎(chǔ)非可行解） Max f(x) = 3x1+2x2+5x3+x4+2x5 x1+2x2+x3+x4+2x5430 (1) 4x1 +2x3+3x4+6x51290 (2) x1 ,x2 ,x3 ,x4 ,x50 x J解x1 x2 x3 x4 x5 x6 x7解的類別一20 30 40 50 0 260 550 二 0 0 0 0 0 430 1290三 0 0 645 0 0 -215 0四 0 0 0 230 100 0 0五300 70 0 0

2、 0 -10 90解：基本思路參見教材P21：1、非可行解（第二約束方程不滿足）；2、基礎(chǔ)可行解；3、基礎(chǔ)非可行解；4、可行解；5、非可行解。二、設(shè)某一線性規(guī)劃問題的數(shù)學(xué)模型如下：設(shè)x3,x4為引入的松弛變量。經(jīng)過求解得到問題的最優(yōu)單純行表如下： CjC1C2 0 0 CB XB b x1 x2 x3 x4 C1 x1 1 1 0 3 -1 C2 x2, 2 0 1 -1 1 j 0 0 -3 -1利用問題的線性規(guī)模數(shù)學(xué)模型和最優(yōu)單純行表求系數(shù)C1 C2和b1 b2解：1）對最優(yōu)單純行表進行反初等變換所以，b1=3/2, b2=7/2.又由3=c3 - z3 得 -3= 0 (3c1-c2由4

3、=c4 z4 得 -1= 0 (-c1+c2) (2)解方程（1）和（2）得c1=2,c2=3三、線性規(guī)劃問題max z=CX，AX=B，X0，設(shè)X(0)為問題的最優(yōu)解。若目標(biāo)函數(shù)中用C*替代C后，問題的最優(yōu)解變?yōu)閄*，求證 （C*-C）(X*-X(0) 0證：因為X(0)為問題max z=CX，AX=B，X0，的最優(yōu)解，而X*為問題max z=CX，AX=B，X0，的可行解，所以有 CX(0) CX* 即 CX(0) - CX* 0 (1)又因為X*為問題max z=C*X，AX=B，X0，的最優(yōu)解，而X(0)為問題max z=C*X，AX=B，X0，的可行解，所以有 C*X* C*X(0)

4、 即C*X* - C*X(0) 0 （2）（1）+（2）得CX(0) - CX* + C*X* - C*X(0)0，即（C*-C）(X*-X(0) 0，證畢。四、有一線性規(guī)劃，原問題目標(biāo)函數(shù)為Max型，有三個決策變量，第一行約束為 型，對應(yīng)松弛變量為x4， 第二行約束為 型，對應(yīng)剩余變量為x5，第三行約束為 型，對應(yīng)松弛變量為x6，用原單純型法求解得到的該線性規(guī)劃的最優(yōu)單純行表如下： cj1051000CBXBbx1x2x3x4x5x65x25010101/21x3000112110 x10100011OBJ=25zj1051486.5cjzj00048-6.51）該線性規(guī)劃問題最優(yōu)解出現(xiàn)什么

5、現(xiàn)象；2）求x1, x2 ,x3對應(yīng)的原技術(shù)系數(shù)矩陣A；解：1）退化現(xiàn)象；2）利用反初等變換可得（注意到：x4 ，x6為松弛變量，x5為剩余變量）010101/2001121100011010101/2011023/2100011010101/201/21/2013/4100011010101/201/21/2013/411/21/2001/4010101/201/21/2013/4422001221100322010422001221322422五、下表中給出某求極大化問題的單純形表，問表中g(shù)1，g2，d的取值范圍如何以及x3，x4，x5為何種變量時有：1）表中有唯一最優(yōu)解；2）表中有多(最

6、優(yōu))解；3）下一步迭代將以x1替換基變量x5；4）該線性規(guī)劃問題無可行解。XB bx1x2x3x4x5x3 dx4 2x5 34-133-5-3100010001 cj - zjg1g2000解：1）d0，g10，g20，且g1g2，d4；4）d0，g10，g20，且x3，x4，x5至少一個為人工變量。六、設(shè)某投資者有3萬元可供為期四年的投資?，F(xiàn)有下列五個投資機會可供選擇：A：在四年內(nèi)，投資者可在每年年初投資，每年每元投資可獲利0.2元，每年獲利后可將本利重新投資。B：在四年內(nèi)，投資者應(yīng)在第一年年初或第三年年初投資，每兩年每元投資可獲利潤0.5元，兩年后獲利。然后可將本利再重新投資。C：在四年

7、內(nèi)，投資者應(yīng)在第一年年初投資，三年后每元投資可獲利0.8元。獲利后可將本利重新投資。這項投資最多不超過2萬元。D：在四年內(nèi)，投資者應(yīng)在第二年年初投資，兩年后每元投資可獲利0.6元。獲利后可將本利重新投資。這項投資最多不超過1.5萬元。E：在四年內(nèi)，投資者應(yīng)在第一年年初投資，四年后每元投資可獲利1.7元。這項投資最多不超過2萬元。投資者四年內(nèi)應(yīng)如何投資，使他在四年后所獲利潤達(dá)到最大？寫出這個問題的線性規(guī)劃模型，不用求解。解：設(shè)xij為第i年初投資第j個投資機會的資金數(shù)，f(x)為總利潤，為了直觀說明，我們用表格形式列出年初投資表和年末資金（本金+利潤）表年初投資表ABCDE1x11x12x13x152x21x243x31x324x41年末資金（本金+利潤）表ABCDE11.2 x11