7.06a LP formulation: variables, constraints, objective function

3 Neil is refurbishing a listed building. There are two types of paint that he can use for the inside walls. One costs \(\pounds 1.45\) per \(\mathrm { m } ^ { 2 }\) and the other costs \(\pounds 0.95\) per \(\mathrm { m } ^ { 2 }\). He must paint the lower half of each wall in the more expensive paint. He has \(350 \mathrm {~m} ^ { 2 }\) of wall to paint. He has a budget of \(\pounds 400\) for wall paint. The more expensive paint is easier to use, and so Neil wants to use as much of it as possible. Initially, the following LP is constructed to help Neil with his purchasing of paint.
Let \(x\) be the number of \(\mathrm { m } ^ { 2 }\) of wall painted with the expensive paint.
Let \(y\) be the number of \(\mathrm { m } ^ { 2 }\) of wall painted with the less expensive paint. $$\begin{array} { l l } \text { Maximise } & P = x + y \\ \text { subject to } & 1.45 x + 0.95 y \leqslant 400 \\ & y - x \leqslant 0 \\ & x \geqslant 0 \\ & y \geqslant 0 \end{array}$$

1. Explain the purpose of the inequality \(y - x \leqslant 0\).
2. The formulation does not include the inequality \(x + y \geqslant 350\). State what this constraint models and why it has been omitted from the formulation.
3. Use the simplex algorithm to solve the LP. Pivot first on the "1" in the \(y\) column. Interpret your solution. The solution shows that Neil needs to buy more paint. He negotiates an increase in his budget to \(\pounds 450\).
4. Find the solution to the LP given by changing \(1.45 x + 0.95 y \leqslant 400\) to \(1.45 x + 0.95 y \leqslant 450\), and interpret your solution. Neil realises that although he now has a solution, that solution is not the best for his requirements.
5. Explain why the revised solution is not optimal for Neil. In order to move to an optimal solution Neil needs to change the objective of the LP and add another constraint to it.
6. Write down the new LP and the initial tableau for using two-stage simplex to solve it. Give a brief description of how to use two-stage simplex to solve it. \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-5_497_558_269_751}
   1. Solve the route inspection problem in the network above, showing the methodology you used to ensure that your solution is optimal. Show your route.
   2. Floyd's algorithm is applied to the same network to find the complete network of shortest distances. After three iterations the distance and route matrices are as follows.

      \cline { 2 - 6 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)	\(\mathbf { 5 }\)
      \(\mathbf { 1 }\)	48	24	28	11	15
      \(\mathbf { 2 }\)	24	8	4	11	16
      \(\mathbf { 3 }\)	28	4	8	7	12

2. A supplier has three warehouses, \(A , B\) and \(C\), at which there are 42,26 and 32 crates of a particular cereal respectively. Three supermarkets, \(D , E\) and \(F\), require 29, 47 and 24 crates of the cereal respectively. The supplier wishes to minimise the cost in meeting the requirements of the supermarkets. The cost, in pounds, of supplying one crate of the cereal from each warehouse to each supermarket is given in the table below. Formulate this information as a linear programming problem.

1. State your decision variables.
2. Write down the objective function in terms of your decision variables.
3. Write down the constraints, explaining what each one represents.

7. A distributor has six warehouses. At one point the distributor needs to move 25 lorries from warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) to warehouses \(W _ { \mathrm { A } } , W _ { \mathrm { B } }\) and \(W _ { \mathrm { C } }\) for the minimum possible cost. The transportation tableau below shows the unit cost, in tens of pounds, of moving a lorry between two warehouses, and the relevant figures regarding the number of lorries available or required at each warehouse.

