36 九江学院学报(自然科学版)　　　　　　　　　　　　　2010年第1期

每次测试所能容纳的人数;

第二个数为费用,表示完成每次测试的时间.所有弧的容量相同,总和为150,费用均为0,表示测试场所容纳的人数为150,学生转换测量仪的时间为

0.为清晰起见,图中只在一条弧上给出了标注.现有20人要在430秒内完成所有测试,即要遍历①、②、③、④、⑤这五类点,问应沿怎样的测试路线行走?(图1中虚线表示将关键测试和非关键测试分开的

16171819682077968

33389689

33

79

→→→→6

171819207978

33

68008968

33

1079

33

→→→→

181920

7

1920

101610161718

33

10161718161719102091020

1718

1919

意思,以下同)

00→

0200011,12,13,14,1,2,3,4,5

7,8,9,1016,17,18,19,20

做同样的测试步骤,20人的全部测试在430秒内完成。

据此,笔者用图2以更清楚地给出问题一的

图1　测试路线行走图

解答:

512模型一的求解　根据第2节的分析二,20人(假定学号相连,且不妨设为1—20号)要在430

秒内完成所有测试,必须是10人完成关键测试耗时215秒,也有10人在215秒内完成所有非关键测试.为保证学号相连以减少登录时间,自然想到让1—5号、11—15号分别做关键测试,而同时让6—10号、16—20号分别做非关键测试.主要问题在于如何减少非关键测试中的可等时间,保证10人完成所有非关键测试的时间不超出215秒.由非关键测试中测量仪的耗时特点,同样自然地想到,让6—10号、16—20号学生排成两队,得初始状态矩阵状态转换:

　　在上述转换过程中,7表示7号学生在做虚拟测试,即其已经做过该类测试从而不需再测.8,9,10,17,18,19,20的意义类

3

3

3

3

3

3

3

3

图2　测试状态转换图

对模型一的注:

注1:因为每个上午可测试34188组,若测试34组,时间还会剩余34188×430=378(秒),等

于说每组有10秒的机动时间;注2:连号优先原则下的小号优先原则,即在非关键测试中,若学号相连,则从小号到大号依次测试,若学号不相连,则先保证连号优先,在保证小号优先.比如,6号做完点②的测试后来到点⑤,按此原则,必须

166

177

188

199

,作如下

排在20号后面等待.6　问题二的模型及解答

[3]

模型二(0-1规划模型):

56

似,0表示虚拟人员在做测试或等待.

由已知,初始状态需要一次登录,耗时25秒,其余状态均只需20秒,故共耗时205秒.等关键测试结束后,再互换做关键测试和做非关键测试的人员,即作如下状态转换:

1,2,3,4,511,12,13,14,15

16,17,18,19,6,7,8,9,10

s.t.

minz=680-3

∑px

i

i=1

ij

∑x

j=1

ij

=1(i=1,…,56)

56

∑px

i

i=1

ij

≤680(j=1,2,3)

→

xij=0或1pi≥0且为整数