管理运筹学西南交通大学

1、西南交通大学2014年全日制硕士研究生入学试题解析试题名称：管理运筹学二一、问题题（60分，共10小题，每小题6分）（答在试卷上的内容无效）1、简述单纯形法的基本思路。解析：这是一道考查单纯形法基本知识的题目，是很容易出简答题的知识点。解：详见寇伟华运筹学P40。2、简述线性规划问题求解出现退化解的特征。解析：P58线性规划问题各种解的情况都容易出问答题，应理解并会用自己的语言组织。解：如果出现基变量等于零，就会造成基本可行解中非零变量的个数小于约束条件方 程的个数，这就是退化现象。在用单纯形法求解时，退化现象表现为，若确定的换出 变量同时有两个或两个以上，就会造成下一次迭代时有一个或几个基变

2、量的取值为0。3、什么是对偶问题的弱对偶性？解析：考查的是对偶问题的性质，对偶问题的性质是常考题目，应熟练掌握。解：详见寇伟华运筹学P76定理3.24、简述影子价值与边际值的区别。解析：这是考查概念的问题，影子价格和边际值是两个简单的概念，理解了自然能说 出他们的区别。解：详见寇伟华运筹学P95影子价格和边际值概念5、简述闭回路法求取运输问题检验数的步骤。解析：闭回路法求运输问题检验数是基本知识和方法，运输问题这里可以问的问题很多，可以问你表上作业法，可以问你差值法求初试基本可行解的步骤，可以问你位势 法求运输问题检验数的步骤等等，需要对运输问题的表上作业法的过程非常熟悉，才 能有助于解决这类

3、问答题以及计算题。解：详见寇伟华运筹学P128。6、简述指派问题等效矩阵的方法及性质。解析：考查指派问题的简答问答题，理解并用自己的语言组织即可。解：详见寇伟华运筹学P154定理6.1。7、简述无向图中连通图与完备图的区别。解析：考查的是图与网络这章的基本知识的概念和区别，应理解并掌握基础知识。解：详见寇伟华运筹学P216和P217完备图和连通图的概念。8、判别可行流是最小费用流的依据是什么？解析：考查图与网络中的基本判别条件，熟练掌握了最小费用流的解题过程也就能自己组织出答案。解：一个可行流是最小费用流的充要条件是网络中不存在负费用的增流圈。9、统筹方法制定最少工程费方案时，费用斜率的计算方

4、法是什么？解析：考查统筹方法的基本知识，应理解费用斜率代表的是什么含义，了解统筹方法的算法过程。珈由中八夕赶工时间的工序直接费用-正常时间的工序直接费用解：费用斜率 正常完工所需时间-赶工完成时间也可以用寇伟华运筹学P318的公式来回答。10、解释下为何 M/ M/1排队模型指标当中，队长与排队长计算结果为何相差不一定是1。解析：P343这是考查排队论这章中基本公式和基础知识的理解并间接考查了的范围取值原因。解：由于Lq L ,故队长和排队长相差一个繁忙度，又由于到达强度必须小q于服务强度，否则排队系统排队长度将会越来越大，以致出现爆炸现象，此时就不是排队问题了，所以0 VV 1。二、计算题（

5、70分，共4个小题）1某生产企业采用两种原料铁和铝，生产三种产品A、B、C,已知铁和铝每天可用资源单位量分别为100和120。生产有关资料如下表：产品单位产品铁消耗量单位产品铝消耗量单位产品利润A2340B3345C1225假设三种产品 A、B、C的日产量分别为 “、5 vq，建立模型使利润最大; A1 A2 A3MaxZ 40x1 40a2 25a3 2X1 3X2 X3 100 st 3x1 3X2 2X3 120 X1，X2，X3 0卜表为对上述模型运用单纯形法求解的一次迭代步骤;Cj40452500CbXbbX1X2X3X4X545X2100/32/311/31/300X520101-

