Equality and Inequality Constraints
Standard form uses equality constraints only.
General LP problems may contain equalities and inequalities, so we must know how to convert each type.
Standard-Form Constraint
In standard form, constraints are written as:
\[Ax=b\]That means each row is an equality:
\[a_i^Tx=b_i\]Equality Constraints
An equality constraint is already in the correct type.
Example:
\[2x_1+x_2=5\]Keep it as:
\[2x_1+x_2=5\]No slack or surplus variable is needed.
Less-Than-or-Equal Constraints
A constraint of the form:
\[a_i^Tx\le b_i\]is converted by adding a slack variable:
\[a_i^Tx+s_i=b_i\]where:
\[s_i\ge 0\]Greater-Than-or-Equal Constraints
A constraint of the form:
\[a_i^Tx\ge b_i\]is converted by subtracting a surplus variable:
\[a_i^Tx-s_i=b_i\]where:
\[s_i\ge 0\]Summary Table
| Original constraint | Standard-form equality |
|---|---|
| $a_i^Tx=b_i$ | $a_i^Tx=b_i$ |
| $a_i^Tx\le b_i$ | $a_i^Tx+s_i=b_i$, $s_i\ge 0$ |
| $a_i^Tx\ge b_i$ | $a_i^Tx-s_i=b_i$, $s_i\ge 0$ |
Example
Convert:
\[3x_1-x_2=10\] \[x_2+2x_3\le 5\] \[3x_1+5x_2+x_3\ge 10\]with:
\[x_1,x_2,x_3\ge 0\]The first constraint stays the same:
\[3x_1-x_2=10\]The second gets a slack variable:
\[x_2+2x_3+s_1=5\]The third gets a surplus variable:
\[3x_1+5x_2+x_3-s_2=10\]with:
\[x_1,x_2,x_3,s_1,s_2\ge 0\]Inequality Direction Matters
For $\le$, add.
For $\ge$, subtract.
This is because:
\[a_i^Tx\le b_i \quad \Rightarrow \quad b_i-a_i^Tx\ge 0\]so the nonnegative difference is added to the left-hand side.
And:
\[a_i^Tx\ge b_i \quad \Rightarrow \quad a_i^Tx-b_i\ge 0\]so the nonnegative excess is subtracted from the left-hand side.
Multiplying Constraints by Negative One
Sometimes it is useful to multiply a constraint by $-1$.
When you do this, the inequality direction changes:
\[a^Tx\le b\]becomes:
\[-a^Tx\ge -b\]and:
\[a^Tx\ge b\]becomes:
\[-a^Tx\le -b\]Equality direction does not change.
Common Mistakes
Do not add slack to a $\ge$ constraint.
Do not subtract surplus from a $\le$ constraint.
Do not forget to add the new slack or surplus variables to the nonnegativity restrictions.
Checklist
You understand equality and inequality conversion if you can:
- keep equality constraints unchanged
- add slack for $\le$
- subtract surplus for $\ge$
- reverse inequality direction when multiplying by $-1$
- write all new variables as nonnegative
See Also
Exam checkpoint
For standard-form questions, use the course convention $\min c^Tx$ subject to $Ax=b$, $x\ge0$. Convert max objectives, add slack to $\le$, subtract surplus from $\ge$, and split free variables.