Linear programming
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 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 Polyhedra, which allows solving and modelling certain problems 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 computers were used to solve such problems. Looking at the information theory complexity, linear programming problems are simple, and can be solved efficiently using algorithms 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.
Linear Programming Media
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 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.
Nobel laureates Leonid Kantorovich
John von Neumann
Graphical solution to the farmer example – after shading regions violating the conditions, the vertex of the unshaded region with the dashed line farthest from the origin gives the optimal combination (its lying on the pesticide and land lines implies that pesticide and land limit revenue)
