matlab里用0-1整数线性规intlinprog求解 不会啊

Question

 

Answer 1

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项工作