Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Finding a minimum sum in a matrix under certain conditions

Subject: Finding a minimum sum in a matrix under certain conditions

From: Milos Milenkovic

Date: 16 Jun, 2009 10:07:01

Message: 1 of 7

Dear friends,
consider please following problem. A matrix containing all possible solutions of a problem is given as follows:
m=4
t=5
t=[0 1430 0 360 460; 0 0 30 0 0; 0 0 0 90 190; 0 0 0 0 0]
We have to find a minimum sum of all nonzero elements in matrix under the conditions that in each row and column can be just one element.
For this example the steps are:
1.Begin from first row and find minimum - 360
2.Continue at second row and find minimum - 30
3.In the third row minimum is 90 but because in that column has already chosen minimum pass on the next cell and that is 190.
4. In the fourth row there is no nonzero elements so don't consider
4.Sum all chosen numbers.

Thank you very much!
You are great all!

Subject: Finding a minimum sum in a matrix under certain conditions

From: John D'Errico

Date: 16 Jun, 2009 10:25:03

Message: 2 of 7

"Milos Milenkovic" <m.milenkovic@mathworks.com> wrote in message <h17qs5$frg$1@fred.mathworks.com>...
> Dear friends,
> consider please following problem. A matrix containing all possible solutions of a problem is given as follows:
> m=4
> t=5
> t=[0 1430 0 360 460; 0 0 30 0 0; 0 0 0 90 190; 0 0 0 0 0]
> We have to find a minimum sum of all nonzero elements in matrix under the conditions that in each row and column can be just one element.
> For this example the steps are:
> 1.Begin from first row and find minimum - 360
> 2.Continue at second row and find minimum - 30
> 3.In the third row minimum is 90 but because in that column has already chosen minimum pass on the next cell and that is 190.
> 4. In the fourth row there is no nonzero elements so don't consider
> 4.Sum all chosen numbers.
>
> Thank you very much!
> You are great all!

But why should we be doing your homework for
you? Surely you will get little out of it that way.

Why not try it yourself? You might learn something.

Subject: Finding a minimum sum in a matrix under certain conditions

From: us

Date: 16 Jun, 2009 10:27:01

Message: 3 of 7

"Milos Milenkovic" <m.milenkovic@mathworks.com> wrote in message <h17qs5$frg$1@fred.mathworks.com>...
> Dear friends,
> consider please following problem. A matrix containing all possible solutions of a problem is given as follows:
> m=4
> t=5
> t=[0 1430 0 360 460; 0 0 30 0 0; 0 0 0 90 190; 0 0 0 0 0]
> We have to find a minimum sum of all nonzero elements in matrix under the conditions that in each row and column can be just one element.
> For this example the steps are:
> 1.Begin from first row and find minimum - 360
> 2.Continue at second row and find minimum - 30
> 3.In the third row minimum is 90 but because in that column has already chosen minimum pass on the next cell and that is 190.
> 4. In the fourth row there is no nonzero elements so don't consider
> 4.Sum all chosen numbers.
>
> Thank you very much!
> You are great all!

show CSSM what YOU have done so far to solve YOUR homework problem...

us

Subject: Finding a minimum sum in a matrix under certain conditions

From: Milos Milenkovic

Date: 16 Jun, 2009 10:37:01

Message: 4 of 7

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <h17rtv$mms$1@fred.mathworks.com>...
> "Milos Milenkovic" <m.milenkovic@mathworks.com> wrote in message <h17qs5$frg$1@fred.mathworks.com>...
> > Dear friends,
> > consider please following problem. A matrix containing all possible solutions of a problem is given as follows:
> > m=4
> > t=5
> > t=[0 1430 0 360 460; 0 0 30 0 0; 0 0 0 90 190; 0 0 0 0 0]
> > We have to find a minimum sum of all nonzero elements in matrix under the conditions that in each row and column can be just one element.
> > For this example the steps are:
> > 1.Begin from first row and find minimum - 360
> > 2.Continue at second row and find minimum - 30
> > 3.In the third row minimum is 90 but because in that column has already chosen minimum pass on the next cell and that is 190.
> > 4. In the fourth row there is no nonzero elements so don't consider
> > 4.Sum all chosen numbers.
> >
> > Thank you very much!
> > You are great all!
>
> But why should we be doing your homework for
> you? Surely you will get little out of it that way.
>
> Why not try it yourself? You might learn something.


