《运筹学》复习题.doc

运筹学-学习指南一、名词解释1松弛变量为将线性规划问题的数学模型化为标准型而加入的变量。2可行域满足线性约束条件的解（x,y）叫做可行解，由所有可行解组成的集合叫做可行域。3人工变量亦称人造变量.求解线性规划问题时人为加入的变量。用单纯形法求解线性规划问题，都是在具有初始可行基的条件下进行的,但约束方程组的系数矩阵A中所含的单位向量常常不足m个，此时可加入若干(至多m)个新变量，称这些新变量为人工变量。4对偶理论每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同时，也给出了另一个问题的解。研究线性规划中原始问题与对偶问题之间关系的理论5灵敏度分析研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。6影子价格反映资源配置状况的价格。影子价格是指在其他资源投入不变的情况下,每增加一单位的某种资源的投入所带来的追加收益。即影子价格等于资源投入的边际收益。只有在资源短缺的情况下,每增加一单位的投入才能带来收益的增加7产销平衡运输一种特殊的线性规划问题。产品的销售过程中，产销平衡是指工厂产品的产量等于市场上的销售量。8西北角法是运筹学中制定运输问题的初始调运方案（即初始基可行解）的基本方法之一。也就是从运价表的西北角位置开始，依次安排m个产地和n个销地之间的运输业务，从而得到一个初始调运方案的方法。 9最优性检验检验当前调运方案是不是最优方案的过程。10动态规划解决多阶段决策过程优化问题的方法：把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解11状态转移方程从阶段K到K+1的状态转移规律的表达式12逆序求解法在求解时，首先逆序求出各阶段的条件最优目标函数和条件最优决策，然后反向追踪，顺序地求出改多阶段决策问题的最优策略和最优路线。13最短路问题最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。14最小费用最大流在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。15排队论排队论(queueing theory), 或称随机服务系统理论, 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。二、选择题1. 用图解法求解一个关于最大利润的线性规划问题时，若其等利润线与可行解区域相交，但不存在可行解区域最边缘的等利润线，则该线性规划问题( B )。 A、有无穷多个最优解 B、有可行解但无最优解 C、有可行解且有最优解 D、无可行解2. 若线性规划问题的最优解同时在可行解域的两个顶点处达到，则此线性规划问题的最优解为（ B ）A、两个 B、无穷多个C、零个 D、过这的点直线上的一切点3. 用图解法求解一个关于最小成本的线性规划问题时，若其等成本线与可行解区域的某一条边重合，则该线性规划问题( A )。A有无穷多个最优解B、有有限个最优解C有唯一的最优解D无最优解4. 在求极小值的线性规划问题中，引入人工变量之后，还必须在目标函数中分别为它们配上系数，这些系数值应为( A )。A、很大的正数 B、较小的正数 C、1 D、05. 对问题的标准型：，利用单纯形表求解时，每做一次换基迭代，都能保证它相应的目标函数值必为（ B ）A 增大 B 不减少 C 减少 D 不增大6. 若最优解不唯一，则在最优单纯形表上（ A ）A 非基变量的检验数必有为零者 B 非基变量的检验数不必有为零者C 非基变量的检验数必全部为零 D 以上均不正确7. 求解线性规划模型时，引入人工变量是为了（ B ）A 使该模型存在可行解 B 确定一个初始的基可行解C 使该模型标准化 D 以上均不正确11. 用大法求解模型时，若在最终单纯形表上基变量中仍含有非零的人工变量，则原模型（ C ）A 有可行解，但无最优解 B 有最优解C 无可行解D 以上都不对12. 已知，是某的两个最优解，则（ D ）也是的最优解。A B C D 无法判断13、线性规划问题的灵敏度分析研究（ BC ） A、对偶单纯形法的计算结果； B、目标函数中决策变量系数的变化与最优解的关系； C、资源数量变化与最优解的关系； D、最优单纯形表中的检验数与影子价格的联系。14、对偶单纯形法迭代中的主元素一定是负元素（ A ）A、正确B、错误C、不一定D、无法判断15、对偶单纯形法求解极大化线性规划时，如果不按照最小化比值的方法选取什么变量则在下一个解中至少有一个变量为正（ 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不能形成C、可以形成 D有可能形成20、运输问题可以用( B )法求解。 A、定量预测 B、单纯形 C、求解线性规划的图解 D、关键线路21、在运输问题的表上作业法选择初始基本可行解时，必须注意（ AD ）。 A、针对产销平衡的表； B、位势的个数与基变量个数相同； C、填写的运输量要等于行、列限制中较大的数值； D、填写的运输量要等于行、列限制中较小的数值。22、用增加虚设产地或者虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输问题 （ A ）A、正确B、错误C、不一定D、无法判断23、通过什么方法或者技巧可以把产销不平衡运输问题转化为产销平衡运输问题( C )A、非线性问题的线性化技巧B、静态问题的动态处理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、正确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、决策变量的允许取值范围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、1700600700300500400锅炉房12337. 在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20 km25km，则（ D ）。 A、最短路线定通过A点 B、最短路线一定通过B点C、最短路线一定通过C点 D、不能判断最短路线通过哪一点38. 在一棵树中，如果在某两点间加上条边，则图一定( A ) A、存在一个圈 B、存在两个圈C、存在三个圈D、不含圈39 网络图关键线路的长度( C )工程完工期。 A大于 B小于 C等于 D不一定等于40. 在计算最大流量时，我们选中的每一条路线( C )。A、一定是一条最短的路线 B、一定不是一条最短的路线C、是使某一条支线流量饱和的路线 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、服务机构D、服务时间46排队系统中，若系统输入为泊松流，则相继到达的顾客间隔时间服从什么分布（ D ）A、正态分布B、爱尔朗分布C、泊松流D、负指数分布47研究排队模型及数量指标的思路是首先明确系统的意义，然后（ ABC ）A、写出状态概率方程B、写出状态转移速度矩阵C、画出状态转移速度图D、写出相应的微分方程48排队系统的状态转移速度矩阵中（ B ）元素之和等于零。A、每一列B、每一行C、对角线D、次对角线三、计算题1.用图解法求解下列问题 答案：依题有可得最优解集合为 也即最优值为 （详细求解过程略去）2. 用分枝界定法求解下列线性规划问题答案：松弛问题的最优解为 x1=2.5, x2=2, OBJ=23 由x1=2.5 得到两个分枝如下： 和 各个分枝问题的松弛解为问题I问题IIx123x29/41f(x)2122问题II的解即原整数问题的最优解3、已知线性规划问题要求：（1）化为标准型式（2）列出用两阶段法求解时第一阶段的初始单纯形表解：（1）令 原模型可以转化为（2）见下表000000-11-11515-33-10100205-610-100100-15111-10001-26-22-10004、求下列线性规划问题，并写出问题的对偶问题 答案： 对偶问题：5、求出下列问题的对偶问题并分别队原问题及对偶问题求解答案：用单纯型法求解过程Cj 536-600-MCBXBbx1x2x3x3x4x5x60x418121-11000x51621(3)-3010-Mx610111-1001OBJ=-10M-M-M-MM00-Mcj - zj5+M3+M6+M-6-M0000x438/31/35/3001-1/306x316/32/31/31-101/30-Mx614/31/3(2/3)000-1/31OBJ=32-14M/34-M/32-2M/36-602+M/3-Mcj - zj1+M/31+2M/3000-2-M/300x41-1/200011/2-5/26x33(1/2)01-101/2-3/23x271/21000-1/23/2OBJ=399/236-603/23/2cj - zj1/20000-3/2-M-3/20x44001-111-35x16102-201-13x2401-1(1)0-12OBJ=42537-702-1cj - zj00-110-2-M+10x48010010-15x11412000-13-6x3401-110-12OBJ=46546-6013cj - zj0-1000-1-M-3对偶问题最优解：y4=0y5=1y6=0y1=0y2=1y3=3原问题最优解：x1=14, x2=0, x3=-4, x4=8, x5=0, x6=0, OBJ=466、 运输问题的数据如下表： B1 B2 B3 B4产量A1A2A3 2 2 3 7 4 3 5 9 1 6 7 8500600300销量 300 200 500 400求最优运输方案。答案：最优方案： f * = 6000 B1 B2 B3 B4产量A1A2A3 100 400 200 400 300 500600300销量 300 200 500 4007、 对于以下运输问题，如何用最小元素法求出初始调运方案？ 答案：求解过程如下。表中“”内数字为删除线出现的先后顺序。8、判断下表中给出的调运方案能否作为表上作业法求解的初始方案？为什么？销地运量产地产量2525201030202052530销量2020301025105答案：不能作为初始方案。因为数字格只有6个，而9、某奶牛站希望通过投资来扩大牛群数，开始只有5000元资金，现在已知可购入A或者B两个品种的奶牛，对于A种牛每投入1000元，当年及以后每年可以获得500元和2头小牛，对种牛每投入1000元，当年及以后每年可以获得200元和3头小牛。问：（1）在今后的四年内应该如何分配投资使奶牛群最大（2）到第四年底奶牛站将有多少头奶牛。答案：状态为阶段可利用的资金；决策为阶段向种牛投入的资金数；为阶段向种牛投入的资金数；则转移函数为递推函数：表示在阶段出生的小牛数；第四年末牧场主应拥有的牛的头数为70头10. 求下面容量网络的最大流，弧边上括号内第一个数为容量，第二个数为流量。（1）、根据标号过程找出增广链，确定流量修正量；（2）、调整流量，画出最大流图，说明最大流量是多少；（3）、根据标号和求解过程确定最小割并算出最小割容量； V2 V4 (3,2) (4,1) V1 (3,1) (1,1) (3,1) V6 (2,0) (2,2) (3,1) (2,2) V3 V5、解：V1V22+V4V63+1+ 1.增广链： （,1）（,2）V2V4（,3）（3,3）（4,2）（-,）V1V6（3,2）(1,1)（3,1）（2,0）V3V5（2,2）（3,1）（2,2）（,2）图1（,1）（,1） 2.V2V4（,2）（3,3）（4,3）（-,）V1V6（3,3）（3,0）（2,1）(1,1)V3V5（2,2）（3,1）（2,2）（,2）图2+V6V4-+2+2V511V2V1增广链 标号过程中，图2为最大流图，最大流量3. 其节点均属则最小割为，最小割容量为3+2=511、一台研磨机对某种工件进行加工，研磨一个工件的时间服从负指数分布，平均需要2分钟。工件的到达服从泊松分布，平均每小时到达25件。试求： 该研磨机空闲的概率和恰巧有5件工件等待研磨的概率？ 每件工件在加工前平均等待的时间是多少？平均等待的工件有多少件？ 一个工件从送达到研磨完，时间超过20分钟的概率？ 等待研磨的工件在810件的概率。答案：模型：M/M/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 (m - l ) = 3.72 10- 44 ；4）P7 P8 P9 0.0465 + 0.0388 + 0.0323 = 0.117612、一台研磨机对某种工件进行加工，研磨一个工件的时间服从负指数分布，平均需要2分钟。工件的到达服从泊松分布，平均每小时到达25件。试求：（1）该研磨机空闲的概率和恰巧有5件工件等待研磨的概率？（2）每件工件在加工前平均等待的时间是多少？平均等待的工件有多少件？（3）一个工件从送达到研磨完，时间超过20分钟的概率？ （4）等待研磨的工件在810件的概率。答案：模型：M/M/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 (m - l ) = 3.72 10- 44 ；4）P7 P8 P9 0.0465 + 0.0388 + 0.0323 = 0.1176 。