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

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

Apply a two week moving average to generate a forecast for the demand for this product in week 7.
Apply exponential smoothing with a smoothing constant of 0.3 to generate a forecast for the demand for this product in week 7.
Which of these forecasts do you prefer and why?

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

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 5 increases from 2 weeks to 6 weeks?
Explain clearly (with reasons) the effect upon the overall project completion time if the completion time for activity 9 is cut from 4weeks to 3 weeks?
Comment upon the project if, after 7 weeks, the status of the activities is as follows:

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

After planning the project a colleague has reviewed your approach and commented that he has heard that integer programming can be applied to the problem. Hence he is surprised that you have not used integer programming. How would you respond?

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?