linear programming

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

Linear programming

Technique for finding the maximum value of some equation, subject to stated linear constraints.
Copyright © 2012, Campbell R. Harvey. All Rights Reserved.

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.
Farlex Financial Dictionary. © 2012 Farlex, Inc. All Rights Reserved
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.

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

Collins Dictionary of Economics, 4th ed. © C. Pass, B. Lowes, L. Davies 2005
References in periodicals archive ?
This problem has been solved via the Integer Linear Programming (ILP).
The rest of the paper is organized as follows: Section II presents the optimization problem formulation and describes the proposed approach based on integer linear programming. Section III includes the application of the proposed approach on test road configurations, and the results.
(2008) describe a study for short-term scheduling of multipurpose batch plants using Mixed Integer Linear Programming. The research presented the network states and tasks (STN) to eliminate the inconvenience of precedence-based formulations which typically include a large number of batches.
Consider the following fuzzy integer linear programming (P), with trapezoidal fuzzy variables.
In this document, we proposed a mixed integer linear programming model for the optimal assignation of the work shift applied to a real case of physiotherapists in the intensive and intermediate care area in a clinic.
Integer Linear Programming. In our framework, because the objects can enter and leave the tracking area, we introduce additional nodes for the source and sink that have been defined proposed by [13].
They use a wide range of optimization problems to demonstrate how the procedures work, formulating the problems as mathematical models, including linear programming, integer linear programming, and goal-programming models.
Solver has more success solving integer linear programming problems than it has solving integer nonlinear programming problems (Fylstra & Lasdon, 1998).
Several researchers have been done in an attempt to find efficient methods of obtaining the solution of Kakuro puzzles.In (Simonis, 2008) authors use MILP (mixed integer linear programming) and a PseudoBoolean model mapped to a SAT solver for solving kakuro puzzles.
3.3 O'Hara's algorithm as an integer linear programming problem
Integer linear programming (ILP), non-linear programming (NLP) and mixed integer linear programming (MILP) are examples of mathematical programming.