《运筹学》复习题.pdf

《《运筹学》复习题.pdf》由会员分享，可在线阅读，更多相关《《运筹学》复习题.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学 -学习指南一、名词解释1 松弛变量为将线性规划问题的数学模型化为标准型而加入的变量。2 可行域满足线性约束条件的解（x,y）叫做可行解，由所有可行解组成的集合叫做可行域。3 人工变量亦称人造变量.求解线性规划问题时人为加入的变量。用单纯形法求解线性规划问题，都是在具有初始可行基的条件下进行的,但约束方程组的系数矩阵A 中所含的单位向量常常不足m 个，此时可加入若干(至多 m)个新变量，称这些新变量为人工变量。4 对偶理论每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同时，也给出了另一个问题的解。研究线性规划中原始问题与对偶问题之间关系的理论5 灵敏度分析研究与分析一个系

2、统（或模型） 的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。6 影子价格反映资源配置状况的价格。影子价格是指在其他资源投入不变的情况下,每增加一单位的某种资源的投入所带来的追加收益。即影子价格等于资源投入的边际收益。只有在资源短缺的情况下 ,每增加一单位的投入才能带来收益的增加7 产销平衡运输一种特殊的线性规划问题。产品的销售过程中，产销平衡是指工厂产品的产量等于市场上的销售量。8 西北角法是运筹学中制定运输问题的初始调运方案（即初始基可行解）的

3、基本方法之一。也就是从运价表的西北角位置开始，依次安排m 个产地和n 个销地之间的运输业务，从而得到一个初始调运方案的方法。9 最优性检验检验当前调运方案是不是最优方案的过程。10 动态规划解决多阶段决策过程优化问题的方法：把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解11 状态转移方程从阶段 K 到 K+1 的状态转移规律的表达式12 逆序求解法在求解时， 首先逆序求出各阶段的条件最优目标函数和条件最优决策，然后反向追踪， 顺序地求出改多阶段决策问题的最优策略和最优路线。13 最短路问题最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之

4、间的最短路径。14 最小费用最大流在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A 到 B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。15 排队论排队论 (queueing theory), 或称随机服务系统理论, 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。二、选择题1. 用图解法求解一个关于最大利润的线性规划问题时，若其等利润线与可行

5、解区域相交，但不存在可行解区域最边缘的等利润线，则该线性规划问题( B )。A、有无穷多个最优解B、有可行解但无最优解C、有可行解且有最优解D、无可行解2. 若线性规划问题的最优解同时在可行解域的两个顶点处达到，则此线性规划问题的最优解为（B ）A、两个B、无穷多个C、零个D、过这的点直线上的一切点3. 用图解法求解一个关于最小成本的线性规划问题时，若其等成本线与可行解区域的某一条边重合，则该线性规划问题( A )。A有无穷多个最优解B、有有限个最优解C有唯一的最优解D无最优解4. 在求极小值的线性规划问题中，引入人工变量之后，还必须在目标函数中分别为它们配上系数，这些系数值应为( A )。A

6、、很大的正数B、较小的正数C、 1 D、0 5. 对LP问题的标准型：max,0ZCX AXb X，利用单纯形表求解时，每做一次换基迭代，都能保证它相应的目标函数值Z必为（B ）A 增大B 不减少C 减少D 不增大6. 若LP最优解不唯一，则在最优单纯形表上（A ）A非基变量的检验数必有为零者B 非基变量的检验数不必有为零者C 非基变量的检验数必全部为零D 以上均不正确7. 求解线性规划模型时，引入人工变量是为了（B ）A 使该模型存在可行解B 确定一个初始的基可行解C 使该模型标准化D 以上均不正确11. 用大M法求解LP模型时， 若在最终单纯形表上基变量中仍含有非零的人工变量，则原模型（C

7、 ）A 有可行解，但无最优解B 有最优解C 无可行解D 以上都不对12. 已知1(2,4)x，2(4,8)x是某LP的两个最优解，则（D ）也是LP的最优解。A (4,4)xB (1,2)xC (2,3)xD 无法判断13、线性规划问题的灵敏度分析研究（BC ）A、对偶单纯形法的计算结果；B、目标函数中决策变量系数的变化与最优解的关系；C、资源数量变化与最优解的关系；D、最优单纯形表中的检验数与影子价格的联系。14、对偶单纯形法迭代中的主元素一定是负元素（A ）A、正确B、错误C、不一定D、无法判断15、 对偶单纯形法求解极大化线性规划时，如果不按照最小化比值的方法选取什么变量则在下一个解中至

