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.
::: {.cell}
```{.pyodide .cell-code}
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon, FancyArrowPatch
import matplotlib.patheffects as pe
fig, ax = plt.subplots(figsize=(9, 8))
# Feasible region
vertices = np.array([[0, 0], [8, 0], [5, 6], [0, 8]])
poly = Polygon(vertices, closed=True, facecolor='#cce5ff',
edgecolor='#3366cc', linewidth=2.5, alpha=0.5,
label='Feasible region $P$')
ax.add_patch(poly)
# Constraint lines
x1_line = np.linspace(-0.5, 11, 300)
ax.plot(x1_line, (40 - 2*x1_line)/5, 'b-', lw=1.5, alpha=0.5,
label='$2x_1+5x_2=40$')
ax.plot(x1_line, (32 - 4*x1_line)/2, 'r-', lw=1.5, alpha=0.5,
label='$4x_1+2x_2=32$')
# Optimal isoline
ax.plot(x1_line, (450 - 30*x1_line)/50, '--', color='#cc5500', lw=2, alpha=0.7,
label='$z^*=450$ isoline')
# Non-path vertex
ax.plot(8, 0, 'o', color='#888888', markersize=9, zorder=4,
markeredgecolor='white', markeredgewidth=1.5)
ax.annotate('$(8,0)$\nnot visited', (8, 0), (9.2, -0.9),
fontsize=9, color='#888888',
arrowprops=dict(arrowstyle='->', color='#aaaaaa', lw=1.2))
# ── Simplex path ────────────────────────────────────────────────────────────
path_pts = [(0, 0), (0, 8), (5, 6)]
path_z = [0, 400, 450]
path_colors = ['#3366cc', '#ff9900', '#8b00ff']
path_labels = ['Start: $(0,\\ 0)$\n$z = 0$',
'Iter 1: $(0,\\ 8)$\n$z = 400$',
'Optimal: $(5,\\ 6)$\n$z^* = 450$']
path_label_offsets = [(-2.2, -1.2), (-2.8, 0.5), (1.0, 1.0)]
# Draw arrows between consecutive BFS vertices
arrow_style = dict(arrowstyle='->', lw=2.8, mutation_scale=20)
for k in range(len(path_pts) - 1):
x_s, y_s = path_pts[k]
x_e, y_e = path_pts[k+1]
ax.annotate('', xy=(x_e, y_e), xytext=(x_s, y_s),
arrowprops=dict(arrowstyle='->', color='#e67300', lw=3.0,
connectionstyle='arc3,rad=0.18'))
# Draw BFS vertices
sizes = [12, 12, 22]
shapes = ['o', 'o', '*']
for pt, z, col, lbl, off, sz, sh in zip(
path_pts, path_z, path_colors, path_labels,
path_label_offsets, sizes, shapes):
ax.plot(pt[0], pt[1], sh, color=col, markersize=sz, zorder=6,
markeredgecolor='white', markeredgewidth=2)
fc = '#f0e0ff' if col == '#8b00ff' else ('#fff3cd' if col == '#ff9900'
else '#e6eeff')
ax.annotate(lbl,
(pt[0], pt[1]),
(pt[0] + off[0], pt[1] + off[1]),
fontsize=10, fontweight='bold', color=col,
bbox=dict(boxstyle='round,pad=0.35', facecolor=fc,
edgecolor=col, alpha=0.95),
arrowprops=dict(arrowstyle='->', color=col, lw=1.6))
# Iteration labels along the arrows
ax.text(-1.3, 4.0, 'Pivot 1\n$x_2$ enters\n$s_1$ leaves', fontsize=9,
color='#e67300', ha='center', style='italic',
bbox=dict(boxstyle='round,pad=0.2', facecolor='#fff8ee',
edgecolor='#ffcc80', alpha=0.85))
ax.text(3.2, 8.2, 'Pivot 2\n$x_1$ enters\n$s_2$ leaves', fontsize=9,
color='#e67300', ha='center', style='italic',
bbox=dict(boxstyle='round,pad=0.2', facecolor='#fff8ee',
edgecolor='#ffcc80', alpha=0.85))
ax.set_xlim(-2.5, 11.5)
ax.set_ylim(-2.0, 10.8)
ax.set_xlabel('$x_1$', fontsize=13)
ax.set_ylabel('$x_2$', fontsize=13)
ax.set_title('Simplex Path: $(0,0) \\to (0,8) \\to (5,6)$', fontsize=14,
fontweight='bold')
ax.set_aspect('equal')
ax.grid(True, alpha=0.3)
ax.legend(fontsize=9, loc='upper right')
ax.axhline(0, color='black', lw=0.8)
ax.axvline(0, color='black', lw=0.8)
plt.tight_layout()
plt.show():::
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}\).
TipSummary: Simplex Tableau
- Bases & Feasibility: The simplex algorithm moves from one Basic Feasible Solution (BFS) to an adjacent one.
- Pivoting: We identify the entering variable (column with positive reduced cost) and the leaving variable (minimum ratio test).
- Degeneracy: Can cause cycling (loops). Use Bland’s rule (smallest index) to guarantee convergence.