以下为《运筹学复习题》的无排版文字预览,完整格式请下载
下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。
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. 任意线性规划问题都有对偶问题
B. 原问题和对偶问题的最优目标值相同
C.对偶问题的对偶是原问题
D. 解对偶问题和对偶单纯形法是同一概念
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的最短 内容过长,仅展示头部和尾部部分文字预览,全文请查看图片预览。 B5
A1
A2
A3
A4
A5
7
9
8
7
4
5
12
5
3
6
9
7
4
6
7
8
11
6
9
5
11
9
9
6
11
问如何分配这五名人员的工作,使总的培训时间最短?
解:A1做B2项工作;A2做B3项工作;A3做B4项工作;A4做B5项工作;A5做B1项工作
6、求下图v1到v8的最短路及最短路长(10分)
解:
v1到v8的最短路有两条:P18={v1,v3,v6,v8}及P18={v1,v3,v7,v6,v8},最短路长为21.
四、某工厂有100台机器,拟分四个周期使用,在每一周期有两种生产任务。据经验,把机器x1台投入第一种生产任务,则在一个生产周期中将 x1台机器作废;余下的机器全部投入第二种生产任务,则有机器作废。如果干第一种生产任务每台机器可收益10,干第二种生产任务每台机器可收益7,问怎样分配机器,使总收益最大?
解某某xk为第k周期末机器完好数,uk为第k+1周期安排干第一种生产任务的机器数。
Dk(xk)={uk|0≤uk≤xk}
其中
用逆推法求得:
最优决策为第一、二周期机器全部投入第二种生产任务,第三、四周期机器全部投入第一种生产任务。
最大收益为2680。
五、已知某物资的产量、销量及运价表如图所示,试制定最优调运方案
销地
产地
甲
乙
丙
丁
产量
1
2
11
3
4
70
2
10
3
5
9
50
3
7
8
1
2
70
销量
20
30
40
60
解:最优调运方案是:
目标函数值为Z*=20×2+30×4+20×0+30×3+20×0+40×1+30×2=350。
六、运用动态规划方法求出下图中从A到E的最短路线及其长度。
?
?
?
?
?
?
?
?
?
?
?
解:
把整个最短路线问题分为4个阶段,建立模型:A,B,C,D,E为5个状态。
当k=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字内容到此结束,中间部分内容请查看底下的图片预览]
以上为《运筹学复习题》的无排版文字预览,完整格式请下载
下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。