7.06a LP formulation: variables, constraints, objective function

6. A linear programming problem in \(x\) and \(y\) is described as follows. Minimise \(C = 2 x + 3 y\) subject to $$\begin{aligned} x + y & \geqslant 8 \\ x & < 8 \\ 4 y & \geqslant x \\ 3 y & \leqslant 9 + 2 x \end{aligned}$$

1. Add lines and shading to Diagram 1 in the answer book to represent these constraints.
2. Hence determine the feasible region and label it R .
3. Use the objective line (ruler) method to find the exact coordinates of the optimal vertex, V, of the feasible region. You must draw and label your objective line clearly.
4. Calculate the corresponding value of \(C\) at V . The objective is now to maximise \(2 x + 3 y\), where \(x\) and \(y\) are integers.
5. Write down the optimal values of \(x\) and \(y\) and the corresponding maximum value of \(2 x + 3 y\). A further constraint, \(y \leqslant k x\), where \(k\) is a positive constant, is added to the linear programming problem.
6. Determine the least value of \(k\) for which this additional constraint does not affect the feasible region.

8. Charlie needs to buy storage containers. There are two different types of storage container available, standard and deluxe. Standard containers cost \(\pounds 20\) and deluxe containers cost \(\pounds 65\). Let \(x\) be the number of standard containers and \(y\) be the number of deluxe containers. The maximum budget available is \(\pounds 520\)

1. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. Three further constraints are: $$\begin{aligned} x & \geqslant 2 \\ - x + 24 y & \geqslant 24 \\ 7 x + 8 y & \leqslant 112 \end{aligned}$$
2. Add lines and shading to Diagram 1 in the answer book to represent all four constraints. Hence determine the feasible region and label it R . The capacity of a deluxe container is \(50 \%\) greater than the capacity of a standard container. Charlie wishes to maximise the total capacity.
3. State an objective function, in terms of \(x\) and \(y\).
4. 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.
5. Calculate the exact coordinates of vertex V.
6. Determine the number of each type of container that Charlie should buy. You must make your method clear and calculate the cost of purchasing the storage containers. Write your name here
   Final output \(\_\_\_\_\) (b)
   6. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-22_807_1426_121_267} \captionsetup{labelformat=empty} \caption{Figure 5
   [0pt] [The total weight of the network is 384]}
   \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-24_2651_1940_118_121} \includegraphics[max width=\textwidth, alt={}, center]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-25_2261_50_312_36} \section*{Q uestion 7 continued} (c) \(\_\_\_\_\) (d) \section*{Diagram 2} (Total 12 marks)
   □ 8.
   \includegraphics[max width=\textwidth, alt={}]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-26_1570_1591_260_189}
   Diagram 1 \section*{Q uestion 8 continued}
   \includegraphics[max width=\textwidth, alt={}]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-28_2646_1833_116_118}

5. \begin{figure}[h] \end{figure} Figure 5 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.

1. Write down the inequalities that form region \(R\).
2. Find the exact coordinates of the vertices of the feasible region. The objective is to maximise \(P\), where \(P = 2 x + 3 y\)
3. Use point testing to find the optimal vertex, V, of the feasible region. The objective is changed to maximise \(Q\), where \(Q = 2 x + \lambda y\) Given that \(\lambda\) is a constant and V is still the only optimal vertex of the feasible region,
4. find the range of possible values of \(\lambda\).

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

6. \begin{figure}[h] \end{figure} Figure 4 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. The vertices of the feasible region are \(A ( 4,7 ) , B ( 5,3 ) , C ( - 1,5 )\) and \(D ( - 2,1 )\).

1. Determine the inequality that defines the boundary of \(R\) that passes through vertices \(A\) and \(C\), leaving your answer with integer coefficients only. The objective is to maximise \(P = 5 x + y\)
2. Find the coordinates of the optimal vertex and the corresponding value of \(P\). The objective is changed to maximise \(Q = k x + y\)
3. If \(k\) can take any value, find the range of values of \(k\) for which \(A\) is the only optimal vertex.

8. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne. The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x , y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.

1. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities.
   (4) An initial Simplex tableau for the above situation is

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	3	2	4	1	0	0	35
   \(s\)	1	3	2	0	1	0	20
   \(t\)	2	4	3	0	0	1	24
   \(P\)	- 4	- 5	- 3	0	0	0	0

2. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage. T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.
3. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.
   (2)

8. A company makes three sizes of lamps, small, medium and large. The company is trying to determine how many of each size to make in a day, in order to maximise its profit. As part of the process the lamps need to be sanded, painted, dried and polished. A single machine carries out these tasks and is available 24 hours per day. A small lamp requires one hour on this machine, a medium lamp 2 hours and a large lamp 4 hours. Let \(x =\) number of small lamps made per day, $$\begin{aligned} & y = \text { number of medium lamps made per day, } \\ & z = \text { number of large lamps made per day, } \end{aligned}$$ where \(x \geq 0 , y \geq 0\) and \(z \geq 0\).

1. Write the information about this machine as a constraint.
2. 1. Re-write your constraint from part (a) using a slack variable \(s\).
   2. Explain what \(s\) means in practical terms. Another constraint and the objective function give the following Simplex tableau. The profit \(P\) is stated in euros.

      Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value
      \(r\)	3	5	6	1	0	50
      \(s\)	1	2	4	0	1	24
      \(P\)	- 1	- 3	- 4	0	0	0

3. Write down the profit on each small lamp.
4. Use the Simplex algorithm to solve this linear programming problem.
5. Explain why the solution to part (d) is not practical.
6. Find a practical solution which gives a profit of 30 euros. Verify that it is feasible.

7 A company repairs and sells computer hardware, including monitors, hard drives and keyboards. Each monitor takes 3 hours to repair and the cost of components is \(\pounds 40\). Each hard drive takes 2 hours to repair and the cost of components is \(\pounds 20\). Each keyboard takes 1 hour to repair and the cost of components is \(\pounds 5\). Each month, the business has 360 hours available for repairs and \(\pounds 2500\) available to buy components. Each month, the company sells all of its repaired hardware to a local computer shop. Each monitor, hard drive and keyboard sold gives the company a profit of \(\pounds 80 , \pounds 35\) and \(\pounds 15\) respectively. The company repairs and sells \(x\) monitors, \(y\) hard drives and \(z\) keyboards each month. The company wishes to maximise its total profit. 7

1. Find five inequalities involving \(x , y\) and \(z\) for the company's problem.
   [0pt] [3 marks]
   7
2. (i) Find how many of each type of computer hardware the company should repair and sell each month.
   7 (b) (ii) Explain how you know that you had reached the optimal solution in part (b) (i).
   7 (b) (iii) The local computer shop complains that they are not receiving one of the types of computer hardware that the company repairs and sells. Using your answer to part (b) (i), suggest a way in which the company's problem can be modified to address the complaint.
   [0pt] [1 mark]

4. The manager of a factory is planning the production schedule for the next three weeks for a range of cabinets. The following constraints apply to the production schedule.

• The total number of cabinets produced in week 3 cannot be fewer than the total number produced in weeks 1 and 2
• At most twice as many cabinets must be produced in week 3 as in week 2
• The number of cabinets produced in weeks 2 and 3 must, in total, be at most 125

The production cost for each cabinet produced in weeks 1,2 and 3 is \(\pounds 250 , \pounds 275\) and \(\pounds 200\) respectively.
The factory manager decides to formulate a linear programming problem to find a production schedule that minimises the total cost of production. The objective is to minimise \(250 x + 275 y + 200 z\)

1. Explain what the variables \(x , y\) and \(z\) represent.
2. Write down the constraints of the linear programming problem in terms of \(x , y\) and \(z\). Due to demand, exactly 150 cabinets must be produced during these three weeks. This reduces the constraints to $$\begin{gathered} x + y \leqslant 75 \\ x + 3 y \geqslant 150 \\ x \geqslant 25 \\ y \geqslant 0 \end{gathered}$$ which are shown in Diagram 1 in the answer book.
   Given that the manager does not want any cabinets left unfinished at the end of a week,
