当前位置：问答库＞考研试题

一、简答题

1． 简述求解最小费用最大流的赋权网络设置方法。

【答案】解:对网络G=（ V ，E ，C ，d ），有可行流f ，保持原网络各点， 每条边用两条方向相反的有向边代替，各边的权

②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令

2． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。

【答案】（l ）某枝已经达到其范围内的最优解; （2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。

按如下规则:

二、计算题

3． 已知有一工程，由八道工序组成，详细资料由如下表所示。

试（1）绘制该项工程的网络图并计算网络时间; （2）求出该网络图的关键工序和关键路线; （3）求出该项工程的最低成本日程。

表

【答案】（l ）由表中的已知条件和数据，绘制如图1所示的网络计划图。

图1

各事项的最早时间为:

各事项最迟时间为：

将各事项的最早时间与最迟时间分别记入该事项右下角的“口”和“△”内，如图所示。

图2

（2）总时差为零的工序为关键工序，从图2可以看出关键路线为工期为15天，工程的直接费用 （各工序直接费用之和）为

（20+30+15+5+18+40+10+15）× 100=15300元 工程间接费用15×500=7500元 工程总费用为15300+7500=22800元

如果要缩短工期，应该首先缩短关键线路上赶一天进度所需费用最小的工序的作业时间。工序B ，G ，H 中， G 赶一天进度所需费用最小，为300元，且小于一天的工程间接费用500元。缩短G 工序l 天，此时总费用为 22800+（300-500）=22600元。此时，关键路线有三条，分别为B ，G ，H ; B ，C 和A ，D ，G ，H 。此时，如果 再缩短工程工期，赶进度所需费用将超过因缩短工期而节约的间接费用，从而导致工程总费用的增加。

（3）由以上分析可知，最低成本日程为14天，此时工程总费用为22600元。

4． 利用单纯型法求解上题的线性规划问题。

【答案】在上述约束条件中加入x 6, x 7, x 8，用单纯形法求解得到表1至表4。

表

1

又

已知工程项目每天 的间接费用为500元，按图2及表中的已知资料，若按图2安排，易知工程总

表2