## Linear Programming |

Linear programming (LP) involves minimizing or maximizing an objective function subject to bounds, linear equality, and inequality constraints. Example problems include design optimization in engineering, profit maximization in manufacturing, portfolio optimization in finance, and scheduling in energy and transportation.

Linear programming is the mathematical problem of finding a vector $x$ that minimizes the function:

$\underset{x}{\mathrm{min}}\mathrm{}\left\{f{}^{T}x\right\}$

Subject to the constraints:

$Ax\le b$ | (inequality constraint) |

${A}_{\mathrm{eq}}x={b}_{\mathrm{eq}}$ | (equality constraint) |

$\mathrm{lb}\le x\le \mathrm{ub}$ | (bound constraint) |

The following algorithms are commonly used to solve linear programming problems:

**Interior point:**Uses a primal-dual predictor-corrector algorithm and is especially useful for large-scale problems that have structure or can be defined using sparse matrices.**Active-set:**Minimizes the objective at each iteration over the active set (a subset of the constraints that are locally active) until it reaches a solution.**Simplex:**Uses a systematic procedure for generating and testing candidate vertex solutions to a linear program. The simplex algorithm is the most widely used algorithm for linear programming.

For more information on algorithms and linear programming, see Optimization Toolbox.

- Linear Programming and Binary Integer Programming (Example)
- Introduction to Optimization Graphical User Interface 6:08 (Video)
- Mixed-Integer Linear Programming in MATLAB 34:08 (Webinar)

- linprog Function in Optimization Toolbox (Functions)
- Interior Point Algorithm (Documentation)
- Active Set Algorithm (Documentation)
- Simplex Algorithm (Documentation)

*See also*: *Optimization Toolbox*, *Global Optimization Toolbox*, *integer programming*, *quadratic programming*, *nonlinear programming*, *multiobjective optimization*, *genetic algorithm*, *simulated annealing*