Understanding the Big-M Method in Linear Programming

Why Do We Need the Big-M Method?

The standard Simplex method easily handles ≤ constraints by adding slack variables. However, when a linear programming problem contains ≥ or = constraints, finding an initial basic feasible solution becomes difficult. This is where the Big-M method comes in.

Introducing Artificial Variables

For every ≥ constraint, we subtract a surplus variable and add an artificial variable. For every = constraint, we simply add an artificial variable. Artificial variables have no physical meaning; they are purely mathematical tools to kickstart the Simplex algorithm.

The Big-M Penalty

We cannot allow artificial variables to be part of the final optimal solution. To force them out, we assign them a massive penalty in the objective function:

• For a maximization problem, we subtract M × A_i (where M is a very large number).
• For a minimization problem, we add M × A_i.

Solving with Big-M

The process follows these steps:

1. Add surplus and artificial variables to put the problem in standard form.
2. Assign the Big-M penalty to artificial variables in the objective function.
3. Perform preliminary row operations so the artificial variables form a valid identity matrix in the initial tableau.
4. Proceed with standard Simplex iterations.

Interpreting the Result

If the final optimal tableau still contains an artificial variable with a non-zero value, the original problem is infeasible. If all artificial variables are driven to zero, you have found the true optimal solution.