7.06d Graphical solution: feasible region, two variables

3 A farmer has 40 acres of land. Four crops, A, B, C and D are available.
Crop A will return a profit of \(\pounds 50\) per acre. Crop B will return a profit of \(\pounds 40\) per acre.
Crop C will return a profit of \(\pounds 40\) per acre. Crop D will return a profit of \(\pounds 30\) per acre.
The total number of acres used for crops A and B must not be greater than the total number used for crops C and D. The farmer formulates this problem as:
Maximise \(\quad 50 a + 40 b + 40 c + 30 d\),
subject to \(\quad a + b \leqslant 20\), \(a + b + c + d \leqslant 40\).

1. Explain what the variables \(a , b , c\) and \(d\) represent. Explain how the first inequality was obtained.
   Explain why expressing the constraint on the total area of land as an inequality will lead to a solution in which all of the land is used.
2. Solve the problem using the simplex algorithm. Suppose now that the farmer had formulated the problem as:
   Maximise \(\quad 50 a + 40 b + 40 c + 30 d\),
   subject to \(\quad a + b \leqslant 20\), \(a + b + c + d = 40\).
3. Show how to adapt this problem for solution either by the two-stage simplex method or the big-M method. In either case you should show the initial tableau and describe what has to be done next. You should not attempt to solve the problem.

4 A small alpine hotel is planned. Permission has been obtained for no more than 60 beds, and these can be accommodated in rooms containing one, two or four beds. The total floor areas needed are \(15 \mathrm {~m} ^ { 2 }\) for a one-bed room, \(25 \mathrm {~m} ^ { 2 }\) for a two-bed room and \(40 \mathrm {~m} ^ { 2 }\) for a four-bed room. The total floor area of the bedrooms must not exceed \(700 \mathrm {~m} ^ { 2 }\). Marginal profit contributions per annum, in thousands of euros, are estimated to be 5 for a one-bed room, 9 for a two-bed room and 15 for a four-bed room.

1. Formulate a linear programming problem to find the mix of rooms which will maximise the profit contribution within the two constraints.
2. Use the simplex algorithm to solve the problem, and interpret your solution. It is decided that, for marketing reasons, at least 5 one-bed rooms must be provided.
3. Solve this modified problem using either the two-stage simplex method or the big-M method. You may wish to adapt your final tableau from part (ii) to produce an initial tableau, but you are not required to do so.
4. The simplex solution to the revised problem is to provide 5 one-bed rooms, 15 two-bed rooms and 6.25 four-bed rooms, giving a profit contribution of \(€ 253750\). Interpret this solution in terms of the real world problem.
5. Compare the following solution to your answer to part (iv): 8 one-bed rooms, 12 two-bed rooms and 7 four-bed rooms. Explain your findings.

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.

4 Colin has a hobby from which he makes a small income. He makes bowls, candle holders and key fobs.
The materials he uses include wood, metal parts, polish and sandpaper. They cost, on average, \(\pounds 15\) per bowl, \(\pounds 6\) per candle holder and \(\pounds 2\) per key fob. Colin has a monthly budget of \(\pounds 100\) for materials. Colin spends no more than 30 hours per month on manufacturing these objects. Each bowl takes 4 hours, each candle holder takes 2 hours and each key fob takes half an hour.

