The Extremum Point Theorem
You may have noticed that the optimum in a linear programming
problem is always found at one of the vertices of the feasible region.
This is the essence of the Extremum Point Theorem:
The
maximum or minimum of an objective function if it exists always
corresponds to a feasible solution located at the vertices of the
feasible region.
You may notice a couple of interesting things suggested by the
wording of the theorem.
- The words "or minimum" suggest that linear programming
can be used to solve situations when the objective is to find a
minumum that satisfies a set of constraints. Up to
now we have only been considering maximizing an objective function.
How will the graphical approach change if we are trying to minimize
the objective function instead? For example, if instead of trying to
maximize yield without spending over $60 (our original problem) our
farmer wanted to get a yield of at least 75 tonnes per hectare
spending as little money as possible? Now the constraints are
x≥2 (that is, he is already committed to
buy two bags of high-grade),
x+y≤9 (that is, he can store no
more than 9 bags) and 18x+8y≥75
(that is, yield must be at least 75 tonnes). The objective then
becomes to minimize
18x+8y.
Use the applet to explore this new situation. (Note that the applet
is designed to two ≤ constraints and one ≥ constraint, but in
this problem we want one ≤ and two ≥. We can get around this by
entering the first constraint as -x≤-2.
Can you see that this does not change the constraint?)
Find the
solution to the nearest 0.1. (We are not restricted to integer
solutions.)
- The words "if it exists" suggest that there may be
situations where no maximum or minimum exists. There are two
different situations where no maximum exists, and one situation where
an infinite number of solutions give the same maximum. The same
situations exist if you are looking for a minimum, although the
non-negativity constraint usually takes care of one of the situations.
Use the applet to find:
- a situation where no maximum or minimum can be found for the objective
- a situation where a minimum but no maximum can be found
- a situation where a maximum can be found, but no minimum exists
unless non-negativity constraints are imposed
- a situation with an infinite number of points that give an equal
maximum
Make sure you have a go before looking at the answers. You'll
remember and understand it better if you can work it out for yourself.