Linear Programming 003 : Graphical Solution

Alright then! We know what linear programming is, what kind of problems it can be used to solve and how these kind of problems can be formulated. So let the solutions begin!!

To start with, we take a two variable linear programming problem (we spare ourselves the formulation this time) and try to discover a solution for it. I shall try my best to structure these articles to fashion discovery of knowledge rather than stating in placidly. Hence, I will leave out some pause points beyond which the readers would have a couple of options — Pause and ponder about the solution given the information above or move ahead to read the solution. I would prefer the former approach since there is nothing better and more effective than discovering a method yourself.

That said, let’s get cracking on the problem at hand. The two variable problem that we will discuss in the solution below is mentioned below:

Okay, so what do we have then? We have two variables x1 and x2 right? Let’s assume we have a piece of paper before us so what we can do before anything at all is draw the equations and inequalities on a graph. Let’s do that to start with.

We first plot the line 2x1 + x2 = 100 in the figure below. A few things to note are mentioned thereafter:

1. We all know how to plot the line representing a linear equation from high school
2. What we may not know or remember is that the plot of a line actually represents two inequalities along with one equation
3. This has been clearly represented in the image below
4. The horizontal axis represents the x1 coordinates and the vertical axis represents the x2 coordinates
5. The line represents the equation of the first constraint
6. The region shaded by the reddish hue represents the inequality 2x1 + x2 <= 100

How so? Well every line divides the plane on which it is plotted into two distinct regions. In the field of convex optimisation, we refer to these regions as affine half-spaces. If the line is of the form:

Then the two half-spaces represent the following inequalities:

In our case, the line represents the equation of the first constraint. The half-space shaded in red represents the inequality 2x1 + x2 <= 100 and the half-space left unshaded represents the inequality 2x1 + x2 >= 100

In order to validate this we consider two points one in each region as mentioned in the table below:

Now that we know how to represent inequalities on a graph, I would encourage the user to try and find a method to plot at least one feasible point that satisfies all the constraints of our problem in the green box. This is our first pause and ponder point. You may choose to pause here and ponder a bit to find this method or read ahead to find the solution mentioned for you.

What I have done below is plotted all the inequalities representing our constraints using one graph or set of axes representing our decision variables. The figure so framed is given below:

As can be clearly seen points representing each inequality are shaded using a different color and the intersection of all these sets of points can be clearly bounded by the polygon ABCDE

Hence, we can clearly state that any point within the interior of the polygon ABCDE will end up satisfying all the constraints of our problem and hence is called a Feasible Point.

The set of these feasible points is called the Feasible region of a linear program.

For the sake of clarity, I have mentioned below the steps that can be used to find out the feasible region of any linear program:

1. Plot all the inequalities using a single set of axis representing the decision variables of the problem
2. Find the region that is an intersection of all regions satisfying each equation
3. This intersection will be the feasible region of the problem

Now that we have that down, we just need one additional concept before moving on to the full fledged solution of our problem.

Isoprofit / Isocost lines:

We know that the objective of our problem is to maximize the value of Z = 3x1 + 2x2. Now the equation 3x1 + 2x2 = c1 represents a line. Each point on this line has the same value of Z which is c1. Each such line for which the value of the objective function stays the same is called an isoprofit or an isocost line for maximization and minimization problems respectively.

Note that if we change c1 arbitrarily, the line simply shifts parallel to itself but the slope of the line stays the same. This fact is represented in the figure below.

Alright then … Now you know everything that one needs to know in order to figure out the solution of our problem. Thus it is appropriate to pause and ponder a bit regarding a generic method to solve any two variable LP using a graph.

The Solution

Finally, after all that necessary jargon, we arrive at a point where we can finally solve this linear programming problem by the graphical method. So speak the truth, most of you must already know the solution by now if you have grasped the concept of isoprofit and isocost lines. However, in order to make things more concrete, we shall walk through the solution step by step.

We know two things by now for sure:

1. All points satisfying the constraints of our problem are contained within a polygon (in our case — the polygon ABCDE)
2. The slope of our objective function never changes — It just shifts parallel to itself as per the value of Z

The problem is that the interior of the polygon ABCDE has an infinite number of points so we cannot employ an exhaustive search to find out the point that renders the best or the most optimal value for our objective function.

When faced with such an infinite search space problem, it is common practice in mathematics and computer science to use a heuristic in order to reduce the this search space to a smaller, preferably finite set. Can we do so in this case?

If you look at the last figure, pick one particular Z = c1 line and shift it parallel to itself, you will find that when shifter to the left the value of Z decreases and when shifted to the right the value of Z always increases. Hence if we take the Z = 0 line passing through the origin and keep moving it to the right (thus increasing the value of Z), we would reach a point where there is only one point in common between our isoprofit line Z = c1 and our feasible region, the polygon ABCDE. If we move the line any further to the right, we will end up increasing Z but violating at least one of our constraints. It can also be intuitively understood that this point where the Z line and the polygon have exactly one point is common has to be one of the vertices of our polygon. Hence using the heuristic above, we can safely say that the optimal point of our problem must lie at one of the vertices of our feasible region — the polygon ABCDE. Therefore each of these vertices is called a basic feasible solution. We shall find out the reason behind this nomenclature in the next article.

Thus, we have reduced the search space from an infinite set to the set of vertices of the feasible region of a LP — in this case the set of points S = {A,B,C,D,E}. If we are able to evaluate the value of Z at these 5 points, we shall be able to identify the optimal solution to this problem. This is exactly what we do below:

Great, now that we have evaluated the Z value at all points, we can assuredly say that the optimum of our linear program lies at point B. Thats it … Done … Solved.

So in summary, the step by step algorithm to solve a linear programming problem is listed below:

1. Plot the inequalities that represent the constraints of the problem
2. Find out feasible region of our problem
3. Evaluate Z at each vertex of the feasible region
4. The vertex that renders the best value for the objective function is the optimum of the problem.

Well, that was rather easy wasn’t it? Yes but the subject of linear programming is only just getting interesting. We are now able to solve linear programs with the graphical method but most situations one would encounter in real life would contain more than two decision variables. In such a case we, with our primitive visual sense, cannot possibly employ this method since we cannot possibly draw a graph in 6 or 7 or more dimensions. What then? Fortunately mathematicians have developed a fantastic tool using algebra that enables us to solve programs in almost as many variables as we wish. This is where and why we part from our geometry boxes and move on to the language of mathematics — algebra. We begin to discuss this method in the next article.

Next Article

Auxiliary Material:

The above method does seem to be robust for any and all linear programming problem in two variables but is it really. Let us address a few popular concerns regarding its robustness.

Are all feasible regions contained within polygons?

Certainly not. There might be a set of constraints that lead to an unbounded feasible region or another set where the feasible region in a void set. It is left to the user to ponder over these cases. I believe the information given above is enough to find your way through these cases.

Can a linear program have more than one optimum?

Well, for instance can the Z line be parallel to one of the sides of our polygon? If yes the yes