linear programming

Home > Science and Technology > Mathematics > Mathematics

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₁, x₂,…, x_n that satisfy the constraints a_i1x₁ + a_i2x₂ + … + a_inx_n = b_i, i = 1,2,…,m

and minimize the linear form c₁x₁ + c₂x₂ + … + c_nx_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_i 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.

linear programming solution of a mathematical problem concerning maximum and minimum values of a first-degree (linear) algebraic expression, with variables subject to certain stated conditions (restraints). For example, the problem might be to find the minimum value of the expression x + y subject to the restraints x ≥0, y ≥0, 2 x + y ≥12, 5 x +8 y ≥74, and x +6 y ≥24. The solution was set forth by the Russian mathematician L. V. Kantorovich in 1939 and was developed independently by the American George B. Dantzig, whose first work on the subject appeared in 1947. A faster, but more complex technique, that is suitable for problems with hundreds or thousands of variables, was developed by Bell Laboratories mathematician Naranda Karmarkar in 1983. Linear programming is particularly important in military and industrial planning.