| A | B | C | D | E | F | |
| A | - | 13 | 11 | 6 | 9 | 11 |
| B | - | 8 | 14 | 3 | 4 | |
| C | - | 15 | 6 | 6 | ||
| D | - | 15 | 14 | |||
| E | - | 2 | ||||
| F | - |
By first finding a minimum spanning tree for the network of cities with F excluded, obtain a lower bound for the salesman's problem.
Now, by finding a minimum spanning tree for the whole network, obtain an itinerary (and give its distance) for the salesman which is not worse than twice the optimal solution. [You may assume that the above distances satisfy the triangular inequality.]
(b) For some optimisation problems, no algorithm which always gives a solution in reasonable time has yet been found. In these cases, heuristic algorithms are often employed.
Illustrate these statements using examples of optimisation problems which you have studied and indicating how the analysis of heuristic algorithms differs in scope from that of algorithms which give optimal solutions.
2. A project consists of activities A to J. The expected
duration E(d) and the variance of the duration Var(d) of each
activity is given in the table below. This table also gives the pre-requisites
of each of the activities.
| Activity | Pre-requisites | E(d) | Var(d) |
| A | - | 3 | 1/9 |
| B | A | 2 | 1/9 |
| C | A | 6 | 16/9 |
| D | C | 2 | 1/9 |
| E | A | 3 | 4/9 |
| F | B | 3 | 1/9 |
| G | C | 5 | 4/9 |
| H | C | 1 | 1/36 |
| I | F,H | 1.5 | 1/36 |
| J | I | 2 | 1/9 |
Draw the activity network and find the critical path and its expected duration. What is the probability that the project takes longer than 17 days to be completed? [You may use the normal distribution table which is provided.]
Outline the main assumptions used to obtain your result, and comment on their validity.
3. (a) Fitters in a certain manufacturing company collect spare
parts from the Parts Department which is staffed by one storekeeper.
Fitters arrive at an average rate of l per hour, and the
storekeeper can service an average of m fitters per hour
(l < m). [Both service times and inter-arrival times can be assumed
to be exponentially distributed.]
Management estimate that it costs the company LmC1 per hour for every fitter who is tied up at the Parts Department. They know that, by introducing new technology, they can improve the reliability of their machinery, and thereby lower the value of l. They estimate that to achieve a particular value of l, this new technology would cost them an average of LmC2/l per hour.
Find, in terms of C1, C2 and m, the value of l which management should aim for in order to minimise the total cost of fitters' idle time and the implementing of the new technology.
[You may assume that, in an M|M|1 queue, the average time a customer spends in the system is 1/(m- l).]
(b) A system of pipelines carries gas from the source S to the sink T, via intermediate points A,B,...,F. Each pipeline has a maximum capacity (in thousands of litres per minute) which cannot be exceeded. Moreover, no accumulation of gas at any of the intermediate points is allowed. At present, a total of 5000 litres per minute is carried by the system from S to T. This flow is shown in the following table. In this table, each pair of numbers in row X and column Y denotes the capacity of the pipeline leading directly from point X to point Y and the flow passing through it; a blank entry means that there is no pipeline from X to Y.
Show that this flow can be augmented to a maximum of 6000 litres per minute.
| S | A | B | C | D | E | F | T | |
| S | - | (3,3) | (2,2) | (2,0 | - | - | - | - |
| A | - | - | - | - | (5,3) | (1,0) | - | - |
| B | - | - | - | - | (1,0) | - | (1,0) | - |
| C | - | - | - | - | - | (1,1) | - | - |
| D | - | - | - | - | - | - | - | (4,3) |
| E | - | - | - | - | - | - | - | (2,2) |
| F | - | - | - | - | - | - | - | (4,1) |
It is being proposed that, in order to increase the overall capacity of the system, the capacity of one of the pipelines CE, BF or ET is to be increased. Which of these three pipelines would you propose should have its capacity increased? Give your reason.
4. (a) A manufacturing company is very concerned with the performance of one of its machines which is very susceptible to wear and tear. It is observed that if the machine is working order one day, then there is a 10% probability that it malfunctions the following day. Also, if the machine is out of order on one day, then the probability that it is malfunctioning the next day is 20%. The company estimates that it loses Lm630 every day the machine is out of order.
The company is now considering implementing a new maintenance programme which would ensure that, if the machine functions properly on one day, then there would only be a 4% probability that it would malfunction the following day.
How much per year should the company be prepared to pay for implementing the new maintenance programme? [Assume there are 365 days in a year.]