# 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.

#### UG examination 2000

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

An operational research worker is analysing brand switching between different airlines by frequent flyers. For the purposes of his analysis he has chosen a number of routes on which three different airlines A, B and C operate similar timetables and similar fares. He hascollected the following data.

```                  To airline
A      B    C
From airline   A 0.90 0.03 0.07
B 0.15 0.80 0.05
C 0.20 0.30 0.50 ```

For example, a frequent flyer who last travelled by airline A has a probability of 0.90 of next travelling by airline A, 0.03 of next travelling by airline B and 0.07 of next travelling by airline C. Currently airlines A, B and C have 20%, 50% and 30% of the market respectively.

• Draw the state transition diagram.
• Assuming frequent flyers make just one flight a month:
• calculate the market share for each airline in two months time
• calculate the long-run market share for each airline
• Assuming frequent flyers make two flights a month:
• calculate the market share for each airline in two months time
• calculate the long-run market share for each airline.

Question 2

A company requires a part X at the rate of 300 units per week. Part X is purchased from an external supplier who charges the company £10 for delivery of an order and £2.50 for each part purchased. The company estimate that its internal costs associated with making an order are £12.50. Assume interest rates are 5% per year and the warehousing costs associated with storage and maintenance are £0.40 per unit per year.

• Calculate the Economic Order Quantity (EOQ) and the total cost per year.

Your current supplier is prepared to give you three options for ordering:

• you can continue as at present, (ordering the EOQ); or
• you can have a 20% reduction in the unit price provided you order exactly 3000 units per order; or
• you can have a 25% reduction in the unit price, and incur no delivery charge, provided you order at least 4,000 units in each order.

Which of these options would you recommend? Give your reasons.

Question 3

. The demand for two products in each of the last four weeks is shown below.

```Week               1   2   3   4
Demand - product 1 134 212 345 467
Demand - product 2 102 132 169 204```

For product 1 calculate a forecast for week 5 using a two week moving average. For product 2 calculate a forecast for week 5 using exponential smoothing with a smoothing constant of 0.9.

These products are produced in an assembly line involving two machines (A and B). To produce one unit of product 1 requires 10 minutes processing on machine A followed by 15 minutes processing on machine B. To produce one unit of product 2 requires 3 minutes processing on machine B, then 3 minutes processing on machine A and finally a further 4 minutes processing on machine B. Currently there are 97 units of product 1 and 45 units of product 2 in stock.

Available working time on machines A and B in week 5 is forecast to be 20 and 27 hours respectively. If these machines are not sufficient to produce all of the required demand of product 1 and product 2 additional units can be bought from an external supplier at a cost of £15 for each unit of product 1 purchased and £25 for each unit of product 2 purchased.

• Formulate the problem of many units of each product the company should make in week 5 as a linear program. You should not attempt to solve this linear program.
• If, in week 5, the external supplier is not available to meet any shortfall in production then formulate and solve an appropriate linear program to decide many units of each product should be made.
• If, in processing products 1 and 2 on machines A and B, the company would prefer to deal in lots ("batches") of 100 units of each product at a time how would this affect the first formulation given above?

Question 4

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

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

The immediate precedence relationships are:

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

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

• Draw the network diagram.
• Calculate the critical activities, the overall project completion time and the float times for each activity.
• Explain clearly (with reasons) the effect upon the overall project completion time if the completion time for activity F increases by 6 weeks.
• The company involved in planning the above construction project has recently realised that the time for activity G (a fairly complicated activity) has been miscalculated. They estimate that the most likely completion time is 7 weeks, but the activity could take as long as 10 weeks. They estimate the probabilities of each of the possible completion times are as below:
• ```Completion time (weeks)   Probability
7                       0.6
8                       0.2
9                       0.1
10                       0.1```

Each week the project takes over 27 weeks means the company will incur a penalty cost of £15,000. A more precise estimate of the completion time for activity G would cost the company £10,000. If this was obtained the company could take measures now to ensure that G was completed in 7 weeks. Would you recommend that this money be spent or not and why?

Question 5

A national store chain has decided to investigate using data envelopment analysis to compare stores. Previously they have used ratio analysis to compare their stores. As a pilot study they have taken seven of their local branches. The data for these branches is shown below.

```Branch   Turnover   Floor        Personnel cost
(£'m)      space        (£'000)
(sq metres)
A        1.3        1100         150
B        3.4        2600         250
C        2.6        2510         370
D        0.9         800         240
E        2.8        1300         340
F        4.7        3900         780
G        3.4        2900         340```

For example branch A had a total turnover of £1.3 million, has a floor space of 1100 square metres and a total personnel cost of £150,000. All of these figures relate to the previous accounting year.

• Compare these branches using a ratio analysis. What do you conclude?
• Compare these branches using data envelopment analysis. What can you say with respect to these branches as a result of that analysis?
• Discuss how you might set targets for branch A so as it can improve its performance.

Question 6

In an airport terminal building there are a number of gates. These gates are used for passengers to board departing aircraft. To ease the problem of assigning gates to aircraft the terminal operator has divided time into 15 minute "slots". Once assigned to a gate each aircraft is allowed two of these slots (i.e. 30 consecutive minutes) for the purposes of boarding. Once an aircraft has finished boarding then the gate must be left free for 15 minutes before another aircraft can be assigned to it.

Currently there are 10 aircraft scheduled for boarding. Their details are as below:

```Aircraft  Earliest slot   Latest slot
1               3              4
2               2              5
3               1              1
4               4              5
5               2              3
6               1              3
7               1              2
8               3              5
9               3              4

10              3              5```

For example the earliest at which aircraft 1 needs a gate is slot 3 (i.e. 45 minutes from the current base time of zero) and the latest time at which they would like a gate is slot 4 (i.e. 60 minutes from the current base time of zero). The terminal operator commonly refers to "slot time" and hence would say that aircraft 1 has a slot time window of [3,4].

Currently there are four gates available to assign to these aircraft. In the event that no gate can be assigned to an aircraft within its slot time window then the terminal operator suffers a penalty cost of £500 for each unit of slot time that an aircraft has to wait outside its slot time window before it is assigned to a gate.

Formulate the problem of assigning gates to aircraft as a zero-one integer linear program.