Edexcel D2 (Decision Mathematics 2) 2006 June

1. (a) State Bellman's principle of optimality.
   (b) Explain what is meant by a minimax route.
   (c) Describe a practical problem that would require a minimax route as its solution.
   (Total 4 marks)
2. Three workers, \(P , Q\) and \(R\), are to be assigned to three tasks, 1,2 and 3 . Each worker is to be assigned to one task and each task must be assigned to one worker. The cost, in hundreds of pounds, of using each worker for each task is given in the table below. The cost is to be minimised.

Formulate the above situation as a linear programming problem, defining the decision variables and making the objective and constraints clear.
(Total 7 marks)

3. A college wants to offer five full-day activities with a different activity each day from Monday to Friday. The sports hall will only be used for these activities. Each evening the caretaker will prepare the hall by putting away the equipment from the previous activity and setting up the hall for the activity next day. On Friday evening he will put away the equipment used that day and set up the hall for the following Monday. The 5 activities offered are Badminton (B), Cricket nets (C), Dancing (D), Football coaching (F) and Tennis (T). Each will be on the same day from week to week. The college decides to offer the activities in the order that minimises the total time the caretaker has to spend preparing the hall each week. The hall is initially set up for Badminton on Monday.
The table below shows the time, in minutes, it will take the caretaker to put away the equipment from one activity and set up the hall for the next.

1. Explain why this problem is equivalent to the travelling salesman problem. A possible ordering of activities is

   Monday	Tuesday	Wednesday	Thursday	Friday
   \(B\)	\(C\)	\(D\)	\(F\)	\(T\)

2. Find the total time taken by the caretaker each week using this ordering.
3. Starting with Badminton on Monday, use a suitable algorithm to find an ordering that reduces the total time spent each week to less than 7 hours.
4. By deleting \(B\), use a suitable algorithm to find a lower bound for the time taken each week. Make your method clear.

4. During the school holidays four building tasks, rebuilding a wall ( \(W\) ), repairing the roof ( \(R\) ), repainting the hall \(( H )\) and relaying the playground \(( P )\), need to be carried out at a Junior School. Four builders, \(A , B , C\) and \(D\) will be hired for these tasks. Each builder must be assigned to one task. Builder \(B\) is not able to rebuild the wall and therefore cannot be assigned to this task. The cost, in thousands of pounds, of using each builder for each task is given in the table below.

1. Use the Hungarian algorithm, reducing rows first, to obtain an allocation that minimises the total cost. State the allocation and its total cost. You must make your method clear and show the table after each stage.
2. State, with a reason, whether this allocation is unique.

5. Victor owns some kiosks selling ice cream, hot dogs and soft drinks. The network below shows the choices of action and the profits, in thousands of pounds, they generate over the next four years. The negative numbers indicate losses due to the purchases of new kiosks.
\includegraphics[max width=\textwidth, alt={}, center]{83ddfbb1-d035-4fae-b39d-a643c877cfed-3_887_1342_340_365} Use a suitable algorithm to determine the sequence of actions so that the profit over the four years is maximised and state this maximum profit.
(Total 12 marks)

6. (a) Explain briefly the circumstances under which a degenerate feasible solution may occur to a transportation problem.
(b) Explain why a dummy location may be needed when solving a transportation problem. The table below shows the cost of transporting one unit of stock from each of three supply points \(A , B\) and \(C\) to each of two demand points 1 and 2 . It also shows the stock held at each supply point and the stock required at each demand point. (c) Complete the table below to show a possible initial feasible solution generated by the north-west corner method. (d) Use the stepping-stone method to obtain an optimal solution and state its cost. You should make your method clear by stating shadow costs, improvement indices, stepping-stone route, and the entering and exiting squares at each stage.

7. A two person zero-sum game is represented by the following pay-off matrix for player \(A\).

1. Formulate the game as a linear programming problem for player \(A\), writing the constraints as equalities and clearly defining your variables.
2. Explain why it is necessary to use the simplex algorithm to solve this game theory problem.
3. Write down an initial simplex tableau making your variables clear.
4. Perform two complete iterations of the simplex algorithm, indicating your pivots and stating the row operations that you use.
   (8)
   (Total 16 marks)

8. The tableau below is the initial tableau for a maximising linear programming problem.

1. Write down the four equations represented in the initial tableau above.
   (4)
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use.
3. State the values of the objective function and each variable.

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Operations

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Operations

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Operations

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Operations

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Operations

9. The figure above shows a capacitated, directed network. The capacity of each arc is shown on each arc. The numbers in circles represent an initial flow from \(S\) to \(T\). Two cuts \(C _ { 1 }\) and \(C _ { 2 }\) are shown on the figure.

1. Write down the capacity of each of the two cuts and the value of the initial flow.
   (3)
2. Complete the initialisation of the labelling procedure on the diagram below by entering values along arcs \(A C , C D , D E\) and \(D T\).
   \includegraphics[max width=\textwidth, alt={}, center]{83ddfbb1-d035-4fae-b39d-a643c877cfed-7_2372_1131_121_475}
3. Hence use the labelling procedure to find a maximal flow through the network. You must list each flow-augmenting path you use, together with its flow.
4. Show your maximal flow pattern on the diagram below.
   \includegraphics[max width=\textwidth, alt={}, center]{83ddfbb1-d035-4fae-b39d-a643c877cfed-8_757_1472_210_294}
5. Prove that your flow is maximal.
   (Total 14 marks)