Hungarian algorithm with parameters

2 The following table shows the times taken, in minutes, by five people, Ron, Sam, Tim, Vic and Zac, to carry out the tasks \(1,2,3\) and 4 . Sam takes \(x\) minutes, where \(8 \leqslant x \leqslant 12\), to do task 2. Each of the four tasks is to be given to a different one of the five people so that the total time for the four tasks is minimised.

1. Modify the table of values by adding an extra row of non-zero values so that the Hungarian algorithm can be applied.
2. 1. Use the Hungarian algorithm, reducing columns first and then rows, to reduce the matrix to a form, in terms of \(x\), from which the optimum matching can be made.
   2. Hence find the possible way of allocating the four tasks so that the total time is minimised.
   3. Find the minimum total time.
3. After special training, Sam is able to complete task 2 in 7 minutes and is assigned to task 2. Determine the possible ways of allocating the other three tasks so that the total time is minimised.

2 The table gives the pay-off matrix for a zero-sum game between two players, A my and Bea. The values in the table show the pay-offs for A my. A my makes a random choice between strategies \(\mathbf { P }\) and \(Q\), choosing strategy \(P\) with probability \(p\) and strategy Q with probability \(1 - \mathrm { p }\).

1. Write down and simplify an expression for the expected pay-off for Amy when Bea chooses strategy X . Write down similar expressions for the cases when B ea chooses strategy Y and when she chooses strategy \(Z\).
2. Using graph paper, draw a graph to show A my's expected pay-off against p for each of Bea's choices of strategy. Using your graph, find the optimal value of pfor A my. A my and Bea play the game many times. A my chooses randomly between her strategies using the optimal value for p.
3. Showing your working, calculate A my's minimum expected pay-off per game. W hy might A my gain more points than this, on average?
4. W hat is B ea's minimum expected loss per game? How should B ea play to minimise her expected loss?

7 The table shows the times taken, in minutes, by four people, \(A , B , C\) and \(D\), to carry out the tasks \(W , X , Y\) and \(Z\). Some of the times are subject to the same delay of \(x\) minutes, where \(4 < x < 11\).

3. Five workers, A, B, C, D and E, are to be assigned to five tasks, 1, 2, 3, 4 and 5 . Each worker must be assigned to only one task and each task must be done by only one worker. The cost, in pounds, of assigning each worker to each task is shown in the table below. The cost of assigning worker D to task 4 is \(\pounds x\), where \(x > 38\) The total cost is to be minimised.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.
   (8)
2. Find the minimum total cost.
   (1) Workers A and D decide that they do not like the task they have been allocated and are allowed to swap tasks with each other. The other three allocations are unchanged. The cost now of allocating the five workers to the five tasks is now \(\pounds 5\) more than the minimum cost found in (b).
3. Calculate the value of \(x\). You must show your working.
   (2)