8、少有一个变量为正（B ）A、换出变量B、换入变量C、非基变量D、基变量16、影子价格是指（D）A、检验数B、对偶问题的基本解C、解答列取值D、对偶问题的最优解17、影子价格的经济解释是（C ）A、判断目标函数是否取得最优解B、价格确定的经济性C、约束条件所付出的代价D、产品的产量是否合理18、在总运输利润最大的运输方案中，若某方案的空格的改进指数分别为IWB=50 元，IWC=-80 元， IYA=0 元， IXC=20 元，则最好挑选( A )为调整格。A、WB 格B、WC 格C、 YA格D、 XC 格19、在一个运输方案中，从任一数字格开始，( B )一条闭合回路。A可以形成至少B不能形成

9、C、可以形成D有可能形成20、运输问题可以用( B )法求解。A、定量预测B、单纯形C、求解线性规划的图解D、关键线路21、在运输问题的表上作业法选择初始基本可行解时，必须注意（AD ） 。A、针对产销平衡的表；B、位势的个数与基变量个数相同；C、填写的运输量要等于行、列限制中较大的数值；D、填写的运输量要等于行、列限制中较小的数值。22、 用增加虚设产地或者虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输问题（ A ）A、正确B、错误C、不一定D、无法判断23、通过什么方法或者技巧可以把产销不平衡运输问题转化为产销平衡运输问题( C ) A、非线性问题的线性化技巧B、静态问题的动态处

10、理C、引入虚拟产地或者销地D、引入人工变量24、动态规划方法不同于线性规划的主要特点是（AD ） 。A、动态规划可以解决多阶段决策过程的问题；B、动态规划问题要考虑决策变量；C、它的目标函数与约束不容易表示；D、它可以通过时间或空间划分一些问题为多阶段决策过程问题。25、 用 DP 方法处理资源分配问题时，通常总是选阶段初资源的拥有量作为决策变量（ B ）A、正确B、错误C、不一定D、无法判断26、用 DP 方法处理资源分配问题时，每个阶段资源的投放量作为状态变量（B ）A、正确B、错误C、不一定D、无法判断27、 动态规划最优化原理的含义是：最优策略中的任意一个K-子策略也是最优的（A ）A

11、、正确B、错误C、不一定D、无法判断28动态规划的核心是什么原理的应用（A ）A、最优化原理B、逆向求解原理C、最大流最小割原理D、网络分析原理29动态规划求解的一般方法是什么？（C ）A、图解法B、单纯形法C、逆序求解D、标号法30 用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（ B ）A、任意网络B、无回路有向网络C、混合网络D、容量网络31动态规划的求解的要求是什么（ACD ）A、给出最优状态序列B、给出动态过程C、给出目标函数值D、给出最优策略32用动态规划解决生产库存的时候，应该特别注意哪些问题？（BC ）A、生产能力B、状态变量的允许取值范围C、决策变量的

12、允许取值范围D、库存容量33. 在网络计划技术中，进行时间与成本优化时，一般地说， 随着施工周期的缩短，直接费用是 ( C )。A、降低的B、不增不减的C、增加的D、难以估计的34. 最小枝权树算法是从已接接点出发，把( C )的接点连接上A、最远B、较远C、最近D、较近35. 在箭线式网络固中，( D )的说法是错误的。A、结点不占用时间也不消耗资源B、结点表示前接活动的完成和后续活动的开始C、箭线代表活动D、结点的最早出现时间和最迟出现时间是同一个时间36. 如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( C )。A 、1200 B、 1400 C、1300 D、1700 3

13、7. 在求最短路线问题中，已知起点到A，B，C 三相邻结点的距离分别为15km，20 km 25km，则（D ） 。A、最短路线 定通过 A 点B、最短路线一定通过B 点C、最短路线一定通过C 点D、不能判断最短路线通过哪一点38. 在一棵树中，如果在某两点间加上条边，则图一定( A ) A、存在一个圈B、存在两个圈C、存在三个圈D、不含圈39 网络图关键线路的长度( C )工程完工期。A大于B小于C等于D不一定等于40. 在计算最大流量时，我们选中的每一条路线( C )。A、一定是一条最短的路线B、一定不是一条最短的路线600 700 300 500 400 锅炉房1 2 3 C、是使某一条

14、支线流量饱和的路线D、是任一条支路流量都不饱和的路线41. 从甲市到乙市之间有公路网络，为了尽快从甲市驱车赶到乙市，应借用（C ）A、树的逐步生成法B、求最小技校树法C、求最短路线法D、求最大流量法42. 为了在各住宅之间安装一个供水管道若要求用材料最省，则应使用( B )。A、求最短路法B、求最小技校树法C、求最大流量法D、树的逐步生成法43排队系统状态转移速度矩阵中，每一列的元素之和等于0。 （ B ）A、正确B、错误C、不一定D、无法判断44. 排队系统中状态是指系统中的顾客数（A ）A、正确B、错误C、不一定D、无法判断45排队系统的组成部分有（ABC ）A、输入过程B、排队规则C、服

