Artificial Variable Methods | Sahithyan's Notes

If the starting basis needs artificial variables, either Big-M or two-phase method should be used.

Big-M Method

Solves the LP in a single simplex run by penalizing artificial variables in the objective.

Assign each artificial variable a coefficient $-M$ in the objective (maximization), where $M$ is an arbitrarily large positive constant.
Run the simplex algorithm normally. The penalty drives artificial variables out of the basis as the objective improves.

Reading the Result

Optimal solution
All artificial variables are 0 in the optimal tableau.
Infeasible problem
At least one artificial variable remains positive (basic with a non-zero value) in the optimal tableau.
Unbounded problem
Detected by the usual minimum ratio test, same as without artificial variables.

Worked Example

\begin{aligned} \text{minimize} \quad & z = 4x_1 + x_2 \\ \text{subject to} \quad & 3x_1 + x_2 = 3 \\ & 4x_1 + 3x_2 \ge 6 \\ & x_1 + 2x_2 \le 4 \\ & x_1, x_2 \ge 0 \end{aligned} \tag{1}

Standard form adds a surplus $s_2$ to the $\ge$ constraint, a slack $s_3$ to the $\le$ constraint, and artificials $a_1, a_2$ to the equality and $\ge$ rows:

\begin{aligned} 3x_1 + x_2 + a_1 &= 3 \\ 4x_1 + 3x_2 - s_2 + a_2 &= 6 \\ x_1 + 2x_2 + s_3 &= 4 \end{aligned} \tag{2}

The tableau convention maximizes and stops when all objective row coefficients are $\ge 0$ . Minimizing $z$ means maximizing $-z$ , so the objective is $\max\ -z - M a_1 - M a_2$ . Written with all terms on the left, the objective row starts as

z + 4x_1 + x_2 + M a_1 + M a_2 = 0 \tag{3}

But $a_1, a_2$ are basic, so they must have coefficient $0$ in the objective row. Subtract $M \times (a_1 \text{ row})$ and $M \times (a_2 \text{ row})$ of $(2)$ from $(3)$ to eliminate them:

\begin{aligned} x_1:\quad & 4 - 3M - 4M = 4 - 7M \\ x_2:\quad & 1 - 1M - 3M = 1 - 4M \\ s_2:\quad & 0 - 0 - (-M) = M \\ \text{RHS}:\quad & 0 - 3M - 6M = -9M \end{aligned}

The two subtracted coefficients in each line are the $x_1$ (or $x_2$ , $s_2$ ) entries of the $a_1$ row and the $a_2$ row. This gives the initial objective row below. Its RHS is the value of the maximand $-z$ ; negate it for $z$ .

1 /

entering column leaving row pivot element updated this step

Basic	$x_1$	$x_2$	$s_2$	$s_3$	$a_1$	$a_2$	RHS
$z$	$4 - 7M$	$1 - 4M$	$M$	$0$	$0$	$0$	$-9M$
$a_1$	$3$	$1$	$0$	$0$	$1$	$0$	$3$
$a_2$	$4$	$3$	$-1$	$0$	$0$	$1$	$6$
$s_3$	$1$	$2$	$0$	$1$	$0$	$0$	$4$

Basis $(a_1, a_2, s_3) = (3, 6, 4)$ . For large $M$ the coefficients $4 - 7M$ and $1 - 4M$ are both negative, so not optimal.

Basic	$x_1$	$x_2$	$s_2$	$s_3$	$a_1$	$a_2$	RHS	Ratio
$z$	$4 - 7M$	$1 - 4M$	$M$	$0$	$0$	$0$	$-9M$
$a_1$	$3$	$1$	$0$	$0$	$1$	$0$	$3$	3/3 = 1
$a_2$	$4$	$3$	$-1$	$0$	$0$	$1$	$6$	6/4 = 1.5
$s_3$	$1$	$2$	$0$	$1$	$0$	$0$	$4$	4/1 = 4

Most negative coefficient is $4 - 7M$ , so $x_1$ enters. Minimum ratio is $1$ in row $a_1$ , so $a_1$ leaves. Pivot element is $3$ .

Basic	$x_1$	$x_2$	$s_2$	$s_3$	$a_1$	$a_2$	RHS	Ratio
$z$	$0$	$(-1 - 5M)/3$	$M$	$0$	$(7M - 4)/3$	$0$	$-2M - 4$
$x_1$	$1$	$1/3$	$0$	$0$	$1/3$	$0$	$1$	1 / (1/3) = 3
$a_2$	$0$	$5/3$	$-1$	$0$	$-4/3$	$1$	$2$	2 / (5/3) = 1.2
$s_3$	$0$	$5/3$	$0$	$1$	$-1/3$	$0$	$3$	3 / (5/3) = 1.8

