Linear Programming: Graphic Solution

In the previous article, you studied that linear programming is a method of achieving the optimum outcome for a maximum or a mini- mum equation with linear constraints.

Once the mathematical model of a linear programming problem has been formulated, the next phase in applying linear programming to a decision-making problem is to find the solution of the model.

An LP problem can be solved by using multiple methods, with graphical and simplex methods being the most popular. An LP problem that involves two variables in a linear relationship can be easily solved with the help of graphical method. When there are only two variables in the problem, most of the analysis can be performed on a two-dimensional graph.

Graphical method helps in showing all the feasible solutions that are present within the feasible area on the graph. The feasible area’s corner points are tested by putting these values in the objective function for determining the optimal solution.

A major advantage of using the graphical approach is its visual nature. It helps us gain a visual representation of the algebra of LP, which in turn supports our understanding of the key concepts. But when an LP problem involves three or more variables, trying to solve the problem by drawing its graph is very difficult. In such cases, the simplex method developed the simplex method is used, developed by G.B. Dantzig is used.

Methods for Solving Linear Programming Problems

As you might recall from the last article, a linear programming problem is one where you need to optimise (maximise or minimise) a linear objective function, subject to constraints in the form of linear inequalities or equations. In this section of the article, you are going to discuss how you can solve such LP problems.

Graphical Method

The graphical method is used to solve a linear program involving only two decision variables that can be represented on a graph of two dimensions. While it is not impossible to graph LP models with three decision variables in three dimensions, it is a very difficult and complicated task to perform, and LP models with four or more decision variables are impossible to graph at all. Despite the limitation of being useful for only two decision variables, the graphical method is still very valuable as it enables the visualisation of the algebra of LP and how a solution is obtained in LP.

When the graphical method is used to determine the optimal solution to the LP problem, the fundamental theorem of linear programming is applied, which states that:

• The set of all feasible solutions to an LP problem is represented by a convex polygon whose extreme points correspond to the basic feasible solutions. In case this, a convex polygon is a convex polyhedron, then at least one of the extreme points gives an optimal solution.
  
  
• The number of basic feasible solutions within the feasible area is finite.
  
  
• If more than one extreme point corresponds to the optimal solution, then the value of the objective function will be the same for all these extreme points.
  
  
• The maximum value for the objective function does not exist for an unbounded feasible region.
  
  
• A minimum value for an unbounded feasible region exists if the objective function has only positive coefficients.

For LP problems involving more than two variables or those involving a large number of constraints, graphical methods are not suited. In such cases, solution methods that are adaptable to computers are more appropriate.

The simplex method is one such approach. This method presents a systematic approach for evaluating the vertices of a feasible region, which then allows you to figure out the optimal value of the objective function. You will study more about the simplex method in the next article.

Graphical Solution of a Linear Programming Problem

The graphical solution of an LP problem involves the following steps:

• Represent the problem in a mathematical form by formulating the mathematical model. For this, decode the given situations or constraints into equations or inequalities.
  
  
  
• Draw x1 and x2 axes. The values of x1 and x2 variables can only lie in the first quadrant because of the non-negativity constraints x1 ≥ 0 and x2 ≥ 0. Infeasible alternatives that lie in the 2nd, 3rd and 4th quadrants are thus removed.
  
  
  
• Plot each of the problem constraints, whether equations or inequalities, as equations on the graph. For each of the constraints, obtain the value of one variable by assigning an arbitrary value to the other variable.
  
  Then, assign a different arbitrary value to the first variable and obtain the value of the other variable. Now plot these two points and join them with a straight line. Each constraint is thus plotted as a line in the first quadrant.
  
  
  
• Identify the feasible solution area that satisfies all the constraints simultaneously. The feasible region is the area common to all the constraints and is usually depicted as a shaded region. Any point that lies within or on the boundary of this shaded region depicts a feasible solution.
  
  The feasible region is a convex polygon formed by the intersection of a finite number of half-planes.
  
  
  
• Plot the objective function by assuming Z = 0. This is a line passing through the origin. Increasing the value of Z moves the line parallelly to the right. For a maximisation problem, draw a line parallel to this line till it is farthest from the origin.
  
  For a minimisation problem, draw a line parallel to this line till the line is closest to the origin. The optimal point is the point where this line passes through the feasible region.

Now, you know the basic steps of the graphical method to solve an LP problem. Know that graphical methods can be classified into two types as

• Extreme Point Enumeration Approach
• ISO-profit (Cost) Function Line Approach

