北京交通大学交通运输学院《942管理运筹学》历年考研真题汇编（含部分答案）.pdf

目录2015年北京交通大学交通运输学院942管理运筹学考研真题2014年北京交通大学交通运输学院942管理运筹学考研真题2013年北京交通大学交通运输学院942管理运筹学考研真题2012年北京交通大学交通运输学院942管理运筹学考研真题2011年北京交通大学交通运输学院942管理运筹学考研真题2010年北京交通大学交通运输学院942管理运筹学考研真题2010年北京交通大学交通运输学院942管理运筹学考研真题及详解2009年北京交通大学交通运输学院942管理运筹学考研真题2009年北京交通大学交通运输学院942管理运筹学考研真题及详解2008年北京交通大学交通运输学院942管理运筹学考研真题2008年北京交通大学交通运输学院942管理运筹学考研真题（含部分答案）2007年北京交通大学交通运输学院417管理运筹学考研真题2007年北京交通大学交通运输学院417管理运筹学考研真题及详解2006年北京交通大学交通运输学院417管理运筹学考研真题2006年北京交通大学交通运输学院417管理运筹学考研真题及详解2005年北京交通大学交通运输学院417管理运筹学考研真题2005年北京交通大学交通运输学院417管理运筹学考研真题及详解2004年北京交通大学交通运输学院管理运筹学考研真题2004年北京交通大学交通运输学院管理运筹学考研真题及详解2003年北方交通大学交通运输学院管理运筹学考研真题2003年北方交通大学交通运输学院管理运筹学考研真题及详解2002年北方交通大学交通运输学院管理运筹学考研真题2002年北方交通大学交通运输学院管理运筹学考研真题及详解2001年北方交通大学交通运输学院管理运筹学考研真题2001年北方交通大学交通运输学院管理运筹学考研真题及详解2000年北方交通大学交通运输学院管理运筹学考研真题2015年北京交通大学交通运输学院942管理运筹学考研真题2014年北京交通大学交通运输学院942管理运筹学考研真题2013年北京交通大学交通运输学院942管理运筹学考研真题2012年北京交通大学交通运输学院942管理运筹学考研真题2011年北京交通大学交通运输学院942管理运筹学考研真题2010年北京交通大学交通运输学院942管理运筹学考研真题2010年北京交通大学交通运输学院942管理运筹学考研真题及详解北京交通大学2010年硕士研究生入学考试科目代码：942 科目名称：管理运筹学一、判断（正确的打“”，错误的打“”）1线性规划问题的每一个基解对应可行域的一个顶点；（北京交通大学2010年研）【答案】【解析】基解不一定是可行解，基可行解对应着可行域的顶点。2若、分别是某一线性规划问题的最优解，则也是该线性规划问题的最优解，其中、为正的实数；（北京交通大学2010年研）【答案】【解析】必须规定，当一线性规划问题存在两个最优解时，则它一定存在无数个最优解，3已知为线性规划问题的对偶问题的最优解，若，则说明在最优生产计划中第 种资源已经完全耗尽；（北京交通大学2010年研）【答案】【解析】对偶问题互补松弛性质中；当时，有，表明在最优生产计划中第 种资源已经完全耗尽。4整数规划问题最优解的目标函数值一定优于其相应线性规划问题最优解的目标函数值；（北京交通大学2010年研）【答案】【解析】因为附加了整数条件，其可行域比其相应线性规划问题的可行域减小，故整数规划问题最优解的目标函数值一定不优于其相应线性规划问题最优解的目标函数值。5指派问题效率矩阵的每个元素乘以同一大于0的常数，将不影响最优指派方案；（北京交通大学2010年研）【答案】【解析】效率矩阵每个元素乘以同一大于0的常数，即目标函数的系数同时增大k倍，不会影响最优基的变化，故不影响最优指派方案。6如果图T是树，则T中一定存在两个顶点，它们之间存在两条不同的链；（北京交通大学2010年研）【答案】【解析】连通且不含圈的无向图称为树。因此任意两点间必定只有一条链。7任一图都存在支撑子图和支撑树；（北京交通大学2010年研）【答案】【解析】当图中存在一个顶点，其次为0时，则该图不存在支撑树。8网络图中任何一个结点都表示前一工序的结束和后一工序的开始；（北京交通大学2010年研）【答案】【解析】网络图的起始点只表示一工序的开始，结束点只表示一工序的结束。9结点最早时间同最迟时间相等的点连接的线路就是关键路线；（北京交通大学2010年研）【答案】【解析】关键路线是指总时差为零的工作链，而该工作链是由一系列最早时间同最迟时间相等的点连接而成的。10假如到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布；（北京交通大学2010年研）【答案】【解析】设N（t）为时间0，t内到达系统的顾客数，则为参数为 的普阿松流的充要条件是：相继到达时间间隔服从相互独立的参数为 的负指数分布。11运输问题是一种特殊的线性规划模型，因而其求解结果也可能出现四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解；（北京交通大学2010年研）【答案】【解析】运输问题是一种特殊的线性规划模型，它总存在可行解，或是存在唯一最优解，或是有无穷最优解。12单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数值得到最快的增长。【答案】【解析】选择任何一个大于零的都可以，由上式可以看出，将最大正检验数对应的变量作为换入变量，将使目标函数值得到最快的增长。二、简答1试简述求解整数规划模型的分枝定界法剪枝的几种情况；（北京交通大学2010年研）答：（1）某枝已经达到其范围内的最优解；（2）某枝域内没有可行解时，即是不可行域；（3）某枝所得数据不优于当前最优解时。2试写出标准指派问题的线性规划问题；（北京交通大学2010年研）答：设，则得线性规划模型3试写出求解最短径路的Dijkstra算法的步骤；（北京交通大学2010年研）答：步骤：（1）给（2）若vi点为刚得到P标号的点，考虑这样的点vj，（vi，vj）属于E，且vj为T标号。对vj的T标号进行如下修改：（3）比较所有具有T标号的点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号时停止。否则用代 转回（2）。4试写出M/M/1排队系统的Little公式；（北京交通大学2010年研）答：三、（40分）某厂生产、三种产品，其所需劳动力、原材料等有关数据如下：每件产品分别需要劳动力和原材料6个小时和3公斤，每件产品分别需要劳动力和原材料为3小时和4公斤，每件产品分别需要劳动力和原材料为5小时和5公斤；拥有的劳动力和原材料总数分别为45小时和30公斤；又知、三种产品的单件利润分别为3、1、4元。（北京交通大学2010年研）要求：1写出该厂获得最大的生产计划问题的线性规划模型并求出最优解；答：设三种产品的产量分别为x1、x2、x3，则得模型：将上述问题改写为标准形式为：用单纯形法计算如下：cj31400CBXBbx1x2x3x4x50 x445 635100 x530 345 01314000 x415 3 10114x36 3/5 4/5101/53/5 11/5 004/53x15 11/3 01/31/34x33 0111/5 2/50201/5 3/5得到最优解，即生产、各5和3件。2写出该线性规划问题的对偶问题，并求对偶问题的最优解；答：对偶问题：由及上述最终单纯形表可知，。3产品的利润在什么范围内变化时，上述最优计划不变？答：保持最优计划不变，即保持各非基变量检验数非正，则解得。4如果设计一种新产品，单件产品消耗劳动力8小时，原材料2公斤，每件可获利3元，问该产品是否值得生产？答：新产品的产量为x6，则相对约束矩阵多一列向量，在最终单纯形表中为，其检验数为，故值得生产。5如果劳动力数量不变，原材料可以从市场购买，每公斤0.4元，问该厂是否购买原材料来扩大生产，以购买多少为宜？答：设购买，则，故可以购买原材料来扩大生产。由两式得，即购买15公斤时可获得最大效益。四、（16分）某公司有甲，乙，丙三个工厂和A，B，C三个客户，这三个工厂在下一时期将分别生产某种产品300，500和400件，公司计划卖给客户A，B，C的产品数量分别为400，300，100件，客户D想尽可能多地购买剩下的商品。工厂卖给各客户单位产品的利润如下表。问如何安排供应使该公司总利润最大。答：该问题属于平衡运输问题，客户D将购买300500400（400300100）400（件）商品。则由沃格尔法得初始方案，并用位势法得各空格检验数所示：ABCD供给量 行差甲2 15 3 13 1 12 30014 3001 1 1乙20018 30017 115 3 12 5001 2 丙20013 2 10 1009 10010 4003 2 2需求量 400300100400 列差3432 3 32 2 34 空格乙C检验数为正，故调整其所在回路，调整值为min200，100100并检验得：ABCD供给量甲2 15 3 13 2 12 30014 300乙10018 30017 10015 3 12 500丙30013 2 10 1 910010 400需求量 400300100400 所有检验数均小于零，即得最优方案如下：ABCD供给量甲 300 300乙100 300 100 500丙300 100 400需求量 400 300 100 400 1200五、（20分）用动态规划方法求解下列整数规划问题：（北京交通大学2010年研）答：将该过程分为3个阶段，决策变量为，状态变量为，表示第k阶段开始时候的状态（k1，2，3），其中，最优指标函数，表示第k阶段状态为时，第k阶段至第3阶段的最优值，且，表示每个阶段的指标函数。采用逆推法。k3时，k2时，k1时，。所以得x1*1，x2*2，x3*0，maxZ18。六、（14分）某理发店只有一个理发员，来理发的顾客到达过程为posson流，平均5人/小时；理发时间服从负指数分布，平均需要10分钟；店内备有5把椅子供顾客等候，多余顾客将到其他理发店理发。（北京交通大学2010年研）求：（1）该理发店忙的概率；（2）该店内恰有2个顾客的概率；（3）在该店内的平均顾客数；（4）每位顾客在该店内的平均逗留时间；（5）等待服务的平均顾客数；（6）每位顾客平均等待时间；（7）顾客损失的概率。答：该问题属于M/M/1/N模型，N5。（1），1P00.7494，即为理发店忙的概率。（2）。（3）。（4）。（5）。（6）顾客的平均等待时间是。（7），即顾客损失的概率。2009年北京交通大学交通运输学院942管理运筹学考研真题2009年北京交通大学交通运输学院942管理运筹学考研真题及详解北京交通大学2009年硕士研究生入学考试科目代码：942 科目名称：管理运筹学一、（50分）已知线性规划问题如下：1求该问题的最优解；答：用对偶单纯形法计算如下：ci251/200CBXBbx1x2x3x4x50 x431 21/2 100 x59013 01251/2000 x42/3 1 11/6 011/61/2 x3301/3101/32 29/6 001/60 x6961106 11/2 x362412 013010得最优解，X*（0，0，6）T，min z1/263。2写出该线性规划问题的对偶问题，并求对偶问题的最优解；答：由上最终单纯形表可得，max w33分别确定x2、x3的目标函数系数c2、c3在什么范围内变化，最优解不变？答：（1）c2变化，最优解不变，要保证，解得，即。（2）c3变化，最优解不变，要保证，解得，即。4求约束条件右端值由变为时的最优解；答：代入最终单纯形表中，因此不是最优解。ci251/2 000 x63 61106 11/2 x3424120130100 x41/2 1 11/6 011/61/2 x3401/3101/3029/6001/6得新的最优解是X*0，0，4T，min z1/242。5求增加新的约束条件x12x2x35时的最优解。答：加入松弛变量x6得下表cj251/20 00CBXBbx1x2x3x4x5x60 x43121/2 1 000 x59013 0 100 x651210 01251/20 000 x42/3 111/6 01 1/601/2 x3301/310 1/300 x6215/3 00 1/3 1229/600 1/600 x41/31/2 101 01/21/2 x351210 010 x563500 133/2400 01/2得最优解X*0，0，5T，minz1/255/2。二、（25分）某铁路企业承担A、B、C三个城市之间的城际旅客列车运输任务，列车的出发和到达时间如下表所示：设旅客列车从到达某站到出发至少需要2个小时的准备时间，试制定一个最佳的旅客列车车底接续方案，使该铁路企业所使用的车底数量最少。答：题中，将达到某城市的列车当成是要完成工作的工作人员，而在该城市出发当成是要完成的工作，则3座城市的列车工作效率如下所示，数据是执行任务需等待时间。A城市：到达 出发 T101 T103 T105 T107 T109T1022381315T10419202568T10615162124T10822234911T110141520253B城市到达 出发 T102 T104 T106T10116233T10315222T105101721C城市到达 出发 T108 T110T107715T109513则对于A城市，利用匈牙利算法指派任务如下：初次指派为：，的个数少于54，故进行划线覆盖所有的零元素；继续求解，依然不符合，故继续划线覆盖所有零元素，并最终求得最优解，即A城市中到达 出发 T101 T103 T105 T107 T109T102 3 T10419 T106 2 T108 4 T110 3所需车底数是3；同理得B城市的指派为，所需车底数为2；C城市指派为，需要车底数为2。综上，该企业总的车底数最少需要是7个。三、（20分）已知运输问题的运价及产销平衡表如下：要求：1用最小元素法求该运输问题的初始解，并进一步求出最优解；2.A3B3的单位运价C33变为什么值时，有无穷多最优解？并进一步给出两个新的最优方案。答：（1）该运输问题的初始解是：B1B2B3B4产量A1 10 10A23 10 12 25A33 2 5销量 6 10 12 12 利用位势法计算个空格的检验数为：产量B1B2B3B4A11 0 101 10A23102 12 25A3313 27 5销量 6101212 空格A2B2检验数小于0，故调整其所在回路，调整量为min（2，3）2，得新方案，并检验之，如表中所示：B1B2B3B4产量A11 2 10 1 10A211021225A3513 2 75销量 61012 12 仍不是最优方案，故继续调整，最后得最终方案如下：B1B2B3B4产量A1 10 10A21 0 12 12 25A35 5销量 6 10 12 12 （2）A3B3的检验数为C33121060时，即C338时，有无穷多最优解。新方案一：B1B2B3B4产量A1 10 10A21.5 11.5 12 254.5 0.5 5A3销量 610 1212 新方案二：B1B2B3B4产量A1 10 10A22 11 12 25A34 1 5销量 6 10 12 12 四、（21分）某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如下表所示。已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优生产计划。（北京交通大学2009年研）答：采用动态规划方法求解。设每个月生产xk件产品，xk小于等于6；sk为每个月开始的存货量，则s10，s50，表示在k月初存货量是sk是从第k个月开始至第4个月的最优指标函数。表示第k个月生产xk个产品时所需要的生产费用，表示第k个月生产xk个产品时，剩余产品所需要的存储费用，（1）k4时，（2）k3时，（3）k2时，（4）k1时，为最优生产计划。五、（20分）在下图中，分别求v1至v6，v1至v4，v6至v2和v2至v5的最短路和最短距离。（北京交通大学2009年研）答：用Floyd方法求解：令网络的权矩阵为k0，由表示从vi到vj点或直接有边或借v1点为中间点是的最短路长，括弧中元素为更新元素，得D（1）k1，；表示从vi到vj点最多经v1，v2的最短路长，得D（2）k2，依次类推，k3，；k4，；k5，；k6，。v1至v6的最短路是v1v3v5v6，最短距离是1。v1至v4的最短路是v1v3v5v4，最短距离是0。v6至v2的最短路是v6v4v2，最短距离是3。v2至v5的最短路是v2v3v5，最短距离1。六、（14分）某汽车加油站只有一个加油设备，汽车到达加油站的过程服从泊松分布，汽车平均到达时间间隔为5分钟，加油站平均1个小时能加24辆车。试求：（1）加油站的空闲的概率；（2）加油站有三辆车的概率；（3）加油站有两辆车以上的概率；（4）加油站内的平均车辆数；（5）车辆在加油站内的平均逗留时间；（6）加油站内的平均等待车数；（7）车辆的平均等待时间。答：属于M/M/1/模型，。（1）加油站的空闲的概率。（2）加油站有三辆车的概率。（3）加油站有两辆车以上的概率。（4）加油站内的平均车辆数即（辆）。（5）车辆在加油站内的平均逗留时间。（6）加油站内的平均等待车数即（辆）。（7）车辆的平均等待时间。2008年北京交通大学交通运输学院942管理运筹学考研真题2008年北京交通大学交通运输学院942管理运筹学考研真题（含部分答案）北京交通大学2008年硕士研究生入学考试试卷考试科目：942管理运筹学注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！一、（35分）已知线性规划问题：max Z3x14x2x3（1）求线性规划问题的最优解：（2）求对偶问题的最优解：（3）求b1的灵敏度范围；（4）求c2的灵敏度范围；如果右端值10，16变为12，10求新问题的最优解。答：（1）由题意，用单纯形法计算。Cj34100 iCBXBb010 12 1105016 22101834100 CjZj45 1/2 11/2 1/2 01006 1 001 16CjZj101 2 0 42 011/2 11/2 36 1001 1 CjZj001 1 1 此时，所有检验数为负，已得最优解XT（6，2，0），目标函数值为Z26。（2）对偶问题Min w10y116y2st y1 2y23 2y1 2y24 y1 y21 y1，y20由互补松弛条件YXs0，XYs0；由X（6，2，0），得Y1s0 Y2s0，即为严格等式，即y1 2y23，2y1 2y24；所以y11，y21。即最优解y11，y21，min w26。（3）灵敏度分析当b1变化b时，可计算B1b B1由，所以。因此8b116。（4）记即，得，所以。（5）当右端值由10，16变为12，10时，。将其反映到最终单纯性表中，再用对偶单纯性法进行迭代，如下。Cj34 100CBXBb4701 1/2 11/232 10 01 1CjZj00 1 114511 1/2 01/2021 0 011CjZj1 0 1 02故新问题的最优解为X（0，5，0，2，0），最优值为z20。二、（20）已知LP问题为要求：（1）设其偶变量为y1，y2，y3，y4，写出其对偶问题；（2）已知原问题最优解（x1，x2，x3，x4，）（2，2，4，0），试根据对偶性质直接求出对偶问题的最优解。（北京交通大学2008年研）答：（1）对偶问题min W8y16y26y39y4st （2）由互补松弛条件YXs0，XYs0；（x1，x2，x3，x4，）（2，2，4，0），则X1sX2sX3s0，X4s0，且0，Y1sY2sY3s0所以，因此（y1，y2，y3，y4）（，1，0）。三、（20）某公司有3个工厂和3个客户，这3个工厂在下一时期将分别制造产品300，500和200件，公司答应卖给客户1，2，3的产品分别是300，200，100件，客户4想尽可能多的购买剩下产品。工厂i卖给客户j的单位产品利润如下表所示。问如何安排生产和供应才能使总利润最大？答：用18减去图中各个利润，将问题转化为运输问题，建立产销平衡表。产量356430001365005898200销量 300 200 100 400 用伏格尔法求解，（）内数据为解产地 销地产量 行差3564（300）300 1 1 2 0（300）1（200）3（0）6500 1 3 589（100）8（100）200 3 3 1 销量300200100400 列差3432 3 32 34 用位势法计算所有空格的检验数，计算结果如下图所示。12 1 0 4 21 1 423 5 4 表中有负检验数，选择（1，3）为调入格，调入量为100，得新的解 300200 200 100 100 100再用位势法检验，得检验数 2 3 2 0 3 1 2 1 41 2 4 4 此时，所有检验数都非负，故上表中的解为最优解。即安排A1生产300提供给B4，A2生产200提供给B1，A2生产200提供给B2，A3生产100提供给B3，A3生产100提供给B1，A3生产100提供给B4，故总利润为15000。四、（25）某工厂有1000台机器，拟分四个阶段使用。已知在每个阶段有两种生产任务，进行第一种生产时每台机器可收益9千元，其机器报废率0.3，而进行第二种生产时每台机器可收益6千元，其机器报废率为0.1文怎样分配机器，使收益最大？（要求写出动态规划模型的基本要素并求解）（北京交通大学2008年研）答：将此题看成一个4个阶段决策问题。令 为状态变量，它表示第k阶段初拥有的完好机器数量，决策变量为第k阶段分配给第一种生产的机器数量，于是为该阶段分配给第二种生产的机器数量。状态转移方程为，设为第k阶段的收益，则令最优值函数表示由机器数量 出发，从第k阶段开始到第4阶段结束时所获得的收益最大值，故有递推关系式：（1）k4时，因f4是u4的线性单调增函数，故得最大解，相应的。（2）k3时，故得最大解，相应的有。（3）k2时，当，相应的有。（4）k1时，当，相应的有。因s11000，所以23793千元。计算结果表明，第1阶段将1000台机器投入第二种生产，第2阶段将900台机器投入到第二种生产，第3阶段将810台机器投入到第一种生产，第4阶段将567台机器投入到第一种生产。可得最大收益为23793千元。五、（10）为解决污水河流的污染问题，某城市拟修建污水处理站。备选的站址有A、B、C三个，其投资等技术经济参数见下表：按环保部门要求，每年至少要从污水中清除8万吨污染物1和6万吨污染物2。请构造一个整数规划模型，在满足环保要求的前提下使投资和运行费用最小。（北京交通大学2008年研）答：设 表示处理的万吨数，被采用时为1，未采用时为0。建立整数规划模型min z500500 x1400800 x23001000 x3六、（20）某修理店只有一个修理工，来修理的顾客到达过程为poisson流，平均5人小时。分别计算在下列修理时间分布的情况下系统的Ls，Lq，Ws与Wq的值。（1）修理时间为常数，每次修理需10分钟；（2）修理时间为负指数分布，平均修理需10分钟；（3）修理时间为正态分布，9分钟，4。答：（1）当修理时间为常数（2）当修理时间为负指数分布（3）当修理时间为正态分布2007年北京交通大学交通运输学院417管理运筹学考研真题2007年北京交通大学交通运输学院417管理运筹学考研真题及详解北京交通大学2007年硕士研究生入学考试试卷考试科目：417管理运筹学注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！一、（20分）某工厂准备生产甲、乙、丙三种产品，它们都消耗A、B两种原材料，有关数据如下表所示：要求：构造使该厂利润最大的线性规划模型，并用单纯型法求解。答：设三种产品的产量分别为x1、x2、x3，则得以下线性规划模型：用单纯形法计算如下：cj31400CBXBb x1x2x3x4x50 x445 635100 x530 345 01314 0 x415 3 10114x36 3/5 4/5101/53/5 11/5 004/53x15 11/3 01/31/34x33 0111/5 2/50201/5 3/5得到最优解，即生产甲和丙各5和3单位。二、（40分）已知线性规划模型Max z2x1x2求：（1）写出原问题的对偶线性规划模型；（2）用对偶单纯型法求解原问题的最优解；（3）增加约束条件3x12x212，最优解会有什么变化？（4）若C1由2降至1.5，C2由1升至2，最优解会有什么变化？（5）资源b3由现在的5变成4，最优解是否发生变化。答：（1）（2）对原问题的对偶问题利用对偶单纯形法cj1524500CBYBby1y2y3y4y50y4206 1100y5152101152450024 y21/3011/61/6 00y51/3 502/3 1/3 115014024 y21/45/4 101/4 1/45y31/215/2 011/23/215/2 007/23/2得最优解，X*7/2，3/2，maxz8.5。（3）即对偶问题增加了一变量y6，其约束变量为a3，2T，目标函数变量为12，在最终单纯形表中的，因此不是最优解，继续计算如下：cj1524 50012CBYBby1y2y3y4y5y624 y21/4 5/4 1 01/4 1/41/45y31/2 15/2 0 11/23/2 3/215/2 0 07/23/23/224 y21/6 5/2 1 1/6 1/3 1/2012 y61/3 50 2/31/311150 1400得原问题最优解X*4，0，maxz8。（4）在其对偶问题中，即资源变量变化，最终单纯形表中，继继续利用对偶单纯形法计算如下：cj15245 00CBYBby1y2y3y4y524 y21/8 5/4 10 1/4 1/45y39/415/201 1/23/215/200 7/23/215 y11/10 14/5 0 1/51/55y33/2061 10060 23得原问题最优解X*（2，3）T，maxz7。（5）即对偶问题c34，y3是基变量，因此检查各非基变量的检验数，因此最优解不发生变化。三、（15分）求出下面运输问题的所有最优解。答：本题为运输平衡问题，用沃格尔法计算如下：（）内数据为解。产地 销地 B1B2B3B4产量 行差A19（6）8（2）13（5）14（5）181 1 4 1 1A2101012（24）14240 0 2 2 A38911（6）1361 1 1 2 2A4107（12）1112123 销量61435560 列差1101 1111 1 11 11 21 用位势法检验，各空格检验数内数据，存在检验数小于零的空格。产地 销地 B1B2B3B4产量A19（6）8（2）13（5）14（5）18A210210312（24）14124A3819311（6）1316A41027（12）111121 12销量61435560在相应回路调整，如空格A1B3所在回路，调整量为5，最后得新方案，并检验如下：不存在检验数小于0的空格，得最优解，A3B1检验数为0，最优解不唯一。产地 销地 B1B2B3B4产量A19（6）8（12）13114118A210110212（24）14124A3809211（6）1316A41027（2）11（5）12（5）12销量61435560由A3B1所在回路，任意变化可得所有最优解如下：产地 销地 B1B2B3B4产量A16c 12c 18A2 24 24A3c 6c 6A4 2c 5c 5 12销量614355 60C的取值范围是0，2。四、（15分）用分支定界法求整数规划问题的最优解Max zX1x2答：利用单纯形法先解相应的线性规划，得最优解如下：cj1 1 00CBXBbx1x2x3x41x13/2 1 0 7/169/321x210/3 0 1 7/87/160 0 21/16 5/32不是整数，故用分支定界法继续求解，z029/6是问题最优解z*的上界，z0是一个下界，则。将问题分成问题B1和B2问题B1问题B2z110/3 z141/9x11x12x27/3 x223/9z1z2，先将问题B2分解成B3和B4问题B3问题B4z117/6 z114/3x15/6 x15/3x22x23接着讲B4分解成问题B5和B6，问题B5问题B6z117/6 z14x12x13x223/9 x21得到一整数解z4，X3，1T，比较个z值，发现B6的解即为最优解。五、（20分）某部门拟将某种新设备5台分配给甲、乙、丙3个工厂，各工厂获得这些设备后可盈利如下表所示，这5台设备应如何分配，使其利润最大？用动态规划方法求解（要求写出状态转移方程和递推方程）。答：将该问题分成3个阶段，xk（k1，2，3，4）为决策变量即在第K阶段分给k工厂xk台设备，sk（k1，2，3，4）为第k阶段开始时候的状态变量，为最优策略的指标函数，表示第k阶段状态为sk时第k阶段至第三阶段的最优值，且，用加法方式。s15，s2s1x1，s3s2x2x3。模型为：0 x15，0 x2s2，0 x3s3其中，a（x1），b（x2），c（x3）分别表示三家工厂获得这种设备后将能为集团提供的盈利，如上表所示，采用逆推法，计算如下：k3时，即S3x3x3*0 0 001 1 412 2 623 3 1134 4 1245 5 125k2时，即x2 S20 12345x2*00 0014 5 5126 54 10 102311 56 104 11 142412 511 106 114 11 161、2512 512 1011 116 114 11 212k1时，即x1 s10 12345x1*521 316 714 910 125 13 210、2分配给各厂的设备分别为2、2、1或者0、2、3获得最大利益21。六、（20分）在下图中，分别求v1至v6，v4至v5，v6至V2的最短路和最短距离。答：用Floyd方法求解：令网络的权矩阵为，Dk表示至少经过vk时的距离，括号内数字即变动的距离。，可得v1至v6的没有通路，最短距离是。v4至v5的最短路是v4v2v3v5，最短距离是3。v6至V2的最短路是v6v4v2，最短距离1。七、排队论（20分）假设到达一个公用电话间的顾客数服从普阿松分布，有两个公用电话间同时使用。两个顾客相继到达的平均间隔时间为3分钟，通话时间服从平均数为3分钟的普阿松分布。公用电话间内最多只能容纳5人。假设到达的顾客见到电话间里已有5个人时就离开这个公用电话间去别处打电话。求：（1）一位到达的顾客只得离开这个电话间去别处打电话的概率；（2）平均队长；（3）电话局打算只要顾客在队伍中的平均等待时间不超过1分钟，就搬走一台电话。但如果因为减少一台电话会使顾客排队等待时间超过5分钟，那么电话局就会放弃原来的打算。问这个公用电话间的服务设施是否需要改变？答：（1）即去别处打电话的概率是0.3276。（2）。（3）当撤走一台电话时，此问题变成M/M/1/5排队模型。电话设施不会改变。2006年北京交通大学交通运输学院417管理运筹学考研真题2006年北京交通大学交通运输学院417管理运筹学考研真题及详解北京交通大学2006年硕士研究生入学考试试卷考试科目：417管理运筹学注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！一、（25分）设有如下的线性规划问题：（1）写出该线性规划的标准型；（10分）答：（2）求原规划的最优解和最优目标函数值。（15分）答：加入一个人工变量x7，利用单纯形法计算如下：cj1233 000 0CBXBbx1x2x3x3x4x5x7x60 x47 2111 100 00 x56 312 2 010 00 x74 4233 001 00 x64 0100000 11233 000 00 x410 1/21/20011/2 0 03x33 3/2 1/2 1 101/2 0 00 x713 1/21/20003/2 1 00 x64 0100000 111/2 1/20003/2 0 01x120 1100210 03x313 011 1320 00 x73 00001 11 00 x64 0100000 1060011 70 0 x1x120，x2x222，x3x3x313；得到最优解X*20，2，13T，minz55。二、（25分）标准型线性规划问题（minZCX，AXb，X0）的最优单纯型表为：其中：x4，x5是对应于初始单位矩阵的松弛变量。试求：（1）求该标准型线性规划目标函数的系数c1c5；答：松弛变量x4，x5的目标函数为0，且由最终单纯形表可知：解得。（2）设该标准型线性规划的右端常数项为b，b1，b2分别为b的两个分量的增量，试分别对两个增量进行灵敏度分析，即求出b1，b2分别变化时的取值范围；答：当，解得；当，解得。（3）假定用bb代替b，其中b，要使现行的最优基B*不变，求的变化范围，并求当时的最优解；答：保持最优基B*不变，则要求解得，当时，最优解不发生变化，。所以X*3，1T，minz9。（4）要使现行的最优基不变，求目标函数系数c1变化范围；答：保持最优基不变，各非基变量检验数认识非负，则：解得，。c1变化范围是3，1。（5）求两个约束的影子价格。答：由最终单纯形表可知，两个影子价格即两个松弛变量的检验数，即分别为3和1。三、（25分）某工厂安排某种生活必需品在以后四个月的生产计划。该产品可以在以后四个月的任一个月生产，不过受用工和原料价格的影响，不同的月份其生产成本不同，该产品在以后四个月的生产成本分别是12，10，15，18元，件。该产品以后四个月需要量分别是400，700，900和800件，考虑到生活必需品的要求，产品需要量必须加以满足。该工厂平常每月最多能生产700件，但在第二个月农闲时期工厂可以聘用临时工加班，加班后可增产300件，但生产成本每件增加3元。过剩产品每件存储费用是每月3元。试完成：（1）仿照运输问题建立使总成本最小的生产计划线性规划数学模型；（10分）答：设xij是第i个月生产供第j个月消费的产品数量，i1，2，2，3，4，j1，2，3，4，其中x2表示第2个月加班完成的产品数量。z表示总成本。则由题意得线性规划数学模型：（2）用运输问题表上作业法求解。（10分）答：总供给量为70043003100；总需求量是4007009008002800，故设一虚拟消费月份5，需求量是300，成本是0，其他如xij（ij），成本是。则化成产销平衡问题，利用沃格尔法得初始解如下：（括号内为分配量，内为检验数）消费月份 生产月份12345产量1（400）12 515 218 221（300）0 7002（700）10 013 016 30 7002（0）13（200）16（100）19（0）0 3003 （700）15 018 10 7004 （700）18 10 700需求量4007009008003003100所有空格检验数均为非负，故得最优解。即4个月份分别生产400件、1000件、700件和700件。（3）理论上讲该问题有几个最优基本可行解？（5分）答：因为存在检验数为0，故有无数个最优基本可行解。四、（25分）某城市公共交通公司共有公交客车1000辆，可投入超负荷和正常负荷两种状态运营，如果当年投入高负荷状态运营，年运量为20万人台，且第一年投入高负荷运营时汽车年完好率为0.8，以后各年投入高负荷运营时每年完好率随车龄每年以0.1递减，如果投入正常负荷状态运营，年运量为15万人台，第一年汽车年完好率为0.95，以后各年投入正常负荷运营时每年完好率随车龄以OO5递减，试安排5年运量最大的运营方案。答：设第k年有xk（k1，2，3，4，5）辆车超负荷状运