Coefficient $(-1 - 5M)/3$ is the most negative, so $x_2$ enters. Minimum ratio is $1.2$ in row $a_2$ , so $a_2$ leaves. Pivot element is $5/3$ .

Basic	$x_1$	$x_2$	$s_2$	$s_3$	$a_1$	$a_2$	RHS	Ratio
$z$	$0$	$0$	$-1/5$	$0$	$M - 8/5$	$1/5 + M$	$-18/5$
$x_1$	$1$	$0$	$1/5$	$0$	$3/5$	$-1/5$	$3/5$	(3/5) / (1/5) = 3
$x_2$	$0$	$1$	$-3/5$	$0$	$-4/5$	$3/5$	$6/5$	skip (-3/5)
$s_3$	$0$	$0$	$1$	$1$	$1$	$-1$	$1$	1/1 = 1

Both artificials are non-basic. Only $-1/5$ (column $s_2$ ) is negative, so $s_2$ enters. Minimum ratio is $1$ in row $s_3$ , so $s_3$ leaves. Pivot element is $1$ .

Basic	$x_1$	$x_2$	$s_2$	$s_3$	$a_1$	$a_2$	RHS
$z$	$0$	$0$	$0$	$1/5$	$M - 7/5$	$M$	$-17/5$
$x_1$	$1$	$0$	$0$	$-1/5$	$2/5$	$0$	$2/5$
$x_2$	$0$	$1$	$0$	$3/5$	$-1/5$	$0$	$9/5$
$s_2$	$0$	$0$	$1$	$1$	$1$	$-1$	$1$

All objective coefficients are non-negative and no artificial is basic. Optimal at $x_1 = 2/5$ , $x_2 = 9/5$ , maximand $-z = -17/5$ , so $z = 17/5 = 3.4$ .

.simplex [data-live] { display: none; } .simplex .stack { display: block; } .simplex .stack > .step { opacity: 1; visibility: visible; margin-top: 16px; } .simplex .stack .step > .tableau { display: table; } .simplex .foot { display: none; }

Two-Phase Method

Uses 2 separate simplex runs, avoiding the arbitrary constant $M$ .

Phase 1

Replace the original objective with minimizing the sum of all artificial variables. This is the same regardless of whether the original problem maximizes or minimizes; the original objective’s direction plays no role in phase 1.
Run the simplex algorithm.
If the minimum is 0, a basic feasible solution to the original problem was found; proceed to phase 2.
If the minimum is positive, the original problem is infeasible. Stop.

Phase 2

Drop the artificial variables and restore the original objective. The original direction only matters here: convert a minimization to $\max\ {-z}$ to fit the tableau convention, or use a maximization objective as is.
Use the phase 1 optimal basis as the starting basic feasible solution: keep the same basic variables and the same rows (with the artificial columns dropped) from the phase 1 final tableau, and only replace the objective row with the restored objective, priced out against those same rows.
Run the simplex algorithm to optimize the original objective.

Unbounded and alternate/infinite optimal solutions are detected in phase 2 the same way as in the ordinary simplex algorithm.

Worked Example

Same LP $(1)$ and standard form $(2)$ as the Big-M example.

Phase 1

Objective becomes $\min\ a_1 + a_2$ , i.e. $\max\ w$ with $w = -a_1 - a_2$ . Pricing out the basic artificials from $w + a_1 + a_2 = 0$ (subtract each artificial’s row) gives the initial $w$ row.

1 /

entering column leaving row pivot element updated this step

Basic	$x_1$	$x_2$	$s_2$	$s_3$	$a_1$	$a_2$	RHS
$w$	$-7$	$-4$	$1$	$0$	$0$	$0$	$-9$
$a_1$	$3$	$1$	$0$	$0$	$1$	$0$	$3$
$a_2$	$4$	$3$	$-1$	$0$	$0$	$1$	$6$
$s_3$	$1$	$2$	$0$	$1$	$0$	$0$	$4$

Phase 1 basis $(a_1, a_2, s_3)$ with $w = -9$ . Coefficients $-7$ and $-4$ are negative, so not optimal.

Basic	$x_1$	$x_2$	$s_2$	$s_3$	$a_1$	$a_2$	RHS	Ratio
$w$	$-7$	$-4$	$1$	$0$	$0$	$0$	$-9$
$a_1$	$3$	$1$	$0$	$0$	$1$	$0$	$3$	3/3 = 1
$a_2$	$4$	$3$	$-1$	$0$	$0$	$1$	$6$	6/4 = 1.5
$s_3$	$1$	$2$	$0$	$1$	$0$	$0$	$4$	4/1 = 4

