Editing Linear programming (section)

{{short description|Method to solve optimization problems}}
{{for|the retronym referring to television broadcasting|Broadcast programming}}
[[File:Linear optimization in a 2-dimensional polytope.svg|thumb|A pictorial representation of a simple linear program with two variables and six inequalities. The set of feasible solutions is depicted in yellow and forms a [[polygon]], a 2-dimensional [[polytope]]. The optimum of the linear cost function is where the red line intersects the polygon. The red line is a [[level set]] of the cost function, and the arrow indicates the direction in which we are optimizing.]]
[[File:3dpoly.svg|thumb|right|A closed feasible region of a problem with three variables is a convex [[polyhedron]]. The surfaces giving a fixed value of the objective function are [[Plane (geometry)|planes]] (not shown). The linear programming problem is to find a point on the polyhedron that is on the plane with the highest possible value.]]

'''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 function#As a polynomial function|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 [[mathematical optimization|optimization]] of a [[linear]] [[objective function]], subject to [[linear equality]] and [[linear inequality]] [[Constraint (mathematics)|constraints]]. Its [[feasible region]] is a [[convex polytope]], which is a set defined as the [[intersection (mathematics)|intersection]] of finitely many [[Half-space (geometry)|half spaces]], each of which is defined by a linear inequality<!-- ;  alternatively, a convex polytope is the [[Minkowski sum]] of a [[convex polytope]] and a convex [[polyhedral cone]] -->. Its objective function is a [[real number|real]]-valued [[affine function|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 [[canonical form|standard form]] as:
:<math> \begin{align}
& \text{Find a vector} && \mathbf{x} \\
& \text{that maximizes}   && \mathbf{c}^\mathsf{T} \mathbf{x}\\
& \text{subject to} && A \mathbf{x} \le \mathbf{b} \\
& \text{and} && \mathbf{x} \ge \mathbf{0}.
\end{align} </math>
Here the components of <math>\mathbf{x}</math> are the variables to be determined, <math>\mathbf{c}</math> and <math>\mathbf{b}</math> are given [[vector space|vectors]], and <math>A</math> is a given [[Matrix (mathematics)|matrix]]. The function whose value is to be maximized (<math>\mathbf x\mapsto\mathbf{c}^\mathsf{T}\mathbf{x}</math> in this case) is called the [[objective function]]. The constraints <math>A \mathbf{x} \le \mathbf{b}</math> and <math>\mathbf{x} \geq \mathbf{0}</math> 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).<ref>{{cite journal |last=von Neumann |first=J. |year=1945 |title=A Model of General Economic Equilibrium |journal=The Review of Economic Studies |volume=13 |issue=1 |pages=1–9|doi=10.2307/2296111 |jstor=2296111 }}</ref>
<ref>{{Cite journal
| last1 = Kemeny
| first1 = J. G.
| last2 = Morgenstern
| first2 = O.
| last3 = Thompson
| first3 = G. L.
| year = 1956
| title = A Generalization of the von Neumann Model of an Expanding Economy
| journal = Econometrica
| volume = 24
| issue = 2
| pages = 115–135
| doi = 10.2307/1905746
| jstor = 1905746
}}</ref>
<ref>{{Cite book
| last = Li
| first = Wu
| title = General Equilibrium and Structural Dynamics: Perspectives of New Structural Economics
| year = 2019
| publisher = Economic Science Press
| location = Beijing
| isbn = 978-7-5218-0422-5
| language = zh
| pages = 122–125
}}</ref>
Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proven useful in modeling diverse types of problems in [[automated planning and scheduling|planning]], [[routing]], [[scheduling (production processes)|scheduling]], [[assignment problem|assignment]], and design.