7.06a LP formulation: variables, constraints, objective function

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.

6 Each day, a factory makes three types of widget: basic, standard and luxury. The widgets produced need three different components: type \(A\), type \(B\) and type \(C\). Basic widgets need 6 components of type \(A , 6\) components of type \(B\) and 12 components of type \(C\).
Standard widgets need 4 components of type \(A , 3\) components of type \(B\) and 18 components of type \(C\).
Luxury widgets need 2 components of type \(A , 9\) components of type \(B\) and 6 components of type \(C\).
Each day, there are 240 components of type \(A\) available, 300 of type \(B\) and 900 of type \(C\).
Each day, the factory must use at least twice as many components of type \(C\) as type \(B\).
Each day, the factory makes \(x\) basic widgets, \(y\) standard widgets and \(z\) luxury widgets.

1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), find four inequalities in \(x , y\) and \(z\) that model the above constraints, simplifying each inequality.
2. Each day, the factory makes the maximum possible number of widgets. On a particular day, the factory must make the same number of luxury widgets as basic widgets.
   1. Show that your answers in part (a) become $$2 x + y \leqslant 60 , \quad 5 x + y \leqslant 100 , \quad x + y \leqslant 50 , \quad y \geqslant x$$
   2. Using the axes opposite, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region.
   3. Find the total number of widgets made on that day.
   4. Find all possible combinations of the number of each type of widget made that correspond to this maximum number.

7 A builder needs some screws, nails and plugs. At the local store, there are packs containing a mixture of the three items. A DIY pack contains 200 nails, 200 screws and 100 plugs.
A trade pack contains 1000 nails, 1500 screws and 2500 plugs.
A DIY pack costs \(\pounds 2.50\) and a trade pack costs \(\pounds 15\).
The builder needs at least 5000 nails, 6000 screws and 4000 plugs.
The builder buys \(x\) DIY packs and \(y\) trade packs and wishes to keep his total cost to a minimum.

1. Formulate the builder's situation as a linear programming problem.
2. 1. On the grid opposite, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of an objective line.
   2. Use your diagram to find the number of each type of pack that the builder should buy in order to minimise his cost.
   3. Find the builder's minimum cost.

9 Ollyin is buying new pillows for his hotel. He buys three types of pillow: soft, medium and firm. He must buy at least 100 soft pillows and at least 200 medium pillows.
He must buy at least 400 pillows in total.
Soft pillows cost \(\pounds 4\) each. Medium pillows cost \(\pounds 3\) each. Firm pillows cost \(\pounds 4\) each.
He wishes to spend no more than \(\pounds 1800\) on new pillows.
At least \(40 \%\) of the new pillows must be medium pillows.
Ollyin buys \(x\) soft pillows, \(y\) medium pillows and \(z\) firm pillows.

1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), find five inequalities in \(x , y\) and \(z\) that model the above constraints.
2. Ollyin decides to buy twice as many soft pillows as firm pillows.
   1. Show that three of your answers in part (a) become $$\begin{aligned} 3 x + 2 y & \geqslant 800 \\ 2 x + y & \leqslant 600 \\ y & \geqslant x \end{aligned}$$
   2. On the grid opposite, draw a suitable diagram to represent Ollyin's situation, indicating the feasible region.
   3. Use your diagram to find the maximum total number of pillows that Ollyin can buy.
   4. Find the number of each type of pillow that Ollyin can buy that corresponds to your answer to part (b)(iii).
      \includegraphics[max width=\textwidth, alt={}]{1258a6d3-558a-46dc-a916-d71f71b175ff-20_2256_1707_221_153}

7 Paul is a florist. Every day, he makes three types of floral bouquet: gold, silver and bronze. Each gold bouquet has 6 roses, 6 carnations and 6 dahlias.
Each silver bouquet has 4 roses, 6 carnations and 4 dahlias.
Each bronze bouquet has 3 roses, 4 carnations and 4 dahlias.
Each day, Paul must use at least 420 roses and at least 480 carnations, but he can use at most 720 dahlias. Each day, Paul makes \(x\) gold bouquets, \(y\) silver bouquets and \(z\) bronze bouquets.

