Equality and inequality constraints
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.