= Solution
Using the <standard maximum form of a linear program>, write
$$
\boxed{\max c^Tx\quad\text{subject to }Ax\leq b,\quad x\geq0,}
$$
where $x\in\mathbb R^n$, $A\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, and $c\in\mathbb R^n$. The inequalities are coordinatewise, and $c^Tx$ is the <objective function>. General <linear programs> can be put in this form: reverse the sign of a minimization <objective function>, reverse lower-bound <linear inequalities>, replace an equality by two opposite <linear inequalities>, and replace each unrestricted variable by the difference of two nonnegative variables. Some conventions instead call the equality-constraint version standard form; the convention here is the maximum-with-upper-bounds convention.
Introduce nonnegative <slack variables> $x_{n+i}=b_i-\sum_{j=1}^n a_{ij}x_j$. The equivalent <slack form of a linear program> is
$$
\boxed{
\begin{aligned}
z&=\sum_{j=1}^n c_jx_j,\\
x_{n+i}&=b_i-\sum_{j=1}^n a_{ij}x_j\quad(1\leq i\leq m),\\
x_j&\geq0\quad(1\leq j\leq n+m).
\end{aligned}}
$$
The original variables are initially nonbasic and the <slack variables> basic. More generally, a <slack form of a linear program> specifies disjoint index <sets> $N,B$ and writes
$$
z=v+\sum_{j\in N}c_jx_j,\qquad
x_i=b_i-\sum_{j\in N}a_{ij}x_j\quad(i\in B),\qquad
x_i\geq0\quad(i\in N\cup B).
$$
Thus each <basic variable> and the <objective function> are expressed using only <nonbasic variables>. Setting all <nonbasic variables> to zero gives the associated <basic solution>, which is a <feasible solution> exactly when the resulting basic values are nonnegative. The <slack form of a linear program> does not itself require that initial <basic solution> to be feasible.
Back to article page
