• Support PF! Buy your school textbooks, materials and every day products Here!

A difficult LP problem

  • #1

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}
 

Answers and Replies

  • #2
33,169
4,854

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
HallsofIvy
Science Advisor
Homework Helper
41,793
922
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.
 

Related Threads for: A difficult LP problem

  • Last Post
Replies
1
Views
1K
Replies
6
Views
1K
Replies
1
Views
1K
Replies
4
Views
1K
  • Last Post
Replies
1
Views
1K
Replies
1
Views
564
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
797
Top