## linear programming

**-**

## linear programming

**linear programming** 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 *x*_{1}, *x*_{2},…, *x _{n}* that satisfy the constraints

*a*

_{i}_{1}

*x*

_{1}+

*a*

_{i}_{2}

*x*

_{2}+ … +

*a*

_{in}*x*=

_{n}*b*,

_{i}*i*= 1,2,…,

*m*

and minimize the linear form

*c*

_{1}

*x*

_{1}+

*c*

_{2}

*x*

_{2}+ … +

*c*

_{n}*x*

_{n}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

*x*values.

_{i}Computationally such problems are solved by the

*simplex method*, an algorithm that terminates after a finite number of steps. It starts at a basic feasible solution and moves through the set of such solutions in such a manner that the value of the linear form is nonincreasing. Very large problems occur in practice involving sparse matrices. Recent work has shown that iterative infinite algorithms are sometimes faster, notably

*Kamarkar's method*.

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**linear programming**