Graphical Solutions of LLP

Owing to the importance of linear programming models in various industries, many types of algorithms have been developed over the years to solve them. Some famous mentions include the Simplex method, the Hungarian approach, and others. Here we are going to concentrate on one of the most basic methods to handle a linear programming problem i.e. the graphical method.

In principle, this method works for almost all different types of problems but gets more and more difficult to solve when the number of decision variables and the constraints increases.

We will first discuss the steps of the algorithm:

Step 1: Formulate the LP (Linear programming) problem

We have already understood the mathematical formulation of an LP problem in a previous section. Note that this is the most crucial step as all the subsequent steps depend on our analysis here.

Step 2: Construct a graph and plot the constraint lines

The graph must be constructed in ‘n’ dimensions, where ‘n’ is the number of decision variables. This should give you an idea about the complexity of this step if the number of decision variables increases.

One must know that one cannot imagine more than 3-dimensions anyway! The constraint lines can be constructed by joining the horizontal and vertical intercepts found from each constraint equation.

Step 3: Determine the valid side of each constraint line

This is used to determine the domain of the available space, which can result in a feasible solution. How to check? A simple method is to put the coordinates of the origin (0,0) in the problem and determine whether the objective function takes on a physical solution or not. If yes, then the side of the constraint lines on which the origin lies is the valid side. Otherwise it lies on the opposite one.

Step 4: Identify the feasible solution region

The feasible solution region on the graph is the one which is satisfied by all the constraints. It could be viewed as the intersection of the valid regions of each constraint line as well. Choosing any point in this area would result in a valid solution for our objective function.

Step 5: Plot the objective function on the graph

It will clearly be a straight line since we are dealing with linear equations here. One must be sure to draw it differently from the constraint lines to avoid confusion. Choose the constant value in the equation of the objective function randomly, just to make it clearly distinguishable.

Step 6: Find the optimum point

Optimum Points

An optimum point always lies on one of the corners of the feasible region. How to find it? Place a ruler on the graph sheet, parallel to the objective function. Be sure to keep the orientation of this ruler fixed in space. We only need the direction of the straight line of the objective function. Now begin from the far corner of the graph and tend to slide it towards the origin.

• If the goal is to minimize the objective function, find the point of contact of the ruler with the feasible region, which is the closest to the origin. This is the optimum point for minimizing the function.
• If the goal is to maximize the objective function, find the point of contact of the ruler with the feasible region, which is the farthest from the origin. This is the optimum point for maximizing the function.

Step 7: Calculate the coordinates of the optimum point.

This is the last step of the process. Once you locate the optimum point, you’ll need to find its coordinates. This can be done by drawing two perpendicular lines from the point onto the coordinate axes and noting down the coordinates.

Otherwise, you may proceed algebraically also if the optimum point is at the intersection of two constraint lines and find it by solving a set of simultaneous linear equations. The Optimum Point gives you the values of the decision variables necessary to optimize the objective function.

The Graphical Method (graphic solving) is an excellent alternative for the representation and solving of Linear Programming models that have two decision variables.

Exercise #1: A workshop has three (3) types of machines A, B and C; it can manufacture two (2) products 1 and 2, and all products have to go to each machine and each one goes in the same order; First to the machine A, then to B and then to C. The following table shows:

• The hours needed at each machine, per product unit
• The total available hours for each machine, per week
• The profit of each product per unit sold

Formulate and solve using the graphical method a Linear Programming model for the previous situation that allows the workshop to obtain maximum gains.

Decision Variables:

• : Product 1 Units to be produced weekly
• : Product 2 Units to be produced weekly

Objective Function:

Maximize2 

Constraints:

The constraints represent the number of hours available weekly for machines A, B and C, respectively, and also incorporate the non-negativity conditions.

For the graphical solution of this model we will use the Graphic Linear Optimizer (GLP) software. The green colored area corresponds to the set of feasible solutions and the level curve of the objective function that passes by the optimal vertex is shown with a red dotted line.

The optimal solution is  and  with an optimal value  that represents the workshop’s profit.