2014管理运筹学一-答案详解

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

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

3、定何时补充，补充多少数量的办法称之为存储策略。二、简答题(20分，共2小题)(答在试卷上的内容无效)1.(10分)如下所示的网络，每条弧旁边的数字是(q、fj),(Cj、fj分别表示该弧的首先知道该如何判断，就是看网络图中还是否存在增流链，是对课本中求网络最大流方法步骤的考查，判断找出了最大流，根据被标号的点和未被标号的点就找出了最小截集，这里给出两种解法。(由于是简答题，解法一可以简略一些回答)解法一：1、标记过程(1)先给源Vs标号(0,8)(2)对Vs进行检查，从Vs出发的边(Vs,V1)上，fs1<Cs1,故V1的标记为(+Vs,l(V2),其中，1(V1)=minq(Vs),(

4、cs1fs1)=min+=1,边(vs,v2)上,fs2=cs2,故v2得不到标记。vs成为已检查过的点。(3)取已标记而未检查的点V1,检查V1,在边(V1,V4)上，f1,4<C1,4,故V4的标记为(+v1,1(V4),其中1(V4)=min«1(4；(。,4一f1,4)=min4仆=1,边(vl)上，小=。,3,故丫3得不到标记，边(V1,V2)上，f1,2=0,故丫2得不到标记，V1成为已检查过的点。(4)检查V4,边(V2,V4)上,f2,4=1>0,故V2的标记为(V4,1(V2),其中，1(V2)=min4(V4),f2,4)=min(1,1)=1,边口,

5、)上，f4,t=C4,t,故V得不到标记。检查V2,边（V2,V3）上,f2,3<C2,3,故V3的标记为（+丫2,1（丫3）,其中，1 (v3)=min4(v2),(c2,3-f2,3)=min%,l=1。(6)检查v3,边(v3,vt)上，f3,t<c3,t,故vt的标记为(+v3,1(t)，其中，1(t)=minl(v3),(c3,tf3,t)=min七,2=1,因汇vt得到标记，进行调整。故可以判断该网络流并非最大流。2 .调整过程(1)反向追踪，按顶点的第一个标记找到一条增流链Q=vsv1V4V2V3Vt。(2)按日=1(t)=1调整增流链上各边的流量：fs,1=fs,1

6、71-31-4f1,4=f1,4-=11=2f2,3二f2,371=21=3f3,t=f3,t71=41=5f2,4=f2,4-1-1=。重复上述标记过程，寻找增流链。给Vs标记（0,+8）,检查Vs,边（Vs,V1）上，",边（Vs,V2）上，fs,2=Cs,2,均不符合标记条件，标号过程无法进行，算法结束。上图给出的可行流即为该网络的最大流。最大流为：v（f）=fs,1+fs,2=f3,t+f4,t=7。已标记的顶点集合为V1=s,未标记的顶点集合V1=&,v2,v3,v4,vt）,故有K(V1,V1)=(Vs,V1),(Vs,V2)是该网络的最小截集。解法查视VsViV

7、4V2V3标记VsViV4V2V3Vt+OO+1+1-1+1+1增流链为Q=vsv1V4V2V3Vt,修改量=1修改后该链为饱和链，继续标号查视Vs标记Vs一+00已不存在由vs到vt的增流链。故可以判断该网络流不是最大流，已标记的顶点集合为V1=s,未标记的顶点集合V=M,V2,V3,V4,V，故有KWiMxVs'ViNVs*）是该网络的最小截集。2.（10分）若如上所示的网络图，已知各弧的单位流量费用为bij,现要在已知最大流的基础上求最小费用流，试简述其方法。（不用计算结果）解析：这道简答题考查的是最小费用流的算法过程，题目比较简单，在课本中给出了详细步骤。解：（1）针对已知最大

8、流为7的网络图G,构建伴随网络流f的增流网络Gf。（2）针对增流网络Gf,查看是否存在基于w的负回路；若不存在，说明当前网络流已经是最小费用流，算法终止，否则转到（3）。（3）针对存在的负回路C,令6=minc'（e）,e为Gf中负回路的边上（4）针对负回路C对应的运输网络G中的圈，判断该圈是否为增流圈；若不是，转到（2）继续寻找负回路，否则转（5）。（5）针对运输网络G中的增流圈，把增流圈中方向与负回路方向一致的所有不饱和边的流量加上d;把增流圈中方向与负回路方向相反的所有正边的流量减去d。（6）继续寻找负回路，若有负回路，继续调整，否则转（1）。三、证明题（10分，共1小题）（答在

9、试卷上的内容无效）试用对偶理论证明下列线性规划模型为无界解。maxZ=3x14x2x3-x1+2x2+3x3<6st.3x1+x2-4x3<7X1,x2.x3之0解析：对偶问题的基本性质中弱对偶性是常考的证明题，这里考查的是弱对偶性里的推论3:若原问题可行，而对偶问题不可行，则原问题的目标函数值无界。解：令X=x2=x3=0,满足约束条件，可知原问题可行。该问题的对偶问题为minw=6y17y2-y1-3y2至32y1y2-4st.3y1-1y1,y2-0由约束条件1可知对偶问题不可行，由对偶问题弱对偶性的推论可知，原问题的为无界解。四、建模题（15分，共1小题）（答在试卷上的内容

10、无效）某企业有5个拟选择的投资项目，其所需投资额与期望收益如下表所示。由于各项目之间有一定的联系，A、C、E之间必须选择一项，且仅需选择一项；B和D之间需选择，也仅需使期望收益最大。选择一项；又由于C和D两项目密切相关，C的实施必须以D的实施为前提条件。该企业共筹集资金1500万元。试构建相应的模型以确定应该选择哪些项目投资，（不用求解）项目所需投资额（万元）期望收益（万兀）A60100B4080C2070D4060E5090解析：这道题很明显是一道考查0-1规划的投资问题建模题，一般的思路是，针对第j个项目，只有投资和不投资两种状态，所以可以用0-1变量xj来描述这两种状态：xj=1表示投资

11、第j个项目，Xj=0表示不投资。但在现实的投资问题中会有许多特殊要求，像排斥问题、优先级问题、不可缺问题等，而这些需要通过约束条件方程来表述。0-1规划问题模型的解1第i个项目被投资Q第i个项目不被投资法采用隐枚举法。解：引入0-1变量Xi(i=A,B,C,D,E),设Xi=«maxz=100XA80Xb70Xc60Xd90Xe60xa+40xb+20XC+40xd+50xe<1500st.，xB+xD<1XCXDxi=0或1四、计算题（85分，共5小题）（答在试卷上的内容无效）1.（15分）用两阶段法求下列线性规划模型的最优解。minz=2x13x212X1st*+3X

12、2>20Xi+X2=10X1,X200所以这道题就只能用此方法解析：题目中已经明确给出了用两阶段法来求解线性规划模型,来解答，考查的就是基础的两阶段法，往年没有考过，考生往往也就疏忽了对基础知识的复习，做起来就比较生疏，而且中间不小心算错了，后面的都白算，因此应该重视基础知识的复习以及加强计算能力。解：将模型化为如下形式，其中X3为松弛变量，X4为多余变量，X5,X6为人工变量minz=xx611，x1+x2+x3=424st'x1+3x2-x4+x5=20x1+x2+x6=10xj_0(j=1,2,3,4,5,6)第一阶段的初始单纯性表如下:CjT000011CBXbbxi乂2

13、x3乂4乂5x0乂341/21/410001x520130-1101乂610110001zj240-111cj-zj-2-40100表中检验数表明还未达到最优解，把乂2作为换入变量，乂5作为换出变量，得到如下单纯形表：cjT000011cBXBbXiX2X3X4X5X60X37/35/12011/12-1/1200X220/31/310-1/31/301X610/32/3001/3-1/31zj2/3001/3-1/31cj-zj-2/300-1/34/30表中检验数表明还未达到最优解，把X1作为换入变量，%作为换出变量，得到如下单纯形表：CjT000011cBXbbX1X2X3X4X5X60

14、X31/4001-1/81/8-5/80X25010-1/21/2-1/20X151001/2-1/23/2zj0000o0cj-zj000011由上表可知，非基变量检验数全部0,已达到最优解，且基变量中不含有人工变量，所以转入第二阶段：恢复原来的目标函数，继续用单纯形法求解。改变后如下表:cjT2300cBXBbx1乂2乂3乂40x31/4001-1/83x25010-1/22x151001/2Zj000-1/2cj-zj0001/2由检验数可知，上表已达到最优解，求出的最优解为1C(X,X2,X3,X4,%,%)=(5,5,0,0,0),目标函数值为z=2x5+3x5=25。42.(25分

15、)考虑如下线性规划问题maxz-5x15x213x3J_Xix23x3三20s.t.Jl2x1+4x2+10x3<90xj>0(j=1,2,3)J分别对两个约束条件引入松弛变量x4,x5,用单纯形法得到如下最优单纯形表。cj-551300CBXbb又2x3x4x5x220-113100*510160-2-410;j00-2-50不用重新求解，分别分析如下问题。(i)约束条件的右边常数变为*=i|10L模型的解会有什么变化?b220(2)使最优解不变的C2的变化范围；0-2(3)Xi对应的系数变为a11=0,模型的解会有什么变化？:a21151(4)增加一个新的约束条件2x1+X2+

16、5X3<50,模型的解会有什么变化?解析：这是一道综合计算题，既考查了对偶单纯形法的应用又考查了灵敏度分析的计算，这是每年必考的计算题之一，虽然变化的类型不算多，但灵活性比较高，需要自己总结归纳，熟练掌握。上二10J101010解：（1）B=Jb=Bb=Jcci，代入单纯形表得:1411-41120120C-551300CBXBbX1X2X3X4X55X210-113100X5-20160-2-41%00-2-50-2-5-X5为换出变量，一V，故X3为换入变量，得新的单纯形表-2-4Cj-551300CbXBbX1X2X3X4X55X2-202310-53/213X310-8012-1

17、/2j-1600-1-1X2为换出变量，X4为换入变量，得新的单纯形法如下:C-551300CbXbbX1X2X3X4X50X44-23/5-1/501-3/1013X326/52/5101/10仃j-103/5-1/500-13/10此时，所有的非基变量检验数均小于0,达到最优解，最优解为(X1,X2,X3,X4,X5)=(0,0,2,4,0),目标函数最优值为z=26(2) X2为基变量，故maXX-2/3),(-5/1).C2<min'0/(-1)即2/3WAc2<0那么C2值得允许变化范围就是13/3,5。10B=|-41，一2_?p1-BR-一一401汨0-：；1

18、-Ci-Cbp1-2-5所以最优解不会发生变化。(4)增加一个新的约束条件2治+x2+5x3<50,引入松弛变量x6化为2X1+X2+5X3+%=50,其中X6之0,把X6作为基变量，然后把这个方程的系数补加到题目中给出单纯形表的最后一行中，得下表cj-5513000CbXbbX1X2X3X4X5X65X220-1131000X510160-2-4100X650215001进行初等变换，使基变量的系数矩阵变为单位矩阵，如下表:cj-5513000CBXbbX1X2X3X4X5X65X220-1131000X510160-2-4100X630302-1016j00-2-500表满足最优检验

19、，基变量也可行，得到最优解（Xi,X2,X3,X4,X5,X6）=（0,20,0,0,10,30）,模型的解不变。3. （10分）六个城市Ci（1WiW6）间航空票价（表示Ci与Cj间票价，单位：100元）见下表（式表示无直接航线），现在要设计出任何两城市间票价最廉的路线方案。请建立模型，并以C1与其他城市间方案为例作具体说明。0500(cij)6>6=402510152082501020笛010250550_解析：从题目给出的矩阵可以联想到图与网络中介绍的无向图，所以这个问题考查的是图与网络的最短路问题，转化成无向图即建立了最短路的模型。解：（1）用图表示出来题目中矩阵即建立了任何两城

20、市间票价路线方案模型，如下图也可以建立如下的网络模型图:10（2）用Dijkstra算法迭代，将计算信息汇集为如下运算表:k0102030405060jT(0j)1*0COoOaooOoO2501aO401251*1013356oO356_*2514*356455355,65455一_*355,66*4545由上表可知C1到C2的最短径路是：C1-C6-C2费用3500C1到C3的最短径路是：C1fC6-C4-C3或C1-C5-C4-C3或C1-C5-C3费用4500C1至ijC4的最短径路是：010504或C1-C6-C4费用3500C1到05的最短径路是：C1一C5费用2500元01到06

21、的最短径路是：C1fC6费用1000元4. （20分）有某物资从NAA处运往B，B2,B3三个地方，各处供应量、需求量（单位：t）及单位运价（单位：10元/t）见下表。、销地产地一、BiB2B3A1592i5A23i7iiA362820销量i8i2i6判断以下给出的方案可否作为初始可行解（说明判断依据）？并求物资最优调运方案及其最小总费用。丁、销地产地BiB2B3Ai3i2A2iiA3i5i4解析：这道题考查的是运输问题的基本定理和表上作业法求产销平衡运输问题的最优值算法，难度不大，还可以考查产销不平衡或产销量不确定等条件的运输问题来增加难度，运输问题是每年必考的计算题之一，应予以重视。解：（

22、1）题目给出的方案不可以作为初始可行解，虽然产销平衡，但是根据定理：m+n-1个变量构成基本可行解的充要条件是它不含闭回路。而给出的方案中基变量个数为6个，而且Xii,Xi3,X33,X3i可以构成一个闭回路，故不可作为初始可行解。（2）构造综合表，在综合表的最右边补一列，在最下面补一行，然后分别计算差值并填入表中，如下表：销地产地、BiB2B3差值Aix11x12x13592153A2x21x22X23317112A3X31X32X33628204销量181216E=46差值215在上表中，最大差值5来自第三列，在第三列中没有被标识的变量所对应的最小运价是C13=2,在这里选择变量X3作为基

23、变量。为3=15,并将取值右上角打上*号，处理后的综合表如下：销地产地、B1B2B3差值A1XX15592153A2X21X22X23317112A3X31X32X33628204销量181216工=46差值215对上表重新计算差值，按照上述方法找出基变量，处理后的综合表如下:销地产地、BiB2B3差值Ai.*XX15592150A2X21XX23317112A3X3112X33628204销量181216E=46差值311重复上述步骤，处理后的综合表如下:销地产地B1B2B3差值A15X9X2*15150A23*111X7X114A36X312*128X33202销量181216Z=46差值

24、301重复上述步骤，处理后的综合表如下:销地产地、B1B2B3差值A1._*xx15592150A2*11XX317110A3*7121628200销量181216工=46差值000在上表中，Xi3,X21,X31,X32,X33为基变量，因此有如下方程式组:U1V3-c13-2U2'vC21=3u3v1=c31=6U3V2=c32=2U3V3=C33=8令U1=0,按照位势法写入表中，得下表:销地0-42产地B1B2B3._*xx150A115592*11XX3A211317*71216A320628销量181216工=46计算出所有非基变量的检验数，并将求出的检验数填到综合表中对应的非基变量Xj的位置,如下表：销地0-42产地、BiB2B3*513150Ai15592*11223A211317*71216A320628销量181216E=46表中没有负检验数，说明已经是最优解，即(x13,x21,x31,x32,x33)=(15,11,7,12,1)调