Solve LPP with Charnes Big M Method? Wrong Question?

  • MHB
  • Thread starter Suvadip
  • Start date
  • Tags
    Method
In summary, the conversation discusses the use of the Big M method to solve a linear programming problem with 'less than equal to' constraints. The speaker believes that the simplex method should be used instead and that there is no need to introduce the artificial variable M. However, another speaker points out that the Big M method is a generalization that allows for 'greater than or equal to' constraints and can be used in this case. The conversation also includes an example of how to use the Big M method and clarifies that the slack variable already serves the purpose of M.
  • #1
Suvadip
74
0
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.
 
Mathematics news on Phys.org
  • #2
suvadip said:
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$ ?
 
  • #3
suvadip said:
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.
 
  • #4
mathmari said:
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
2x+y<=8
x,y>=0

Can it be solved by Big M method?
 
  • #5
suvadip said:
No, the LPP was
Max z=2x+3y
subject to
x+y<=8
x+2y<=5
2x+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.
 
  • #6
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.
 
  • #7
I like Serena said:
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.
 
  • #8
suvadip said:
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.
 
  • #9
I like Serena said:
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?
 
  • #10
suvadip said:
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:
 

FAQ: Solve LPP with Charnes Big M Method? Wrong Question?

What is the Charnes Big M method?

The Charnes Big M method is a technique used to solve linear programming problems with constraints. It involves adding an artificial variable with a large coefficient (M) to the objective function in order to convert constraints with inequalities into equations.

How does the Charnes Big M method work?

The Charnes Big M method works by first converting all constraints with inequalities into equations by introducing an artificial variable with a large coefficient (M). Then, the problem is solved using the simplex method to find the optimal solution. If the optimal solution violates the artificial variable's constraints, the value of M is increased and the problem is solved again until a feasible solution is found.

When should the Charnes Big M method be used?

The Charnes Big M method should be used when solving linear programming problems with constraints that include inequalities. It is particularly useful when the problem does not have a feasible solution, as it helps in finding a feasible solution by introducing an artificial variable.

What are the advantages of using the Charnes Big M method?

The Charnes Big M method is advantageous because it can handle both equality and inequality constraints, as well as problems with infeasible solutions. It also allows for the use of the simplex method, which is a powerful tool for solving linear programming problems.

Are there any limitations of the Charnes Big M method?

Yes, there are some limitations of the Charnes Big M method. It can be computationally intensive, as it requires multiple iterations to find a feasible solution. It also relies on the appropriate choice of M, which can be difficult to determine in some cases. Additionally, the method may not work for highly complex problems with a large number of variables and constraints.

Similar threads

MHB Two-Phase Method for Solving LPPs Without Art. Vars.
Replies
1
Views
1K
MATLAB Solving transportation problems (LPP) using linprog in MATLAB
Replies
3
Views
4K
MHB How can the variables m, n, s, and t be solved for these equations?
Replies
2
Views
2K
MHB Solutions of the given linear programming problem
Replies
4
Views
2K
I Optimization problem with multiple outputs: impossible?
Replies
6
Views
2K
Express ##x^3+y^3## in terms of ##m## and ##n##
Replies
17
Views
1K
A The eigenvalue power method for quantum problems
Replies
2
Views
1K
MHB Solve for x⁴+16x-12=0 using effective methods
Replies
8
Views
3K
MHB Implementation of numerical method
Replies
1
Views
2K
MHB Which procedure takes the minimum time to solve modulus functions?
Replies
5
Views
967

Hot Threads

Recent Insights

Back
Top