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

一、计算题

1． 有4个工人，要指派他们分别完成4项工作，每个人做各项工作所消耗的时间如表所示。问指派哪个人去完成哪项工作，可使总的消耗时间为最小?

表

【答案】第一步:将系数矩阵进行变换为

第二步:进行试指派，得到

因为m=3

第三步：做最少的直线覆盖所有的0元素，并进行再指派

指派成功，此项工作有多种指派方案，minz=70，指派矩阵如下:

由解矩阵得最优指派方案为: （1） （2）

甲→A ，乙→D ，丙→C ，丁→B ; 甲→B ，乙→A ，丙→C ，丁→D 。

2． 某制造厂每周购进某种机械零件50件，订购费为40元，每周保管费为3.6元。试求:

（l ）E ，O ，Q ;

（2）该厂为少占用流动资金，希望存储量达到最低限度，决定宁可使总费用超过最低费用的4%作为存储 策略，问这时订购批量为多少?

【答案】已知R=50，C 3=40，C 1=3.6。 （l ）E ，O ，Q 公式，可求得

（2）由题意，有

该厂为了少占用流动资金，应取

件。

，解得Q=44件，Q=25件。所以

3． 求图中所示的网络最大流。

图

【答案】令图中所有弧的可行流为0，同时给图中的中间顶点标上名称，如下图所示（弧旁的数字为

）。

图

用标号算法求最大流 步骤一

，依次给v 2标号（v S ，15），v 6标号（v 2，9），片标号（l ）标号过程。先给v s 标号（0，+∞）（v 6，9）。

（2）调整过程。在网络上寻找增广链

=

，如图双箭头所示。

图