北京理工大学858运筹学历年考研真题汇编（含部分答案）.pdf

目录2015年北京理工大学858运筹学考研真题（回忆版）2014年北京理工大学858运筹学考研真题（回忆版）2013年北京理工大学858运筹学考研真题（回忆版）2012年北京理工大学858运筹学考研真题（回忆版）2010年北京理工大学858运筹学考研真题（回忆版）2008年北京理工大学858运筹学考研真题2008年北京理工大学858运筹学考研真题及详解2007年北京理工大学458运筹学考研真题2007年北京理工大学458运筹学考研真题及详解2006年北京理工大学458运筹学考研真题2006年北京理工大学458运筹学考研真题及详解2005年北京理工大学458运筹学考研真题2005年北京理工大学458运筹学考研真题及详解2004年北京理工大学458运筹学考研真题2004年北京理工大学458运筹学考研真题及详解2003年北京理工大学458运筹学考研真题2003年北京理工大学458运筹学考研真题及详解2002年北京理工大学430运筹学考研真题2002年北京理工大学430运筹学考研真题及详解2001年北京理工大学430运筹学考研真题2001年北京理工大学430运筹学考研真题及详解2000年北京理工大学430运筹学考研真题1999年北京理工大学运筹学考研真题2015年北京理工大学858运筹学考研真题（回忆版）2015年北京理工大学运筹学考研真题（回忆版）1考的是线性规划单纯形法计算和灵敏度分析（45分）大概是MAXZ=_X1+_X2+_X3_X1+_X2+_X3=_X1+_X2+_X3=_X1,X2=0,X3无约束第一问计算可行解（要迭代五次，所以一定要把计算的基本功打扎实）。第二问是写出对偶问题和对偶问题可行解。第三问是b的灵敏度分析，按题设要求b变化后，需要计算。第四问是c（基变量）变化，变化后需要计算。第五问是增设条件？我记不清了，但是第五问变化后，最优解不变。2整数规划，考的是隐枚举法（15分）Minf=_X1_X2_X3_X4_X1_X2_X3_X4_X5=_X1_X2_X3_X4_X5=_X1_X2_X3_X4_X50k1，2.10八、排队论每个电话持续时间3分钟，每个人的忍耐限度为3分钟。1能允许的最大通话量。2根据（1）求P0，Ls，Lq，Ws，Wq。2013年北京理工大学858运筹学考研真题（回忆版）2012年北京理工大学858运筹学考研真题（回忆版）2010年北京理工大学858运筹学考研真题（回忆版）2008年北京理工大学858运筹学考研真题2008年北京理工大学858运筹学考研真题及详解北京理工大学2008年攻读硕士学位研究生入学考试试题科目代码：858 科目名称：运筹学一、（10分）现有一求最大值的线性规划问题，对应下列含有未知变量的表，试讨论下表中a1，a2，c1，c2，d为何范围值时，表现为下列情况：（1）表中的解为唯一最优解；（2）表中解为无穷多最优解之一；（3）表中解为退化的可行解；（4）下一步迭代将以x1代替基变量x5；（5）该线性规划问题具有无界解；（6）该线性规划问题无可行解。解：（1）c10且c20，。（2）；c10，c20或c20，c10。（3）d0。（4）。（5）。（6）。二、（35分）某企业用甲、乙、丙三种原料生产A、B、C、D四种产品，每种产品消耗原料定额以及三种原料的数量如下表所示：求使总利润最大的生产计划。现求得最优单纯形表为：请解答下列问题：（1）写出此问题的线性规划模型及其对偶问题，并写出问题的最优解、最优基、最优基的逆和对偶问题的解；（2）解释最优生产计划中有的产品不安排生产的原因；（3）对产品B的利润进行灵敏度分析；（4）若原料甲增加420吨，影子价格是否变化，求原料甲增加后的最优解和各原料的影子价格。解：（1）设产品A、B、C、D分别生产万件，则可建立如下线性规划模型：其对偶问题为：问题的最优解为。最优基为最优基的逆对偶问题的最优解为。（2）产品A和D没有安排生产，原因是：虽然他们单位产品的利润高，但是生产时消耗的原料也多，这两种产品三种原料都消耗，而产品B和C都只消耗两种原料，在原料有限的情况下，生产A和D较生产B和C不划算，所以没有安排他们的生产。（3）设产品B的利润未知，则在最终单纯形表中，要满足各非基变量的检验数非正，则：解得，所以当时，最优解不发生变化，否则最优解发生变化。（4）原材料甲增加420吨后：中有负分量，所以最优解发生变化。用对偶单纯形法进行求解如下：2512 14 15000CBXBx1x2x3x4x5x6x712 x261011 0 5/41/21/4 014 x3160010 1 3/201/200 x7302 0 0 7/43/2 3/41z 2972010 0 2164012 x259501 0 3/81/4 1/81/214 x3158500 1 5/83/4 7/81/225 x11510 0 7/83/43/8 1/2z 2970500 0 161/8 21/4 35/8 1/2所以原料甲增加后的最优解为，原料甲、乙、丙的影子价格分别为21/4，35/8，1/2。三、（15分）现有某集团公司下属甲、乙、丙、丁、戊五个生产企业，生产同一种产品，价格、质量都相同。需要供应A、B、C三个地区。单位运输费用、各企业的产量、各地区的需求如下表。其中B地区的需求必须满足。集团公司的目标是使总运输费用最低。试求解这个的运输问题。解：这是一个产销不平衡的运输问题，销量大于产量，构造一个虚拟的产地己，其产量为10。由于B地区的需求必须满足，所以产地己到B地区的单位运价为M（无穷大的数），产地己到其他地区的单位运价为0。建立产销平衡表如下：地 销 地 产 甲 乙 丙 丁 戊 己 销量A7 3 9 4 11 0 30B4 2 5 6 10 M 24C6 8 12 2 5 0 36产量12 18 21 14 15 10 首先，用伏格尔法寻找得到初始基可行解。地 销 地 产 甲 乙 丙 丁 戊 己 销量A2 18 10 30B3 21 24C7 14 15 36产量12 18 21 14 15 10 用位势法计算各空格处的检验数为：从上表中可以看出，各非基变量的检验数均大于0，所以已求得最优解，总运费为330。四、（25分）某厂计划连续生产B产品，每月初开始生产。B的生产成本费为每吨X2千元，其中X是B产品当月的产量。仓库存货成本费是每月每吨1千元。估计3个月的需求量分别为5，10，15吨。现设开始时第1个月的月初库存为零，第3个月月末存货为零。试问：每月应生产多少吨B产品，可使总的生产和存货费用最小?（用动态规划方法求出最优解，不必求最优值）。解：按月份将问题划分为三个阶段，设为第k阶段对产品的需求量，为第k阶段生产产品B的吨数，为第k阶段结束时的产品库存量，则有。表示第k阶段生产产品B吨时的成本，表示在第k阶段结束时有库存量所需的库存费用。，。动态规划的顺序递推关系式为：边界条件：五、（20分）有三个研究小组同时独立研制某产品。为加强力量，决定选派3名专家到这三个小组去工作，已知增派人数分别为0，1，2，3人时各组的不成功概率由表给出，问应如何分派这三名专家，以使这三个小组同时不成功的概率都最小?解：将问题按研究小组分为三个阶段，设阶段变量为第k阶段至第3阶段可供增派的专家数，为第k阶段指派的专家数，状态转移方程为：。令为第k阶段指派的专家数为时，不成功的概论。最优值函数为第k阶段至第3阶段可供增派的专家数为时，不成功概论的最小值。因此，动态规划的逆序递推关系式为：边界条件：。k3时，其数值计算如下表所示。012300.9 0.901 0.7 0.712 0.6 0.623 0.5 0.53当k2时，其数值计算如下表所示。012300.60.9 0.54010.60.7 0.40.9 0.36120.60.6 0.40.7 0.30.9 0.27230.60.5 0.40.6 0.30.7 0.20.9 0.183当k1时，其数值计算如下表所示。012330.50.18 0.30.27 0.20.36 0.20.54 0.072 2所以，得到最优解为：。六、（30分）某电话亭有一部电话，来打电话的顾客数服从泊松分布，相继两个人到达间隔的平均时间为10分钟，通话时间服从负指数分布，平均数为3分钟。求：（1）顾客到达电话厅要等待的概率。（2）等待打电话的平均顾客数。（3）当一个顾客至少要3分钟才能打电话时，电信局打算增设一台电话机，问到达速度增加到多少时，装第二台电话机才合理的?（4）打一次电话要逗留10分钟以上的概率是多少?（可用指数式表示）（5）目前情况下，安装第二台电话机后，顾客的平均等待时间是多少?解：（1）（人/小时），（人/小时）；顾客到达电话厅要等待的概率为：。（2）。（3）由题意，令到达速度为 人/小时，则：。（4）顾客在系统中的逗留时间，服从参数为的负指数分布。在本题中，逗留时间，服从参数为的负指数分布。分布函数为；所以打一次电话要逗留10分钟以上的概率为：。（5）安装两部电话机后，系统变为M/M/2模型：；。七、（15分）某码头平均3天有2艘船停靠，平均每艘船需要1天时间卸货。设船的到达间隔时间和卸货时间服从负指数分布。船只在港口逗留一天给公司造成1000元的费用。港口现共有100名工人，他们每人的平均工资为30元/天，某咨询公司建议码头另招40名工人，并将全部工人分成两班，每班70人。这将导致每班为每船装卸时间变为3/2，你认为码头采用哪个方案好?为什么?答：以一个周期（3天）为例。（1）按码头的现有方案（为M/M/1系统）：（艘/天），（艘/天）；船只期望损失与港口工人成本之和为：。（2）按咨询公司建议的方案（为M/M/2系统）：（艘/天），（艘/天），；。船只期望损失与港口工人成本之和为：因为按咨询公司建议的方案的期望总成本较小，所以，应采纳咨询公司建议的方案。2007年北京理工大学458运筹学考研真题2007年北京理工大学458运筹学考研真题及详解北京理工大学2007年攻读硕士学位研究生入学考试试题科目代码：458 科目名称：运筹学一、（20分）考虑下列线性规划问题：1用单纯形法计算此问题，并写出最优解、最优值与最优基；答：将原问题改写为标准形式为：根据标准形式用单纯形法计算：114M 0 0M9 11210 0 9/202 11101 0 04 11100 1 4M1 M1 2M4 00 0 114 M 0 0M1 310 10 21/306 020 01 1_44 111 00 143M3 5M 0 00 2M4 1 14 M0 011/3 11/3 0 1/30 2/3 06020 01 1 413/3 02/31 1/30 1/3 040 M1 0 2 此时由计算可知，非基变量的检验数均不为正数，故已得到最优解，最优值为17，最优基为。2写出此线性规划问题的对偶问题，并求出对偶问题的解。答：对偶问题为：由原问题的最优解可知，对偶问题中的第一个和第三个约束条件是等式，且则对偶问题的最优解为，最优值为17二、（25分）某工厂生产甲、乙、丙三种产品，各种产品每件所需原料A分别为2、4、2 kg：每件所需原料B为4、6、5kg；消耗工时为6、3、8小时；各产品的利润分别为每件160、180、120元。每周企业可用于这些产品的工时为900小时，可提供的原料A、B分别为480 kg和800 kg。以总利润最大为目标考虑各产品的生产计划。通过计算，得到下列最优单纯形表：请解答下列问题：（1）写出此问题的线性规划模型及其最优解、最优基和最优基的逆；（2）把最优单纯型表中“*”的格中数字补充完整；（3）若产品乙的利润从180变为250而其它参数均不变时，问题的最优解和最优值是什么?答：（1）规划模型为：由最优单纯形表可知，最优解为最优基为（2）cj160 180 1200 00CBXBb18050 011/12 0 1/41/6160125 1011/80 1/8 11/8030 005/12 1 3/4 5/1200850 25 10（3）cj160 250 1200 00CBXBb25050 011/120 1/41/615/2160125 1011/80 1/811/820030 005/121 3/45/121000950/12 0 170/4 1070/6 由此可得最优值为，最优值是29000三、（15分）甲、乙两个企业生产同一种产品，价格、质量都相同。现需供应A、B、C、D四个地区。单位运输费用、各企业的产量、各地区的需求如下表：由于某种原因，企业乙必须满额生产。试用表上作业法求解以上便总运输费用最低的运输问题。答：由题意知，该运输问题是产销不平衡问题，添加一个虚拟销地E，销量为10，使该问题变成平衡问题。产地 销地 A B C D E产量甲 3 4 7 5 0 50乙 8 6 5 9 M 70销量20 35 25 30 10 第一步，用伏格尔法寻找得到初始基可行解地 销 地 产 A B C D E 销量甲20 20 10 50乙 35 25 10 70产量20 35 25 30 10 第二步，用位势法计算各空格处的检验数为：产地 销地 A B C D E产量 ui甲 3 2 4 6 7 5 0 500乙1 8 6 5 9 M4 M 704销量20 35 25 30 10 vj3215 0 从上表中可以看出，各非基变量的检验数均大于0，所以已求得最优解：甲A20，D20，E10；乙B35，C25，D10四、（25分）某企业根据市场需求预测今后3个月月底的交货任务分别是2千件、3千件、3千件。该厂的生产能力为每月6千件，该厂仓库的存货能力为3千件，每生产1千件产品的费用为1千元。在进行生产的月份，工厂要固定支出3千元开工费。仓库保管费用为每1千件0.5千元。假定开始时和计划期末库存量都是零。试问应在各个月生产多少件产品，才能既满足交货任务又使总费用最少?答：用动态规划方法来求解。按3个月将问题分为3个阶段。令为状态变量，它表示第k阶段开始时的库存量，；为决策变量，它表示第k阶段的生产量。表示第k阶段生产产品时的成本费用；表示在第k阶段有库存量时所需的存储费用，。故第k月内的总成本为最优值函数表示从第k阶段初库存量为到第n阶段末库存量为0时的最小总费用。则基本方程为：（1）当k3时，由于第3月末的库存量为0，第3阶段的生产量必为，计算结果见下表所示：0 123 0 6631 5 522 4 4130 00（2）当k2时，01234560 66 7.55 94 10.5 10.561 566.55848.5 8.552 465.55 74 8.5 8.54364.55 647.5 60（3）当k1时，s10，0123450 510.5 6.58.588.5 9.56153再按计算的顺序反推算，可找出每个月的最优生产决策为：其相应的最小成本为15千元。五、（20分）考虑一种由4种不同部件A1，A2，A3，A4组成的系统，各部件都运行时系统才能运行。系统的可靠性可以通过在一个或几个部件中并联若干个单元而得到提高。并联n个单元后部件的可靠性（概率）R和费用C（单位为千元）见下表：现有资金15于元。在4个部件中各并联多少个单元才使系统运行的可靠性最高?答：将问题按照4种不同部件分为4个阶段：决策变量：分配给第k种部件的个数，为对应所需的费用，相应的可靠性概率为；状态变量：在阶段k到第4阶段剩余的费用；则表示分配给第K1种至第4种部件所剩余的费用；递推关系：当k4时：3 0.815 0.82 2当k3时：160.90.80.720.72180.90.820.738 0.738 1当k2时：1280.60.720.4320.432 1100.60.7380.4428 0.80.720.576 0.576 2110.60.7380.4428 0.80.720.576 0.576 2当k1时：123150.70.5760.40320.750.5760.4320.850.4320.36720.432 2最优解为；可靠性为0.432六、（25分）高速公路某出口只有一个收费通道，假设到达该出口的汽车流为泊松流，平均每小时为30辆，收费员的服务时问服从负指数分布，平均每小时可服务40辆汽车。（1）计算这个排队系统的数量指标Po、Lq、Ls、Wq、Ws。（2）考虑到车主的抱怨，该出口考虑在该出口多安排一外员工，这样，每小时可服务50辆汽车，计算这个排队系统的数量指标Po、Lq、Ls、Wq、Ws。（3）另外，该出口也可考虑多安排一个收费通道，每个收费通道的服务率仍为40辆汽车。（4）请对（2）（3）这两个方案进行评价。答：（1）（2）（3）此为M/M/2排队模型。（4）综合比较（2）（3）方案，（3）方案的等待时间要更为短，各项系统指标更好，系统的效率更高，有显著优越性。七、（20分）某航空公司售票处开展电话订票业务。据统计分析，电话到达过程服从泊松分布，平均到达率为每小时20个，平均每个业务员每小时可以处理10个电话订票业务。请问该公司应该安装多少台电话，才能使因电话占线而损失的概率小于10%。答：此题目为M/M/S/S排队模型：假设公司应该安装c台电话，故：【注：此题目为M/M/S/S排队模型，有些超纲。】2006年北京理工大学458运筹学考研真题2006年北京理工大学458运筹学考研真题及详解北京理工大学2006年攻读硕士学位研究生入学考试试题科目代码：458 科目名称：运筹学一、（20分）考虑下列线性规划问题：（1）不通过计算，直接讨论此问题是否存在最优解：（2）用较简单的方法求出此问题的最优解及最优值，并解释为什么说这是较简单的方法。答：（1）存在最优解。（2）因为是只有两个变量，所以用图解法较为简单。最优解是，最优值为f110。二、（25分）考虑下列线性规划：最优单纯形表为：（1）计算此线性规划原问题的各参数；（2）写出此线性规划的最优解、最优基B、它的逆B1和影子价格；（3）试求c2在什么范围内，此线性规划的最优解不变；（4）若b1变为45，最优解及最优值是什么?答：（1）由最优单纯形表可知，为所加的松弛变量，。由可得，；由此解得。同理，可解出：，。（2）该规划问题的最优解为：，最优基为：，影子价格是（3）这时最优单纯形表变为下表所示：cj3 8 c213000CBXBb X1X2X3X4X5X68 c2X220 0111/703/73X15 1032/701/70X55 0032/711/7cjzj004 c22/71/7 c2027/71/7 c2若要保证最优解不变，则有：故c2可以在6，之间变化，而不影响最优解。（4），故最优解为：。最优值是1035/7。三、（15分）甲、乙、丙三个企业生产同一种产品，价格、质量都相同。现需供应A、B、C、D四个地区。单位运输费用、各企业的产量、各地区的需求如下表：由于某种原因，企业甲必须满额生产。试用表上作业法求解以上使总运输费用最低的运输问题。答：此题为运输不平衡问题，故添加一个销地E，这样可以写出这个问题的产销平衡表产地 销地 ABCDE产量甲 7 9 8 11 M 30乙 10 8 9 12 0 70丙 14 13 10 15 0 60销量45 30 35 40 10 第一步，用伏格尔法寻找得到初始基可行解A B C D E 销量地 销 地 产 甲30 30乙15 30 15 10 70丙 35 25 60产量45 30 35 40 10 第二步，用位势法计算各空格处的检验数为：产地 销地 ABCDE产量 ui甲 7 4 9 4 8 2 11 M3 M 300乙 10 8 2 9 12 0 703丙1 14 2 13 10 15 30 606销量4530354010 vj75493 第三步，由于，检验数中有个负数，所以需要对上述解进行改进，改进的解为下表：地 销 地A B C D E 销量 产 甲30 30乙15 30 25 70丙 35 15 10 60产量45 30 35 40 10 第四步，对上述改进的解用位势法计算各空格处的检验数：产地 销地 ABCDE产量 ui甲 7 4 9 4 8 2 11 M6 M 300乙 10 8 2 9 12 30 703丙1 14 2 13 10 15 0 606销量4530354010 vj75496 从上表中可以看出，各非基变量的检验数均大于0，所以已求得最优解：甲A30，乙A15，B30，D25，丙C35，D15，E10。四、（23分）某公司拟在甲、乙、丙三个地区设置5个销售点，各地区设置销售点数目的盈利情况如下表，问这应如何设置这5个销售点，使公司利润最大?答：将问题按地区分为三个阶段，甲、乙、丙三个地区分别编号为1，2，3。设表示为分配给第K个地区到第n个地区的销售点数目。表示为分配给第K个地区的销售点数目。则为分配给第K1个地区至第n个地区的销售点数目。表示为个销售点分配给第K个地区所得的盈利值。表示为个销售地分配给第K个地区到第n个地区时所得到的最大盈利值。因而可写出逆推关系式为：下面从最后一阶段开始向前逆推计算：第三阶段：设将个销售点（）全部分配给地区丙时，则最大盈利值为：，其中，因为此时只有一个地区，有多少个销售点就全部分配给地区丙，故它的盈利值就是该段的最大盈利值。其数值计算如下表所示。0 1 2 3 4 500 001 4 412 4 423 11 1134 12 1245 12 125其中表示使为最大值时的最优决策。第二阶段：设把个销售地（）分配给地区乙和地区丙时，则对每个值，有一种最优分配方案，使最大盈利值为：因为给乙地区个销售点，其盈利值为，余下的个销售点就给丙地区，则它的盈利最大值为。现在要选择的值，使取最大值。其数值计算如下表：01234500 0010450 5120454 100 102301154 104 110 1424012511 104 114110 1615012512 1011 114114 11212第一阶段：设把 个销售地（这里只有的情况）分配给地区甲、乙和地区丙时，则最大盈利值为：因为给甲地区个销售点，其盈利值为，余下的个销售点就给乙和丙地区，则它的盈利最大值为。现在要选择的值，使取最大值，它就是所求的总盈利最大值，其数值计算如下表：0123455021316 714 910125 13210，2然后按计算表格的顺序反推算，可知最优分配方案有两个：（1）由于即得甲地区分配0个，乙地区分配2个，丙地区分配3个销售点，可使盈利值最大。（2）由于即得甲地区分配2个，乙地区分配2个，丙地区分配1个销售点，可使盈利值最大。两个分配方案所得到的总盈利值均为21。五、（22分）某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概率为0.4，每次试制一批的装配费为200元，每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制，每次生产多少件，才能使得期望费用最小？解：把三次试制当作三个阶段（k1，2，3），决策变量xk表示第k次生产的产品的件数；状态变量sk表示第k次试制前是否已经生产出合格品，如果有合格品，则sk0；如果没有合格品，记sk1。最优函数表示从状态sk、决策xk出发的第k阶段以后的最小期望费用。故有。生产出一件合格品的概率为0.4，所以生产xk件产品都不合格的概率为，至少有一件合格品的概率为，故有状态转移方程为：其中k1，2，3用表示第k阶段的费用，第k阶段的费用包括制造成本和装配费用，故有根据状态转移方程以及C（xk），可得到：如果3个月后没有试制出一件合格品，则要承担2000元的罚金，因此有。当k3时，计算如下表：C（x3）20 f3（s3）x3*0 1 2345600 00120 15 11.2 9.32 8.59 8.56 8.93 8.565当k2时，计算如下表：C（x2）8.56 f2（s2）x2*01234000018.56 8.14 7.08 6.85 7.11 6.853当k1时，有：C（x1）6.85 f1（s1）x1*0123000016.85 7.11 6.46 6.48 6.462上面三个表中并没有列出xk取更大数值的情况，因为可以证明以后的的值是对单调增加的。因此得到的最优策略是，在第1个阶段试制2件产品；如果都不合格，在第2阶段试制3件产品；如果仍都不合格，则在第3个阶段试制5件产品。该策略得到的最小的期望费用6.46。六、（20分）某单服务台的服务系统，顾客按平均每小时40人的泊松流到达，服务时间服从指数分布，平均每小时服务率为。已知顾客因排队耽误造成的损失为每小时每人平均50元，服务系统每小时的费用为20元。假设这是某公司内部的一个服务系统，试确定使公司总支出最少的服务率。并依据求出的最优服务率，计算此服务系统的空闲概率，平均系统队长和平均系统逗留时间三项数量指标。答：由题意可知，该模型是M/M/1，40；，故最优服务率为50；，空闲概率为1/5。平均系统队长为：；平均系统逗留时间为：。七、（25分）某两个服务台的排队系统，最多容纳4名顾客。已知系统的稳态概率为：试求：（1）系统中的平均顾客数Ls；（2）系统中的平均排队顾客数Lq；（3）某一时刻正在被服务的顾客平均数；（4）若顾客的平均到达率为每小时2人，求顾客在系统中的平均逗留时间Ws；（5）若2名服务员具有相同的服务率，利用前面得出的结果，求服务员为一名顾客服务的平均时间（1/）。答：（1）该系统可看成是一个M/M/2/4排队系统，其中，；由。可求出系统中的平均顾客数为2人。（2）。则系统中的平均排队顾客数为。（3）某一时刻正在被服务的顾客平均数为：（人）。（4）由题意可知，；系统的实际到达率。由公式可得 。则顾客在系统中的平均逗留时间为64分钟。（5）由于，且2名服务员具有相同的服务率。；则服务员为一名顾客服务的平均时间52分钟。2005年北京理工大学458运筹学考研真题2005年北京理工大学458运筹学考研真题及详解北京理工大学2005年攻读硕士学位研究生入学考试试题科目代码：458科目名称：运筹学一、（20分）考虑下列线性规划问题：（1）求解此问题；（2）写出此问题的对偶规划及其最优解。答：（1）将原问题添加松弛变量，人工变量，改为标准形式为：用大M法进行计算，列出单纯形表，见下表：cj1430 0 MCBXBb015 1221 0 015/2020 2150 1 020M10 1110 0 1101 M 4 M 3 M 0 0 0 cj14 300 MCBXBb415/2 1/21 11/20 015025/2 3/20 41/21 025/3M5/2 1/20 01/20 151/2M1 0 1 1/2M2 0 0 cj1 4 300 MCBXBb45 0 1 110 1 05 0 0 411 3 15 1 0 01 0 2 0 0 1 3 0 2M 此时所有的非基变量的检验数均小于0，得到最优解，为，最优值为25。（2）对偶规划为：由（1）已解出原问题的最优解，可得，最优值为25。二、（25分）考虑下列线性规划：x4，X5分别为第1、2个约束的松弛变量，则最优单纯形表为：填写出此线性规划最优单纯形表中空格处的数值，并求：（1）写出此线性规划的最优解、最优值、最优基B和它的逆B1；（2）求此线性规划的影子价格?（3）试求c2在什么范围内，此线性规划的最优解不变；答：（1）最优解为，最优值则为20；最优基为，。（2）影子价格为。（3）设，此时最优单纯形表变为：cj310 0CBXBb05 2011 2 5 1110 1 00 若要使最优解不变，则只需：故可以在之间变化，而不影响最优解。三、（15分）用表上作业法求解以下运输问题：答：此运输问题是不平衡，添加一个虚拟销地D，则这个问题的产销平衡表为：地 产 地 销 A B C D 产量甲3 6 5 0 60乙8 5 7 0 30丙4 9 8 0 30产量38 45 29 8 第一步，用伏格尔法寻找得到初始基可行解：地 A B C D 产量产 地 销 甲8 23 29 60乙 22 8 30丙30 30产量38 45 29 8 第二步，用位势法计算各空格处的检验数为：产地 销地 A B C D产量 ui甲 3 6 5 1 0 600乙6 8 5 3 7 0 301丙 4 2 9 2 8 2 0 301销量38 45 29 8 vj3651 第三步，由于，检验数中有两个负数，所以需要对上述解进行改进，选取最小的2为换入变量，改进的解为下表：地 产 地 销A B C D 产量 甲16 15 29 60乙 30 30丙22 8 30产量38 45 29 8 第四步，对上述改进的解用位势法计算各空格处的检验数：产地 销地 A B C D产量 ui甲 3 6 5 1 0 600乙6 8 5 3 7 2 0 301丙 4 2 9 2 8 0 301销量38 45 29 8 vj3651 从上表中可以看出，各非基变量的检验数均大于0，所以已求得最优解：甲A 16，B 15，C 29乙B 30丙A 22四、（20分）有一种设备最长使用3年时间，现考虑它在3年内的更新问题。在每年年初要作出决策，是继续使用还是更新。如果继续使用，已知每年需要支付的维修费用如下表所示（单位：百元）：如果更新设备，已知在各年年初购置该种设备的价格如下表所示（残值忽略不，计）（单位：百元）：己知开始时该设备已经使用了1年，问每年年初应怎样作出决策，才能使3年内该项设备的购置和维修总费用最少?（用动态规划方法求解）答：建立动态规划模型，n3设：在第k年设备已使用过t年，再使用一年的维修费用；：在第k年卖掉一台已使用过t年的设备，买进一台新设备的更新费用。阶段k（k1，2，3）表示计划使用该设备的年限数。状态变量：第k年初，设备已使用过的年数；状态变量：是第k年初更新，还是保留使用旧设备，分别用R与K表示。状态转移方程为：阶段指标为：最优指标函数表示第k年初，使用一台已使用了年的设备，到第n年末的最大收益，则可得如下的逆序动态规划方程：实际上：当k3时：状态变量可取1，2，3。当k2时：能取1，2。当k1时：由于年初已经使用了一年，故 取1；所以上述计算递推回去，当时，由状态转移方程：知，得；则 推出；所以最少费用为1900元。五、（25分）某厂有100台设备，可用于加工甲、乙两种产品。根据以往经验，、这些设备都用于加工甲产品时，每季度末损坏1/3台：而都用于加工乙产品时，每季度末损坏1/10台，损坏的设备当年不能修复。每台机器一季度用于加工甲产品可获利10百元：加工乙产品可获利7百元。问如何安排各季度加工甲、乙产品的设备台数，才能使全年获利最大?（用动态规划方法求解）答：设阶段序数k表示季度，k1，2，3，4。状态变量：第k季度初，拥有的完好的设备台数；状态变量：第k季度中用于加工甲产品的设备台数，则为该季度中用于生产乙产品的设备台数。状态转移方程为：。设为第k年度的获利，则：。令最优值函数表示由设备数出发，从第k个季度开始到第4个季度结束时所生产的产品的最大获益值。因而有逆推关系式：从第4季度开始，向前逆推计算。当k4时：因是的线性单调增函数，故得最大解，相应的有当k3时：此时有。当k2时：此时当k1时：此时。已知，于是可得：第一季度，用于生产甲产品的设备数目是0台，100台全部用于生产乙产品；第二季度，用于生产甲产品的设备数目是0台，用于生产乙产品的设备数目是90台；第三季度，用于生产甲产品的设备数目是81台，用于生产乙产品的设备数目是0台；第四季度，用于生产甲产品的设备数目是54台，用于生产乙产品的设备数目是0台。这样所得的利润是最高，其最高利润为2680。六、（20分）一个小型的平价自选市场只有一个收款出口，假设到达收款出口的顾客流为泊松流，平均每小时为30人。收款员的服务时间服从负指数分布，平均每小时可服务40人。（1）计算这个排队系统的数量指标Po，Lq，Ls，Wq，Ws；（2）顾客对这个排队系统抱怨化费时间太多。商店为了改进服务，准备对以下两方案进行选择：a在收款出口除了收款员外，专顾一名包装员。这样可以使每小时的服务率从40人提高到60人。b增加一个收款出口，使排队系统变成M/M/2系统，每个收款出口每小时的服务率仍为40人。请对这两个排队系统进行评价，并作出选择。答：（1）；（2）对于a）方案中，对于b方案中，a与b方案相比较，b的等待时间较为短，故比较好。七、（25分）某机场有一条专供飞机降落的跑道。假定飞机降落占用跑道的平均时间为2分钟（这里“占用”指不准其他飞机使用）。设飞机在空中的平均耽误时间（Wq）不得超过10分钟，飞机的到达为泊松分布。（1）如果飞机占用跑道时间服从负指数分布，机场的最大允许载荷量（以每小时能到达的飞机平均数表示）是多少?（2）如果飞机占用跑道时间服从任意独立分布，并已知一架飞机占用跑道的标准差为1分钟，那么机场的最大允许载荷量是多少?（3）如果飞机占用跑道时间服从负指数分布，并另外规定：要求一架飞机从到达到降落时间大于20分钟的概率小于0.05，这时机场的最大允许载荷量是多少?（计算过程中如有对数，不必求出，结果可用含对数的式子表示）答：（1）由题意知：。此排队系统模型为 M/M/1排队模型：则机场的最大允许载荷量（以每小时能到达的飞机平均数表示）是25架。（2）由题意知：，标准差。此排队系统模型为 M/G/1排队模型，且。故此时机场的最大允许载荷量是26.67架。（3）由题意知：。此排队系统模型为 M/M/1排队模型，由于要满足，则由于，则：求解可得：。因为，则。即这时机场的最大允许载荷量是架。2004年北京理工大学458运筹学考研真题2004年北京理工大学458运筹学考研真题及详解北京理工大学2004年攻读硕士学位研究生入学考试试题科目代码：458 科目分号：0802 科目名称：运筹学一、（25分）求解下列线性规划问题。答：将上述规划问题转化为标准形式，为：用大M法列单纯形表求解，得：502100M MM2 11 61 0101/3M1 11201 011/22M5 08M21 M M 00 502100MM211/3 1/61/611/601/60 M1/3 2/34/301/31 1/311/42/3M3/24/3M7/201/3M7/2M4/3M7/20 5 0 21 00MM213/8 1/40 11/8 1/8 1/81/83/201/4 1/2 1 01/43/4 1/43/41/21/40 021/8 21/8 M21/8 M21/8 5 021 00MM211/4 01/2 11/4 1/41/41/4 51/2 1201/23/2 1/23/2 01/2 011/4 9/4 M11/4 M9/4 此时表中非基变量的检验数均不为正数，故达到最优解，。二、（25分）某公司制造三种产品A、B、C，需要两种资源（劳动力和原材料），这些产品对两种资源的需求、单位利润以及该公司的资源限制如下表所示，要求确定总利润最大的最优生产计划。设x1，X2，x3分别是产品A、B、C的产量，我们可得到该问题的线性规划模型如下：其中，x1，x2，x3是产品A、B、C的产量。这个线性规划问题的最终单纯形表如下：（1）求出使得最优解不变的产品A的单位利润变动范围。问C12时最优解变不变?（2）从上表中判断该规划最优解是否唯一，并说明理由（3）求出使原材料对偶价格不变的b2的变化范围。（4）由于技术上的突破，每单位产品B对原材料的需要量减少为2个单位，这时是否需要改变生产计划?为什么?答：（1）假设，把它代入最优单纯形表中，得：15 005 1053 01100若要使最优解不变，则：所以当c1在3，6之间变化时，最优解不会变化。故当C12时最优解发生变化。（2）不是唯一的，因为非基变量存在一个检验数为0，所以该规划问题有无穷多最优解。（3）将其反映到最优单纯形表中，列的数值为：当时问题的最优基不会变化，解得：（4）由题意知，变为变化后的单纯形表为：3 15 0035 1053 010