Welcome to our community

Be a part of something great, join today!

Big M method of LPP

suvadip

Member
Feb 21, 2013
69
In a LPP all the constraints are given as 'less than equal to' type. But it was asked to solve the LPP by Charnes Big M method. Is the question wrong?

According to me, we have to apply simplex method to solve it. There is no scope tp introduce M.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
In a LPP all the constraints are given as 'less than equal to' type. But it was asked to solve the LPP by Charnes Big M method. Is the question wrong?

According to me, we have to apply simplex method to solve it. There is no scope tp introduce M.
Is there maybe a constraint, where b is negative? I mean for example $ -4x_1+2x_2 \leq -4$ ?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
In a LPP all the constraints are given as 'less than equal to' type. But it was asked to solve the LPP by Charnes Big M method. Is the question wrong?

According to me, we have to apply simplex method to solve it. There is no scope tp introduce M.
The Big M method is a generalization that allows for 'greater than or equal to' constraints.
The simplex method also solves those.
 

suvadip

Member
Feb 21, 2013
69
Is there maybe a constraint, where b is negative? I mean for example $ -4x_1+2x_2 \leq -4$ ?

No, the LPP was
Max z=2x+3y
subject to
x+y<=8
x+2y<=5
2
x+y<=8
x,y>=0

Can it be solved by Big M method?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
No, the LPP was
Max z=2x+3y
subject to
x+y<=8
x+2y<=5
2
x+y<=8
x,y>=0

Can it be solved by Big M method?
No need. The regular simplex method works for this.
The only 'greater than' constraints are the non-negativity constraints, which are a standard part of the simplex method.
 

Random Variable

Well-known member
MHB Math Helper
Jan 31, 2012
253
I haven't' done any linear programming in a long time. But if the problem written in standard form has no negative resource values, and thus no need to create artificial variables, using the Big-M method or the two-phase method doesn't' seem to make any sense.
 

suvadip

Member
Feb 21, 2013
69
No need. The regular simplex method works for this.
The only 'greater than' constraints are the non-negativity constraints, which are a standard part of the simplex method.
Actually I need a answer of type 'it can not be solved by Big M method' or 'it can be solved by Big M method'. The question was set in a university exam and it was clearly instructed to solve it by Big M method.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
Actually I need a answer of type 'it can not be solved by Big M method' or 'it can be solved by Big M method'. The question was set in a university exam and it was clearly instructed to solve it by Big M method.
Then the answer is yes, it can be solved by the Big M method.
 

suvadip

Member
Feb 21, 2013
69
Then the answer is yes, it can be solved by the Big M method.

How? I guess the way may be like this:

let a constraint is x1+2x2<=5
Introducing slack variable x3 we can write
x1+2x2+x3=5

As we are bound to solve by Big M method, we can now introduce artificial variable x4 to get
x1+2x2+x3+x4=5

Am I right?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
How? I guess the way may be like this:

let a constraint is x1+2x2<=5
Introducing slack variable x3 we can write
x1+2x2+x3=5
Correct.

As we are bound to solve by Big M method, we can now introduce artificial variable x4 to get
x1+2x2+x3+x4=5

Am I right?
Huh? You already introduced x3 for the slack.
No need to introduce x4 here?? :confused: