运筹学复习题
以下为《运筹学复习题》的无排版文字预览，完整内容请下载
2020年运筹学复习题
一、选择题
1、下列说法错误的是（ D ）.
A.可行解集有界非空时,则在极点上至少有一点达到最优值;
B. 若线性规划有三个最优解X(1)、X(2)、X(3)，则X=αX(1)+(1-α)X(3)及X=α1X(1)+α2X(2)+α3X(3)均为最优解,其中?;
C . 若原问题具有无界解，则对偶问题无可行解;
0－1规划的变量有n个，则有个可行解;
2、对一个极大化的线性规划问题用单纯形法求解，若对所有的检验数，但对某个非基变量，有，则该线性规划问题（B ）
A．有唯一的最优解；B．有无穷多个最优解；C．为无界解；D．无可行解.?
3、设线性规划的约束条件为( C )
则基本可行解为
??? A．(0, 0, 4, 3)??????? B．(3, 4, 0, 0)
??? C．(2, 0, 1, 0)??????? D．(3, 0, 4, 0)
4、 有6 个产地4个销地的平衡运输问题模型具有特征是（ B ）
??? A．有10个变量24个约束 B．有24个变量10个约束
??? C．有24个变量9个约束 D．有9个基变量10个非基变量
5、动态规划问题中最优策略具有性质是（ C ）
A．每个阶段的决策都是最优的；
B．当前阶段以前的各阶段决策是最优的；
C．无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略；
D．它与初始状态无关.
6、若一个指派问题的系数矩阵的某行各元素都加上常数得到一个新的矩阵，这一新矩阵对应着一个新的指派问题，则（ A ）.
A．新问题与原问题有相同的最优解； B．新问题最优目标值大于原问题最优目标函数值；
C．新问题最优解等于原问题最优解加上；D．新问题最优解小于原问题最优解.
7、下列关于对偶问题说法不正确的是（ D ）
A. 任意线性规划问题都有对偶问题
Ｂ. 原问题和对偶问题的最优目标值相同
Ｃ.对偶问题的对偶是原问题
Ｄ. 解对偶问题和对偶单纯形法是同一概念
8、在求解整数规划问题时，不可能出现的是（ D ）
A．唯一最优解 B．无可行解 C．多重最优解 D．无穷多最优解
二、填空题
1、已知线性规划求极小值，用对偶单纯形法求解时，初始表中应满足条件（?对偶问题可行 ）.
2、非基变量的系数变化后，最优表中(非基变量? )发生变化.
3、设运输问题求最大值，则当所有检验数（?小于等于0 ）时得到最优解.
4、线性规划的最优解是(0，6),它的
第1、2个约束中松驰变量（S1,S2）=（?? 0 , 2 ? ）.
5、在资源优化的线性规划问题中，某资源有剩余，则该资源影子价格等于（?? 0 ? ）.
6、将目标函数转化为求极小值是（?）
7、运输问题的检验数λij的经济含义是（???xij增加一个单位总运费增加λij）.
8、在任一图G中，当点集V确定后，（树图）是G中边数最少的连通图.
9、具有个顶点的完全图有（ ）条边.
10、Dijkstra算法中的点标号b(j)的含义是（发点vi到点vj的最短路长 ）.
三、解答题
1、写出下列线性规划问题的对偶问题：
解：
2、用单纯形法求解以下线性规划问题
解：化为标准型如下
?
?
3
5
0
0
0
?
CB
XB
b
x1
x2
x3
x4
x5 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 =4时， f(D1)=3, f(D2)=1, f(D3)=5
当k=3时，
，相应的决策为
，相应的决策为
?
当k=2时，
，相应的决策为或
，相应的决策为
，相应的决策为或
当k=1时，
，相应的决策为
所以最短路线为：A->B2->C1->D1->E，其长度为8.
七、设个叶子的二叉树，各叶子上其权分别为4,3,3,2，2,1，求最优二叉树.
八、 最优检索问题，使用计算机进行图书分类.现有五类图书共100万某某，其中有A类50万某某，有B类20万某某，C类5万某某，D类10万某某，E类15万某某.问如何安排分检过程可使总的运算（比较）次数最小？
[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]
以上为《运筹学复习题》的无排版文字预览，完整内容请下载
运筹学复习题由用户“wozhaofneg”分享发布，转载请注明出处