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.

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

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

Week 1 2 3 4 5 6 Demand 21 33 55 66 90 102

A company is considering using Markov theory to analyse consumers switching between two different brands of mouth wash (brands X and Y). An analysis of shopper behaviour data has produced the transition matrix shown below for the probability of switching each year between brands.

To brand X Y From brand X 0.9 0.1 Y 0.4 0.6

- What will be the market shares in another year if the current market shares are 60% and 40% for brands X and Y respectively?
- What will be the long-run market shares?
- Would you expect brand X ever to achieve, or come close to, its long-run market share or not? Give your reasons.

**Question 2**

A company requires a part X at the rate of 1500 units per week. Each unit costs £6 when purchased from the current supplier. The ordering cost associated with placing an order with the current supplier is £37. The interest rate is assumed to be 6% per year and the warehousing costs associated with storage and maintenance are £1 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 15% reduction in the unit price provided you order at least 10,000 units per order; or
- you can have a 30% reduction in the unit price if you order at least 40,000 units in each order.

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

**Question 3**

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

Activity Completion time (weeks) 1 3 2 1 3 1 4 7 5 2 6 3 7 1 8 2 9 4 10 4

The immediate precedence relationships are:

Activity Activity number number 1 must be finished before 2,3,5 can start 3 4 4 6 5 7,8,9 6 10 7 6

- Finished - 1,2,3,4,5,7
- In progress - 6 (2 weeks to completion); 8 (1 week to completion); 9 (3 weeks to completion)

**Question 4**

The transportation cost per unit in shipping a product from a factory (A or B) to a warehouse (W1 or W2) is shown below.

To W1 W2 From A 4 5 B 6 3

For example sending one unit from Factory A to warehouse W2 costs £5. In the forthcoming month it is estimated that production capacity at A and B is 2500 and 3000 units respectively. Demand at W1 and W2 is estimated to be 4000 and 1500 units respectively.

For a variety of logistical reasons the amount shipped from factory A to warehouse W1 must be within 500 units of the amount shipped from factory B to warehouse W1

- Formulate the problem of determine the optimal transportation schedule that minimises the total transportation cost as a linear program.
- Solve this linear program graphically.
- Comment upon the transportation schedule that you obtain.

**Question 5**

In an assembly line a company is trying to decide how to allocate tasks
to machines. There are n tasks and each task requires time t_{i}
for its completion. Tasks are completed by being allocated to machines
and there are m machines to which the tasks can be allocated.

The matrix [p_{ij}] governs whether, or not, it is possible
to allocate task i to machine j; p_{ij}=1 if this is possible,
p_{ij}=0 if this is not possible.

Precedence relationships apply to the tasks. These precedence relationships
are represented by the matrix [q_{ij}]; where q_{ij}=1
if task i must be completed, *on an earlier machine*, before task
j can start, q_{ij}=0 if there is no precedence relationship between
task i and task j. Here we mean that if a precedence relationship exists
between i and j then i must be completed on some machine k before j can
be started on any machine r (>k).

Assuming that each machine can only process one task at a time, but that machines are not limited in the total number of tasks that they can process. Formulate the problem of allocating tasks to machines so as to minimise the maximum time that any machine spends working before completing the tasks allocated to it as an integer linear program.

**Question 6**

The table below lists the edges and their associated costs in a graph containing 8 vertices (A to H). Find the shortest spanning tree of this graph by applying the Kruskal algorithm.

Edge Cost AB 10 BC 7 AG 9 FH 7 HA 4 DE 4 FD 9 GF 10 GB 3 GC 4

There are 6 branches of a local store which are being compared. Their statistics, for the total turnover and sales volume as compared with the total personnel costs are given below.

Branch Turnover Sales Personnel cost (£'000) volume (£'000) A 100 1400 15 B 300 2300 25 C 350 1950 35 D 100 750 25 E 250 1500 30 F 400 2000 50

For example branch A had a total turnover of £100,000, a sales volume of 1400 (measured in cubic metres) and a total personnel cost of £15,000.

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?