Formulation from word problem

8 [Figure 2, printed on a separate sheet, is provided for use in this question.]
A bakery makes two types of pizza, large and medium.
Every day the bakery must make at least 40 of each type.
Every day the bakery must make at least 120 in total but not more than 400 pizzas in total.
Each large pizza takes 4 minutes to make, and each medium pizza takes 2 minutes to make. There are four workers available, each for five hours a day, to make the pizzas. The bakery makes a profit of \(\pounds 3\) on each large pizza sold and \(\pounds 1\) on each medium pizza sold.
Each day, the bakery makes and sells \(x\) large pizzas and \(y\) medium pizzas.
The bakery wishes to maximise its profit, \(\pounds P\).

1. Show that one of the constraints leads to the inequality $$2 x + y \leqslant 600$$
2. Formulate this situation as a linear programming problem.
3. On Figure 2, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and an objective line.
4. Use your diagram to find the maximum daily profit.
5. The bakery introduces a new pricing structure in which the profit is \(\pounds 2\) on each large pizza sold and \(\pounds 2\) on each medium pizza sold.
   1. Find the new maximum daily profit for the bakery.
   2. Write down the number of different combinations that would give the new maximum daily profit.

9 A factory can make three different kinds of balloon pack: gold, silver and bronze. Each pack contains three different types of balloon: \(A , B\) and \(C\). Each gold pack has 2 type \(A\) balloons, 3 type \(B\) balloons and 6 type \(C\) balloons.
Each silver pack has 3 type \(A\) balloons, 4 type \(B\) balloons and 2 type \(C\) balloons.
Each bronze pack has 5 type \(A\) balloons, 3 type \(B\) balloons and 2 type \(C\) balloons.
Every hour, the maximum number of each type of balloon available is 400 type \(A\), 400 type \(B\) and 400 type \(C\). Every hour, the factory must pack at least 1000 balloons.
Every hour, the factory must pack more type \(A\) balloons than type \(B\) balloons.
Every hour, the factory must ensure that no more than \(40 \%\) of the total balloons packed are type \(C\) balloons. Every hour, the factory makes \(x\) gold, \(y\) silver and \(z\) bronze packs.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), simplifying your answers.
(8 marks)

6 [Figure 1, printed on the insert, is provided for use in this question.]
A factory makes two types of lock, standard and large, on a particular day.
On that day:
the maximum number of standard locks that the factory can make is 100 ;
the maximum number of large locks that the factory can make is 80 ;
the factory must make at least 60 locks in total;
the factory must make more large locks than standard locks.
Each standard lock requires 2 screws and each large lock requires 8 screws, and on that day the factory must use at least 320 screws. On that day, the factory makes \(x\) standard locks and \(y\) large locks.
Each standard lock costs \(\pounds 1.50\) to make and each large lock costs \(\pounds 3\) to make.
The manager of the factory wishes to minimise the cost of making the locks.

1. Formulate the manager's situation as a linear programming problem.
2. On Figure 1, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of the objective line.
3. Find the values of \(x\) and \(y\) that correspond to the minimum cost. Hence find this minimum cost.

5 Findlay is trying to get into his local swimming team. The coach will watch him swim and will then make his decision. Findlay must swim at least two lengths using each stroke and must swim at least 8 lengths in total, taking at most 10 minutes. Findlay needs to put together a routine that includes breaststroke, backstroke and butterfly. The table shows how Findlay expects to perform with each stroke. Findlay needs to work out how many lengths to swim using each stroke to maximise his expected total number of style marks.

1. Identify appropriate variables for Findlay's problem and write down the objective function, to be maximised, in terms of these variables.
2. Formulate a constraint for the total number of lengths swum, a constraint for the time spent swimming and constraints on the number of lengths swum using each stroke. Findlay decides that he will swim two lengths using butterfly. This reduces his problem to the following LP formulation: $$\begin{array} { l c } \text { maximise } & P = 2 x + y , \\ \text { subject to } & x + y \geqslant 6 , \\ & 4 x + y \leqslant 16 , \\ & x \geqslant 2 , y \geqslant 2 , \end{array}$$ with \(x\) and \(y\) both integers.
3. Use a graphical method to identify the feasible region for this problem. Write down the coordinates of the vertices of the feasible region and hence find the integer values of \(x\) and \(y\) that maximise \(P\).
4. Interpret your solution for Findlay.

