824交通运输系统工程-2015(A卷答案)

第1页共4页标准答案——A卷一、解：标准化及加入人工变量后形式如下532132maxMxxxxs0,,,,,152210.65432162154321xxxxxxxxxxxxxxts用单纯形表求解如下014且0)0,1(4P所以原线性规划问题解无界。二、解：3位工人，4项任务，人数少于任务数，虚拟一个人，其费用ijC=0，得效率矩阵如下：000013161491514410413152ijCijC经行列变换，第2页共4页0]0[0047501110]0[621113]0[1ijC未找到位不同行不同列的4个零元素，对效率矩阵进行调整，调整量得Q=2，调整后如下0]0[22255]0[98]0[6]0[91302ijC已经找到满足条件的位于不同行不同列的4个零元素，得分配矩阵如下：01001001001010002ijC甲→A;乙→B;丙→C;丁→D。由此可知，C由虚拟人完成，重新分配C，此时转化为人数，对任务数进行二次分配。构建效率矩阵如下：001600140013ijC经过指派后，C由甲完成。由此可知，最终经过二次指派后，甲完成C、D工作，乙完成B，丙完成A。总费用S=13+4+4+9=30三、解：以621,,,VVV6个村庄为顶点，村庄与村庄之间的线路为边，构成含6个顶点的最小树图。6个顶点须6-1=5条边。采用避圈法求解，总里程S=4+5+5+6+6=26但路网可以不同。比如:V1→V2，V1→V6，V5→V6，V1→V3，V3→V4.或V1→V2，V1→V6，V5→V6，V3→V5，V3→V4.或V1→V2，V1→V6，V5→V6，V6→V3，V3→V4.四、解：先计算72,1,VVV任意两点间的最短路权。（1）由距离矩阵法计算任意两点间的最短路权。初始距离矩阵如下：第3页共4页01.51.5042.5403218306026022.518203300D迭代后最终距离矩阵为：05.15.55.86475.10475.45.25.55.54032475.8730571065.42502545.24720375.5710530D（2）计算各顶点作为维修站的公交运行的总里程S(Vi)ijvjjidVqVS*)()(1i=1,2,7S(V1)=917.5S(V2)=542.5S(V3)=692.5S(V4)=1187.5S(V5)=1152.5S(V6)=605S(V7)=697.5(3)求Vk。使S(Vk)=min{S（Vk）}，Vk=V2=542.5，所以维修站建立在V2处。五、解：该系统为M/M/1//模型，6辆/小时，10量/小时，=3/5＜1（1）24.0256)1(1（2）039.0137554))53(*52()1(333（3）9.012qL辆（4）15.0qW小时六、解：（1）标号法找增广链，找到一条增广链：Vs→V2→V3→Vt，调整量为Q=2调整后得：第4页共4页v1(1,1)(4,4)(3,2)(10,6)(4,4)(3,2)(5,3)(4,4)(2,2)(7,7)(8,5)(3,2)vsvtv4v3v2v5（2）对上图继续寻找增广链，找到Vs→V5→V3→Vt，增广链调整量Q=1调整后为：v1(1,1)(4,4)(3,3)(10,6)(4,4)(3,2)(5,4)(4,4)(2,2)(7,7)(8,6)(3,2)vsvtv4v3v2v5（3）对上图继续找增广链，找到Vs→V2→V5→V3→Vt，调整量为Q=1调整得：v1(1,1)(4,4)(3,3)(10,7)(4,4)(3,3)(5,5)(4,4)(2,2)(7,7)(8,7)(3,2)vsvtv4v3v2v5（4）上图无法找到增广链，该网络对应的最大流即为所求f=7+7=14。所以火车站到机场网络的最大流为14。