1. Write down the initial solution given by the north-west corner rule.
2. Obtain improvement indices for the unused routes.
3. Use the stepping-stone method to find an improved solution and state why it is degenerate.
4. Placing a zero in cell \(( 2,2 )\), show that the improved solution is optimal and state the transportation pattern.
5. Find the total cost of the optimal solution. \section*{Please hand this sheet in for marking}

   Stage	State	Destination	Cost	Total cost
   \multirow[t]{3}{*}{1}	Marquee	Deluxe Cuisine
   	Castle	Deluxe Castle Cuisine
   	Hotel	Deluxe Cuisine Hotel
   \multirow[t]{3}{*}{2}	Church	Marquee Castle Hotel
   	Castle	Marquee Castle
   	Registry Office	Marquee Castle Hotel
   3	Home	Castle Church Registry

   \section*{Please hand this sheet in for marking}

   1. 	A	B	\(C\)	D	\(E\)	\(F\)	\(G\)	\(H\)
      A	-	85	59	31	47	52	74	41
      B	85	-	104	73	51	68	43	55
      C	59	104	-	54	62	88	61	45
      D	31	73	54	-	40	59	65	78
      E	47	51	62	40	-	56	71	68
      \(F\)	52	68	88	59	56	-	53	49
      \(G\)	74	43	61	65	71	53	-	63
      \(H\)	41	55	45	78	68	49	63	-

   2. 	A	\(B\)	\(C\)	D	\(E\)	\(F\)	\(G\)	\(H\)
      A	-	85	59	31	47	52	74	41
      B	85	-	104	73	51	68	43	55
      C	59	104	-	54	62	88	61	45
      D	31	73	54	-	40	59	65	78
      E	47	51	62	40	-	56	71	68
      \(F\)	52	68	88	59	56	-	53	49
      G	74	43	61	65	71	53	-	63
      \(H\)	41	55	45	78	68	49	63	-

2. A school entrance examination consists of three papers - Mathematics, English and Verbal Reasoning. Three teams of markers are to mark one style of paper each. The table below shows the average time, in minutes, taken by each team to mark one script for each style of paper. It is desired that the scripts are marked as quickly as possible.
Formulate this information as a linear programming problem.

1. State your decision variables.
2. Write down the objective function in terms of your decision variables.
3. Write down the constraints, explaining what each one represents.

7. Mrs. Hartley organises the tennis fixtures for her school. On one day she has to send a team of 10 players to a match against school \(A\) and a team of 6 players to a match against school \(B\). She has to select the two teams from a squad that includes 7 players who live in village \(C\), 5 players who live in village \(D\) and 8 players who live in village \(E\). Having a small budget, Mrs. Hartley wishes to minimise the total amount spent on travel. The table below shows the cost, in pounds, for one player to travel from each village to each of the schools they are competing against.

1. Use the north-west corner rule to find an initial solution to this problem.
2. Obtain improvement indices for this initial solution.
3. Use the stepping-stone method to obtain an optimal solution and state the pattern of transportation that this represents. \section*{Please hand this sheet in for marking}

   Stage	State	Action
   \multirow[t]{2}{*}{1}	G	GI
   	H	HI
   \multirow[t]{3}{*}{2}	D	DG DH
   	E	EG \(E H\)
   	F	FG FH
   \multirow[t]{3}{*}{3}	A	AD \(A E\) \(A F\)
   	B	BD BE \(B F\)
   	C	CD CE CF
   4	Home	Home-A Home-B Home-C

   \section*{Please hand this sheet in for marking}
   1. \includegraphics[max width=\textwidth, alt={}, center]{4e50371b-0c1c-4b4e-b21d-60858ae160df-8_662_1025_529_440}
   2. Sheet for answering question 6 (cont.)

2. The payoff matrix for player \(A\) in a two-person zero-sum game with value \(V\) is shown below. Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player \(B\).

1. Rewrite the matrix as necessary and state the new value of the game, \(v\), in terms of \(V\).
2. Define your decision variables.
3. Write down the objective function in terms of your decision variables.
4. Write down the constraints.

4. A furniture manufacturer has three workshops, \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\). Orders for rolls of fabric are to be placed with three suppliers, \(S _ { 1 } , S _ { 2 }\) and \(S _ { 3 }\). The supply, demand and cost per roll in pounds, according to which supplier each workshop uses, are given in the table below. Starting with the north-west corner method of finding an initial solution, find an optimal transportation pattern which minimises the total cost. State the final solution and its total cost.
(11 marks)

1. A glazing company runs a promotion for a special type of window. As a result of this the company receives orders for 30 of these windows from business \(B _ { 1 } , 18\) from business \(B _ { 2 }\) and 22 from business \(B _ { 3 }\). The company has stocks of 20 of these windows at factory \(F _ { 1 } , 35\) at factory \(F _ { 2 }\) and 15 at factory \(F _ { 3 }\). The table below shows the profit, in pounds, that the company will make for each window it sells according to which factory supplies each business.

The glazing company wishes to supply the windows so that the total profit is a maximum.
Formulate this information as a linear programming problem.

1. State your decision variables.
2. Write down the objective function in terms of your decision variables.
3. Write down the constraints and state what each one represents.
   

