Standard Form | Sahithyan's Notes

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$ .

\begin{aligned} \text{maximize} \quad & z = c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \ge 0, \quad b \ge 0 \end{aligned}

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

\begin{aligned} x_1 + x_2 &\le 4 && \quad (1) \\ x_1 + 3x_2 &\ge 6 && \quad (2) \\ x_1 - x_2 &= 1 && \quad (3) \\ x_1, x_2 &\ge 0 \end{aligned}

Solution Reveal Hide

Convert each requirement:

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

Standard form:

\text{maximize } z' = -2x_1 - 3x_2

\begin{aligned} x_1 + x_2 + s_1 &= 4 && \quad (1') \\ x_1 + 3x_2 - s_2 + a_1 &= 6 && \quad (2') \\ x_1 - x_2 + a_2 &= 1 && \quad (3') \\ x_1, x_2, s_1, s_2, a_1, a_2 &\ge 0 \end{aligned}

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

A = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 3 & 0 & -1 & 1 & 0 \\ 1 & -1 & 0 & 0 & 0 & 1 \end{bmatrix}, \quad b = \begin{bmatrix} 4 \\ 6 \\ 1 \end{bmatrix}, \quad c = \begin{bmatrix} -2 & -3 & 0 & 0 & 0 & 0 \end{bmatrix}^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$ .