# Linear programming formulation

**Keywords:** linear programming formulation, teaching notes

**Description:** 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

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:

- all variables continuous (i.e. can take fractional values)
- a single objective (minimise or maximise)
- the objective and constraints are linear i.e. any term is either a constant or a constant multiplied by an unknown.

- many practical problems can be formulated as LP's
- there exists an algorithm (called the
*simplex*algorithm) which enables us to solve LP's numerically relatively easily.

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*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:

- first mortgages must be at least 55% of all mortgages issued and at least 25% of all loans issued (in £ terms)
- second mortgages cannot exceed 25% of all loans issued (in £ terms)
- 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.

**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

x_{i} = 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 X_{1} -X_{2} (the difference of two new variables) where X_{1} >= 0 and X_{2} >= 0.

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.14x_{1} + 0.20x_{2} + 0.20x_{3} + 0.10x_{4} on total loans of (x_{1} + x_{2} + x_{3} + x_{4} ). 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.

In case you are interested the optimal solution to this LP (solved using the package as dealt with later ) is x_{1} = 208.33, x_{2} =41.67 and x_{3} =x_{4} =0. Note here this this optimal solution is not unique - other variable values, e.g. x_{1} = 62.50, x_{2} =0, x_{3} =100 and x_{4} =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:

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 (x_{1}. x_{2} and x_{3} ) can be thought of as the recipe telling us how to make up one kilogram of feed mix.

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.

In case you are interested the optimal solution to this LP (solved using the package as dealt with later ) is x_{1} = 0.3667, x_{2} =0.2667 and x_{3} =0.3667 to four decimal places.

- increasing the number of nutrients considered
- increasing the number of possible ingredients considered - more ingredients can never increase the overall cost (other things being unchanged), and may lead to a decrease in overall cost
- placing both upper and lower limits on nutrients
- dealing with cost changes
- dealing with supply difficulties
- filler cost

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.

- 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?