Standard Form of Linear Programming Models

Introduction

Referring to Top Brass Tropy example, the LP model is given as follows:

\[ \begin{align} \max \quad & 12x_1 + 9x_2 & (\text{profit}) \\ \text{s.t.} \quad & x_1 \leq 1000 & (\text{footballs}) \\ & x_2 \leq 1500 & (\text{soccer balls}) \\ & x_1 + x_2 \leq 1750 & (\text{plaques}) \\ & 4x_1 + 2x_2 \leq 4800 & (\text{wood}) \\ & x_1, x_2 \geq 0 \end{align} \]

LPs in standard form has the following properties:

1. All variables are nonnegative.
2. All main constraints are equality constraints.
3. Objective function and main constraints are simplified so that variables appear at most once on the left-hand-side (LSH) and any constant including zeros appers on the right-hand-side (RHS).

Main inequality constraints can be converted into equalities by adding or substractiong non-negative slack or surplus variables. All maing constraints above can be converted into equalities by adding slack variables \(x_3, x_4, x_5, x_6\) as follows:

\[ \begin{align} \max \quad & 12x_1 + 9x_2 \\ \text{s.t.} \quad & x_1 + x_3 &= 1000 \\ & x_2 + x_4 &= 1500 \\ & x_1 + x_2 + x_5 &= 1750 \\ & 4x_1 + 2x_2 + x_6 &= 4800 \\ & x_1, x_2, x_3, x_4, x_5, x_6 &\geq 0 \end{align} \]

see example 5.3 in the textbook.

Non-positive variables can be eliminated by substituting new variables equal to their negatives. Assume we have ten variables \(x_1, x_2, \ldots, x_{10}\) and \(x_7\) is non-positive. Then we can substitute \(x_7 = -y_7\) and \(y_7 \geq 0\). Then the new variable \(y_7\) will replace \(x_7\) in the model.

If a variable is unrestricted (i.e. it can take negative, positive, or zero values), then it can be represented as the difference of two non-negative variables. Assume we have a variable \(x_1\) that is unrestricted. Then we can substitute \(x_1 = x_1^+ - x_1^-\) where \(x_1^+\) and \(x_1^-\) are non-negative variables. Then the new variables \(x_1^+\) and \(x_1^-\) will replace \(x_1\) in the model.

see example 5.4 in the textbook.

Standard Form of LP Models

Standard LPs can be represented as follows:

\[ \begin{align} \max \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \geq 0 \end{align} \]

where \(c\) is the vector of objective function coefficients, \(x\) is the vector of decision variables, \(A\) is the matrix of constraint coefficients, and \(b\) is the vector of right-hand-side values.

or in sum product notation:

\[ \begin{align} \max \quad & \sum_{j=1}^n c_j x_j \\ \text{s.t.} \quad & \sum_{j=1}^n a_{ij} x_j = b_i, \quad i = 1, 2, \ldots, m \\ & x_j \geq 0, \quad j = 1, 2, \ldots, n \end{align} \]

where \(c_j\) is the objective function coefficient of variable \(x_j\), \(a_{ij}\) is the coefficient of variable \(x_j\) in constraint \(i\), \(b_i\) is the right-hand-side value of constraint \(i\), \(n\) is the number of decision variables, and \(m\) is the number of constraints.

see example 5.5 in the textbook.

References

1: Optimization in OR textbook by R. Rardin