Maximizing x1+1.2*x2+1.5*x3 subject to Constraints | Linear Equations

[Tranquillity]

Hello guys I have to maximise x1+1.2*x2+1.5*x3 subject

2*x3<=60
2*x2<=45
2*x1+x2+3*x3<=80
x1>=20
x2+x3>=10
x1,x2,x3>=0

I am told that one of the constraints is redundant i.e one of the equations can be removed and then use the Simplex method to obtain the values for x1,x2,x3.

The problem is that I know how to do the Simplex method but cannot see which constraint can be removed.

My question really reduces to a system of linear equations question so that's why I have posted it at this section.

My lecturer said that it's really easy to spot the redundant constraint by just seeing the above equation, but I still cannot see it!

Any help would be greatly appreciated.

Thank you!

Kind regards

 

[CaptainBlack]

Hello guys I have to maximise x1+1.2*x2+1.5*x3 subject

2*x3<=60
2*x2<=45
2*x1+x2+3*x3<=80
x1>=20
x2+x3>=10
x1,x2,x3>=0

I am told that one of the constraints is redundant i.e one of the equations can be removed and then use the Simplex method to obtain the values for x1,x2,x3.

The problem is that I know how to do the Simplex method but cannot see which constraint can be removed.

My question really reduces to a system of linear equations question so that's why I have posted it at this section.

My lecturer said that it's really easy to spot the redundant constraint by just seeing the above equation, but I still cannot see it!

Any help would be greatly appreciated.

Thank you!

Kind regards

x1>=0 is redundant since you also have x1>=20.

CB

 

[Tranquillity]

Thank you very much! I should have spotted it by myself, silly me!

Kind regards

 

[Tranquillity]

Hello guys, sorry to bother again.
One of the capacity constraints should be removed and not the non-negativity constraint, in order to make our simplex algorithm easier. That was the point of asking us to remove a constraint.

Can you see any other constraint which could be removed except the non-negativity constraints?

Thank you.

Kind regards

 

[CaptainBlack]

Hello guys, sorry to bother again.
One of the capacity constraints should be removed and not the non-negativity constraint, in order to make our simplex algorithm easier. That was the point of asking us to remove a constraint.

Can you see any other constraint which could be removed except the non-negativity constraints?

Thank you.

Kind regards

Replace x1 with x4=x1-20 and re-express the problem in terms of x4 in place of x1, now you have the positivity constraint back.

 

[Tranquillity]

I mean can you see any of these constraints

2*x3<=60
2*x2<=45
2*x1+x2+3*x3<=80
x1>=20
x2+x3>=10

that is possible just to remove it without any substitutions?

 

[CaptainBlack]

I mean can you see any of these constraints

2*x3<=60
2*x2<=45
2*x1+x2+3*x3<=80
x1>=20
x2+x3>=10

that is possible just to remove it without any substitutions?

Not that is obvious.

CB

 

[Tranquillity]

Ok, thank you very much for the help

Kind regards

 

[Sudharaka]

Hello guys I have to maximise x1+1.2*x2+1.5*x3 subject

2*x3<=60
2*x2<=45
2*x1+x2+3*x3<=80
x1>=20
x2+x3>=10
x1,x2,x3>=0

I am told that one of the constraints is redundant i.e one of the equations can be removed and then use the Simplex method to obtain the values for x1,x2,x3.

The problem is that I know how to do the Simplex method but cannot see which constraint can be removed.

My question really reduces to a system of linear equations question so that's why I have posted it at this section.

My lecturer said that it's really easy to spot the redundant constraint by just seeing the above equation, but I still cannot see it!

Any help would be greatly appreciated.

Thank you!

Kind regards

Hi Tranquillity, :)

Looking at the constraint, \(2x_1+x_2+3x_3\leq 80\) we see that, \(3x_3\leq 80\) since all \(x_1,\, x_2,\, x_3\geq 0\). Now we are also given the constraint, \(2x_3\leq 60\Rightarrow 3x_3\leq 90\). So considering the two constraints,

\[2x_1+x_2+3x_3\leq 80\Rightarrow 3x_3\leq 80\mbox{ and }2x_3\leq 60\Rightarrow 3x_3\leq 90\]

we see that \(2x_3 \leq 60\) is the redundant constraint.

Kind Regards,
Sudharaka.

 

[Tranquillity]

Thank you :)
I have confirmed using a tool for solving Simplex problems (before solving on hand) and both cases i.e using the redundant constraint or removing it, give the same answer!

Kind regards,
Tranquillity

 

[Sudharaka]

Thank you :)
I have confirmed using a tool for solving Simplex problems (before solving on hand) and both cases i.e using the redundant constraint or removing it, give the same answer!

Kind regards,
Tranquillity

You are welcome, since this problem involves \(\geq\) constraints you can use variations of the Simplex method to solve this problem such as, Big M method and http://web.itu.edu.tr/topcuil/ya/2phase.pdf.

1) The Big M Method

2) http://businessmanagementcourses.org/Lesson09TheBigMMethod.pdf

3) http://www.statslab.cam.ac.uk/~ff271/teaching/opt/notes/notes8.pdf

 

[Tranquillity]

Thanks again for that, I have another small question on the topic. I solved my system and got some non-integer values but my variables should be integers. So I will have to round up the decimals to get an integer answer. The obvious thing to do is to round x2=22.5 to 22 and x3=5.83 to 5 (these are the answers, x1 is already an integer).

If I try rounding up 22.5 to 23 the constraint 2*x2<=45 is not satisfied. So I have to round it down to 22.

