Why understand the Two-Phase Simplex Method in Linear Programming?

What Is the Two‑Phase Simplex Method?

In standard simplex, you assume you can start from a basic feasible solution (for example, by using slack variables only). But when you have ≥ or = constraints, or when the right‑hand side structure is complicated, such a starting point is not obvious. The two‑phase method systematically builds one.

Key ideas:

• Artificial variables: temporary variables added to create an initial basis.
• Phase I: minimize the sum of artificial variables to test feasibility.
• Phase II: drop artificial variables and solve the original LP using simplex.

If Phase I cannot drive all artificial variables to zero, the original LP is infeasible.

Why Is the Two‑Phase Method Needed?

1. Some LPs do not have an obvious BFS

Constraints with ≥ or = do not produce a slack‑only BFS. Simplex cannot start without one.

2. Artificial variables create a temporary BFS

They allow simplex to begin even when the original constraints do not provide a feasible corner point.

3. Phase I checks feasibility

If the minimum value of the artificial objective is not zero, the LP has no feasible solution.

4. Phase II solves the real problem

Once feasibility is established, artificial variables are removed and simplex proceeds normally.

5. It avoids Big‑M instability

Two‑phase avoids choosing an arbitrarily large M, which can cause numerical issues.

How the Two‑Phase Simplex Method Works (Step by Step)

Step 1: Convert the LP to standard form

Rewrite all constraints as equations by adding slack or surplus variables. Ensure all variables satisfy nonnegativity.

Step 2: Identify where artificial variables are required

Artificial variables are needed when:

• a constraint is of type =, or
• a constraint is of type ≥ (after adding a surplus variable).

Each such constraint receives an artificial variable \( a_i \) to form an initial basis.

Step 3: Build the Phase I auxiliary problem

Construct the Phase I objective:

\[ \min \sum a_i \]

This forces simplex to eliminate artificial variables if the LP is feasible.

Step 4: Construct the initial Phase I tableau

Artificial variables serve as the initial basic variables. Compute the Phase I objective row by expressing the sum of artificial variables in terms of nonbasic variables.

Step 5: Run simplex on Phase I

Perform standard simplex iterations:

• Choose entering variable: most negative reduced cost.
• Choose leaving variable: minimum ratio test.
• Pivot to update the basis.

Continue until no negative reduced costs remain.

Step 6: Interpret the Phase I result

• If the optimal value is zero: feasible → proceed to Phase II.
• If the optimal value is positive: infeasible → stop.

Step 7: Prepare the Phase II tableau

Remove artificial variables and restore the original objective function. Express the original objective in terms of the current basis.

Step 8: Run simplex on Phase II

Use the Phase I BFS as the starting point. Perform simplex iterations until optimality is reached.

Step 9: Final interpretation

The final BFS from Phase II is the optimal solution (if bounded). If the objective is unbounded, simplex will detect it during Phase II.

Numerical Example

Consider the constraint:

\[ x_1 + x_2 = 4 \]

This cannot produce a BFS using only slack variables. We introduce an artificial variable:

\[ x_1 + x_2 + a_1 = 4 \]

Phase I objective:

\[ \min a_1 \]

If simplex drives \(a_1 = 0\), the constraint is feasible and Phase II begins. If not, the LP is infeasible.