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 2001

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

Brand switching between different varieties of hair shampoo is believed to be common amongst consumers. A shampoo company has decided to quantitatively investigate this and for the purposes of their analysis has collected data on brand switching between three different brands of shampoo (Brands X, Y and Z). These data are shown below.

               To brand
               X    Y    Z
From brand X   0.80 0.05 0.15
           Y   0.02 0.95 0.03
           Z   0.10 0.30 0.60

For example, a consumer who bought brand X last month has a probability of 0.80 of buying brand X the following month, 0.05 of buying brand Y the following month and 0.15 of buying brand Z the following month. Currently brands X, Y and Z have 30%, 55% and 15% of the market respectively.

 Question 2

A company regularly reviews order quantity decisions, which are typically made according to cost (Economic Order Quantity, EOQ) criteria. The time for a regular review with respect to a component P has now arrived. Previously the order quantity for P has been 500 units at each order.

Data from the last 7 weeks have been gathered in order to forecast future demand for P. This is shown below.

Week    1   2   3   4   5   6   7
Demand  245 290 456 312 380 430 515 

For example demand for component P in week 7 was 515 units. Apply exponential smoothing with a smoothing constant of 0.7 to forecast the demand for P in week 8. Apply a 4 week moving average to forecast the demand for P in week 8. Which of these two demand forecasts for P do you prefer and why?

The external supplier charges £7.45 for each unit of P supplied and the company estimate that their internal costs associated with making an order are £22.85. Assume interest rates are 5% per year and the warehousing costs associated with storage and maintenance are £1.12 per unit per year.

Question 3

In a machine shop of a production facility there are four machines (A, B, C and D). Each of these machines is used for processing work on three products (X, Y and Z). The number of minutes processing for each product on each machine is as below.

           A B C D
Product X  2 3 5 1
        Y  3 5 4 9
        Z  2 4 5 1

For example product X requires 2 minutes processing on machine A, 3 minutes processing on machine B, 5 minutes processing on machine C and 1 minute processing on machine D.

Currently there are 95 units of X, 34 units of Y and 82 units of Z in stock. Demand for these products in the next week is forecast to be 124, 350 and 90 units for products X, Y and Z respectively.

In the next week available production time on machines A, B, C and D is 20, 35, 55 and 70 hours respectively

Machines A and B are linked such that each minute of processing on machine A must be balanced by at least two minutes of processing on machine B. Technological constraints also require that the number of units of X produced and the number of units of Z produced must be approximately equal (where by approximately equal, we mean that the absolute difference between the number of units of X produced and the number of units of Z produced must be less than or equal to ten).

Formulate the problem of how much of each product to produce in the next week as an integer program with linear constraints and a linear objective function.

Question 4

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

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

The immediate precedence relationships are:

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

In addition there must be a time lag of at least 7 weeks between the end of activity B and the start of activity I. Resource restrictions also mean that once activities C and D have both finished two weeks must elapse before activity J can start.

Question 5

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

Edge Cost
 AB   14
 BD    9
 AC    7
 DE    3
 DA    2
 FC    3
 CE    5

(b) The head office of an organisation has decided to use data envelopment analysis to compare different branches. The data they have collected for these branches are shown below.

Branch   Sales   Number of   Personnel
         (£'m)   personnel   cost(£'000) 
  1       1.1       13          600
  2       4.4       23         1200
  3       3.6       19          770
  4       2.9       12          750
  5       2.4       18          740
  6       5.2       37         1345
  7       2.4       25         1100

For example branch 1 last year had sales of £1.1 million and had 13 personnel whose total cost was £600,000.

Question 6

A company manufactures three models of moveable action figures ("Mega Man", "Wizard Woman" and "Power Puppy", referred to by the initials MM, WW and PP respectively) for the toy market. These action figures are made in three different production stages. The time required for producing one unit of each figure at each stage are given below:

         Time in minutes
         MM   WW   PP
Stage 1  3.1  2.2  X
      2   X   2.3 1.2
      3  0.9  0.8  X

An X in the above table indicates that a particular figure does not require a particular production stage. Hence to produce one "Mega Man" requires 3.1 minutes at stage 1, no processing at stage 2 and 0.9 minutes processing at stage 3.

"Mega Man" figures are sold separately for £13.99 but "Wizard Woman" and "Power Puppy" are packaged and sold as one item for £15.99

Currently these action figures, aided by an extensive advertising campaign, are selling as fast as they can be made and the company is limited by the capacity of the machines available at each production stage. The available capacities (in hours) for the three stages for the next week are 410, 430 and 440 for stages 1, 2 and 3 respectively.

The company has contracted to produce at least 2000 "Mega Man" figures in the next week.