what is linear programming

(LP) 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 equations.

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Given a polyhedron and a real-valued affine function defined on this polyhedron, a linear programming method will find a point on the polyhedron where this function has the smallest (or largest) value if such point exists, by searching through the polyhedron vertices.

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

Maximize \mathbf{c}^T \mathbf{x}
Subject to A\mathbf{x} \leq \mathbf{b}.

where \mathbf{x} represents the vector of variables (to be determined), \mathbf{c} and \mathbf{b} are vectors of (known) coefficients and \mathbf{A} is a (known) matrix of coefficients. The expression to be maximized or minimized is called the objective function (\mathbf{c}^T \mathbf{x} in this case). The equations A\mathbf{x} \leq \mathbf{b} are the constraints which specify a convex polytope over which the objective function is to be optimized.