2014管理运筹学一

1、试题代码：929西南交通大学2014年硕士研究生招生入学考试试题名称：管理运筹学一考试时间：2014年1月考生请注意：1、本试题共五题，共4页，满分150分，请认真检查；2、答题时，直接将答案内容写在考场提供的答题纸上，答在试卷上的内容无效；3、请在答题纸上按要求填写试题代码和试题名称；4、试卷不得拆开，否则遗失后果自负。一判断题（20分，共5小题）（答在试卷上的内容无效）（对错误的选项应改错或说明原因）对一个有n个变量m个约束条件的标准型线性规划模型，其可行域的顶点恰好为 TOC o 1-5 h z Cm个。（X ）解析：可以举个例子，假设是2两个变量2个约束条件，那么可行域的顶点并不恰好

2、为1个。指派问题系数矩阵的某一行（列）各元素分别减去该行（列）的最小元素，得到的新矩阵求得的最优解和原系数矩阵求得的最优解相同。（V ）整数规划模型的最优目标函数值一定不大于其对应的线性规划模型的最优目标函数值。（V ）对于一个动态规划问题，应用顺序解法或逆序解法可能会得到不同的结果。（X ）解析：顺序法和逆序法是解决动态规划问题的两种方法，对于同一个动态规划问题，无论使 用的是哪种方法，最后得出的结果是一定的，相同的。改错：对于一个动态规划问题，应用顺序解法或逆序解法得到相同的结果。存储策略就是决定补充存储数量的策略。（X ）解析：存储策略不止是决定补充存储数量，而且还决定补充时间，这里题目

3、说的不全面。改错：决定何时补充，补充多少数量的办法称之为存储策略。二、简答题（20分，共2小题）（答在试卷上的内容无效）（10分）如下所示的网络，每条弧旁边的数字是（。、f ），（。、f分别表示该弧的 ij ij ij ij容量和流量）。试判断该网络流是否为最大流，并找出其最小截集。解析：这是一道考查网络的流中最大流的基础题，判断网络流是否为最大流，首先知道该如 何判断，就是看网络图中还是否存在增流链，是对课本中求网络最大流方法步骤的考查，判 断找出了最大流，根据被标号的点和未被标号的点就找出了最小截集，这里给出两种解法。（由于是简答题，解法一可以简略一些回答） 解法一：1、标记过程（1）先给