1. A team of gardeners is called in to attend to the grounds of a stately home. The three gardeners will each be assigned to one of three areas, the lawns, the hedgerows and the flower beds. The table below shows the estimated time, in hours, it will take each gardener to do each job.

The team wishes to complete the tasks in the least total time.
Formulate this information as a linear programming problem.

1. State your decision variables.
2. Write down the objective function in terms of your decision variables.
3. Write down the constraints and explain what each one represents.
   

5 Greetings cards are sold in luxury, standard and economy packs.
The table shows the cost of each pack and number of cards of each kind in the pack. Alice needs 25 cards, of which at least 8 must be handmade cards, at least 8 must be cards with flowers and at least 4 must be cards with animals.

1. Explain why Alice will need to buy at least two packs of cards. Alice does not want to spend more than \(\pounds 12\) on the cards.
2. (a) List the combinations of packs that satisfy all Alice's requirements.
   (b) Which of these is the cheapest? Ben offers to buy any cards that Alice buys but does not need. He will pay 12 pence for each handmade card and 5 pence for any other card. Alice does not want her net expenditure (the amount she spends minus the amount that Ben pays her) on the cards to be more than \(\pounds 12\).
3. Show that Alice could now buy two luxury packs. Alice decides to buy exactly 2 packs, of which \(x\) are luxury packs, \(y\) are standard packs and the rest are economy packs.
4. Give an expression, in terms of \(x\) and \(y\) only, for the number of cards of each type that Alice buys. Alice wants to minimise her net expenditure.
5. Find, and simplify, an expression for Alice's minimum net expenditure in pence, in terms of \(x\) and \(y\). You may assume that Alice buys enough cards to satisfy her own requirements.
6. Find Alice's minimum net expenditure.

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.

5 A baker makes three types of jam-and-custard doughnuts.

• Each batch of type X uses 6 units of jam and 4 units of custard.
• Each batch of type Y uses 7 units of jam and 3 units of custard.
• Each batch of type Z uses 8 units of jam and 2 units of custard.

The baker has 360 units of jam and 180 units of custard available. The baker has plenty of doughnut batter, so this does not restrict the number of batches made. From past experience the baker knows that they must make at most 30 batches of type X and at least twice as many batches of type Y as batches of type Z . Let \(x =\) number of batches of type X made \(y =\) number of batches of type Y made \(z =\) number of batches of type Z made.

1. Set up an LP formulation for the problem of maximising the total number of batches of doughnuts made. The baker finds that type Z doughnuts are not popular and decides to make zero batches of type Z .
2. Use a graphical method to find how many batches of each type the baker should make to maximise the total number of batches of doughnuts made.
3. Give a reason why this solution may not be practical. The baker finds that some of the jam has been used so there are only \(k\) units of jam (where \(k < 360\) ).
   There are still 180 units of custard available and the baker still makes zero batches of type Z .
4. Find the values of \(k\) if exactly one of the other (non-trivial) constraints is redundant. Express your answer using inequalities.

7 A linear programming problem is
Maximise \(P = 4 x + y\) subject to $$\begin{aligned} 3 x - y & \leqslant 30 \\ x + y & \leqslant 15 \\ x - 3 y & \leqslant 6 \end{aligned}$$ and \(x \geqslant 0 , y \geqslant 0\)

1. Use a graphical method to find the optimal value of \(P\), and the corresponding values of \(x\) and \(y\). An additional constraint is introduced.
   This constraint means that the value of \(y\) must be at least \(k\) times the value of \(x\), where \(k\) is a positive constant.
2. 1. Determine the set of values of \(k\) for which the optimal value of \(P\) found in part (a) is unchanged.
   2. Determine, in terms of \(k\), the values of \(x , y\) and \(P\) in the cases when the optimal solution is different from that found in part (a).

5 A garden centre sells mixed packs of flower bulbs.
Each pack contains bulbs which produce flowers of two different colours. The cost, in \(\pounds\), of a pack of each colour combination is shown in the table below.

1. Represent the information in the table as a network in which the vertices are the colours and the arcs are the packs available, weighted using the costs.
2. Construct a minimum spanning tree for the network. Taylor wants to buy at most four different packs of bulbs and to ensure that the packs include bulbs capable of producing all four flower colours. Taylor wants to minimise the total cost of these packs.
3. Determine whether or not buying the packs represented by the solution to part (b) solves Taylor's problem.
4. Represent Taylor's problem as an LP formulation, in which the variables are the number of packs of each type.

