运筹学部分试题

广东工业大学试卷用纸，共9页第1页学院：专业：学号：姓名：装订线广东工业大学考试试卷(B)课程名称:运筹学试卷满分100分考试时间:题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、判断题（每题2分，共20分）1、线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。2、当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。3、对一个动态规划问题，应用顺序法或逆序法可能会得出不同的最优解。4、线性规划的最优解的基变量的值等于零，则线性规划问题有无穷多个最优解。5、表上作业法实质上就是求解运输问题的单纯形法。6、在用大M法求解线性规划问题时，人工变量变量在目标函数中的系数取为M。7、目标规划问题的偏差变量一定非负。8、整数规划问题的松弛问题的可行解必定是整数规划的可行解9、任一图中，当点集确定后，树是该图中边数最少的连通图。10、运输问题可能是无界解（）二、单项选择题（每小题2分，共14分）1、下面哪一项不属于线性规划的标准形式的基本要求（）A．除非负约束外，约束条件为等式B．目标函数最小化C．约束条件右端常数非负D．各决策变量只能取非负值。2、根据互补松弛性定理，线性规划原问题第j个约束是严格不等式，则对偶问题中第j个变量是（）。广东工业大学试卷用纸，共9页第2页A．xj≥0B．xj≤0C．xj=0D．不一定3、有m个产地，n个销地的产销平衡的运输问题中，用表上作业法求解得到时，表中空格数是（）。A．m×nB．m+n－1C．m+nD．m×n－(m+n－1)4、关于树下列说法不正确的是（）A．它是连通的无圈图B．去掉任一条边后不再连通C．两顶点间存在唯一一条道路D．边数可能大于顶点数5、对于容量网络下列说法正确的是（）A．增广链上所有前向边都是饱和边B．增广链可能存在着后向边是零流边C．若一个可行流中存在增广链，则该可行流不是最大流D．可能不存在可行流6、对于指派问题下列说法正确的是（）A．匈牙利法可直接用来求解最大化指派问题B．在用匈牙利法求解指派问题时，承担任务的人数可以不等于任务数C．将系数矩阵的某行元素都加上同一个非零常数，最优解不变D．用匈牙利法求解时系数矩阵的元素可以是负数7、下面哪一条不是标准指派问题的要求（）A．目标函数最大化B．承担任务的人数等于任务数C．一人只能承担一项任务D．一项任务只能由一人承担也必须由一人承担三、（15分）求解下列运输问题，表格中间的数字为单位运价。产销甲乙丙丁产量A3113107B19284C741059销量3656广东工业大学试卷用纸，共9页第3页四、（15分）用逆序法或顺序法，求解最短路问题。五、（6分）求下图所示网络中的最大流，每条边上的序数表示（cij,fij）AB1B2B3C1C3C2D1D2E789565875935621334V1V4V7V3V2V5V6531472321651广东工业大学试卷用纸，共9页第4页六、（10分）用匈牙利法求解下属指派问题，已知效率矩阵如下：1096109532485724679278310283七、（20分）已知线性规划问题0XX8X2X59X4X3tsX5X10Z21212121,..max用单纯形法求的最终单纯形表如下：X1X2X3X4X23/2015/14-3/14X1110-1/72/700-5/14-25/14（1）写出对偶问题的最优解。（4分）（2）右端项由89变为911时，该问题的最优解如何变化？（10分）（3）目标函数为maxz=12x1+4x2时，上述最优解如何变化？（6分）一、单项选择题（本大题有8小题，每小题2分，共16分）1、在单纯性法计算中，如果检验数都小于等于零，而且非基变量的检验数全为负数，则表明此问题有（）。A、无穷多组最优解B、无最优解C、无可行解D、唯一最优解2、互相对偶的两个线性规划问题，若其中一个无可行解，则另一个必定（）。A、无可行解B、有可行解，也可能无可行解C、有最优解D、有可行解3、资源的影子价格是一种（）。A、机会成本B、市场价格C、均衡价格D、实际价格4、检验运输方案的闭合回路法中，该回路含有（）个空格为顶点。A、4个B、2个C、1个D、3个广东工业大学试卷用纸，共9页第5页5、m个产地，n个销地的初始调运表中，调运数字应该为（）A、m+n个B、m+n--１个C、m×nD、m+n+1个6、下图中，从起始端到末端的最短路长度为A、10B、11C、12D、137、在网络图中，关键线路是指各条线路中作业总时间（）的一条线路。A、最短B、中间C、成本最小D、最长8、具有n个顶点的树的边数是（）。A、n个B、n-1个C、n+1个D、n+2个二、填空题（本大题有5小题，每空2分，共10分）9、可行域中任意两点间联结线段上的点均在可行域内，这样的点集叫。10、线形规划的标准形式有如下四个特点：、、、。11、一个模型是m个约束，n个变量，则它的对偶模型为个约束，个变量。12、PERT图中，事件（结点）的最早开始时间是各项紧前作业最早结束时间中的。13、动态规划是解决最优化问题的一种理论和方法。14、预测的原理有、、。三、简答题（本大题有2小题，每小题5分，共10分）15、写出下列线性规划模型的对偶问题-公式传不上来16、介绍什么是表上作业法四、计算题（合计64分）17、已知下列线性规划问题：用单纯型法求解：(22分)-公式传不上来广东工业大学试卷用纸，共9页第6页18、请计算出下面这个网络图的各工序最早完工时间和最迟开始时间，并指出它的关键线路。(20分)-图传不上来19、请用表上作业法解下题，得到最优解,并计算此时总运费：现在有运价表如下:(22分)产地销地BBB产量A51612A24014A3674销量91011一、单项选择题（共10分）1、D；2、B；3、A；4、C；5、B；6、A；7、D；8、B；二、填空题（共25分）9、凸集；10、目标最大化、约束为等式、决策变量均非负、右端项非负；11、n、m；12、最大值。13、多阶段决策过程；14、慢性原理、类推原理、相关原理；三、简答题（共10分）15、写出下列线性规划模型的对偶问题答：16、答：运输问题的数学模型是利用产销平衡表和单位运价表来直接求解，其称为表上作业法。四、计算题（合计64分）17、解：（22分）用单纯型法求解：(22分：三阶段，每阶段5分，计15分；结果值7分)广东工业大学试卷用纸，共9页第7页解：上式转化成：18、解：由上图可见：ACDG为关键线路（20分）19、根据上面运价表以及销量和产量的要求，使用表上作业法：51624036791011得到下面运输方案：210检验空格：210A3113D1144CB空格A检验：6–5+2–0=30空格B检验：7–0+2–3=60空格C检验：6-1+5–3=70空格D检验：4–1+5–2=60故全部符合要求。总运输费用：2×5+3×2+4×3+10×1+11×0=38答：上面的运输方案为最佳方案，总运费为38。（22一、不定项选择题(每小题3分，共9分)1．下列说法正确的是（）A、图解法同单纯行法虽然求解的形式不同，但从几何上解释，两者是一致的；B、线性规划问题的每一个基解对应可行域的一个顶点；C、如果线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点；D、线性规划问题的任意可行解都可以用全部基可行解的线形组合来表示。2．下列说法正确的是（）A、线性规划问题是目标规划问题的一种特殊形式；广东工业大学试卷用纸，共9页第8页B、正偏差变量应取正值，负偏差变量应取负值；C、目标规划模型中，应同时包含绝对约束与目标约束；D、当目标规划问题模型中存在的约束条件，则该约束为绝对约束。3．下列说法错误的是（）A、整数规划解的目标函数值一般优于其相应的线性规划问题解的目标函数值；B、用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值；C、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解；D、求解0-1规划的隐枚举法是分枝定界法的特例。二、判断题（每小题2分，共10分）1．若线性规划原问题有无穷多最优解，则其对偶问题也具有无穷多最优解。（）2．如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。（）3．表上作业法实质上就是求解运输问题的单纯形法。（）4．用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较剪枝。（）5．动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性。（）三(20分)、考虑下列线性规划：1(7分)、化标准形式，求最优解；2(4分)、写出最优基和它的逆；3(2分)、求此线性规划的对偶问题的最优解；4(2分)、试求在什么范围内，此线性规划的最优解不变；5(5分)、若变为45，最优解及最优值是什么。四(10分)、已知线性规划问题：1(5分)、写出对偶问题；2(5分)、已知原问题的最优解为，求对偶问题的最优解。五(13分)、已知运输问题的运价表及初始方案如下：BjCijAiB1B2B3B4BjXijAiB1B2B3B4A1512411A110616A221039A28210A385116A314822广东工业大学试卷用纸，共9页第9页8141214要求：1（8分）、求最佳调运方案；2（5分）、如B2的销量增加到20，试把问题化为平衡的运输问题。六(10分)、用图解法解下列目标规划模型。七(12分)、有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D不同的工作，每人做各项工作所消耗的时间如下表所示：ABCD甲791012乙13121517丙15161415丁11121516问：应该如何指派，才能使总的消耗时间为最少。八(8分)、用动态规划方法解下列非线性规划问题（只建模,不求解）：九(8分)、计算下图所示的从A到E的最短路。