3 Maggie is a personal trainer. She has twelve clients who want to lose weight. She decides to put some of her clients on weight loss programme \(X\), some on programme \(Y\) and the rest on programme \(Z\). Each programme involves a strict diet; in addition programmes \(X\) and \(Y\) involve regular exercise at Maggie's home gym. The programmes each last for one month. In addition to the diet, clients on programme \(X\) spend 30 minutes each day on the spin cycle, 10 minutes each day on the rower and 20 minutes each day on free weights. At the end of one month they can each expect to have lost 9 kg more than a client on just the diet. In addition to the diet, clients on programme \(Y\) spend 10 minutes each day on the spin cycle and 30 minutes each day on free weights; they do not use the rower. At the end of one month they can each expect to have lost 6 kg more than a client on just the diet. Because of other clients who use Maggie's home gym, the spin cycle is available for the weight loss clients for 180 minutes each day, the rower for 40 minutes each day and the free weights for 300 minutes each day. Only one client can use each piece of apparatus at any one time. Maggie wants to decide how many clients to put on each programme to maximise the total expected weight loss at the end of the month. She models the objective as follows. $$\text { Maximise } P = 9 x + 6 y$$

1. What do the variables \(x\) and \(y\) represent?
2. Write down and simplify the constraints on the values of \(x\) and \(y\) from the availability of each of the pieces of apparatus.
3. What other constraints and restrictions apply to the values of \(x\) and \(y\) ?
4. Use a graphical method to represent the feasible region for Maggie's problem. You should use graph paper and choose scales so that the feasible region can be clearly seen. Hence determine how many clients should be put on each programme.

5 Roland Neede, the baker, is making cupcakes. He makes three sizes of cupcake: miniature, small and standard. Miniature cupcakes are sold in boxes of 24 and each cupcake uses 3 units of topping and 2 decorations. Small cupcakes are sold in boxes of 20 and each cupcake uses 5 units of topping and 3 decorations. Standard cupcakes are sold in boxes of 12 and each cupcake uses 7 units of topping and 4 decorations. Roland has no restriction on the amount of cake mix that he uses but he only has 5000 units of topping and 3000 decorations available. Cupcakes are only sold in complete boxes, and Roland assumes that he can sell all the boxes of cupcakes that he makes. Irrespective of size, each box of cupcakes sold will give Roland a profit of \(\pounds 1\). Roland wants to maximise his total profit. Let \(x\) denote the number of boxes of miniature cupcakes, \(y\) denote the number of boxes of small cupcakes and \(z\) denote the number of boxes of standard cupcakes that Roland makes.

1. Construct an objective function, \(P\), to be maximised.
2. By considering the number of units of topping used, show that \(18 x + 25 y + 21 z \leqslant 1250\).
3. Construct a similar constraint by considering the number of decorations used, simplifying the coefficients so that they are integers with no common factor.
4. Set up an initial Simplex tableau to represent Roland's problem.
5. Perform one iteration of the Simplex algorithm, choosing a pivot from the \(x\) column. Explain how the choice of pivot row was made and show how each row was calculated.
6. Write down the values of \(x , y\) and \(z\) from the first iteration of the Simplex algorithm. Hence find the maximum profit that Roland can make, remembering that cupcakes can only be sold in complete boxes. Calculate the number of units of topping and the number of decorations that are left over with this solution.
7. The constraint from the number of units of topping can be rewritten as \(18 P + 7 y + 3 z \leqslant 1250\). Form a similar expression for the constraint from the number of decorations. Use this to find the number of boxes of small cupcakes which maximises the profit when there are no decorations left over. Find the solution which gives the maximum profit using all the topping and all the decorations, and find the values of \(x , y\) and \(z\) for this solution. {}

