Big M method of LPP

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

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

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

Member
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
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??