6 Beth wants to buy some tokens for use in a game.
Each token is either a silver token or a gold token.
Silver tokens and gold tokens have different points values in the game.
Silver tokens have a value of 1.5 points each.
Gold tokens have a value of 4 points each.
Beth already has 2 silver tokens and 1 gold token.
She also has \(\pounds 10\) that can be spent on buying more tokens.
Silver tokens can be bought for \(\pounds 2\) each.
Gold tokens can be bought for \(\pounds 6\) each.
After buying some tokens, Beth has \(x\) silver tokens and \(y\) gold tokens.
She now has a total of at least 5 tokens and no more than 8 tokens.

1. Set up an LP formulation in \(x\) and \(y\) for the problem of maximising the points value of tokens that she finishes with.
2. Use a graphical method to determine how many tokens of each type Beth should buy to maximise the points value of her tokens.

6 Tamsin is planning how to spend a day off. She will divide her time between walking the coast path, visiting a bird sanctuary and visiting the garden centre. Tamsin has given a value to each hour spent doing each activity. She wants to decide how much time to spend on each activity to maximise the total value of the activities. Tamsin's requirements are that she will spend:

• a total of exactly 6 hours on the three activities
• at most 3.5 hours walking the coast path
• at least as long at the bird sanctuary as at the garden centre
• at least 1 hour at the garden centre.
  1. 1. Explain why the maximum total value of the activities done is achieved when \(3 x + y\) is maximised.
     2. Show how the requirement that she spends at least as long at the bird sanctuary as at the garden centre leads to the constraint \(x + 2 y \geqslant 6\).
     3. Explain why there is no need to require that \(y \geqslant 0\).
  2. Represent the constraints graphically and hence find a solution to Tamsin's problem.

8 A sweet shop sells three different types of boxes of chocolate truffles. The cost of each type of box and the number of truffles of each variety in each type of box are given in the table below. Narendra wants to buy some boxes of truffles so that in total he has at least 20 milk chocolate, 10 plain chocolate, 16 white chocolate and 12 nutty chocolate truffles.

1. Explain why Narendra needs to buy at least four boxes of truffles.
2. Narendra decides that he will buy exactly four boxes. Determine the minimum number of Assorted boxes that Narendra must buy.
3. For your answer in part (ii),
   Narendra finds that the sweet shop has sold out of Assorted boxes, but he then spots that it also sells small boxes of milk chocolate truffles and small boxes of nutty chocolate truffles. Each small box contains 4 truffles (all of one variety) and costs \(\pounds 0.50\). He decides to buy \(x\) boxes of No Nuts and \(y\) boxes of Speciality, where \(x + y < 4\), so that he has at least 10 plain chocolate and 16 white chocolate truffles. He will then buy as many small boxes as he needs to give a total of at least 20 milk chocolate and 12 nutty chocolate truffles.
4. (a) Set up constraints on the values of \(x\) and \(y\).
   (b) Represent the feasible region graphically.
   (c) Hence determine the cheapest cost for Narendra. www.ocr.org.uk after the live examination series. If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity. For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1GE.
   OCR is part of the

7 Sam is making pies.
There is exactly enough pastry to make 7 large pies or 20 medium pies or 36 small pies, or some mixture of large, medium and small pies. This is represented as a constraint \(180 x + 63 y + 35 z \leqslant 1260\).

1. Write down what \(\mathrm { X } , \mathrm { Y }\) and Z represent. There is exactly enough filling to make 5 large pies or 12 medium pies or 18 small pies, or some mixture of large, medium and small pies.
2. Express this as a constraint of the form \(a x + b y + c z \leqslant d\), where \(a , b , c\) and \(d\) are integers. The number of small pies must equal the total number of large and medium pies.
3. Show that making exactly 9 small pies is inconsistent with the constraints.
4. Determine the maximum number of large pies that can be made.

6 Sasha is making three identical bead bracelets using amber, brown and red coloured beads. Sasha has 20 amber beads, 12 brown beads and 10 red beads. Each bracelet must use exactly 12 beads.
The profit from selling a bracelet is 6 pence for each amber bead used plus 2 pence for each brown bead used plus 3 pence for each red bead used. Sasha wants to maximise the total profit from selling the three bracelets.