4 A farmer has 40 acres of land that can be used for growing wheat, potatoes and soya beans. The farmer can expect a profit of \(\pounds 80\) for each acre of wheat, \(\pounds 31\) for each acre of potatoes and \(\pounds 100\) for each acre of soya beans. Land that is left unplanted incurs no cost and generates no profit. The farmer wants to choose how much land to use for growing each crop to maximise the profit. It takes 4 hours to plant each acre of wheat, 2 hours to plant each acre of potatoes and 1 hour to plant each acre of soya beans. There are 60 hours available in total for planting. At most 25 acres can be used for wheat and at most 10 acres can be used for soya beans.
Let \(x\) denote the number of acres used for wheat, \(y\) denote the number of acres used for potatoes and \(z\) denote the number of acres used for soya beans.

1. Express the profit, \(\pounds P\), as a function of \(x , y\) and \(z\).
2. Explain why the constraint \(4 x + 2 y + z \leqslant 60\) is needed. Write down three more constraints on the values of \(x , y\) and \(z\), other than that they must be non-negative.
3. Set up an initial Simplex tableau to represent the farmer's problem. Perform one iteration of the Simplex algorithm, choosing a pivot from the column with the most negative value in the objective row. Show how each row that has changed was calculated. Julie uses the Simplex algorithm to solve the farmer's problem. Her final tableau is given below. The order of the rows and the use of the slack variables in Julie's tableau may be different from yours.

   P	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
   1	0	9	0	20	0	80	0	2000
   0	1	0.5	0	0.25	0	-0.25	0	12.5
   0	0	-0.5	0	-0.25	1	0.25	0	12.5
   0	0	0	1	0	0	1	0	10
   0	0	0.5	0	-0.25	0	-0.75	1	17.5

4. Write down the values of \(x , y\) and \(z\) from Julie's final tableau. Hence advise the farmer on how many acres to use for each crop and how much land should be left unplanted.

4 Table 4 shows the butter and sugar content in two recipes. The first recipe is for 1 kg of toffee and the second is for 1 kg of fudge. \begin{table}[h] \section*{Table 6.1} (ii) Specify an efficient rule for using one-digit random numbers to simulate the time taken at the till by customers purchasing fuel. Table 6.2 shows the distribution of time taken at the till by customers who are not buying fuel. \section*{Table 6.2} (iii) Specify an efficient rule for using two-digit random numbers to simulate the time taken at the till by customers not buying fuel. What is the advantage in using two-digit random numbers instead of one-digit random numbers in this part of the question? The table in the insert shows a partially completed simulation study of 10 customers arriving at the till.
(iv) Complete the table using the random numbers which are provided.
(v) Calculate the mean total time spent queuing and paying. \end{table}

4 An eco-village is to be constructed consisting of large houses and standard houses.
Each large house has 4 bedrooms, needs a plot size of \(200 \mathrm {~m} ^ { 2 }\) and costs \(\pounds 60000\) to build.
Each standard house has 3 bedrooms, needs a plot size of \(120 \mathrm {~m} ^ { 2 }\) and costs \(\pounds 50000\) to build.
The area of land available for houses is \(120000 \mathrm {~m} ^ { 2 }\). The project has been allocated a construction budget of \(\pounds 42.4\) million. The market will not sustain more than half as many large houses as standard houses. So, for instance, if there are 500 standard houses then there must be no more than 250 large houses.

1. Define two variables so that the three constraints can be formulated in terms of your variables. Formulate the three constraints in terms of your variables.
2. Graph your three inequalities from part (i), indicating the feasible region.
3. Find the maximum number of bedrooms which can be provided, and the corresponding numbers of each type of house.
4. Modify your solution if the construction budget is increased to \(\pounds 45\) million.

4 Two products are to be made from material that is supplied in a single roll, 20 m long and 1 m wide. The two products require widths of 47 cm and 32 cm respectively. Two ways of cutting lengths of material are shown in the plans below. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-5_408_1538_520_269} \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-5_403_1533_952_274}

1. Given that there should be no unnecessary waste, draw one other cutting plan that might be used for a cut of length \(z\) metres.
2. Write down an expression for the total area that is wasted in terms of \(x , y\) and \(z\). All of the roll is to be cut, so \(x + y + z = 20\).
   There needs to be a total length of at least 20 metres of the material for the first product, the one requiring width 47 cm .
