Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization).

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polytope. A linear programming algorithm finds a point in the polytope where this function has the largest (or smallest) value if such a point exists.

Linear programs are problems that can be expressed in standard form as:

{\begin{aligned}&{\text{Find a vector}}&&\mathbf {x} \\&{\text{that maximizes}}&&\mathbf {c} ^{\mathsf {T}}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}

Here the components of $\mathbf {x}$ are the variables to be determined, $\mathbf {c}$ and $\mathbf {b}$ are given vectors, and $A$ is a given matrix. The function whose value is to be maximized ( $\mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x}$ in this case) is called the objective function. The constraints $A\mathbf {x} \leq \mathbf {b}$ and $\mathbf {x} \geq \mathbf {0}$ specify a convex polytope over which the objective function is to be optimized.

Linear programming can be applied to various fields of study. It is widely used in mathematics and, to a lesser extent, in business, economics, and some engineering problems. There is a close connection between linear programs, eigenequations, John von Neumann's general equilibrium model, and structural equilibrium models (see dual linear program for details).^[1] ^[2] ^[3] Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proven useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.

^ von Neumann, J. (1945). "A Model of General Economic Equilibrium". The Review of Economic Studies. 13 (1): 1–9. doi:10.2307/2296111. JSTOR 2296111.
^ Kemeny, J. G.; Morgenstern, O.; Thompson, G. L. (1956). "A Generalization of the von Neumann Model of an Expanding Economy". Econometrica. 24 (2): 115–135. doi:10.2307/1905746. JSTOR 1905746.
^ Li, Wu (2019). General Equilibrium and Structural Dynamics: Perspectives of New Structural Economics (in Chinese). Beijing: Economic Science Press. pp. 122–125. ISBN 978-7-5218-0422-5.

[1] von Neumann, J. (1945). "A Model of General Economic Equilibrium". The Review of Economic Studies. 13 (1): 1–9. doi:10.2307/2296111. JSTOR 2296111.

[2] Kemeny, J. G.; Morgenstern, O.; Thompson, G. L. (1956). "A Generalization of the von Neumann Model of an Expanding Economy". Econometrica. 24 (2): 115–135. doi:10.2307/1905746. JSTOR 1905746.

[3] Li, Wu (2019). General Equilibrium and Structural Dynamics: Perspectives of New Structural Economics (in Chinese). Beijing: Economic Science Press. pp. 122–125. ISBN 978-7-5218-0422-5.

[1]

[2]

[3]