Graphical and Simplex Method of Solving LP Problems

Linear Programming (LP) is a versatile tool in optimization which has wide applications in manufacturing, logistics, finance and resource management industries. The two most basic techniques to solve LP issues are the Graphical Method, and the Simplex Method. Each is appropriate for different problem dimensions and complexity levels.

In this article we’ll delve deeper into both methods , highlight the differences between them and answer the most frequently asked questions encountered in LP problem-solving.

What is Graphical and Simplex Method of Solving LP Problems?

Linear Programming is a mathematical technique for finding the most optimal resources, for example maximum profit, minimum cost within defined linear constraints. It involves:

Decision variables (quantities to determine)
Objective function (to optimize)
Constraints (resource limits)

1. The Graphical Method

What is the Graphical Method?

The Graphical Method represents a visual way of solving LP-problems with two variables of the decision. It encourages intuitive comprehension and is great for teaching basic concepts of LP.

Steps to Solve an LP Problem Using the Graphical Method:

Step 1: Define Decision Variables

Let’s assume:

$x_1$ : units of Product A
$x_2$ : units of Product B

Step 2: Write the Objective Function

Example:

Maximize $3x_1 + 5x_2$

Step 3: Write Constraints

Example:

$2×1+x2≤1002x_1 + x_2 \leq 100$
$x1+2×2≤80x_1 + 2x_2 \leq 80$
$x1,x2≥0x_1, x_2 \geq 0$

Step 4: Graph the Constraints

Plot each constraint line on the coordinate plane.
Identify the feasible region where all constraints overlap.

Step 5: Find Corner Points

Corner points (vertices) of the feasible region are potential solutions.

Step 6: Evaluate the Objective Function

Plug in the corner points on the objective function and determine the one with the highest (or lowest) value according to the aim.

When to Use the Graphical Method

When there are only two decision variables
For educational purposes or conceptual understanding

The Graphical Method: A Visual Approach (for Two Variables Only)

The graphical method is a visual approach that’s best suited for linear programming problems involving only two decision variables (x1 and x2). Here’s a breakdown of the steps involved:

Plotting the Constraints: Each constraint is represented as a line on the graph. Convert each constraint equation (like Ax + By ≤ C) to slope-intercept form (y = mx + b) to plot the line.
Shading the Feasible Region: Identify the valid portion of the graph that satisfies all the constraints. This shaded area represents the feasible region where all the constraints are met simultaneously.
Introducing the Objective Function: The objective function (usually maximizing profit or minimizing cost) is depicted as a line with a variable slope. By moving this line (without changing its slope), you’re essentially exploring different possible solutions.
Identifying the Optimal Point: The optimal solution lies on the corner point of the feasible region where the objective function line touches it. This corner point represents the values for x1 and x2 that optimize the objective function.

Strengths and Limitations of the Graphical Method:

Strengths:
- Easy to visualize and understand, especially for beginners.
- Provides a clear geometric interpretation of the solution space.
Limitations:
- Applicable only to problems with two decision variables.
- Becomes cumbersome and impractical for problems with more variables.

2. The Simplex Method

What is the Simplex Method?

The Simplex Method is an Algebraic procedure used for solving LP problems which contain two or more variables. It is better applicable to large scale and complex problems.

How the Simplex Method Works

It starts at a feasible solution (normally at the origin or one vertex in the feasible region) and moves along the edges in the feasible region until it obtains the optimal value of the objective function.

Basic Terminology:

Tableau: A matrix used to organize coefficients
Basic variables: Variables included in the current solution
Non-basic variables: Variables not included (set to zero)
Pivot: The process of changing the basic variable in the tableau to move toward optimality

Steps in the Simplex Method:

Step 1: Convert the LP Problem to Standard Form

All constraints must be in the form: $≤\leq$
Add slack variables to convert inequalities to equalities

Step 2: Set Up the Initial Simplex Tableau

Create a matrix (tableau) with:

