The Simplex Tableau Method

The simplex algorithm is an iterative algorithm that solves linear programs by walking from vertex to vertex along the edges of this polytope (boundaries of the feasible region) until it arrives at a vertex that optimizes the objective. It is a very popular and de facto method to solve the LP examples. Let’s understand the algorithm via a simple example.

Example

Let’s consider the case of a shop that produces three types of automobile trailers: flatbed, economy, and luxury. The shop has a limited working capacity of 24 days per month for metalworking and 60 days per month for woodworking. The production data for the trailers is as follows:

• Flatbed trailers: A half day of metalworking, 1 day of woodworking, and $6 profit per unit

• Economy trailers: Two days of metalworking, 2 days of woodworking, and $14 profit per unit

• Luxury trailers: One day of metalworking, 4 days of woodworking, and $13 profit per unit.

Let $x_1$, $x_2$, $x_3$ denote the number of flatbeds, economy, and luxury trailers produced in a month by the shop. The aim is to maximize the total profit, which is given by $g(x) = 6x_1 + 14x_2 + 13x_3$, subject to the following constraints:

• $0.5x_1 + 2x_2 + x_3 \leq 24$ (metalworking capacity).

• $x_1 + 2x_2 + 4x_3 \leq 60$ (woodworking capacity).

• $x_1, x_2, x_3 \geq 0$ (nonnegativity constraints).

The problem can be formularized as an LP problem as follows: