12.3 Solving the LPP Using the Simplex Method
The Simplex Method is a systematic, tabular approach used to solve linear programming problems involving more than two variables or when a graphical solution is impractical. It iteratively improves the solution by moving from one vertex (corner point) of the feasible region to another, in search of the optimal value of the objective function.
Step 1: Represent the Problem in Tabular Form
We begin by organizing the coefficients of the objective function and constraints into a matrix format:
| Biscuit ([latex]x[/latex]1) | Cupcake ([latex]x[/latex]2) | RHS (Resources) | |
|---|---|---|---|
| Objective (Z) | 5 | 4 | - |
| Mixer | 3 | 5 | 78 |
| Oven | 4 | 1 | 36 |
This corresponds to the original problem:
Maximize: [latex]Z = 5 \times 1 + 4 \times 2[/latex]
Subject to:
Step 2: Convert Inequalities to Equations
To apply the Simplex Method, we convert the inequalities into equalities by introducing slack variables:
- Let [latex]u[/latex] be the slack variable for the mixer constraint
- Let [latex]w[/latex] be the slack variable for the oven constraint
The constraints become:
[latex]\begin{align*} &3 \times 1 + 5 \times 2 + u = 78 \\ &4 \times 1 + 1 \times 2 + w = 36 \\ \end{align*}[/latex]
The initial simplex tableau is then constructed by bringing all terms to the left-hand side and expressing the objective function in standard form (with negative coefficients):
| Basic Variable | [latex]x[/latex]1 | [latex]x[/latex]2 | [latex]u[/latex] | [latex]w[/latex] | RHS |
|---|---|---|---|---|---|
| [latex]Z[/latex] | -5 | -4 | 0 | 0 | 0 |
| [latex]u[/latex] | 3 | 5 | 1 | 0 | 78 |
| [latex]w[/latex] | 4 | 1 | 0 | 1 | 36 |
Step 3: Iterative Optimization
The Simplex Method proceeds by performing pivot operations to eliminate negative values in the objective row. Each iteration improves the value of the objective function by selecting:
- The entering variable (the most negative coefficient in the objective row)
- The leaving variable (determined by the minimum ratio test)
This process continues until there are no negative values in the objective row, indicating that the optimal solution has been reached. The following video illustrates the steps of the simplex method to solve our LPP.
Video: Transportation Problem - NWC Initial Allocation
Video: "Simplex Method, Example 1" by Dr D’s Math Help [7:44] is licensed under the Standard YouTube License.Transcript and closed captions available on YouTube.
