QUESTION 1                     (30 marks)

Consider the transportation problem for three supply points and three demand points with trans- portation costs given by the following table:

(a) Find initial basic feasible solutions using the following methods (you should have three solutions).

Write down the cost corresponding to each basic feasible solution.

(i) Northwest corner method;

(ii)  Minimum cost method;

(iii) Vogel’s method.

(b) Explain why the solution in (a)(i) (i.e. Northwest corner method) is optimal.

(c)  Suppose that the route from supply point S3  to demand point D2  is broken.  Propose another solution that has the same cost as the optimal solution in part (b) / (a)(i).

(d)  Suppose that cost of supply one unit from supply point S2 to demand point D3 is reduced from 106 to 25 (assume that the route from supply point S3  to demand point D2  is repaired).  Determine whether the optimal solution to the modified transportation problem has changed. If the optimal solution has changed, provide the new optimal solution.

QUESTION 2                (15 marks)

You lead a team of four members (yourself included) to participate in a game. There are four tasks in the game, each represented by a shape.  The tasks are of varying difficulties and the probability that Player i completes a task j is given by the following matrix.

Each player has to complete exactly one task.  Using the Hungarian method on an appropriate cost matrix, assign each player to a task so as to maximize the probability of completing all tasks. For example, if you make the following assignment:

1 → ,  2 → ,  3 → , 4 → ,

the probability of success is (0.9)(0.2)(0.2)(0.4) = 0.0144.  It may be convenient to consider the log- probability function. Specifically, for a probability value, p, its corresponding log-probability is given by log2 p. Certain log-probabilites are given below.

QUESTION 3                   (15 marks)

Consider the following network.

21              1                                                        1              1

We apply Dijkstra’s algorithm to find the shortest distance from node 1 to node 16. After relaxing the edges from vertices 1, 2, 3, 4, 5, 6, 7, 8, 10, 13, and 14, we have that Q = {9, 11, 16} and the labels to be

w1 = 0,        w2 = 1,      w3 = 1,        w4 = 2,        w5 = 4,        w6 = 6,      w7 = 10,      w8 = 7   w9 = 11,     w10 = 8,     w11 = 22,     w12 = o,     w13 = 10,     w14 = 7,     w15 = o,     w16 = 44 .

(a) Write down the vertex, in the next iteration, to relax edges from.

(b)  Determine the shortest distance from node 1 to node 16. In your solution, write down the changes

in values of w15  and w16 .

(c)  Determine a shortest path from node 1 to node 16.

QUESTION 4                    (15 marks)

Consider the following flow network with source 1 and sink 16 and initial flow of size 11.

3/3

(a) Apply Ford-Fulkerson’s algorithm to the initial flow to find a maximum flow. (b) Find a cut with minimum capacity.

(c)  Suppose we increase the capacity of the edge 12 → 13 from 2 to 10.  Determine the size of a maximum flow in the modified network.

QUESTION 5                                                                                                               (10 marks)

Consider the following bipartite network with left nodes  1 , 5, 6, 7, 10, 11, 12, 16 and right nodes 2, 3, 4, 8, 9, 13, 14, 15. Highlighted with thick edges is a matching of size seven:

{5 → 4, 6 → 2, 7 → 3, 10 → 8, 11 → 9, 12 → 15, 16 → 14}.

Use the augmenting path algorithm to find a matching of size eight.

QUESTION 6                           (15 marks)