Section A

A1  Consider the following linear programming problem.

subject to x1 + 2x2  ≤ 1                                               (2)

3x1 + x2  ≤ 2.                                              (3)

Note the absence of non-negativity constraints for the variables x1 , x2 .

(a) Using a graphical method, find the optimal solution x*  of the problem (1–3), and

the optimal value z* .                                                                                           [6]

(b) Suppose that, in the objective function z, the coefficient of x2  is allowed to vary while the coefficient of x1  is held fixed.  That is, take z = 8x1 + c2 x2 .  Perform a sensitivity analysis for the coefficient c2 ; that is, find conditions for c2 ensuring that x*  remains optimal, and explain what happens when these conditions fail.       [8]

(c) Rewrite the problem (1–3) in standard form.  (Recall:  a standard form problem includes non-negativity constraints for all control variables.)

How would you represent the feasible solution (x1 , x2 ) = (   1, 1) in your rewritten  problem?                                                                                                         [4] (d)  [Type. Word limit:  150 words.] In general, when is it more appropriate to use  the graphical solution method rather than the simplex algorithm, and when is the opposite true? Explain your answer. Answer using words only, without formulae.

[2] 

A2   (a) Emma wants to solve the following linear programming problem:

subject to 2Y1 + 3Y2 + 11Y3  ≤ 1                                   (5)

7Y1 + 5Y2 + 7Y3  ≤ 1                                     (6)

10Y1 + 3Y2 + Y3  ≤ 1                                     (7)

Y1 , Y2 , Y3    0.                                               (8)

Write down the payoff matrix of a two-person, zero-sum game, in which Emma is

Player B and Emma’s optimal strategy is related to the optimal solution of the

problem (4–8).

Explain the relationship between Emma’s optimal strategy in the game and the optimal solution of the linear programming problem, and the relationship between the value of the game and the optimal value of the linear programming problem.

(Do not attempt to solve the game or the linear programming problem.)            [4]

(b) Consider a situation where players A and B are sharing a cake, which they both like. A common method of sharing is for player A to cut the cake into two slices, and player B to pick which slice they get.  This is supposed to result in player A cutting the cake into two equal slices.

(i)  [Type. Word limit:  150 words.] In what way does this situation resemble a two-player, zero-sum game of the kind we have explored in the course?  In what way does it differ? Answer using words only, without formulae.        [3]

(ii)  [Type.  Word limit:  150 words.]  How does the idea of Nash equilibrium

help explain our intuition that player A will cut the cake into two equal slices? Answer using words only, without formulae.                                                [2]

(c) Consider the following game against nature.

Nature

A     B

Move 1    3      5

Player   Move 2    6      2

Move 3     1     8

You estimate that the probabilities of nature being in states A and B are pA  = 1/3 and pB  = 2/3, respectively.

Find the optimal strategy under:

(ii) the maximin criterion.                                                                              [4]

(d)  [Type.  Word limit:  200 words.]  Compare your answers to part (c).  When might it be appropriate to use the expected value criterion, and when the maximin criterion? Answer using words only, without formulae.                                     [3]

Section B

B1  Consider the following warehousing problem.  You manufacture a product, and must choose over a period of T = 3 months how many items to manufacture and how many

to sell.  The price of selling pt  and the cost of warehousing ct  in month t are given, in pounds (£), in the following table:

The warehouse capacity is K = 400 items, and at the beginning of month 1, it contains 200 items. You want to have an empty warehouse at the beginning of month 4.

(a) Using backward recursion and maximising profit, find the number of items to sell

and manufacture in each month t = 1, 2, 3. Report the total profit made.         [8]

(b) In the course, we introduced the idea of a shadow price associated with a resource. How would you interpret the shadow price of the warehouse capacity?  Calculate it, and then use your answer to make a specific recommendation:  under what circumstances should you increase the warehouse capacity (prior to month t = 1)?

[5]

(c) Suppose that an additional requirement is made: the warehouse must contain at least 300 items in months t = 2, 3. You still start with 200 items at the beginning of month 1, and should have an empty warehouse at the beginning of month 4.

How does this change the solution of the warehouse problem? Find the number of items to sell and manufacture in each month t = 1, 2, 3, and the total profit made.

[7]

B2  Consider a two-person, zero-sum game with the following payoff matrix:

Player B

B1         B2

Player A   A1       0        7

A2       a      —4

A3        1        2

A4       2        6

(a) Let a = 4.  Find the optimal strategies for players A and B using the graphical method.                                                                                                          [8]

(b) You should find that, when a = 4, the optimal strategy for player A only involves moves A2  and A4 .  For which values of a are these moves involved in player A’s

optimal strategy? What happens for other values of a?                                      [8]

(c)  [Type.  Word limit:  100 words.]  How should you interpret the value of the game above? Take note of the fact that the optimal strategies are not pure. Answer using words only, without formulae.                                                                 [2]

(d)  [Type.   Word  limit:   100  words.]   When discussing ‘games against nature’, we introduced the so-called ‘maximax’ strategy for player A. Would that strategy be appropriate for this game? Explain briefly. Answer using words only, without formulae.                                                                                                         [2]

B3 You work for a transport company.  You must transport cars from two manufacturing

sites, labelled 1 and 2, to three delivery points, labelled 5, 6 and 7. The transport must take place via two intermediate sites, labelled 3 and 4. The road network is represented by the following graph, where vertices (circled numbers) are the locations, and edges are roads between them.

(£60; 100)

(£50; 200)

(£100; 400)

(£60; 250)

(£80; 200)

7      £1000

In the network above, each edge has a label (£c; n), where £c is the cost of transporting one car along that edge, and n is the maximum number of cars that can be transported along that edge.

Each delivery point vertex is labelled with a reward:  you receive £3000 for each car delivered to site 5,  £2000 for each car delivered to site 6, and £1000 for each car delivered to site 7.

There are 400 cars available at each manufacturing site (1 and 2). Each delivery point (5, 6 and 7) can take at most 300 cars.  You do not have to take every car from the manufacturing points, but cars cannot be left at intermediate points.

Due to space restrictions, only 400 cars can be sent through intermediate point 4.

(a) With the goal of maximising your profit, write a linear programming problem to determine how many cars you should transport along each road.   Explain any notation you introduce and the meaning of the objective function and constraints. (Do not attempt to solve the problem.)                                                               [10]

(b) It is possible to formulate this problem as a dynamic programming problem. Ex- plain what the stages, states, and (transition and terminal) costs or rewards are. Outline briefly how you would go about solving the problem. Does dynamic pro- gramming make the problem easier to solve?  (Again, do not attempt to solve the problem.)                                                                                                                [6]