武汉科技大学824交通运输系统工程2015--2017(都有答案)考研真题+答案

　 姓 名 ：

　 报 考 专 业 ：

　 准 考 证 号 码 ：

　密 封 线 内 不 要 写 题

　5 2015 年攻读硕士学位研究生入学考试试题

　科目名称：交通运输系统工程（■A 卷□B 卷）科目代码：824 考试时间：3 小时

　 满分 150

　分 可使用的常用工具：□无

　√计算器

　√直尺

　□圆规（请在使用工具前打√）

　注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。

　一、用单纯形法求解下列线性规划问题（25 分）

　     0 , ,15 2 210.3 2 ) (3 2 12 13 2 13 2 1x x xx xx x xt sx x x S MAX

　二、有甲、乙、丙 3 位工人要完成 4 项（A、B、C、D）任务，每人可完成一项或两项任务，已知每个工人完成每项任务的费用矩阵如下所示，求总费用最小的任务方案。（30分）

　13 16 14 915 14 4 104 13 15 2 C 三、某镇有 6 个村庄，村庄之间的距离如下表所示，现欲修建乡村公路实现各村互通，问如何规划道路，既保证各村相通，又保证道路总里程最短。（20 分）

　V V 1 1

　 V V 2 2

　 V V 3 3

　 V V 4 4

　 V V 5 5

　 V V 6 6

　 V V 1 1

　 0 4 6 11 6 5 V V 2 2

　 4 0 7 7 7 7 V V 3 3

　 6 7 0 6 6 6 V V 4 4

　 11 7 6 0 8 9 V V 5 5

　 6 7 6 8 0 5 V V 6 6

　 5 7 6 9 5 0 四、某城市有 7 个公交线路首末站，各首末站的位置如下图所示。某点上的数字为该首末站线路上运行的公交车数量，边上数字表示该边所连首末站间的距离。现需设一个公交检修站，对公交车进行检修。试问检修站建在哪一个首末站时，可以使得运行车辆到检修站的总行驶路程最短。（30 分）

　3 2 64 1.52.52318V 1 (30)V 2 (40)V 3 (15) V 4 (20)V 5 (20)V 6 (25) V 7 (35) 五、某汽车加油站只有一台加油设备，汽车到达服从泊松分布，平均每 10min 到达一辆车；加油站给汽车加油时间为6min，加油时间服从负指数分布。试求：（20 分）

　(1) 加油站中没有车辆排队的概率；

　(2)加油站有 3 辆汽车的概率；

　(3)平均排队长度；

　(4) 车辆的平均排队时间。

　标准答案 ——A A 卷

　一、 解：

　标准化及加入人工变量后形式如下 5 3 2 13 2 max Mx x x x s           0 , , , , ,15 2 210.6 5 4 3 2 16 2 15 4 3 2 1x x x x x xx x xx x x x xt s 六、如下图所示的网络图，v s 表示火车站，v t 表示机场，求火车站到机场的网络最大流，每弧旁的数字是（c ij ，f ij ）。（25 分）。

　v 1(1,1)(4,4)(3,2)(10,4)(4,2)(3,2)(5,3)(4,4)(2,2)(7,7)(8,3)(3,2)v sv tv 4v 3 v 2v 5

　 用单纯形表求解如下

　0 14   且 0 ) 0 , 1 (4   P

　所以原线性规划问题解无界。

　二、解：

　3 位工人，4 项任务，人数少于任务数，虚拟一个人，其费用ijC =0，得效率矩阵如下：

　0 0 0 013 16 14 915 14 4 104 13 15 2ijC ijC 经行列变换， 0 ] 0 [ 0 04 7 5 011 10 ] 0 [ 62 11 13 ] 0 [1ijC 未找到位不同行不同列的 4 个零元素，对效率矩阵进行调整，调整量得 Q=2，调整后如下 0 ] 0 [ 2 22 5 5 ] 0 [9 8 ] 0 [ 6] 0 [ 9 13 02ijC 已经找到满足条件的位于不同行不同列的 4 个零元素，得分配矩阵如下：

　 0 1 0 01 0 0 10 0 1 01 0 0 02ijC 甲→A;乙→B;丙→C;丁→D。

　由此可知，C 由虚拟人完成，重新分配 C，此时转化为人数，对任务数进行二次分配。构建效率矩阵如下：

　0 0 160 0 140 0 13ijC

　经过指派后，C 由甲完成。

　 由 此可知，最终经过二次指派后，甲完成 C、D 工作，乙完成 B，丙完成 A。

　总费用 S=13+4+4+9=30 三、解：

　以6 2 1, , , V V V   6 个村庄为顶点，村庄与村庄之间的线路为边，构成含 6 个顶点的最小树图。6 个顶点须 6-1=5 条边。

　 采用避圈法求解，总里程 S=4+5+5+6+6=26 但路网可以不同。比如:V 1 →V 2 ，V 1 →V 6 ，V 5 →V 6 ，V 1 →V 3 ，V 3 →V 4 . 或 V 1 →V 2 ，V 1 →V 6 ，V 5 →V 6 ，V 3 →V 5 ，V 3 →V 4 . 或 V 1 →V 2 ，V 1 →V 6 ，V 5 →V 6 ，V 6 →V 3 ，V 3 →V 4 . 四、 解：

　先计算7 2 , 1, V V V   任意两点间的最短路权。

　（1）由距离矩阵法计算任意两点间的最短路权。初始距离矩阵如下：

　0 1.51.5 0 4 2.54 0 3 2 183 0 6 02 6 0 22.5 18 2 0 33 0                0D 迭代后最终距离矩阵为：

　 0 5 . 1 5 . 5 5 . 8 6 4 75 . 1 0 4 7 5 . 4 5 . 2 5 . 55 . 5 4 0 3 2 4 75 . 8 7 3 0 5 7 106 5 . 4 2 5 0 2 54 5 . 2 4 7 2 0 37 5 . 5 7 10 5 3 0 D （2）计算各顶点作为维修站的公交运行的总里程 S(V i ) ijvjj id V q V S * ) ( ) (1

　i=1,2,  7 S(V 1 )=917.5 S(V 2 )=542.5 S(V 3 )=692.5 S(V 4 )=1187.5 S(V 5 )=1152.5 S(V 6 )=605 S(V 7 )=697.5 (3)求 V k 。使 S(V k )=min{S（V k ）}，V k =V 2 =542.5，所以维修站建立在 V 2 处。

　五、解：

　该系统为 M/M/1/  /  模型， 6   辆/小时， 10   量/小时，  =3/5＜1 （1）

　24 . 0256) 1 (1      

　（2）

　039 . 0137554) )53( *52( ) 1 (3 33       

　（3）

　9 . 012 qL 辆 （4）

　15 . 0  qW 小时 六、解：

　（1）标号法找增广链，找到一条增广链：V s →V 2 →V 3 →V t ，调整量为 Q=2 调整后得：

　 v 1(1,1)(4,4)(3,2)(10,6)(4,4)(3,2)(5,3)(4,4)(2,2)(7,7)(8,5)(3,2)v sv tv 4v 3 v 2v 5 （2）对上图继续寻找增广链，找到 V s →V 5 →V 3 →V t ，增广链调整量 Q=1 调整后为：

　v 1(1,1)(4,4)(3,3)(10,6)(4,4)(3,2)(5,4)(4,4)(2,2)(7,7)(8,6)(3,2)v sv tv 4v 3 v 2v 5 （3）对上图继续找增广链，找到 V s →V 2 →V 5 →V 3 →V t ，调整量为 Q=1 调整得：

　v 1(1,1)(4,4)(3,3)(10,7)(4,4)(3,3)(5,5)(4,4)(2,2)(7,7)(8,7)(3,2)v sv tv 4v 3 v 2v 5 （4）上图无法找到增广链，该网络对应的最大流即为所求 f=7+7=14。

　所以火车站到机场网络的最大流为 14。

　 姓 名 ：

　 报 考 专 业 ：

　 准 考 证 号 码 ：

　密 封 线 内 不 要 写 题

　6 2016 年攻读硕士学位研究生入学考试试题

　科目名称：交通运输系统工程（□A 卷☑B 卷）科目代码：824 考试时间：3 小时

　 满分 150 分 可使用的常用工具：□无

　☑ 计算器

　☑ 直尺

　□圆规（请在使用工具前打√）

　注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。

　一、简答题(共 3 小题，每小题 10 分，共 30 分) 1. （10 分）满足生灭过程的条件是什么？ 2. （10 分）简述求解整数规划的割平面法的基本思路。

　3. （10 分）某公司要从 A 1 ，A 2 ，……A 10 十个可供选择的投资项目中确定 5 个投资对象，使总投资额最小。假设十个项目的投资额分别是c 1 ，c 2 ，……，c 10 ，且在项目的选择上要满足下列限制条件：

　（1）选择了 A 1 或 A 2 就不能选择 A 4 ，反之亦然； （2）在 A 5 ，A 6 ，A 7 ，A 8 中最多只能选择 3 个。

　试写出上述问题的模型。

　二、（20 分）用单纯形法求解下列线性规划问题。

　       0 , ,0 22 26.2 2 ) (3 2 13 23 13 2 13 2 1x x xx xx xx x xt sx x x S MAX

　三、（30 分）某货物有甲、乙、丙三个产地，A、B、C、D 四个区域需要该货物。由于各区域与三产地间的距离不同、对该货物的需求也不同，该货物由产地销往四个区域获得的利润也不同，已知该货物三个产地的产量、四个区域的需求量以及该货物由产地销往需求各区域的利润（元/件）如下表所示。试帮助该货物确定一个盈利最大的销售方案。

　A B C D 产量（件）

　甲 10 5 6 7 2500 乙 8 2 7 6 2500 丙 9 3 4 8 5000 需求量（件）

　1500 2000 3000 3500

　 四、（20 分）甲、乙、丙、丁、戊五名工人的各项技能得分如下表所示，现从这 5 人中挑选 4 人去参加各项技能的单项大赛，竞赛同时举行，每人最多只能参加一项，若以他们的技能得分作为选派依据，应如何分配最有利？

　 A B C D 甲 90 92 68 80 乙 80 88 65 78 丙 95 89 85 72 丁 75 78 89 96 戊 70 80 90 92

　五、（20 分）如下图所示，Vs 是某货物的生产地，其他点是该货物的需求地，弧上的数字表示运费（运费参照其计划运费，大于计划成本取值为正，小于计划成本取值为负），现需将货物从 Vs 运送到其他各点，试问该如何走，才能保证 Vs 到其他点的运输费用最少。

　 六、（30 分）一个停车场只有一个进口，假设到达停车场的进口的车辆数为泊松流，平均每小时 30 辆，进口发卡工作人员的服务时间服从负指数分布，平均每小时可服务 45 辆。

　（1）

　计算这个排队系统的评价指标 P 0 ，L q ，L s ，W q ，W s ；

　B 卷参考答案

　 一、简答题0 (30 分) )

　1．（10 分）

　答：系统具有 0，1，2，……个状态。在任一时刻，若系统处于状态 i， ①在（t,t+Δt）内系统由状态 i 转移到状态 i+1 的概率为 λ i Δt+O(Δt)； ②在（t,t+Δt）内系统由状态 i 转移到状态 i-1 的概率为 μ i Δt+O(Δt)； ③在（t,t+Δt）内系统发生两次以上转移的概率为 O(Δt)。

　2.（10 分）

　答：首先不考虑变量是整数这一条件，通过增加线性约束条件（割平面）使得原可行域被切掉一部分，这部分只包含非整数解，但没有割掉任何整数可行解，最终可行域的整数顶点恰好是原问题的最优解。

　3. （10 分）解：设 （2）

　顾客对这个排队系统抱怨花费时间太多，停车场为改进服务，准备以下两种方案供选择：

　a)将进口处人工发卡改为车牌自动识别，这样可以使每小时的服务率从 45 辆提高到 60 辆。