Extreme Point Enumeration Approach

An extreme point or vertex is a unique point where a hyperplane inter- sects. The extreme point enumeration approach of graphically solving an LP problem is based on the principle of extreme value theorem which states that if f is a continuous function over a closed, bounded interval, then there is a point in the interval at which f has an absolute maximum and there is also a point at which f has an absolute minimum value.

The various steps involved in this approach are as follows:

• Identify the decision variables, constraints and objective of the problem.
  
  
• Formulate the mathematical model of the problem.
  
  
• Plot each of the problem constraints as an equation on the graph Each one will geometrically represent a straight line.
  
  
• Identify the common region that satisfies all the constraints simultaneously. It is a convex polygon formed by the intersection of a finite number of half-planes.
  
  
• Determine the vertices of the convex polygon. These vertices are called the extreme points of the feasible region.
  
  
• Find the coordinates of each extreme point/vertex of the feasible region. Determine the values of the objective function at each extreme point. The optimal point is the extreme point at which the value of the objective function is optimum (maximum or mini- mum) and its coordinates give us the optimal solution.

ISO-profit (Cost) Function Line Approach

The Iso-profit (cost) function line method is another approach to find the optimum point in a graphic linear programming problem. After graphing the feasible region, the point lying in the feasible region that produces the highest profit is the optimal solution to the problem. The term Iso-profit (cost) implies that any combination of points generates the same profit (cost) as any other combination on the same line.

The various steps involved in this approach are as follows:

• Identify the decision variables, constraints and objective of the problem.
  
  
• Formulate the mathematical model of the problem.
  
  
• Plot a graph taking in all the constraint equations of the problem and identify the feasible region. The feasible region is the intersection of the regions satisfying all the constraints. As you read earlier, it is restricted to the first quadrant only. The feasible region obtained in this step may be bounded or unbounded.
  
  
• Identify the common region that satisfies all the constraints simultaneously. It is a convex polygon formed by the intersection of a finite number of half-planes.
  
  
• Determine the corner points of the feasible region.
  
  
• Calculate the coordinates of all the corner points of the feasible region.
  
  
• Give a suitable value k to the objective function Z and draw the corresponding straight line in the xy plane so that it lies within the feasible region. This is the iso-profit (iso-cost) function line.
  
  
• Draw the iso-profit (iso-cost) function line parallel to itself till the line is farthest from the origin (for highest possible profit) or closest to the origin (for lowest possible cost). Each such line for which the value of the objective function remains the same is called an iso-profit line for maximisation problems, or an iso-cost line for minimisation problems.
  
  
• Determine the optimum solution with the coordinates of the point where the highest possible iso-profit or lowest possible cost line passes on the feasible region.

Important Terms of Linear Programming for Graphic Solution

• Solution of LPP: The solution of the LPP is a set of values of the variables xl, x2…., xn that satisfies the constraints.
  
  
• Basic feasible solution: A basic feasible solution is a set of values of the variables xl, x2…., xn that satisfies all constraints along with the non-negativity restrictions.
  
  
• Optimum basic feasible solution: A basic feasible solution becomes optimum if it also optimises the objective function.
  
  
• Feasible region: The region in the graph that satisfies all the constraints is known as the feasible region.
  
  
• Corner point: A corner point is a point that falls along the corner of a feasible region.
  
  
• Bounded set: A set which consists of a boundary around the feasible set is referred as the bounded set. An LP problem (with a bounded set) always has an optimal solution. In other words, a bounded set has a maximum value as well as a minimum value.
  
  
• Unbounded set: A set that has no boundary and continues indefinitely is known as an unbounded set. An optimal solution for an LP problem with an unbounded set may or may not be possible, but in case an optimal solution does exist, it occurs at a corner point.
  
  
• Unbounded solution: Those solutions where the objective function’s value can be increased or decreased indefinitely are called unbounded solutions.
  
  
• Fundamental extreme point theorem: The fundamental extreme point theorem states that if an optimum solution for an LP problem exists, it occurs at one of the extreme points or corner points of the convex polygon of the set of all feasible solutions.
  
  
• Fundamental theorem of LP: This includes the following points:
  • If there is a solution to a bounded LP problem, it occurs at one of the corner points of the convex polygon of the set of all feasible solutions.
  • The maximum value for the objective function does not exist for an unbounded feasible region.
  • A minimum value for an unbounded feasible region exists if the objective function has only positive coefficients.