1. 设决策变量 x = [ x1' x2' … xn'], xi表示第i个人是否做m项工作,xi = [xi1 xi2 … xim],xij取1表示第i个人做第j项工作,xij取0表示第i个人不做第j项工作;
2. 目标函数 sum( Cij * xij ) 最小化
3. 约束条件:第i个人最多做1项工作,sum( xi ) <= 1
第j项工作有且仅有1人做,sum( xj ) = 1
Matlab代码:
% 目标函数
C = [6 2 6 7 6
7 5 3 8 3
1 10 7 4 2
3 9 2 7 11
7 2 6 5 8
5 6 4 1 3];
C2 = C';
f = C2(:);
% 约束条件
[n,m] = size(C);
A = kron( eye(n),ones(1,m) );
b = ones(n,1);
Aeq = repmat( eye(m),1,n );
beq = ones(m,1);
lb = zeros(m*n,1); % 下限
ub = ones(m*n,1); % 上限
intcon = 1:m*n;
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);
y = f'*x
% 显示结果
for ii = 1:n
disp(['第' num2str(ii) '人:'])
ind = find( x( (ii-1)*m+(1:m) ) == 1);
if isempty(ind)
disp('无工作')
else
disp(['第' num2str(ind) '项工作'])
end
end
结果:
总时间消耗
y =
9
第1人:
无工作
第2人:
第5项工作
第3人:
第1项工作
第4人:
第3项工作
第5人:
第2项工作
第6人:
第4项工作