19春运筹学期末考试复习题

1、2019年春运筹学期末考试复习题 注意事项：本复习题满分共：400分。一、单项选择题（本大题共 28小题，每小题4分，共112分）1、下列叙述正确的是（）。A.线性规划问题，若有最优解，则必是一个基变量组的可行基解B.线性规划问题一定有可行基解C.线性规划问题的最优解只能在最低点上达到D.单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次答案：A TOC o 1-5 h z 2、数学规划的研究对象为（）。A.数值最优化问题B .最短路问题C .整数规划问题D .最大流问题答案：A3、下列方法中可以用来求解部分树的方法的为（）。A.闭回路法B .破圈法 C .踏石法D .匈牙利算法

2、答案：B4、把各种备选方案、可能出现的状态和概率以及产生的后果绘制在一张图上，称为（）。A.决策树B .最大流 C .最小支撑树D.连通图答案：A5、以下说法中，不属于无概率决策问题（不确定型决策问题）的特点的为（）。A.决策人面临多种决策方案B.对每个决策方案对应的几个不同决策状态无法估计其出现概率的大小C.仅凭个人的主观倾向和偏好进行方案选择D.未来情况和条件出现的概率已知答案：D6、线性规划问题中决策变量应为（）。A.连续变量B .离散变量C .整数变量D .随机变量答案：A7、线性规划问题的数学模型由目标函数、约束条件和A.非负条件 B .顶点集合C答案：D8、典型的无概率决策准则，不

3、包括（）。A.乐观准则B .折中准则 C答案：D9、以下说法中不正确的为（）。A.完成各个作业需要的时间最长的路线为关键路线C.所有关键作业的总时差为 0D:）三个部分组成。最优解 D .决策变量.等可能准则 D .最大后悔值准则B .关键路线上的作业称为关键作业.以上说法均不正确答案：D10、（）也称小中取大准则。这是一种在不确定型决策问题中，充分考虑可能出现的最小收益后，在 最小收益中再选取最大者的保守决策方法。.等可能准则D .后悔值准则）B.无穷多最优解D.惟一最优解A.悲观准则B .折中准则 C答案：A11、当某个非基变量检验数为零，则该问题有（A.无解C.退化解答案：BP和D,则有

4、（）。12、假设对于一个动态规划问题，应用顺推法以及逆推解法得出的最优解分别为B. PDC. P=DD.不确定答案：C13、下列有关线性规划问题的标准形式的叙述中错误的是（）。A.目标函数求极大B.约束条件全为等式C.约束条件右端常数项全为正D.变量取值全为非负答案：C14、运输问题的基变量有（）个。A. mx nB. m+n-1m+nD.不确定答案：B）,表不该目标越重要。15、目标规划的目标权系数是定量的概念，数值（A.越小B.越大C.为0D.为正答案：B16、下列叙述正确的是（）。A.线性规划问题，若有最优解，则必是一个基变量组的可行基解B.线性规划问题一定有可行基解C.线性规划问题的最

5、优解一定唯一D.单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次答案：A17、设M是线性规划问题，N是其对偶问题，则（）不正确。A. M有最优解，N不一定有最优解B.若M和N都有最优解，则二者最优值肯定相等C.若M无可行解，则N无有界最优解N的对偶问题为M答案：A18、PERT网络图中，（）表示为完成某个工序所需的时间或资源等数据。A.节点B.弧C.权D.圆圈答案：C19、网络的最大流量应（）它的最小割集的容量。A.大于B.等于C.小于D.不大于答案：B20、利用单纯形法求解线性规划问题时，判断当前解是否为最优解的标准为所有非基变量的检验数应为（ ）。A.正B.负C.非正D.非

6、负答案：C21、若原问题为无界解，则对偶问题的解是（）。A.无解B,无穷多解C.无界解D.不能确定答案：A22、PERT网络图中，（）表示一个事件，用圆圈和里面的数字表示。A.节点C.权答案：A23、具有7个节点的树T的边恰好为（）条。A. 5C. 7D答案：B24、下列数学模型中，（）是线性规划模型。MinZ=3xi+X22x3B.2x1+3x2-4x312401+x2+2x3 83xi-x 2+3x3=6xi0,x 2 无约束，x 3W 0B.弧D.关键路线68MaxZ=10 x+x2-3x 3x2i+5x222xj 0, j=1,2,3C.Z=5xi +6x2+8x3-9x 4 D. x