3. Write this as a linear constraint on the variables. There needs to be a total length of at least 24 metres of the material for the second product, the one requiring width 32 cm .
4. Write this as a linear constraint on the variables.
5. Formulate an LP in terms of \(x\) and \(y\) to minimise the area that is wasted. You will need to use the relationship \(x + y + z = 20\), together with your answers to parts (ii), (iii) and (iv).
6. Solve your LP graphically, and interpret the solution.

7. A leisure company owns boats of each of the following types: 2-person boats which are 4 metres long and weigh 50 kg .
4-person boats which are 3 metres long and weigh 20 kg .
8-person boats which are 14 metres long and weigh 100 kg .
The leisure company is willing to donate boats to a local sports club to accommodate up to 40 people at any one time. However, storage facilities mean that a maximum combined length of the boats must not be more than 75 metres. Also, it must be possible to transport all the boats on a single trailer which has a maximum load capacity of 600 kg . The club intends to hire the boats out to help with the cost of maintaining them. It plans to charge \(\pounds 10 , \pounds 12\) and \(\pounds 8\) per day, for the 2 -, 4 - and 8 -person boats respectively and wishes to maximise its daily revenue ( \(\pounds R\) ). Let \(x , y\) and \(z\) represent the number of 2-, 4- and 8-person boats respectively given to the club.

1. Model this as a linear programming problem simplifying your expressions so that they have integer coefficients.
   (4 marks)
2. Show that the initial tableau, when using the simplex algorithm, can be written as:

   Basic Variable	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	Value
   \(s\)	1	2	4	1	0	0	20
   \(t\)	4	3	14	0	1	0	75
   \(u\)	5	2	10	0	0	1	60
   \(R\)	\({ } ^ { - } 10\)	\({ } ^ { - } 12\)	\({ } ^ { - } 8\)	0	0	0	0

3. Explain the purpose of the variables \(s\), \(t\) and \(u\).
4. By increasing the value of \(y\) first, work out the next two complete tableaus.
5. Explain how you know that your final tableau gives an optimal solution and state this solution in practical terms. Sheet for answering question 3
   NAME \section*{Please hand this sheet in for marking}
   3. \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-08_2017_1051_462_244}
      \section*{Please hand this sheet in for marking}
   4. \(F \quad \bullet\)
      H •
      I •
      J •
      Complete matching:
      F •
      \section*{Sheet for answering question 5} NAME \section*{Please hand this sheet in for marking}
      \includegraphics[max width=\textwidth, alt={}]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-10_2398_643_248_1224}
      Sheet for answering question 6
      NAME \section*{Please hand this sheet in for marking}
   5. \(\_\_\_\_\)
   6. \(\_\_\_\_\)
   7. \(\_\_\_\_\)
   8. \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-11_592_1292_1078_312}
      Sheet for answering question 6 (cont.) \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_595_1299_351_312} \includegraphics[max width=\textwidth, alt={}, center]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-12_597_1298_1409_308}

6. A company makes lighting sets to be sold to stores for use during the Christmas period. As the product is only required at this time of year, all manufacturing takes place during September, October and November. The sets are delivered to stores at the end of each of these months. Any sets that have been made but do not need to be delivered at the end of each of September and October are put into storage which the company must pay for. Let \(x , y\) and \(z\) be the number of sets manufactured in September, October and November respectively. The demand for lighting sets and the relevant costs are shown in the table below. The company must be able to meet the demand at the end of each month and there must be no unsold articles at the end of November.

1. 1. Express \(z\) in terms of \(x\) and \(y\).
   2. Hence, find an expression for the total costs incurred in terms of \(x\) and \(y\). The company wishes to minimise its total costs by modelling this situation as a linear programming problem.
2. Find as inequalities the constraints that apply in addition to \(x \geq 800\) and \(y \geq 0\).
   (2 marks)
3. On graph paper, illustrate these inequalities and label clearly the feasible region.
   (4 marks)
4. Use your graph to solve the problem. You must state how many sets should be produced in each month and the total costs incurred by the company.
   (3 marks)

