# linear programming

(redirected from Integer program)
Also found in: Dictionary, Thesaurus, Encyclopedia.
Related to Integer program: Integer number, Integer linear programming

## 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.
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.

Collins Dictionary of Business, 3rd ed. © 2002, 2005 C Pass, B Lowes, A Pendleton, L Chadwick, D O’Reilly and M Afferson
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.

Collins Dictionary of Economics, 4th ed. © C. Pass, B. Lowes, L. Davies 2005
References in periodicals archive ?
The test instances and the OPL code for the integer program can be found at http://mail.ipb.ac.rs/~rakaj/home/tas.zip.
The integer program (2) has [3.sup.(m+n)] feasible points, so the cost of an exhaustive search for the optimal solution grows exponentially with m and n.
Solving the integer program for various values of X gives the information credit limits.
In line (9), the binary integer program is constructed.
The expected value problem is a MIP and is often used in practice as the related stochastic mixed integer program is in general much harder to solve, since it considers multiple scenarios (e.g., Durbach and Stewart [28] and Maggioni and Wallace [29]).
In this respect, the integer program is deficient because if it fails to find a feasible integer solution, it runs virtually forever and finally provides no useful information to the decision maker.
To solve this Knapsack problem, we use a binary integer program employing branch and bound algorithm [18].
Seker and Noyan [9] formulate the GAP as a mixed integer program with the objective of minimizing the number of conflicts and at the same time minimizing the total semideviation between idle time and buffer time:
The generalized binary integer program is formulated as follows:
We applystochastic online algorithms to solve stochastic integer programs.

Site: Follow: Share:
Open / Close