Section 5.4.2: Linear Programming Problems

Classic areas for the use of LP in process engineering are optimal blending and scheduling problems. LP is heavily used in optimising production schedules for multiproduct multifeed plants, in particular refineries.

A requirement for the use of LP is that all cost functions are linear. This is often the case for operation, where the use of a resource is typically proportional to the time of use or throughput. In designing new plant the `7/10 power law' tends to apply to capital costs and so o.f.s are nonlinear and Lp cannot be used directly.

Example 1

This is typical of `product mix' problems.

A company has two plants in which it can make a product. Plant A is an older plant on which production costs are £ 170/te and for the newer plant B they are £ 150/te.

Transport costs to the three main customers P, Q and R are significant and depend on their distances from the plants. These costs in £/te are as shown below.

Plant:        A            B
Customer: P   Q   R    P   Q   R
Cost:    25  60  75   20  50  80

Plant A has a maximum production rate of 1.7 te/day and plant B of 0.75 te/day. Customers will take as much product as is offered (all pay the same price) but their minimum requirements, listed below, must always be satisfied.

Customer:  P    Q     R
Minimum:  0.9  0.7   0.4

Find the company's optimum production and distribution schedule.

Solution

The o.f. will be the total cost to the company and must thus be minimised.

Let the production for P, Q and R at A be x1 to x3 respectively, and the same at plant B be x4 to x6. The function to be minimised is then:

min:
P = 170 (x1+x2+x3) + 150 (x4+x5+x6) + 25x1 + 60x2 + 75x3 + 20x4 + 50x5 + 80x6
;

Plant capacity imposes the following inequality constraints:

x1+x2+x3 <= 1.7 ; x4+x5+x6<= 0.75 ;

The customers' minimum requirements give:

x1 + x3 >= 0.9 ;
x2 + x4 >= 0.7 ;
x3 + x6 >= 0.4 ;

Example 2

A company finds itself with spare capacity in its batch production facility. Up to 20 hours/week reactor capacity, 10 hours/week crystalliser and 5 hours/week centrifuge are available.

Three products A, B and C might be manufactured using this capacity. the requirements in hours/batch of each are listed below.

Product:      A     B    C
Reactor      0.8   0.2  0.3
Crystalliser  0.4   0.3   -
Centrifuge   0.2    -   0.1

There is a sales limit equivalent to 20 batches/week for product C, but none for A or B.

The profit per batch is £20, £6 and £8 for A, B and C respectively. find the optimum weekly production schedule.

Solution

This is a typical batch plant equipment allocation problem.

Letting the number of batches of A, B and C be x1, x2 and x2, the o.f. is:

max: 20 x1 + 6 x2 + 8 x3;

Equipment constraints are then:

0.8 x1 + 0.2 x2 + 0.3 x3 <=20;
0.4 x1 + 0.3 x2 <= 10 ;
0.2 x1 + 0.1 x3 <= 5 ;

And C production limit gives:

x3<=20 ;

Strictly speaking the number of batches must be an integer so this really should be an MILP. However, when the numbers involved are quite large, it is usually possible to solve as an LP and round down.

Solving as an LP gives optimum as 13.75 batches of A, 15 of B and 20 of C for a profit of £525/week. Rounding A production up to 14 batches violates the first constraint, requiring 20.2 hours of reactor time per week. Rounding down to 13 batches gives a near-optimal o.f. of 510. A true MILP solution (section 5.4.3) gives a better o.f. of 524 with 14 batches of both A and B.

Note that this `solution' simply says that the equipment required will be available for the total number of hours required each week. it does not say what the operating schedule should be, nor indeed, since it will normally be necessary to have the equipment available at particular times and in a given sequence, whether a schedule is in fact feasible.

Next - Section 5.4.3: MILP Problems
Return to Example Questions
Return to Section 5 Index