1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), find three inequalities in \(x , y\) and \(z\) that model the above constraints.
2. On a particular day, Paul makes the same number of silver bouquets as bronze bouquets.
   1. Show that \(x\) and \(y\) must satisfy the following inequalities. $$\begin{aligned} & 6 x + 7 y \geqslant 420 \\ & 3 x + 5 y \geqslant 240 \\ & 3 x + 4 y \leqslant 360 \end{aligned}$$
   2. Paul makes a profit of \(\pounds 4\) on each gold bouquet sold, a profit of \(\pounds 2.50\) on each silver bouquet sold and a profit of \(\pounds 2.50\) on each bronze bouquet sold. Each day, Paul sells all the bouquets he makes. Paul wishes to maximise his daily profit, \(\pounds P\). Draw a suitable diagram, on the grid opposite, to enable this problem to be solved graphically, indicating the feasible region and the direction of the objective line.
      (6 marks)
   3. Use your diagram to find Paul's maximum daily profit and the number of each type of bouquet he must make to achieve this maximum.
3. On another day, Paul again makes the same number of silver bouquets as bronze bouquets, but he makes a profit of \(\pounds 2\) on each gold bouquet sold, a profit of \(\pounds 6\) on each silver bouquet sold and a profit of \(\pounds 6\) on each bronze bouquet sold. Find Paul's maximum daily profit, and the number of each type of bouquet he must make to achieve this maximum.
   (3 marks) Turn over -

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.

2 A baker can make apple cakes, banana cakes and cherry cakes.
The baker has exactly enough flour to make either 30 apple cakes or 20 banana cakes or 40 cherry cakes. The baker has exactly enough sugar to make either 30 apple cakes or 40 banana cakes or 30 cherry cakes. The baker has enough apples for 20 apple cakes, enough bananas for 25 banana cakes and enough cherries for 10 cherry cakes. The baker has an order for 30 cakes. The profit on each apple cake is 4 p , on each banana cake is 3 p and on each cherry cake is 2 p . The baker wants to maximise the profit on the order.

1. The availability of flour leads to the constraint \(4 a + 6 b + 3 c \leqslant 120\). Give the meaning of each of the variables \(a , b\) and \(c\) in this constraint.
2. Use the availability of sugar to give a second constraint of the form \(X a + Y b + Z c \leqslant 120\), where \(X , Y\) and \(Z\) are numbers to be found.
3. Write down a constraint from the total order size. Write down constraints from the availability of apples, bananas and cherries.
4. Write down the objective function to be maximised.
   [0pt] [You are not required to solve the resulting LP problem.]

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 An online shopping company selects some of its parcels to be checked before posting them. Each selected parcel must pass through three checks, which may be carried out in any order. One person must check the contents, another must check the postage and a third person must check the address. The parcels are classified according to the type of customer as 'new', 'occasional' or 'regular'. The table shows the time taken, in minutes, for each check on each type of parcel. The manager in charge of checking at the company has allocated each type of parcel a 'value' to represent how useful it is for generating additional income. In suitable units, these values are as follows. $$\text { new } = 8 \text { points } \quad \text { occasional } = 7 \text { points } \quad \text { regular } = 4 \text { points }$$ The manager wants to find out how many parcels of each type her department should check each hour, on average, to maximise the total value. She models this objective as $$\text { Maximise } P = 8 x + 7 y + 4 z .$$

1. What do the variables \(x , y\) and \(z\) represent?
2. Write down the constraints on the values of \(x , y\) and \(z\). The manager changes the value of parcels for regular customers to 0 points.
3. Explain what effect this has on the objective and simplify the constraints.
4. Use a graphical method to represent the feasible region for the manager's new problem. You should choose scales so that the feasible region can be clearly seen. Hence determine the optimal strategy. Now suppose that there is exactly one hour available for checking and the manager wants to find out how many parcels of each type her department should check in that hour to maximise the total value. The value of parcels for regular customers is still 0 points.
5. Find the optimal strategy in this situation.
6. Give a reason why, even if all the timings and values are correct, the total value may be less than this maximum. \section*{Question 6 is printed overleaf.}

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. {}