15、务机构D、服务时间46排队系统中，若系统输入为泊松流，则相继到达的顾客间隔时间服从什么分布（D ）A、正态分布B、爱尔朗分布C、泊松流D、负指数分布47研究排队模型及数量指标的思路是首先明确系统的意义，然后（ABC ）A、写出状态概率方程B、写出状态转移速度矩阵C、画出状态转移速度图D、写出相应的微分方程48排队系统的状态转移速度矩阵中（B ）元素之和等于零。A、每一列B、每一行C、对角线D、次对角线三、计算题1.用图解法求解下列LP问题12max2zxx12121212221228 416 .412 ,0 stxxxxxxx x答案：依题有可得最优解集合为1212(,) |(,)(2,3)(

16、1)(4,2),01aaax xx x也即1212(,) |(,)(42 ,2),01 aaax xx x最优值为8z（详细求解过程略去）2. 用分枝界定法求解下列线性规划问题12121212max( )6424132 7,0 f xxxxxxxx x且为整数答案：松弛问题的最优解为x1=2.5, x2=2, OBJ=23 由 x1=2.5 得到两个分枝如下：121212112max( )6424132 7I2,0 f xxxxxxxxx x问题且为整数和121212112max( )6424132 7II3,0 f xxxxxxxxx x问题且为整数各个分枝问题的松弛解为问题 I 问题 II

17、 x1 2 3 x2 9/4 1 f(x) 21 22 问题 II 的解即原整数问题的最优解3、已知线性规划问题123123123123123max5675315 561020 5 ,0 , zs.t.xxxxxxxxxxxxx xx无约束要求： （1）化为标准型式（2）列出用两阶段法求解时第一阶段的初始单纯形表解： （1）令133333;,0 xzzxxxxx x、，原模型可以转化为133333123346123351233712334567;,0533155610 10205 ,0 xzzxxxxxxxxxxxxxxxxxxxxxxx x xxx x x x、，（2）见下表0 0 0 0

18、0 0 -1 1 1x2x3x3x4x5x6x7x-1 6x15 1 5 -3 3 -1 0 1 0 0 5x20 5 -6 10 -10 0 1 0 0 -1 7x5 1 1 1 -1 0 0 0 1 jc-jz2 6 -2 2 -1 0 0 0 4、求下列线性规划问题，并写出LP问题的对偶问题1212121212max3224 3214 3 ,0 zs.t.xxxxxxxxx x答案：51315000244Xmax4Z对偶问题：12312312312,3min4143332220,0 w s.t.yyyyyyyyyyy5、求出下列问题的对偶问题并分别队原问题及对偶问题求解123123123

19、123123: max( )5362182316.10,0,f xxxxxxxxxxstxxxx xx原问题不限答案：123123123123123: min( )1816102523.36,0,g yyyyyyyyyystyyyy yy对偶问题不限用单纯型法求解过程Cj5 3 6 -6 0 0 M CBXBbx1x2x3x3x4x5x60 x418 1 2 1 1 1 0 0 0 x516 2 1 (3) 3 0 1 0 M x610 1 1 1 1 0 0 1 OBJ= 10M M M M M 0 0 M cj - zj5+M 3+M 6+M -6-M 0 0 0 0 x438/3 1/3

20、 5/3 0 0 1 1/3 0 6 x316/3 2/3 1/3 1 1 0 1/3 0 M x614/3 1/3 (2/3) 0 0 0 1/3 1 OBJ= 32-14M/3 4-M/3 2-2M/3 6 6 0 2+M/3 M cj - zj1+M/3 1+2M/3 0 0 0 -2-M/3 0 0 x41 1/2 0 0 0 1 1/2 5/2 6 x33 (1/2) 0 1 1 0 1/2 3/2 3 x27 1/2 1 0 0 0 1/2 3/2 OBJ= 39 9/2 3 6 6 0 3/2 3/2 cj - zj1/2 0 0 0 0 3/2 -M-3/2 0 x44 0 0

21、 1 1 1 1 3 5 x16 1 0 2 2 0 1 1 3 x24 0 1 1 (1) 0 1 2 OBJ= 42 5 3 7 7 0 2 1 cj - zj0 0 1 1 0 2 -M+1 0 x48 0 1 0 0 1 0 1 5 x114 1 2 0 0 0 1 3 6 x34 0 1 1 1 0 1 2 OBJ= 46 5 4 6 6 0 1 3 cj - zj0 1 0 0 0 1 -M3 对偶问题最优解：y4=0 y5=1 y6=0 y1=0 y2=1 y3=3 原问题最优解：x1=14, x2=0, x3=-4, x4=8, x5=0, x6=0, OBJ=466、 运输问

