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 ?
Solving optimization problem by convex optimization is just like to solve linear programming problem by least square method [11, 12].
This indicates the inability of simple linear programming model to estimate the sustainable cropping pattern for the study area.
We have here developed a linear programming method for the performance prioritization of decision alternatives involving incomplete weight information.
2009) shows application of linear programming model to household data in Vihiga district, and determines optimal household consumption bundle of locally available food commodities and the associated expenditures meeting dietary needs.
Khachiyan, A polynomial algorithm for linear programming, Soviet Math.
The problem can be expressed as the following linear programming problem:
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].
Analyses of modeling regional production and national distribution of plywood were studied for business activity programming and compared to linear programming.
Lotteries have the further advantage that they are nonnegative by definition so the choice variables in the program are nonnegative, a requirement of the standard form of linear programming.
so the analyst must view the output of linear programming critically to ensure that the result makes sense.
A major task in the development of realistic linear programming models is determining and stating the exact numerical value of the objective function coefficients.
The constrained multiple objective linear programming model permits the articulation of multiple objectives and generates on ordered list of optimum solutions.

Full browser ?