|
|
(page 2 of 7) |
|
We can now look at our objective function. If we plot the line x + y = c for some constant c, all points on this line will have an objective value of c. For instance, the blue line is x + y = 4. The points along this line have an objective value of 4. Can we do better than this? |
|
|
We want to maximize our objective function, so if we move the blue line in the direction of the arrow, we will be improving our objective value. Here we have moved it to x + y = 5. All points on this line have an objective value of 5. Those points on the line that are within the green region are feasible solutions with an objective value of 5. This is better than our previous objective value of 4, but can we do even better? |
|
|
This time we will try x + y = 6. Now we have feasible solutions with an objective value of 6. The point (2,4) is one such point. We are improving our objective value, but can we still do better? What happens if we try x + y = 7? |
|
|
Indeed we still have a feasible solution that lies on our line. Namely, (3,4) has an objective value of 7. But can we do better than this? Notice that if we push the objective function any further in the direction of the arrow, the line will lie entirely outside of our feasible region. This means that we can't improve any further and we have found our optimal solution. |
|
|
The point (3,4) is the feasible solution that optimizes our objective function, therefore we call it the optimal solution.
Notice that the optimal solution lies on two of the constraints. We call these active or binding constraints. The constraint   x + 2y >= 2   is non-binding. In fact, at our optimal solution, x + 2y = 3 + 2(4) = 11. The slack of this constraint then is 11-2 = 9. |
|
|
So, we just took a 2 variable LP and solved it graphically. We first plotted all the constraints in order to find the feasible region. We then pushed the objective function as far as we could before leaving the feasible region. This showed us where our optimal solution was. We will now look at another example. |
|
|