2 A landscape gardener is designing a garden. Part of the garden will be decking, part will be flowers and the rest will be grass. Let d be the area of decking, f be the area of flowers and g be the area of grass, all measured in \(\mathrm { m } ^ { 2 }\). The total area of the garden is \(120 \mathrm {~m} ^ { 2 }\) of which at least \(40 \mathrm {~m} ^ { 2 }\) must be grass. The area of decking must not be greater than the area of flowers. Also, the area of grass must not be more than four times the area of decking. Each square metre of grass will cost \(\pounds 5\), each square metre of decking will cost \(\pounds 10\) and each square metre of flowers will cost \(\pounds 20\). These costs include labour. The landscape gardener has been instructed to come up with the design that will cost the least.

1. Write down a constraint in d , f and g from the total area of the garden.
2. Explain why the constraint \(\mathrm { g } \leqslant 4 \mathrm {~d}\) is required.
3. Write down a constraint from the requirement that the area of decking must not be greater than the area of flowers.
4. Write down a constraint from the requirement that at least \(40 \mathrm {~m} ^ { 2 }\) of the garden must be grass and write down the minimum feasible values for each of \(d\) and \(f\).
5. Write down the objective function to be minimised.
6. Write down the resulting LP problem, using slack variables to express the constraints from parts (ii) and (iii) as equations.
   (You are not required to solve the resulting LP problem.)

1 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries. \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-2_885_873_388_635}

1. Write down the inequalities that define the feasible region. The objective is to maximise \(P _ { m } = x + m y\), where \(m\) is a positive, real-valued constant.
2. In the case when \(m = 2\), calculate the values of \(x\) and \(y\) at the optimal point, and the corresponding value of \(P _ { 2 }\).
3. (a) Write down the values of \(m\) for which point \(A\) is optimal.
   (b) Write down the values of \(m\) for which point \(B\) is optimal.

3 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries. \includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-4_919_917_322_575}

1. Obtain the four inequalities that define the feasible region.
2. Calculate the coordinates of the vertices of the feasible region, giving your values as fractions. The objective is to maximise \(P = x + 4 y\).
3. Calculate the value of \(P\) at each vertex of the feasible region. Hence write down the coordinates of the optimal point, and the corresponding value of \(P\). Suppose that the solution must have integer values for both \(x\) and \(y\).
4. Find the coordinates of the optimal point with integer-valued \(x\) and \(y\), and the corresponding value of \(P\). Explain how you know that this is the optimal solution.

6 Consider the following linear programming problem.

1. Represent the constraints graphically. Shade the regions where the inequalities are not satisfied and hence identify the feasible region.
2. Calculate the coordinates of the vertices of the feasible region, apart from the origin, and calculate the value of \(P\) at each vertex. Hence find the optimal values of \(x\) and \(y\), and state the maximum value of the objective.
3. Suppose that, additionally, \(x\) and \(y\) must both be integers. Find the maximum feasible value of \(y\) for every feasible integer value of \(x\). Calculate the value of \(P\) at each of these points and hence find the optimal values of \(x\) and \(y\) with this additional restriction. Tom wants to use the Simplex algorithm to solve the original (non-integer) problem. He reformulates it as follows.

   Maximise	\(\quad P = 5 x + 8 y\),
   subject to	\(3 x - 2 y \leqslant 12\),
   	\(3 x + 4 y \leqslant 30\),
   	\(- 3 x + 8 y \leqslant 24\),
   	\(x \geqslant 0 , y \geqslant 0\).

4. Explain why Tom needed to change the third constraint.
5. Represent the problem by an initial Simplex tableau.
6. Perform one iteration of the Simplex algorithm, choosing your pivot from the \(\boldsymbol { y }\) column. Show how the pivot row was used to calculate the other rows. Write down the values of \(x , y\) and \(P\) that result from this iteration. Perform a second iteration of the Simplex algorithm to achieve the optimum point.

6 Sandie makes tanning lotions which she sells to beauty salons. She makes three different lotions using the same basic ingredients but in different proportions. These lotions are called amber, bronze and copper. To make one litre of tanning lotion she needs one litre of fluid. This can either be water or water mixed with hempseed oil. One litre of amber lotion uses one litre of water, one litre of bronze lotion uses 0.8 litres of water and one litre of copper lotion uses 0.5 litres of water. Any remainder is made up of hempseed oil. Sandie has 40 litres of water and 7 litres of hempseed oil available.

