运筹学计算题复习
运筹学计算题复习
一、第一章线性规划及单纯形法
1、 下表是某求极大化线性规划问题时得到的单纯形表，表中无任何松驰变量，
α为参数，
（1） 试完成该表；
（2） 若该表中所示的21,x x 为问题的最优基，试求α的取值范围
j C
α
2
1
-4
B c B x b 1x
2x
3x
4x
1x
3 1 0 1 -1 2
2x 1
0 1 -1 0 j j z c -
j C
α
2
1
-4
B c B x b 1x
2x
3x
4x
α 1x
3 1 0 1 -1 2
2x 1
0 1 -1 0
j j z c -
3-α
α-4
43≤≤α
2、 在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。
Max 43217432x x x x z +++=
???
??≥-=-+-=--+0,,,37628432..4
32143214321x x x x x x x x x x x x t s 解：在第二个约束条件两边乘以-1，变为标准形式
Max 43217432x x x x z +++=
???
??≥=+-+-=--+0,,,37628432..4
32143214321x x x x x x x x x x x x t s 1x 的系数列向量??????-=121p ，2x 的系数列向量??
?
???=232p ，
3x 的系数列向量??????--=613p ；4x 的系数列向量??
?
???-=744p
（1） 因为21,P P 线性独立，令非基变量0,43=x x 得???==21
21x x
基本可行解()8,0,0,2,11)1(==Z X T
（2） 因为31,P P 线性独立，令非基变量0,42=x x 得???
????
-
==131413451x x
基本解T
X
??? ??-=0,1314,0,13
45
)
2(
（3） 因为41,P P 线性独立，令非基变量0,32=x x 得???
????
==575
3441x x
基本可行解5117,57,0,0,534
)
3(=
??
? ??=Z X T
（4） 因为32,P P 线性独立，令非基变量0,41=x x 得???
????
==16716
4532x x
基本可行解16163,0,167,1645,0)
4(=
??
?
??=Z X T
（5） 因为42,P P 线性独立，令非基变量0,31=x x 得???
????
-==29729
6842x x
基本解T
X
??? ??-=297,0,29
68
,0)
5(
（6） 因为43,P P 线性独立，令非基变量0,21=x x 得???
????
-=-=314531
6843x x
基本解T
X ??? ?
?
--=3145,3168,0,0)
5(
比较最大值431,,Z Z Z 可知5
117
3=
Z 为最大值，故最优解为5117,57,0,0,5
34
)
3(=
??? ??=Z X
T
3、 分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每
一步相应于图形上哪一个顶点？
Max 212x x z +=
S.T.???
??≥≤+≤+0,242615532
12121x x x x x x
解：（1）图解法，作图如下图所示，由图得唯一最优解T X )4
3
,415(*=，对应于
图上的点为2A ，其最优值为4
33
*=z 。
15
5321=+x x
X 1
X 2
A 3
A 2 A 1
24
2621=+x x
（2） 单纯形法，引入松驰变量0,43≥x x ，标准型为
Max 212x x z +=
S.T.???
??≥=++=++0,,,242615534
321421321x x x x x x x x x x
j C
2 1
i θ
B C B X b
1x
2x
3x
4x
0 3x
15 3 5 1 0 5 0
4x
24
6 2 0 1 4 j σ
2
1 0 0 0 3x
3 0
4 1 -1/2 3/4 2
1x
4
1 1/3 0 1/6 1
2 j σ
1/3 0 -1/3 1 2x 3/4 0 1 1/4 -1/8 2
1x
15/4
1 0 -1/1
2 5/24 j σ
-1/12
-7/24
因为()4,3,2,10=≤j j σ，故问题的最优解T X )0,0,4
,4(*=，其最优目标函数值
为433
*=z
4、 建模题：某公司有资金3000万元，六年内有A 、B 、C 、D 、E 五种投资项目可供选择。其中：项目A 从第一年到第六年初均可投资，当年末可获利10%；项目B 可在第一年到四年初投资，周期为3年，到期可25%；项目C 只能在第二年初投资，周期为3年，到期可获利45%，但规定最大投资额不超过1000万元；项目D 只能在第四年初投资，周期为3年，到期可获利40%，但规定最大投资额不超800万元；项目E 只能在第五年投资，周期为2年，到期可