1. Let \(b\) be the number of bowls Colin makes in a month, \(c\) the number of candle holders and \(f\) the number of key fobs. Write out, in terms of these variables, two constraints corresponding to the limit on monthly expenditure on materials, and to the limit on Colin's time. Colin sells the objects at craft fairs. He charges \(\pounds 30\) for a bowl, \(\pounds 15\) for a candle holder and \(\pounds 3\) for a key fob.
2. Set up an initial simplex tableau for the problem of maximising Colin's monthly income subject to your constraints from part (i), assuming that he sells all that he produces.
3. Use the simplex algorithm to solve your LP, and interpret the solution from the simplex algorithm. Over a spell of several months Colin finds it difficult to sell bowls so he stops making them.
4. Modify and solve your LP, using simplex, to find how many candle holders and how many key fobs he should make, and interpret your solution. At the next craft fair Colin takes an order for 4 bowls. He promises to make exactly 4 bowls in the next month.
5. Set up this modified problem either as an application of two-stage simplex, or as an application of the big-M method. You are not required to solve the problem. The solution now is for Colin to produce 4 bowls, \(6 \frac { 2 } { 3 }\) candle holders and no key fobs.
6. What is Colin's best integer solution to the problem?
7. Your answer to part (vi) is not necessarily the integer solution giving the maximum profit for Colin. Explain why.

3 Three products, A, B and C are to be made.
Three supplements are included in each product. Product A has 10 g per kg of supplement \(\mathrm { X } , 5 \mathrm {~g}\) per kg of supplement Y and 5 g per kg of supplement Z . Product B has 5 g per kg of supplement \(\mathrm { X } , 5 \mathrm {~g}\) per kg of supplement Y and 3 g per kg of supplement Z .
Product C has 12 g per kg of supplement \(\mathrm { X } , 7 \mathrm {~g}\) per kg of supplement Y and 5 g per kg of supplement Z .
There are 12 kg of supplement X available, 12 kg of supplement Y , and 9 kg of supplement Z .
Product A will sell at \(\pounds 7\) per kg and costs \(\pounds 3\) per kg to produce. Product B will sell at \(\pounds 5\) per kg and costs \(\pounds 2\) per kg to produce. Product C will sell at \(\pounds 4\) per kg and costs \(\pounds 3\) per kg to produce. The profit is to be maximised.

1. Explain how the initial feasible tableau shown in Fig. 3 models this problem. \begin{table}[h]

   P	a	b	c	s 1	s 2	s 3	RHS
   1	- 4	- 3	- 1	0	0	0	0
   0	10	5	12	1	0	0	12000
   0	5	5	7	0	1	0	12000
   0	5	3	5	0	0	1	9000

   \captionsetup{labelformat=empty} \caption{Fig. 3}
   \end{table}
2. Use the simplex algorithm to solve this problem, and interpret the solution.
3. In the solution, one of the basic variables appears at a value of 0 . Explain what this means. There is a contractual requirement to provide at least 500 kg of product A .
4. Show how to incorporate this constraint into the initial tableau ready for an application of the two-stage simplex method. Briefly describe how the method works. You are not required to perform the iterations.

1 A furniture manufacturer is planning a production run. He will be making wardrobes, drawer units and desks. All can be manufactured from the same wood. He has available \(200 \mathrm {~m} ^ { 2 }\) of wood for the production run. Allowing for wastage, a wardrobe requires \(5 \mathrm {~m} ^ { 2 }\), a drawer unit requires \(3 \mathrm {~m} ^ { 2 }\), and a desk requires \(2 \mathrm {~m} ^ { 2 }\). He has 200 hours available for the production run. A wardrobe requires 4.5 hours, a drawer unit requires 5.2 hours, and a desk requires 3.8 hours. The completed furniture will have to be stored at the factory for a short while before being shipped. The factory has \(50 \mathrm {~m} ^ { 3 }\) of storage space available. A wardrobe needs \(1 \mathrm {~m} ^ { 3 }\), a drawer unit needs \(0.75 \mathrm {~m} ^ { 3 }\), and a desk needs \(0.5 \mathrm {~m} ^ { 3 }\). The manufacturer needs to know what he should produce to maximise his income. He sells the wardrobes at \(\pounds 80\) each, the drawer units at \(\pounds 65\) each and the desks at \(\pounds 50\) each.

1. Formulate the manufacturer's problem as an LP.
2. Use the Simplex algorithm to solve the LP problem.
3. Interpret the results.
4. An extra \(25 \mathrm {~m} ^ { 2 }\) of wood is found and is to be used. The new optimal solution is to make 44 wardrobes, no drawer units and no desks. However, this leaves some of each resource (wood, hours and space) left over. Explain how this can be possible.

