How to Calculate Reduced Costs in the Big-M Method

In the Big-M method, an artificial variable is assigned a large penalty so the simplex method has an incentive to drive it out of the basis. That penalty affects not only the objective value but also the reduced costs of other variables. The key is to include the costs of the current basic variables when calculating those reduced costs.

This example uses a maximization problem and the common tableau convention $c_j-z_j$. With this convention, a positive reduced cost indicates a possible objective improvement.

Reduced cost in a simplex tableau

For a variable in column $j$, the reduced cost is

$$\bar c_j=c_j-z_j=c_j-c_B^T B^{-1}A_j,$$

where $c_j$ is its objective coefficient, $c_B$ contains the objective coefficients of the current basic variables, and $B^{-1}A_j$ is the column’s current tableau column. In a tableau, you can calculate $z_j$ by multiplying each basic variable’s objective coefficient by its entry in column $j$ and adding the results.

Some textbooks use the opposite sign, $z_j-c_j$. Under that convention, the signs and entering-variable rule reverse. The arithmetic is the same, so check which convention your tableau uses before interpreting a sign.

Worked Big-M example

Consider

$$\begin{aligned} \text{maximize } & z=3x_1+2x_2\\ \text{subject to } & x_1+x_2\ge 4,\\ &x_1+2x_2=6,\\ &x_1,x_2\ge 0. \end{aligned}$$

The first constraint is a “greater than or equal to” constraint, so subtract a surplus variable $s_1$ and add an artificial variable $a_1$. The equality constraint needs an artificial variable $a_2$:

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

For a maximization problem, penalize each artificial variable with coefficient $-M$. The objective used by the Big-M method is therefore

$z=3x_1+2x_2-Ma_1-Ma_2,$

where $M$ is understood to be sufficiently large and positive. The initial basis is $a_1,a_2$, so the basic-cost vector is $c_B=(-M,-M)$.

The constraint coefficients and objective coefficients are:

Variable	$x_1$	$x_2$	$s_1$	$a_1$	$a_2$	RHS
Row for $a_1$	1	1	-1	1	0	4
Row for $a_2$	1	2	0	0	1	6
Objective coefficient $c_j$	3	2	0	$-M$	$-M$

Calculate $z_j$ by weighting each column entry by its row’s basic cost. For $x_1$, the column is $(1,1)$, so

$z_{x_1}=(-M)(1)+(-M)(1)=-2M,$

and its reduced cost is $c_{x_1}-z_{x_1}=3-(-2M)=3+2M$.

For $x_2$, the column is $(1,2)$:

$z_{x_2}=(-M)(1)+(-M)(2)=-3M,$

so its reduced cost is $2-(-3M)=2+3M$.

For the surplus variable $s_1$, the column is $(-1,0)$:

$z_{s_1}=(-M)(-1)+(-M)(0)=M,$

so its reduced cost is $0-M=-M$.

The artificial variables are basic, so each has reduced cost zero: for example, $z_{a_1}=-M$ and $c_{a_1}=-M$. The initial reduced-cost row is therefore

Variable	$x_1$	$x_2$	$s_1$	$a_1$	$a_2$
$c_j-z_j$	$3+2M$	$2+3M$	$-M$	0	0

The initial objective value is $-4M-6M=-10M$, because the initial basic artificial-variable values are 4 and 6. With the $c_j-z_j$ convention, both original decision variables have positive reduced costs. If $M>1$, $x_2$ has the larger one, $2+3M$, so it is selected as the entering variable under the largest-positive-reduced-cost rule. The ratio test then compares $4/1=4$ and $6/2=3$, so $a_2$ leaves the basis.

Why the artificial-variable costs matter

The reduced cost of $x_2$ is not just its original objective coefficient, 2. It is $2+3M$ because the two current basic artificial variables contribute $-3M$ to $z_{x_2}$. Omitting their costs would give the wrong reduced-cost row and could lead to a wrong pivot choice.

As simplex pivots proceed, the basis changes. Recalculate $c_B$ and the tableau columns at each step; reduced costs from the initial tableau cannot simply be reused. A valid final solution to the original problem must have every artificial variable equal to zero. At an optimal solution of the Big-M problem, if the penalty is known to be sufficiently large (or treated symbolically), a positive artificial variable indicates that the original constraints are infeasible. With an arbitrary finite numerical $M$, a positive artificial variable may instead reflect an inadequate penalty. If an artificial variable remains basic at value zero, it may be possible to remove it from the basis or leave it there as a degenerate basic variable.

Common mistakes

• Using $+M$ in a maximization objective: Under the convention used here, artificial variables receive coefficient $-M$ in a maximization problem. For minimization, the usual penalty is $+M$.
• Forgetting the basic costs: Compute $z_j$ using the objective coefficients of the current basis, including artificial variables still in it.
• Mixing sign conventions: If a tableau lists $z_j-c_j$, a positive entry does not mean the same thing as a positive entry in a $c_j-z_j$ row.
• Treating $M$ as an ordinary small constant: The method assumes a sufficiently large penalty. In computations, an arbitrary numeric value for $M$ can cause numerical difficulties or fail to represent the intended priority; two-phase simplex avoids this issue by separating feasibility from optimization.