(Page 1 of 7)

 

We can take a problem with only two variables and graph it.   From the graph we can then determine the optimal solution.   While it may be rare that we would need to solve a 2 variable problem in the "real world," understanding the geometry can lead us to better intuition about LPs and how we can solve them.

Lets try this with the following example:

Maximize

x+y

Subject to:

x + 2 y ³ 2

 

x £ 3

 

y £ 4

 

x ³ 0 y ³ 0

 

We first look at the non-negativity constraints.   If x and y are greater than or equal to zero, we only need to concern ourselves with the positive quadrant of our graph.   Therefore, we will start our graphing exercise with the graph on the right.

 

We will now look at our first constraint: x + 2 y >= 2.   We want to find all the points which satisfy this constraint.   We therefore will graph x + 2 y = 2 which will provide the border for the region of points that satisfy it.

We can see that the point (0,0) does not satisfy this constraint, therefore it’s the points above this line that are feasible for this constraint.

 

Our second constraint says that x <=3.   We can add this to the graph.

 

And our final constraint imposes y <= 4 which we can also add to the graph.

 

We now have all our constraints graphed and we can see the region where all the constraints are satisfied.   This is called the feasible region.   Any point in this region satisfies all the constraints, and is called feasible.   Any point outside of this region violates one or more of them, and is called infeasible.

 

Our optimal solution must be feasible, therefore it must lie in the green region.   For each point in this region we can calculate the objective value.   For instance, the point (1,2) has an objective value of 1+2=3.   Our task is to find the point which gives the maximum objective value.   Clearly, (1,2) is not optimal since the point (1,3) has a larger objective value of 4.   But which point has the largest value?   Next we will look at how we find this solution geometrically.