　b)增加一个进口，每个进口每小时的服务率仍为 45 辆。

　请对这两个方案进行评价，并作出选择。

　 为投资项目 ，不确定 0为投资项目 确定 , 1iiAAx i

　      10 ， 2 , 1 i ， 0 或 1311.) ( in8 7 6 54 34 210iii ixx x x xx xx xt sx c S M 二、（0 20 分）

　解：将线性规划问题化为标准型，并引入人工变量为：

　                   0 , , , , , , , ,0 22 26.0 0 0 2 2 ) (9 8 7 6 5 4 3 2 19 8 3 27 6 3 15 4 3 2 19 8 7 6 5 4 3 2 1x x x x x x x x xx x x xx x x xx x x x xt sMx x Mx x Mx x x x x S MAX 用单纯形表求解过程为：

　C j

　X j

　X B

　2 -1 2 0 -M 0 -M 0 -M

　ib

　 i

　x 1

　x 2

　x 3

　x 4

　x 5

　x 6

　x 7

　x 8

　x 9

　-M x 5

　1 1 1 -1 1 0 0 0 0 6 6 -M x 7

　-2 0 1 0 0 -1 1 0 0 2 - -M x 9

　0 [2] -1 0 0 0 0 -1 1 0 0 j j jZ C    M  2

　1 3  M 2+M -M 0 -M 0 -M 0 -8M -M x 5

　1 0 3/2 -1 1 0 0 1/2 -1/2 6 4 -M x 7

　-2 0 [1] 0 0 -1 1 0 0 2 2 -1 x 2

　0 1 -1/2 0 0 0 0 -1/2 1/2 0 - j j jZ C    M  2

　0 2325M -M 0 -M 0 212M 2321 M -8M -M x 5

　[4] 0 0 -1 1 3/2 -3/2 1/2 -1/2 3 3/4 2 x 3

　-2 0 1 0 0 -1 1 0 0 2 - -1 x 2

　-1 1 0 0 0 -1/2 1/2 -1/2 1/2 1 -

　 j j jZ C   

　5 4  M

　0 0 -M 0 2323M 2325 M 212M 2321 M -3M+3 2 x 1

　1 0 0 -1/4 1/4 3/8 -3/8 1/8 -1/8 3/4

　2 x 3

　0 0 1 -1/2 1/2 -1/4 1/4 1/4 -1/4 7/2

　-1 x 2

　0 1 0 -1/4 1/4 -1/8 1/8 -3/8 3/8 7/4

　j j jZ C    0 0 0 5/4 45  M -3/8 M 83 -9/8 M 89

　由单纯形表的计算结果可以看出， 04  ，且 ) 3 , 2 , 1 ( 04  i a i ，所以该线性规划问题有无解界。

　三、（0 30 分）

　解：用利润表中最大值 10 减去利润表上的数字，使之成为一个运输问题，如表 1 所示。

　表 1

　A B C D 产量（件）

　甲 0 5 3 3 2500 乙 2 8 3 4 2500 丙 1 7 6 2 5000 需求量 1500 2000 3000 3500

　用最小元素法求初始解（表 2）：

　表 2

　A B C D 产量（件）

　甲 1500 500 500

　2500 乙

　 2500

　2500 丙

　1500

　3500 5000 需求量 1500 2000 3000 3500

　用位势法求空格检验数为（表 3）：

　表 3

　A B C D U i

　甲

　3 0 乙 3 4

　5 -1 丙 -1

　0

　2 V j

　0 5 4 0

　表 3 中还有非基变量的检验数小于 0，利用闭回路法进行调整，把（丙，A）格作为进基变量，以此格为出发点，作闭回路，调整量为 1500，调整后的方案为表 4（注意，表中 0 值可在（甲，A）也可在（丙，B），后面计算检验数要与之对应。）

　表 4

　A B C D 产量（件）

　甲

　2000 500

　2500 乙

　 2500

　2500 丙 1500 0

　3500 5000 需求量 1500 2000 3000 3500

　用位势法求空格检验数（表 5）。

　表 5

　A B C D U i

　甲 1

　 3 0 乙 1 1

　2 2 丙

　 3

　2 V j

　-1 5 1 0

　所有非基变量的检验数均为非负，故表 4 的解即为最优解。

　此调运方案下，可获利 1500×9+2000×5+0×3+500×6+2500×7+3500×8=72000 元。

　四、（0 20 分）

　解：先虚拟一项技能，每个人完成该项技能的得分为 M(M 可取 100 分，或者表中最高分 96 分)，然后用表中最大数减去表中各数，将其转化为标准的指派问题，用匈牙利法求解。

　令 M=96 分，得到初始效率矩阵为：

　96 92 90 80 7096 96 89 78 7596 72 85 89 9596 78 65 88 8096 80 68 92 90ijc

　0 4 6 16 260 0 7 18 210 24 11 7 10 18 31 8 160 16 28 4 696  ijc

　进行行例变换，进行第一次指派得0 4 ] 0 [ 12 250 ] 0 [ 1 14 200 24 5 3 ] 0 [] 0 [ 18 25 4 150 16 22 ] 0 [ 51ijc

　由以上指派知，已经找到 5 个独立的 0 元素，已得最优方案。即

　 0 0 1 0 00 1 0 0 00 0 0 0 11 0 0 0 00 0 0 1 0ijx ，甲参加 B，丙参加 A，丁参加 D，戊参加 C，乙不参加。

　五、（0 20 分）

　解：本题为求某点到其他各点的最短路，图中具有负权的弧，标号法失效，可用逐次逼近算法或距离矩阵法计算。

　以逐次逼近算法为例：

　令 ) 5 , 4 , 3 , 2 , 1 , ( ,1s j Psj sj  

　用   ) 5 , 4 , 3 , 2 , 1 ; 5 , 4 , 3 , 2 , 1 , ( min1   j s i P PijtsitSJ 进行迭代计算， 当1 tsjtsjP P ，停止迭代，tsjP 即为所求。本题计算过程如下表所示：

　sj

　tsjP

　v s

　v 1

　v 2

　v 3

　v 4

　v 5

　t=1 t=2 t=3 t=4 v s

　0 1 ∞ 2 ∞ ∞ 0 0 0 0 v 1

　∞ 0 3 4 ∞ ∞ 1 1 1 1 v 2

　∞ -2 0 5 2 ∞ ∞ 4 1 1 v 3

　∞ 4 ∞ 0 -3 ∞ 2 2 2 2 v 4

　∞ ∞ 2 3 0 ∞ ∞ -1 -1 -1 v 5

　∞ ∞ 2 ∞ 2 0 ∞ ∞ ∞ ∞ 由上表可知，Vs→V 1 的运费为 1，Vs→V 2 的运费为 1，Vs→V 3 的运费为 2，Vs→V 4 的运费为-1，Vs→V 5 不可达。

　六、（0 30 分）

　（1）解：该系统为 M/M/1/∞/∞模型 h / 辆 5 4 ， h / 辆 30     ， （1）315 40 31 1 10       P

　) 辆 ( 21530  sL

　（辆）345 40 32     s qL L

　 ) (5 11 1h W s   ) (5 425 415 11 1h W Ws q     (2)解：a 方案，仍为 M/M/1/∞/∞, h / 辆 60 ， h / 辆 30    

　21600 31 1 10       P

　) 辆 ( 13030  sL

　（辆）21600 31     s qL L

　) (301 1h W s   ) (601601301 1h W Ws q     b 方案是 M/M/2/∞/∞模型，319030, / 辆 5 4 ， h / 辆 30       sh

　2912)4345301 ( ] ) () 1 ( !1) (!1[1 1100     SnSnS nP  ) 辆 (872] )311 ( ! 2 [ ]291231)312 [() 1 ( !) (2 220       SP SLSq ) 辆 (29204530872    q sL L

　比较两个方案的 L q ，L s 可知，方案 b 由于方案 a，故应增加一个进口。

　 姓 名 ：

　 报 考 专 业 ：

　 准 考 证 号 码 ：

　密 封 线 内 不 要 写 题

　7 2017 年全国硕士研究生招生考试初试自命题试题

　科目名称：交通运输系统工程（□A 卷 ☑B 卷）科目代码：824 考试时间：3 小时

　 满分 150 分 可使用的常用工具：□无

　 ☑ 计算器

　☑ 直尺

　□圆规（请在使用工具前打√）

　注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。

　 一、（5 25 分）填空与简答

　1. （5 5 分）已知标准的 M/M/3 排队服务系统，平均每分钟到达的顾客数为 0.9人，每位顾客的平均服务时间为 2min，则系统的服务强度为

　。

　2. （5 5 分）图（b）是图（a）的

　。

　3. （5 5 分）单纯形法求解线性规划问题时，若在所有大于零的j 中，存在一个k 对应的kx 的系数列向kp ≤0，则此线性规划问题的解的情况为：

　 。

　4 4. . （0 10 分）针对整数规划问题及它的松弛问题，简述二者最优解间的关系。

　二、 （0 30 分）已知求某目标函数极大化的线性规划问题的初始单纯形表如下所示，请回答以下问题：

　C j

　C B

　 X j

　 X B

　10 15 12 0 0 0 -M

　ib

　 i

　X 1

　X 2

　X 3

　X 4

　X 5

　X 6

　X 7

　0 x 4

　5 3 1 1 0 0 0 9

　0 x 5

　-5 6 15 0 1 0 0 15

　-M x 7

　2 1 1 0 0 -1 1 5

　j j jZ C   

　 1. （5 5 分）写出与上述单纯形表相对应的标准式的线性规划模型。

　2. （5 5 分）计算表中各检验数的值。

　 3. （0 20 分）根据初始单纯形表，求解与之相对应的线性规划问题的最优解。

　三、 （0 20 分）已知运输问题的产销平衡表和单位运价表如下：

　A B C D 产量 甲 12 6 15 4 10 乙 10 5 12 2 25 丙 6 14 10 5 5 销量 6 10 12 12

　要求用最小元素法求运输问题的初始解，并求最优解。

　 四、（5 25 分）某运输队有五辆汽车，准备驶往三个目的地送货。一地的货物只需一辆汽车运送，其运输利润如下表所示：

　汽车 目的地 1 2 3 4 5 A 10? 12 14 11 13 B 13 20 23 15 21 C 8 6 10 7 5 0 1.(20 分) )求最优调运方案。

　5 2.(5 分) )若车 2 载不下目的地 A 所需货物，则对最优解有何影响？

