Standard Form

The graphical method only works for 2 (or 3) decision variables. An algebraic method is needed beyond that, and it starts by rewriting the linear program in a fixed form.

Given an LP in $n$ variables and $m$ constraints, with $x \in \mathbb{R}^n$, $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$, standard form requires:

• Maximization
  Replace $\min c^T x$ by $\max (-c^T x)$.
• Equality constraints
  Convert every inequality with a slack, surplus, or artificial variable, and scale each row so $b \ge 0$.
• Non-negative variables
  $x \ge 0$.

where $n$ counts the original variables plus the added ones.

Variable

Assume $A$ has full row rank $m$ with $n \ge m$. Pick $m$ linearly independent columns forming an invertible basis matrix $B \in \mathbb{R}^{m \times m}$; the remaining columns form $N$. Partition $x = (x_B, x_N)$ accordingly.

Basic Variable

A component of $x_B$. Setting $x_N = 0$ gives $x_B = B^{-1} b$. The solution is a basic feasible solution when $B^{-1} b \ge 0$.

Non-Basic Variable

A component of $x_N$, fixed at $0$ while $x_B$ is solved for.

Slack Variable

For a constraint $a_i^T x \le b_i$, add $s_i \ge 0$ to get $a_i^T x + s_i = b_i$. Absorbs unused capacity.

Surplus Variable

For a constraint $a_i^T x \ge b_i$, subtract $s_i \ge 0$ to get $a_i^T x - s_i = b_i$. Absorbs excess over the minimum.

Artificial Variable

A variable $a_i \ge 0$ added to row $i$ with coefficient $+1$ purely to supply a starting basic variable, with no meaning in the original problem.

When It Is Required

After the RHS of every constraint is made non-negative (multiply the row by $-1$ if needed), each constraint must contribute one variable that appears with coefficient $+1$ in that row and $0$ in all others (a unit column). That variable becomes basic in the starting solution.

• $\le$ constraint
  The slack variable is already such a unit column. No artificial variable.
• $\ge$ constraint
  The surplus variable has coefficient $-1$, not a unit column. Add an artificial variable.
• $=$ constraint
  No slack or surplus at all. Add an artificial variable.

So the number of artificial variables equals the number of $\ge$ constraints plus the number of $=$ constraints (after fixing signs).

Handling Them

A valid final solution must have every artificial variable equal to $0$ (non-basic, or basic at value $0$). If one stays positive, the original problem is infeasible. 2 methods drive them out:

• Big-M method
• Two-phase method

Worked Example

Minimize $z = 2x_1 + 3x_2$ subject to

Convert each requirement:

• Objective
  Minimizing $z$ becomes maximizing $z' = -2x_1 - 3x_2$.
• $(1)$ is $\le$: add slack $s_1$.
• $(2)$ is $\ge$: subtract surplus $s_2$, then add artificial $a_1$.
• $(3)$ is $=$: add artificial $a_2$.

Standard form:

With $x = (x_1, x_2, s_1, s_2, a_1, a_2)^T$:

Starting basis $B$ = columns of $s_1, a_1, a_2$ = $I_3$, so $x_B = B^{-1} b = (s_1, a_1, a_2)^T = (4, 6, 1)^T \ge 0$ and $x_N = (x_1, x_2, s_2)^T = 0$.