Linear Programming

Solve linear optimization problems

Linear programming (LP),involves minimizing or maximizing a linear 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:

Linear Programming

Subject to the constraints:

Linear Programming (inequality constraint)
Linear Programming (equality constraint)
Linear Programming (bound constraint)

The following algorithms are commonly used to solve linear optimization 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.
  • Active-set: Minimizes the objective of the linear optimization problem 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 and the related dual-simplex algorithm are the most widely used algorithms for linear programming.

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

Examples and How To

Software Reference

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

Optimization Techniques Training Course

In this course you’ll learn applied optimization techniques in the MATLAB® environment, focusing on using Optimization Toolbox™ and Global Optimization Toolbox.

Learn more and register