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.

UG examination 2002

Answer FOUR questions.
All questions carry equal marks.
If more than four questions are answered only the first four answered will be marked.
Marks will be deducted in this examination if there is insufficient written explanation.

Question 1

In an attempt to investigate brand switching between different brands of washing powder a research company has been hired to survey shoppers to discover their brand switching behaviour.

A survey of a number of shoppers, in relation to the three main brands, X, Y and Z, on the market has revealed the following:

Current purchase    Previous purchase   Number
       X                    X           200 
       Y                    Y           150 
       Z                    Z           100 
       Y                    X            50 
       Z                    X            25 
       X                    Y            80 
       Z                    Y            45 
       X                    Z           130 
       Y                    Z            20

For example of the shoppers surveyed there were 25 whose current purchase is brand Z but whose previous purchase was brand X.

 Question 2

The Home Secretary has ordered a review into the efficiency of a number of police stations in the same borough of London. As part of this review the following data has been collected over the course of four working weeks:

Station   Number  Arrests  Arrests 
                  Day      Night 
P1        9.9     5.5      10.7 
P2        9.4     4.4      15.4 
P3        8.3     6.6      17.8 
P4        7.3     2.4      10.9 
P5        5.2     3.8      13.5 
P6        3.5     3.1       2.2

For station P1 for example the average number of police officers on duty and on the streets at any one time was 9.9. Over the same period there were on average 5.5 arrests made during the day and 10.7 arrests made during the night.

Stations P1 to P5 deal with areas that are predominately urban in nature with a high proportion of shops, pubs, clubs and takeaways. Station P6 deals with an area that is mainly residential in nature.

Question 3

A company requires a supplier to deliver to it 1000 units per week of a component that is needed for production. Each component that the company purchases from its supplier costs £11. The company estimate that their internal costs associated with making with an order to the supplier are £23.50 and that the storage costs associated with keeping one component in stock before it is used in production are £0.45 per month. Because the company has been experiencing cash flow difficulties it has been having to borrow money from its bank at 10% over the current monetary base rate of 3% per year.

Question 4

The demand for a product X in each of the last five weeks is shown below.

Week    1  2  3  4  5 
Demand 14 18 23 28 35 

This product is produced using three machines, A, B and C. To produce one unit of the product requires 7 minutes processing on machine A followed by 12 minutes processing on machine C and then a further 5 minutes processing on machine B. The cost of running these machines is estimated to be £10 per working hour in labour cost and £6 per working hour in general running costs. Currently (at the end of week 5) there are 7 units of the product in stock.

Available working time on machines A, B and C in week 6 is forecast to be 1, 2 and 3 hours respectively. If this available working time is not sufficient to met the required production of the product then additional hours are available via overtime working at a cost of £15 per labour hour. Union requirements mean that the number of overtime hours devoted to producing product X on each of these machines must be "equalised" so that the biggest difference in overtime hours is no more than four hours.

What is the decision problem here? Formulate this decision problem as a linear program.

Question 5

The following table defines the various activities in a small project:

            Activity        Completion time (weeks)
                A                       4
                B                       2
                C                       1
                D                       5
                E                       2
                F                       3
                G                       2
                H                       5
                I                       2
                J                       4
                K                       6

The immediate precedence relationships are:

                  Activity                               Activity
                     A       must be finished before         F       can start
                     D                                       J
                     C                                       D,F
                     B                                       E,K
                     G                                       H,I,C
                     I                                       J,K
                     H                                       B

In addition there must be a time lag of at least 2 weeks between the end of activity G and the start of activity A.

Question 6

In a study concerned with the supply of certain customers a company is trying to decide where to locate supply facilities. There are n customers and each customer i requires a delivery quantity qi to be supplied from one, and only one, supply facility. There are m possible locations for supply facilities and each possible location (facility) j has a fixed cost fj associated with deciding to make use of a facility at location j. Delivery costs dij give the cost of supplying all of the demand of customer i from a facility located at j.

Location j has an upper limit on the demand that can be supplied from that location of Qj. Company policy is that the number of facilities that they operate must lie between p1 and p2.

Formulate, as a zero-one linear integer program, the problem of deciding which locations to use for facilities.

What assumptions have you made in producing your formulation?

How would your formulation change if it was now possible to supply customers from more than one facility?