Simplex Method: Definition and Solving Linear Programming

Simplex Method: Definition and Solving Linear Programming

Simplex Method: Definition and Solving Linear Programming
6 min read

The simplex method is an algebraic procedure for solving linear programming problems, that is, optimizing (maximizing or minimizing) a linear objective function subject to linear inequality constraints. It was developed by George Dantzig in 1947 and is the basis of much optimization software. Unlike the graphical method, which is practical only for two variables, simplex can handle many variables.

Basic concept

The solution of a linear programming problem lies at a corner point (extreme point) of the feasible region. Simplex moves from one corner point to an adjacent corner point that improves the objective value, until no further improvement is possible. The last point is the optimal solution.

Steps

  • Convert to standard form: for ≤ constraints, add slack variables to make them equations. A maximization objective is written as Z - c1x1 - c2x2 = 0.

  • Build the initial simplex tableau with the basic variables (initially the slacks).

  • Choose the pivot column: the column with the most negative value in the Z row (the entering variable).

  • Choose the pivot row with the ratio test: divide the right-hand side (RHS) by the positive entries in the pivot column and pick the smallest ratio (the leaving variable).

  • Perform row operations (Gauss-Jordan elimination) so the pivot element becomes 1 and the other entries in the pivot column become 0.

  • Check optimality: if there are no negative values in the Z row (for maximization), the solution is optimal. If there are, repeat from step 3.

Example problem

Maximize Z = 3x1 + 2x2 subject to:

  • x1 + x2 ≤ 4

  • x1 + 3x2 ≤ 6

  • x1 ≤ 3

  • x1, x2 ≥ 0

Standard form

Add slacks s1, s2, s3: x1 + x2 + s1 = 4, x1 + 3x2 + s2 = 6, x1 + s3 = 3, and Z - 3x1 - 2x2 = 0.

Iteration 1

  • Pivot column: x1 (coefficient -3 is the most negative).

  • Ratio test: 4/1 = 4, 6/1 = 6, 3/1 = 3. The smallest is 3 in the third row, so s3 leaves and x1 enters.

  • Result: x1 = 3, s1 = 1, s2 = 3, and Z = 9.

Iteration 2

  • The Z row still contains x2 with coefficient -2, so x2 enters.

  • Ratio test: the s1 row = 1/1 = 1, the s2 row = 3/3 = 1 (a tie, a degenerate case, pick either one).

  • Result: x2 = 1 and Z = 9 + 2 × 1 = 11.

There are no more negative coefficients in the Z row, so the optimal solution is x1 = 3, x2 = 1, Z = 11. You can verify this: 3 + 1 = 4 (satisfied), 3 + 3 = 6 (satisfied), and 3 ≤ 3 (satisfied).

Special cases

  • ≥ constraints or equalities require artificial variables with the Big-M or two-phase method.

  • Minimization can be converted to maximization by multiplying the objective by -1, or solved with the dual method.

  • An unbounded solution occurs when there is no positive ratio in the pivot column. Alternative optimal solutions occur when a non-basic variable has a 0 coefficient in the Z row of the optimal tableau.

Strengths and weaknesses

  • Strengths: solves problems with many variables and constraints, is systematic, and produces extra information such as slack values and shadow prices.

  • Weaknesses: long manual calculation, applies only to linear models, and in certain cases its worst-case performance is exponential even though it is usually efficient in practice.

Conclusion

The simplex method is a core operations research tool for linear optimization, for example production allocation, ingredient blending, and resource scheduling. In your thesis, show the model formulation, the tableau of each iteration, and verify the result with software such as Excel Solver or an optimization library.

Recommended for you