linear programming
linear programming
| Noun | 1. | linear programming - a mathematical technique used in economics; finds the maximum or minimum of linear functions in many variables subject to constraints |
linear programming
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
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
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
linear programming
(application)linear programming
A mathematical technique used to obtain an optimum solution in resource allocation problems, such as production planning.linear programming
Linear programming
Linear Programming
linear programming
a technique for utilizing limited resources to meet a desired objective, such as minimizing cost or maximizing profit, where the resource limits are expressed as constraints.For example, consider a firm making only two products, bookcases and chairs, and trying to decide how many of each to make. The company's output will be limited by the productive resources which it has available, and these are depicted graphically in Fig. 52 where output of bookcases is represented on the horizontal axis and output of chairs on the vertical axis. If the company has only 40 hours of machine time available each week, while a bookcase needs 2 hours of machine time to make and a chair 2 hours of machine time, then the maximum output with the available machine would be represented by line XY. If there were only 42 hours of labour available, and each bookcase needs 3 hours' work while each chair needs 1.5 hours'work, then the maximum output with the available labour force would be represented by line RT.
The area OXZT represents all feasible combinations of bookcases and chairs which can be produced with the limited machine-hours and man-hours available (the feasible region).
If each bookcase (b) sold makes a profit of £5, and each chair (c) £4, then in order to maximize profit the firm would seek to maximize output:
5b + 4c.
For example, in order to earn a profit of £60 the company could produce 12 bookcases or 15 chairs or some combination of the two, as represented by the broken line MP in Fig. 52. Combinations of bookcases and chairs corresponding to larger total profits can be represented by other lines such as LN, which are parallel to MP but further out from the origin O. The line LN represents the largest profit which the firm can earn with its available man-hours and machine-hours, since it is the highest broken line which just touches the resource constraints represented by the feasible region OXZT. The firm will therefore settle at point Z producing OV chairs per week and OW bookcases each week in order to maximize its profits from available resources.
Linear programming also provides information about the value of additional resources to a company. For example, it shows how much extra profit could be earned by increasing the number of machine-hours or man-hours available, and thus indicates the maximum amount which the company should pay for additional units of these resources. These maximum amounts which the company could afford to pay for additional resources without prejudicing profitability are called SHADOW PRICES of the machine-hour and man-hour resources.
Where a company produces more than two outputs, two-dimensional graphical analysis is impossible. However, an optimum combination of outputs can still be calculated using a similar reasoning process called the simplex method.
linear programming
a mathematical technique for utilizing limited resources tomeet a desired objective, such as minimizing cost or maximizing profit, where the resource limits are expressed as constraints. For xample, consider a firm making only two products: bookcases and chairs, and trying to decide how many of each to make. The company's output will be limited by the productive resources that it has available, and these are depicted graphically in Fig. 111, where quantities of bookcases are represented on the horizontal axis and quantities of chairs on the vertical axis. If the company has only 80 hours of machine time available each week, while a bookcase needs five hours of machine time to make and a chair 5 hours of machine time, then the maximum output with the available machine would be represented by line XY. Again, if there were only 84 man hours of direct labour hours available, and each bookcase needs seven hours work while each chair needs three hours work, then the maximum output with the available direct labour force would be represented by line RT.
The area OXZT represents all feasible combinations of bookcases and chairs that can be produced with the limited machine hours and man hours available (the feasible region).
If each bookcase (b) sold makes a profit of £5, and each chair (c) £4, then in order to maximize profit the firm would seek to maximize output:
For example, in order to earn a profit of £60 the company could produce 12 bookcases or 15 chairs or some combination of the two, as represented by the broken line MT in Fig. 111. Combinations of bookcases and chairs corresponding to larger total profits can be represented by other lines, such as IN, which are parallel to MT but further out from the origin, 0. The line IN represents the largest profit that the firm can earn with its available man hours and machine hours, since it is the highest broken line, which just touches the resource constraints represented by the feasible region OXZT. The firm will therefore settle at point Z, producing OV chairs per week and OW bookcases each week in order to maximize its profits from available resources.
Linear programming also provides information about the value of additional resources to a company. For example, it shows how much extra profit could be earned by increasing the number of machine hours or man hours available, and thus indicate the maximum amount that the company should pay for additional units of these resources. These maximum amounts that the company could afford to pay for additional resources without prejudicing profitability are called SHADOW PRICES of the machine-hours and man-hour resources. See PRODUCTION POSSIBILITY BOUNDARY.
linear programming
- noun
Words related to linear programming
noun a mathematical technique used in economics
Related Words
- applied math
- applied mathematics
- greyhound cramp
- greyhound exertional rhabdomyolysis
- greyhound friends of north carolina
- greyhound lines canada
- greyhound lines inc.
- greyhound package express
- greyhound pets of america
- illusory correlations
- illusory figure
- illust.
- illustrable
- illustratable
- illustrate
- illustrated
- illustrated books
- illustrated broadside
- illustrated chronicles
- illustrated codex of chronicles
- illustrated configuration audit manual
- illustrated incunabula short title catalogue
- illustrated laughing square
- illustrated list of manufactured items
- illustrated london news, ltd.
- illustratedly
- illustrated manuals for development projects