2014年929管理运筹学1答案

1、西南交通大学2014年全日制硕士研究生入学试题解析试题名称：管理运筹学一一、判断题（20分，共5小题）（答在试卷上的内容无效）（对错误的选项应改错或说明原因）1对一个有n个变量m个约束条件的标准型线性规划模型，其可行域的顶点恰好为 TOC o 1-5 h z 呼个。（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出发的边(* , V)上，fsi Cs,，故V的标记为(+ Vs , I (V2),其中，l(vj=min 讣(Vs),(Csi- fs) = min =7,边叫)，f,2= C?，故 V?得不到标记。Vs成为

4、已检查过的点。(3 )取己标记而未检查的点V，检查V，在边(VJ上，以E3Z/luT0-/us 1 4 2 3 t， I :修改后如下图(2,2)V%修改后该链为饱和链，继续标号查视Vs标记Vs一标号+ OO已不存在由Vs到、的增流链。故可以判断该网络流不是最大流，已标记的顶点集合为y -，未标记的顶点集合V v乂乂，V ,v/?故有K （V,V） = i （V,V） , （V,V）是该网络的最小截集。I = iVi 2 3 4 ，i，is is2。久 匚I lij _t|x/J 旧un。2、（ 10分）若如上所示的网络图，已知各弧的单位流量费用为bj，现要在已知最大流的基础上求最小费用流，试

5、简述其方法。（不用计算结果）解析：这道简答题考查的是最小费用流的算法过程，题目比较简单，在课本中给出了详细步骤。解：（1）针对已知最大流为7的网络图G,构建伴随网络流f的增流网络Gf（2）针对增流网络G”查看是否存在基于W的负回路；若不存在，说明当前网络流已经 TOC o 1-5 h z 是最小费用流，算法终止，否则转到（3）。（3） 针对存在的负回路C，令=min?c （e） ,e为Gf中负回路的边（4）针对负回路C对应的运输网络G中的圈，判断该圈是否为增流圈；若不是，转到（2）继续寻找负回路，否则转（5）。（5）针对运输网络G中的增流圈，把增流圈中方向与负回路方向一致的所有不饱和边的流量加

6、上；把增流圈中方向与负回路方向相反的所有正边的流量减去。（6） 继续寻找负回路，若有负回路，继续调整，否则转（1）。三、证明题（10分，共1小题）（答在试卷上的内容无效）试用对偶理论证明下列线性规划模型为无界解。maxZ = 3 为 4x2 x3-X| 2x2 3x3 三 6st+x2 4x3 兰 7KM 0解析：对偶问题的基本性质中弱对偶性是常考的证明题，这里考查的是弱对偶性里的推论3:若原问题可行，而对偶问题不可行，则原问题的目标函数值无界。解：令 =x2 =x3 =0，满足约束条件，可知原问题可行。该问题的对偶问题为min w =6% 7y2% 3 y?二 32% +y2 3 4st3*

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

8、题很明显是一道考查0-1规划的投资问题建模题，一般的思路是，针对第j个项目，只有投资和不投资两种状态，所以可以用0-1变量X来描述这两种状态：*=1表示投资第j个项目，*=0表示不投资。但在现实的投资问题中会有许多特殊要求，像排斥问题、优先级问题、不可缺问题等，而这些需要通过约束条件方程来表述。0-1规划问题模型的解1第i个项目被投资0第i个项目不被投法采用隐枚举法。P167解：引入 0-1 变量 x (i =A,B,C,D,E)，设 Xj =max z = 100 xa 80 冷 70Xc60XD 90 xe 60 xa +40 xb +20 xc +40 xd +50 xe 兰 1500

9、XA +XC +XE =1 stXB+XD 兰 1Xc 兰 XDx =0 或 1五、计算题（85分，共5小题）（答在试卷上的内容无效）1、（ 15分）用两阶段法求下列线性规划模型的最优解。min z =2x 3x2fl 1/XAx220% 十 X2 = 10Xi，X2-0解析：题目中已经明确给出了用两阶段法来求解线性规划模型，所以这道题就只能用此方法来解答， 考查的就是基础的两阶段法，往年没有考过，考生往往也就疏忽了对基础知识的复习，做起来就比较生 疏，而且中间不小心算错了，后面的都白算，因此应该重视基础知识的复习以及加强计算能力。解：将模型化为如下形式，其中X3为松弛变量，X4为多余变量，X

10、5, x6为人工变量1x. x=44 2 3stXj3x? X4+X5= 20 为 +x2 +x6 =10 Xj-0(j =123,4,5,6)CB第一阶段的初始单纯性表如下:CjT000011CBXBb0X31X51X6ZjCj z0X341/21/410001X520130-1101X10110001Zj240-111CjZj-2-40100表中检验数表明未达到最优解，把X2作为换入变量，CjT00CBX BbXiX2X5作为换出变量，得到如下单纯形表：001XXX只3451X60X37/35/12011/12-1/1200X220/31/310-1/31/301X10/32/3001/3

11、-1/31Zj2/3001/3-1/31Cj-Zj表中检验数表明还未达到最优解，表-2/3把X00-1/31作为换入变量，X6作为换出变量，4/3得到如下单纯形0：CjT000011cBXBbX1X2X3X4X5X60X31/4001-1/81/8-5/80X25010-1/21/2-1/20X151001/2-1/23/2Zj0000o0Cj-Zj000011由上表可知，非基变量检验数全部0,已达到最优解，且基变量中不含有人工变量，所以转入第二阶段：恢复原来的目标函数，继续用单纯形法求解。改变后如下表：CjT2300CBXBbXIX2X3X40X31/4001-1/83X25010-1/22

12、*51001/2Zj000-1/2Cj _召0001/2由检验数可知，上表已达到最优解，求出的最优解为1（为*飞3飞4飞5羌）=（5,5, 一，0,0,0），目标函数值为z=2 5 3 5 = 25。42、（ 25分）考虑如下线性规划问题max z = -5*5X213X3+x2+3x3 兰 20stt?12x4x2+10 x3 兰 90*02,3）分别对两个约束条件引入松弛变量X4,x5,用单纯形法得到如下最优单纯形表。Cj-551300CBXBbXIX2X3X4x5X2X52010:03-40CT00-2-50不用重新求解，分别分析如下问题。(1)约束条件的右边常数变为= Ib2 20 1

13、 (2)使最优解不变的C 2的变化范围；Xg r-21对应的系数变为a, = 0，模型的解会有什么变化？J21-.5-(4)增加一个新的约束条件2xX25X3- 50,模型的解会有什么变化？解析：这是一道综合计算题，既考查了对偶单纯形法的应用又考查了灵敏度分析的计算，这是每年必考的计算题之一，虽然变化的类型不算多，但灵活性比较高，需要自己总结归纳，解：(1) Bd101101;，代入单纯形表 1 04 14 1 一2熟练掌握。Cj-551300CBXBbX1X2X3X4X55X210-113100X5-20160-2-41aj00-2-5025x5为换出变量，V，-2-4故X3为换入变量，得新

14、的单纯形表Cj-551300cBXBbX1X2X3X4X55X2-202310-53/213X310-8012-1/2aj-160X2为换出变量，X4为换入变量，得新的单纯形法如下：0-1-1一 20 得：Cj-551300CBXBbX2X3X4X5:X4X34-23/56/5-1/52/500-3/101/10a-103/5-1/500-13/10此时，所有的非基变量检验数均小于0,达到最优解，最优解为(为必氏必风)=(0,0,2,4,0)，目标函数最优值为z = 26(2)X2为基变量，故maXX-2/3),(-5/1)A .：即-2/3心乞0cA minb/(1*那么c2值得允许变化范围

15、就是13/3,5】。(3)|-01-4PT*5:; i - ci CB P| = -200 5所以最优解不会发生变化。(4)增加一个新的约束条件2X1 X2 5XA 50，引入松弛变量X6化为2X1 X2 5X3 XA = 50 ,其中X6 -0，把X6作为基变量，然后把这个方程的系数补加到题目中给出单纯形表的最后一行中，得下表Cj-5513000CBXBbX1X2X3X4X5X65X220-1131000X510160-2-4100X650215001进行初等变换，使基变量的系数矩阵变为单位矩阵，如下表:Cj-5513000CBXBbX1X2X3X4X5X65X220-1131000X510

16、160-2-4100X630302-10100-2-500表满足最优检验，基变量也可行，得到最优解G卷，X2,X3,X4,X5,X6）=（0,20,0,0,10,30），模型的解不变。3、（ 10分）六个城市G （仁i乞6）间航空票价q （表示g与C.间票价，单位：100元）见F表（：表示无直接航线），现在要设计出任何两城市间票价最廉的路线方案。请建立模型,并以C i与其他城市间方案为例作具体说明。0 500040251001520oQ250102000(Cij)6 601025055解析：从题目给出的矩阵可以联想到图与网络中介绍的无向图，所以这个问题考查的是图与网络的最短路问题，转化成无向图

17、即建立了最短路的模型。P226解：（1）用图表示出来题目中矩阵即建立了任何两城市间票价路线方案模型，如下图也可以建立如下的网络模型图:由上表可知Ci到C2的最短径路是：Gr J C?费用3500Ci到 C3的最短径路是：GrC6rC4rC 或 G r C5 r C4Q3 或 G C5 r C费用4500。Ci到C4的最短径路是：G r C5 r C4或G r CA - C4费用3500。q到C5的最短径路是：G rC5费用2500元q到C6的最短径路是：G rC6费用1000元4、（20分）有某物资从A|5A25Aj处运往BB2E3三个地方，各处供应量、需求量（单位：t）及单位运价（单位：10

18、元/t）见下表。、销地产地BiB2B3产量a59215A31711a62820销量181216判断以下给出的方案可否作为初始可行解（说明判断依据）？并求物资最优调运方案及其最小总费用。销地产地B1B2B3a312A211a1514解析：这道题考查的是运输问题的基本定理和表上作业法求产销平衡运输问题的最优值算法，难度不大，还可以考查产销不平衡或产销量不确定等条件的运输问题来增加难度，运输问题是每年必考的计算题之一，应予以重视。解：（1）题目给出的方案不可以作为初始可行解，虽然产销平衡，但是根据定理：m+n-1个变量构成基本可行解的充要条件是它不含闭回路。而给出的方案中基变量个数为6个，而且Xn，

19、Xi3，X33, X31可以构成一个闭回路，故不可作为初始可行解。（2）构造综合表，在综合表的最右边补一列，在最下面补一行，然后分别计算差值并填入表中，如下 表：、销地 产地BiB2B3产量差值AiXiix2x13153A2x21x22x23112A3X31X32X33204销量181216送=46差值215在上表中，最大差值5来自第二歹U,在第二歹U中没有被标识的变量所对应的最小运价是C13 = 2,在这里选择变量X!3作为基变量。X3=15,并将取值画上圈，处理后的综合表如下:肖地产地B1B2XXA2x21x22A3x31x32销量1812差值21B3产量差值2153x23112x3320

20、416Z=465对上表重新计算差值，按照上述方法找出基变量，处理后的综合表如下:、销地 产地BiB2B3产量差值AXX2150A2x21Xx23112A3X312X33204销量181216送=46差值311重复上述步骤，处理后的综合表如下:、销地产地BiB2AiXXA23XA 3x312销量1812差值30B3产量差值2150X114x3320216Z=461重复上述步骤，处理后的综合表如下:、销地 产地BiB2B3产量差值AiXX2150A23XX110A3628200销量181216送=46差值000在上表中，X13 , X2” X31 , X32氐3为基变量，因此有如下方程式组:U1

21、V3 = Ci3 = 2U2 V|_ c/ 3U3V1 - C31 =6U3 V2 - C32= 23 v3 = C33 = 8令比二0,按照位势法写入表中，得下表:、销地产地-4B2产量、。、1XX153A23XX116A320销量181216送=46计算出所有非基变量的检验数，并将求出的检验数填到综合表中对应的非基变量xij的位置,如下表：、销地产地、0Bi-4B22B3产量0A1559132*15153A23*1272116A36*21*28*20销量181216送=46表中没有负检验数，说明已经是最优解，即（心必厂乂彳厂乂彳？，X33）=（15,11,7,12,1）调运方案为从A1运到B3 15吨，从A2运到B11吨，从A3运到B1 7吨，从A3运到B? 12吨，从A3运到 B31 吨。则目标函数值z=（2