1. Express Sasha's problem as a linear programming formulation in two variables \(a\) and \(b\), where \(a\) represents the number of amber beads in each bracelet and \(b\) represents the number of brown beads in each bracelet.
2. Determine how many beads of each colour will be used in each bracelet.
3. By listing all the feasible solutions, identify an aspect of the optimal solution, other than the profit, that is different from all the other feasible solutions. The beads that are not used in making the bracelets can be sold. The profit from selling each amber bead is \(k\) pence, where \(k\) is an integer, but nothing for each brown or red bead sold. All the previous constraints still apply. Instead of maximising the profit from the bracelets, Sasha wants to maximise the total profit from selling the bracelets and any left over beads. You are given that the optimal solution to the earlier problem does not maximise the total profit from selling the bracelets and any left over beads.
4. Determine the least possible value of Sasha's maximum total profit.
5. Why might Sasha not achieve this maximum profit?

6 An initial simplex tableau is shown below. The variables \(s , t\) and \(u\) are slack variables.

1. For the LP problem that this tableau represents, write down the following, in terms of \(x\) and \(y\) only.
   The graph below shows the feasible region for the problem (as the unshaded region, and its boundaries), and objective lines \(P = 10\) and \(P = 20\) (shown as dotted lines). \includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-7_883_1043_1272_244} The optimal solution is \(P = 23\), when \(x = 0\) and \(y = 4.6\).
2. Complete the first three rows of branch-and-bound in the Printed Answer Booklet, branching on \(y\) first, to determine an optimal solution when \(x\) and \(y\) are constrained to take integer values. In your working, you should show non-integer values to \(\mathbf { 2 }\) decimal places. The tableau entry 18.8 is reduced to 0 .
3. Describe carefully what changes, if any, this makes to the following.

5 A garden centre sells tulip bulbs in mixed packs. The cost of each pack and the number of tulips of each colour are given in the table. Dirk is designing a floral display in which he will need the number of red tulips to be at most 50 more than the number of white tulips, and the number of white tulips to be less than or equal to twice the number of pink tulips. He has a budget of \(\pounds 240\) and wants to find out which packs to buy to maximise the total number of bulbs. Dirk uses the variables \(x , y\) and \(z\) to represent, respectively, how many of pack A , pack B and pack C he buys. He sets up his problem as an initial simplex tableau, which is shown below. Initial tableau
Row 1
Row 2
Row 3
Row 4

1. Show how the constraint on the number of red tulips leads to one of the rows of the tableau. The tableau that results after the first iteration is shown below.
   After first iteration
   Row 5
   Row 6
   Row 7
   Row 8

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
   1	0	- 0.04	0.06	0	0	0.02	4.8
   0	0	1	- 1	1	0	0	5
   0	0	10.8	7.3	0	1	0.1	24
   0	1	0.96	1.06	0	0	0.02	4.8

2. Which cell was used as the pivot?
3. Explain why row 2 and row 6 are the same.
4. (a) Read off the values of \(x , y\) and \(z\) after the first iteration.
   (b) Interpret this solution in terms of the original problem.
5. Identify the variable that has become non-basic. Use the pivot row of the initial tableau to eliminate \(x\) algebraically from the equation represented by Row 1 of the initial tableau. The feasible region can be represented graphically in three dimensions, with the variables \(x , y\) and \(z\) corresponding to the \(x\)-axis, \(y\)-axis and \(z\)-axis respectively. The boundaries of the feasible region are planes. Pairs of these planes intersect in lines and at the vertices of the feasible region these lines intersect.
6. The planes defined by each of the new basic variables being set equal to 0 intersect at a point. Show how the equations from part (v) are used to find the values \(P\) and \(x\) at this point. A planar graph \(G\) is described by the adjacency matrix below. \(\quad\) \(A\) \(B\) \(C\) \(D\) \(E\) \(F\) \(\left( \begin{array} { c c c c c c } A & B & C & D & E & F \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \end{array} \right)\)
7. Draw the graph \(G\).
8. Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it.
9. Explain why graph \(G\) cannot have a Hamiltonian cycle that includes the edge \(A B\). Deduce how many Hamiltonian cycles graph \(G\) has. A colouring algorithm is given below. STEP 1: Choose a vertex, colour this vertex using colour 1. STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1 . STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2 . STEP 4: Go back to STEP 2.
10. Apply this algorithm to graph \(G\), starting at \(E\). Explain how the colouring shows you that graph \(G\) is not bipartite. By removing just one edge from graph \(G\) it is possible to make a bipartite graph.
11. Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. Graph \(G\) is augmented by the addition of a vertex \(X\) joined to each of \(A , B , C , D , E\) and \(F\).
12. Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2.