6、11Zj304515150Cj-Zj10010-150请完成（1）进一步求解获得最优解（6分）（2）判断此问题最优解属于哪一种情况，为什么？ （3分）（3）若存在多重解，请写出所有的最优解。（6分）解析：考查单纯形法的计算过程以及最优解的判别，每年必考计算题目之一。解：（1） X1,X3的检验数相同，故选其中一个作为换入变量，这里选X3作为换入变量，根据最小比值原则，确定 X5为换出变量，调整后得到单纯形表如下:Cj40452500CbXbbX1X2X3X4X545X280/31/3101/3-1/325X32010101Zj4045251510Cj-Zj000-15-10单纯形表中所有非基变

7、量的检验数全部小于等于0,说明已达最优，最优解为(X1,X2,X3,X4,X5) (0,80/3,20,0,0),目标函数值为 z 45 80/3 25 20 1700。(2)此问题属于多重解。因为非基变量Xi检验数为0,即表明有多重解。(3)把Xi作为换入变量，根据最小比值原则确定 X3为换出变量，调整后的单纯形表如下:Cj40452500CbXbbX1X2X3X4X545X22001-1/31/3-2/340X12010101Zj4045251510Cj-Zj000-15-10已最优，新的最优解为(Xi,X2,X3,X4,X5)(20,20,0,0,0),目标函数值z 45 20 40 2

8、0 1700,将(1)得出的最优 解记做X(1),将(3)得到的最优解记做X(2), 则可以求出无穷个最优解：X X(1) (1 )X(2)(0,80/3,20,0,0) (1)(20,20,0,0,0)。2 (15分)某运输网络 G如下图，各条边数字依次为容量、流量、费用。请完成(1)判断图G是否为可行流。(2)判断图G是否为流值为(3分)10的最小费用流，如果不是，将当前的网络调整为最小费用流，要求计算出总费用。(6分)(3)求图G的最小费用最大流，要求计算出总费用。(6分)解析：考查的图与网络中可行流的判别条件，最小费用流的算法，以及最小费用最大流的算法，每年必考计算题的类型之一。解(1

9、)图G满足可行流的两个条件：任意边的容量限制条件，中间点的平衡条件。故该图为可行流。(2)构造增流网络Gf如下图存在负回路 C tViV2t ,故题目中给出的流并非流值为10的最小费用流。现在取:min 4,6,22。对题目中所给的流修改得新的网络图如下：b( f) 8 2 2 4 6 2 2 4 8 1 52。(3)使用标记算法求最大流标记：先给s表上（0,）检查s,边（S,V1）上，fs,1 Cs,i,故V1得不到标记，边（S,V2）上，fs,2< Cs,2,故V2标记为（s,l（V2）,其中，l（V2） min ,22。检查V2 ,边（V2,t）上，f2,t C2,t ,故t得不到