3. 1. use a graphical approach to solve the linear programming problem and hence determine the production schedule which minimises the cost of production. You should make your method and working clear.
   2. Find the minimum total cost of the production schedule.

3. Donald plans to bake and sell cakes. The three types of cake that he can bake are brownies, flapjacks and muffins. Donald decides to bake 48 brownies and muffins in total.
Donald decides to bake at least 5 brownies for every 3 flapjacks.
At most \(40 \%\) of the cakes will be muffins.
Donald has enough ingredients to bake 60 brownies or 45 flapjacks or 35 muffins.
Donald plans to sell each brownie for \(\pounds 1.50\), each flapjack for \(\pounds 1\) and each muffin for \(\pounds 1.25\) He wants to maximise the total income from selling the cakes. Let \(x\) represent the number of brownies, let \(y\) represent the number of flapjacks and let \(z\) represent the number of muffins that Donald will bake. Formulate this as a linear programming problem in \(x\) and \(y\) only, stating the objective function and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.

4. \begin{figure}[h] \end{figure} Figure 3 shows the constraints of a maximisation linear programming problem in \(x\) and \(y\), where \(x \geqslant 0\) and \(y \geqslant 0\). The unshaded area, including its boundaries, forms the feasible region, \(R\). An objective line has been drawn and labelled on the graph.

1. List the constraints as simplified inequalities with integer coefficients. The optimal value of the objective function is 216
2. 1. Calculate the exact coordinates of the optimal vertex.
   2. Hence derive the objective function. Given that \(x\) represents the number of small flower pots and \(y\) represents the number of large flower pots supplied to a customer,
3. deduce the optimal solution to the problem. TOTAL FOR DECISION MATHEMATICS 1 IS 40 MARKS END

4. \begin{figure}[h] \end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\). The unshaded area, including its boundaries, forms the feasible region, \(R\). An objective line has been drawn and labelled on the graph.

1. State the inequalities that define the feasible region. The maximum value of the objective function is \(\frac { 160 } { 3 }\) The minimum value of the objective function is \(\frac { 883 } { 41 }\)
2. Determine the objective function, showing your working clearly.

4. \begin{figure}[h] \end{figure} Figure 4 shows three of the six constraints for a linear programming problem in \(x\) and \(y\) The unshaded region and its boundaries satisfy these three constraints.

1. State these three constraints as simplified inequalities with integer coefficients. The variables \(x\) and \(y\) represent the number of orange fish and the number of blue fish, respectively, that are to be kept in an aquarium. The number of fish in the aquarium is subject to these three further constraints
   • there must be at least one blue fish
   • the orange fish must not outnumber the blue fish by more than ten
   • there must be no more than five blue fish for every orange fish
   • Write each of these three constraints as a simplified inequality with integer coefficients.
   • Represent these three constraints by adding lines and shading to Diagram 1 in the answer book, labelling the feasible region, \(R\)
   The total value (in pounds) of the fish in the aquarium is given by the objective function $$\text { Maximise } P = 3 x + 5 y$$
