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 x1, x2,…, xn that satisfy the constraints ai1x1 + ai2x2 + … + ainxn = bi, i = 1,2,…,m
and minimize the linear form c1x1 + c2x2 + … + 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, 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.
and minimize the linear form c1x1 + c2x2 + … + 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, 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
Problem Solving , A managerial problem can be described as the gap between a given current state of affairs and a future desired state. Problem solving may then be tho… Simultaneous equations , simultaneous equations Two or more equations that can be manipulated to give common solutions. In the simultaneous equations x+10y = 25 and x+y = 7,… Solution , A solution is a homogeneous mixture of two or more substances. The term homogeneous means "the same throughout." For example, suppose that you make a… Benedicts solution , Fehling's solution (fā´lĬngz), deep-blue, alkaline solution used to test for the presence of aldehydes (e.g., formaldehyde, HCHO) or other compounds… Colligative Properties , Colligative properties are those properties of solutions that depend on the number of dissolved particles in solution, but not on the identities of t… Concentration , Concentration is the degree to which one substance is present in a mixture. The concentration of each substance in a mixture can be expressed in mass…
About this article
linear programming
All Sources -
You Might Also Like
NEARBY TERMS
linear programming