Section A

A1   (a) Consider the following linear programming problem (LPP).

Maximise z = —x1 + 5x2

subject to x1 + 2x2    2

x1 + 2x2  ≤ 8

x1  ≤ 4

—x1 + 4x2  ≤ 10

x1 , x2    0.

Solve this LPP using the graphical solution method  (not the graphical naïve method.) Make sure you justify your answer.                                                   [5]

(b) Find tolerance intervals for the coefficients of the objective function z = c1 x1 +c2 x2 for the LPP in part (a). That is, determine the range of c1  such that the optimal solution remains the same (keeping c2   = 5 fixed), and then do the same for c2

(keeping c1  = — 1 fixed).                                                                                      [7]

(c) Consider a game against nature with the following payoff matrix, where you are player A.

 Nature

 N1     N2     N3  

Player A   A1        0    11     7

A2        9     2     6

A3        3     3     2

You believe that the states of nature N1 , N2  and N3  occur with probabilities 1/4,

(i) Find the optimal strategy under the expected value criterion.                    [2]

(ii) Compute the regret matrix, and find the optimal strategy under the minimax criterion and the expected value criterion applied to regret.                       [6]

A2   (a) Consider the warehousing problem described in this course, maintaining the same notation, over a period of T = 3 months. The manufacturing cost and sell prices per item each month are given in this table:

Your warehouse has capacity K = 500 and at the start of month 1 it contains I1  = 400 items. You aim to have an empty warehouse at the end of the 3 month period.

Find the optimal number of items to manufacture and to distribute to retailers each month. Summarise your solution in a table, and give the total profit attained

over the period.                                                                                             [10] (b) Consider a zero sum game between two players with the following payoff matrix:

 Player B

  B1          B2      B3

Player A   A1    —6   b — 1      7

A2        4      — 1   — 2

A3         b         a      5

Under what conditions (on a and b) is (A3 , B2 ) a saddle point?                        [5]

(c) Suppose that a = 6 and b  8. Show that the value of the game lies in the interval [5, 7].                                                                                                               [5]

Section B

B1  Transport for London (TfL) is deciding how many buses to run on the following network,

in which vertices represent bus stops in central London, and edges represent streets between them. TfL wishes to decide how many buses to run down each street per day.

5

6

7

Key

Buses start at stops 1 and 2 (bus garages), and end at stops 9 and 10 (bus depots). Stops 3, 4, 7 and 8 are normal bus stops, and every bus which enters them must also leave them. Stop 5 is also a bus garage: every bus which enters stop 5 must also leave it, but additional buses can also start there.  Stop 6 is also a bus depot:  buses which enter stop 6 may pass through, or they may end their route there.

Attached to each street are a capacity and a demand. For instance, the street between stops 1 and 3 has capacity 200 and demand 120. The capacity is the maximum number of buses which can pass along that street per day.

If a street has x buses running down it per day and demand d, define its unmet demand penalty to be £500(d — x). Let the unmet demand penalty of the network be the sum of the unmet demand penalties of each street.

The cost of running a bus (not per street, but per bus) is £250 for the day.

TfL seeks to minimise the unmet demand penalty of the network plus the cost of running the buses.

(a) Write down a linear programming problem (LPP) for TfL, using the control vari- ables xij   = the number of buses to run from stop i to stop j, for suitable combi- nations of i and j . Explain the meaning of your constraints and objective function.

Do not attempt to solve the linear programming problem.                 [10]

(b) Give two ways in which TfL could use a sensitivity analysis of your LPP in order to improve their understanding of the situation. (Maximum: 3 sentences.)       [3]

(c) What happens in your LPP if the number of buses on a street exceeds the demand? It may be better to try to match the demand as closely as possible, instead of merely exceeding it.  How could you change your objective function to meet this goal? Can the problem still be solved using linear programming?                     [3]

(d) Suppose that stop 6 is changed so that it is both a bus garage and a bus depot; that is, buses can pass through it, end their route there or start their route there. How could you change your LPP to represent this, while ensuring that it can still be solved using linear programming?                                                                [4]

Table 1: Failure probabilities according to resource unit allocation.

B2  The Marine Exploration Institute wants to reach the bottom of the Galathea Depth, a deep oceanic trench. To do this, they will finance three independent research teams, each pursuing a different approach.

The Institute has two resource units (consisting of money, equipment, etc.), and they must decide how to distribute these between the teams.  The units are discrete:  they cannot be divided up.

The probability of failure of each team after one year, given a number of resource units allocated to that team, is given in Table 1.

(a) The Institute must decide on the allocation of all units simultaneously, at the start of the programme.

Describe the problem of allocating units to teams as a dynamic programming prob- lem (not a Markov dynamic programming problem), with the goal of minimising the probability that, after one year, all teams have failed. You must describe explic- itly the stages, states and transitions, and you must define any notation you use, even if it comes from the course.  Write down a (forward or backward) recursion equation explicitly.

(Hint: The recursion equation will be different from the usual one! The following observation may help.  If Team 1 has probability of failure 0.3 and Team 2 has probability of failure 0.2, the probability that both teams fail is 0.3  0.2 = 0.06.) [10]

(b) Solve the dynamic programming problem in part (a).                                     [5]

(c) This part can be attempted independently of parts (a) and (b).

Now consider a different setting. The Institute will first decide on funding for Team 1, and let them work for one year. If they fail, the Institute will decide on funding for Team 2, and let them work for one year.  If they also fail, the Institute will

do the same for Team 3.  The Institute has two resource units available over the

lifetime of the programme, and must decide how to allocate them to teams.

In this setting, describe the problem of allocating units to teams as a Markov dynamic programming problem with costs, with the goal of minimising the prob- ability of failure after three years. Your four stages 0, 1, 2 and 3 should represent the situation after zero, one, two and three years.  You should set the terminal costs to be 1 for failure states and 0 for success states, and set transition costs to be zero; this will ensure that the value function of any state is a failure probability.

In your answer, describe the states and actions in each stage, and give explicitly the transition probability matrices for the transitions from stage 0 to stage 1 and stage 1 to stage 2.

Do not attempt to solve the Markov dynamic programming problem.

(Hint: in your states, you will need to keep track both of success and failure, and of the budget consumption to date.)                                                                [8]

(d) Explain briefly why you cannot use a standard (i.e., non-Markov) dynamic pro- gramming problem to model the situation in part (c).  (Maximum:  2 sentences.)

[2]