　 五、（0 30 分）已知下图所示的公路交通网络，图中弧上第一个数据为路段上的最大通行能力，第二个数据为给出的流量，Vs，Vt 分别为始点和终点。

　1.(5 25 分) )试求该网络最大流； 2.(5 5 分) )指出此交通网络的瓶颈路段，并提出可以提高路网交通流量的方法。

　 、 六、 （0 20 分）画出排队系统 M/M/1/3/∞/FCFS，λ=2，μ=4 的状态转移图，并求解系统状态概率 P 0 ，系统运行指标 L S 。

　 B 卷参考答案

　一、填空与简答 (25 分) 1. （5 分）0.6 2. （5 分）真子图 3. （5 分）无解 4. （10 分）答：设有极大化的整数规划问题 A，其相应的松弛问题为 B。则二者最优解的关系为：①若 B 无解，则 A 无解； ②若 B 有最优解且满足 A 的整数约束条件，则 B 的最优解即为 A 的最优解；③若 B 有最优解，但不满足 A 整数约束，则 B 的最优解一定是 A 的最优解的一个上限。

　二、（30 分）

　解：1. （5 分）与初始单纯形表对应的线性规划问题的标准形为：

　                 0 , , , , , ,5 215 15 6 59 3 5.0 0 0 12 15 10 ) (7 6 5 4 3 2 17 6 3 2 15 3 2 14 3 2 17 6 5 4 3 2 1x x x x x x xx x x x xx x x xx x x xt sMx x x x x x x S MAX 2. （5 分）计算的检验数见表 1 第 6 行与第 3、4、5 行最后一列。

　3. （20 分）解：与之相对性的线性规划问题的求解过程如表 1 所示 表 1

　C j

　C B

　 X j

　 X B

　10 15 12 0 0 0 -M

　ib

　 i

　X 1

　X 2

　X 3

　X 4

　X 5

　X 6

　X 7

　0 x 4

　[5] 3 1 1 0 0 0 9 9/5 0 x 5

　-5 6 15 0 1 0 0 15 - -M x 7

　2 1 1 0 0 -1 1 5 5/2 j j jZ C    10 2  M 15  M

　12  M

　0 0 M 

　0 -5M 10 x 1

　1 3/5 1/5 1/5 0 0 0 9/5 9 0 x 5

　0 9 [16] 1 1 0 0 24 3/2

　 -M x 7

　0 -1/5 3/5 -2/5 0 -1 1 7/5 7/3 j j jZ C    0 95 M 1053M 522M  0 M 

　0 5718M 10 x 1

　1 39/80 0 3/16 -1/80 0 0 3/2

　12 x 3

　0 9/16 1 1/16 1/16 0 0 3/2

　-M x 7

　0 -43/80 0 -7/16 -3/80 -1 1 1/2

　j j jZ C    0 8043827 M 0 167821 M  80385 M  -M 0

　由单纯形表可知，所有非基变量检验数 σj<0，且存在人工变量 x 7 =1/2，故原线性规划问题无可行解。

　三、（20 分）

　解：用最小元素法确定初始解见表 1 表 1

　A B C D 产量 甲

　 10

　10 乙 1 10 2 12 25 丙 5

　5 销量 6 10 12 12

　用位势法计算空格检验数见表 2 表 2

　A B C D U i

　甲 -1 -2

　-1 0 乙

　 -3 丙

　13 2 7 -7 V j

　13 8 15 5

　存在检验数<0 的情况，初始解不是最优解，用闭回路法进行调整。选择（甲-B）空格为进基变量，作闭回路，确定调整量为 10，调整后的方案见表 3。（注意，调整后（乙，B）或(甲，C)任选一个地方填入 0，后面计算检验数时应与此对应。）

　表 3

　A B C D 产量 甲

　10

　 10 乙 1 0 12 12 25 丙 5

　5 销量 6 10 12 12

　 计算空格检验数见表 4 表 4

　A B C D U i

　甲 1

　2 1 0 乙

　 -1 丙

　13 2 7 -5 V j

　11 6 13 3

　所有检验数均大于 0，表 3 对应的解即为最优解。

　即甲→B=10，乙→A=1，乙→C=12，乙→D=12，丙→A=5。

　四、（25 分）

　1 、（20 分）解：该问题为指派问题。

　首先虚拟 D、E 两个目的地，又求利润极大化，用效率矩阵中最大元素 23去减各数，同时车辆到虚拟目的地的利润为 0，得出标准的指派问题，效率矩阵如下：

　0 0 0 0 00 0 0 0 018 16 13 17 152 8 0 3 1010 12 9 11 13ijc ， 进行行列变换，使得各行各列至少有 1 个零元素得1ijc ， 在1ijc 中找独立零元素为：0 0 0 ] 0 [ 00 0 0 0 ] 0 [5 3 0 4 22 8 0 3 101 3 ] 0 [ 2 41ijc ，不足 5 个，对1ijc 进行调整后得2ijc ， 在2ijc 中找独立零元素数为：0 0 1 ] 0 [ 00 0 1 0 ] 0 [4 2 0 3 11 7 0 2 90 2 ] 0 [ 1 32ijc ，不足 5 个，调整后得3ijc ，在3ijc 中找独立零元素为：0 0 2 ] 0 [ 00 ] 0 [ 2 0 04 1 0 2 ] 0 [1 6 ] 0 [ 1 8] 0 [ 1 0 0 23ijc ，等于 5 个。

　 0 0 0 1 00 1 0 0 00 0 0 0 10 0 1 0 01 0 0 0 0ijx ，指派结果为：A→5，B→3，C→1，利润为：13+23+8=44 2. （5 分）解：因为最优方案中目的地 A 是由 5 号汽车装载，故无影响。

　五、（30 分）

　1. （25 分）解：

　判断是否为最大流：

　寻找增广链，并依次进行调整 ①V s →V 1 →V 5 →V 2 →V t ，调整量△=1 ②V s →V 5 →V 4 →V t 1 ③V s →V 3 →V 4 →V t ，调整量△=2 ④V s →V 3 →V 5 →V 4 →V t ，调整量△=1 此后再也找不到增广链，调整后的流量图为：

　由此可知给定的流不是最大流，调整后最大流为 V（f）=7+3+4=7+7=14 2. （5 分）解：网络最大流对应的交通瓶颈为（V s ，V 1 ）, （V s ，V 5 ）, （V 3 ，V 5 ）, （V 3 ，V 4 ），可提高对应路段的最大通行，以提高该路网的流量。

　六、（20 分）

　 解：状态转移图：

　（5 分）

　列出状态平衡方程：0 121P P  ,0 241P P  ,0 381P P  , 301iiiP (8 分) 解得 P 0 =0.533 （2 分）

　733 . 0 067 . 0 3 133 . 0 2 267 . 0 1 533 . 0 030           nn snP L （ （5 分）

　2 2 S 0

　S 1

　S 2

　S 3

　2 4 4 4