7、i+4x3-x 4=19 x2-5x 3+4x4 30 xi+x2-6x 40,j=1,2,3,4MaxZ=x+4x2-8x 3+x24 x x i+4x3-x 4=29 x2-5x 3+4x4 40 4 xi+x2-6x 40,j=1,2,3,4答案：A25、若线性规划问题的最优解不唯一，则在最优单纯形表上A.非基变量的检验数都为零B.非基变量检验数不必有为零者C.非基变量检验数必有为零D.非基变量的检验数都小于零答案：C26、对于总运输费用最小的运输问题，若已得最优运输方案，则其中所有空格的检验数均（）。A.非正B.非负C.大于0D.小于0答案：B27、下列步骤中，不属于目标规划模型图解法

8、的为（）。A.作平面直角坐标系B.作出目标约束所在直线，标出偏差方向C.作出目标函数的一族平行线D.按优先级次序，确定满意解答案：C28、下列关于图的说法中，错误的为（）。A点表示所研究的事物对象B.边表示事物之间的联系C.无向图是由点及边所构成的图D.无环的图称为简单图答案：D二、判断题（本大题共34小题，每小题2分，共68分） TOC o 1-5 h z 1、增加约束条件时，线性规划模型的可行域不扩大。（）答案：对2、决策变量、目标函数和约束条件是数学规划模型的三个要素，若目标函数和约束条件均为线性的数学规划问题称为非线性规划。（）答案：错3、产地数与销地数相等的运输问题是产销平衡运输问题

9、。（）答案：错4、能够通过网络的最大可行流称最大流。（）答案：对5、确定主观概率常用的方法是专家咨询法。（）答案：对6、在二人有限对策中，若甲乙双方的赢得总和不全为零，则称为二人有限非零和对策。（）答案：对7、完成各个作业需要的时间最长的路线称为关键路线。（）答案：对8、线性规划问题存在至少一个对偶问题。（）答案：错9、目标函数和约束函数都是非线性的数学规划问题称为线性规划问题。（）答案：错10、在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或是极小，原问题可行解的目标函数值都一定超过其对偶问题可行解的目标函数值。（）答案：错11、图的最小生成树一定唯一。（） 答案：错12、动态规划的

10、逆推与顺推解法得到不同的最优解。答案：错13、对于线性规划标准型，利用单纯形求解时，每做一次换基迭代，都能保证它相应的目标函数值必为不 TOC o 1-5 h z 减少。（）答案：对14、当目标规划问题模型中存在 X1 +x2 +d= 5的约束条件，则该约束为系统约束。（）答案：错15、PER刖络图中，事件通常用箭线表示，作业用圆圈表示。（）答案：错16、无多重边的图称为简单图。（）答案：错17、运输问题、最短路问题和求网络最大流问题，都可看作是最小费用流的特例。（）答案：对18、目标规划问题中，权系数是定量的概念，数值越大，表示该目标越重要。（）答案：对19、若线性规划问题存在可行域，则问题

11、的可行域是凸集。（）答案：对20、目标规划模型中，应同时包含系统约束与目标约束。（）答案：错21、PERT网络图中，任何消耗时间或资源的行动都可称作作业。（）答案：对22、任务分配问题共有 mx m个约束条件。（）答案：错23、树枝总长为最短的部分树称为图的最小部分树。（）答案：对24、目标的优先级是一个定性的概念，不同优先级的目标无法从数量上来衡量。（）答案：对25、单纯形法计算中，应选取最小正检验数对应的变量作为换入变量。（）答案：错26、当目标规划问题模型中存在 2x1 +x2 4的约束条件，则该约束为目标约束。（） 答案：错27、PERT网络图中，事件消耗一定的时间和资源。（）答案：错

12、28、在动态规划模型中，问题的阶段数等于问题中的子问题的数目。（）答案：对29、运输问题和求网络最大流问题，都可看作是最小费用流的特例。（）答案：对30、当网络中不存在任何增广链时，则网络达到最大流状态。（）答案：对31、在可行解的状态下，原问题与对偶问题的目标函数值是相等的。（）答案：错32、在解决运输问题时，采用闭回路法，可以得到运输问题的基本可行解。（）答案：错33、在整数规划问题中，若变量取值为0或者1,则为01规划问题。（）答案：对34、PER刖络图是由结点、弧及权所构成的有向图。（）答案：对三、名词解释（本大题共22小题，每小题5分，共110分）1、凸集1.如果n维空间的一个子集

