How to Solve a Difficult LP Problem?

  • Thread starter aeronautical
  • Start date
In summary: So to solve the LP problem, first graph the feasible region, then find the vertices (corners), and finally evaluate the objective function at each vertex to determine the minimum value. In summary, to solve the given LP problem, one should graph the feasible region, find the vertices (corners), and evaluate the objective function at each vertex to determine the minimum value. This concept is based on the idea that the maximum or minimum of a linear function on a convex set occurs at a vertex.
  • #1
aeronautical
34
0

Homework Statement



Solve the LP problem?
Minimize -x_{1} - 5x_{2} + x_{3}

when

x_{1} + 3x_{2} + 3 x_{3} <= 4
- x_{1} - 2x_{2} + x_{3} >= -5
3x_{2} - x_{3} <= 3
x_{1}, x_{2}, x_{3} >= 0

Please explain how this process works (with all the steps), thanks.


The Attempt at a Solution



I read somewhere that in order to consider a minimized problem, one shall maximize: -x_{1} - 5x_{2} + x_{3}
 
Physics news on Phys.org
  • #2
aeronautical said:

Homework Statement



Solve the LP problem?
Minimize -x_{1} - 5x_{2} + x_{3}

when

x_{1} + 3x_{2} + 3 x_{3} <= 4
- x_{1} - 2x_{2} + x_{3} >= -5
3x_{2} - x_{3} <= 3
x_{1}, x_{2}, x_{3} >= 0

Please explain how this process works (with all the steps), thanks.


The Attempt at a Solution



I read somewhere that in order to consider a minimized problem, one shall maximize: -x_{1} - 5x_{2} + x_{3}
No, that's not it at all, although minimizing -x1 -5x2 + x3 is equivalent to maximizing +x1 +5x2 - x3. There is also the concept of the dual problem in linear programming, which is more involved than I have time or inclination to explain right now.

For your problem, you have only three variables, so why don't you graph your feasible region? Any potential solution will occur at a corner point, so all you have to do is to evaluation your objective function (-x1 -5x2 + x3), and pick the point that gives you the smallest value.
 
  • #3
The basic concept of LP is that the max or min of a linear function on a convex set occurs at a vertex. Find the vertices of the set (the points where the bounding planes intersect) and evaluate the object function at each one to determine where it is a minimum.
 

1. What is a difficult LP problem?

A difficult LP (linear programming) problem is a type of optimization problem that involves finding the maximum or minimum value of a linear objective function while satisfying a set of linear constraints. The difficulty of a LP problem can vary depending on the number of variables and constraints, as well as the complexity of the objective function and constraints.

2. How can I solve a difficult LP problem?

There are several methods for solving difficult LP problems, including the simplex method, interior point methods, and branch and bound algorithms. The most suitable method will depend on the specific characteristics of the problem, such as the size and complexity of the constraints.

3. What makes a LP problem difficult to solve?

A LP problem can be difficult to solve due to a variety of factors, such as a large number of variables and constraints, nonlinearity in the objective function or constraints, or the presence of integer or binary variables. These factors can increase the computational complexity of the problem and make it more challenging to find an optimal solution.

4. Can a difficult LP problem have multiple optimal solutions?

Yes, it is possible for a difficult LP problem to have multiple optimal solutions. This is known as degeneracy and can occur when the constraints are parallel or redundant, leading to more than one solution that satisfies the objective function and constraints. In some cases, degeneracy can also cause difficulties in the solution process and result in longer computation times.

5. Are there any practical applications of difficult LP problems?

Yes, difficult LP problems have many practical applications in various fields such as economics, operations research, and engineering. They can be used to optimize resource allocation, production planning, transportation routing, and other decision-making processes. Many real-world problems can be formulated as LP problems and solved to find the most efficient and effective solutions.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
777
  • Calculus and Beyond Homework Help
Replies
1
Views
540
  • Precalculus Mathematics Homework Help
Replies
3
Views
829
  • Calculus and Beyond Homework Help
Replies
2
Views
879
  • Calculus and Beyond Homework Help
Replies
3
Views
985
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
923
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
Back
Top