Linear programming, sometimes known as linear optimization, is the problem of maximizing or minimizing a linear function over a convex
polyhedron specified by linear and non-negativity constraints. Simplistically,
linear programming is the optimization of an outcome based on some set
of constraints using a linear mathematical model.
Linear programming is implemented in the Wolfram Language as LinearOptimization[f,
cons, vars], which minimizes the linear
function
subject to the linear constraints cons over the variablesvars.
For example, a vector minimizing subject to and for can be found.
Linear programming theory falls within convex optimization theory and is also considered to be an important part of operations
research. Linear programming is extensively used in business and economics, but
may also be used to solve certain engineering problems.
Examples from economics include Leontief's input-output model, the determination of shadow prices, etc., an example of a business application would be maximizing profit in a factory that manufactures a number of different products from the same raw material using the same resources, and example engineering applications include Chebyshev approximation and the design of structures (e.g., limit analysis of a planar truss).
Linear programming can be solved using the simplex method (Wood and Dantzig 1949, Dantzig 1949), which moves along polytope
edges when the feasible region is a polytope. Khachian
(1979) gave a polynomial timealgorithm.
Karmarkar (1984) developed another polynomial timealgorithm, an interior
point method based on projectivities. Interior
point methods were known as early as the 1960s in the form of barrier function methods,
but the attention accompanying Karmarkar's announcement led to renewed interest in
them.
In the Season 4 opening episode "Trust Metric" (2007) of the television crime drama NUMB3RS, math genius Charlie
Eppes uses the phrase "you don't need Karmarkar's algorithm" to mean "you
don't need to be a rocket scientist to know...."
subject to the linear constraints cons over the variables vars.
For example, a vector 
minimizing 
subject to 
and 
for 
can be found.
