您好,欢迎访问三七文档
2014-2015复习一、名词解释(5道,15分)1.优化2.线性规划3.可行解4.可行域5.基6.基本可行解7.影子价格8.灵敏度分析9.运输问题10.整数规划11.0-1规划12.松弛问题13.目标规划14.偏差变量15.链16.路17.最小生成树18.PERT网络图19.关键路线法20.最早开始时间21.最迟完成时间22.总时差二、选择题(10道,20分)1.如果一个线性规划问题有n个变量,m个约束方程(mn),系数矩阵的数为m,则基可行解的个数最为_C_。A.m个B.n个C.CnmD.Cmn个2.下列图形所包含的区域不是凸集的是:CA.椭圆形B.三角形C.弯月形D.长方形3.在单纯形表的终表中,若若非基变量的检验数有0,那么最优解CA.不存在B.唯一C.无穷多D.无穷大4.在约束方程中引入人工变量的目的是DA体现变量的多样性B变不等式为等式C使目标函数为最优D形成一个单位阵5.对于线性规划问题标准型:maxZ=CX,AX=b,X≥0,利用单纯形法求解时,每作一次迭代,都能保证它相应的目标函数值Z必为AA.增大B.不减少C.减少D.不增大6.求解线性规划的单纯形法中,最小比值法则min,1,,ilikbima公式中,系数满足BA.=0B.0C.0D.无限制7.求目标函数为极大的线性规划问题时,若全部非基变量的检验数≤O,且基变量中有人工变量时该问题有BA无界解B无可行解C唯一最优解D无穷多最优解8.在线性规划问题中,当采用大M法求解时,如经过迭代,检验数均满足最优判别条件,但仍有人工变量为基变量,且其不为零,则该线性规划问题为A。A.无可行解B.无界解C.有最优解D.无穷多最优解9.设X、Y分别是标准形式的原问题与对偶问题的可行解,则C。10.如果z。是某标准型线性规划问题的最优目标函数值,则其对偶问题的最优目标函数值w﹡A。A.W﹡=Z﹡B.W﹡≠Z﹡C.W﹡≤Z﹡D.W﹡≥Z﹡11.互为对偶的两个线性规划问题的解存在关系_B。A.原问题无可行解,对偶问题也无可行解B.一个问题具有无界解,则另一问题无可行解C.若最优解存在,则最优解相同D.一个问题无可行解,则另一个问题具有无界解12.如果某种资源的影子价格大于其市场价格,则说明_BA.该资源过剩B.该资源稀缺C.企业应尽快处理该资源D.企业应充分利用该资源,开僻新的生产途径13.若线性规划问题最优基中某个基变量的目标系数发生变化,则C。A.该基变量的检验数发生变化B.其他基变量的检验数发生变化C.所有非基变量的检验数发生变化D.所有变量的检验数都发生变化14.有m个产地n个销地的平衡运输问题模型具有特征A.有mn个变量m+n个约束B.有m+n个变量mn个约束C.有mn个变量m+n-1约束D.有m+n-1个基变量,mn-m-n-1个非基变量15.运输问题的初始方案中,没有分配运量的格所对应的变量为BA基变量B非基变量C松弛变量D剩余变量16.表上作业法的基本思想和步骤与单纯形法类似,那么基变量所在格为CA有单位运费格B无单位运费格C有分配数格D无分配数格17.一般讲,在给出的初始调运方案中,最接近最优解的是CA西北角法B最小元素法C沃格尔法D位势法18.运输问题中,调运方案的调整应在检验数为C负值的点所在的闭回路内进行。A任意值B最大值C绝对值最大D绝对值最小19.若运输问题中总供应量大于总需要量,则DA.必须用线性规划单纯形法求最优解B.不存在可行解C.虚设一个供应点D.虚设一个需求点20.若运输问题中总需要量大于总供应量,则:DA.必须用线性规划单纯形法求最优解B.不存在可行解C.虚设一个需求点D.虚设一个供应点21.整数规划问题中,变量的取值可能是D。A.整数B.0或1C.大于零的非整数D.以上三种都可能22.下列方法中用于求解分配问题的是D_。A.单纯形表B.分枝定界法C.表上作业法D.匈牙利法23.要求不超过第一目标值、恰好完成第二目标值,目标函数是AA.)(min22211ddpdpZB.)(min22211ddpdpZC.)(min22211ddpdpZD.)(min22211ddpdpZ24.关于图论中图的概念,以下叙述(B)正确。A图中的有向边表示研究对象,结点表示衔接关系。B图中的点表示研究对象,边表示点与点之间的关系。C图中任意两点之间必有边。D图的边数必定等于点数减1。25、关于顶点的次,说法不正确的是:CA.某顶点的次是指以该点为端点的边数B.次为1的点为悬挂点C.顶点次数等于边数D.次为奇数的点为奇点26.关于树的概念,以下叙述(B)正确。A树中的点数等于边数减1B连通无圈的图必定是树C含n个点的树是唯一的D任一树中,去掉一条边仍为树。27.一个连通图中的最小树(B),其权(A)。A是唯一确定的B可能不唯一C可能不存在D一定有多个。28.关于可行流,以下叙述(A)不正确。A.可行流的流量大于零而小于容量限制条件B.在网络的任一中间点,可行流满足流人量=流出量。C.各条有向边上的流量均为零的流是一个可行流D.可行流的流量小于容量限制条件而大于或等于零。29.求解最大流的标记化方法中,标号过程的目的是:CA.增加流量B.构造四通八达的路C.寻找增广链D.给出标号30.关于可增广链的性质,正确的是:AA.前向边中的流量应小于该边的最大容量B.后向边中的流量应大于等于0C.后向边中的流量应小于该边的最大容量D.都有可能31.容量网络的条件包括:DA.网络中有一个始点和一个终点B.流过网络的流量都具有一定方向C.每边(弧)都赋予了一个容量,表示容许通过该弧的最大流量D.以上都是32.关于网络计划技术的说法不正确的是:BA.它需要分清哪项工作先作,哪项工作后做B.它不是一种统筹方法C.它的目的是缩短工期或降低成本D.它需要找出关键工作33.已知某一活动i→j开始的最早时间ESi,j=3,该活动的作业时间为5,则结点j的最早结束时间EFj为:BA.3B.8C.不确定D.234.在网络图中,活动ij的最早开始时间等于:CA.ES(j)B.ES(i)+T(i,j)C.ES(i)D.LF(j)35.虚活动:BA.占用时间,但不消耗资源B.不占用时间,也不消耗资源C.不占用时间,但消耗资源D.既消耗资源,也消耗时间36.关于工作的时间参数,下列说法正确的是:DA.工作的最早开始时间是它的箭尾事件的最早时间B.工作的最早完成时间是它的最早开始时间加上本工作作业时间C.工作的最迟开始时间是它的箭头事件的最迟时间减去本工作作业时间D.以上都正确37.关于关键路线,下列说法不正确的是:DA.与总工期时间相等的线路是关键线路B.线路时差最小的线路又称为次关键线路C.网络计划的精华是控制关键线路D.关键线路一定只有一条三、填空题(10空,10分)1.线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。2.若线性规划问题有最优解,则最优解一定可以在可行域的顶点(极点)达到。3.满足非负条件的基本解称为基本可行解。4.将线性规划模型化成标准形式时,“≤”的约束条件要在不等式左_端加入松弛变量。5.化一般线性规划模型为标准型时,可能引入的变量有松弛变量、剩余变量、非负变量。6.若原问题可行,但目标函数无界,则对偶问题不可行。7.如果原问题的某个变量无约束,则对偶问题中对应的约束条件应为等式_。8.原问题有7个变量8个约束,其对偶问题有8个变量7个约束。9.线性规划问题的最优基为B,基变量的目标系数为CB,则其对偶问题的最优解Y﹡=CBB-1。10.用表上作业法求解某运输问题,若已计算出某空格的检验数为-2,则其经济意义是运费还可以减少11.按照表上作业法给出的初始调运方案,从每一空格出发可以找到且仅能找到_1条闭回路12.表上作业法的初始基本可行解应满足的条件是含有m+n-1个非零的基变量且不构成闭回路。13.在分枝定界法中,若选X2=3.6进行分支,则构造的约束条件应为X2≤3,X2≥4。14.在0-1整数规划中变量的取值可能是_0或1。15.某工程公司拟从四个项目中选择若干项目,若令用ix的线性表达式表示下列要求:只有项目2被选中,项目4才能被选中:024242xxxx或;16.使第一目标恰好完成,则其在目标规划中的目标函数是:P1(d1++d1-)17.在图论中,通常用点表示研究对象,用边或有向边表示研究对象之间具有某种特定的关系。18.在图论中,给边或有向边赋了权的图称为网络19.有向图中,若链中每一条弧的走向一致,如此的链称路;闭链称为圈;闭回路又称为回路。20.任一树中的边数必定是它的点数减1。21.流量为零的弧称为零流弧。四、判断(10道,10分)1.若线性规划存在最优解则一定存在基本最优解对2.若线性规划无界解则其可行域无界对3.若线性规划存在基本解则也一定存在基本解可行解错4.线性规划的基本可行解只有有限多个对5.可行解集不一定是凸集错6.任何线性规划都存在一个对应的对偶线性规划对7.X*为最优解且B是最优基时,则Y*=CBB-1是最优解对8.原问题与对偶问题都可行,则都有最优解对9.对偶问题有可行解,原问题无可行解,则对偶问题具有无界解对10.若某种资源影子价格不为零,则该资源一定有剩余错11.减少一约束,目标值不会比原来变差对12.当bi在允许的最大范围内变化时,最优解不变错13.因为运输问题是一种特殊的线性规划问题,所以运输问题也可以用单纯形方法求解对14.产地数为3,销地数为4的平衡运输问题有7个基变量错15.按最小元素法求得运输问题的初始方案,从任一非基格出发都存在唯一一个闭回路对16.运输问题中运价表的每一个元素都分别乘于一个常数,则最优解不变对11,2,3,40iiiixìïïï==íïïïî,第个项目被选中;,第个项目未被选中;17.运输问题中运价表的每一个元素都分别加上一个常数,则最优解不变对18.运输问题中用位势法求得的检验数不唯一错19.部分变量要求是整数的规划问题称为纯整数规划对20.求最大值整数规划问题的目标函数值比其松弛问题目标函数值小对21.求最小值整数规划问题的目标函数值比其松弛问题目标函数值小错22.变量取0或1的规划是整数规划对23.整数规划的可行解集合是离散型集合对24.如果与整数规划相对应的线性规划无可行域,则整数规划也无可行域对25.正偏差变量大于等于零,负偏差变量小于等于零错26.系统约束中没有正负偏差变量对27.一对正负偏差变量至少一个等于零对28.要求不超过目标值的目标函数是minZ=d-错29.破圈法是:任取一圈,去掉圈中最长边,直到无圈对30.最大流问题是找一条从起点到终点的路,使得通过这条路的流量最大对31.截量等于截集中弧的流量之和错32.任意可行流量不超过任意截量对33.狄克斯屈拉算法是求最大流的一种标号算法错34.可行流是最大流的充要条件是不存在发点到收点的增广链对35.容量不超过流量错36.网络计划中的总工期是网络图中的最短路的长度错37.A完工后B才能开始,称A是B的紧后工序错38.虚工序不需要资源,是用来表达工序之间的衔接关系的虚设活动。对39.关键路线存在且唯一错40.计划网络图不允许有多个始点和终点对41.单时差为零的工序称为关键工序错五、计算(5道,45分)1.图解法求解线性规划问题。2.表格单纯形法求解线性规划问题,要求会画表格,会判断解的类型。3.会写出原问题的对偶问题。4.会应用互补松弛性定理解相应的问题。5.灵敏度分析:(①目标函数系数变化对最优解的影响;②约束右端项变化对最优解的影响;③增加约束条件对最优解的影响)6.运输问题的表上作业法:(初始方案求解:沃格尔法、最小元素法;、检验数求解:闭回路法、位势法(优选);方案调整:闭回路法)7.标准分配问题的匈牙利求解。8.目标规划的图解法。9.最小支撑树(最小部分树)的破圈和避圈求法。10.最短路的标号求法。11.会求网络最大流。12.网络图的绘制。13.用标号法计算网络图时间参数:(包括最早开始时间、最早结束时间、最迟开始
本文标题:运筹期末复习
链接地址:https://www.777doc.com/doc-1999921 .html