Standard Form of a Linear Program

Convert any linear program into standard form: a maximization with all constraints written as $\le$ inequalities and all decision variables non-negative. Handle minimization objectives, $\ge$ constraints, equality constraints, and free (unrestricted) variables via variable splitting.

Step 1 of 157%

Tutorial

Standard Form: Definition and First Two Rules

A linear program is in standard form when it is written as

\begin{align*}\text{maximize} \quad & c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \\ \text{subject to} \quad & a_{i1} x_1 + a_{i2} x_2 + \cdots + a_{in} x_n \le b_i, \quad i = 1, \ldots, m \\ & x_1, x_2, \ldots, x_n \ge 0. \end{align*}

Three requirements must hold:

The objective is maximized.
Every constraint is a $\le$ inequality.
Every decision variable is non-negative.

Any LP can be converted into standard form. The two simplest rules:

Minimization to maximization: $\min f(\mathbf{x}) \;\Longleftrightarrow\; \max\bigl(-f(\mathbf{x})\bigr).$ Negate every coefficient in the objective. (The optimal value flips sign; the optimal $\mathbf{x}$ is unchanged.)
$\ge$ to $\le$ : Multiply both sides of the constraint by $-1$ and reverse the direction. So $a^T \mathbf{x} \ge b$ becomes $-a^T \mathbf{x} \le -b$ .

For example, $\min 5x_1 - 2x_2$ becomes $\max -5x_1 + 2x_2$ , and $3x_1 + x_2 \ge 7$ becomes $-3x_1 - x_2 \le -7$ .