Finding the minimum cost of a matrix

Question

Danish Nasir 2021-9-10

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1450804-finding-the-minimum-cost-of-a-matrix

评论： Danish Nasir 2021-9-11

采纳的回答： Abolfazl Chaman Motlagh

Suppose i have cost matrix M= [ 100 250 300 400

600 900 400 300

250 300 160 190].

The size of matrix 3x4. Let column represent machines and row represent worker.I want to minimize cost Matrix M. Each column should have only one cost. I didn't want to use matchpair function.

How can i use intlinprog function of Matlab for minimization cost?

5 个评论
显示 3更早的评论隐藏 3更早的评论

Abolfazl Chaman Motlagh 2021-9-11

在 MATLAB Online 中打开

your constraints are wrong for this problem. as you can see in the solutions 6 and 8 means worker 2 and 4 are simultaneusly work on machine 2. in a symmetric model as you mentioned balanced the other constraint should be added :

which means just 1 worker can work on every machine. including this you have 4+4 constraints (4 before):

you can create these 4 constraints by :

Aeq = [ ones(1,4) zeros(1,12);
    zeros(1,4) ones(1,4) zeros(1,8);
    zeros(1,8) ones(1,4) zeros(1,4);
    zeros(1,12) ones(1,4);
    1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;
    0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
    0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0;
    0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1];

if you get the solution, you can easily create 4 first row with this:

kron(eye(4),ones(1,4))
ans = 4×16
     1     1     1     1     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     1     1     1     1     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     1     1     1     1     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     1     1     1     1

and 4 second row with this:

kron(ones(1,4),eye(4))
ans = 4×16
     1     0     0     0     1     0     0     0     1     0     0     0     1     0     0     0
     0     1     0     0     0     1     0     0     0     1     0     0     0     1     0     0
     0     0     1     0     0     0     1     0     0     0     1     0     0     0     1     0
     0     0     0     1     0     0     0     1     0     0     0     1     0     0     0     1

Abolfazl Chaman Motlagh 2021-9-11

sure, i add generall method in comment of Accepted answer. give me some time to write it clear and properly.

Danish Nasir 2021-9-11

Thanx for the help.

Please remember that output of the code (minimize cost) will be such that "any size matrix can be given as an input to the code".

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Abolfazl Chaman Motlagh 2021-9-10

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1450804-finding-the-minimum-cost-of-a-matrix#answer_784929

编辑：Abolfazl Chaman Motlagh 2021-9-10

在 MATLAB Online 中打开

If i get that right, you have an assignment task.

so you want to solve this :

your constraint should be :

which i represent machines, and j represent workers. you have 3 workers and 4 machines. hence the constraints are not symmetric.

you also need boundery conditions.

i am going to linearize 2d index of x_i,j to a vector so we have

finally :

M= [ 100 250 300 400;
     600 900 400 300;
     250 300 160 190];
f = M(:)' ;
Aeq = [ 1 0 0 1 0 0 1 0 0 1 0 0;
        0 1 0 0 1 0 0 1 0 0 1 0;
        0 0 1 0 0 1 0 0 1 0 0 1];
beq = ones(3,1);
x = intlinprog(f,1:12,[],[],Aeq,beq,zeros(12,1),inf(12,1));
LP:                Optimal objective value is 560.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer
within tolerance, options.IntegerTolerance = 1e-05 (the default value).
find(x)
ans = 3×1
     1
     9
    11

which means X11 = 1, X33=1, X42=1.

and that means : the worker 1 assign to machie 1, worker 2 assign to machine 4, and worker 3 assign to machine 3.

5 个评论
显示 3更早的评论隐藏 3更早的评论

Abolfazl Chaman Motlagh 2021-9-11

编辑：Abolfazl Chaman Motlagh 2021-9-11

在 MATLAB Online 中打开

General Solution : Given mxn Matrix of Cost Coefficients.

m represent number of workers. and index i represent i-th worker.

n represent number of machines. and index j represent j-th machine.

3 different situation could happend:

m=n . workers are equal to machines.

in this case we need both constraints for limit workers to work somewhere and workers to work exactly on one machine :

Aeq = [ kron(eye(m),ones(1,m)); 
    kron(ones(1,m),eye(m))];
beq = ones(2*m,1);      % m=n , so m+n is 2m

m<n . workers are less than machines.

in this case we need a set of constraints to limit workers to work exactly on one machine. ( so n-m machine remain without any worker):

Aeq = kron(ones(1,n),eye(m));
beq = ones(m,1);

m>n. workers are more than machines.

in this case, similar to previous we need a set of constraints to limit machines to have exactly one worker. ( so m-n workers won't do anything):

Aeq = kron(eye(n),ones(1,m));
beq = ones(n,1);

Hence :

f = M(:)';
x = intlinprog(f,1:m*n,[],[],Aeq,beq,zeros(m*n,1),inf(m*n,1));
ind = find(x);

you can find index of worker and machine by using :

[worker_index machine_index] = ind2sun([m n],ind);

means worker_index(k) are working on machine_index(k) for all k.

for formulation of problem see accepted answer and comments below the original question.

Abolfazl Chaman Motlagh 2021-9-11

编辑：Abolfazl Chaman Motlagh 2021-9-11

在 MATLAB Online 中打开

yes, i'am sorry. i forgot to include constraints for ensure than workers are not having more than one job, and machines have more than one workers. here is complete solution. i hope it doesn't have any problem:

M= [30187,18877,45543,43822;
31457,19802,46460,45501;
33977,21638,48279,48831;
35815,22274,50330,52160;
36817,23199,54771,52584]; % for example
[m n] = size(M);
f = M(:)';
if m==n
    Aeq = [ kron(eye(m),ones(1,m)); 
            kron(ones(1,m),eye(m))];
    beq = ones(2*m,1);
    x = intlinprog(f,1:m*n,[],[],Aeq,beq,zeros(m*n,1),ones(m*n,1));
elseif m>n
    Aeq = kron(eye(n),ones(1,m));
    beq = ones(n,1);
    A = kron(ones(1,n),eye(m));
    b = ones(m,1);
    x = intlinprog(f,1:m*n,A,b,Aeq,beq,zeros(m*n,1),ones(m*n,1));
else  %(m<n)
    Aeq = kron(ones(1,n),eye(m));
    beq = ones(m,1);
    A = kron(eye(n),ones(1,m));
    b = ones(n,1);
    x = intlinprog(f,1:m*n,A,b,Aeq,beq,zeros(m*n,1),ones(m*n,1));
end
ind = find(x);
[worker_index machine_index] = ind2sub([m n],ind);

in 2rd and 3rd cases i add an inequality to make sum of machines for each worker be less than 1(m>n), and some of worker on each machine be less than 1(m<n).

Danish Nasir 2021-9-11