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, 2x+y≥12, 5x+8y≥74, and x+6y≥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.

Mathematical modeling technique useful for guiding quantitative decisions in business, industrial engineering, and to a lesser extent the social and physical sciences. Solving a linear programming problem can be reduced to finding the optimum value (see optimization) of a linear equation (called an objective function), subject to a set of constraints expressed as inequalities. The number of inequalities and variables depends on the complexity of the problem, whose solution is found by solving the system of inequalities like a system of equations. The extensive use of linear programming during World War II to deal with transportation, scheduling and allocations of resources under constraints like cost and priority gave the subject an impetus that carried it into the postwar era. The number of equations and variables needed to model real-life situations accurately is large, and the solution process can be time-consuming even with computers. Seealso simplex method.

Learn more about linear programming with a free trial on Britannica.com.