linear programming


Also found in: Dictionary, Thesaurus, Acronyms, Encyclopedia, Wikipedia.

Linear programming

Technique for finding the maximum value of some equation, subject to stated linear constraints.

Linear Programming

In mathematics, a process or technique for finding the maximum or minimum value of a linear function subject to certain restraints. Linear programming is important to securities analysis as it helps determine the maximum or minimum rate of return on a particular investment. While the maximum rate of return is not necessarily the expected rate of return, it may help an investor decide if a security is worth a certain level of risk.
Linear programmingclick for a larger image
Fig. 52 Linear programming. Limitations on productive resources.

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 programmingclick for a larger image
Fig. 111 Linear programming.

linear programming

a mathematical 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 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.

References in periodicals archive ?
The proposed model attain to incorporate the functional link network application in linear programming technique
Hence, we can present a determination way to get a initial feasible basis for a linear programming model: First, doing a finite series row elementary transformation on the augment coefficients matrix B = [[A|b].sub.mx(n+1)] till to perform it as its simplest form under the condition of keeping the resource vector b always positive, a r x r initial feasible basis is obtained (r [less than or equal to] m); and whereafter, turn into the simplex method in the simplex table by arrange the simplest form matrix into initial simplex table.
Analyses of modeling regional production and national distribution of plywood were studied for business activity programming and compared to linear programming. A theory of model behavior was also presented.
For a more complete description, see any linear programming textbook such as Luenberger (1973) or Bertsimas and Tsitsiklis (1997).
Further significant progress in linear programming was made in the beginning of the 1990s, when new randomized algorithms for linear programming were obtained independently by Kalai [1992], and by Matousek et al.
"Linear Programming Applications on Microcomputers," Journal of the Operational Research Society, v.
In that discussion it was claimed that the SCMLP model could best achieve the desired objectives of the Smith model and applications of linear programming procedures to the portfolio selection process without the necessity of having the individual investor place absolute weights on his investment preferences.
Performance of the Forecasting Models According to the Correctness Criterion (Japanese Yen) Rank Forecasting method Single or % Correct composite (RSOM) 1.5 Constrained Linear Combination Composite 80.6 1.5 Constrained Multiple Objective Composite 80.6 Linear Programming 3.
Still, we can make some speedup estimates on the basis of CPlex promotional literature [3]: their code runs only 10 to 14 times faster on a Cray Y-MP than on a Sun-4, for five linear programming problems (viz.
Instead, linear programming techniques are used to construct a production possibilities set and to measure productive efficiency relative to the production frontier associated with the set.
Two appendices explore the use of time series analysis and linear programming to make volume projections.
The next chapter contains linear programming model of the paddy-farming sector.

Full browser ?