4. A company produces \(x _ { 1 }\) finished articles at the end of January, \(x _ { 2 }\) finished articles at the end of February, \(x _ { 3 }\) finished articles at the end of March, \(x _ { 4 }\) finished articles at the end of April. Other details for each month are as follows: The cost of storing each finished but unsold article is \(\pounds 500\) per month. Thus, for example, any article unsold at the end of January would incur a \(\pounds 500\) charge if it is stored until the end of February or a \(\pounds 1000\) charge if it is stored until the end of March. There must be no unsold stock at the end of April.
The selling price of each article is \(\pounds 4000\) and the total profit ( \(\pounds P\) ) must be maximised.

1. Rewrite \(x _ { 4 }\) in terms of the other 3 variables.
2. Show that the total cost incurred \(( \pounds C )\) is given by: $$C = 600 x _ { 1 } + 900 x _ { 2 } + 200 x _ { 3 } + 1125000$$
3. Hence, show that \(P = { } ^ { - } 600 x _ { 1 } - 900 x _ { 2 } - 200 x _ { 3 } + 2875000\).
4. Three of the constraints operating can be expressed as \(x _ { 1 } \geq 200\), \(x _ { 2 } \geq 0\) and \(x _ { 3 } \geq 0\). Write down inequalities representing two further constraints.
   (2 marks)
5. Explain why it is not appropriate to use a graphical method to solve this problem.
6. An employee of the company wishes to use the Simplex algorithm to solve the problem. He tries to generate an initial tableau with \(x _ { 1 } , x _ { 2 }\) and \(x _ { 3 }\) as the non-basic variables. Explain why this is not appropriate and explain what he should do instead. You are not required to generate an initial tableau or to solve the problem.
   (2 marks)

4 A publisher is considering producing three books over the next week: a mathematics book, a novel and a biography. The mathematics book will sell at \(\pounds 10\) and costs \(\pounds 4\) to produce. The novel will sell at \(\pounds 5\) and costs \(\pounds 2\) to produce. The biography will sell at \(\pounds 12\) and costs \(\pounds 5\) to produce. The publisher wants to maximise profit, and is confident that all books will be sold. There are constraints on production. Each copy of the mathematics book needs 2 minutes of printing time, 1 minute of packing time, and \(300 \mathrm {~cm} ^ { 3 }\) of temporary storage space. Each copy of the novel needs 1.5 minutes of printing time, 0.5 minutes of packing time, and \(200 \mathrm {~cm} ^ { 3 }\) of temporary storage space. Each copy of the biography needs 2.5 minutes of printing time, 1.5 minutes of packing time, and \(400 \mathrm {~cm} ^ { 3 }\) of temporary storage space. There are 10000 minutes of printing time available on several printing presses, 7500 minutes of packing time, and \(2 \mathrm {~m} ^ { 3 }\) of temporary storage space.

1. Explain how the following initial feasible tableau models this problem.

   P	\(x\)	\(y\)	\(z\)	\(s 1\)	\(s 2\)	\(s 3\)	RHS
   1	- 6	- 3	- 7	0	0	0	0
   0	2	1.5	2.5	1	0	0	10000
   0	1	0.5	1.5	0	1	0	7500
   0	300	200	400	0	0	1	2000000

2. Use the simplex algorithm to solve your LP, and interpret your solution.
3. The optimal solution involves producing just one of the three books. By how much would the price of each of the other books have to be increased to make them worth producing? There is a marketing requirement to provide at least 1000 copies of the novel.
4. Show how to incorporate this constraint into the initial tableau ready for an application of the two-stage simplex method. Briefly describe how to use the modified tableau to solve the problem. You are NOT required to perform the iterations.

5 Corey is training for a race that starts in 18 hours time. He splits his training between gym work, running and swimming.

• At most 8 hours can be spent on gym work.
• At least 4 hours must be spent running.
• The total time spent on gym work and swimming must not exceed the time spent running.

Corey thinks that time spent on gym work is worth 3 times the same time spent running or 2 times the same time spent swimming. Corey wants to maximise the worth of the training using this model.

