Introduction, terminology, the feasible region  (Page 2/2)

Consider again the feasible region described in [link] . Let's say that we have the objective function $f(x,y)=x-2y$ with this feasible region. If we consider Equation  [link] corresponding to

then we get the level line

which has been drawn in [link] . Level lines corresponding to

have also been drawn in. It is very important to realise that these are not the only level lines; in fact, there are infinitely many of them and they are all parallel to each other . Remember that if we look at any one level line $f(x,y)$ has the same value for every point $(x,y)$ that lies on that line. Also, $f(x,y)$ will always have different values on different level lines.

If a ruler is placed on the level line corresponding to $f(x,y)=-20$ in [link] and moved down the page parallel to this line then it is clear that the ruler will be moving over level lines which correspond to larger values of $f(x,y)$ . So if we wanted to maximise $f(x,y)$ then we simply move the ruler down the page until we reach the “lowest” point in the feasible region. This point will then be the feasible point that maximises $f(x,y)$ . Similarly, if we wanted to minimise $f(x,y)$ then the “highest” feasible point will give the minimum value of $f(x,y)$ .

Since our feasible region is a polygon, these points will always lie on vertices in the feasible region . The fact that the value of our objective function along the line of the ruler increases as we move it down and decreases as we move it up depends on this particular example. Some other examples might have that the function increases as we move the ruler up and decreases as we move it down.

It is a general property, though, of linear objective functions that they will consistently increase or decrease as we move the ruler up or down. Knowing which direction to move the ruler in order to maximise/minimise $f(x,y)=ax+by$ is as simple as looking at the sign of $b$ (i.e. “is $b$ negative, positive or zero?"). If $b$ is positive , then $f(x,y)$ increases as we move the ruler up and $f(x,y)$ decreases as we move the ruler down. The opposite happens for the case when $b$ is negative: $f(x,y)$ decreases as we move the ruler up and $f(x,y)$ increases as we move the ruler down. If $b=0$ then we need to look at the sign of $a$ .

If $a$ is positive then $f(x,y)$ increases as we move the ruler to the right and decreases if we move the ruler to the left. Once again, the opposite happens for $a$ negative. If we look again at the objective function mentioned earlier,

with $a=1$ and $b=-2$ , then we should find that $f(x,y)$ increases as we move the ruler down the page since $b=-2<0$ . This is exactly what we found happening in [link] .

The main points about linear programming we have encountered so far are

• The feasible region is always a polygon.
• Solutions occur at vertices of the feasible region.
• Moving a ruler parallel to the level lines of the objective function up/down to the top/bottom of the feasible region shows us which of the vertices is the solution.
• The direction in which to move the ruler is determined by the sign of $b$ and also possibly by the sign of $a$ .

These points are sufficient to determine a method for solving any linear program.