《运筹学》试题（答案）
一、单项选择题。
下列每题给出的四个答案中只有一个是正确的，将表示正确答案的字母填入题后的括号中。
（20分）
1．对一个极大化的线性规划问题用单纯形法求解，若对所有的检验数0
≤j σ，但对某个
非基变量j x ，有0
=j σ，则该线性规划问题（ B ）
A ．有唯一的最优解；
B ．有无穷多个最优解；
C ．为无界解；
D ．无可行解。
2．使用人工变量法求解极大化线性规划问题时，当所有的检验数0
≤j σ，在基变量中仍含有非零的人工变量，表明该线性规划问题（ D ）
A ．有唯一的最优解；
B ．有无穷多个最优解；
C ．为无界解；
D ．无可行解。
3．在对偶问题中，若原问题与对偶问题均具有可行解，则（ A ） A ．两者均具有最优解，且它们最优解的目标函数值相等；
B ．两者均具有最优解，原问题最优解的目标函数值小于对偶问题最优解的目标函数值；
C ．若原问题有无界解，则对偶问题无最优解；
D ．若原问题有无穷多个最优解，则对偶问题只有唯一最优解；
4．在用对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（ D ）
A ．b 列元素不小于零；
B ．检验数都大于零；
C ．检验数都不小于零；
D ．检验数都不大于零。
5．在产销平衡运输问题中，设产地为m 个，销地为n 个，那么解中非零变量的个数（ A ）。
A ．不能大于(m +n -1)；B ．不能小于(m +n -1)；C ．等于(m +n -1)；D ．不确定。
6．在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题（ B ）。
A ．无最优解；B ．有无穷多个最优解；C ．有唯一最优解；D ．出现退化解。
7．在目标规划中，求解的基本原则是首先满足高级别的目标，但当高级别目标不能满足时（ D ）。
A ．其后的所有低级别目标一定不能被满足；
B ．其后的所有低级别目标一定能被满足；
C ．其后的某些低级别目标一定不能被满足；
D ．其后的某些低级别目标有可能被满足。
8．若一个指派问题的系数矩阵的某行各元素都加上常数k 得到一个新的矩阵，这一新矩阵对应着一个新的指派问题，则（ A ）。
A ．新问题与原问题有相同的最优解；
B ．新问题最优目标值大于原问题最优目标函数值；
C ．新问题最优解等于原问题最优解加上k ；
D ．新问题最优解小于原问题最优解。
9．如果要使目标规划实际实现值不超过目标值，则相应的偏离变量应满足（ B ）。
A ．0>+d ；
B ．0=+d ；
C ．0=-d ；
D ．
.0,0>>+-d d
10．动态规划问题中最优策略具有性质：（ C ） A ．每个阶段的决策都是最优的；
B ．当前阶段以前的各阶段决策是最优的；
C ．无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应
构成最优策略；
D ．它与初始状态无关。
二、计算题
1．用单纯形法求解以下线性规划问题
⎪⎪⎩⎪⎪⎨
⎧≥≤+≤≤+=0
,18
231224..53max 21212121x x x x x x t s x x z
解：
化为标准型如下
⎪⎪⎩⎪⎪⎨
⎧≥=+
+=+
=+
+=0
,18
231224..53max 215
214
23121x x x x x x x x x t s x x z
所以最优解为x 1=2, x 2=6，最优值为z =36
2．已知线性规划问题：
⎪⎩⎪
⎨⎧≥≤+++≤++++++=0,,,20
23220322..432max 4
3214
3
2143214321x x x x x x x x x x x x t s x x x x z
（1） （1） 写出其对偶问题
（2） （2） 若已知其对偶问题最优解为2.0,2.121==y y ，根据对偶理论求出原问题
的最优解。
解：
（1）其对偶问题为
⎪⎪⎪⎩⎪
⎪⎪⎨⎧≥≥+≥+≥+≥++=0
,4
2333222122020min 212
121212121y y y
y y y y
y y y y y w
（2）将2.0,2.121==y y 代入到对偶问题的四个约束条件可得 1*1.2+2*0.2>1; 2*1.2+0.2>1; 2*1.23*0.2=3; 3*1.2+2*0.2=4
那么由互补松驰性得，x 1=0; x 2=0; x 3>0; x 4>0。
再由y 1, y 2>0得，原问题的两个约束条件均取等号，这样联立方程求解原问题的最优解为，x 1=0; x 2=0; x 3=4; x 4=4，目标函数值z=28.
3．求出下图中从A 到E 的最短路线及其长度。
把整个最短路线问题分为4个阶段，建立模型：A ，B ，C ，D ，E 为5个状态。
当k =4时， f (D 1)=3, f (D 2)=1, f (D 3)=5 当k =3时，
5
455123min 4)(5)(2)(min )(3211=⎪⎭⎪
⎬⎫⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=D f D f D f C f ，相应的决策为11*
3)(D C u =
4
254113min 2)(4)(1)(min )(3212=⎪⎭⎪
⎬⎫⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=D f D f D f C f ，相应的决策为12*
3)(D C u =
当k =2时，
7
344543min 3)(4)(4)(min )(2111=⎪⎭⎪
⎬⎫⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=C f C f D f B f ，相应的决策为
11*
2)(D B u =或21*2)(C B u =
63415min 3)(1)(min )(212=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=C f C f B f ，相应的决策为12*
2)(C B u = 8
355435min 3)(5)(3)3(min )(213=⎪
⎭
⎪
⎬⎫
⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=C f C f D f B f ，相应的决策为
33*
2)(D B u =或23*
2)(C B u =
当k =1时，
8
182637min 1)(2)(3)(min )(321=⎪
⎭
⎪
⎬⎫
⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=B f B f B f A f ，相应的决策为2*
1)(B A u =
所以最短路线为：A->B 2->C 1->D 1->E ，其长度为8。
4．已知A ，B 两人对策时对A 的赢得矩阵如下，求双方各自的最优策略及对策值。
⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--021302412
解：这是一个纯局势下的对策问题，A 取α1，B 取β2为双方的最优纯策略。
A 的蠃得值的1，B 的赢得值为-1。
5．某一决策问题的损益矩阵如下表所示，其中矩阵元素值为年利润。
（1） （1） 若各事件发生的概率j P
是未知的，分别用悲观准则（maxmin 准则）、乐观准则(maxmax 准则)选出决策方案。
（2）
（2） 若1.0,7.0,2.0321===P P P
，则用期望收益值准则会选择哪个方案？
解：参照P378-386。
此处略。