Finding an Initial BFS: The Two-Phase Method

The tableau simplex method needs an initial basic feasible solution (BFS) whose basic columns form an identity matrix. When every constraint is $\le$ with a nonnegative right-hand side, the slack variables provide this identity automatically. But many LPs include $\ge$ or $=$ constraints, for which no obvious starting basis exists.

The two-phase method handles this by temporarily adding artificial variables to manufacture an identity basis, then driving them out in a first auxiliary LP called Phase 1.

The setup rules (assuming each constraint's RHS satisfies $b_i \ge 0$) are:

• A $\le b_i$ constraint gets a slack $s_i$ added: $(\,\cdots\,) + s_i = b_i.$
• A $\ge b_i$ constraint gets a surplus $s_i$ subtracted and an artificial $a_i$ added: $(\,\cdots\,) - s_i + a_i = b_i.$
• A $= b_i$ constraint gets only an artificial $a_i$ added: $(\,\cdots\,) + a_i = b_i.$

If any RHS is negative, multiply that row by $-1$ first so that $b_i \ge 0$.

The Phase 1 objective is to minimize the sum of artificial variables:

$$\min\ w = \sum_i a_i.$$

The initial Phase 1 BFS sets each artificial equal to its row's RHS, each slack equal to its RHS, and every other variable to $0$. The artificials (and any usable slacks) form an identity, so we can begin pivoting immediately.

For example, consider

$$\begin{aligned}\max\ z &= 2x_1 + 3x_2 \\ \text{s.t.}\ x_1 + x_2 &\le 6 \\ 2x_1 + x_2 &\ge 4 \\ x_1, x_2 &\ge 0.\end{aligned}$$

The Phase 1 standard form is

$$\begin{aligned} x_1 + x_2 + s_1 &= 6, \\ 2x_1 + x_2 - s_2 + a_1 &= 4, \end{aligned}$$

with $\min w = a_1$. The initial BFS is $s_1 = 6,\ a_1 = 4$, all others $0$.