7.06a LP formulation: variables, constraints, objective function

6 Jean knits items for charity. Each month the charity provides her with 75 balls of wool.
She knits hats and scarves. Hats require 1.5 balls of wool each and scarves require 3 balls each. Jean has 100 hours available each month for knitting. Hats require 4 hours each to make, and scarves require 2.5 hours each. The charity sells the hats for \(\pounds 7\) each and the scarves for \(\pounds 10\) each, and wants to gain as much income as possible. Jean prefers to knit hats but the charity wants no more than 20 per month. She refuses to knit more than 20 scarves each month.

1. Define appropriate variables, construct inequality constraints, and draw a graph representing the feasible region for this decision problem.
2. Give the objective function and find the integer solution which will give Jean's maximum monthly income.
3. If the charity drops the price of hats in a sale to \(\pounds 4\) each, what would be an optimal number of hats and scarves for Jean to knit? Assuming that all hats and scarves are sold, by how much would the monthly income drop?

6 A company manufactures two types of potting compost, Flowerbase and Growmuch. The weekly amounts produced of each are constrained by the supplies of fibre and of nutrient mix. Each litre of Flowerbase requires 0.75 litres of fibre and 1 kg of nutrient mix. Each litre of Growmuch requires 0.5 litres of fibre and 2 kg of nutrient mix. There are 12000 litres of fibre supplied each week, and 25000 kg of nutrient mix. The profit on Flowerbase is 9 p per litre. The profit on Growmuch is 20 p per litre.

1. Formulate an LP to maximise the weekly profit subject to the constraints on fibre and nutrient mix.
2. Solve your LP using a graphical approach.
3. Consider each of the following separate circumstances.
   (A) There is a reduction in the weekly supply of fibre from 12000 litres to 10000 litres. What effect does this have on profit?
   (B) The price of fibre is increased. Will this affect the optimal production plan? Justify your answer.
   [0pt] (C) The supply of nutrient mix is increased to 30000 kg per week. What is the new profit? [1]

5 John is reviewing his lifestyle, and in particular his leisure commitments. He enjoys badminton and squash, but is not sure whether he should persist with one or both. Both cost money and both take time. Playing badminton costs \(\pounds 3\) per hour and playing squash costs \(\pounds 4\) per hour. John has \(\pounds 11\) per week to spend on these activities. John takes 0.5 hours to recover from every hour of badminton and 0.75 hours to recover from every hour of squash. He has 5 hours in total available per week to play and recover.

1. Define appropriate variables and formulate two inequalities to model John's constraints.
2. Draw a graph to represent your inequalities. Give the coordinates of the vertices of your feasible region.
3. John is not sure how to define an objective function for his problem, but he says that he likes squash "twice as much" as badminton. Letting every hour of badminton be worth one "satisfaction point" define an objective function for John's problem, taking into account his "twice as much" statement.
4. Solve the resulting LP problem.
5. Given that badminton and squash courts are charged by the hour, explain why the solution to the LP is not a feasible solution to John's practical problem. Give the best feasible solution.
6. If instead John had said that he liked badminton more than squash, what would have been his best feasible solution?

3 Use a graphical approach to solve the following LP. $$\begin{aligned} & \text { Maximise } \quad 2 x + 3 y \\ & \text { subject to } \quad x + 5 y \leqslant 14 \\ & \quad x + 2 y \leqslant 8 \\ & \quad 3 x + y \leqslant 21 \\ & \quad x \geqslant 0 \\ & y \geqslant 0 \end{aligned}$$ Section B (48 marks)

1 Consider the following LP.
Maximise \(x + y\) subject to \(2 x + y < 44\) \(2 x + 3 y < 60\) \(10 x + 11 y < 244\) Part of a graphical solution is produced below and in your answer book.
Complete this graphical solution in your answer book. \includegraphics[max width=\textwidth, alt={}, center]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-2_1316_1346_916_356}

