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$ . The natural starting basis is $(a_1, a_2, s_3) = (3, 6, 4)$ , read straight off $(2)$ .

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$	$1$	$0$	$0$	$M$	$M$	$0$
$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)$ . But $a_1, a_2$ are basic with a nonzero coefficient $M$ in the objective row, so it isn’t canonical yet: subtract $M \times (a_1 \text{ row})$ and $M \times (a_2 \text{ row})$ from the objective row to zero them out.

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$

Objective row after eliminating $a_1, a_2$ . Its RHS is the value of the maximand $-z$ ; negate it for $z$ . 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$ . The natural starting basis is again $(a_1, a_2, s_3) = (3, 6, 4)$ .

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$	$0$	$0$	$0$	$0$	$1$	$1$	$0$
$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)$ . But $a_1, a_2$ are basic with coefficient $1$ in the $w$ row, so it isn’t canonical yet: subtract the $a_1$ row and the $a_2$ row from the $w$ row to zero them out.

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$

$w$ row after eliminating $a_1, a_2$ : $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$ . Carry over the phase 1 final basis $(x_1, x_2, s_3) = (3/5, 6/5, 1)$ , columns $x_1, x_2, s_2, s_3$ only.

1 /

entering column leaving row pivot element updated this step

Basic	$x_1$	$x_2$	$s_2$	$s_3$	RHS
$z$	$4$	$1$	$0$	$0$	$0$
$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$

Basis $(x_1, x_2, s_3) = (3/5, 6/5, 1)$ , carried over from the phase 1 final tableau. But $x_1, x_2$ are basic with nonzero coefficients $4$ and $1$ in the objective row, so it isn’t canonical yet: subtract $4 \times (x_1 \text{ row})$ and $1 \times (x_2 \text{ row})$ to zero them out.

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$

Objective row after eliminating $x_1, x_2$ . 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.