Two-Phase Method¶

Definition¶

The two-phase method initializes and solves an LP using artificial variables $R_i\ge0$ $0$ . Phase I maximizes

r=-\sum_iR_i

subject to the augmented constraints. If its optimum is negative, the original LP is infeasible. If its optimum is zero, restore the original objective, remove artificial variables from the working model, put the objective row in canonical form for the resulting feasible basis, and apply simplex in Phase II.

Interpretation¶

The two-phase method splits a difficult start into two easier problems. Phase I only asks whether the constraints can be satisfied at all and, if so, finds a basic feasible solution; Phase II then runs the ordinary simplex method from there with the real objective.

A flowchart: an LP without an obvious starting basis goes through Phase I, which either finds a feasible solution and continues to Phase II or shows that the LP is infeasible.

The flowchart starts from an LP with $\ge$ or $=$ rows, where no slack basis is available. Phase I adds artificial variables $R_i$ and maximizes $\displaystyle r=-\sum_iR_i$ $- i \sum R_{i}$ . If $r^*=0$ $0$ , all $R_i$ are zero, so the solution satisfies the original constraints and Phase II continues from it. If $r^*<0$ $0$ , every feasible solution of the Phase I problem has some $R_i>0$ $0$ , so the original LP is infeasible.

The Phase I objective is chosen so that its optimum answers the feasibility question: since every $R_i\ge0$ $0$ , always $r\le0$ $0$ , and $r=0$ exactly when all artificial variables vanish. The artificial variables only make a start possible: each has a unit column and starts at the right-hand side of its row, and a solution with some $R_i>0$ means nothing for the real problem.

Phase I ignores the real objective, so its solution need not be optimal: in the Examples it reaches $(0,25/3)$ , where $3x_1+2x_2=50/3$ $50/3$ , and Phase II improves this to $25$ at $(5,5)$ . Before Phase II, the real objective row must be restored and put in canonical form for the new basis; only then can the optimality test be read from it.

Key Results¶

Eliminate basic artificial variables from the initial Phase I objective row before pivoting.
The phase-I objective can never exceed zero.
A zero-valued artificial variable still in the basis needs basis cleanup before its column is removed; the supplied worked example avoids this case.

Examples¶

For $x_1+x_2\le10$ and $2x_1+3x_2=25$ $25$ , Phase I finds $(0,25/3)$ .
Phase II for objective $3x_1+2x_2$ reaches $(5,5)$ and value 25.

Prerequisites¶

Infeasible Linear Program

Sources¶

OR Modelling · Week 2

Aliases: two-phase simplex method, two-phase simplex Symbols: sum

Last updated: 20 October 2026 03:02