[数据结构与算法]matlab 0-1整数线性规划问题（指派问题）举例讲解

现有5人 ，每个人都能完成A,B,C,D,E 5种任务，但他们完成一次每种任务需要的时间各不相同，现让这5人做A,B,C,D,E5个任务，怎样分配才能让5人完成所有任务的总时间最短？

设25个变量，分别代表第 i 人教第 j 门课，i 和 j =1：5，目标函数为 z=c*x(i,j)，x只能取 0 或 1 ；

没有 不等式约束条件,只有 等式约束条件;

约束条件：

（1）1人只能选1门课：x(i,1)+x(i,2)+x(i,3)+x(i,4)+x(i,5)=1，i=1:5.

对应的系数矩阵为:

1? 1? 1? 1??1? ?0? 0? 0??0??0? 0? 0? 0??0??0? 0? 0? 0??0??0? 0? 0? 0??0??0,? i=1时，其余变量系数均为0.

0? 0? 0??0??0? 1? 1? 1? 1??1? 0? 0? 0??0??0? 0? 0? 0??0??0? 0? 0? 0??0??0,? i=2时，其余变量系数均为0.

0? 0? 0??0??0? ?0? 0? 0??0??0? 1? 1? 1? 1??1? 0? 0? 0??0??0? 0? 0? 0??0??0,? i=3时，其余变量系数均为0.

0? 0? 0??0??0? ?0? 0? 0??0??0? 0? 0? 0??0??0? 1? 1? 1? 1??1? 0? 0? 0??0??0,? i=4时，其余变量系数均为0.

0? 0? 0??0??0? ?0? 0? 0??0??0? 0? 0? 0??0??0? 0? 0? 0??0??0? 1? 1? 1? 1??1,? i=5时，其余变量系数均为0.

（2）1门课只能被1人选：x(1,j)+x(2,j)+x(3,j)+x(4,j)+x(5,j)=1, j=1:5.

对应的系数矩阵为:

1? 0? 0? 0??0? ?1? 0? 0??0??0? 1? 0? 0??0??0? 1? 0? 0??0??0? 1? 0? 0??0??0,? j=1时，其余变量系数均为0.

0? 1? 0??0??0? ?0? 1? 0??0??0? 0? 1? 0??0??0? 0? 1? 0??0??0? 0? 1? 0??0??0,? j=2时，其余变量系数均为0.

0? 0? 1??0??0? ?0? 0? 1? 0??0? 0? 0? 1??0??0? 0? 0? 1??0??0? 0? 0? 1??0??0,? j=3时，其余变量系数均为0.

0? 0? 0??1??0? ?0? 0? 0??1??0? 0? 0? 0??1??0? 0? 0? 0??1??0? 0? 0? 0??1??0,? j=4时，其余变量系数均为0.

0? 0? 0??0??1? ?0? 0? 0??0??1? 0? 0? 0??0??1? 0? 0? 0??0??1? 0? 0? 0??0??1,? j=5时，其余变量系数均为0.

Data=[2,3,1,5,7;3,4,6,1,2;1,3,5,2,4;4,7,4,2,1;5,6,3,5,1];
c=Data(:);
Aeq=zeros(10,25);
for i=1:5
    Aeq(i,[1:5]+(i-1)*5)=1; %约束条件(1)
    Aeq(i+5,i:5:25)=1; %约束条件(2)
end
beq=ones(10,1);
intcon=1:25;  %25个变量均为整数
lb=zeros(25,1);  %变量最小值为0
ub=ones(25,1);   %变量最大值为1
[x fval]=intlinprog(c,intcon,[],[],Aeq,beq,lb,ub);
reshape(x,5,5)

?运行结果：

? ? ?0 ? ? 1 ? ? 0 ? ? 0 ? ? 0
? ? ?0 ? ? 0 ? ? 0 ? ? 1 ? ? 0
? ? ?1 ? ? 0 ? ? 0 ? ? 0 ? ? 0
? ? ?0 ? ? 0 ? ? 0 ? ? 0 ? ? 1
? ? ?0 ? ? 0 ? ? 1 ? ? 0 ? ? 0