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:

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

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":

COIN-OR - Projects - SYMPHONY
... 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 linear constraints ... A Pure Integer Programming problem is a Linear Programming problem in which all the variables are allowed to assume only integer values ... A Mixed Integer Programming (MIP) problem is similar to a Pure IP Problem, but only some of the variables are constrained to be integers ...
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 ...
Linear Programming - Solvers and Scripting (programming) Languages
... 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 ... Qoca GPL 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 ...
Least Absolute Deviations - Solving Methods - Solving Using Linear Programming
... The problem can be solved using any linear programming technique on the following problem specification ... is in a format that can be solved with any linear programming package ...
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 each variable belong ... 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 ... an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming) the solution to the relaxed linear program can be used ...

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)