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 1999

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.

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

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.

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:

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.

                   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

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 ti 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 [pij] governs whether, or not, it is possible to allocate task i to machine j; pij=1 if this is possible, pij=0 if this is not possible.

Precedence relationships apply to the tasks. These precedence relationships are represented by the matrix [qij]; where qij=1 if task i must be completed, on an earlier machine, before task j can start, qij=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.

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?