6 Jack is making pizzas for a party.
He can make three types of pizza:
| Suitable for vegans | Suitable for vegetarians | Suitable for meat eaters |
| Type X | | | ✓ |
| Type Y | | ✓ | ✓ |
| Type Z | ✓ | ✓ | ✓ |
- There is enough dough to make 30 pizzas.
- Type Z pizzas use vegan cheese. Jack only has enough vegan cheese to make 2 type Z pizzas.
- At least half the pizzas made must be suitable for vegetarians.
- Jack has enough onions to make 50 type X pizzas or 20 type Y pizzas or 20 type Z pizzas or some mixture of the three types.
Suppose that Jack makes \(x\) type X pizzas, \(y\) type Y pizzas and \(z\) type Z pizzas.
- Formulate the constraints above in terms of the non-negative, integer valued variables \(x , y\) and \(z\), together with non-negative slack variables \(s , t , u\) and \(v\).
Jack wants to find out the maximum total number of pizzas that he can make.
- Set up an initial simplex tableau for Jack's problem.
- Carry out one iteration of the simplex algorithm, choosing your pivot so that \(x\) becomes a basic variable.
When Jack carries out the simplex algorithm his final tableau is:
| \(P\) | \(x\) | \(y\) | \(z\) | \(s\) | \(t\) | \(u\) | \(v\) | RHS |
| 1 | 0 | 0 | 0 | 0 | 0 | \(\frac { 3 } { 7 }\) | \(\frac { 2 } { 7 }\) | \(28 \frac { 4 } { 7 }\) |
| 0 | 0 | 0 | 0 | 1 | 0 | \(- \frac { 3 } { 7 }\) | \(- \frac { 2 } { 7 }\) | \(1 \frac { 3 } { 7 }\) |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 2 |
| 0 | 1 | 0 | 0 | 0 | 0 | \(\frac { 5 } { 7 }\) | \(\frac { 1 } { 7 }\) | \(14 \frac { 2 } { 7 }\) |
| 0 | 0 | 1 | 1 | 0 | 0 | \(- \frac { 2 } { 7 }\) | \(\frac { 1 } { 7 }\) | \(14 \frac { 2 } { 7 }\) |
- Use this final tableau to deduce how many pizzas of each type Jack should make.
Jack knows that some of the guests are vegans. He decides to make 2 pizzas of type \(Z\).
- Plot the feasible region for \(x\) and \(y\).
- Complete the branch-and-bound formulation in the Printed Answer Booklet to find the number of pizzas of each type that Jack should make.
You should branch on \(x\) first.
\section*{END OF QUESTION PAPER}