13、S中任意两点X1、X2连线上的点都在 S中，则称为凸集。2、存储策略答案：存储策略是指决定多长时间补充一次货物以及每次补充多少数量的策略。3、无概率决策问题答案：无概率决策问题是指决策人面临多种决策方案，对每个决策方案对应的几个不同决策状态无法估计其出现概率的大小，仅凭个人的主观倾向和偏好进行方案选择。4、对策论答案：对策论又被称为博弈论，它是运筹学的一个重要分支，主要研究具有竞争或者对抗性质的现象和规律，在经济学、政治科学、军事科学、进化生物学以及当代的计算机科学等领域中有广泛的应用。5、可行解答案：求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性约束条件的解叫做可行解。6、

14、关键活动答案：为了完成整个项目的进度计划，需要找出其中最长的路径，即关键路径。关键路径上的活动称为项 目的关键活动。7、增广链答案：由发点到收点之间的一条链，如果在前向弧上满足流量小于容量，即fij0,则称这样的链为增广链。8、局势答案：局势是指在一局对策中，每个局中人从其策略集中各取出一个策略参与对策，这些策略合起来称为一个局势。9、线性规划的建模答：线性规划的建模是指将用语言文字描述的应用问题转化为用线性规划模型描述的数学问题。10、灵敏度分析答：灵敏度分析是分析研究一个线性规划模型中的参数A,b,C取值的变化对最优解或最优基的影响。11、基础图答：若把一个有向图 D中所有弧的方向去掉，即

15、每一条弧都有相应的无向边替代，所得到一个无向图称为该有向图D的基础图。12、纳什均衡答：在一局二人有限非零和对策中，无论对方的策略如何选择，本方都会选择某个确定的策略，则该策略被称为支配性策略。而由双方各自的支配性策略所构成的这个局势，就被定义为纳什均衡。13、正偏差变量答案：正偏差变量指实际值超出目标值的差距。14、作业的最早开始时间答案：作业的最早开始时间是它的各项紧前作业最早结束时间中的最大一个值。15、连通图答案：若一个图中，任意两点之间至少存在一条链，称这样的图为连通图。16、0-1规划问题答案：在整数规划问题中，若变量取值为0或者1,则为0-1规划问题。17、负偏差变量答案：负偏差

16、变量指实际值未达到目标值的差距。18、作业的最迟结束时间答案：作业的最迟结束时间是它的各项紧后作业最迟开始时间中的最小一个。19、最小割答案：网络中所有割集中容量之和为最小的一个割集。20、偏差变量答案：偏差变量指实际值与目标值的差距。d+表示实际值超出目标值的差距；d-表示实际值未达到目标值的差距。21、图答案：图是指点 V和边E的集合，用以表示对某种现实事物的抽象。其中点表示所研究的事物对象；边表 示事物之间的联系。22、容量网络答案：容量网络指对网络上的每条弧（Vi, Vj）都给出一个最大的通过能力，称为该弧的容量，记为C（Vi,Vj ）,简称容量。以 Cij表不。四、简答题（本大题共5

17、小题，每小题10分，共50分）1、简述何谓最小支撑树问题，最小支撑树问题的常用方法有哪些。答：如何找出网络的最小树就是最小支撑树问题。最小支撑树问题可以采用避圈法和破圈法等方法进行求解，也可借助相关的运筹学软件包进行求解。2、简述产销平衡运输问题的数学模型？答：具有m个产地ai （ i =1,2,，m）和n个销地bj（ j =1,2,，n）的运输问题的数学模型为m nmin z 二:二 Wij Xiji m j Tl mZ Xij = bj ,（j = 1,2, n）iT ns.t. Z Xij =ai, （i =1,2 m） jmXj之0对于产销平衡问题有 nm bj = ai j 1i 1

18、运输问题有mn个决策变量， m + n个约束条件。由于产销平衡条件，只有m+n-1个相互独立，因此，运输问题的基变量只有m - n -1个。3、简述树的性质？答：（1）任何树必存在次数为 1的点；（2）具有n个节点的树T的边恰好为 n -1条；（3）任何有n个节点，n ,1条边的连通图必是一棵树。4、简述整数规划的求解方法有哪些？答：整数规划的求解方法包括：（1）图解法；（2）分枝定（限）界法；（3）割平面法；（4）匈牙利法；（5）隐枚举法。5、简述网络图的绘制原则和注意事项？答：（1）节点标号原则：箭头节点的标号要大于箭尾节点的标号。（2）两个节点之间只能表示一道工序，只能划一条箭线。作业和

