2016年湖北大学数学与统计学学院运筹学复试笔试最后押题五套卷
● 摘要
一、计算题
1． 在图中，（l ）用Dijkstra 方法求从v l 到各点的最短路; （2）指出对v l 来说，哪些顶点是不可到达的。
图
【答案】（1）
①v1已经获得P 标号，
计算从v l 到各点的最短路的步骤如下:
，修改v2，v5，v7的T 标号
因为
②v5已经获得P 标号
，
，改写v6的T
标号为
，所以有
。
于是，有v 1到各点v 2，v 5，v 7，v 6，v 8的最短路为
（2）v 1不能到达v 3及v 4。
2． 已知下列资料，如表所示:
表
，
因为
求出这项工程的最低成本日程。
【答案】由表中的己知条件和数据，绘制如图所示的网络图。
图
各事项的最早时间为:
各事项最迟时间为:
将各事项的最早时间与最迟时间分别记入该事项右下角的“口”和“△”内，如图所示。
图
总时差为零的工序为关键工序，从图中可以看出关键路线为工程的直接费用（各工序直接费用之和）为
如果要缩短工期，应该首先缩短关键线路上赶一天进度所需费用最小的工序的作业时间。工序B ，G ，H 中， G 赶一天进度所需费用最小，为300元，且小于一天的工程间接费用500元。缩短G 工序1天，此时总费用为 22500+（300-500）=22600元。此时，关键路线有三条，分别为B ，G ，H ；B ，C 和A ，D ，G ，H 。此时，如果再 缩短工程工期，赶进度所需费用将超过因缩短工期而节约的间接费用，从而导致工程总费用的增加。
所以，最低成本日程为14天，此时工程总费用为22600元。
3． 有四项工作A 、B 、C 、D 分别由甲、乙、丙、丁四个人来完成，各人完成各项任务所花费的时间（单位: 天）如下。试求解每人都承担一项工作的最优分配方案
表
. 又己知工程
项目每天的间接费用为500元，按图及表中的己知资料，若按图安排，易知工程总工期为巧天，
【答案】该问题是指派问题，且是求目标最小。因此用匈牙利方法计算如下:
相关内容
相关标签