一、指派问题(0-1规划问题）

练习：教材P150,5.12

例题：四个人完成4项任务所用的时间如下，问如何指派任务使得完成所有任务的时间最短？

人员\任务   t1    t2    t3    t4

m1           2     15    13    4

m2        10     4    14    15

m3        9      14    16    13

m4        7      8     11     9

c_ij:表示第i个人完成第j项任务所用的时间；

决策变量x_ij:若第i个人选择第j项任务则x_ij=1;否则，x_ij=0；

模型为：

model:

sets:

task/1..4/:t;

man/1..4/:m;

link(man,task):c,x;

endsets

data:

c=2 15 13 4

10 4 14 15

9 14 16 13

7 8 11 9;

enddata

[obj] min=@sum(link:c*x);

@for(task(j):@sum(man(i):x(i,j))=1);

@for(man(i):@sum(task(j):x(i,j))=1);

@for(link:@bin(x));

end

求得：最优指派为：m1--t4,m2--t2,m3--t1,m4--t3

最优值为:28。

本题注意要点：

（1）@bin：界定函数，限制x为0或1

（2）请尝试把[obj]去掉，解的结果是否一致？

（3）人员-任务矩阵的构建方法：由sets:和data:部分来完成。

（4）@for和@sum嵌套使用的技巧。

（5）请尝试去掉end

（6）最优解对应的决策变量值为多少？