22、题的数据如下表：B1B2B3 B4产量A1 A2 A3 2 2 3 7 4 3 5 9 1 6 7 8 500 600 300 销量300 200 500 400 求最优运输方案。答案：最优方案：f * = 6000 B1B2B3 B4产量A1 A2 A3 100 400 200 400 300 500 600 300 销量300 200 500 400 7、 对于以下运输问题，如何用最小元素法求出初始调运方案？答案：求解过程如下。表中“”内数字为删除线出现的先后顺序。8、判断下表中给出的调运方案能否作为表上作业法求解的初始方案？为什么？1B2B3B4B5B产量1A25 25 2A20 10

23、30 3A20 20 4A5 25 30 销量20 20 30 10 25 105 答案：不能作为初始方案。因为数字格只有 6 个，而18nm销地运量产地9、某奶牛站希望通过投资来扩大牛群数，开始只有5000 元资金， 现在已知可购入A 或者 B两个品种的奶牛， 对于 A 种牛每投入1000 元，当年及以后每年可以获得500 元和 2 头小牛，对B种牛每投入1000 元，当年及以后每年可以获得200 元和 3 头小牛。问：（1）在今后的四年内应该如何分配投资使奶牛群最大（2）到第四年底奶牛站将有多少头奶牛。答案：状态nS为阶段n可利用的资金；决策nd为阶段n向 A 种牛投入的资金数；nnSd为

24、阶段n向B种牛投入的资金数；则转移函数为10.20.3nnnSSd递推函数：11()()()nnnnnnffSdSr(3);1000nnnnSdrnr表示在阶段n出生的小牛数45000S；第四年末牧场主应拥有的牛的头数为70 头10. 求下面容量网络的最大流，弧边上括号内第一个数为容量，第二个数为流量。（1） 、根据标号过程找出增广链，确定流量修正量；（2） 、调整流量，画出最大流图，说明最大流量是多少；（3） 、根据标号和求解过程确定最小割并算出最小割容量；V2V4 (3,2) (4,1) V1 (3,1)(1,1) (3,1) V6 (2,0) (2,2) (3,1) (2,2) V3 V

25、5、解：1.增广链：1min2,1,31V1V22 + V4V63 + 1 + （4V,3）（2V,2）2(,1)V（-,）（2,0）（2,2）（ 4,2）（ 3,1）（ 3,3）（3,1）(1,1) （ 2,2）（3,2）V6V5V4V3V2V1（1V,2）（2V,1）4(, 2)V2. 增广链2min 1,2,1,21标号过程中，图2 为最大流图，最大流量max325f3.1SV其节点均属S则最小割为1213(,)(,), (,)S SV VV V，最小割容量为3+2=5 11、一台研磨机对某种工件进行加工，研磨一个工件的时间服从负指数分布，平均需要2分钟。工件的到达服从泊松分布，平均每小

26、时到达25 件。试求： 该研磨机空闲的概率和恰巧有5 件工件等待研磨的概率？ 每件工件在加工前平均等待的时间是多少？平均等待的工件有多少件？ 一个工件从送达到研磨完，时间超过20 分钟的概率？ 等待研磨的工件在810 件的概率。答案：模型： M/M/1 参数： 25 件/小时， 0.5 件/分钟 30 件/小时， / = 5/6；1） P0 1 6 ，P6 0.0558 ；2）加工前平均等待时间wq = 10 分钟，平均等待的工件数Lq = 4.1667 件；3）P( T 20 ) = e-20 ( - ) = 3.72 10- 44 ；4）P7 P8 P9 0.0465 + 0.0388 +

27、 0.0323 = 0.1176 12、一台研磨机对某种工件进行加工，研磨一个工件的时间服从负指数分布，平均需要2分钟。工件的到达服从泊松分布，平均每小时到达25 件。试求：（1）该研磨机空闲的概率和恰巧有5 件工件等待研磨的概率？（2）每件工件在加工前平均等待的时间是多少？平均等待的工件有多少件？（3）一个工件从送达到研磨完，时间超过20 分钟的概率？（4）等待研磨的工件在810 件的概率。答案：模型： M/M/1 2 + V5（4V,2）（2V,2）（-,）（2,1）（ 2,2）（4,3）（ 3,0）（3,3）（3,1）(1,1) （ 2,2）（3,3）V6V5V4V3V2V1（1V,1）（5V,1）图 2 3(, 2)V图 1 V1V21 + V4V62 + 1 - 参数： 25 件/小时， 0.5 件/分钟 30 件/小时， / = 5/6；1） P0 16 ，P6 0.0558 ；2）加工前平均等待时间wq = 10 分钟，平均等待的工件数Lq = 4.1667 件；3）P( T 20 ) = e-20 ( - ) = 3.72 10- 44 ；4）P7 P8 P9 0.0465 + 0.0388 + 0.0323 = 0.1176 。