2. 1. Use the objective line method to determine the optimal point of the feasible region, giving its coordinates as exact fractions.
   2. Hence find the maximum total value of the fish in the aquarium, stating the optimal number of orange fish and the optimal number of blue fish. \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Please check the examination details below before entering your candidate information}

      Candidate surname								Other names
      Centre Number				Candidate Number
      □			□

      \end{table} \section*{Pearson Edexcel Level 3 GCE} \section*{Friday 17 May 2024} Afternoon \section*{Further Mathematics} Advanced Subsidiary
      Further Mathematics options
      27: Decision Mathematics 1
      (Part of options D, F, H and K) \section*{D1 Answer Book} Do not return the question paper with the answer book.
      1. \(\begin{array} { l l l l l l l l l l l } 4 & 6.5 & 7 & 1.3 & 2 & 5 & 1.5 & 6 & 4.5 & 6 & 1 \end{array}\) 2.
      \includegraphics[max width=\textwidth, alt={}]{ca57c64b-0b33-4179-be7f-684bd6ea2162-12_435_815_392_463}
      \section*{Diagram 1} Use this diagram only if you need to redraw your activity network. \includegraphics[max width=\textwidth, alt={}, center]{ca57c64b-0b33-4179-be7f-684bd6ea2162-12_442_820_2043_458} Copy of Diagram 1

      VJYV SIHI NI JIIYM ION OC

      V346 SIHI NI JLIYM ION OC

      V34V SIHI NI IIIIM ION OC

      Key: \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{ca57c64b-0b33-4179-be7f-684bd6ea2162-13_1217_1783_451_236} \captionsetup{labelformat=empty} \caption{Diagram 2}
      \end{figure} 3. \includegraphics[max width=\textwidth, alt={}, center]{ca57c64b-0b33-4179-be7f-684bd6ea2162-14_2463_1240_339_465}
      Shortest route from A to M:
      Length of shortest route from A to M:
      
      \includegraphics[max width=\textwidth, alt={}]{ca57c64b-0b33-4179-be7f-684bd6ea2162-16_3038_2264_0_0}
      \includegraphics[max width=\textwidth, alt={}]{ca57c64b-0b33-4179-be7f-684bd6ea2162-17_1103_1247_397_512}
      \section*{Diagram 1} \section*{There is a copy of Diagram 1 on page 11 if you need to redraw your graph.}

      VJYV SIHI NI JIIIM ION OC

      V341 S1H1 NI JLIYM ION OA

      V34V SIHI NI IIIVM ION OC

      Use this diagram only if you need to redraw your graph. \includegraphics[max width=\textwidth, alt={}, center]{ca57c64b-0b33-4179-be7f-684bd6ea2162-19_1108_1252_1606_509} Copy of Diagram 1

1. Jonathan makes two types of information pack for an event, Standard and Value.

Each Standard pack contains 25 posters and 500 flyers.
Each Value pack contains 15 posters and 800 flyers.
He must use at least 150000 flyers.
Between \(35 \%\) and \(65 \%\) of the packs must be Standard packs.
Posters cost 20p each and flyers cost 4p each.
Jonathan wishes to minimise his costs.
Let x and y represent the number of Standard packs and Value packs produced respectively.
Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem. \section*{(Total for Question 5 is 5 marks)} TOTAL IS 40 MARKS

6. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(\quad P = 2 x + 2 y - z\) subject to \(\quad 3 x + y + 2 z \leqslant 30\) $$\begin{aligned} x - y + z & \geqslant 8 \\ 4 y + 2 z & \geqslant 15 \\ x , y , z & \geqslant 0 \end{aligned}$$

1. Explain why the Simplex algorithm cannot be used to solve this linear programming problem.
2. Set up the initial tableau for solving this linear programming problem using the big-M method. After a first iteration of the big-M method, the tableau is

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(s _ { 1 }\)	3	0	1.5	1	0	0.25	0	-0.25	26.25
   \(a _ { 1 }\)	1	0	1.5	0	-1	-0.25	1	0.25	11.75
   \(y\)	0	1	0.5	0	0	-0.25	0	0.25	3.75
   \(P\)	\(- ( 2 + M )\)	0	2-1.5M	0	M	\(- 0.5 + 0.25 M\)	0	\(0.5 + 0.75 M\)	7.5-11.75M

3. State the value of each variable after the first iteration.
4. Explain why the solution given by the first iteration is not feasible. Taking the most negative entry in the profit row to indicate the pivot column,
5. obtain the most efficient pivot for a second iteration. You must give reasons for your answer.

8. Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running. Susie decides that in her training next week she should

• maximise the total time spent cycling and running
• train for at most 39 hours
• spend at least \(40 \%\) of her time swimming
• spend a total of at least 28 hours of her time swimming and running

Susie needs to determine how long she should spend next week training for each activity. Let

