2 A linear programming problem is $$\begin{array} { l l } \text { Maximise } & P = 4 x - y - 2 z
\text { subject to } & x + 5 y + 3 z \leqslant 60
& 2 x - 5 y \leqslant 80
& 2 y + z \leqslant 10
& x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$

1. Use the simplex algorithm to solve the problem. In the case when \(z = 0\) the feasible region can be represented graphically.
   \includegraphics[max width=\textwidth, alt={}, center]{9fe422a0-c498-4ad5-bdfc-f70482960d39-2_636_1619_1564_230} The vertices of the feasible region are \(( 0,0 ) , ( 40,0 ) , ( 46.67,2.67 ) , ( 35,5 )\) and \(( 0,5 )\), where non-integer values are given to 2 decimal places. The linear programming problem is given the additional constraint that \(x\) and \(y\) are integers.
2. Use branch-and-bound, branching on \(x\) first, to show that the optimum solution with this additional constraint is \(x = 45 , y = 2\). 350 people are at a TV game show. 21 of the 50 are there to take part in the game show and the others are friends who are in the audience, 22 are women and 20 are from London, 2 are women from London who are there to take part in the game show and 15 are men who are not from London and are friends who are in the audience.
3. Deduce how many of the 50 people are in two of the categories 'there to take part in the game show', 'is a woman' and 'is from London', but are not in all three categories. The 21 people who are there to take part in the game show are moved to the stage where they are seated in two rows of seats with 20 seats in each row. Some of the seats are empty.
4. Show how the pigeonhole principle can be used to show that there must be at least one pair of these 21 people with no empty chair between them. The 21 people are split into three sets of 7 . In each round of the game show, three of the people are chosen. The three people must all be from the same set of 7 but once two people have played in the same round they cannot play together in another round. For example, if A plays with B and C in round 1 then A cannot play with B or with C in any other round.
5. By first considering how many different rounds can be formed using the first set of seven people, deduce how many rounds there can be altogether.