Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

STAT0025: Optimisation Algorithms in Operational Research

2020/21, main exam session

Section A

A1   (a) Consider a generic linear programming problem in standard form: Maximise X = cx 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 X = 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

 

 

y1         y2     y3           y4                 y5          y6

Sol

y3

y2

y6

3/11    0    1        1/11       2/11   0

7/11     1    0       6/11       1/11   0

13/11   0    0       19/11      5/11    1

14/11 18/11 79/11

g

29/11   0    0     16/11     10/11    0

92/11

(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

             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 an optimal stopping problem with the following setup:

  There are two states, 1 and 2, in each stage.

 When transitioning to the next stage, the probability of remaining in the same state is 1/5, and the probability of changing to the other state is 4/5.

  The cost of continuing is c(1) = 5 in state 1 and c(2) = 10 in state 2.

  The terminal reward is T(0) (1) = 40 in state 1 and T(0) (2) = 20 in state 2.

  The reward for stopping early is T (1) = T (2) = 12 in both states.

Find the optimal policy with two stages to go.                                                 [6]

(c) What features of dynamic programming problems make it possible to solve them without listing every path through the problem? How do we preserve this solution method in the context of Markov dynamic programming problems?                 [3]


(d) 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 X = 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 X-row entry?

In terms of your diagram of the feasible region, what is the meaning of the X-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 are running an import-export company.  Each year, you must decide whether or not to buy insurance.

Your revenue each year is £300.  Your costs, due to loss of shipments, are random. Each year, these costs are £100 with probability 5/12, £180 with probability 5/12, or £360 with probability 1/6, independently of other years.

If you buy insurance, you must pay the insurer a premium of £80.  In return, the insurer will pay the portion of your costs above the excess of £200.  For example, if

your costs are £100, your portion is £100 and the insurer’s portion is £0; if your costs are £360, your portion is £200 and the insurer’s portion is £160.

If you do not buy insurance, you must pay all your costs.

Your profit each year is your revenue, minus the premium (if you buy insurance), minus your portion of your costs due to loss of shipments.

Regard the company as having three financial positions: Good, Shaky and Bankrupt.

If the company is in a Good position, then they remain in a Good position next year if the profit is positive, and move to a Shaky position if the profit is negative.  If the company is in a Shaky position, then they move to a Good position if the profit is greater than £100, move to a Shaky position if the profit is between £0 and £100, and move to a Bankrupt position if the profit is negative. If the comany is in a Bankrupt position, then they remain in that position in all future years.

You run the company for the next N = 2 years. You get to keep the profit each year as a reward. If, after that time, the company is in a Good position, you gain an extra reward of £100; if it is in a Shaky position, you gain no extra reward; and if it is Bankrupt you

have lost your job, which we will treat as a penalty of £1000.

On the day you take over the company, it is in a Shaky position.

(a) Formulate this as a Markov dynamic programming problem with actions, with the goal of maximising your expected reward. Make clear your choice of stages, states, transition and terminal rewards and transition probabilities for each action.     [8]

(b) Solve the problem, showing all necessary steps.                                                [6]

(c) Under the optimal policy determined in (b), what is the probability that the com- pany ends up in a Good position?                                                                   [3]

(d) Suppose that, instead, you consider only the probability of bankruptcy, and want to minimise this.  How would you adapt the method of Markov dynamic programming in order to determine the optimal actions to take? You do not need to solve the problem, but you do need to describe it precisely.

(Give an answer that can be applied in general to problems of this type, rather than one specific to the revenue, costs and probabilities in this specific problem.)

[3]

B3 You play a game with a friend. You hold three cards: a red 1, a black 3, and a joker.

Your friend holds two cards: a black 1 and a red 2.

The game works as follows.  Suppose you both play number cards.  If the colours are the same, your friend pays you the sum of the two numbers. If the colours are different, you pay your friend the sum of the numbers. (For example, if you play red 1 and your friend plays black 1, then you pay £2 to your friend; if you play red 1 and your friend plays red 2, then your friend pays you £3.)

Suppose that you play the joker. Then, if your friend plays a black card, they pay you a jackpot of size J > 0; if your friend plays a red card, you pay them the jackpot of size J.

(a) Formulate this as a two-player, zero-sum game, in which you are player A, and the


(b) Let J = 3. Solve the game using the graphical method.                                    [6]

(c) Describe in detail how the solution of the game depends on the value of J, giving the optimal actions and payoff associated with every possible value of J  >  0, including non-integer values,                                                                            [8]

(d) What happens to the value of the game as J ! 1? Describe how your approach to playing the game might change as J gets large.                                            [3]