(page 5 of 7)

 

Lets look at one more example and then we'll draw some conclusions.

Minimize

x + 1/3 y

Subject to:

x + y ³ 20

 

-2 x + 5 y £ 150

 

x ³ 5

 

x ³ 0 y ³ 0

 

This time around we will do things more quickly. To the right you have a graph of the non-negative quadrant (representing the non-negativity constraints) and the three constraints.

What does the feasible region look like in this case?

 

Our feasible region goes on forever off to the right. This region is called "unbounded" because we can go in one direction forever. For instance, the point (x, 10) is feasible for any positive x greater than 10 - no matter how large!

 

We will next look at our objective function. Here we have graphed x + 1/3 y = 30.

Now we would like to minimize our objective function, so we want to move this constraint so as to find solutions with lower objective values, i.e. in the direction of the arrow.

And rather than take incremental steps this time, lets just move it as far as we can in that direction in one bold move!

 

And there we have it. We have moved our objective function as far as we can. If we move it any further we will leave the feasible region. Therefore we have found our optimal solution at (5,15) with an objective value of 10.

 

Lets look again at our objective function. What would have happened if we had wanted to maximize it? Now our arrow would point the other way and we would be encouraged to move the objective function as far as we could in that direction.

Well, we could keep pushing out the objective function forever. It would never leave the feasible region because our feasible region is unbounded in that direction. We call this an "unbounded LP" and there is no optimal solution.

So we solved another 2 variable LP. This time we had an unbounded feasible region. Depending on the objective function, this may cause no problems in solving the LP and we can find an optimal solution. But in other cases it will lead to an unbounded LP and there will be no optimal solution.