1. Formulate a linear programming problem to represent Corey's problem. Your formulation must include defining the variables that you are using. Suppose that Corey spends the maximum of 8 hours on gym work.
2. 1. Use a graphical method to determine how long Corey should spend running and how long he should spend swimming.
   2. Describe why this solution is not practical.
   3. Describe how Corey could refine the LP model to make the solution more realistic.

1 Hussain wants to travel by train from Edinburgh to Southampton, leaving Edinburgh after 9 am and arriving in Southampton by 4 pm . He wants to leave Edinburgh as late as possible.
Hussain rings the train company to find out about the train times. Write down a question he might ask that leads to
(A) an existence problem,
(B) an optimisation problem.

7. A company makes two types of wooden bookcase, the Manhattan and the Brooklyn. The pieces of wood used for each bookcase go through three stages. They must be cut, assembled and packaged. The table below shows the time, in hours, needed to complete each of the three stages for a single bookcase, and the profit made, in pounds, when each type of bookcase is sold. The table also shows the amount of time, in hours, that is available each week for each of the three stages. Shortest route: \(\_\_\_\_\) Length of shortest route: \(\_\_\_\_\) 3. \section*{Diagram 1} \section*{Grid 1} 4. \(\begin{array} { l l l l l l l l l l l } 180 & 80 & 250 & 115 & 100 & 230 & 150 & 95 & 105 & 90 & 390 \end{array}\) \(\begin{array} { l l l l l l l l l l l } 180 & 80 & 250 & 115 & 100 & 230 & 150 & 95 & 105 & 90 & 390 \end{array}\) 5.

1. (a) \includegraphics[max width=\textwidth, alt={}, center]{e7f89fa1-0afa-4aec-a430-14ec98f487c8-22_616_1477_735_230}
   

\begin{figure}[h] \end{figure} 7. \begin{figure}[h] \end{figure}

2. A restaurant sells two sizes of pizza, small and large. The restaurant owner knows that, each evening, she needs to make

• at least 85 pizzas in total
• at least twice as many large pizzas as small pizzas

In addition, at most \(80 \%\) of the pizzas must be large.
Each small pizza costs \(\pounds 2\) to make and each large pizza costs \(\pounds 3\) to make.
The restaurant owner wants to minimise her costs. Let \(x\) represent the number of small pizzas made each evening and let \(y\) represent the number of large pizzas made each evening. Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.

7. A theatre company is planning to sell two types of ticket, standard and premier. The theatre company has completed some market research and has used this to form the following constraints.

• They will sell at most 450 tickets.
• They will sell at least three times as many standard tickets as premier tickets.
• At most \(85 \%\) of all the tickets sold will be standard.

The theatre wants to maximise its profit. The profit on each standard ticket sold is \(\pounds 5\) and the profit on each premier ticket sold is \(\pounds 8\) Let \(x\) represent the number of standard tickets sold and \(y\) represent the number of premier tickets sold. Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.
(Total 6 marks)

2. Chris has been asked to design a badge in the shape of a triangle XYZ subject to the following constraints.

• Angle \(Y\) should be at least three times the size of angle \(X\)
• Angle \(Z\) should be at least \(50 ^ { \circ }\) larger than angle \(X\)
• Angle \(Y\) must be at most \(120 ^ { \circ }\)

Chris has been asked to maximise the sum of the angles \(X\) and \(Y\).
Let \(x\) be the size of angle \(X\) in degrees.
Let \(y\) be the size of angle \(Y\) in degrees.
Let z be the size of angle \(Z\) in degrees.
Formulate this information as a linear programming problem in \(x\) and \(y\) only. State the objective and list the constraints as simplified inequalities with integer coefficients. You are not required to solve this problem.

8. Class 8 B has decided to sell apples and bananas at morning break this week to raise money for charity. The profit on each apple is 20 p , the profit on each banana is 15 p . They have done some market research and formed the following constraints.

• They will sell at most 800 items of fruit during the week.
• They will sell at least twice as many apples as bananas.
• They will sell between 50 and 100 bananas.

Assuming they will sell all their fruit, formulate the above information as a linear programming problem, letting \(a\) represent the number of apples they sell and \(b\) represent the number of bananas they sell. Write your constraints as inequalities.
(Total 7 marks)

