运筹学》试题（答案）
一、单项选择题。 下列每题给出的四个答案中只有一个是正确的， 将表示正确答 案的字母填入题后的括号中。 （20 分）
1．对一个极大化的线性规划问题用单纯形法求解，若对所有的检验数
j 0
，但对某个
非基变量 xj ，有 j 0，则该线性规划问题（ B ）
A ．有唯一的最优解； B．有无穷多个最优解； C．为无界解； D．无可行解。
2．使用人工变量法求解极大化线性规划问题时，当所有的检验数
j 0
，在基变量中仍
含有非零的人工变量，表明该线性规划问题（ 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．若一个指派问题的系数矩阵的某行各元素都加上常数 阵对应着一个新的指派问题，则（ A ）。
k 得到一个新的矩阵，这一新矩
A ．新问题与原问题有相同的最优解； B ．新问题最优目标值大于原问题最优目标函数值； C．新问题最优解等于原问题最优解加上 k ；D ．新问题最优解小于原问题最优解。 9．如果要使目标规划实际实现值不超过目标值，则相应的偏离变量应满足（
A．
B ）。
d 0；B．d 0；C．d 0；D．
d 0, d 0.
10 ．动态规划问题中最优策略具有性质： （ C ） A．每个阶段的决策都是最优的；
B．当前阶段以前的各阶段决策是最优的；
C．无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应
构成最优策略； D．它与初始状态无关。
二、计算题
1．用单纯形法求解以下线性规划问题
maxz 3x1 5x2
x1 s.t.
3x1 x1,x2
2
2x2 2x2 0
4 12 18
解： 化为标准型如下
maxz 3x1
x1 s.t.
3x1 x1,x2
5x2
x3
4
x4
2x2 2x2
x5
12
18
3 CB 0 0 0 XB x3 x4 x5 cj-zj 0 5 0 x3 x2 x5 cj-zj 0 5 3 x3 x2 x1 cj-zj 2 6 2 4 6 6 b 4 12 18 x1 1 0 3 3 1 0 [3] 3 0 0 1 0 5 x2 0 [2] 2 5 0 1 0 0 0 1 0 0 0 x3 1 0 0 0 1 0 0 0 1 0 0 0 0 x4 0 1 0 0 0 1/2 -1 -5/2 1/3 1/2 -1/3 -5/2 0 x5 θi 6 9 0 0 1 0 0 4 2 0 1 0 -1/3 0 1/3 -1
所以最优解为 x1=2, x2=6，最优值为 z=36
2．已知线性规划问题：
maxz x1 2x2
x1
3x3
2x2
4x4 2x3 3x3
3x4 2x4
20 20
s.t. 2x1 x2
x1,x2,x3,x4 0
1） （1） 写出其对偶问题
2） （2） 若已知其对偶问题最优解为
y1 1.2, y2 0.2
，根据对偶理论求出原问题
的最优解。
解：
（1）其对偶问题为
y1
min w 20y1 20y2
2y2
y2
1 2 3 4
2y1 2y1 3y1 y1,y2
3y2
2y2 0
（2）将 y1 1.2, y2
0.2
代入到对偶问题的四个约束条件可得
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
那么由互补松驰性得， x1=0; x2=0; x3>0; x4> 0。再由 y1, y2>0 得，原问题的两个约束条件均取 等号，这样联立方程求解原问题的最优解为， x1=0; x2=0; x3=4; x4=4 ，目标函数值 z=28.
3．求出下图中从 A 到 E 的最短路线及其长度。
B1
C1
B2
1
C2
B3
D11
D2
5
D3
A，B，C，D，E 为 5个状态。
解： 把整个最短路线问4 个阶段，建立模型 题分为 当 k=4 时， 当
f(D1)=3, f(D 2)=1, f(D 3)=5
k=3 时，
运筹学教程第五版课后答案