10、标记，边（Vi,V2）上，fl,2> 0 ,故对Vi标记（-V2,l（Vi）,其中，l（Vi）min 2,62。检查 Vi ,边(Vi,t)上，fi,t< Q,t,故对 t 标记(Vi,l(t),其中，l(t) min 2,42,t得到标记，进行下一步调整。调整：按顶点的第一个标记找到一条增流链Q sv2V1t，按 l （t） 2调整增流链上各边的流量，调整后如下图:上图中不存在增流链，已达最大流,该流是在最小费用的基础上得到的最大流，故上图即为最小费用最大流，总费用为b（f）82 4442448i64o3. （20分）某企业经营管理 应原料：原材料基地A: 200t ,单价原材料

11、基地B: 300t,单价原材料基地 C: 400t.单价 单价运价表（元/t）如下：2个加工工厂甲和乙.有200 元/t:i80 元/t:i60 元/t3个原材料基地以下列数量供原材料基地力口工厂甲乙A4050B2030Ci0060两个加工厂的容量及加工费用如下:力口工厂甲乙容量450t500t加工费400 元 /t300 元/t请完成(1)试建立该运输问题白数学模型。(10分)(2)加工厂出售产品的价格是 900元/t。问该企业如何组织两个加工厂的生产，使获得的利润 最大？利润值是多少？ (10分)解析：这是考查运输问题的题型，考查了不平衡运输问题的建模以及运输问题的求解。解：(1)原材料供

12、应量为 200+300+400=900t ,加工量为：450+500=950t。加工量大于供应量950-900=50t,这是一个需大于求的不平衡运输问题。虚设一个原材料基地为D ,供应量为50to设Xj为加工厂i加工来自原材料基地 j的加工量，i=甲，乙；j=A,B,C,D 。则建立的 运输问题模型如下：原料 加工厂ABCD销量甲6406006600450乙550510520050020030040050950(2)将求最大利润的问题转化成求最小费用的问题，构造综合表，用差值法确定初始基本 可行解。.、原料 加工尸ABCD销量差值甲X11640X12600X1366050*0450600乙X2

13、1550X22510X23520X050051020030040050950差值90901400用差值法重新构造综合表如下:原料 加工厂一、ABCD销量差值甲X11640X12600X66050*045040乙X21550X22510400*520X05001020030040050950差值90901400重新构造综合表如下:原料 加工广ABCD销量差值甲X11640X12600X66050*045040乙X21550X22510400*520X05004020030040050950差值909000A和B两列中差值相等，任选一个，这里选 B歹U,构造出的初始基本可行解的综合表如下:原料 加

14、工广ABCD销量差值甲200*640200*600X66050*045040乙X550100*510400*520X05004020030040050950差值909000基变量个数为5个，已得初始基本可行解。用位势法进行检验，在上表中，x11,x12,x14,x22,x23为基变量，因此有如下方程组:U1V1G1640U1V2c12600U1V4c140U2V2C22510U2V3C23520令U10 ,按照位势法的步骤写入表后，得下表:,尹料 力口工广640A600 B610C0D销量0甲200*640200*60050660050*450-90乙5500100*510400*520090

15、50020030040050950表中没有负检验数，说明已经找到最优解（'，'*''型/）（200,200,50,100,400） o即应该安排原材料 A 200t,原材料B 200t ,原材料D （虚）50t运往甲，原材料 B 100t,原 材料C 400t运往乙。则最小费用为值 z 640 200 600 200 0 50 510 100 520 400 507000。 由于只能提供原材料 900t,所以最大利润值w 900 900 507000 303000元。4. （20分）某港口外运公司的货场，装货汽车随机到达平均间隔时间为7.5min,服从指数分布。

16、装车设备为叉车，经统计一台叉车装一辆货车的平均时间12min,服从指数分布，若两台叉车同时装车时间缩短一半。问题如下：（1） “两台叉车同时装一辆汽车方式”和“用两台叉车各装一辆汽车”分别属于哪种排队模型形式（A/B/C）? （4分）（2）分别计算排队长 La和平均等待时间 W来比较两种作业方式哪一种更好？ （10分）qq（3）若采取叉车各装一辆汽车方式，若想使汽车到达后不排队的概率大于0.3,那么货场应至少安排几个叉车？ （ 6分）提示；（M / M / C）:/ /FCFS模型参考公式如下C 1 n 1Pon 0 nn! C!nPn P/当1 n<C。 n!解析：本题考查的排队论的知

17、识, 模型的计算公式和应用条件。每年和存储论必考其中之一,C! 12 P°应记住课本上给的几种简单排队论的题目首先你要找出到达强度和服务强度/ / FCFS ）的排队模型形式。解：（1）两台叉车同时装一辆汽车方式属于（M / M /1）:（用两台叉车各装一辆汽车属于（M /M /C）:（ / / FCFS ）的排队模型形式。（2）平均到达强度辆/h,平局服务强度60/12 5辆/h对第一种作业方式：到达强度 4辆/h,服务强度 5辆/h,繁忙度 /4/5 0.8。队长L 辆，排队长La L 3.2辆。服务时间 W L 1h,平均等待时间qWqLq0.8h。对第二种作业方式：C 2,繁

18、忙度/c 8/2 5 0.8n .n!C!325-1Lqcc!(1)20.8 8252 2!(0.2)225.6 辆，WqLq25.63.2ho比较可得第一种作业方式更优。(3)假设有N个，则相当于N个(M/M /1):( / /FCFS)模型，其中： 8/N ,5,5NP0 15NP (15N(15N按照要求P0P8881(1) 15N 5N5N5N)2>0.3求得N>1.91,取整数，则可知至少2台。三、建模题(20分，共两个小题，每小题 10分)1.已知某种产品有 n个销售点，有 m个配送中心可供选择以实现对产品的配送。设在配送 中心i对该产品的年配送能力上限为Ci,并因配送该产品而会增加年配送费用为Fi。