8. A manufacturer of frozen yoghurt is going to exhibit at a trade fair. He will take two types of frozen yoghurt, Banana Blast and Strawberry Scream. He will take a total of at least 1000 litres of yoghurt.
He wants at least \(25 \%\) of the yoghurt to be Banana Blast. He also wants there to be at most half as much Banana Blast as Strawberry Scream. Each litre of Banana Blast costs \(\pounds 3\) to produce and each litre of Strawberry Scream costs \(\pounds 2\) to produce. The manufacturer wants to minimise his costs. Let \(x\) represent the number of litres of Banana Blast and \(y\) represent the number of litres of Strawberry Scream. Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.
(Total 6 marks)

7. A caterer can make three different sizes of salad; small, medium and large. The caterer will make a total of at least 280 salads. The caterer wants at least \(35 \%\) of the salads to be small and no more than \(20 \%\) of the salads to be large. The caterer has enough ingredients to make 400 small salads or 300 medium salads or 200 large salads. The profit on each small, medium and large salad is \(40 \mathrm { p } , 60 \mathrm { p }\) and 85 p respectively. The caterer wants to maximise his total profit. Let \(x\) represent the number of small salads, \(y\) represent the number of medium salads and \(z\) represent the number of large salads. Formulate this information as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.
(Total 8 marks)

4 Answer this question on the insert provided. The list of numbers below is to be sorted into decreasing order using shuttle sort. $$\begin{array} { l l l l l l l l l } 21 & 76 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$

1. How many passes through shuttle sort will be required to sort the list? After the first pass the list is as follows. $$\begin{array} { l l l l l l l l l } 76 & 21 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$
2. State the number of comparisons and the number of swaps that were made in the first pass.
3. Write down the list after the second pass. State the number of comparisons and the number of swaps that were used in making the second pass.
4. Complete the table in the insert to show the results of the remaining passes, recording the number of comparisons and the number of swaps made in each pass. You may not need all the rows of boxes printed. When the original list is sorted into decreasing order using bubble sort there are 30 comparisons and 17 swaps.
5. Use your results from part (iv) to compare the efficiency of these two methods in this case. Katie makes and sells cookies. Each batch of plain cookies takes 8 minutes to prepare and then 12 minutes to bake. Each batch of chocolate chip cookies takes 12 minutes to prepare and then 12 minutes to bake. Each batch of fruit cookies takes 10 minutes to prepare and then 12 minutes to bake. Katie can only bake one batch at a time. She has the use of the kitchen, including the oven, for at most 1 hour.
   [0pt]
6. Each batch of cookies must be prepared before it is baked. By considering the maximum time available for baking the cookies, explain why Katie can make at most 4 batches of cookies. [2] Katie models the constraints as $$\begin{gathered} x + y + z \leqslant 4 \\ 4 x + 6 y + 5 z \leqslant 24 \\ x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$ where \(x\) is the number of batches of plain cookies, \(y\) is the number of batches of chocolate chip cookies and \(z\) is the number of batches of fruit cookies that Katie makes.
7. Each batch of cookies that Katie prepares must be baked within the hour available. By considering the maximum time available for preparing the cookies, show how the constraint \(4 x + 6 y + 5 z \leqslant 24\) was formed.
8. In addition to the constraints, what other restriction is there on the values of \(x , y\) and \(z\) ? Katie will make \(\pounds 5\) profit on each batch of plain cookies, \(\pounds 4\) on each batch of chocolate chip cookies and \(\pounds 3\) on each batch of fruit cookies that she sells. Katie wants to maximise her profit.
9. Write down an expression for the objective function to be maximised. State any assumption that you have made.
10. Represent Katie's problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm, choosing to pivot on an element from the \(x\)-column. Show how each row was obtained. Write down the number of batches of cookies of each type and the profit at this stage. After carrying out market research, Katie decides that she will not make fruit cookies. She also decides that she will make at least twice as many batches of chocolate chip cookies as plain cookies.
11. Represent the constraints for Katie's new problem graphically and calculate the coordinates of the vertices of the feasible region. By testing suitable integer-valued coordinates, find how many batches of plain cookies and how many batches of chocolate chip cookies Katie should make to maximise her profit. Show your working.