1. By defining appropriate variables \(a , b\) and \(c\), show that the constraint on the amount of water available can be written as \(10 a + 8 b + 5 c \leqslant 400\).
2. Find a similar constraint on the amount of hempseed oil available. The tanning lotions also use two colourants which give two further availability constraints. Sandie wants to maximise her profit, \(\pounds P\). The problem can be represented as a linear programming problem with the initial Simplex tableau below. In this tableau \(s , t , u\) and \(v\) are slack variables.

   \(P\)	\(a\)	\(b\)	\(c\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
   1	-8	-7	-4	0	0	0	0	0
   0	10	8	5	1	0	0	0	400
   0	0	2	5	0	1	0	0	70
   0	2	4	1	0	0	1	0	176
   0	5	1	3	0	0	0	1	80

3. Use the initial Simplex tableau to write down two inequalities to represent the availability constraints for the colourants.
4. Write down the profit that Sandie makes on each litre of amber lotion that she sells.
5. Carry out one iteration of the Simplex algorithm, choosing a pivot from the \(a\) column. Show the operations used to calculate each row. After a second iteration of the Simplex algorithm the tableau is as given below.

   \(P\)	\(a\)	\(b\)	\(c\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
   1	0	0	14.3	0	2.7	0	1.6	317
   0	0	0	-16	1	-3	0	-2	30
   0	0	1	2.5	0	0.5	0	0	35
   0	0	0	-9.2	0	-1.8	1	-0.4	18
   0	1	0	0.1	0	-0.1	0	0.2	9

6. Explain how you know that the optimal solution has been achieved.
7. How much of each lotion should Sandie make and what is her maximum profit? Why might the profit be less than this?
8. If none of the other availabilities change, what is the least amount of water that Sandie needs to make the amounts of lotion found in part (vii)?

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.

6 William is making the bridesmaid dresses and pageboy outfits for his sister's wedding. He expects it to take 20 hours to make each bridesmaid dress and 15 hours to make each pageboy outfit. Each bridesmaid dress uses 8 metres of fabric. Each pageboy outfit uses 3 metres of fabric. The fabric costs \(\pounds 8\) per metre. Additional items cost \(\pounds 35\) for each bridesmaid dress and \(\pounds 80\) for each pageboy outfit. William's sister wants to have at least one bridesmaid and at least one pageboy. William has 100 hours available and must not spend more than \(\pounds 600\) in total on materials. Let \(x\) denote the number of bridesmaids and \(y\) denote the number of pageboys.

1. Show why the constraint \(4 x + 3 y \leqslant 20\) is needed and write down three more constraints on the values of \(x\) and \(y\), other than that they must be integers.
2. Plot the feasible region where all four constraints are satisfied. William's sister wants to maximise the total number of attendants (bridesmaids and pageboys) at her wedding.
3. Use your graph to find the maximum number of attendants.
4. William costs his time at \(\pounds 15\) an hour. Find, and simplify, an expression, in terms of \(x\) and \(y\), for the total cost (for all materials and William's time). Hence find, and interpret, the minimum cost solution to part (iii).

6 A recipe for jam states that the weight of sugar used must be between the weight of fruit used and four thirds of the weight of fruit used. Georgia has 10 kg of fruit available and 11 kg of sugar.

1. Define two variables and formulate inequalities in those variables to model this information.
2. Draw a graph to represent your inequalities.
3. Find the vertices of your feasible region and identify the points which would represent the best mix of ingredients under each of the following circumstances.
   (A) There is to be as much jam as possible, given that the weight of jam produced is the sum of the weights of the fruit and the sugar.
   (B) There is to be as much jam as possible, given that it is to have the lowest possible proportion of sugar.
   (C) There is to be as much jam as possible, given that it is to have the highest possible proportion of sugar.
   (D) Fruit costs \(\pounds 1\) per kg, sugar costs 50 p per kg and the objective is to produce as much jam as possible within a budget of \(\pounds 15\).

2 Consider the following linear programming problem.
Maximise $$\mathrm { P } = 6 x + 7 y$$ subject to $$\begin{aligned} & 2 x + 3 y \leqslant 9 \\ & 3 x + 2 y \leqslant 12 \\ & x \geqslant 0 \\ & y \geqslant 0 \end{aligned}$$

1. Use a graphical approach to solve the problem.
2. Give the optimal values of \(x , y\) and P when \(x\) and \(y\) are integers.

6 A company is planning its production of "MPowder" for the next three months.

• Over the next 3 months 20 tonnes must be produced.
• Production quantities must not be decreasing. The amount produced in month 2 cannot be less than the amount produced in month 1 , and the amount produced in month 3 cannot be less than the amount produced in month 2.
• No more than 12 tonnes can be produced in total in months 1 and 2.
• Production costs are \(\pounds 2000\) per tonne in month \(1 , \pounds 2200\) per tonne in month 2 and \(\pounds 2500\) per tonne in month 3.

The company planner starts to formulate an LP to find a production plan which minimises the cost of production: $$\begin{array} { l l } \text { Minimise } & 2000 x _ { 1 } + 2200 x _ { 2 } + 2500 x _ { 3 } \\ \text { subject to } & x _ { 1 } \geq 0 x _ { 2 } \geq 0 x _ { 3 } \geq 0 \\ & x _ { 1 } + x _ { 2 } + x _ { 3 } = 20 \\ & x _ { 1 } \leq x _ { 2 } \\ & \bullet \cdot \cdot \end{array}$$

1. Explain what the variables \(x _ { 1 } , x _ { 2 }\) and \(x _ { 3 }\) represent, and write down two more constraints to complete the formulation.
2. Explain how the LP can be reformulated to: $$\begin{array} { l l } \text { Maximise } & 500 x _ { 1 } + 300 x _ { 2 } \\ \text { subject to } & x _ { 1 } \geq 0 x _ { 2 } \geq 0 \\ & x _ { 1 } \leq x _ { 2 } \\ & x _ { 1 } + 2 x _ { 2 } \leq 20 \\ & x _ { 1 } + x _ { 2 } \leq 12 \end{array}$$
3. Use a graphical approach to solve the LP in part (ii). Interpret your solution in terms of the company's production plan, and give the minimum cost.

4 An air charter company has the following rules for selling seats on a flight.

1. The total number of seats sold must not exceed 120.
2. There must be at least 100 seats sold, or the flight will be cancelled.
3. For every child seat sold there must be a seat sold for a supervising adult.
   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).
   The price for a child seat is \(\pounds 50\) and the price for an adult seat is \(\pounds 100\).
4. Find the maximum income available from the flight, and mark and label the corresponding point on your graph.
5. Find the minimum income available from a full plane, and mark and label the corresponding point on your graph.
6. Find the minimum income available from the flight, and mark and label the corresponding point on your graph.
7. At \(\pounds 100\) for an adult seat and \(\pounds 50\) for a child seat the company would prefer to sell 100 adult seats and no child seats rather than have a full plane with 60 adults and 60 children. What would be the minimum price for a child's seat for that not to be the case, given that the adult seat price remains at \(\pounds 100\) ?

6 A manufacturing company holds stocks of two liquid chemicals. The company needs to update its stock levels. The company has 2000 litres of chemical A and 4000 litres of chemical B currently in stock. Its storage facility allows for no more than a combined total of 12000 litres of the two chemicals. Chemical A is valued at \(\pounds 5\) per litre and chemical B is valued at \(\pounds 6\) per litre. The company intends to hold stocks of these two chemicals with a total value of at least \(\pounds 61000\). Let \(a\) be the increase in the stock level of A, in thousands of litres ( \(a\) can be negative).
Let \(b\) be the increase in the stock level of B , in thousands of litres ( \(b\) can be negative).

1. Explain why \(a \geqslant - 2\), and produce a similar inequality for \(b\).
2. Explain why the value constraint can be written as \(5 a + 6 b \geqslant 27\), and produce, in similar form, the storage constraint.
3. Illustrate all four inequalities graphically.
4. Find the policy which will give a stock value of exactly \(\pounds 61000\), and will use all 12000 litres of available storage space.
5. Interpret your solution in terms of stock levels, and verify that the new stock levels do satisfy both the value constraint and the storage constraint.

3 Solve the following LP problem graphically.
Maximise \(2 x + 3 y\) subject to \(\quad x + y \leqslant 11\) $$\begin{aligned} 3 x + 5 y & \leqslant 39 \\ x + 6 y & \leqslant 39 . \end{aligned}$$