A pictorial representation of a simple linear program with 2 variables & six inequalities. The set of feasible solutions is depicted in light red & forms a 2-dimensional polytope. The linear cost function is represented by the red line & the arrow: The red line is a level set of the cost function, & the arrow indicates the direction in which we are optimizing.
Linear programming 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(LP) is a specific case of mathematical programming (mathematical optimization).
More formally, linear programming(LP) is a technique for the optimization of a linear objective function, subject to linear equality & 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 objectives 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 point exists.
Linear programs are problems; that can be expressed in canonical form:
Maximize c x
Subject to Ax < b
and x > 0
where x represents the vector of variables (to be determined), c & b are vectors of (known) coefficients, A is a (known) matrix of coefficients, & (.)T is the matrix transpose. The expression to be maximized /or/ minimized is called the objective function (cTx in this case). The inequalities Ax ≤ b are the constraints, which specify a convex polytope over which the objective function is to be optimized. In this context, 2 vectors are comparable when they have the same dimensions. If every entry in the first is < 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(LP) can be applied to various fields of study. It is used in business & economics, but can also be utilized for some engineering problems. Industries that use linear programming models include telecommunications, energy, transportation, & manufacturing. It has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment, & design.