大工14秋《运筹学》在线作业3作业及答案.doc

《大工14秋《运筹学》在线作业3作业及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、大工14秋《运筹学》在线作业3作业及答案一、单选题（共 5 道试题，共 40 分。）    得分：40V1.  一个有8个点的连通图至少有（）条边。A.4B.5C.6D.7      满分：8  分  得分：82.  假设对于一个动态规划问题，应用顺推法及逆推解法得出的最优解分别为E和F，则有（）。A.E>FB.E

2、B.分配问题C.运输问题D.最短路问题      满分：8  分  得分：85.  下列说法不正确的为（）。A.完成各个作业需要时间最长的路线称为关键路线B.关键路线上的作业称为关键作业C.所有关键作业的总时差为0D.以上说法均不正确      满分：8  分  得分：8二、判断题（共 15 道试题，共 60 分。）    得分：60V1.  总时差是指在不影响到各项紧后作业最迟开工的条件下，该作业可以推迟开工的最大限度。A.错误B.正确      满分：4  分  得分：42.  当网络中不存在任何增广链时，网络达到最大流状态。A.错误B.正确      满分：4  分  得分：43. 

3、 动态规划问题的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段决策问题。A.错误B.正确      满分：4  分  得分：44.  狄克斯特拉算法可以用来求解一个节点到所有节点之间的最短路。A.错误B.正确      满分：4  分  得分：45.  应用狄克斯特拉算法n次，可以求出所有点间的最短路。A.错误B.正确      满分：4  分  得分：46.  具有n个节点的树的边恰好为n+1条。A.错误B.正确      满分：4  分  得分：47.  一个动态规划问题若能用网络表达，则节点代表各阶段的状态值，各条弧代表了可行的方案选择。A.错误B.正确      

4、满分：4  分  得分：48.  动态规划问题的计算中较多采用逆序算法。A.错误B.正确      满分：4  分  得分：49.  作业的最早结束时间为它的最早开始时间加上该项作业的计划时间。A.错误B.正确      满分：4  分  得分：410.  割的容量是指所有割集中容量之和为最小的一个割集。A.错误B.正确      满分：4  分  得分：411.  最优化原理认为“无论初始状态和初始决策如何，对于前面决策所形成的状态而言，余下的决策序列必构成最优策略。”A.错误B.正确      满分：4  分  得分：412.  求网络最大流的标号算法的基本思想是指寻找增广链，改善流量

5、分布；再重复，直到不存在任何增广链为止。A.错误B.正确      满分：4  分  得分：413.  树是无圈连通图中边数最多的，在树图上只要任意再加上一条边，一定会出现圈。A.错误B.正确      满分：4  分  得分：414.  网络的最大流是指能够通过网络的最大可行流。A.错误B.正确      满分：4  分  得分：415.  在狄克斯特拉算法中，每次迭代可以使多个节点同时获得永久标记。A.错误B.正确      满分：4  分  得分：4