6. Jonathan is going to make hats to sell at a fete. He can make red hats and green hats. Jonathan can use linear programming to determine the number of each colour of hat that he should make. Let \(x\) be the number of red hats he makes and \(y\) be the number of green hats he makes.
One of the constraints is that there must be at least 30 hats.

1. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. Two further constraints are $$\begin{aligned} & 2 y + x \geqslant 40 \\ & 2 y - x \geqslant - 30 \end{aligned}$$
2. Write down two more constraints which apply.
3. Represent all these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R . The cost of making a green hat is three times the cost of making a red hat. Jonathan wishes to minimise the total cost.
4. Use the objective line (ruler) method to determine the number of red hats and number of green hats that Jonathan should make. You must clearly draw and label your objective line. Given that the minimum total cost of making the hats is \(\pounds 107.50\)
5. determine the cost of making one green hat and the cost of making one red hat. You must make your method clear.

5. A linear programming problem in \(x\) and \(y\) is described as follows. $$\begin{array} { l l } \text { Maximise } & \mathrm { P } = 5 x + 3 y \\ \text { subject to: } & x \geqslant 3 \\ & x + y \leqslant 9 \\ & 15 x + 22 y \leqslant 165 \\ & 26 x - 50 y \leqslant 325 \end{array}$$

1. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
2. Use the objective line method to find the optimal vertex, V, of the feasible region. You must draw and label your objective line and label vertex V clearly.
3. Calculate the exact coordinates of vertex V and hence calculate the corresponding value of P at V . The objective is now to minimise \(5 x + 3 y\), where \(x\) and \(y\) are integers.
4. Write down the minimum value of \(5 x + 3 y\) and the corresponding value of \(x\) and corresponding value of \(y\).

8. A shop sells three types of pen. These are ballpoint pens, rollerball pens and fountain pens. The shop manager knows that each week she should order

• at least 50 pens in total
• at least twice as many rollerball pens as fountain pens

In addition,

• at most \(60 \%\) of the pens she orders must be ballpoint pens
• at least a third of the pens she orders must be rollerball pens

Each ballpoint pen costs \(\pounds 2\), each rollerball pen costs \(\pounds 3\) and each fountain pen costs \(\pounds 5\) The shop manager wants to minimise her costs.
Let \(x\) represent the number of ballpoint pens ordered, let \(y\) represent the number of rollerball pens ordered and let \(z\) represent the number of fountain pens ordered.

1. Formulate this information as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. The shop manager decides to order exactly 10 fountain pens. This reduces the problem to the following $$\begin{array} { l r } \text { Minimise } & P = 2 x + 3 y \\ \text { subject to } & x + y \geqslant 40 \\ & 2 x - 3 y \leqslant 30 \\ - x + 2 y \geqslant 10 \\ & y \geqslant 20 \\ & x \geqslant 0 \end{array}$$
2. Represent these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R .
3. Use the objective line method to find the optimal vertex, V, of the feasible region. You must make your objective line clear and label the optimal vertex V.
4. Write down the number of each type of pen that the shop manager should order. Calculate the cost of this order.
   (Total \(\mathbf { 1 6 }\) marks)

7. Emily is planning to sell three types of milkshake, strawberry, vanilla and chocolate. Emily has completed some market research and has used this to form the following constraints on the number of milkshakes that she will sell each week.

• She will sell fewer than 200 non-vanilla milkshakes in total.
• She will sell at most 2.5 times as many strawberry milkshakes as vanilla milkshakes.
• At most, \(75 \%\) of the milkshakes that she will sell will be vanilla.

The profit on each strawberry milkshake sold is \(\pounds 0.75\), the profit on each vanilla milkshake sold is \(\pounds 1.20\) and the profit on each chocolate milkshake sold is \(\pounds 1.45\) Emily wants to maximise her profit.
Let \(x\) represent the number of strawberry milkshakes sold, let \(y\) represent the number of vanilla milkshakes sold and let \(z\) represent the number of chocolate milkshakes sold.

1. Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. In week 1, Emily sells 100 strawberry milkshakes and 25 chocolate milkshakes.
2. Calculate the maximum possible profit and minimum possible profit, in pounds, for the sale of all milkshakes in week 1. You must show your working.