OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.
A full list of the topics available in OR-Notes can be found here.
The conditions for a mathematical model to be a linear program (LP) are:
LP's are important - this is because:
We will return later to the simplex algorithm for solving LP's but for the moment we will concentrate upon formulating LP's.
Some of the major application areas to which LP can be applied are:
We consider below some specific examples of the types of problem that can be formulated as LP's. Note here that the key to formulating LP's is practice. However a useful hint is that common objectives for LP's are minimise cost/maximise profit.
A bank makes four kinds of loans to its personal customers and these loans yield the following annual interest rates to the bank:
The bank has a maximum foreseeable lending capability of £250 million and is further constrained by the policies:
Formulate the bank's loan problem as an LP so as to maximise interest income whilst satisfying the policy limitations.
Note here that these policy conditions, whilst potentially limiting the profit that the bank can make, also limit its exposure to risk in a particular area. It is a fundamental principle of risk reduction that risk is reduced by spreading money (appropriately) across different areas.
We follow the approach:
Note here that as in all formulation exercises we are translating a verbal description of the problem into an equivalent mathematical description.
A useful tip when formulating LP's is to express the variables, constraints and objective in words before attempting to express them in mathematics.
Essentially we are interested in the amount (in £) the bank has loaned to customers in each of the four different areas (not in the actual number of such loans). Hence let
xi = amount loaned in area i in £m (where i=1 corresponds to first mortgages, i=2 to second mortgages etc)
and note that xi >= 0 (i=1,2,3,4).
Note here that it is conventional in LP's to have all variables >= 0. Any variable (X, say) which can be positive or negative can be written as X1-X2 (the difference of two new variables) where X1 >= 0 and X2 >= 0.
(a) limit on amount lent
x1 + x2 + x3 + x4 <= 250
Note here the use of <= rather than = (following the general rule, given a choice between an equality and an inequality choose the inequality (as this allows for more flexibility in optimising the objective function)).
(b) policy condition 1
x1 >= 0.55(x1 + x2)
i.e. first mortgages >= 0.55(total mortgage lending) and also
x1 >= 0.25(x1 + x2 + x3 + x4)
i.e. first mortgages >= 0.25(total loans)
(c) policy condition 2
x2 <= 0.25(x1 + x2 + x3 + x4)
(d) policy condition 3 - we know that the total annual interest is 0.14x1 + 0.20x2 + 0.20x3 + 0.10x4 on total loans of (x1 + x2 + x3 + x4). Hence the constraint relating to policy condition (3) is
0.14x1 + 0.20x2 + 0.20x3 + 0.10x4 <= 0.15(x1 + x2 + x3 + x4)
Note: whilst many of the constraints given above could be simplified by collecting together terms this is not strictly necessary until we come to solve the problem numerically and does tend to obscure the meaning of the constraints.
To maximise interest income (which is given above) i.e.
maximise 0.14x1 + 0.20x2 + 0.20x3 + 0.10x4
In case you are interested the optimal solution to this LP (solved using the package as dealt with later) is x1= 208.33, x2=41.67 and x3=x4=0. Note here this this optimal solution is not unique - other variable values, e.g. x1= 62.50, x2=0, x3=100 and x4=87.50 also satisfy all the constraints and have exactly the same (maximum) solution value of 37.5
Consider the example of a manufacturer of animal feed who is producing feed mix for dairy cattle. In our simple example the feed mix contains two active ingredients and a filler to provide bulk. One kg of feed mix must contain a minimum quantity of each of four nutrients as below:
Nutrient A B C D gram 90 50 20 2
The ingredients have the following nutrient values and cost
A B C D Cost/kg Ingredient 1 (gram/kg) 100 80 40 10 40 Ingredient 2 (gram/kg) 200 150 20 - 60
What should be the amounts of active ingredients and filler in one kg of feed mix?
In order to solve this problem it is best to think in terms of one kilogram of feed mix. That kilogram is made up of three parts - ingredient 1, ingredient 2 and filler so let:
x1 = amount (kg) of ingredient 1 in one kg of feed mix
x2 = amount (kg) of ingredient 2 in one kg of feed mix
x3 = amount (kg) of filler in one kg of feed mix
where x1 >= 0, x2 >= 0 and x3 >=
0.
Essentially these variables (x1, x2 and x3) can be thought of as the recipe telling us how to make up one kilogram of feed mix.
100x1 + 200x2 >= 90 (nutrient A)
80x1 + 150x2 >= 50 (nutrient B)
40x1 + 20x2 >= 20 (nutrient C)
10x1 >= 2 (nutrient D)
Note the use of an inequality rather than an equality in these constraints, where we assume that the nutrient levels we want are lower limits on the amount of nutrient in one kg of feed mix.
x1 + x2 + x3 = 1
Presumably to minimise cost, i.e.
minimise 40x1 + 60x2
which gives us our complete LP model for the blending problem.
In case you are interested the optimal solution to this LP (solved using the package as dealt with later) is x1= 0.3667, x2=0.2667 and x3=0.3667 to four decimal places.
Obvious extensions/uses for this LP model include:
Blending problems of this type were, in fact, some of the earliest applications of LP (for human nutrition during rationing) and are still widely used in the production of animal feedstuffs.
A company manufactures four variants of the same product and in the final part of the manufacturing process there are assembly, polishing and packing operations. For each variant the time required for these operations is shown below (in minutes) as is the profit per unit sold.
Assembly Polish Pack Profit (£)
Variant 1 2 3 2 1.50
2 4 2 3 2.50
3 3 3 2 3.00
4 7 4 5 4.50
Let:
xi be the number of units of variant i (i=1,2,3,4) made per
year
Tass be the number of minutes used in assembly per year
Tpol be the number of minutes used in polishing per year
Tpac be the number of minutes used in packing per year
where xi >= 0 i=1,2,3,4 and Tass, Tpol, Tpac >= 0
(a) operation time definition
Tass = 2x1 + 4x2 + 3x3 +
7x4 (assembly)
Tpol = 3x1 + 2x2 + 3x3 + 4x4
(polish)
Tpac = 2x1 + 3x2 + 2x3 + 5x4
(pack)
(b) operation time limits
The operation time limits depend upon the situation being considered. In the first situation, where the maximum time that can be spent on each operation is specified, we simply have:
Tass <= 100000 (assembly)
Tpol <= 50000 (polish)
Tpac <= 60000 (pack)
In the second situation, where the only limitation is on the total time spent on all operations, we simply have:
Tass + Tpol + Tpac <= 210000 (total time)
Presumably to maximise profit - hence we have
maximise 1.5x1 + 2.5x2 + 3.0x3 + 4.5x4
which gives us the complete formulation of the problem.
We shall solve this particular problem later in the course.
Under normal working conditions a factory produces up to 100 units of a certain product in each of four consecutive time periods at costs which vary from period to period as shown in the table below.
Additional units can be produced by overtime working. The maximum quantity and costs are shown in the table below, together with the forecast demands for the product in each of the four time periods.
Time Demand Normal Overtime Overtime
Period (units) Production Production Production
Costs Capacity Cost
(£K/unit) (units) (£K/unit)
1 130 6 60 8
2 80 4 65 6
3 125 8 70 10
4 195 9 60 11
It is possible to hold up to 70 units of product in store from one period to the next at a cost of £1.5K per unit per period. (This figure of £1.5K per unit per period is known as a stock-holding cost and represents the fact that we are incurring costs associated with the storage of stock).
It is required to determine the production and storage schedule which will meet the stated demands over the four time periods at minimum cost given that at the start of period 1 we have 15 units in stock. Formulate this problem as an LP.
The decisions that need to be made relate to the amount to produce in normal/overtime working each period. Hence let:
xt = number of units produced by normal working in period
t (t=1,2,3,4), where xt >= 0
yt = number of units produced by overtime working in period
t (t=1,2,3,4) where yt >= 0
In fact, for this problem, we also need to decide how much stock we carry over from one period to the next so let:
It = number of units in stock at the end of period t (t=0,1,2,3,4)
xt <= 100 t=1,2,3,4
y1 <= 60
y2 <= 65
y3 <= 70
y4 <= 60
It <= 70 t=1,2,3,4
closing stock = opening stock + production - demand
then assuming
we have that
I1 = I0 + (x1 + y1) - 130
I2 = I1 + (x2 + y2) - 80
I3 = I2 + (x3 + y3) - 125
I4 = I3 + (x4 + y4) - 195
where I0 = 15
Note here that inventory continuity equations of the type shown above are common in production planning problems involving more than one time period. Essentially the inventory variables (It) and the inventory continuity equations link together the time periods being considered and represent a physical accounting for stock.
I0 + (x1 + y1) >= 130
I1 + (x2 + y2) >= 80
I2 + (x3 + y3) >= 125
I3 + (x4 + y4) >= 195
However these equations can be viewed in another way. Considering the inventory continuity equations we have that the above equations which ensure that demand is always met can be rewritten as:
I1 >= 0
I2 >= 0
I3 >= 0
I4 >= 0
To minimise cost - which consists of the cost of ordinary working plus the cost of overtime working plus the cost of carrying stock over (1.5K per unit). Hence the objective is:
minimise
(6x1 + 4x2 + 8x3 + 9x4) + (8y1 + 6y2 + 10y3 + 11y4) + (1.5I0 + 1.5I1 + 1.5I2 + 1.5I3 + 1.5I4)
Note here that we have assumed that if we get an answer involving fractional variable values this is acceptable (since the number of units required each period is reasonably large this should not cause too many problems).
In case you are interested the optimal solution to this LP (solved using the package as dealt with later) is x1=x2=x3=x4=100; y1=15, y2=50, y3=0 and y4=50; I0=15, I1=0, I2=70, I3=45 and I4=0 with the minimal objective function value being 3865
Note:
Period 1 2 3 4 5 6 7 8 P=plan
P P P P D=do (follow) the plan in a period
D P P P P
D P P P P
D P P P P
This rolling horizon approach would be preferable to carrying out the plan for 4 time periods and then producing a new plan for the next 4 time periods, such as shown below.
Period 1 2 3 4 5 6 7 8 P=plan
P P P P D=do (follow) the plan in a period
D D D D
P P P P
D D D D
Some more LP formulation examples can be found here.