What is Linear programming?
[[File:Linear Programming Feasible Region.svg|frame|A series of linear constraints on two variables produces a region of possible values for those variables. Solvable problems will have a feasible region in the shape of a [[simple polygon]].]] '''Linear programming''' or '''Linear optimisation''' is a field of [[mathematics]] that deals with finding optimal values or solutions that can be described with linear equations and [[inequality|inequalities]]. Very often this involves finding the minimal or maximal values, given some conditions, or constraints. Linear programming is often used for problems where no exact solution is known, for example for planning traffic flows. Linear programming is one of the main methods used in [[Operations research]]. Linear optimization is a special case of [[Convex optimization]]. It forms the basis for several methods of solving problems of [[Integer programming]]. In many cases, the solutions of linear programs can be mapped to [[Polyhedron|Polyhedra]], which allows solving and modelling certain problems [[geometry|geometrically]]. In the case of linear programming, the word ''programming'' should be seen as ''planning''; [[George Dantzig]] coined the term in the 1940s, long before [[computer]]s were used to solve such problems. Looking at the information theory [[complexity]], linear programming problems are simple, and can be solved efficiently using [[algorithm]]s such as the [[interior point method]]. In many cases, the [[Simplex algorithm]] developed by Dantzig has proven to be very fast, even though its complexity is exponential, in the worst case. [[Leonid Kantorovich]] developed the first methods of linear programming in 1939. {{math-stub}} [[Category:Combinatorial optimization]]