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.

linear programming

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. See also simplex method.

A mathematical technique used to obtain an optimum solution in resource allocation problems, such as production planning.

Linear programming

An area of mathematics concerned with the minimization (or maximization) of a linear function of several variables subject to linear equations and inequalities. The subject in its present form was created in 1947, when G.B. Dantzig defined the general model and proposed the first, and still the most widely used, method for its solution: the simplex method.

Although the linearity assumptions are restrictive, many algorithms for extensions of linear programming, such as problems with nonlinear or integer restrictions, involve successively solving linear programming problems. With a result in 1979 giving a polynomially bounded ellipsoid method, an alternative to the simplex method, linear programming became the focus of work by computer scientists, and nonlinear methods have been refocused on solving the linear programming problem. Work by N. K. Karmarkar announced in 1984 attracted much attention because of claims of vastly improved performance of a new interior method. The relative merits of Kamarkar's method and the simplex method remain to be determined, but there seems to be a place for both methods. Karmarkar's work stimulated considerable activity in linear programming methodology. See Nonlinear programming, Optimization

The linear programming problems is to minimize linear objective function (1) subject to restrictions (2).

(1)

(2)

The variables x₁, …, x_n are required to take on real values, and the coefficients a_ij, c_j, and b_i are real constants. The objective could be to maximize rather than minimize, and among constraints (2) the equations could be replaced by inequalities of the form less-than-or-equal-to or greater-than-or-equal-to. The set of x_j's satisfying constraints (2) form a convex polyhedron, and the optimum value of the objective function will always be assumed at a vertex of the polyhedron unless the objective function is unbounded. The simplex method works by moving from vertex to vertex until the vertex yielding the optimum value of the objective function is reached, while interior methods stay inside the polyhedron.

An important extension in practice is to integer programming, where some of the x_j's are required to take on integral values. The most common case in practice is where the integer x_j must be 0 or 1, representing decision choices such as to whether to switch from production of one product to another or whether to expand a warehouse to allow for larger throughput. Whereas linear programming solution times tend to be less than an hour, adding the constraint that some or all of the x_j's must be integral may cause the running time to be very long.

Early work on computer programs was done in the 1950s. Commercial computer codes implementing the simplex method have been used in industry since the mid-1960s. Efficient methods for handling the structures encountered have been developed. In particular, the matrices tend to be very sparse, that is, most (usually over 99%) of the a_ij's are zeroes. In the 1980s, intense development in software was begun because of changed hardware and new algorithmic developments.

Following the early work on codes, the petroleum industry quickly became the major user of linear programming, and still is an important user, especially for blending models in petroleum refining. Commercial codes are used in industry and government for a variety of applications involving planning, scheduling, distribution, manufacturing, and so forth. In universities, linear programming is taught in most business schools, industrial engineering departments, and operations research departments, as well as some mathematics departments. The model is general enough to be useful in the physical and social sciences. The improved computational efficiency achieved in the 1980s has gone hand-in-hand with expanded applications, particularly in manufacturing, transportation, and finance. See Operations research

(application)

linear programming - A procedure for finding the maximum or minimum of a linear function where the arguments are subject to linear constraints. The simplex method is one well known algorithm.