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.
linear programming [′lin·ē·ər ′prō‚gram·iŋ]
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).
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
| (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. |
Linear Programming
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.
REFERENCE
Iudin, D. B., and E. G. Gol’shtein. Lineinoe programmirovanie. Moscow, 1969.V. G. KARMANOV
Want to thank TFD for its existence? Tell a friend about us, add a link to this page, add the site to iGoogle, or visit the webmaster's page for free fun content.
| ?Page tools | ||
|---|---|---|
|