3 Consider the following linear programming problem:
Maximise \(\quad 3 x + 4 y\) subject to \(\quad 2 x + 5 y \leqslant 60\) \(x + 2 y \leqslant 25\) \(x + y \leqslant 18\)

1. Graph the inequalities and hence solve the LP.
2. The right-hand side of the second inequality is increased from 25 . At what new value will this inequality become redundant?

4 A wall 4 metres long and 3 metres high is to be tiled. Two sizes of tile are available, 10 cm by 10 cm and 30 cm by 30 cm .

1. If \(x\) is the number of boxes of ten small tiles used, and \(y\) is the number of large tiles used, explain why \(10 x + 9 y \geqslant 1200\). There are only 100 of the large tiles available.
   The tiler advises that the area tiled with the small tiles should not exceed the area tiled with the large tiles.
2. Express these two constraints in terms of \(x\) and \(y\). The smaller tiles cost 15 p each and the larger tiles cost \(\pounds 2\) each.
3. Given that the objective is to minimise the cost of tiling the wall, state the objective function. Use the graphical approach to solve the problem.
4. Give two other factors which would have to be taken into account in deciding how many of each tile to purchase.

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

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

4 In a factory, two types of motor are made. Each motor of type X takes 10 man hours to make and each motor of type Y takes 12 man hours to make. In each week there are 200 man hours available. To satisfy customer demand, at least 5 of each type of motor must be made each week.
Once a motor has been started it must be completed; no unfinished motors may be left in the factory at the end of each week. When completed, the motors are put into a container for shipping. The volume of the container is \(7 \mathrm {~m} ^ { 3 }\). A type X motor occupies a volume of \(0.5 \mathrm {~m} ^ { 3 }\) and a type Y motor occupies a volume of \(0.3 \mathrm {~m} ^ { 3 }\).

1. Define appropriate variables and from the above information derive four inequalities which must be satisfied by those variables.
2. Represent your inequalities on a graph and shade the infeasible region. The profit on each type X is \(\pounds 100\) and on each type Y is \(\pounds 70\).
3. The weekly profit is to be maximised. Write down the objective function and find the maximum profit.
4. Because of absenteeism, the manager decides to organise the work in the factory on the assumption that there will be only 180 man hours available each week. Find the number of motors of each type that should now be made in order to maximise the profit.

6 Ian the chef is to make vegetable stew and vegetable soup for distribution to a small chain of vegetarian restaurants. The recipes for both of these require carrots, beans and tomatoes. 10 litres of stew requires 1.5 kg of carrots, 1 kg of beans and 1.5 kg of tomatoes.
10 litres of soup requires 1 kg of carrots, 0.75 kg of beans and 1.5 kg of tomatoes. Ian has available 100 kg of carrots, 70 kg of beans and 110 kg of tomatoes.

1. Identify appropriate variables and write down three inequalities corresponding to the availabilities of carrots, beans and tomatoes.
2. Graph your inequalities and identify the region corresponding to feasible production plans. The profit on a litre of stew is \(\pounds 5\), and the profit on a litre of soup is \(\pounds 4\).
3. Find the most profitable production plan, showing your working. Give the maximum profit. Ian can buy in extra tomatoes at \(\pounds 2.50\) per kg .
4. What extra quantity of tomatoes should Ian buy? How much extra profit would be generated by the extra expenditure? \section*{END OF QUESTION PAPER} \section*{OCR}

3 Mary takes over a small café. She will sell two types of hot drink: tea and coffee.
A coffee filter costs her \(\pounds 0.10\), and makes one cup of coffee. A tea bag costs her \(\pounds 0.05\) and makes one cup of tea. She has a total weekly budget of \(\pounds 50\) to spend on coffee filters and tea bags. She anticipates selling at least 500 cups of hot drink per week. She estimates that between \(50 \%\) and \(75 \%\) of her sales of cups of hot drink will be for cups of coffee. Mary needs help to decide how many coffee filters and how many tea bags to buy per week.

