Standard form

Let $\mathbf{A}\in {\mathbb{R}}^{m\times n}$, $\mathbf{b}\in {\mathbb{R}}^m$, and $\mathbf{c}\in {\mathbb{R}}^n$. Let $\mathbf{x}=\left[\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right]$ be a tuple of variables. We focus on LP problems in standard (equality) form: $$\begin{array}{rl}min& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ (P)\text{s.t.}& \mathbf{A}\mathbf{x}=\mathbf{b}\\ & \mathbf{x}\ge \mathbf{0}.\end{array}$$

The standard form is often the preferred form to use when studying linear programming because, as we will soon see, it simplifies the discussion of certain ideas, especially those related to computations. It is also prevalent in the research literature on linear programming.

We can convert any given minimization LP problem to an equivalent one in standard form using one of the following transformations:

• If $x_i$ is constrained to be nonpositive (i.e. $x_i\le 0$), create a new variable $x_i^{\prime }$ and replace every occurrence of $x_i$ with $-x_i^{\prime }$. Note that $x_i\le 0$ becomes $x_i^{\prime }\ge 0$.

• If $x_i$ is a free variable, create two new variable $x_i^{+}$ and $x_i^{-}$ and replace every occurrence of $x_i$ with $x_i^{+}-x_i^{-}$ and add $x_i^{+}\ge 0,x_i^{-}\ge 0$ to the problem.

• For an inequality ${\mathbf{a}}^{\mathsf{T}}\mathbf{x}\le \beta$, create a new slack variable $s$ and replace the inequality ${\mathbf{a}}^{\mathsf{T}}\mathbf{x}\le \beta$ with ${\mathbf{a}}^{\mathsf{T}}\mathbf{x}+s=\beta$ and $s\ge 0$.

• For an inequality ${\mathbf{a}}^{\mathsf{T}}\mathbf{x}\ge \beta$, create a new surplus variable $s$ and replace the inequality ${\mathbf{a}}^{\mathsf{T}}\mathbf{x}\ge \beta$ with ${\mathbf{a}}^{\mathsf{T}}\mathbf{x}-s=\beta$ and $s\ge 0$.

It is not difficult to check that each of the above transformations results in an equivalent LP problem in the sense that every feasible solution to the transformed problem can be converted to a feasible solution to the original LP problem with the same objective function value and vice versa. Furthermore, the transformed problem has an optimal solution if and only if the original problem does.

Example

We convert the following into an equivalent LP problem in standard form: $$\begin{array}{rrcr}min& 3x& +& 2y\\ \text{s.t.}& x& +& 3y& \le & 6\\ & -7x& -& y& \ge & 4\\ & x& & & \le & 0\\ & & & y& & \text{free}.\end{array}$$

First, we replace $x$ with $-x^{\prime }$ and $y$ with $y^{+}-y^{-}$, $y^{+},y^{-}\ge 0$ to obtain $$\begin{array}{rrcrcr}min& -3x^{\prime }& +& 2y^{+}& -& 2y^{-}\\ \text{s.t.}& -x^{\prime }& +& 3y^{+}& -& 3y^{-}& \le & 6\\ & 7x^{\prime }& -& y^{+}& +& y^{-}& \ge & 4\\ & x^{\prime }& ,& y^{+}& ,& y^{-}& \ge & 0.\end{array}$$

Finally, we introduce a slack variable $s$ to the first inequality and a surplus variable $t$ to the second inequality to obtain: $$\begin{array}{rrcrcr}min& -3x^{\prime }& +& 2y^{+}& -& 2y^{-}\\ \text{s.t.}& -x^{\prime }& +& 3y^{+}& -& 3y^{-}& +& s& & & =& 6\\ & 7x^{\prime }& -& y^{+}& +& y^{-}& & & -& t& =& 4\\ & x^{\prime }& ,& y^{+}& ,& y^{-}& ,& s& ,& t& \ge & 0.\end{array}$$