Introduction to Linear Programming

Linear Programs in Standard Form

Every linear program can be converted into standard form to be used in algorithms like the Simplex algorithm where the objective is maximized, the constraints are equalities and all variables $x_i$ are non-negative like so:

$$\begin{array}{rll} \mathbf{\text{max}} &c_1x_1 + c_2x_2 + ...+c_nx_n&\\ \mathbf{\text{subject to}} & a_{11}x_1+a_{12}x_2+...a_{1n}x_n &= b_1\\ &...&=...\\ &a_{m1}x_1+a_{m2}x_2 + ...+a_{mn}x_n &= b_m\\ &x_1\geq 0, ...x_n\geq0& \end{array}$$

To get linear program into standard form, we apply each of the following rules:

Rule 1: If the problem is $\mathbf{\text{min }} z$, convert it to $\mathbf{\text{max }} -z$

Example: $\mathbf{\text{min }} x_1+x_2\Rightarrow \mathbf{\text{max }} -x_1-x_2$

Rule 2: Remove a negative RHS by multiplying the whole constraint by $-1$

Example: $-2x_1+4x_2-x_3\geq -9\Rightarrow 2x_1-4x_2+x_3 \mathbf{\leq} 9$

Rule 3: If a constraint reads $a_{i1}x_1+a_{i2}x_2 +...+a_{in}x_n\mathbf{\leq} b_i$, add a non-negative slack variable $s_i\geq0$ to get $a_{i1}x_1+a_{i2}x_2 +...+a_{in}x_n\mathbf{+}s_i\mathbf{=} b_i$. The slack variable represents the amount of unused resource.

Example: $x_1+2x_2+x_3-x_4\leq 5\Rightarrow x_1+2x_2+x_3-x_4+s_1= 5$

Rule 4: If a constraint reads $a_{i1}x_1+a_{i2}x_2 +...+a_{in}x_n\mathbf{\geq} b_i$, subtract a non-negative surplus variable $s_i\geq0$ to get $a_{i1}x_1+a_{i2}x_2 +...+a_{in}x_n\mathbf{-}s_i\mathbf{=} b_i$. The surplus variables represent the amount the LHS exceeds the RHS.

Example: $x_1+2x_2+x_3-x_4\geq 5\Rightarrow x_1+2x_2+x_3-x_4-s_1= 5$

Rule 5: If a variable $x_j$ can be positive or negative (called a free variable, which is unrestricted in sign), substitute $x_j$ everywhere (also in the objective) with the difference $x'_j-x''_j$ where $x'_j\geq0$ and $x''_j\geq0$.

Example: $x_1+3x_2\leq 7\Rightarrow x_1+3x'_2-3x''_2\leq 7$ with $x'_3, x''_3\geq 0$ and $x_3\in\mathbb{R}$

Another way to remove free variables is to substitute $x_j$ with a constraint that contains the variable.

Example: We have the constraint $x_1+2x_2+x_3= 4$ and $x_3$ can be positive or negative, then solve for $x_3= 4-x_1-2x_2$ and substitute $4-x_1-2x_2$ for every $x_3$.

Rule 6: Resolve variables and constraints with percentages. The total of all utilization is $x_1+x_2+...x_n$. If a constraint must be $x_k$ to have $p$ percent, we can write $\frac{x_k}{x_1+x_2+x_k+...x_n}\leq p\Leftrightarrow (1-p)x_k-px_1-px_2-...-px_n\leq 0$.

Example: We want at least $p=30\%$ of $x_2$ and we have 3 variables. So $\frac{x_3}{x_1+x_2+x_3}\geq 0.3$ from which follows $0.7x_3-0.3x_1-0.3x_2\leq 0$.

Another way to solve percentage constraints is by introducing a summation variable $x_{n+1} = x_1+x_2+...+x_n$ from which follows the set of contraints

$$\begin{array}{rl} x_1+x_2+...+x_n-x_{n+1}&=0\\ x_1-px_{n+1}&\leq 0\\ x_2-px_{n+1}&\leq 0\\ ...&\\ x_n-px_{n+1}&\leq 0\\ \end{array}$$

This form is easier to compute since a lot of zero-coefficients are in the matrix. But this adds another variable, which might increase the overall execution time.

Simplex algorthm