Finding the minimum cost of a matrix

15 views (last 30 days)

Show older comments

丹麦纳西尔 on 10 Sep 2021

Commented: 丹麦纳西尔on 11 Sep 2021

Accepted Answer: Abolfazl Chaman Motlagh

假设我有成本矩阵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 Comments
ShowHide 4 older comments

Abolfazl Chaman Motlagh on 11 Sep 2021

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 = [一个（1,4）零（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

丹麦纳西尔 on 11 Sep 2021

谢谢各位的帮助。

请记住，代码的输出（最小化成本）将是如此” any size matrix can be given as an input to the code".

Accepted Answer

Abolfazl Chaman Motlagh on 10 Sep 2021

1
Link

Direct link to this answer

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

编辑：Abolfazl Chaman Motlagh on 10 Sep 2021

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 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.

这意味着：工人1分配给Machie 1，Worker 2分配给机器4，而Worker 3分配给机器3。

5 Comments
ShowHide 4 older comments

Abolfazl Chaman Motlagh on 11 Sep 2021

一般解决方案：给定成本系数的MXN矩阵。

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可能发生了不同的情况：

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），一个（1，m））;
                                  
                                   kron(ones(1,m),eye(m))];
                                  
                                   beq = ones(2*m,1);% m=n , so m+n is 2m

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），一个（1，m））;
                                  
                                   beq =一个（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.

丹麦纳西尔 on 11 Sep 2021

Suppose M= [30187 18877 45543 43822

31457 19802 46460 45501

33977 21638 48279 48831

35815 22274 50330 52160

36817 23199 54771 52584 ]

In this case m=5,n=4

The code is

T1=size(M,1)

T2=size(M,2)

if T1==T2

Aeq = [ kron(eye(T1),ones(1,T1));

kron(ones(1,T1),eye(T1))];

beq = ones(2*T1,1); % m=n , so m+n is 2m

elseif T1

aeq = kron（一个（1，t2），眼睛（T1））;

beq = ones(T1,1);

elseif T1>T2

Aeq = kron(eye(T2),ones(1,T1));

beq = ones(T2,1);

end

f = M(:)';

[x,fval] = intlinprog(f,1:T1*T2,[],[],Aeq,beq,zeros(T1*T2,1),inf(T1*T2,1));

ind = find(x);

[worker_index machine_index] = ind2sub([T1 T2],ind)

当我运行代码时，worker_index出现为1 1 1 1和machine_index = 1 2 3 4。

Pls check why the error coming in index when m>n?

Abolfazl Chaman Motlagh on 11 Sep 2021

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(:)';
                                  
                                   ifm==n
                                  
                                   aeq = [kron（eye（m），一个（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));
                                  
                                   elseifm>n
                                  
                                   aeq = kron（eye（n），一个（1，m））;
                                  
                                   beq =一个（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），一个（m*n，1））;
                                  
                                   else％（m 
                                  
                                   Aeq = kron(ones(1,n),eye(m));
                                  
                                   beq = ones(m,1);
                                  
                                   A = kron(eye(n),ones(1,m));
                                  
                                   b =一个（n，1）;
                                  
                                   x = intlinprog（f，1：m*n，a，b，aeq，beq，zeros（m*n，1），一个（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

丹麦纳西尔 on 11 Sep 2021

谢谢各位的帮助。代码是有效的。

s manbetx 845

MATLAB

发布

R2020a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

开始狩猎！

Translated by

Finding the minimum cost of a matrix

5 Comments
ShowHide 4 older comments

Accepted Answer

5 Comments
ShowHide 4 older comments

更多的Answers (0)

See Also

Categories

Tags

s manbetx 845

发布

Community Treasure Hunt

Finding the minimum cost of a matrix

5 Comments ShowHide 4 older comments

Accepted Answer

5 Comments ShowHide 4 older comments

更多的Answers (0)

See Also

Categories

Tags

s manbetx 845

发布

Community Treasure Hunt

5 Comments
ShowHide 4 older comments

5 Comments
ShowHide 4 older comments