运筹学期末试卷及答案_运筹学期末试卷答案

运筹学期末试卷及答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“运筹学期末试卷答案”。

一、判断题（21分）

1、可行解是基本可行解的充要条件是它的正分量所对应的A中列向量线性无关（）；

2、如果一个LP问题有最优解，则它的对偶问题也有最优解，且它们的最优解相等（）；

3、若线性规划问题有最优解，则一定有唯一的最优解（）；

4、若一个原始线性规划问题无界，则它的对偶问题也无界（）；

5、设f:RnR1在点xRn处的Hee矩阵2f(x)存在，若2f(x)0，并且2f(x)正定，则x是（UMP）的严格局部最优解（）；

6、若f:RnR1是S上的凸函数，任意实数0则f是S上的凸函数（）；

7、设SRn是非空开凸集，f:RnR1二阶连续可导，则f是S上的严格凸函数的充要条件是f的Hee矩阵2f(x)在 S上是正定的（）.二、1.将下面的线性规划问题化成标准形（7分）

2，写出下面线性规划的对偶规划（7分）

maxz4x15x26x3

minzx14x23x3

2x13x24x3105x2x8x20123 s.t

x12x25x39x1,x30,x2无约束.2x13x25x32xxx4123 s.t3x1x26x31x10,x30,x2为自由变量.三、证明题（10分）

设f:RnR1在点xRn处可微.若x是（UMP）的局部最优解，则f(x)0.四、用对偶单纯形法求解下列线性规划问题（10分）

minz15x124x25x3 6x2x32s.t5x2xx1231

xj0,j1,2,3

五、把线性规划问题（18分）

minZ2x1x2x3 x1x2x36s.tx2x4 记为（P）

12x1,x2,x30求（1）用单纯形算法解（p）；（2）c2由1变为(3)； 由64变为34 

六、用分枝定界法解下述ILP问题（10分）

maxzx1x2

2x1x25s.t4x1x22 x1,x20,且为整数

七、求以下无约束非线性规划问题的最优解（8分）

minf(xx221,2)x1x26x1x1x24x27

八、验证下列非线性规划为凸规划（9分）

minf(x)x2214x29x13x1x211 s.tg1(x)5x17x290gx)2x22x22(12x1x24x270

一、判断题（20分）

1.V;

2.X;

3.X;

4.X;

5.X ；

6.V 。

3）b

7.X（二、1.解：对自由变量x2用x4x5代替;对第一个不等式约束添加松弛变量x6,对第二个不等式约束添加剩余变量x7,再用zz代替原来的目标函数,便得到了标准形式的LP问题（2分）

minz4x15(x4x5)6x3

（4分）

s.t

2x13(x4x5)4x3105x2(xx)8xx2014536 x2(xx)5xx945371xj0,j1,3,4,5,6,7（8分）

2．解：这里c(1,4,3)T,b(2,4,1)T,根据定义，其对偶问题是

（2分）

max(21423)

（4分）

s.t

21233134123 56323110,30,2无约束（7分）

三、证明题（10分）

证：用反证法，若 f(x)0，现令Pf(x)，则有

（2分）

f(x)Pf(x)f(x)f(x)0（5分）

由定理，必存在0，使当t(0,)时，有

f(xtP)f(x)（8分）T2

成立

但这与假设矛盾.因此必有

f(x)0

（10分）

四、解：引进非负的剩余变量x40,x50,将不等式约束化为等式约束 6x2x3x42 5x12x2x3x51

x0,j1,,5j将等式两端同乘以（-1），就直接得到原问题一个基本（不可行）解和对偶问题的一个可行解（检验数向量0）其对应的单纯形标如下

1r161r2r13r04r13r221r1r243r0r22zx4x5152450005620z150051102x21011x511162034081106311133（6分）

1573170022225111x210444415131x3012222（8分）z

1117此时，b0,故原问题的最优解为x(0，)T，其最优值为。

422（10分）

五、解：（1）在约束条件中加入松弛变量x4,x5得

minz2x1x2x3

x1x2x3x46 s.tx12x2x5它的初始表

x1,,5j（2分）

z211000x4x511211060014r2r1rz2r1

1zx1x5031201210131111016（5分）100)其,最优值为z012。

此时检验数向量0,故最优解为x(6,0,T（6分）

(2)x1是非基变量11(c1c1)1（8分）

zx1x5011112012111101101r231r1r231rzr23

zx2004/37/31/346/310012/31/32/31/31/31/38/310/36x1

03（10分）,此时检验数向量0,故最优解为x(8/3,10/3,T0)其最优值为z046。（12分）3T(3)原问题的最优解为x(6,0,0),所对应的可行基B=A110 B1, 11

10A5=,1110331ccb6  故 bBb z1501147（16分）

从而新问题对应的单纯形表为

z x1x503120610131111013 7T,其0最优值为z06。由于b0，故最优解为x(3,0（18分）

六、解：用图解法解求ILP问题的松弛问题的最优解为(,)T,最优值为z0（2分）

它的最优解不符合整数的要求,可任选一个变量,如选择x17[]1,（4分）6786323。67进行分枝.由于6引进两个约束x11和x12生成两个子问题

maxzx1x2 maxzx1x2

s.t

2x1x254xx212x11x1,x20,且整数

(p1)

和

2x1x254xx212s.t(p2)（6分）

x21x1,x20,且整数ILP问题(p1)的松弛LP问题的最优解x1(1,2)T,最优值z3。(p2)的松弛LP问题的最优解

x2(2,1)T,最优值z3。

（8分）

由于33,故ILP问题的最优解x1(1,2)T,x2(2,1)T,最优值z3。

（10分）

2x1x26

七、解：目标函数的梯度向量为 f(x)，x2x412（2分）

令f(x)0，求得f的驻点

x(8/T3。

（4分）

21，2fx的一、二阶顺序主子式分别为 f的Hee矩阵为fx122 20，211230（6分）

对xRn,2fx为正定矩阵，因而f是Rn上的凸函数。故（8分）x(8/3,2T/为它的整体最优解。3

八、解：

f的Hee矩阵为

232fx38，（2分）

2fx的一、二阶顺序主子式本别为

20，233870，因而2fx为正定矩阵，f是严格凸函数.（4分）

4－1而g2x=，它也是一个正定矩阵，因而g2x也是严格凸函数，－142（7分）

其它的不等是约束为线性的。由定理知，该非线性规划是一个凸规划。

（9分）