# OR-Notes

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.

#### Network analysis - integer programming tutorial question

A project manager in a company is considering a portfolio of 10 large
project investments. These investments differ in the estimated long-run
profit (net present value) they will generate as well as in the amount
of capital required.

Let P_{j} and C_{j} denote the estimated profit and
capital required (both given in units of millions of £) for investment
opportunity j (j=1,...,10) respectively. The total amount of capital available
for these investments is Q (in units of millions of £).

Investment opportunities 3 and 4 are mutually exclusive and so are 5
and 6. Furthermore, neither 5 nor 6 can be undertaken unless either 3 or
4 is undertaken. At least two and at most four investment opportunities
have to be undertaken from the set {1,2,7,8,9,10}.

The project manager wishes to select the combination of project investments
that will maximise the total estimated long-run profit subject to the restrictions
described above.

Formulate this problem as an integer program.

The table below defines the activities within a small project.

Activity Completion time Immediate predecessor
(weeks) activities
A 2 -
B 3 -
C 4 A
D 3 B,A
E 8 D,C
F 3 C
G 2 E
H 3 F,G

- Draw the network diagram.
- Calculate the minimum overall project completion time and identify
which activities are critical.
- What is the slack (float) time associated with each of the non-critical
activities.

In the above network there are a number of options for the completion
time for activities C, D and E as shown below:

Activity Completion time Cost (£'000)
C 4 3
3 7
2 10
1 15
D 3 12
2 16
1 25
E 8 5
7 9
6 14

For example choosing a completion time for activity E of 6 weeks costs
£14,000.

- Formulate the problem of deciding the completion time for C, D and
E so as to ensure that the project is completed within 17 weeks as an integer
program.