Linear Programming¶
Overview¶
Linear Programming is a method by which an optimal, minimum or maximum, outcome is obtained for mathamatical models formed from linear functions of decision variables subject to constraints.
Typically, a linear program (LP) takes the following form.
where \(\sum{c^{T}x}\) is the cost function or objective function, \(x_j\) is the optimization variable, and \(Ax = b\) and \(l \le x \le u\) are constraints. In such a problem, \(A, b, c, l,\) and \(u\) are assumed to be known parameters of the mathematical model.
Important Concepts¶
Review the following concepts.
Solving Linear Programs¶
- LPs can be efficiently solved with the following numerical methods:
- simplex, dual simplex method
- interior point methods for LPs with very sparse matricies
- decomposition, dual decomposition and regularized decomposition approaches for LP’s with special block structures of their coefficient matrices A
Stochastic Linear Programs¶
In many applications of Linear Programming, exact values are not known for the mathematical model; rather, expectations are used. As a result, the solution must be computed with different methods in order to achieve a desired probability distribution, rather than a known solution.