Most negative is $-7$ , so $x_1$ enters. Minimum ratio is $1$ in row $a_1$ , so $a_1$ leaves. Pivot element is $3$ .

Basic	$x_1$	$x_2$	$s_2$	$s_3$	$a_1$	$a_2$	RHS	Ratio
$w$	$0$	$-5/3$	$1$	$0$	$7/3$	$0$	$-2$
$x_1$	$1$	$1/3$	$0$	$0$	$1/3$	$0$	$1$	1 / (1/3) = 3
$a_2$	$0$	$5/3$	$-1$	$0$	$-4/3$	$1$	$2$	2 / (5/3) = 1.2
$s_3$	$0$	$5/3$	$0$	$1$	$-1/3$	$0$	$3$	3 / (5/3) = 1.8

Coefficient $-5/3$ is negative, so $x_2$ enters. Minimum ratio is $1.2$ in row $a_2$ , so $a_2$ leaves. Pivot element is $5/3$ .

Basic	$x_1$	$x_2$	$s_2$	$s_3$	$a_1$	$a_2$	RHS
$w$	$0$	$0$	$0$	$0$	$1$	$1$	$0$
$x_1$	$1$	$0$	$1/5$	$0$	$3/5$	$-1/5$	$3/5$
$x_2$	$0$	$1$	$-3/5$	$0$	$-4/5$	$3/5$	$6/5$
$s_3$	$0$	$0$	$1$	$1$	$1$	$-1$	$1$

$w = 0$ and all coefficients are non-negative. Both artificials are non-basic, so $(x_1, x_2, s_3) = (3/5, 6/5, 1)$ is a basic feasible solution of the original problem.

Phase 2

Drop columns $a_1, a_2$ . Restore $\max\ -z$ with $-z = -4x_1 - x_2$ . Written with all terms on the left, the objective row starts as

(-z) + 4x_1 + x_2 = 0

But $x_1, x_2$ are basic (from the phase 1 final tableau), so they must have coefficient $0$ in the objective row. Subtract $4 \times (x_1 \text{ row})$ and $1 \times (x_2 \text{ row})$ of the phase 1 final tableau (columns $x_1, x_2, s_2, s_3$ only, dropping $a_1, a_2$ ) to eliminate them:

\begin{aligned} x_1:\quad & 4 - 4(1) - 1(0) = 0 \\ x_2:\quad & 1 - 4(0) - 1(1) = 0 \\ s_2:\quad & 0 - 4(1/5) - 1(-3/5) = -1/5 \\ \text{RHS}:\quad & 0 - 4(3/5) - 1(6/5) = -18/5 \end{aligned}

This gives the initial objective row below, alongside the phase 1 final rows for $x_1, x_2, s_3$ with the $a_1, a_2$ columns dropped.

1 /

entering column leaving row pivot element updated this step

Basic	$x_1$	$x_2$	$s_2$	$s_3$	RHS
$z$	$0$	$0$	$-1/5$	$0$	$-18/5$
$x_1$	$1$	$0$	$1/5$	$0$	$3/5$
$x_2$	$0$	$1$	$-3/5$	$0$	$6/5$
$s_3$	$0$	$0$	$1$	$1$	$1$

Starts from the phase 1 basis $(x_1, x_2, s_3)$ . Coefficient $-1/5$ in column $s_2$ is negative, so not optimal.

Basic	$x_1$	$x_2$	$s_2$	$s_3$	RHS	Ratio
$z$	$0$	$0$	$-1/5$	$0$	$-18/5$
$x_1$	$1$	$0$	$1/5$	$0$	$3/5$	(3/5) / (1/5) = 3
$x_2$	$0$	$1$	$-3/5$	$0$	$6/5$	skip (-3/5)
$s_3$	$0$	$0$	$1$	$1$	$1$	1/1 = 1

$s_2$ enters. Minimum ratio is $1$ in row $s_3$ , so $s_3$ leaves. Pivot element is $1$ .

Basic	$x_1$	$x_2$	$s_2$	$s_3$	RHS
$z$	$0$	$0$	$0$	$1/5$	$-17/5$
$x_1$	$1$	$0$	$0$	$-1/5$	$2/5$
$x_2$	$0$	$1$	$0$	$3/5$	$9/5$
$s_2$	$0$	$0$	$1$	$1$	$1$

All objective coefficients are non-negative. Optimal at $x_1 = 2/5$ , $x_2 = 9/5$ , so $z = 17/5 = 3.4$ , matching the Big-M result.