1. Explain why the number of tea bags which she buys should be no more than the number of coffee filters, and why it should be no less than one third of the number of coffee filters.
2. Allocate appropriate variables, and draw a graph showing the feasible region for Mary's problem. Mary's partner suggests that she buys 375 coffee filters and 250 tea bags.
3. How does this suggestion relate to the estimated demand for coffee and tea?

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

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

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

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

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

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

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

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

7. A fitness centre runs introductory courses aimed at the following groups of customers: Pensioners, who will be charged \(\pounds 4\) for a 2 -hour session.
Other adults, who will be charged \(\pounds 10\) for a 4 -hour session.
Children, who will be charged \(\pounds 2\) for a 1 -hour session.
Let the number of pensioners, other adults, and children be \(x , y\) and \(z\) respectively.
Regulations state that the number of pensioners, \(x\), must be at most 5 more than the number of adults, \(y\). There must also be at least twice as many adults, \(y\), as there are children, \(z\). The centre is able to supervise up to 40 person-hours each day at the centre and wishes to maximise the revenue \(( \pounds R )\) that can be earned each day from these sessions. You may assume that the places on any courses that the centre runs will be filled.

1. Modelling this situation as a linear programming problem, write down the constraints and objective function in terms of \(x , y\) and \(z\). Using the Simplex algorithm, the following initial tableau is obtained.
2. \(\_\_\_\_\)

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

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

6. The manager of a new leisure complex needs to maximise the Revenue \(( \pounds R )\) from providing the following two weekend programmes. The following restrictions apply to each weekend.
No more than 90 participants can be accommodated.
There must be at most 40 adults.
A maximum of 600 person-hours of windsurfing can be offered.
A maximum of 300 person-hours of sailing can be offered.

1. Formulate the above information as a linear programming problem, listing the constraints as inequalities and stating the objective function \(R\).
2. On graph paper, illustrate the constraints, indicating clearly the feasible region.
3. Solve the problem graphically, stating how many adults and how many children should be accepted each weekend and what the revenue will be. The manager is considering buying more windsurfing equipment at a cost of \(\pounds 2000\). This would increase windsurfing provision by \(10 \%\).
4. State, with a reason, whether such a purchase would be cost effective.

5 [Figure 3, printed on the insert, is provided for use in this question.]
A landscape gardener has three projects, \(A , B\) and \(C\), to be completed over a period of 4 months: May, June, July and August. The gardener must allocate one of these months to each project and the other month is to be taken as a holiday. Various factors, such as availability of materials and transport, mean that the costs for completing the projects in different months will vary. The costs, in thousands of pounds, are given in the table. By completing the table of values on Figure 3, or otherwise, use dynamic programming, working backwards from August, to find the project schedule that minimises total costs. State clearly which month should be taken as a holiday and which project should be undertaken in which month.

5 Each path from \(S\) to \(T\) in the network below represents a possible way of using the internet to buy a ticket for a particular event. The number on each edge represents a charge, in pounds, with a negative value representing a discount. For example, the path SAEIT represents a ticket costing \(23 + 5 - 4 - 7 = 17\) pounds. \includegraphics[max width=\textwidth, alt={}, center]{172c5c92-4254-4593-b741-1caa83a1e833-12_1023_1330_540_350}

1. By working backwards from \(\boldsymbol { T }\) and completing the table on Figure 4, use dynamic programming to find the minimum weight of all paths from \(S\) to \(T\).
2. State the minimum cost of a ticket for the event and the paths corresponding to this minimum cost.
   (3 marks)
   1. \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4}

      Stage	State	From	Value
      1	I	\(T\)	-7
      	\(J\)	\(T\)	-6
      	\(K\)	\(T\)	-5
      2	\(E\)	\(I\)	\(- 7 - 4 = - 11\)
      	F	I
      		\(J\)
      	G	I
      		\(J\)
      		\(K\)
      	\(H\)	\(K\)
      3

      \end{table}