• \(x\) represent the number of hours swimming
• \(y\) represent the number of hours cycling
• \(z\) represent the number of hours running
  1. Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.
     (5)

Susie decides to solve this linear programming problem by using the two-stage Simplex method.

Set up an initial tableau for solving this problem using the two-stage Simplex method. As part of your solution you must show how

The following tableau \(T\) is obtained after one iteration of the second stage of the two-stage Simplex method.

b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(\mathrm { S } _ { 2 }\)	\(S _ { 3 }\)	Value
\(y\)	0	1	0	1	0	1	11
\(s _ { 2 }\)	0	0	5	-2	1	-5	62
\(x\)	1	0	1	0	0	-1	28
\(P\)	0	0	-1	1	0	1	11

Obtain a suitable pivot for a second iteration. You must give reasons for your answer.

Starting from tableau \(T\), solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use.

7. A publisher plans to produce three versions of the same book: a paperback, a hardcover, and a deluxe edition.

• Each paperback takes 4 minutes to print and 1 minute to bind
• Each hardcover takes 8 minutes to print and 5 minutes to bind
• Each deluxe edition takes 15 minutes to print and 12 minutes to bind

The printing machine is available for at most 150 hours and the binding machine must be used for at least 60 hours. The publisher decides to produce

• at least 1600 books in total
• at least three times as many paperbacks as hardcovers

The profit on each paperback sold is \(\pounds 8\), the profit on each hardcover sold is \(\pounds 20\) and the profit on each deluxe edition sold is \(\pounds 40\) Let \(x , y\) and \(z\) represent the number of paperbacks, hardcovers and deluxe editions produced.

1. Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. The publisher decides to solve this linear programming problem by using the two-stage simplex method.
2. Set up an initial tableau for solving this problem using the two-stage simplex method. As part of your solution, you must show how
   • the constraints have been made into equations by using slack variables, exactly two surplus variables and exactly two artificial variables
   • the rows for the two objective functions are formed
   The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.

   b.v.	\(x\)	\(y\)	\(z\)	\(\mathrm { S } _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(\mathrm { S } _ { 1 }\)	0	0	0	1	1	3	0	-1	-3	600
   \(z\)	0	\(\frac { 4 } { 11 }\)	1	0	\(- \frac { 1 } { 11 }\)	\(\frac { 1 } { 11 }\)	0	\(\frac { 1 } { 11 }\)	\(- \frac { 1 } { 11 }\)	\(\frac { 2000 } { 11 }\)
   \(x\)	1	\(\frac { 7 } { 11 }\)	0	0	\(\frac { 1 } { 11 }\)	\(- \frac { 12 } { 11 }\)	0	\(- \frac { 1 } { 11 }\)	\(\frac { 12 } { 11 }\)	\(\frac { 15600 } { 11 }\)
   \(s _ { 4 }\)	0	\(\frac { 40 } { 11 }\)	0	0	\(\frac { 1 } { 11 }\)	\(- \frac { 12 } { 11 }\)	1	\(- \frac { 1 } { 11 }\)	\(\frac { 12 } { 11 }\)	\(\frac { 15600 } { 11 }\)
   \(P\)	0	\(- \frac { 4 } { 11 }\)	0	0	\(- \frac { 32 } { 11 }\)	\(- \frac { 56 } { 11 }\)	0	\(\frac { 32 } { 11 }\)	\(\frac { 56 } { 11 }\)	\(\frac { 204800 } { 11 }\)
   I	0	0	0	0	0	0	0	1	1	0

3. Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method to obtain a new tableau. Make your method clear by stating the row operations you use. After three iterations of the second stage of the two-stage simplex method, the following tableau is obtained.

   b.v.	\(x\)	\(y\)	\(z\)	\(\mathrm { S } _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	Value
   \(s _ { 2 }\)	0	0	0	1	1	3	0	600
   \(z\)	0	0	1	\(\frac { 1 } { 10 }\)	0	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 10 }\)	100
   \(x\)	1	0	0	\(- \frac { 3 } { 40 }\)	0	\(- \frac { 9 } { 8 }\)	\(- \frac { 7 } { 40 }\)	1125
   \(y\)	0	1	0	\(- \frac { 1 } { 40 }\)	0	\(- \frac { 3 } { 8 }\)	\(\frac { 11 } { 40 }\)	375
   \(P\)	0	0	0	\(\frac { 29 } { 10 }\)	0	\(\frac { 7 } { 2 }\)	\(\frac { 1 } { 10 }\)	20500

   Given that the publisher produces the optimal number of each version of the book,
