Section A

A1   (a) Consider a generic linear programming problem in standard form: Maximise z = cT x subject to Ax ≤ b, x  0.

Regard this as the primal problem. Write down its dual, and convert it to standard

form. Maintain matrix notation throughout.                                                      [3]

(b) Is the following statement true or false? Justify your answer carefully. ‘The ranges of validity of the shadow prices in the dual problem are related to the tolerance intervals of the objective function coefficients in the primal problem.’               [3]

(c) Consider the following linear programming problem:

Maximise z = 2x1 + 6x2  x3

2x1  x2 + 3x3  ≤ 2                                                  (2)

x1 + 6x2 + x3  ≤ 4                                                  (3)

x1 , x2 , x3    0.                                                 (4)

Regard this as the primal problem.  The final tableau in the simplex algorithm applied to the dual problem is

(Note the objective function in the tableau is    g .) Using only this tableau, what can you deduce about the primal problem? Justify your answer.                      [4]

(d) Consider the following game against nature.

Nature

N1      N2      N3

Player   A1       10    10    10

A2        9     20    30

A3      20     5     20

Your beliefs about the state of nature are that N1  will occur with probability 1/4, N2  with probability 3/8 and N3  with probability 3/8.

Find the optimal action on the basis of the expected value criterion, and its ex- pected payoff.                                                                                                  [4]

(e) The expected value criterion does not correspond to a Nash equilibrium in the

game against nature. Comment on the implications of this.                               [3]

(f) In the course, we saw the expected value-standard deviation (EVSD) criterion.

Comment on the effect of using the EVSD criterion as a way to distinguish between

actions A1  and A2  in (d), and its suitability in this example.  (You might like to

set K = 2 as the parameter to the EVSD criterion.)                                          [3]

A2   (a) In the following network, vertices are labelled with letters, and edges are labelled with numbers. The label on each edge represents the costs of travelling along that edge.  For the two vertices in stage 3, there are terminal costs associated with arriving at that vertex.

Stage 1

9

B                              E

3

H

6

4

A              5              C              3              F

2

I

4

5

10

D                              G

Terminal

costs

7

3

Find the path from stage 0 to stage 3 which attains the minimium cost across all possible paths, taking into account the terminal costs.  (If you decide to annotate the network, you must define your annotations.)                                              [6]

(b) Consider the warehousing problem covered in the lecture course, retaining all the same notation, but with the following change: you are such a large manufacturer that your manufacturing and selling activities impact the selling price per unit of your product.

If rt  is the proportion of your warehouse capacity that you sell in month t, the table below shows the manufacturing cost (ct ) and selling price (pt ) per unit in month t:

The warehouse capacity is K = 1000, and the initial stock in your warehouse in month 1 is I1  = 300.  Consider the problem over a period of T = 4 months, and assume that you want to have an empty warehouse at the end of the period (i.e., I5  = 0.) Your goal is to maximise your profit over the period.

Describe how you would use dynamic programming to solve this problem, and write down explicitly a mathematical programming problem for finding the optimal number of units to manufacture and sell in month 3, as a function of the number of units in the warehouse at the start of the month (I3 ). Without attempting

to further solve the problem, explain whether it is possible to solve it using

the simplex algorithm.                                                                                     [9] (c) Solve the two-player, zero-sum game with the following payoff matrix:

Player B

B1      B2      B3      B4

Player A   A1        2      0     — 1    — 1

A2        5     —3    — 1    — 2

A3        4      1      1      2

A4      — 1     3      0      5

[5]

Section B

B1  Consider the following linear programming problem:

Maximise z = x1 + 4x2

x1 + 2x2  ≤ 8                                                  (6)

2x1 — x2  ≤ 1                                                  (7)

x1 , x2    0.                                                 (8)

(a) Draw the feasible region. Label all the basic solutions, and indicate, for each one, which are the basic variables. (Use our standard notation for slack variables. You do not have to find the values of the basic variables.)                                       [4]

(b) Solve the problem using the simplex algorithm.                                                [8]

(c) Using your solutions to the previous parts, answer the following questions about the simplex algorithm:

(i) When entering a variable, why do we choose the column with the most negative z-row entry?

In terms of your diagram of the feasible region, what is the meaning of the z-row entries?                                                                                           [4]

(ii) When exiting a variable, why do we choose the row with the smallest non- negative a-ratio?

In terms of your diagram of the feasible region, what is the geometric meaning

of the a-ratio (when this is non-negative)?                                                   [4]

Note: If you were unable to answer part (a) or (b), you may answer part (c) by referring to any example from the course.

B2 You work for an internet service provider (ISP). Your customers’ internet connections are routed through three computer clusters. You plan to upgrade these clusters in order to support more connections per day, and therefore improve your customers’ experience.

Each cluster has some possible upgrade plans associated with it, each of which has some expense (in thousands of pounds sterling) and some reward (in millions of supported additional connections per day). These are expressed in the following table:

An entry‘—’means that this plan cannot be used with this cluster.

The total budget available for the upgrade project is £25 000.

(a) With the goal of maximising the total number of supported additional connec- tions per day, formulate this upgrade project as a dynamic programming problem. You must describe the stages, states, transitions and rewards.  You must explain any notation you introduce, and if you use any diagrams, you must explain their meaning.                                                                                                         [6]

(b) Using forward recursion, solve the dynamic programming problem.  Describe ex- plicitly the optimal upgrade plan (or optimal upgrade plans, if there are more than one), the total expense and how many additional connections per day this plan will support.                                                                                                    [8]

(c) Give an informal explanation of why, in general, problems of this type cannot be solved by choosing upgrades with the largest reward until you run out of money.

[3]

(d) Another team at the ISP says that, in the next year, they will not need to support any more than 4 million additional connections per day.   Describe, briefly but precisely, how you would modify your solution procedure in order to avoid spending money on upgrades that will not be necessary in the next year. Explain how your modified procedure works.  (You do not need to solve the problem in this part, just explain the procedure for doing so.)                                          [3]