You are wright!
Ok.
Thanks anyway

Subject: Finding a minimum sum in a matrix under certain conditions

From: Milos Milenkovic

Date: 16 Jun, 2009 18:07:02

Message: 5 of 7

"Milos Milenkovic" <m.milenkovic@mathworks.com> wrote in message <h17qs5$frg$1@fred.mathworks.com>...
> Dear friends,
> consider please following problem. A matrix containing all possible solutions of a problem is given as follows:
> m=4
> t=5
> t=[0 1430 0 360 460; 0 0 30 0 0; 0 0 0 90 190; 0 0 0 0 0]
> We have to find a minimum sum of all nonzero elements in matrix under the conditions that in each row and column can be just one element.
> For this example the steps are:
> 1.Begin from first row and find minimum - 360
> 2.Continue at second row and find minimum - 30
> 3.In the third row minimum is 90 but because in that column has already chosen minimum pass on the next cell and that is 190.
> 4. In the fourth row there is no nonzero elements so don't consider
> 4.Sum all chosen numbers.
>
> Thank you very much!
> You are great all!

I don't know where and how to define constraint 3. to get the wanted solution

t =[0 1430 0 360 460; 0 0 30 0 0; 0 0 0 90 190; 0 0 0 0 0];
       
proc1Matrix = zeros(size(t));
proc2Matrix = zeros(size(t));
for i = 1:size(t, 1);
    currRow = t(i, :);
    nonZeroElems = nonzeros(currRow);
    minNonZeroElem = min(nonZeroElems);
    if ~isempty(minNonZeroElem)
        minElement = find(currRow == minNonZeroElem);
        proc1Matrix(i, minElement) = minNonZeroElem
    end
end
Z=sum(sum(proc1Matrix))

Mercy

Subject: Finding a minimum sum in a matrix under certain conditions

From: Milos Milenkovic

Date: 16 Jun, 2009 18:34:01

Message: 6 of 7

"Milos Milenkovic" <m.milenkovic@mathworks.com> wrote in message <h18n06$9g1$1@fred.mathworks.com>...
> "Milos Milenkovic" <m.milenkovic@mathworks.com> wrote in message <h17qs5$frg$1@fred.mathworks.com>...
> > Dear friends,
> > consider please following problem. A matrix containing all possible solutions of a problem is given as follows:
> > m=4
> > t=5
> > t=[0 1430 0 360 460; 0 0 30 0 0; 0 0 0 90 190; 0 0 0 0 0]
> > We have to find a minimum sum of all nonzero elements in matrix under the conditions that in each row and column can be just one element.
> > For this example the steps are:
> > 1.Begin from first row and find minimum - 360
> > 2.Continue at second row and find minimum - 30
> > 3.In the third row minimum is 90 but because in that column has already chosen minimum pass on the next cell and that is 190.
> > 4. In the fourth row there is no nonzero elements so don't consider
> > 4.Sum all chosen numbers.
> >
> > Thank you very much!
> > You are great all!
>
> I don't know where and how to define constraint 3. to get the wanted solution
>
> t =[0 1430 0 360 460; 0 0 30 0 0; 0 0 0 90 190; 0 0 0 0 0];
>
> proc1Matrix = zeros(size(t));
> proc2Matrix = zeros(size(t));
> for i = 1:size(t, 1);
> currRow = t(i, :);
> nonZeroElems = nonzeros(currRow);
> minNonZeroElem = min(nonZeroElems);
> if ~isempty(minNonZeroElem)
> minElement = find(currRow == minNonZeroElem);
> proc1Matrix(i, minElement) = minNonZeroElem
> end
> end
> Z=sum(sum(proc1Matrix))
>
> Mercy

Subject: Finding a minimum sum in a matrix under certain conditions

From: Marcus M. Edvall

Date: 17 Jun, 2009 01:13:55

Message: 7 of 7

Hi Milos,

If you do this:

t(t==0) = NaN;

and check

help min

you can get some nicer code.

Best wishes, Marcus
Tomlab Optimization Inc.
http://tomopt.com/
http://tomdyn.com/

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us