5 A firm is considering various strategies for development over the next few years. In the network, the number on each edge is the expected profit, in millions of pounds, moving from one year to the next. A negative number indicates a loss because of building costs or other expenses. Each path from \(S\) to \(T\) represents a complete strategy. \includegraphics[max width=\textwidth, alt={}, center]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-12_748_1575_559_228}

1. By completing the table on the page opposite, or otherwise, use dynamic programming working backwards from \(\boldsymbol { T }\) to find the maximum weight of all paths from \(S\) to \(T\).
2. State the overall maximum profit and the paths from \(S\) to \(T\) corresponding to this maximum profit.

   1. Stage	State	From	Calculation	Value
      1	G	\(T\)
      	H	\(T\)
      	I	\(T\)
      2	D	G
      		\(H\)
      	E	G
      		\(H\)
      		I
      	\(F\)	\(H\)
      		I
      3

   2. Maximum profit is £ \(\_\_\_\_\) million Corresponding paths from \(S\) to \(T\) \(\_\_\_\_\)

5

1. Display the following linear programming problem in a Simplex tableau.
   Maximise \(\quad P = x - 2 y + 3 z\) subject to $$\begin{array} { r } x + y + z \leqslant 16 \\ x - 2 y + 2 z \leqslant 17 \\ 2 x - y + 2 z \leqslant 19 \end{array}$$ and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).
2. 1. The first pivot to be chosen is from the \(z\)-column. Identify the pivot and explain why this particular value is chosen.
   2. Perform one iteration of the Simplex method.
3. 1. Perform one further iteration.
   2. Interpret the tableau that you obtained in part (c)(i) and state the values of your slack variables.

3

1. Given that \(k\) is a constant, display the following linear programming problem in a Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 6 x + 5 y + 3 z \\ \text { subject to } & x + 2 y + k z \leqslant 8 \\ & 2 x + 10 y + z \leqslant 17 \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
2. 1. Use the Simplex method to perform one iteration of your tableau for part (a), choosing a value in the \(x\)-column as pivot.
   2. Given that the maximum value of \(P\) has not been achieved after this first iteration, find the range of possible values of \(k\).
3. In the case where \(k = - 1\), perform one further iteration and interpret your final tableau.
   
   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-07_2484_1707_223_155}

4 A linear programming problem involving variables \(x , y\) and \(z\) is to be solved. The objective function to be maximised is \(P = 2 x + 6 y + k z\), where \(k\) is a constant. The initial Simplex tableau is given below.

1. In addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), write down three inequalities involving \(x , y\) and \(z\) for this problem.
2. 1. By choosing the first pivot from the \(\boldsymbol { y }\)-column, perform one iteration of the Simplex method.
   2. Given that the optimal value has not been reached, find the possible values of \(k\).
3. In the case when \(k = 20\) :
   1. perform one further iteration;
   2. interpret the final tableau and state the values of the slack variables.

6

1. Display the following linear programming problem in a Simplex tableau.
   Maximise \(\quad P = 4 x + 3 y + z\) subject to $$\begin{aligned} & 2 x + y + z \leqslant 25 \\ & x + 2 y + z \leqslant 40 \\ & x + y + 2 z \leqslant 30 \end{aligned}$$ and \(x \geqslant 0 , \quad y \geqslant 0 , \quad z \geqslant 0\).
2. The first pivot to be chosen is from the \(x\)-column. Perform one iteration of the Simplex method.
3. 1. Perform one further iteration.
   2. Interpret your final tableau and state the values of your slack variables.

3. Three depots, F, G and H, supply petrol to three service stations, S, T and U. The table gives the cost, in pounds, of transporting 1000 litres of petrol from each depot to each service station. F, G and H have stocks of 540000,789000 and 673000 litres respectively.
S, T and U require 257000,348000 and 412000 litres respectively. The total cost of transporting the petrol is to be minimised. Formulate this problem as a linear programming problem. Make clear your decision variables, objective function and constraints.