4. 1. state the maximum profit the publisher can earn,
   2. find the number of hours the binding machine will be used.
5. Give a reason why the publisher may not earn the profit stated in (d)(i).

5. A garden centre makes hanging baskets to sell to its customers. Three types of hanging basket are made, Sunshine, Drama and Peaceful. The plants used are categorised as Impact, Flowering or Trailing. Each Sunshine basket contains 2 Impact plants, 4 Flowering plants and 3 Trailing plants. Each Drama basket contains 3 Impact plants, 2 Flowering plants and 4 Trailing plants. Each Peaceful basket contains 1 Impact plant, 3 Flowering plants and 2 Trailing plants. The garden centre can use at most 80 Impact plants, at most 140 Flowering plants and at most 96 Trailing plants each day. The profit on Sunshine, Drama and Peaceful baskets are \(\pounds 12 , \pounds 20\) and \(\pounds 16\) respectively. The garden centre wishes to maximise its profit. Let \(x , y\) and \(z\) be the number of Sunshine, Drama and Peaceful baskets respectively, produced each day.

1. Formulate this situation as a linear programming problem, giving your constraints as inequalities.
2. State the further restriction that applies to the values of \(x , y\) and \(z\) in this context. The Simplex algorithm is used to solve this problem. After one iteration, the tableau is

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(- \frac { 1 } { 4 }\)	0	\(- \frac { 1 } { 2 }\)	1	0	\(- \frac { 3 } { 4 }\)	8
   \(s\)	\(\frac { 5 } { 2 }\)	0	2	0	1	\(- \frac { 1 } { 2 }\)	92
   \(y\)	\(\frac { 3 } { 4 }\)	1	\(\frac { 1 } { 2 }\)	0	0	\(\frac { 1 } { 4 }\)	24
   \(P\)	3	0	-6	0	0	5	480

3. State the variable that was increased in the first iteration. Justify your answer.
4. Determine how many plants in total are being used after only one iteration of the Simplex algorithm.
5. Explain why for a second iteration of the Simplex algorithm the 2 in the \(z\) column is the pivot value. After a second iteration, the tableau is

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(\frac { 3 } { 8 }\)	0	0	1	\(\frac { 1 } { 4 }\)	\(- \frac { 7 } { 8 }\)	31
   \(s\)	\(\frac { 5 } { 4 }\)	0	1	0	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 4 }\)	46
   \(y\)	\(\frac { 1 } { 8 }\)	1	0	0	\(- \frac { 1 } { 4 }\)	\(\frac { 3 } { 8 }\)	1
   \(P\)	\(\frac { 21 } { 2 }\)	0	0	0	3	\(\frac { 7 } { 2 }\)	756

6. Use algebra to explain why this tableau is optimal.
7. State the optimal number of each type of basket that should be made. The manager of the garden centre is able to increase the number of Impact plants available each day from 80 to 100 . She wants to know if this would increase her profit.
8. Use your final tableau to determine the effect of this increase. (You should not carry out any further calculations.)

1. Four workers, A, B, C and D, are to be assigned to three tasks, 1, 2 and 3 . Each task must be assigned to just one worker and each worker can do one task only.

Worker A cannot do task 2 and worker D cannot do task 3
The cost of assigning each worker to each task is shown in the table below.
The total cost is to be minimised. Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.
(6) \section*{(Total for Question 1 is 6 marks)}