1. Given that \(x\) and \(y\) are propositions, draw a 4-line truth table for \(x \Rightarrow y\), allowing \(x\) and \(y\) to take all combinations of truth values. If \(x\) is false and \(x \Rightarrow y\) is true, what can be deduced about the truth value of \(y\) ? A story has it that, in a lecture on logic, the philosopher Bertrand Russell (1872-1970) mentioned that a false proposition implies any proposition. A student challenged this, saying "In that case, given that \(1 = 0\), prove that you are the Pope."
   Russell immediately replied, "Add 1 to both sides of the equation: then we have \(2 = 1\). The set containing just me and the Pope has 2 members. But \(2 = 1\), so the set has only 1 member; therefore, I am the Pope." Russell's string of statements is an example of a deductive sequence. Let \(a\) represent " \(1 = 0\) ", \(b\) represent " \(2 = 1\) ", \(c\) represent "Russell and the Pope are 2" and \(d\) represent "Russell and the Pope are 1". Then Russell's deductive sequence can be written as \(( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d\).
2. Assuming that \(a\) is false, \(b\) is false, \(a \Rightarrow b\) is true, \(c\) is true, and that \(d\) can take either truth value, draw a 2-line truth table for \(( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d\).
3. What does the table tell you about \(d\) with respect to the false proposition \(a\) ?
4. Explain why Russell introduced propositions \(b\) and \(c\) into his argument.
5. Russell could correctly have started a deductive sequence: \(a \wedge [ a \Rightarrow ( ( 0.5 = - 0.5 ) \Rightarrow ( 0.25 = 0.25 ) ) ]\).
   Had he have done so could he correctly have continued it to end at \(d\) ?
   Justify your answer.
6. Draw a combinatorial circuit to represent \(( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d\). 3 Floyd's algorithm is applied to the incomplete network on 4 nodes drawn below. The weights on the arcs represent journey times. \includegraphics[max width=\textwidth, alt={}, center]{4b5bc097-1052-4e44-8623-a84ceaab0289-4_400_558_347_751} The final matrices are shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{final time matrix}

   \cline { 2 - 5 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)
   \(\mathbf { 1 }\)	6	5	3	10

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

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	-

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.)

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)

5. A car-hire firm has six branches in a region. Three of the branches, \(A , B\) and \(C\), have spare cars, whereas the other three, \(D , E\) and \(F\), require cars. The total number of cars required is equal to the number of cars available. The table below shows the cost in pounds of sending one car from each branch with spares to each branch needing more cars and the number of cars available or required by each branch.

1. Use the north-west corner method to obtain a possible pattern of moving cars and find its cost. The firm wishes to minimise the cost of redistributing the cars.
2. Calculate shadow costs for the pattern found in part (a) and improvement indices for each unoccupied cell.
3. State, with a reason, whether or not the pattern found in part (a) is optimal.

5. A carpet manufacturer has two warehouses, \(W _ { 1 }\) and \(W _ { 2 }\), which supply carpets for three sales outlets, \(S _ { 1 } , S _ { 2 }\) and \(S _ { 3 }\). At one point \(S _ { 1 }\) requires 40 rolls of carpet, \(S _ { 2 }\) requires 23 rolls of carpet and \(S _ { 3 }\) requires 37 rolls of carpet. At this point \(W _ { 1 }\) has 45 rolls in stock and \(W _ { 2 }\) has 40 rolls in stock. The following table shows the cost, in pounds, of transporting one roll from each warehouse to each sales outlet: The company's manager wishes to supply the 85 rolls that are in stock such that transportation costs are kept to a minimum.

1. Use the north-west corner rule to obtain an initial solution to the problem.
2. Calculate improvement indices for the unused routes.
3. Use the stepping-stone method to obtain an optimal solution.

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.

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\).