How to Solve a Difficult LP Problem?

[aeronautical]

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}

 

[Mark44]

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 -x₁ -5x₂ + x₃ is equivalent to maximizing +x₁ +5x₂ - x₃. 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 (-x₁ -5x₂ + x₃), and pick the point that gives you the smallest value.

 

[HallsofIvy]

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.