运筹学期末复习题

《运筹学》期末复习题一、单项选择题1、下列论述对的的是（）。A．线性规划问题，若有最优解，则必是一种基变量组的可行基解B．线性规划问题一定有可行基解C．线性规划问题的最优解只能在最低点上到达D．单纯形法求解线性规划问题时，每换基迭代一次必使目的函数值下降一次答案：A2、线性规划的变量个数与其对偶问题的（）相等。A．变量目的函数C．约束条件个数答案：C3、在运用表上作业法求各非基变量的检查数时，有闭回路法和（）两种措施。A．西北角法C．最低费使用方法答案：B4、下列各项（）不是目的规划的特点。A．多目的C．具有优先次序答案：B5、下列有关图的说法中，错误的为（）。A．点表达所研究的事物对象C．无向图是由点及边所构成的图答案：D6、运用单纯形法求解线性规划问题时，首先需要（）。A．找初始基础可行基C．确定改善方向答案：A7、对偶问题最优解的剩余变量解值（）原问题对应变量的检查数的绝对值。A．不小于C．等于答案：C第1页共17页B．变量约束条件D．不确定B．位势法D．元素差额法B．单一目的D．不求最优B．检查目前基础可行解与否为最优解D．确定入变量的最大值和出变量B．不不小于D．不能确定8、当某个非基变量检查数为零，则该问题有（）。A．无解B．无穷多最优解C．退化解D．惟一最优解答案：B9、PERT网络图中，（）表达一种工序。A．节点B．弧C．权D．关键路线答案：B10、假设对于一种动态规划问题，应用顺推法以及逆推解法得出的最优解分别为P和D，则有（A．P>DB．P答案：C11、下列有关线性规划问题的原则形式的论述中错误的是（）。A．目的函数求极大B．约束条件全为等式C．约束条件右端常数项全为正D．变量取值全为非负答案：C12、线性规划问题的数学模型由目的函数、约束条件和（）三个部分构成。A．非负条件B．顶点集合C．最优解D．决策变量答案：D13、假如原问题有最优解，则对偶问题一定具有（）。A．无穷多解B．无界解C．最优解D．不能确定答案：C14、运送问题的基变量有（）个。A．m某nB．m+n-1C．m+nD．不确定答案：B15、目的规划的目的权系数是定量的概念，数值（），表达该目的越重要。A．越小B．越大C．为0D．为正第2页共17页答案：B16、下列论述对的的是（）。A．线性规划问题，若有最优解，则必是一种基变量组的可行基解B．线性规划问题一定有可行基解C．线性规划问题的最优解一定唯一D．单纯形法求解线性规划问题时，每换基迭代一次必使目的函数值下降一次答案：A17、设M是线性规划问题，N是其对偶问题，则（）不对的。A．M有最优解，N不一定有最优解B．若M和N均有最优解，则两者最优值肯定相等C．若M无可行解，则N无有界最优解D．N的对偶问题为M答案：A18、PERT网络图中，（）表达为完毕某个工序所需的时间或资源等数据。A．节点C．权答案：C19、网络的最大流量应（）它的最小割集的容量。A．不小于C．不不小于答案：B20、运用单纯形法求解线性规划问题时，判断目前解与否为最优解的原则为所有非基变量的检查数应为（）。A．正C．非正答案：C21、若原问题为无界解，则对偶问题的解是（）。A．无解C．无界解答案：A22、PERT网络图中，（）表达一种事件，用圆圈和里面的数字表达。第3页共17页B．弧D．圆圈B．等于D．不不小于B．负D．非负B．无穷多解D．不能确定A．节点C．权答案：A23、具有7个节点的树T的边恰好为（）条。A．5B．弧D．关键路线B．6C．7D．8答案：B24、下列数学模型中，（）是线性规划模型。A.MinZ=3某1+某2－2某3B.Ma某Z=10某1+某2-3某322某1+3某2-4某3≤12某1+5某2≤154某1+某2+2某3≥8某1-8某2+3某3≥223某1-某2+3某3=6某j≥0,j=1,2,3某1≥0,某2无约束,某3≤02C.D.Z=5某1+6某2+8某3-9某4Ma某Z=某1+4某2-8某3+某4某1+4某3-某4=19某2-5某3+4某4≥30某1+某2-6某4≤9某j≥0,j=1,2,3,4某1+4某3-某4=29某2-5某3+4某4≥40某1+某2-6某4≤19某j≥0,j=1,2,3,4答案：A25、若线性规划问题的最优解不唯一，则在最优单纯形表上（）。A．非基变量的检查数都为零C．非基变量检查数必有为零答案：C26、对于总运送费用最小的运送问题，若已得最优运送方案，则其中所有空格的检查数均（）。A．非正C．不小于0答案：B27、下列环节中，不属于目的规划模型图解法的为（）。A．作平面直角坐标系C．作出目的函数的一族平行线答案：C28、下列有关图的说法中，错误的为（）。第4页共17页B．非基变量检查数不必有为零者D．非基变量的检查数都不不小于零B．非负D．不不小于0B．作出目的约束所在直线，标出偏差方向D．按优先级次序，确定满意解A．点表达所研究的事物对象C．无向图是由点及边所构成的图答案：D二、判断题1、若LP问题有最优解，则要么最优解唯一，要么有无穷多最优解。（）答案：对2、在运送问题的解的检查数的计算时，常采用匈牙利法。（）答案：错3、偏差变量是指实际值与目的值的差距，其中d可以用来表达实际值未到达目的值的差距。（）答案：错4、作业的最早结束时间是它的最早开始时间加上该项作业的计划时间。（）答案：对5、关键路线上的作业称为关键作业。（）答案：对6、破圈法可以用来求解部分树。（）答案：对7、增长约束条件时，线性规划模型的可行域不扩大。（）答案：对8、线性规划问题存在至少一种对偶问题。（）答案：错9、产地数与销地数相等的运送问题是产销平衡运送问题。（）答案：错10、在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或是极小，原问题可行解的目的函数值都一定超过其对偶问题可行解的目的函数值。（）答案：错11、图的最小生成树一定唯一。（）答案：错12、动态规划的逆推与顺推解法得到不一样的最优解。（）答案：错13、对于线性规划原则型，运用单纯形求解时，每做一次换基迭代，都能保证它对应的目的函数值必为不第5页共17页+减少。（）答案：对14、当目的规划问题模型中存在某1某2d答案：错15、PERT网络图中，事件一般用箭线表达，作业用圆圈表达。（）答案：错16、无多重边的图称为简朴图。（）答案：错17、运送问题、最短路问题和求网络最大流问题，都可看作是最小费用流的特例。（）答案：对18、目的规划问题中，权系数是定量的概念，数值越大，表达该目的越重要。（）答案：对19、若线性规划问题存在可行域，则问题的可行域是凸集。（）答案：对20、目的规划模型中，应同步包括系统约束与目的约束。（）答案：错21、PERT网络图中，任何消耗时间或资源的行动都可称作作业。（）答案：对22、任务分派问题共有m某m个约束条件。（）答案：错23、树枝总长为最短的部分树称为图的最小部分树。（）答案：对24、目的的优先级是一种定性的概念，不一样优先级的目的无法从数量上来衡量。（）答案：对25、单纯形法计算中，应选用最小正检查数对应的变量作为换入变量。（）答案：错26、当目的规划问题模型中存在2某1某24的约束条件，则该约束为目的约束。（）答案：错27、PERT网络图中，事件消耗一定的时间和资源。（）答案：错第6页共17页5的约束条件，则该约束为系统约束。（）28、在动态规划模型中，问题的阶段数等于问题中的子问题的数目。（）答案：对29、运送问题和求网络最大流问题，都可看作是最小费用流的特例。（）答案：对30、当网络中不存在任何增广链时，则网络到达最大流状态。（）答案：对31、在可行解的状态下，原问题与对偶问题的目的函数值是相等的。（）答案：错32、在处理运送问题时，采用闭回路法，可以得到运送问题的基本可行解。（）答案：错33、在整数规划问题中，若变量取值为0或者1，则为0—1规划问题。（）答案：对34、PERT网络图是由结点、弧及权所构成的有向图。（）答案：对35、完毕各个作业需要的时间最长的路线称为关键路线。（）答案：对三、名词解释题1、规划问题答案：生产和经营中常常提出怎样合理安排，使人力、物力等多种资源得到充足运用，获得最大的效益。这就是所谓的规划问题。2、对偶问题答案：内容一致但从相反角度提出的一对问题称为对偶问题。3、无向图答案：无向图是指由点及边所构成的图。4、割集答案：割集是指容量网络中一组弧的集合，割断这些弧，能使流中断，简称割。5、路线答案：从PERT网络图中从最初事件到最终事件的一条路。6、偏差变量答案：偏差变量指实际值与目的值的差距。第7页共17页7、PERT网络图答案：PERT网络图是由结点、弧及权所构成的有向图。8、增广链答案：由发点到收点之间的一条链，假如在前向弧上满足流量不不小于容量，即fij0，则称这样的链为增广链。9、系统约束答案：系统约束指某种资源在使用上要受到严格的限制，决不容许超用或超负荷运行。10、简朴图答案：既没有自环也没有平行边的图称为简朴图。11、状态转移律答案：状态参数变化的规律。从第k阶段的某一状态值k出发，当决策变量某k的取值确定之后，下一阶段的状态值k+1按某种规律T(k,某k)确定。12、闭回路答案：闭回路指调运方案中由一种空格和若干个有数字格的水平和垂直连线包围成的封闭回路。13、正偏差变量答案：正偏差变量指实际值超过目的值的差距。14、作业的最早开始时间答案：作业的最早开始时间是它的各项紧前作业最早结束时间中的最大一种值。15、连通图答案：若一种图中，任意两点之间至少存在一条链，称这样的图为连通图。16、0-1规划问题答案：在整数规划问题中，若变量取值为0或者1，则为0-1规划问题。17、负偏差变量答案：负偏差变量指实际值未到达目的值的差距。18、作业的最迟结束时间答案：作业的最迟结束时间是它的各项紧后作业最迟开始时间中的最小一种。19、最小割答案：网络中所有割集中容量之和为最小的一种割集。20、偏差变量答案：偏差变量指实际值与目的值的差距。d表达实际值超过目的值的差距；d表达实际值未到达目的值的差距。第8页共17页+21、图答案：容量网络指对网络上的每条弧(vi，vj)都给出一种最大的通过能力，称为该弧的容量，记为c(vi，vj)，简称容量。以cij表达。23、状态答案：状态指某阶段初始状况。既反应前面各阶段决策的结局，又是本阶段作出决策的出发点和根据。是动态规划中各阶段信息的传递点和结合点。四、简答题1、简述避圈法的环节？答案：答：将图中所有的点分为V和v两部分，其中V——最小部分树内点的集合；v——非最小部分树内点的集合。（1）任取一点vi加粗，令vi∈V；（2）取V中与v相连的边中一条最短的边(vi,vj)，加粗(vi,vj)，令vj∈V；（3）反复（2），至所有的点均在V之内。2、简述运用分枝定界法求解整数规划问题时，首先需要寻找替代问题，简述替代问题应具有的条件。答案：（1）轻易求解；（2）松弛问题的解集应所有包括原问题的解集。3、简述图解法的合用条件和基本环节。答案：答：对于只含两个变量的线性规划问题，可通过在平面上作图的措施求解。图解法的环节如下：（1）建立平面直角坐标系；（2）图示约束条件，找出可行域；（3）图示代表目的函数的直线及目的函数值增长（或减小）的方向；（4）将目的函数直线沿其法线方向在可行域内向可行域边界平移至目的函数到达最优值为止，目的函数到达最优值的点就为最长处。4、简述运用元素差额法确定运送问题初始方案的基本思想和环节。答：基本思想：从总体考虑，得到初始可行方案。环节：从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供应数量。5、简述求网络最大流的标号算法的基本环节。答：第一步：标号过程，找一条增广链第9页共17页（1）给源点标号[,()=]，表达从点有无限流出潜力+（2）找出与已标号节点i相邻的所有未标号节点j，若1)(i,j)是前向弧且饱和，则节点j不标号；2)(i,j)是前向弧且未饱和，则节点j标号为[i,(j)]，表达从节点i正向流出，可增广+(j)=min[(i),cijfij]；3)(j,i)是后向弧，若fji=0，则节点j不标号；4)(j,i)是后向弧，若fji>0，则节点j标号为[i,(j)]，表达从节点j流向i，可增广(j)=min[(i),fji]；（3）反复环节（2），也许出现两种状况：1)节点t尚未标号，但无法继续标识，阐明网路中已不存在增广链，目前流V(f)就是最大流；所有获标号的节点在V中，未获标号节点在V中，V与V间的弧即为最小割集；算法结束；2)节点t获得标号，找到一条增广链，由节点t标号回溯可找出该增广链；到第二步。第二步：增广过程。（1）对增广链中的前向弧，令f=f+(