Linear programming
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 Mathematica as LinearProgramming[c, m, b],
which finds a vector 
which minimizes the quantity
subject to the constraints 
and 
for 
.
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 runs along polytope edges of the visualization solid to find the best
answer. Khachian (1979) found a 
polynomial time algorithm.
A much more efficient polynomial
time algorithm was found by Karmarkar
(1984). This method goes through the middle of the solid (making it a so-called interior point method), and
then transforms and warps. Arguably, interior point methods were known as early as
the 1960s in the form of the barrier function methods, but the media hype accompanying
Karmarkar's announcement led to these methods receiving a great deal of attention.
Linear programming in which variables may take on integer values only is known as
integer programming.
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...."
Bellman, R. and Kalaba, R. Dynamic Programming and Modern Control Theory. New York:
Academic Press, 1965.
Dantzig, G. B. "Programming of Interdependent Activities. II. Mathematical Model."
Econometrica 17, 200-211, 1949.
Dantzig, G. B. Linear Programming and Extensions. Princeton, NJ: Princeton
University Press, 1963.
Greenberg, H. J. "Mathematical Programming Glossary." http://carbon.cudenver.edu/~hgreenbe/glossary/.
Karloff, H. Linear Programming. Boston, MA: Birkhäuser, 1991.
Khachian, L. G. "A Polynomial Algorithm in Linear Programming." Dokl. Akad. Nauk SSSR 244, 1093-1096, 1979. English translation in Soviet
Math. Dokl. 20, 191-194, 1979.
Karmarkar, N. "A New Polynomial-Time Algorithm for Linear Programming."
Combinatorica 4, 373-395, 1984.
Pappas, T. "Projective Geometry & Linear Programming." The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra,
pp. 216-217, 1989.
Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Linear Programming and the Simplex Method." §10.8 in Numerical Recipes in FORTRAN: The Art of Scientific Computing,
2nd ed. Cambridge, England: Cambridge University Press, pp. 423-436, 1992.
Sultan, A. Linear Programming: An Introduction with Applications.
San Diego, CA: Academic Press, 1993.
Tokhomirov, V. M. "The Evolution of Methods of Convex Optimization." Amer.
Math. Monthly 103, 65-71, 1996.
Weisstein, E. W. "Books about Linear Programming." http://www.ericweisstein.com/encyclopedias/books/LinearProgramming.html.
Wood, M. K. and Dantzig, G. B. "Programming of Interdependent Activities. I.
General Discussion." Econometrica 17, 193-199, 1949.
Yudin, D. B. and Nemirovsky, A. S. Problem Complexity and Method Efficiency in Optimization.
New York: Wiley, 1983.
