929管理运筹学1答案.docx

1、929管理运筹学1答案西南交通大学2014年全日制硕士研究生入学试题解析试题名称：管理运筹学一一、判断题（20分，共5小题）（答在试卷上的内容无效）（对错误的选项应改错或说明原因）1对一个有n个变量m个约束条件的标准型线性规划模型，其可行域的顶点恰好为呼个。 （x ）解析：可以举个例子，假设是 2两个变量2个约束条件，那么可行域的顶点并不恰好 为1个。2、 指派问题系数矩阵的某一行（列）各元素分别减去该行（列）的最小元素，得到的新矩阵求得的最优解和原系数矩阵求得的最优解相同。 （V ）3、 整数规划模型的最优目标函数值一定不大于其对应的线性规划模型的最优目标函数值。 （V ）4、 对于一个动态

2、规划问题，应用顺序解法或逆序解法可能会得到不同的结果。（X ）解析：顺序法和逆序法是解决动态规划问题的两种方法， 对于同一个动态规划问题， 无论使用的是哪种方法，最后得出的结果是一定的，相同的。改错：对于一个动态规划问题，应用顺序解法或逆序解法得到相同的结果。5、 存储策略就是决定补充存储数量的策略。 （X ） 解析：存储策略不止是决定补充存储数量，而且还决定补充时间，这里题目说的不全面。改错：决定何时补充，补充多少数量的办法称之为存储策略。二、简答题（20分，共2小题）（答在试卷上的内容无效）1、（ 10分）如下所示的网络，每条弧旁边的数字是（ q、 ）, （ Cj、币）分别表示该弧解析：这

