Variables: 32 Integers: 8
Global optimal solution found.
Objective value: 784.5000 Objective bound: 784.5000 Infeasibilities: 0.7105427E-14 Extended solver steps: 0 Total solver iterations: 84
Variable Value Reduced Cost X1 40.00000 0.000000 X2 50.00000 0.000000 X3 75.00000 0.000000 X4 25.00000 0.000000 Y 2.000000 0.000000
Row Slack or Surplus Dual Price 1 784.5000 -1.000000 2 0.000000 -1.000000 3 10.00000 0.000000 4 0.000000 -0.2000000 5 0.000000 -0.7000000 6 0.000000 -4.000000
即该造船厂下四个季度的生产量分别为40条、50条、75条、25条，可使可使总费用最小，为784.5万元。
问题三：设有4位应聘者到某公司参加三个阶段的面试：公司要求第个应聘者都必须首先找公司的秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4位应聘者的顺序是一样的）。由于4位应聘者的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：
应聘者甲 应聘者乙 秘书初试 13 10 主管复试 15 20 经理面试 20 18 应聘者丙 20 16 10 应聘者丁 8 10 15 为了确定4位应聘者全部面试用时的最少时间，试给出相应的数学模型及其LINGO求解程序。 建立模型:
tij分别表示第i(i?1,2,3,4)位应聘者在第j(j?1,2,3)个面试阶段的面试时间，记xij表示第
i(i?1,2,3,4)位应聘者在第j(j?1,2,3)个阶段的面试开始时刻（且令起初时刻为0）。以T表示面试总
用时，也就是最后一位面试者面试结束的时刻。那么目标函数为
minT?max?xi3?ti3?
i 4
其中每位应聘者必须参加完前一阶段面试才能进行下一阶段的面试，也就是说：
xij?tij?xi,j?1(i?1,2,3,4，j?1,2)
对于第j阶段同一个时间段只能有1位应聘者面试，可以用0?1变量yik表示第k(k?1,2,3,4)位应聘者是否排着第i(i?1,2,3,4)位应聘者前面时会使用时更少（0表示否，1表示是），则
xij?tij?xkj?Tyik
根据题目的意思则有：
yki?1?yik
即令i?k。并且有
xkj?tkj?xij?Tykj?T?1?yik?
编写程序：
在lingo软件中编写上述模型的程序： SETS:
PORSONS/1..4/; INTERVIEW/1..3/;
PI(PORSONS,INTERVIEW):TIME,X; PP(PORSONS,PORSONS)|&1 #LT# &2:Y; ENDSETS DATA: TIME=13,15,20 10,20,18 20,16,10 8,10,15; ENDDATA
MIN=T;
T=@MAX(PI(I,J)|J#EQ#3:X(I,J)+TIME(I,J));
@FOR(PI(I,J)|J#LT#3:X(I,J)+TIME(I,J) @FOR(INTERVIEW(J):@FOR(PP(I,K):X(I,J)+TIME(I,J)-X(K,J) @FOR(PP:@BIN(Y)); 运行程序： Local optimal solution found. Objective value: 84.00000 Objective bound: 84.00000 Infeasibilities: 0.000000 Extended solver steps: 63 Total solver iterations: 6653 Variable Value Reduced Cost T 84.00000 0.000000 5 TIME( 1, 1) 13.00000 0.000000 TIME( 1, 2) 15.00000 0.000000 TIME( 1, 3) 20.00000 0.000000 TIME( 2, 1) 10.00000 0.000000 TIME( 2, 2) 20.00000 0.000000 TIME( 2, 3) 18.00000 0.000000 TIME( 3, 1) 20.00000 0.000000 TIME( 3, 2) 16.00000 0.000000 TIME( 3, 3) 10.00000 0.000000 TIME( 4, 1) 8.000000 0.000000 TIME( 4, 2) TIME( 4, 3) X( 1, 1) X( 1, 2) X( 1, 3) X( 2, 1) X( 2, 2) X( 2, 3) X( 3, 1) X( 3, 2) X( 3, 3) X( 4, 1) X( 4, 2) X( 4, 3) Y( 1, 2) Y( 1, 3) Y( 1, 4) Y( 2, 3) Y( 2, 4) Y( 3, 4) Row 1 2 3 4 5 6 7 8 9 10 11 12 13 14 10.00000 15.00000 8.000000 21.00000 36.00000 21.00000 36.00000 56.00000 31.00000 56.00000 74.00000 0.000000 9.500000 19.50000 0.000000 0.000000 1.000000 0.000000 1.000000 1.000000 84.00000 0.000000 0.000000 0.000000 5.000000 0.000000 5.000000 2.000000 1.500000 0.000000 0.000000 10.00000 63.00000 0.000000 6 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.9999970 0.000000 0.000000 -83.99950 0.000000 83.99950 -83.99950 0.000000 0.000000 Dual Price -1.000000 -0.9999970 0.9999970 0.000000 0.000000 0.9999970 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 Slack or Surplus 15 53.00000 0.000000 16 33.00000 0.000000 17 61.00000 0.000000 18 41.00000 0.000000 19 0.000000 0.9999970 20 54.00000 0.000000 21 13.00000 0.000000 22 23.00000 0.000000 23 0.000000 0.9999970 24 20.00000 0.000000 25 57.50000 0.000000 26 0.000000 0.000000 27 37.50000 0.000000 28 21.50000 0.000000 29 49.00000 0.000000 30 33.00000 0.000000 31 1.500000 0.000000 32 48.00000 0.000000 33 16.50000 0.000000 34 36.50000 0.000000 35 0.000000 0.000000 36 18.00000 0.000000 37 47.50000 0.000000 38 0.000000 0.9999970 39 29.50000 0.000000 40 19.50000 0.000000 41 46.00000 0.000000 42 36.00000 0.000000 43 1.500000 0.000000 44 56.00000 0.000000 45 21.50000 0.000000 46 39.50000 0.000000 T=84，Y(1,2)=0，Y(1,3)=0，Y(1,4)=1，Y(2,3)=0，Y(2,4)=1，Y(3,4)=1 即 y12?0,y13?0,y14?1,y23?0,y24?1,y34?1 结果分析：应聘者甲在应聘者乙、丙前面面试，应聘者丁在应聘者甲、乙、丙前面面试，应聘者乙在应聘者丙前面面试。所以4位应聘者全部面试所用的时间最少为84分钟。 问题四：职员时序安排模型 一项工作一周7 天都需要有人（比如护士工作），每天（周一至周日）所 需的最少职员数为20、16、13、16、19、14 和12，并要求每个职员一周连续工作5 天，试求每周所需最少职员数，并给出安排。注意这里我们考虑稳定后的情况。 解： 模型建立： 因为每天护士工作的人数是不同的，而且每个护士可以连续的工作5天，所 以我们可以设周1，2，3，4，5，6和周日开始上班的人数依x1、x2、x3、x4、x5、x6、 7 x7。把在同一天开始工作的服务员编为一组。周一组的工作日是从周1到周5，如下表中的周1组的那一列；在周1这一天，在岗工作的有从周4，5，6，日以及周1组来的服务员，而这一天需要至少20人。把这件事表达在下表的周1行。其他各行各列也有类似的意义。 各组在岗情况 周 1组 周2组 周3组 周4组 周5组 周6组 周日组 必须人数 x4x5x6x7周1 x120 各 x2x5x6x7周2 x116 日 x2x3x6x7 周3 x113 在 x2x3x4x7周4 x116 岗 x2x3x4x5周5 x119 情 x2 x3 x4 x5 x6 周6 14 况 x3 x4 x5 x6 x7 周日 12 目标函数： MinZ=x1+x2+x3+x4+x5+x6+x7 约束条件： x1 +x4+x5+x6+x7?20 x1+x2 +x5+x6+x7?16 s·t x1 +x2+x3 +x6+x7?13 x1+x2+x3+x4 +x7?16 x1+x2+x3+x4+x5 ?19 x2+x3+x4+x5+x6 ?14 x3+x4+x5+x6+x7?12 8