Linear Programming

Linear programming (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships. Linear programming is a specific case of mathematical programming (mathematical optimization).

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polyhedron, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such a point exists.

Linear programs are problems that can be expressed in canonical form:

& text{maximize} && mathbf{c}^mathrm{T} mathbf{x}\
& text{subject to} && A mathbf{x} leq mathbf{b} \
& text{and} && mathbf{x} ge mathbf{0}

where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients, A is a (known) matrix of coefficients, and is the matrix transpose. The expression to be maximized or minimized is called the objective function (cTx in this case). The inequalities Axb are the constraints which specify a convex polytope over which the objective function is to be optimized. In this context, two vectors are comparable when they have the same dimensions. If every entry in the first is less-than or equal-to the corresponding entry in the second then we can say the first vector is less-than or equal-to the second vector.

Linear programming can be applied to various fields of study. It is used in business and economics, but can also be utilized for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.

Read more about Linear ProgrammingHistory, Uses, Standard Form, Augmented Form (slack Form), Duality, Covering-packing Dualities, Complementary Slackness, Open Problems and Recent Work, Integer Unknowns, Integral Linear Programs, Solvers and Scripting (programming) Languages

Other articles related to "linear programming, linear, programming":

Linear Programming Relaxation
... In mathematics, the linear programming relaxation of a 0-1 integer program is the problem that arises by replacing the constraint that each variable must be 0 or 1 by a weaker constraint, that ... constraint of the form of the original integer program, one instead uses a pair of linear constraints The resulting relaxation is a linear program, hence the name ... relaxation technique transforms an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming) the solution to ...
Linear Programming - Solvers and Scripting (programming) Languages
... LGPL an incremental constraint solving toolkit that efficiently solves systems of linear equalities and inequalities ... glpk GPL GNU Linear Programming Kit, a free LP/MILP solver ... a library for incrementally solving systems of linear equations with various goal functions CLP CPL an LP solver from COIN-OR R-Project GPL a programming language and software environment for statistical ...
... SYMPHONY is a program for solving a class of mathematical problems called integer programming (IP) problems and its variants ... A linear programming problem is an optimization (mathematics) problem in which we want to maximize or minimize a linear objective function over a set of ... A Pure Integer Programming problem is a Linear Programming problem in which all the variables are allowed to assume only integer values ...
Least Absolute Deviations - Solving Methods - Solving Using Linear Programming
... The problem can be solved using any linear programming technique on the following problem specification ... does not contain the absolute value operator, it is in a format that can be solved with any linear programming package ...
Change-making Problem - Methods of Solving - Linear Programming
... Integer Linear Programming is often a quick way to solve this kind of problem, but the time it will take to resolve the problem is not certain, and may be slow in some cases ...

Famous quotes containing the word programming:

    If there is a price to pay for the privilege of spending the early years of child rearing in the driver’s seat, it is our reluctance, our inability, to tolerate being demoted to the backseat. Spurred by our success in programming our children during the preschool years, we may find it difficult to forgo in later states the level of control that once afforded us so much satisfaction.
    Melinda M. Marshall (20th century)