The Big-M Method for Initialization

When we standardize an LP for the simplex method, each $\le$ constraint contributes a slack variable whose column is a unit vector — the slack can serve as a basic variable in the initial tableau at value $b_i$. But $\ge$ and $=$ constraints don't yield such a ready-made basic column.

The Big-M method patches this gap by attaching an artificial variable $a_i \ge 0$ to every constraint that lacks an obvious initial basic variable. The artificial has no physical meaning in the original problem — it is a placeholder that gives the simplex something to start with.

The conversion rules (assuming $b_i \ge 0$; otherwise multiply the constraint by $-1$ first):

$$\begin{array}{l|l}\textrm{Original constraint} & \textrm{Standardized form} \\ \hline \sum_j a_{ij}x_j \le b_i & \sum_j a_{ij}x_j + s_i = b_i \\ \sum_j a_{ij}x_j \ge b_i & \sum_j a_{ij}x_j - s_i + a_i = b_i \\ \sum_j a_{ij}x_j = b_i & \sum_j a_{ij}x_j + a_i = b_i \end{array}$$

To illustrate, the constraints

$$x_1 + x_2 \le 8, \qquad x_1 + 2x_2 \ge 4$$

standardize to

$$x_1 + x_2 + s_1 = 8, \qquad x_1 + 2x_2 - s_2 + a_1 = 4.$$

The initial basis is $\{s_1, a_1\}$ with values $s_1 = 8$ and $a_1 = 4$ (and $x_1 = x_2 = s_2 = 0$).