Simplex Tableau

Interactive visualizations for Chapter 4 of the Ricerca Operativa notes

The Furniture Workshop LP

We apply the Simplex method to the same LP studied graphically in Chapter 2:

\[ \begin{aligned} & \text{maximize} && 30\,x_1 + 50\,x_2 \\ & \text{subject to} && 2\,x_1 + 5\,x_2 \leq 40 && \text{(wood)} \\ & && 4\,x_1 + 2\,x_2 \leq 32 && \text{(labour)} \\ & && x_1, x_2 \geq 0. \end{aligned} \]

Introducing slack variables \(s_1, s_2 \geq 0\) converts the inequalities to equalities:

\[ \begin{aligned} 2x_1 + 5x_2 + s_1 &= 40 \\ 4x_1 + 2x_2 + s_2 &= 32 \end{aligned} \]

The Simplex method starts at a basic feasible solution (BFS) and moves along edges of the feasible polytope, improving the objective at each step, until no improving direction exists.

Iteration 0: Initial Tableau

The initial basis is \(\{s_1, s_2\}\). Setting the non-basic variables \(x_1 = x_2 = 0\) gives the BFS \((0, 0)\) with \(z = 0\).

Pivot step: divide row 1 by 5 (the pivot element), then eliminate \(x_2\) from all other rows.

Iteration 1: After First Pivot

Pivoting \(x_2\) into the basis (replacing \(s_1\)) gives the updated tableau.

Pivot step: divide row 2 by \(16/5\), then eliminate \(x_1\) from all other rows.

Iteration 2: Optimal Tableau

Pivoting \(x_1\) into the basis (replacing \(s_2\)) gives the final tableau.

Both binding constraints (\(2x_1+5x_2=40\) and \(4x_1+2x_2=32\)) are active at the optimum, confirming that all resources are fully utilised.

Pivot Sequence Visualized

The three BFS vertices visited by the Simplex method, connected in order.

The Simplex method traverses the edges of the feasible polytope, moving only to adjacent vertices with a strictly better objective value. It never revisits a vertex (assuming non-degeneracy) and terminates in at most finitely many steps.

Simplex Path Summary Table

Conclusion: The Simplex method reaches the optimum in just two pivot operations, visiting vertices \((0,0) \to (0,8) \to (5,6)\). The optimal solution is \(x_1^* = 5\) chairs, \(x_2^* = 6\) tables, with profit \(z^* = \mathbf{450}\).