运筹学试题01答案

1、一、有如下线性规划问题，令x6，x7分别为约束条件（1）和（2）的松弛变量，指出下表各组解的类型（1、可行解，2、非可行解，3、基础可行解，4、基础非可行解） 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、基础可行解；3、基础非可行解；4、可行解；5、非可行解。二、设某一线性规划问题的数学模型如下：设x3,x4为引入的松弛变量。经过求解得到问题的最优单纯行表如下： 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利用问题的线性规模数学模型和最优单纯行表求系数C1 C2和b1 b2解：1）对最优单纯行表进行反初等变换所以，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三、线性规划问题max z=CX，AX=B，X0，设X(0)为问题的最优解。若目标函数中用C*替代C后，问题的最优解变为X*，求证 （C*-C）(X*-X(0) 0证：因为X(0)为问题max z=CX，AX=B，X0，的最优解，而X*为问题max z=CX，AX=B，X0，的可行解，所以有 CX(0) CX* 即 CX(0) - CX* 0 (1)又因为X*为问题max z=C*X，AX=B，X0，的最优解，而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，证毕。四、有一线性规划，原问题目标函数为Max型，有三个决策变量，第一行约束为 型，对应松弛变量为x4， 第二行约束为 型，对应剩余变量为x5，第三行约束为 型，对应松弛变量为x6，用原单纯型法求解得到的该线性规划的最优单纯行表如下： cj1051000CBXBbx1x2x3x4x5x65x25010101/21x3000112110 x10100011OBJ=25zj1051486.5cjzj00048-6.51）该线性规划问题最优解出现什么

5、现象；2）求x1, x2 ,x3对应的原技术系数矩阵A；解：1）退化现象；2）利用反初等变换可得（注意到：x4 ，x6为松弛变量，x5为剩余变量）010101/2001121100011010101/2011023/2100011010101/201/21/2013/4100011010101/201/21/2013/411/21/2001/4010101/201/21/2013/4422001221100322010422001221322422五、下表中给出某求极大化问题的单纯形表，问表中g1，g2，d的取值范围如何以及x3，x4，x5为何种变量时有：1）表中有唯一最优解；2）表中有多(最

6、优)解；3）下一步迭代将以x1替换基变量x5；4）该线性规划问题无可行解。XB bx1x2x3x4x5x3 dx4 2x5 34-133-5-3100010001 cj - zjg1g2000解：1）d0，g10，g20，且g1g2，d4；4）d0，g10，g20，且x3，x4，x5至少一个为人工变量。六、设某投资者有3万元可供为期四年的投资。现有下列五个投资机会可供选择：A：在四年内，投资者可在每年年初投资，每年每元投资可获利0.2元，每年获利后可将本利重新投资。B：在四年内，投资者应在第一年年初或第三年年初投资，每两年每元投资可获利润0.5元，两年后获利。然后可将本利再重新投资。C：在四年

7、内，投资者应在第一年年初投资，三年后每元投资可获利0.8元。获利后可将本利重新投资。这项投资最多不超过2万元。D：在四年内，投资者应在第二年年初投资，两年后每元投资可获利0.6元。获利后可将本利重新投资。这项投资最多不超过1.5万元。E：在四年内，投资者应在第一年年初投资，四年后每元投资可获利1.7元。这项投资最多不超过2万元。投资者四年内应如何投资，使他在四年后所获利润达到最大？写出这个问题的线性规划模型，不用求解。解：设xij为第i年初投资第j个投资机会的资金数，f(x)为总利润，为了直观说明，我们用表格形式列出年初投资表和年末资金（本金+利润）表年初投资表ABCDE1x11x12x13x152x21x243x31x324x41年末资金（本金+利润）表ABCDE11.2 x11