4、源七标号（0，8）（2）对V进行检查，从V出发的边（V，V ）上，f vc，故V的标记为（+Vsss 1s1s11s 1其中，l(v ) = min b(v ),(c - f R= min、8,1= 1，边(v ,v)上，f = c，/ ，故顷不到标记。V成为已检查过的点。(3)取已标记而未检查的点V，检查V，在边(v ,V )上，f 0，故七的标记为（-V4,l A，其中，(4)检查 V4，边(v2,V4)上l(V ) = min(v ), f = min(1,1) = 1，边(v ,v )上，f = c ，故v 得不到标记。242,44 t4,t4,tt检查v ,边(v , v )上，f

5、V c ,故v的标记为(+V ,l(v ),其中， TOC o 1-5 h z 232,32,3323l(v ) = min(v ),(c - f )= min,1= 1。322,32,3检查v ,边(v , v )上，f V c ,故v的标记为(+v ,l(t),其中，3 t3,t3,tt3l(t) = min(v3),(c3t -f3t)= minb,2= 1,因汇v,得到标记，进行调整。故可以判断该网络流并非最大流。调整过程反向追踪，按顶点的第一个标记找到一条增流链Q = vvvvvv。s 1 4 2 3 t按0 = l(t) =1调整增流链上各边的流量：=f +0= 3 +1 = 4=

6、f +0 = 1 +1 = 2=f +0 = 2 +1 = 332,3f = f +0 = 4 +1 = 5f = f -0= 1 -1 = 02,42,4其他边上流量保持不变。调整后的得到网络图上一个新的可行流，如下图重复上述标记过程，寻找增流链。给v标记(0，+8)，检查v，边(v , v )上，f = c， sss 1s ,1s ,1边(vs，v2)上，fs,2=cs,2，均不符合标记条件，标号过程无法进行，算法结束。上图给出的可行流即为该网络的最大流。最大流为：v( f *) = fs1 +乙=/ t + /广7。已标记的顶点 集合为匕=，未标记的顶点集合V =v,v ,v ,v ,v

7、 ，故有111234 tK(V ,V) = b , v ),(v , v )是该网络的最小截集。11s 1 s 2解法二:查视vsv1v4v2v3标记vsv1v4v2v3vt标号+ 8+1+1-1+1+1增流链为Q = WWW ,修改量= s 1 4 2 3 t修改后该链为饱和链，继续标号查视vs标记vs标号+ 8已不存在由七到匕的增流链。故可以判断该网络流不是最大流，已标记的顶点集合为匕= *，未标记的顶点集合V = V , v , v , v , v ，故有K（V ,V） = b , v ）,（v , v ）是该网络的最小截集。11234 t11s 1 s 22.（10分）若如上所示的网络

8、图，已知各弧的单位流量费用为七7.，现要在已知最大流的基础上求最小费用流，试简述其方法。（不用计算结果）解析：这道简答题考查的是最小费用流的算法过程，题目比较简单，在课本中给出了详细步 骤。解：（1）针对已知最大流为7的网络图G，构建伴随网络流f的增流网络Gf。（2）针对增流网络G，查看是否存在基于伊的负回路；若不存在，说明当前网络流已经是最小费用流，算法终止，否则转到（3）。（3）针对存在的负回路C ,令6 = min V（e）, eG负回路的边匕（4）针对负回路C对应的运输网络G中的圈，判断该圈是否为增流圈；若不是，转到2） 继续寻找负回路，否则转（5）。（5）针对运输网络G中的增流圈，把

9、增流圈中方向与负回路方向一致的所有不饱和边的流 量加上6 ；把增流圈中方向与负回路方向相反的所有正边的流量减去6。（6）继续寻找负回路，若有负回路，继续调整，否则转（1）。三、证明题（10分，共1小题）（答在试卷上的内容无效）试用对偶理论证明下列线性规划模型为无界解。max Z = 3x + 4 x + x-x + 2 x + 3 x 6s.t. - 3x + x - 4x 0123解析：对偶问题的基本性质中弱对偶性是常考的证明题，这里考查的是弱对偶性里的推论3： 若原问题可行，而对偶问题不可行，则原问题的目标函数值无界。解：令气=x2= %= 0，满足约束条件，可知原问题可行。该问题的对偶问

10、题为min w = 6 y + 7 yf - 3 * 3y + y 4s.t. 1、y1，y2 0由约束条件1可知对偶问题不可行，由对偶问题弱对偶性的推论可知，原问题的为无界解。四、建模题（15分，共1小题）（答在试卷上的内容无效）某企业有5个拟选择的投资项目，其所需投资额与期望收益如下表所示。由于各项目之间有 一定的联系，A、C、E之间必须选择一项，且仅需选择一项；B和D之间需选择，也仅需 选择一项；又由于C和D两项目密切相关，C的实施必须以D的实施为前提条件。该企业 共筹集资金1500万元。试构建相应的模型以确定应该选择哪些项目投资，使期望收益最大。（不用求解）项目所需投资额（万元）期望收

11、益（万元）A60100B4080C2070D4060E5090解：引入 0-1 变量七（i = A, B,C, D, E），设 I,=1第i个项目被投资0第i个项目不被投资解析：这道题很明显是一道考查0-1规划的投资问题建模题，一般的思路是，针对第j个项 目，只有投资和不投资两种状态，所以可以用0-1变量I,来描述这两种状态：I, = 1表示投 资第j个项目，= 0表示不投资。但在现实的投资问题中会有许多特殊要求，像排斥问题、 优先级问题、不可缺问题等，而这些需要通过约束条件方程来表述。0-1规划问题模型的解 法采用隐枚举法。max z = 100 x + 80 x + 70 x + 60 x

12、 + 90 x60 xA + 40 xB + 20 xc + 40 xD + 50工日 1500s.t.x + x + x = 1x + x 1x xC DX = 0或 1四、计算题（85分，共5小题）（答在试卷上的内容无效）1.（15分）用两阶段法求下列线性规划模型的最优解。min z = 2 x + 3x1211/s.t.2 x1 + 4 x2 20 气+ x2 =10 x , x 0 解析：题目中已经明确给出了用两阶段法来求解线性规划模型，所以这道题就只能用此方法 来解答，考查的就是基础的两阶段法，往年没有考过，考生往往也就疏忽了对基础知识的复 习，做起来就比较生疏，而且中间不小心算错了

13、，后面的都白算，因此应该重视基础知识的 复习以及加强计算能力。解：将模型化为如下形式，其中为松弛变量，x为多余变量，x，x为人工变量 TOC o 1-5 h z 3456min z = x + xf151 6x + x + x = 42 14 23s.t. 0( j =61,2,3,4,5,6)第一阶段的初始单纯性表如下:c. T000011cBXBbx1x2x3x4x5x60 x341/21/410001x520130-1101x610110001zj240-111c - z,-2-40100表中检验数表明还未达到最优解，把x2作为换入变量，尤5作为换出变量，得到如下单纯形表：c T0000

14、11cXbxxxxxxBB1234560 x37/35/12011/12-1/1200 x220/31/310-1/31/301x610/32/3001/3-1/31zj2/3001/3-1/31c - z.-2/300-1/34/30表中检验数表明还未达到最优解，把七作为换入变量x6作为换出变量，得到如下单纯形表：C . T000011CXbxxxxxxBB1234560 x31/4001-1/81/8-5/80 x25010-1/21/2-1/20 x151001/2-1/23/2zj0000o0c - z.000011由上表可知，非基变量检验数全部N0,已达到最优解，且基变量中不含有人工

15、变量，所以 转入第二阶段：恢复原来的目标函数，继续用单纯形法求解。改变后如下表：c T2300cBXBbX1X2X3X40X31/4001-1/83X25010-1/22X151001/2z000-1/20001/2由检验数可知，上表已达到最优解，求出的最优解为1(X,X ,X ,X ,X ,X ) = (5,5,丁，0,0,0)目标函数值为z = 2X5 + 3X5 = 251 2 3 4 5 6J，目 4刀函 I 且/y z 八丁八。2. (25分)考虑如下线性规划问题max z = 一5 x + 5 x +13 xx + x + 3x V 20s.t 12x + 4x +10 x 0(j

16、 = 1,2,3)i j分别对两个约束条件引入松弛变量X4,X5，用单纯形法得到如下最优单纯形表。不用重新求解，分别分析如下问题。b 10 （1）约束条件的右边常数变为b=202模型的解会有什么变化?（2）使最优解不变的c 2的变化范围;(3)X对应的系数变为c1aiia21-2模型的解会有什么变化?（4）增加一个新的约束条件2x + x + 5x 50，模型的解会有什么变化?解析：这是一道综合计算题，既考查了对偶单纯形法的应用又考查了灵敏度分析的计算，这是每年必考的计算题之一，虽然变化的类型不算多，但灵活性比较高，需要自己总结归纳，熟练掌握。解：（1）B-1 =-10b = B-1b =-1

17、0一10 -=-10 一，代入单纯形表得:-41-4120-20c j-551300CBXBbX1X2X3X4X55X210-113100X5-20160-2-41bj00-2-50X为换出变量，故X5-2-43为换入变量，得新的单纯形表cj-551300CBXBbX1X2X3X4X55X2-202310-53/213X310-8012-1/2bj-1600-1-1X2为换出变量，4为换入变量，得新的单纯形法如下:3 , X , X , X , X ) = (0,0,2,4,0)，目标函数最优值为 z = 2612345(2) X2为基变量，故max (-2/3),(-5/1) Ac minb/(-1)即-2/3 Ac2 0那么c2值得允许变化范围就是113/3,5。-10-10o0(3) B-1 =-41P： = B-1P1 =-415=55 =c -c p =-2-E 0- 0 =-2 0所以最优解不会发生变化。11 B 15(4)增加一个新的约束条件2x +