Description:
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. It's 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 point exists.
Linear programs are problems that can be expressed in canonical form:
where x represents the vector of
variables (to be determined), c and b are vectors of (known) coefficients and A is a (known) matrix of coefficients. The
expression to be maximized or minimized is called the objective function (c^{T}x in this case). The
equations Ax ≤ b 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 every entry in one is less-than or equal-to the corresponding
entry in the other. Otherwise, they are incomparable.)
Linear
programming can be applied to various fields of study. It is used most
extensively 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.
Standard form
Standard form is the usual and most intuitive
form of describing a linear programming problem. It consists of the following
four parts:
• A linear function to be maximized
e.g.
• Problem
constraints of
the following form
e.g.
• Non-negative
variables
e.g.
• Non-negative
right hand side constants
The problem is usually expressed in matrix form, and then becomes:
Other forms, such as minimization problems, problems with
constraints on alternative forms, as well as problems involving negative variables can always be rewritten into an
equivalent problem in standard form.
(Our solved example in mathguru.com uses
this concept)
http://en.wikipedia.org/wiki/Linear_programming
The
above explanation is copied from Wikipedia, the free encyclopedia and is
remixed as allowed under the Creative Commons Attribution- ShareAlike 3.0 Unported
License.