The Simplex Algorithm

The Simplex algorithm extends linear programming beyond two variables, where the graphical method cannot be used. It is an algebraic method that systematically moves from one vertex of the feasible region to an adjacent vertex with a better (or equal) objective value, until the optimum is found.

---

Standard Form

To apply the Simplex algorithm, the LP must be in standard form:

• Maximise $P = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$P=c1​x1​+c2​x2​+⋯+cn​xn​
• Subject to: $a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n \leq b_i$ai1​x1​+ai2​x2​+⋯+ain​xn​≤bi​ for each constraint
• $x_j \geq 0$xj​≥0 for all $j$j
• $b_i \geq 0$bi​≥0 for all $i$i (right-hand sides non-negative)

Slack Variables

Convert each "≤" inequality to an equality by adding a slack variable $s_i \geq 0$si​≥0:

$a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n + s_i = b_i$ai1​x1​+ai2​x2​+⋯+ain​xn​+si​=bi​

The slack variable represents unused capacity.

---

The Initial Tableau

Write the system as a table (the Simplex tableau):

	$x_1$x1​	$x_2$x2​	$s_1$s1​	$s_2$s2​	RHS
$s_1$s1​	$a_{11}$a11​	$a_{12}$a12​	1	0	$b_1$b1​
$s_2$s2​	$a_{21}$a21​	$a_{22}$a22​	0	1	$b_2$b2​
$P$P	$-c_1$−c1​	$-c_2$−c2​	0	0	0

The initial basic feasible solution is: $x_1 = 0, x_2 = 0, s_1 = b_1, s_2 = b_2, P = 0$x1​=0,x2​=0,s1​=b1​,s2​=b2​,P=0.

---

The Simplex Iteration

Step 1: Choose the pivot column.

Select the column with the most negative entry in the objective row (bottom row). This is the variable that will enter the basis.

If no entry in the objective row is negative, the current solution is optimal — stop.

Step 2: Choose the pivot row.

For each row (excluding the objective row), compute the ratio $\text{RHS} / \text{pivot column entry}$RHS/pivot column entry (only for positive entries).

The row with the smallest positive ratio is the pivot row. The variable in this row leaves the basis.

Step 3: Pivot.

Divide the pivot row by the pivot element (to make it 1). Then use row operations to make all other entries in the pivot column equal to 0.

Step 4: Repeat from Step 1.

---

Worked Example

Maximise $P = 5x + 4y$P=5x+4y subject to:

• $6x + 4y \leq 24$6x+4y≤24
• $x + 2y \leq 6$x+2y≤6
• $x, y \geq 0$x,y≥0