OR-Notes: J E Beasley
OR-Notes: J E Beasley
OR-Notes: J E Beasley
J E Beasley
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.
You will recall from the Two Mines example that the conditions for a mathematical model to be
a linear program (LP) were:
We will return later to the simplex algorithm for solving LP's but for the moment we will
concentrate upon formulating LP's.
Blending
Production planning
Oil refinery management
Distribution
Financial and economic planning
Manpower planning
Blast furnace burdening
Farm planning
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.
Financial planning
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:
1. first mortgages must be at least 55% of all mortgages issued and at least 25% of all loans
issued (in £ terms)
2. second mortgages cannot exceed 25% of all loans issued (in £ terms)
3. to avoid public displeasure and the introduction of a new windfall tax the average interest
rate on all loans must not exceed 15%.
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 same approach as for the Two Mines example - namely
variables
constraints
objective.
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.
Variables
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)
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.
Constraints
x1 + x2 + x3 + x4 <= 250
Note here the use of <= rather than = (following the general rule we put forward in the Two
Mines problem, namely given a choice between an equality and an inequality choose the
inequality (as this allows for more flexibility in optimising the objective function)).
(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
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.
Objective
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
Blending problem
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
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?
Variables
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:
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.
Constraints
nutrient constraints
Note the use of an inequality rather than an equality in these constraints, following the rule we
put forward in the Two Mines example, where we assume that the nutrient levels we want are
lower limits on the amount of nutrient in one kg of feed mix.
balancing constraint (an implicit constraint due to the definition of the variables)
x1 + x2 + x3 = 1
Objective
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.
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.
Given the current state of the labour force the company estimate that, each year, they
have 100000 minutes of assembly time, 50000 minutes of polishing time and 60000
minutes of packing time available. How many of each variant should the company make
per year and what is the associated profit?
Suppose now that the company is free to decide how much time to devote to each of the
three operations (assembly, polishing and packing) within the total allowable time of
210000 (= 100000 + 50000 + 60000) minutes. How many of each variant should the
company make per year and what is the associated profit?
Variables
Let:
Constraints
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:
Objective
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.
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.
Factory planning solution
Variables
The decisions that need to be made relate to the amount to produce in normal/overtime working
each period. Hence let:
In fact, for this problem, we also need to decide how much stock we carry over from one period
to the next so let:
Constraints
production limits
y1 <= 60
y2 <= 65
y3 <= 70
y4 <= 60
It <= 70 t=1,2,3,4
then assuming
we have that
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.
demand must always be met - i.e. no "stock-outs". This is equivalent to saying that the
opening stock in period t plus the production in period t must be greater than (or equal to)
the demand in period t, i.e.
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
Objective
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:
As discussed above assuming It >= 0 t=1,2,3,4 means "no stock-outs" i.e. we need a
production plan in which sufficient is produced to ensure that demand is always satisfied.
Allowing It (t=1,2,3,4) to be unrestricted (positive or negative) means that we may end up
with a production plan in which demand is unsatisfied in period t (It < 0). This unsatisfied
demand will be carried forward to the next period (when it will be satisfied if production
is sufficient, carried forward again otherwise).
If It is allowed to be negative then we need to amend the objective to ensure that we
correctly account for stock-holding costs (and possibly to account for stock-out costs).
If we get a physical loss of stock over time (e.g. due to damage, pilferage, etc) then this
can be easily accounted for. For example if we lose (on average) 2% of stock each period
then multiply the right-hand side of the inventory continuity equation by 0.98. If this is
done then we often include a term in the objective function to account financially for the
loss of stock.
If production is not immediately available to meet customer demand then the appropriate
time delay can be easily incorporated into the inventory continuity equation. For example
a 2 period time delay for the problem dealt with above means replace (xt + yt) in the
inventory continuity equation for It by (xt-2 + yt-2).
In practice we would probably deal with the situation described above on a "rolling
horizon" basis in that we would get an initial production plan based on current data and
then, after one time period (say), we would update our LP and resolve to get a revised
production plan. In other words even though we plan for a specific time horizon, here 4
months, we would only even implement the plan for the first month, so that we are
always adjusting our 4 month plan to take account of future conditions as our view of the
future changes. We illustrate this 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 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