Now, rounding up 5.83 to 6 works for a strange reason (it satisfies all of the constraints). I thought that only rounding up to 5 would work since the obvious thing to do was rounding down and not up.

So 22.5 rounds to 22 and 5.83 to 6.

Should I check every time with roundings to see the largest one that satisfies my constraints?

Any feedback on that would be greatly appreciated.

Thanks again.

Kind regards,
Tranquillity

 

[Sudharaka]

I solved my system and got some non-integer values but my variables should be integers.

Can you explain for what purpose you have to do this?

 

[Tranquillity]

Yes, the problem has to do with quantities of ice creams being sold, so we want integer solutions.

x1,x2,x3 are the quantities of three different flavours being sold per day.

So I have to round it up.

Kind regards,
Tranquillity

 

[Sudharaka]

Yes, the problem has to do with quantities of ice creams being sold, so we want integer solutions.

x1,x2,x3 are the quantities of three different flavors being sold per day.

So I have to round it up.

Kind regards,
Tranquillity

So I assume that the objective function \(z=x_1+1.2x_2+1.5x_3\) gives the profit. And you are trying to maximize the profit. Is that correct?

 

[Tranquillity]

Yup! And the answers I found by hand were double checked with an online tool, so I am sure I should be getting non-integer values.

Kind regards,
Tranquillity

 

[Sudharaka]

Yup! And the answers I found by hand were double checked with an online tool, so I am sure I should be getting non-integer values.

Kind regards,
Tranquillity

Suppose you have a fractional part in the answer for \(x_1,x_2\) or \(x_3\). Then round up to the nearest integer and see whether that satisfies each constraint. If it doesn't then you'll have to go for the other value (the second nearest integer value). That way the error of the approximation will be minimized. So, \(22.5\) should be rounded to \(22\) and \(5.83\) to \(6\).

 

[Tranquillity]

Suppose you have a fractional part in the answer for \(x_1,x_2\) or \(x_3\). Then round up to the nearest integer and see whether that satisfies each constraint. If it doesn't then you'll have to go for the other value (the second nearest integer value). That way the error of the approximation will be minimized. So, \(22.5\) should be rounded to \(22\) and \(5.83\) to \(6\).

But rounding rules are saying that 22.5 should be 23 and 5.83 should be 6.

But in the context of this type of problem, every values shouldn't be rounded up to the lower integer?

What I was thinking is that let x1,x2,x3 be any type of product or let them be humans (maybe for some other problem)

If you got the answer 5.83 people, the logical thing to do is to round them to 5, not to 6, since we are talking about objects/humans (countable items in a context of a problem)

I hope you understand what I am thinking exactly.

Now in this problem you can't have 5.83 ice creams, you should round them to 5, by a logical thinking and 22.5 ice creams should be rounded to 22.

Because you are rounding countable items/people etc, you are not just rounding a number with no meaning.

But in the particular problem 22.5 rounded to 22 and 5.83 rounded to 6 are the max optimal values that fit the constraints. (but with the common rounding rules 22.5 should be 23)

But with the logical thinking I explained above, 5.83 should be rounded up to 5.

So this problem showed me that I shouldn't be thinking with the "logical way"

I should check both roundings and see which is the largest which satisfies the constraints.

Hope my thoughts were clear enough.

Any feedback would be great! :)

 

[Sudharaka]

But rounding rules are saying that 22.5 should be 23 and 5.83 should be 6.

But in the context of this type of problem, every values shouldn't be rounded up to the lower integer?

Your goal is to minimize the error of the profit when approximating values. Having this in mind you will have to use the nearest possible integer for each \(x_1,x_2\) and \(x_3\) so that all the constraints are satisfied. Using rounding rules for each value will surely minimize the error of the approximated solution but will violate the given constraints.

What I was thinking is that let x1,x2,x3 be any type of product or let them be humans (maybe for some other problem)

If you got the answer 5.83 people, the logical thing to do is to round them to 5, not to 6, since we are talking about objects/humans (countable items in a context of a problem)

I hope you understand what I am thinking exactly.

Suppose as you suggest that \(x_1,x_2\) and \(x_3\) are the number of people of different expertise that should be hired for a company, and we are trying to maximize the profit. Then if the same linear programming model is used the best approximate for \(x_3\) will be \(6\) since that number of people for \(x_3\) will maximize the profit.

 

[Tranquillity]

So, given I found some non integer values but need integer values for my problem, I will first try rounding to the upper integer to see if it satisfies the constraints, if not then obviously the lower one will satisfy the problem. This is the method I should use after all, right?

Thanks again for all, it is much appreciated!

Kind regards,
Tranquillity

 

[Sudharaka]

So, given I found some non integer values but need integer values for my problem, I will first try rounding to the upper integer to see if it satisfies the constraints, if not then obviously the lower one will satisfy the problem. This is the method I should use after all, right?

Thanks again for all, it is much appreciated!

Kind regards,
Tranquillity

Yes, I don't know if you have gained the intuition behind this reasoning. If not, I suggest that you start a new thread so that a member other than myself will be able to provide insight about this matter, probably using a different approach.

 

[Tranquillity]

I have understand it, the only thing I was arguing about is that you can't chop people or objects :p That's why I was thinking it's more logical to chop down than to add something up.

But yup since I can find a max number which satisfies all of the constraints that's fair enough :)

Thanks for all :)

 

[Sudharaka]

I have understand it, the only thing I was arguing about is that you can't chop people or objects :p That's why I was thinking it's more logical to chop down than to add something up.

But yup since I can find a max number which satisfies all of the constraints that's fair enough :)

Thanks for all :)

Glad to help you. :)