Simplex Method

Fundamentals of Linear Programming: Traversing vertices to find the optimum

1. Introduction: A Geometric Approach to Optimization

Linear Programming (LP) is a mathematical optimization technique used to minimize or maximize a linear objective function (such as cost or profit) subject to constraints represented by linear inequalities.

Its geometric meaning is clear: it is nothing more than exploring the "Vertices" of a polytope (feasible region) defined by the constraints. The Fundamental Theorem of Linear Programming guarantees that "if an optimal solution exists, it must lie at one of the vertices of the region."

The Simplex Method exploits this property. Starting from an initial vertex, the algorithm iteratively moves to an adjacent vertex that improves the objective function value (Pivot Operation), reaching the optimal solution in a finite number of steps.

2. General Form

The standard form of a linear programming problem for $n$ variables $\boldsymbol{x} = (x_1, x_2, \dots, x_n)^T$ is described as follows:

Objective Function

\[ \text{Maximize } Z = \boldsymbol{c}^T \boldsymbol{x} \]

(where $\boldsymbol{c}$ is the profit coefficient vector)

Constraints and Slack Variables

To apply the Simplex Method, inequality constraints $\boldsymbol{Ax} \le \boldsymbol{b}$ must be converted into equality constraints. By introducing non-negative slack variables $\boldsymbol{s} = (s_1, \dots, s_m)^T$, we transform the problem into a system of linear equations (Canonical Form):

\[ \boldsymbol{Ax} + \boldsymbol{I}\boldsymbol{s} = \boldsymbol{b} \] \[ \boldsymbol{x} \ge 0, \quad \boldsymbol{s} \ge 0 \]

Importance of Identity Matrix $I$:
Here, $\boldsymbol{I}$ is an $m \times m$ Identity Matrix. Since an independent slack variable is added with a coefficient of 1 to each of the $m$ constraint equations, the coefficient matrix for the slack variables becomes an identity matrix (diagonal elements are 1, others are 0). This allows us to immediately find a "trivial feasible basis solution" where $\boldsymbol{x}=\boldsymbol{0}$ and $\boldsymbol{s}=\boldsymbol{b}$ at the initial stage of calculation.

3. Algorithm Procedure

Initialization: Find a feasible basis solution (usually the origin $\boldsymbol{x}=0$) and construct the initial Simplex Tableau.
Optimality Test: Check the objective function row ($Z$-row). If all coefficients are non-negative, the current solution is optimal, and the process terminates.
Determine Pivot Column (Entering Variable): Select the variable that most improves the objective function (the variable with the most negative coefficient). This becomes the "Entering Variable."
Determine Pivot Row (Leaving Variable): Calculate the ratio of the constant term to the coefficient for each row to see how far we can move in that direction without violating constraints (Minimum Ratio Test). The row with the minimum ratio becomes the "Leaving Variable."
Pivot Operation: Using Gaussian elimination, make the selected pivot element "1" and all other elements in that column "0."
Return to Step 2.

4. Example Problem

To deepen our understanding of the theory, let's solve the following specific production planning problem.

Objective Function (Maximize Profit):
\[ \text{Max } Z = 4x_1 + 3x_2 \]
Constraints:
\[ \begin{cases} x_1 + x_2 \le 40 \quad \dots (1) \\ 2x_1 + x_2 \le 60 \quad \dots (2) \\ x_1, x_2 \ge 0 \end{cases} \]

5. Step 1: Initial Tableau

Introduce slack variables $s_1, s_2$ to convert inequalities to equalities and create the tableau.
(Rewrite as $Z - 4x_1 - 3x_2 = 0$)

Basis	$Z$	$x_1$	$x_2$	$s_1$	$s_2$	Constant	Remark (Ratio)
$s_1$	0	1	1	1	0	40	$40/1=40$
$s_2$	0	2	1	0	1	60	$60/2=30$ (Min)
$Z$	1	-4	-3	0	0	0

Assessment: Since there are negative values in the $Z$-row, it is not optimal. Select $x_1$ column (coefficient -4) as the entering variable and $s_2$ row (minimum ratio) as the leaving variable. The pivot is "2".

6. Step 2: Pivot Operation (1st Iteration)

Divide the entire pivot row by 2 and eliminate $x_1$ from other rows.

Basis	$Z$	$x_1$	$x_2$	$s_1$	$s_2$	Constant	Remark (Ratio)
$s_1$	0	0	0.5	1	-0.5	10	$10/0.5=20$ (Min)
$x_1$	0	1	0.5	0	0.5	30	$30/0.5=60$
$Z$	1	0	-1	0	2	120

Assessment: There is still a negative value (-1) in the $Z$-row. Select $x_2$ column as the entering variable and $s_1$ row as the leaving variable. The next pivot is "0.5".

7. Step 3: Pivot Operation (2nd Iteration - Convergence)

Perform matrix operations similarly.

Basis	$Z$	$x_1$	$x_2$	$s_1$	$s_2$	Constant	Remark
$x_2$	0	0	1	2	-1	20
$x_1$	0	1	0	-1	1	20
$Z$	1	0	0	2	1	140	Complete

Conclusion: Reaching the Optimal Solution

All coefficients in the $Z$-row are non-negative, so the calculation is complete.

Optimal Solution: $x_1 = 20, \quad x_2 = 20$
Max Profit: $Z = 140$

Geometrically, this means we started from the origin $(0,0)$, passed through vertex $(30,0)$, and finally reached the optimal vertex $(20,20)$.