Big-M Method | Sahithyan's Notes

When the starting basis needs artificial variables, the 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$ .

/* This block is passed through unscoped, so every rule keeps the .walkthrough prefix explicitly. */ .walkthrough [data-live] { display: none; } .walkthrough .stack { display: block; } .walkthrough .stack > .step { opacity: 1; visibility: visible; margin-top: 16px; } .walkthrough .stack .step [data-stage] { display: revert; } .walkthrough .stack .step [data-stage] table { display: revert; } .walkthrough .foot { display: none; }