1、全国自考物流数学（指派问题和旅行商问题、物资调运问题的图上作业法）模拟试卷 1 及答案与解析一、应用题1 求下面费用矩阵对应的旅行问题的最佳路径。2 有 4 台机器可同时加工 5 种零件，费用系数矩阵如表 611 所示，求费用最小的分派方案。3 一个公司要分派 4 个推销员去 4 个地区推销某种商品，4 个推销员各有不同的经验和能力，因而他们在每一地区能获得的利润不同，其估计值如表 612 所示。4 找出下列段道图(图 619 一图 621)的最优投递路线。(1)(2)(3)5 某公司想在下列 6 个可供选择的地点新建 5 个仓库，问应选择哪几个位置建仓库可使总费用最小? 在不同地点新建仓库的
2、费用由表 613 的数据给出(单位：干元)。6 求图 622 和图 623 两个段道图中的最优投递路线。(1)(2)7 设有服装产地 A1，A 2，A 3，A 4 及销地 B1，B 2，B 3，B 4，B 5。表 71 和表 72两表中的数据分别表示的是该服装厂各产地一年的产量和销量以及各产地和销地之间的距离。试画出这个实际问题的交通图。8 如图 711 所示交通图的物资调运问题(单位：吨)，试做出第一个流向图。9 如图 715 所示交通图，试作出第一个流向图。10 检查图 717 是否为最优流向图11 检查图 718 是否为最优，若不是最优，将其调整为最优。12 如图 722 所示的交通图，
3、求其最优流向图。13 图 728 所示流向图，试调整一次使之成为最优流向图。14 某汽车运输公司有许多载重量为 5 吨的卡车，某天该公司接受了表 75 所示的9 项运输业务。装卸点位置如图 730 所示的交通图(线上数字单位：km)。怎样安排卡车来完成这些运输业务才能够做到最节约?15 某运输公司接受了一项货运业务，如表 76 所示，收发货点的位置如图 733所示，求车辆最优调度方案。16 设有服装产地 A1，A 2，A 3，A 4 及销地 B1，B 2，B 3，B 4，B 5。表 77 和表78 中的数据分别表示的是该服装厂各产地一年的产量和销量以及各产地和销地之间的距离。试画出这个实际问题
4、的交通图。17 把图 735 按图上作业法的规定进行修改使之成为规范的流向图。18 检查图 736 是否为最优流向图。19 如图 737 所示的流向图，试调整一次使之成为最优流向图。20 设有 A，B，C ，D ，E 五人和五项任务， ，要求每一个人只能完成一项任务，一项任务也只能由一个人来完成，效益矩阵中相关数据如表61 所示。 请用表上作业法把这五项任务指派给这五个人，使所得效益最高。21 现有三个人甲、乙、丙去完成三项任务 I，要求每个人只完成一项任务，每项任务只能由一个人完成；三人完成各项任务的费用由表 64 给出。问怎样指派三人去完成三项任务，使总费用最少?22 有 A，B，C ，D
5、 四项任务分派给甲、乙、丙、丁四个人去做，这四个人都能承担上述四项任务，完成各项任务所需时间如矩阵 C1 所示。问如何分派任务才能使完成任务的总工时最小。23 求下列标准型分派问题的最优解。24 有 6 个仓库 I，和，需要 6 辆卡车 A，B，C ，D，E，F。卡车现在的位置与仓库之间的英里数已知(见表 65)，试确定每辆卡车应该开到哪个仓库去，使运行的总的里程为最少。25 现有三项任务 J1，J 2，J 3，并有三台机器 A，B，C 可用以去完成任务，要求每台机器只能完成一项任务，而每项任务只有一台机器完成。三台机器完成各项任务的费用如表 66 所示，请用列举法和匈牙利算法分别指派三台机器
6、去完成这项任务，可使费用最少。26 设 u1，u 2u3，u 4，u 5 各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。27 甲、乙、丙、丁四景点之间的距离表如下： 求从某一个景点出发遍历备景点各一次的最短路径。28 设有 4 件工作分派给 4 个人来做，每项工作只能由一个人来做，每个人只能做一项工作。表 67 为各人对各项工作所具有的工作效率，请适当安排人选，使总效率最大。29 求下列费用矩阵对应的旅行商问题的最佳路径。(1)(2)30 某设备公司有 3 台设备可以租给 A，B，C，D 四项工程使用，各设备用于各工程创造的利润如表 68 所示。问将哪一
7、台设备租给哪一项工程，才能使创造的总利润最大?31 图 61 中 A，B，C ， D，E，F 分别代表岛和陆地，它们之间有桥相连，问一个人能否经过图中的每座桥恰好一次既无重复也无遗漏?32 求图 63 所示的段道图的最优解。33 找出图 66 中段道图的最优投递路线。34 求图 69 所示段道路的最优化解。35 判定以下各图(图 613 一图 615)能否一笔画出。(1)(2) (3)36 某厂有 A，B，C 三台机器及三项作业 I， ，要求每台机器只完成一项作业，每项作业只由一台机器完成，三台机器完成各项作业的费用由表 69 给出。问怎样指派三台机器去完成这三项作业，可使费用最小?37 设有
8、 A，B，C 三个人去完成 I，三项任务，要求每一个人只能完成一项任务，每项任务只由一个人完成，效益矩阵中相关数据由表 610 给出。问怎样把三项任务分派给三个人，使所得效益最高?38 求下列价格矩阵对应的指派问题费用最小的最优解。39 已知 A，B，C ，D ，E 五项工作由 5 人张、王、赵、李、刘来完成， 5 人做 5 项工作时间如矩阵 M 所示，问如何指派，使 5 人花费总时间最少 ?40 求解下列矩阵的最小化分派问题。(1) (2)(3)全国自考物流数学（指派问题和旅行商问题、物资调运问题的图上作业法）模拟试卷 1 答案与解析一、应用题1 【正确答案】 利用匈牙利算法求解2 【正确答
9、案】 首先将费用系数矩阵转化为方阵，添加一台虚构的机器补成方阵，但是对应的费用全为 0。再采用匈牙利方法求最优解，在结果解中应解除虚设的圈。所以：即：E，D，C，A 此时，应选择费用最低的机器加工 B，即选择机器，加工 B，费用均为 6，故总费用为：2+2+4+2+6=163 【正确答案】 最优分配为： 总利润为：35+40+32+32=1394 【正确答案】 (1)见附图 21。 (2)见附图 22。(3)见附图 23。5 【正确答案】 引入一个虚拟的仓库：从而，答案为：A 一不用费用=0B 一 5 费用=8000 元 C 一 2 费用=10000 元 D 一 3 费用=10000 元 E
10、一 1 费用=14000 元 F 一 4 费用=20000 元总费用=62000 元6 【正确答案】 (1)见附图 24。 (2)见附图 25。7 【正确答案】 根据图上作业法规则，可画出例 1 中物资调运问题的交通图，如图71 所示。8 【正确答案】 图 711 中无圈，根据“取一端，它的供需归邻站” 来作第一个流向图。在图 711 中，A，H，L，E，M 五个点出发的弧只有一条，这样的点称为端点，而与这个端点相邻接的那个点称为该端点的邻站，比如，A 的邻站是 B 点，L的邻站是 G 点。先取一个端点，它若是出发点，就把其全部发量运往它的邻站，它若是收点，则由其邻站供应其全部收量。如取 A
11、点，它是发点，把 10 吨的物资全运往其邻站 B，B 点就共有 25 吨的物资往外运了，且以后就不必再考虑 A 点与弧 AB 了。再取 E 点，它是收点，收量是 9 吨，应该由其邻站 D 供应其全部需要。D 点是发点，将其全部的 9 吨物资运往 E 点，这时 E 的需求已全部满足，因此以后就不用考虑 E，D 及弧 ED 了。继续做，得图 712，得到的流线图不会有对流现象。9 【正确答案】 图 715 中有三个圈，先“甩弧破圈” 。先取上面的圈：A 1A2 一B1B2 一 A1，抹去最长的弧 A2B1，破掉这个圈。再取下面的大圈：A 3 一 A4 一 B4一 B2 一 B1B3 一 A3，抹去
12、最长弧 A3A4，破掉这个圈，剩下的就变成没有圈的图了。用口诀“ 取一端，它的供需归邻站 ”的方法作第一个流向图。如图 716 所示。这个流向图所示的调运方案的运输量为：2125+5100+5010+10239+6118+5292+2317+10252+10100+8110=1084210 【正确答案】 图 717 里有三个圈，先检查上边的小圈，小圈总长为：120+239+180+266=805 外圈有两个流向，总长为：未超过圈长的一半。内圈没有流向，因此这个小圈合乎基本定理的要求，今后称这样的圈为合格的。再检查第一个大圈(B 1 一 B2 一B4 一 A4 一 A3 一 B3 一 B1)，这
13、个圈的总长度为：165+180+118+317+349+252=1381这个大圈的外圈流向只有一个，长度为： 没超过这个大圈长的一半。内圈流向有三个，总长为：252+165+118=535 1 一 B2 一 B4 一 A4 一 A3B3 一B1 一 A2 一 A1)，这个圈的长度为：120+239+118+317+349+252+165+266=1826 其中有五个内圈流向，总长为： 没有超过这个圈长的一半。另外，只有一个外圈流向，长为 31711 【正确答案】 由于路线 9 已长于 2+3 和 4+4，路线 9 可以去掉，去掉该线后此流向图只有一个圈，圈长为 13。内圈流向总长度为 765。
14、因此，这个圈不合格，用外调整法：外圈各流向上加调整量 10；无流向的弧添上外圈流向，流量为 10；内圈各流向的流量减去 10，得到图 719。 图 719 中，内圈流向长 312 【正确答案】 用“ 甩弧破圈 ”的方法，作第一个流向图，如图 723 所示。其投影图如图 724 所示。要检查图 723 是否为最优流向图，检查其每一个“要检查的圈 ”是否都合格就可以了。因为其投影连通，恰好有 9 个点 8 条弧：再加上一条弧就能成一个圈了，这样的圈正是“要检查的圈” 。图 724 中有 4 条没有流向的弧：AD，BC，GH，HE。把 AD 加入图 723，在流向图中就有一个“要检查的图”4 一 B
15、EDA，圈长为 10，内圈流向长 38，不合格，调整。调整量为2，内圈流向均减 2，外圈流向均加 2，无流向的弧加入流量为 2 的外圈流向，如图725 所示。 图 725 中圈 DEFI-HG-D 仍然不合格，因为其内圈流向长 3+3+2+2=108 再调整，调整量为 1，内圈各流向均减 1，外圈各流向均加 1，无流向的弧加入流量为 1 的外圈流向，得图726。调整后得到这个圈的内圈流向长为 3+2+2=7外圈流向长为 3+3=613 【正确答案】 外圈流向的总长度为：4+5+3+3+2+5+3+1=26?圈总长为3+4+3+5+3+3+2+5+3+1=32 因为 2616，即外圈流向总长超过
16、圈长一半，需要调整，用内调整法。先求出调整量，把外圈按由大到小的次序按列表 73 的排列，得表74。 表 74 中，累加弧长 17 恰好刚超过圈长一半 16，因此选调整量为 4，将流向图的内圈各弧上都加上流量为 4 的内圈流向，再消除对流即得到图 729。图 729 中所示的流向图中，外圈流向图总长为：5+3+5=1314 【正确答案】 码头的装货量共 150 吨，卸货量为 50 吨，因此码头是空车的收点，收量为 100 吨。钢厂装货量为 50 吨，卸货量为 100 吨，因此钢厂是空车的发点，发量为 50 吨。火车站也是空车的发点，发量为 50 吨。仓库的装货量与卸货量均为50 吨，因此，仓库
17、既非空车的收点也非发点。画出表明空车收点、发点的交通图如图 731 所示(线上的数字是该路段的长度)。 要使空驶的吨公里数最少，就要对图 731 所示的交通图作一个最优流向图。用图上作业法来求解这一问题。抹去火车站到钢厂这段弧，按“供需归邻站” 的方法画出流向和表明流量，再把抹去的弧补回来，见图 732。 检查图 732，这一流向图是否最优?圈的总长度为：14+20+10+18=62 内圈流向总长为：10+20=3015 【正确答案】 先确定空车的收点、发点：发货点是空车收点，发货量是空车收量。B 2 点发 150 吨石灰到 A1 点卸货，于是 B2 点是空车收点，收货量为 150 吨；A1
18、点是空车的发货点，发货量是 150 吨；其余的 B1 点收空车 240 吨，A 2 点发空车240 吨，B 3 点收空车 240 吨，A 3 点发空车 240 吨。由此及图 733，可得交通图734。 先抹去弧 A1A2，按“供需归邻站” 的方法作出流向图，见图 734，此流向图只有一个圈，圈长为：1+2+2+3=8 内圈流向长2 为了减少收发车的空驶，可以将以上两条回路合并成一条回路(每辆车的载重量为 15 吨)：上述回路(1)派出两辆车到 B1 点装 30 吨水泥运到 A2 点卸下后，空驶到 B3 点装 30 吨砖运到 A3 点卸下后，空驶到 B2 点装 30吨石灰运到 A1 点，再空驶回
19、 B1 点，这就完成了一次循环运输，这样循环 5 次。回路(2)派两辆车到 B1 点装水泥 30 吨运到 A2 点，卸下货后空驶到 B3 点，装 10 吨砖运到 A3 点卸下，空驶回 B1 点，就完成一次循环运输，这样循环 3 次。合并后的回路：派两辆车到 B1 点装 30 吨水泥运到 A2 点卸下后，空驶到 B3 点装 10 吨砖运到A3 点，卸下后空驶到 B1 点，这样循环 8 次，最后由 A3 点直接空驶到 B2，这样循环运输 5 次，最后由 A1 点回到车场。16 【正确答案】 附图 26 即为题目中物资调运问题的交通图。17 【正确答案】 根据：(1)流向要画在物资运输方向的右侧；(
20、2)在一段路线上若有几个同方向的流向应该把它们合并成一个流向，并把流向相加。如附图 27 所示。18 【正确答案】 这个图里有三个圈，先检查上边的小圈，小圈总长为：12n+239+180+266=805 内圈有两个流向，总长为： 未超过圈长的一半。外圈没有流向，因此这个小圈合乎基本定理的要求，称这样的圈是合格的。再检查下边的大圈，这个圈的总长度为：165+180+118+317+349+252=1381 这个大圈的外圈流向只有一个，长度为：没超过这个大圈长的一半。内圈流向有三个，总长为：252+165+118=535 没有超过这个圈长的一半。另外，只有一个外圈流向，长为 31719 【正确答案
21、】 外圈流向的总长度为：4+5+3+3+2+5+3+1=26 圈总长为3+4+3+5+3+3+2+5+3+1=32 因为 2616，即外圈流向总长超过圈长一半，需要调整，用内调整法。先求出调整量，把外圈按由大到小的次序列成附表 18 的形式。附表 18 中，累加弧长 17 恰好超过圈长一半 16，因此选调整量为 4，将流向图的内圈各弧上都加上流量为 4 的内圈流向，再消除对流即得下面的附图 28。附图 28 中所示的流向图中，外圈流向图总长为：5+3+5=1320 【正确答案】 利用最大元素法制定初始指派方案，如表 62 所示。各个空格的检验数如表 63 所示。表 63 中检验数全不是正数，因
22、此以上指派方案为最优，即指派效益为：15+11+10+7+7=5021 【正确答案】 只有 3 1=6 种指派方法，下面一一列举出来(括号中对应的任务为(， ，)：(甲，乙，丙) ，费用为 17+24+35=76(甲，丙，乙) ，费用为 17+22+31=70(乙，甲，丙) ，费用为 20+15+35=70(乙，丙，甲) ，费用为 20+22+23=65(丙，甲，乙) ，费用为 25+15+31=71(丙，乙，甲) ，费用为 25+24+23=72由上可知，指派(乙，丙，甲)最少，因此，最优指派方案为(乙，丙，甲)。22 【正确答案】 (1)交换矩阵，使其每一行、每一列均至少有一个 0。(2)
23、求最优指派方案。(i)依次检查 C3 的各行，找出只有一个没有标记的 0 元素的行，并将这个 0 元素加上标记“*”，与这个元素“0”同列的 0 元素全部划去： (ii)依次检查各列，找出只有一个没有标记的 0 元素的列，并将这个 0 元素加上标记“*”，与这个元素“0”同行的 0 元素全部划去： 得到的 C5 中有 4 个0*，把它们对应的 xij 换成 1，其他元素全换成 0，得： 即最优指派为(丙，乙，丁，甲)，最小总工时为：8+7+11+7=3323 【正确答案】 (1)变换矩阵，使其每一行、每一列均至少有一个 0，已满足。(2)标记 0 元素。 (3)标“*” 的 0 少于方程阶数，但出现 0 元素闭回路(4 个 0 元素位于矩阵的 4 个顶点)。任选一个 0 画“0”，破去闭回路，并划去“0”同行与同列其它 0 元素，得最优解24 【正确答案】 (1)交换矩阵，使其每一行、每一列均至少有一个 0。(2)标记“*” 。 (3)在上述矩阵中进行调整，得到以下矩阵： (4)重复标记“*”的步骤得到：
