What Is Linear Programming?

Linear programming, also known as linear optimization, is minimizing or maximizing a linear objective function subject to bounds, linear equality, and linear inequality constraints. Example problems include blending in process industries, production planning in manufacturing, cash flow matching in finance, and planning in energy and transportation.

Linear programming is the mathematical problem of finding a vector \(x\) that minimizes the function:

\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]

Subject to the constraints:

\[\begin{eqnarray}Ax \leq b & \quad & \text{(inequality constraint)} \\A_{eq}x = b_{eq} & \quad & \text{(equality constraint)} \\lb \leq x \leq ub & \quad & \text{(bound constraint)}\end{eqnarray}\]

Linear Programming with MATLAB

You can use MATLAB^® to implement the following commonly used algorithms to solve linear programming problems:

• Interior point: Uses a primal-dual predictor-corrector algorithm and is especially useful for large-scale linear programs that have structure or can be defined using sparse matrices.
• Simplex: Uses a systematic procedure for generating and testing candidate vertex solutions to a linear program. The simplex algorithm and the related dual-simplex algorithm are the most widely used algorithms for linear optimization.

The linprog solver in Optimization Toolbox™ implements these linear optimization techniques.

Special Cases of Linear Programming

Algorithms for some special cases of linear optimization problems where the constraints have a network structure are typically faster than the general-purpose interior-point and simplex algorithms. Special cases include:

• Maximum network flow: Uses augmenting-path and push-relabel algorithms.
• Shortest path: Uses Dijkstra, Bellman-Ford, and search algorithms.
• Linear assignment: Uses a bipartite matching algorithm.

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