Coefficients of decision variables
Slack variables
Right-hand side (RHS) values

Step 3: Identify the Pivot Column and Pivot Row

Choose the most negative value in the objective function row as the pivot column.
Use the minimum ratio test to choose the pivot row.

Step 4: Perform Pivoting

Use elementary row operations to make pivot element = 1, and other entries in the pivot column = 0.

Step 5: Repeat

Continue iterations until no negative values remain in the objective function row—indicating an optimal solution.

When to Use the Simplex Method

When there are more than two variables
For large and complex LP problems
When using software tools like Excel, MATLAB, or Python

The Simplex Method: A Powerful Workhorse (for Any Number of Variables)

The simplex method is an iterative algorithmic approach that can handle linear programming problems with any number of decision variables. It works by systematically evaluating different corner points of the feasible region to find the one that optimizes the objective function. The method involves a series of calculations and pivoting techniques to move from one vertex to another until the optimal solution is reached.

Strengths and Limitations of the Simplex Method:

Strengths:
- Can solve problems with any number of decision variables.
- Efficiently handles complex linear programming models.
- Widely used in practice due to its effectiveness and automation potential.
Limitations:
- Can be computationally intensive for very large problems (although advancements in algorithms are improving this).
- The underlying calculations might not be as intuitive as the graphical method for beginners.

Comparison: Graphical vs. Simplex Method

Feature	Graphical Method	Simplex Method
Variables	Only 2	Two or more
Type	Visual	Algebraic
Application	Educational, simple problems	Complex, large-scale problems
Tools needed	Graph paper or plotting tool	Spreadsheet, coding, or solver
Speed	Fast for small problems	Fast for large problems using automation

Applications of LP Solving Methods

Both methods are widely used in various fields:

Manufacturing: Product mix optimization
Logistics: Transportation and routing
Finance: Portfolio optimization
Project Management: Resource allocation
Healthcare: Staff scheduling

Software for Solving LP Problems

You can apply the Simplex Method using:

Excel Solver: Built-in LP solver in Excel
LINDO/LINGO: Specialized software for LP
Python: Libraries like PuLP, SciPy
MATLAB: linprog() function

These tools speed up computations and reduce errors.

FAQ: Graphical and Simplex Method of Solving LP Problems

Q1: What is the major limitation of the Graphical Method?

It is applicable to solve only two decision variable LP problem. Beyond that the visual representation is impossible.

Q2: Is the Simplex Method always accurate?

Of course, if used properly, the Simplex Method provides an optimal solution for the feasible and bounded LP problems.

Q3: How do I know which method to use?

Use the Graphical Method for simple problems with 2 variables.
Use the Simplex Method for problems with 3 or more variables or when the problem is complex.

Q4: Can both methods yield the same result?

Yes. For 2-variable issues, both the Graphical and the Simplex methods will reach the same optimal solution – though in different ways.

Q5: What happens if an LP problem has multiple optimal solutions?

In the Graphical method this manifests as the objective line overlapping one of the edges of the feasible region. It will be shown when the reduced cost to a non-basic variable is zero in the Simplex Method.

Q6: Can the Simplex Method be done by hand?

Technically, yes—but it is tedious for anything more than a basic problem. Software tools are strongly recommended.

Q7: What is degeneracy in LP?

Degeneracy happens only if a basic variable takes a value at zero. It may result in cycling, when the algorithm is spinning without improving. Modern solvers prevent this.

Q8: How long does it take to solve an LP problem using these methods?

Graphical Method: A few minutes
Simplex Method: Varies with complexity; seconds to minutes with software

In Conclusion

The graphical method though with limited variables provides a great learning tool for understanding the concept of linear programming. Contrarily, simplex method is the formidable workhorse to solve practical world LP problem because of its scalability and efficiency. The choice between them is based on the complexity of your problem. For two-variable problems the graphical method shows specifically what is wrong. For the more problems with variables, the simplex method is the recommendation method and for calculation purposes you can use the solver software to do the calculation automatically.