19、箭线是一对一的关系。（3）全图只有一个起点、一个终点。（4）不能出现缺口与回路。（5）各项作业之间的关系：1）作业a结束后可以开始 b和c2）作业c在a和b均结束后才能开始RYCr3） ab两项作业结束后才可以开始 c和d4)作业c在a结束后即可进行，但作业 d必须同时在a和b结束后才能开始(6)从左到有，从上到下，尽量避免交叉。五、计算题(本大题共3小题，每小题20分，共60分)1、某一最大化线性规划问题在利用单纯形法计算时得到表1。其中a,b,c,d,e, f为未知数，原问题中要求各变量均非负。问a,b,c,d,e, f应满足什么条件下，有下面各解成立？表1CBX BbX1X2X3X4X5

20、X6X3f7c10e0X42-1-501-10X66a-300-41cj -zjbd00-30(1)是非可行解；(2)是唯一最优解；(3)有无穷多最优解；(4)是退化基可行解；(5)是可行解但非最优解，只有人可以为换入变量且换出变量必为X6。解：(1)当所有基变量取值均非负时的基解才是可行基解，故当 f 0,b 0,d 0,d =0,b0o（4）现行解为退化基可行解的条件是基变量中含有零分量且所有的检验数均非正。所以 b 0,d 0,d 0 ；只有x6f6f6可以为换出变量，所以有故参数应满足：f之0,b A0,d M0 , o7a7a2、已知：（1）运输问题的供需关系与单位运价表（见表 1）

21、;（2）用最小元素法求得表 1的初始调运方案（见表 2）;试用闭回路法求其检验数，并判断此初始调运方案是否最优。表1供需关系与单位运价表肖地产地甲乙丙丁132765027523603254525销量60402015表2初始调运方案产地甲乙丙丁110405022520156032525销量60402015解：先找出各非基变量的闭回路，即从表2的某一空格（非基变量）为起点，用水平或垂直线，只有碰到数字格（基变量）后才旋转 90：继续向前划，直到回到起始空格为止。检验数的计算，就是从空格对应的单位运价开始，对闭回路所对应的单位运价交替地赋予“+”和“-”号，并计算它们的代数和，如表 3所示。表3空格

22、闭回路检验数（1丙）（1 丙）一（2 丙）一（2 甲）一（1 甲）一（1 丙）7-2+7-3=9（1 丁）（1 丁）一（ 2丁）一（ 2 甲）一（1 甲）一（1 丁）6-3+7-3=7（2乙）（2 乙）一（2 甲）一（1 甲）一（1 乙）一（2 乙）5-7+3-2=-1（3乙）（3 乙）-（3 甲）-（1 甲）-（1 乙）-（3 乙）5-2+3-2=4（3丙）（3 丙）-（3 甲）-（2 甲）-（2 丙）-（3 丙）4-2+7-2=7（3 丁）（3 丁）-（3 甲）-（2 甲）-（2 丁）-（3 丁）5-2+7-3=7选出检验数最小的为（-1 ）,小于0,所以该初始调运方案不是最优调运方案。3

23、、试用单纯形法解下列线性规划问题max z = x1 2x22x1 2x2 . 8s.t. J0 x1 + 2x2 0解：化标准形，找一个单位矩阵作为基，列出初始单纯形表max z = x1 2x2 0 x3 0 x42x1 2x2 x3=8st. 0 x1 十 2x2+ x4 = 4x1, x2, x3,刈2 0建立初始单纯形表o 11 o2 22 o_-A如表1所示，其中Cj为目标函数中决策变量 Xj的系数（j =1,2,3,4）,由系数矩阵选择单位矩阵B1= 1 0 作为初始可行基，则对应的基变量为XB =（x3, x4）T ,基变量的系数CB=（0,：0 1 一0）,常数向量（资源向量

24、）b =（8,4）T ,列出约束方程组的增光矩阵 bA.（注：XB所对应的列的变量（x3,X4）为基变量，其余的变量都为非基变量）计算初始单纯形表中的检验数Cj1200b/ =6./ aik1CbX BbXiX2X3X40X3822108/2=40X440【2】014/2=2 tCj -Zj1200表2进行迭代运算，得出下一个单纯形表，对增广矩阵进行线性变换，将主元素变为Cj -Zj =Cj -CBB-Pj=Cj CbR，如非基变量 刈*2的检验数:C14=0 CBP(1)=1- (0 0)L- (0*2+0*2) =10C2_Z2=C2 CbP2=2- (0 0)1=2- (0*2+0*2)