Free variables
Free Variables
A free variable is a variable with no sign restriction.
It can be positive, zero, or negative.
Standard form requires all variables to be nonnegative, so free variables must be replaced.
Definition
A free variable satisfies:
\[x_j\in\mathbb{R}\]It is not restricted by:
\[x_j\ge 0\]or:
\[x_j\le 0\]Standard Replacement
Replace the free variable by the difference of two nonnegative variables:
\[x_j=x_j^+-x_j^-\]where:
\[x_j^+\ge 0, \qquad x_j^-\ge 0\]This works because every real number can be written as the difference of two nonnegative numbers.
Example
If $x_1$ is free, replace it by:
\[x_1=x_1^+-x_1^-\]Then every occurrence of $x_1$ is replaced.
For example:
\[2x_1+3x_2\le 5\]becomes:
\[2(x_1^+-x_1^-)+3x_2\le 5\]or:
\[2x_1^+-2x_1^-+3x_2\le 5\]Objective Example
If the objective contains:
\[4x_1+x_2\]and $x_1$ is free, then:
\[4x_1+x_2=4x_1^+-4x_1^-+x_2\]So the new objective coefficients for $x_1^+$ and $x_1^-$ are:
\[4, \qquad -4\]Non-Unique Representation
The representation:
\[x_j=x_j^+-x_j^-\]is not unique.
For example:
\[3=3-0=4-1=10-7\]This is acceptable for standard-form conversion.
At an optimal basic solution, usually not both parts are positive, but the conversion itself does not require that.
Alternative Elimination Method
Sometimes a free variable can be eliminated using an equality constraint.
If an equality contains $x_j$ with nonzero coefficient, solve that equation for $x_j$ and substitute into the rest of the problem.
This reduces the number of variables and constraints.
However, the difference method is usually simpler and safer for exams.
Full Example
Original problem:
\[\min x_1+3x_2\]subject to:
\[x_1+2x_2=5\] \[x_2\ge 0\]where $x_1$ is free.
Replace:
\[x_1=x_1^+-x_1^-\]Then:
\[\min x_1^+-x_1^-+3x_2\]subject to:
\[x_1^+-x_1^-+2x_2=5\] \[x_1^+,x_1^-,x_2\ge 0\]This is now compatible with standard form.
Common Mistake
Do not simply write:
\[x_j\ge 0\]if the original variable is free.
That changes the feasible region and may change the answer.
Checklist
You understand free variables if you can:
- identify a variable with no sign restriction
- replace it by $x_j^+-x_j^-$
- substitute into every constraint and the objective
- remember that both new variables must be nonnegative
- avoid accidentally imposing $x_j\ge 0$
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.