3、是一道考查网络的流中最大流的基础题， 判断网络流是否为最大流， 首先知道该如何判断，就是看网络图中还是否存在增流链， 是对课本中求网络最大流方法步骤的考查， 判断找出了最大流，根据被标号的点和未被标号的点就找出了最小截集，这里给出两种解法。(由于是简答题，解法一可以简略一些回答)解法一：1、标记过程(1 )先给源Vs标号(0,：)(2)对Vs进行检查，从Vs出发的边(Vs , Vi ) 上, fsi Csi，故Vi的标记为(+ Vs , I(V2),其中，l(vi) =min 讣(Vs),(Csi - fsi) = min ,1 =1，边(Vs)上， fs2 = Cs2，故 V2 得不到标记。

4、Vs成为已检查过的点。(3 )取已标记而未检查的点 V,，检查V,，在边(V4)上，,4 0 ,故 V2 的标记为(V4,I(V2),其中，l(V2)=mi门勺“),f2,4=min(i,i) =i，边 SvJ上，fqtit，故 w得不到标记。(5)检查 V2 ,边(V2, V3)上，f2 ,乐 C2,3 ,故 V3 的标记为(+v2,I(v3),其中，I (v3) =min(v2), (c2,3 f2,3)=min,i=i。(6)检查 V3 ,边(V3,Vt)上,f3,t V C3,t，故 Vt 的标记为( + V3,l(t)，其中，l(t)=mi nt(V3),(Q,t - f3,t)=m

5、 i n,2=i,因汇Vt得到标记，进行调整。故可以判断该网 络流并非最大流。2、调整过程(i )反向追踪，按顶点的第一个标记找到一条增流链 VsViV4V2V3Vt 0(2)按v -l(t) =i调整增流链上各边的流量：fs,i = f:s, =3+i =4fi,4 二 fi,4 二=2f2,3 二f2,3 +8 =2+i =3f3厂f：3,t =4+i =5f2,4 =f2,4 日=i T=0其他边上流量保持不变。调整后的得到网络图上一个新的可行流，如下图重复上述标记过程，寻找增流链。给 Vs标记（0, ）,检查vs，边（Vs,w）上，fs1 = cs,1，边 （Vs，V2）上，fs,2

6、=Cs,2，均不符合标记条件，标号过程无法进行，算法结束。上图给出的可行流即为该网络的最大流。 最大流为：v（ f ） = fsj + fs,2 = f3,t + f4,t =7。已标记的顶点集合为y ，未标记的顶点集合V1 = g ,v2, V3,V4,Vt 1 ，故有K（Vi,VJ =、（Vs, Vi）, （VsM） 是该网络的最小截集。解法查视VsV1V4V2V3标记VsV1V4V2V3Vt号 标+ m+1+1-1+1+1增流链为Q = VsV1V4V2V3Vt，修改量：=1修改后如下图修改后该链为饱和链，继续标号查视Vs标记Vs一号 标+ OO已不存在由Vs到Vt的增流链。故可以判断该

7、网络流不是最大流，已标记的顶点集合为 y - ，未标记的顶点集合Vi = iVi,V2,V3, V4,v/?，故有 K（Vi,Vi） = i（Vs,Vi）,（Vs,V2）是该网络的最小截集。2、（ 10分）若如上所示的网络图，已知各弧的单位流量费用为 bj，现要在已知最大流的基础上求最小费用流，试简述其方法。 （不用计算结果）解析：这道简答题考查的是最小费用流的算法过程， 题目比较简单，在课本中给出了详细步骤。解：（1）针对已知最大流为 7的网络图G,构建伴随网络流 f的增流网络Gf。（2） 针对增流网络 Gf，查看是否存在基于 w的负回路；若不存在，说明当前网络流已经是最小费用流，算法终止，

8、否则转到（ 3）。（3） 针对存在的负回路 C ,令= min?c（e）,e为Gf中负回路的边（4） 针对负回路C对应的运输网络 G中的圈，判断该圈是否为增流圈；若不是，转到（ 2）继续寻找负回路，否则转（5）。（5） 针对运输网络G中的增流圈，把增流圈中方向与负回路方向一致的所有不饱和边的流量加上；把增流圈中方向与负回路方向相反的所有正边的流量减去 。（6 ）继续寻找负回路，若有负回路，继续调整，否则转（ 1）。三、证明题（10分，共1小题）（答在试卷上的内容无效）试用对偶理论证明下列线性规划模型为无界解。maxZ = 3为 4x2 x3-X| 2x2 3x3 三 6st +x2 4x3 兰

9、 7X1,X2,X3 一0解析：对偶问题的基本性质中弱对偶性是常考的证明题， 这里考查的是弱对偶性里的推论 3：若原问题可行，而对偶问题不可行，则原问题的目标函数值无界。解：令 =x2 =x3 =0，满足约束条件，可知原问题可行。该问题的对偶问题为min w =6% 7y2% 3 y?二 32% +y2 3 4st 3yi -4y2 二 1yi, y0由约束条件i可知对偶问题不可行，由对偶问题弱对偶性的推论可知，原问题的为无界解。四、建模题（15分，共1小题）（答在试卷上的内容无效）某企业有5个拟选择的投资项目， 其所需投资额与期望收益如下表所示。 由于各项目之间有 一定的联系，A、C、E之间

10、必须选择一项，且仅需选择一项； B和D之间需选择，也仅需选择一项；又由于 C和D两项目密切相关，C的实施必须以D的实施为前提条件。该企业 共筹集资金1500万元。试构建相应的模型以确定应该选择哪些项目投资， 使期望收益最大。（不用求解）项目所需投资额（万兀）期望收益（万元）A60100B4080C2070D4060E5090解析：这道题很明显是一道考查 0-1规划的投资问题建模题，一般的思路是，针对第 j个项 目，只有投资和不投资两种状态， 所以可以用0-1变量x来描述这两种状态：Xj =1表示投资第j个项目，Xj =0表示不投资。但在现实的投资问题中会有许多特殊要求， 像排斥问题、优先级问题

11、、不可缺问题等，而这些需要通过约束条件方程来表述。 0-1规划问题模型的解法采用隐枚举法。P167max z = 100xa 80冷 70xc 60xd 90xe 60xa +40xB +20xC +40xd +50xe 兰 1500 Xa +xc +xe =1st xB +xD 兰 1xc 兰 Xdx =0或1五、计算题（85分，共5小题）（答在试卷上的内容无效）1、( 15分)用两阶段法求下列线性规划模型的最优解。min z =2x 3x2fl 1 /Xx220% 十 x2 = 10Xi,X2 -0解析：题目中已经明确给出了用两阶段法来求解线性规划模型， 所以这道题就只能用此方法 来解答，

12、考查的就是基础的两阶段法，往年没有考过，考生往往也就疏忽了对基础知识的复 习，做起来就比较生疏， 而且中间不小心算错了， 后面的都白算，因此应该重视基础知识的 复习以及加强计算能力。解：将模型化为如下形式，其中 X3为松弛变量，X4为多余变量，x5，x6为人工变量1x2 x3 = 44stX1 * 3x? X4 + X5 = 20为 +x2 +x6 =10Xj -0(j =123,4,5,6)第一阶段的初始单纯性表如下:CjT000011CBXbb0X31X51X6ZjCjzCj T000011CBXbbX1X2X3X4X5X0X341/21/410001X520130-1101X101100

13、01Zj240-111Cj _Zj-2-40100表中检验数表明未达到最优解， 把X2作为换入变量，X5作为换出变量，得到如下单纯形表:Cj T 0 0 0 0 1 1CBX BbX1X2X3X4X5X60X37/35/12011/12-1/1200X220/31/310-1/31/301X10/32/3001/3-1/31Zj2/3001/3-1/31Cj _Zj-2/300-1/34/30表中检验数表明还未达到最优解， 把X1作为换入变量，x6作为换出变量，得到如下单纯形表：CjT000011CBX BbX1X2X3X4X5X60X31/4001-1/81/8-5/80X25010-1/2

14、1/2-1/20X151001/2-1/23/2Zj0000o0Cj -Zj000011由上表可知，非基变量检验数全部 0,已达到最优解，且基变量中不含有人工变量，所以转入第二阶段：恢复原来的目标函数，继续用单纯形法求解。改变后如下表：Cj T 2 3 0 0CBXbbXiX2X3X40X31/4001-1/83X25010-1/22Xi51001/2Zj000-1/2Cj _召0001/2由检验数可知，上表已达到最优解，求出的最优解为1(Xi,X2,X3,X4,X5,X6)=(5,5,，0,0,0)，目标函数值为 z=2 5 3 5 = 25。42、( 25分)考虑如下线性规划问题max z

15、 = -5xi 5x2 13x3+x2 +3x3 兰 20stt?12x1 +4x2 +10x3 兰90Xj O(1,2,3)分别对两个约束条件引入松弛变量 X4,x5，用单纯形法得到如下最优单纯形表。Cj-551300CBXbbXiX2X3X4x5X220-113100X510160-2-41CTj00-2-50不用重新求解，分别分析如下问题。(1)约束条件的右边常数变为(2)使最优解不变的 C2的变化范围；g r-2(3) X1对应的系数变为 a = 0 ，模型的解会有什么变化？丿21 - .5 -(4) 增加一个新的约束条件 2xi X2 5x3 - 50，模型的解会有什么变化?解析：这

16、是一道综合计算题，既考查了对偶单纯形法的应用又考查了灵敏度分析的计算， 这是每年必考的计算题之一，虽然变化的类型不算多，但灵活性比较高，需要自己总结归纳，熟练掌握。1 0-丄 _1 01101；10D = B b =4 1 一4 1 一20 一一20 一，代入单纯形表得:解：(1) BdCj-551300CbXbbX1X2X3X4X55X210-113100X5-20160-2-41aj00-2-50-2 -5x5为换出变量， V ，故x3为换入变量，得新的单纯形表-2 -4Cj-551300CBX BbX1X2X3X4X55X2-202310-53/213X310-8012-1/2aj-16

17、00-1-1X2为换出变量，X4为换入变量，得新的单纯形法如下:Cj-551300CbXbbX2X3X4X50X44-23/5-1/501-3/1013X326/52/5101/10aj-103/5-1/500-13/10此时，所有的非基变量检验数均小于 0,达到最优解，最优解为(为必氏必风)=(0,0,2,4,0)，目标函数最优值为 z = 26(2)X2为基变量，故maxX-2/3),(-5/1) . ：c minb/(1*即-2/3心乞0 那么c2值得允许变化范围就是 13/3,5】。(4)增加一个新的约束条件2x1 x2 5x 50 ,引入松弛变量x6化为2x1 x2 5x3 x =

18、50 ,其中x6 - 0，把x6作为基变量，然后把这个方程的系数补加到题目中给出单纯形表的最后一行中，得下表Cj-5513000CbXbbX1X2X3X4X5X65X220-1131000X510160-2-4100X650215001进行初等变换，使基变量的系数矩阵变为单位矩阵，如下表:Cj-5513000CbXbbX1X2X3X4X5X65X220-1131000X510160-2-4100X630302-10100-2-500表满足最优检验，基变量也可行，得到最优解 （捲，x2,x3,X4,X5,x6） = （0,20,0,0,10,30），模型的解不变。3、（ 10分）六个城市G （仁

19、i乞6）间航空票价q（表示g与Cj间票价，单位：100元）见请建立模型,F表（：表示无直接航线），现在要设计出任何两城市间票价最廉的路线方案。并以Ci与其他城市间方案为例作具体说明。解：（1）用图表示出来题目中矩阵即建立了任何两城市间票价路线方案模型，如下图C4也可以建立如下的网络模型图:10(2)用Dijkstra算法迭代，将计算信息汇集为如下运算表:k CjCiC2C3C4C5C61*0co00COQOQO250iaO40i25i*i0i3356aO356*25i435*6455355,6545535 5,66*454,5由上表可知Ci到C2的最短径路是 ：G r 丿C? 费用3500Ci

20、 到 C3 的最短径路是： Gr C6 r C4 r C或 G r C5 r C4 r C3 或 G C5 r C3费用4500。Ci到C4的最短径路是： G r C5 r C4或G r C C4费用3500。Ci到C5的最短径路是： G r C5费用2500元Ci到C6的最短径路是：G r C6费用1000元4、 （20分）有某物资从 Ai,A2,Aj处运往 BB2,B3三个地方，各处供应量、需求量（单位：t）及单位运价（单位：10元/t）见下表。、销地产地BiB2B3产量A59215A31711A62820销量181216判断以下给出的方案可否作为初始可行解 （说明判断依据）？并求物资最优

21、调运方案及其最小总费用。销地产地B1B2B3A312A211A1514解析：这道题考查的是运输问题的基本定理和表上作业法求产销平衡运输问题的最优值算法，难度不大，还可以考查产销不平衡或产销量不确定等条件的运输问题来增加难度， 运输问题是每年必考的计算题之一，应予以重视。解：（1）题目给出的方案不可以作为初始可行解，虽然产销平衡，但是根据定理： m+n-1个变量构成基本可行解的充要条件是它不含闭回路。 而给出的方案中基变量个数为 6个，而且Xn,Xi3,X33, X31可以构成一个闭回路，故不可作为初始可行解。（2）构造综合表，在综合表的最右边补一列，在最下面补一行，然后分别计算差值并填入 表中

22、，如下表：、销地产地BiB2B3产量差值AiXii5X29X132153A2X213X221X237112A3X316X322X338204销量181216送=46差值215在上表中，最大差值 5来自第三列，在第三列中没有被标识的变量所对应的最小运价是C13 = 2，在这里选择变量X!3作为基变量。X3=15，并将取值画上圈，处理后的综合表如下:肖地产地 、B1B2B3产量差值A1X5X92153A2X213X221X237112A3X316X322X338204销量181216Z =46差值215对上表重新计算差值，按照上述方法找出基变量，处理后的综合表如下:、销地产地BiB2B3产量差值A

23、iX5X92150A2X213X1X237112A3X3162X338204销量181216送=46差值311重复上述步骤，处理后的综合表如下:、销地 产地 、B1B2B3产量差值A1X5X92150A23X1X7114A 3X3162X338202销量181216Z =46差值301重复上述步骤，处理后的综合表如下:、销地产地BiB2B3产量差值AiX5X92150A23X1X7110A3628200销量181216送=46差值000在上表中，X13 , X21 , X31 , X32氐3为基变量，因此有如下方程式组:u1 V3 = Ci3 = 2U2 V| C21 = 3u3 V1 - C31 = 6U3 V2 - C32 = 2u3 V3 = C33 = 8令比=0，按照位势法写入表中，得下表:、销地 产地 、0B1-4B22B3产量0A1X5X92153A23X1X7116A362820销量181216送=46计算出所有非基变量的检验数，并将求出的检验数填到综合表中对应的非基变量 xij的位