6. The tableau below is the initial tableau for a maximising linear programming problem.
| Basic variable | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value |
| \(r\) | 7 | 10 | 10 | 1 | 0 | 0 | 3600 |
| \(s\) | 6 | 9 | 12 | 0 | 1 | 0 | 3600 |
| \(t\) | 2 | 3 | 4 | 0 | 0 | 1 | 2400 |
| \(P\) | - 35 | - 55 | - 60 | 0 | 0 | 0 | 0 |
- Write down the four equations represented in the initial tableau above.
- 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.
(9) - State the values of the objective function and each variable.
(3)
\includegraphics[max width=\textwidth, alt={}, center]{2ae673c0-206a-468b-ae6f-ac55e5970f7b-7_867_1533_322_311}
Figure 5 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 Figure 5. - Write down the capacity of each of the two cuts and the value of the initial flow.
- Complete the initialisation of the labelling procedure on Diagram 1 by entering values along \(\operatorname { arcs } A C , C D , D E\) and \(D T\).
- 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.
- Show your maximal flow pattern on Diagram 2.
- Prove that your flow is maximal.