2. An outdoor theatre is holding a summer gala performance. The theatre owner must decide whether to take out insurance against rain for this performance. The theatre owner estimates that

• on a fine day, the total profit will be \(\pounds 15000\)
• on a wet day, the total loss will be \(\pounds 20000\)

Insurance against rain costs \(\pounds 2000\). If the performance must be cancelled due to rain, then the theatre owner will receive \(\pounds 16000\) from the insurer. If the performance is not cancelled due to rain, then the theatre owner will receive nothing from the insurer. The probability of rain on the day of the gala performance is 0.2
Draw a decision tree and hence determine whether the theatre owner should take out the insurance against rain for this performance.

3. The table below shows the stock held at each supply point and the stock required at each demand point in a standard transportation problem. The table also shows the cost, in pounds, of transporting the stock from each supply point to each demand point. The problem is partially described by the linear programming formulation below.
Let \(x _ { i j }\) be the number of units transported from i to j $$\begin{aligned} & \text { where } \quad i \in \{ A , B , C , D \} \\ & \quad j \in \{ Q , R , S \} \text { and } x _ { i j } \geqslant 0 \\ & \text { Minimise } P = 23 x _ { A Q } + 18 x _ { A R } + 12 x _ { A S } + 8 x _ { B Q } + 10 x _ { B R } + 14 x _ { B S } \\ & \quad + 11 x _ { C Q } + 14 x _ { C R } + 21 x _ { C S } + 19 x _ { D Q } + 15 x _ { D R } + 11 x _ { D S } \end{aligned}$$

1. Write down, as inequalities, the constraints of the linear program.
2. Use the north-west corner method to obtain an initial solution to this transportation problem.
3. Taking AS as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
4. Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and the

1. Four students, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , are to be allocated to four rounds, \(1,2,3\) and 4 , in a competition. Each student is to take part in exactly one round and no two students may play in the same round.

Each student has been given an estimated score for each round. The estimated scores for each student are shown in the table below.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total estimated score. You must make your method clear and show the table after each stage.
2. Find this total estimated score.
   

3. The table below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { E } , \mathrm { F } , \mathrm { G }\) and H , to three sales points, \(\mathrm { A } , \mathrm { B }\) and C . It also shows the stock held at each supply point and the amount required at each sales point.
A minimum cost solution is required.

1. Explain why it is necessary to add a dummy demand point.
2. On Table 1 in the answer book, insert appropriate values in the dummy demand column, D. After finding an initial feasible solution and applying one iteration of the stepping-stone method, the table becomes

   	\(A\)	\(B\)	\(C\)	\(D\)
   \(E\)	21
   \(F\)	19	13
   \(G\)		6	23
   \(H\)	5			18

3. Starting with GD as the next entering cell, perform two further iterations of the stepping-stone method to obtain an improved solution. You must make your method clear by showing your routes and stating the

1. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S.

Each task must be assigned to just one worker and each worker can do only one task.
Worker B cannot be assigned to task Q and worker D cannot be assigned to task R.
The amount, in pounds, that each worker would earn when assigned to each task is shown in the table below. The Hungarian algorithm can be used to find the maximum total amount that would be earned by the four workers.

1. 1. Explain how to modify the table so that the Hungarian algorithm could be applied.
   2. Modify the table as described in (a)(i).
2. Formulate the above situation as a linear programming problem. You must define the decision variables and make the objective function and constraints clear.
   

5. Sebastien needs to make a journey. He can choose between travelling by plane, by train or by coach. Sebastien knows the exact costs of all three travel options, but he also wants to account for his travel time, including any possible delays. The cost of Sebastien's time is \(\pounds 50\) per hour.
The table below shows the costs, the journey times (without delays), and the corresponding probabilities of delays, for each travel option.

1. By drawing a decision tree, evaluate the EMV of the total cost of Sebastien's journey for each node of your tree.
2. Hence state the travel option that minimises the EMV of the total cost of Sebastien's journey.
3. A cube root utility function is applied to the total costs of each option. Determine the travel option with the best expected utility and state the corresponding value.