OR-Notes

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.

A full list of the topics available in OR-Notes can be found here.

Integer programming tutorial question

Recall the production planning problem dealt with before under linear programming. To remind you of it we repeat the problem and its formulation below.

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

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

Production planning solution

Variables

Let:

x_i be the number of units of variant i (i=1,2,3,4) made per year
T_ass be the number of minutes used in assembly per year
T_pol be the number of minutes used in polishing per year
T_pac be the number of minutes used in packing per year

where x_i >= 0 i=1,2,3,4 and T_ass, T_pol, T_pac >= 0

Constraints

(a) operation time definition

T_ass = 2x₁ + 4x₂ + 3x₃ + 7x₄ (assembly)
T_pol = 3x₁ + 2x₂ + 3x₃ + 4x₄ (polish)
T_pac = 2x₁ + 3x₂ + 2x₃ + 5x₄ (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:

T_ass <= 100000 (assembly)
T_pol <= 50000 (polish)
T_pac <= 60000 (pack)

Objective

Presumably to maximise profit - hence we have

maximise 1.5x₁ + 2.5x₂ + 3.0x₃ + 4.5x₄

which gives us the complete formulation of the problem.

Suppose now we have the additional constraints:

• that either the company makes none of variant 2 or it makes at least 18,000 units; and
• that if any of variant 4 are made a fixed cost of £250 will be incurred.

Formulate the problem (including these additional constraints) as an IP.

Solve this IP using the package.