Contents
raw book

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 xix_i are non-negative like so:

maxc1x1+c2x2+...+cnxnsubject toa11x1+a12x2+...a1nxn=b1...=...am1x1+am2x2+...+amnxn=bmx10,...xn0\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 min z\mathbf{\text{min }} z, convert it to max z\mathbf{\text{max }} -z

Example: min x1+x2max x1x2\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-1

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

Rule 3: If a constraint reads ai1x1+ai2x2+...+ainxnbia_{i1}x_1+a_{i2}x_2 +...+a_{in}x_n\mathbf{\leq} b_i, add a non-negative slack variable si0s_i\geq0 to get ai1x1+ai2x2+...+ainxn+si=bia_{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: x1+2x2+x3x45x1+2x2+x3x4+s1=5x_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 ai1x1+ai2x2+...+ainxnbia_{i1}x_1+a_{i2}x_2 +...+a_{in}x_n\mathbf{\geq} b_i, subtract a non-negative surplus variable si0s_i\geq0 to get ai1x1+ai2x2+...+ainxnsi=bia_{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: x1+2x2+x3x45x1+2x2+x3x4s1=5x_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 xjx_j can be positive or negative (called a free variable, which is unrestricted in sign), substitute xjx_j everywhere (also in the objective) with the difference xjxjx'_j-x''_j where xj0x'_j\geq0 and xj0x''_j\geq0.

Example: x1+3x27x1+3x23x27x_1+3x_2\leq 7\Rightarrow x_1+3x'_2-3x''_2\leq 7 with x3,x30x'_3, x''_3\geq 0 and x3Rx_3\in\mathbb{R}

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

Example: We have the constraint x1+2x2+x3=4x_1+2x_2+x_3= 4 and x3x_3 can be positive or negative, then solve for x3=4x12x2x_3= 4-x_1-2x_2 and substitute 4x12x24-x_1-2x_2 for every x3x_3.

Rule 6: Resolve variables and constraints with percentages. The total of all utilization is x1+x2+...xnx_1+x_2+...x_n. If a constraint must be xkx_k to have pp percent, we can write xkx1+x2+xk+...xnp(1p)xkpx1px2...pxn0\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%p=30\% of x2x_2 and we have 3 variables. So x3x1+x2+x30.3\frac{x_3}{x_1+x_2+x_3}\geq 0.3 from which follows 0.7x30.3x10.3x200.7x_3-0.3x_1-0.3x_2\leq 0.

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

x1+x2+...+xnxn+1=0x1pxn+10x2pxn+10...xnpxn+10\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