linear programming(redirected from 0-1 integer programming)
Also found in: Dictionary, Thesaurus, Financial.
a mathematical discipline dealing with the theory and methods of solution of extremum problems for linear functions on sets defined by systems of linear inequalities and equalities. Linear programming is a branch of mathematical programming.
A typical problem of linear programming is to maximize the linear function
subject to the constraints
(3) xj ≥ 0, j = 1, 2,..., n
where cj, aij, and bi are given variables.
Linear-programming problems are mathematical models of numerous problems that have technical and economic applications. Let us consider as an example the following problem of planning the operation of an enterprise. The production of uniform products requires the expenditure of various production factors, such as raw materials, manpower, the stock of machine tools, fuel, and transport. Usually there exist several developed technological modes of production with varying expenditures of the production factors per unit time for the production of the articles. The number of production factors used and the number of articles made depend on the amount of time the enterprise will spend on a particular technological mode of production.
The problem is then raised of efficiently distributing the working time of the enterprise among the various technological modes of production such that the maximum number of articles will be produced under the given limitations upon the cost of each production factor. We state the problem in the following manner. Suppose there exist n technological modes of producing an article and m production factors. Let us introduce the following notation. Let cj be the number of articles produced per unit time through the jth technological mode of production, aij be the expenditure of the ith production factor per unit time during the jth technological mode of production, bi be the available resources of the ith production factor, and xj be the planned working time according to the jth technological mode of production. The value
denotes the total expenditure of the ith production factor under the plan x(i) = (x1(i), x2(i) ..., xn(i)). Since the resources are limited by the values bi, the conditions (2) and (3) naturally arise. The problem is posed of finding a distribution of time (optimal plan) x* = (x*1, x*2, ..., x*n) of work for each technological mode of production such that the total volume of production
is at a maximum, that is, the problem (1)–(3). The transportation problem is another example of applied linear-programming problems.
The choice of the term “linear programming” is not very apt. Linear programming is concerned with solving problems of compiling an optimal program (plan) of activities. It may therefore be considered as a mathematical method of operations research.
The function (1) in linear programming is generally called the object-function, or efficiency criterion; the vector x = (x1, x2,..., xn) is the plan; the vector x* = (x*1, x*2,..., x*n) is the optimal plan; and the set defined by the conditions (2)–(3) is the feasible set, or set of plans. The simplex method is one of the basic methods of solving linear-programming problems. Geometrically it consists in the following. The feasible set (2)-(3) is a convex polyhedral set (if bounded, a multidimensional convex polyhedron). If a linear-programming problem has a solution, there exists a vertex x* of the polyhedral set that is an optimal plan. The simplex method consists in obtaining an arrangement of the vertices in which the value of the object-function increases as we go from one vertex to the next. To each vertex there corresponds a system of equations that can be selected in a special fashion from the system of inequalities (2)-(3), and therefore the computational procedure of the simplex method consists in successively solving systems of linear algebraic equations. The simplicity of the algorithm makes this method suitable for computers.
REFERENCEIudin, D. B., and E. G. Gol’shtein. Lineinoe programmirovanie. Moscow, 1969.
V. G. KARMANOV
linear programming[′lin·ē·ər ′prō‚gram·iŋ]
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).
An important extension in practice is to integer programming, where some of the xj's are required to take on integral values. The most common case in practice is where the integer xj 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 xj'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 aij'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