Linear Programming Definition/Meaning:
A technique in optimization, pioneered by George B. Dantzig,
that is widely used in economic, military, and business-management decisions. It
deals with the problem of finding nonnegative values of the variables x1,
. . xn that satisfy the constraints
ai1x1 + ai2x2 +.
. . . . . +ainxn = bi,
i = 1,2,...m
and minimize the linear form
c1x1 + c1x2 + .. . . . + cnxn
Maximizing problems and problems with inequality constraints or unrestricted
variables can be converted to this form. An optimum solution (if any exist) is
known to be a basic feasible solution, which is one that satisfies the
constraints and has at most m positive xi values.
Computationally such problems
are solved by the simplex method, which starts at a basic feasible solution and
searches the set of such solutions in such a manner that the value of the linear
form is nonincreasing. An important recent advance is the algorithm developed by N.Z. Shor
and L. G. Khachian. In theory this is significantly faster than the simplex
method but it is as yet uncertain whether this can be realized in practice.