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):