Also referred to as
linear programming. A linear program is a problem that can be expressed as follows (the
standard form:
minimize cx
subject to Ax = b
x>= 0
Where x is the
vector of variables to be solved for, A is a matrix of known
coefficients, and c and b are
vectors of known coefficients. 'cx' is called the
objective function and the equations 'Ax=b" are called the
constraints.
All of these entities have consistent dimensions, and you can add
transpose symbols to taste. The matrix A is usually not square, so you can't solve it just by
inverting A. Usually A has more
columns than rows, and Ax=b is likely to be underdetermined, leaving great
latitude in the choice of x with which to
minimize cx.
The word
programming is used here in the sense of
planning, and the relationship to
computer programming was incidental to the choice of
name, so the phrase 'LP
program' is not
redundant.
Software required to solve these problems (usually in economics or
finance) often requires
distributed computing.
It can be used for
modeling many diferse types of problems to do with
planning, routing, scheduling, assignment, and
design, and can be used by any industry from energy to
manufacturing to
finance.