7.06c Working with constraints: algebra and ad hoc methods

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

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

5 Roland Neede, the baker, is making cupcakes. He makes three sizes of cupcake: miniature, small and standard. Miniature cupcakes are sold in boxes of 24 and each cupcake uses 3 units of topping and 2 decorations. Small cupcakes are sold in boxes of 20 and each cupcake uses 5 units of topping and 3 decorations. Standard cupcakes are sold in boxes of 12 and each cupcake uses 7 units of topping and 4 decorations. Roland has no restriction on the amount of cake mix that he uses but he only has 5000 units of topping and 3000 decorations available. Cupcakes are only sold in complete boxes, and Roland assumes that he can sell all the boxes of cupcakes that he makes. Irrespective of size, each box of cupcakes sold will give Roland a profit of \(\pounds 1\). Roland wants to maximise his total profit. Let \(x\) denote the number of boxes of miniature cupcakes, \(y\) denote the number of boxes of small cupcakes and \(z\) denote the number of boxes of standard cupcakes that Roland makes.

1. Construct an objective function, \(P\), to be maximised.
2. By considering the number of units of topping used, show that \(18 x + 25 y + 21 z \leqslant 1250\).
3. Construct a similar constraint by considering the number of decorations used, simplifying the coefficients so that they are integers with no common factor.
4. Set up an initial Simplex tableau to represent Roland's problem.
5. Perform one iteration of the Simplex algorithm, choosing a pivot from the \(x\) column. Explain how the choice of pivot row was made and show how each row was calculated.
6. Write down the values of \(x , y\) and \(z\) from the first iteration of the Simplex algorithm. Hence find the maximum profit that Roland can make, remembering that cupcakes can only be sold in complete boxes. Calculate the number of units of topping and the number of decorations that are left over with this solution.
7. The constraint from the number of units of topping can be rewritten as \(18 P + 7 y + 3 z \leqslant 1250\). Form a similar expression for the constraint from the number of decorations. Use this to find the number of boxes of small cupcakes which maximises the profit when there are no decorations left over. Find the solution which gives the maximum profit using all the topping and all the decorations, and find the values of \(x , y\) and \(z\) for this solution. {}

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

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

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.

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

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

1. Four workers, Chris (C), James (J), Katie (K) and Nicky (N), are to be allocated to four tasks, 1, 2, 3 and 4. Each worker is to be allocated to one task and each task must be allocated to one worker.

The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.
2. State which worker should be allocated to each task and the resulting total profit made.

3. Table 1 below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to four demand points \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required. \begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method.
Table 3 shows some of the improvement indices for this solution. \begin{table}[h] \end{table} \begin{table}[h] \end{table}

1. Explain why a zero has been placed in cell B3 in Table 2.
   (1)
2. Calculate the shadow costs and the missing improvement indices and enter them into Table 3 in your answer book.
3. Taking the most negative improvement index to indicate the entering cell, state the steppingstone route that should be used to obtain the next solution. You must state your entering cell and exiting cell.

2. The table shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of three demand points, 1, 2 and 3 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
   (1)
2. Taking D1 as the entering cell, use the stepping stone method to find an improved solution. Make your route clear.
   (2)
3. Perform one further iteration of the stepping stone method to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
4. Determine whether your current solution is optimal, giving a reason for your answer.

1. Four bakeries, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , supply bread to four supermarkets, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . The table gives the cost, in pounds, of transporting one lorry load of bread from each bakery to each supermarket. It also shows the number of lorry loads of bread at each bakery and the number of lorry loads of bread required at each supermarket. The total cost of transportation is to be minimised.

1. Use the north-west corner method to obtain a possible solution. A partly completed table of improvement indices is given in Table 1 in the answer book.
2. Complete Table 1.
3. Taking the most negative improvement index to indicate the entering cell, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.
4. State the cost of your improved solution.

7. Four salespersons \(A , B , C\) and \(D\) are to be sent to visit four companies 1,2,3 and 4. Each salesperson will visit exactly one company, and all companies will be visited.
Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in \(\pounds 10000\) s) are shown in the table below.

1. Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage.
2. State the value of the maximum sales.
3. Show that there is a second allocation that maximises the sales.

4 Four workers, \(A , B , C\) and \(D\), are to be allocated, one to each of the four jobs, \(W , X , Y\) and \(Z\). The table shows how much each worker would charge for each job. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_401_846_1745_642}

1. What is the total cost of the four jobs if \(A\) does \(W , B\) does \(X , C\) does \(Y\) and \(D\) does \(Z\) ?
2. Apply the Hungarian algorithm to the table, reducing rows first. Show all your working and explain each step. Give the resulting allocation and the total cost of the four jobs with this allocation.
3. What problem does the Hungarian algorithm solve?

1 Four friends have rented a house and need to decide who will have which bedroom. The table below shows how each friend rated each room, so the higher the rating the more the room was liked. The Hungarian algorithm is to be used to find the matching with the greatest total. Before the Hungarian algorithm can be used, each rating is subtracted from 6.

1. Explain why the ratings could not be used as given in the table.
2. Apply the Hungarian algorithm, reducing rows first, to match the friends to the rooms. You must show your working and say how each matrix was formed.

6 Rowena and Colin play a game in which each chooses a letter. The table shows how many points Rowena wins for each combination of letters. In each case the number of points that Colin wins is the negative of the entry in the table. Both Rowena and Colin are trying to win as many points as possible. Colin's letter \begin{table}[h] \end{table}

1. Write down Colin's play-safe strategy, showing your working. What is the maximum number of points that Colin can win if he plays safe?
2. Explain why Rowena would never choose the letter \(W\). Rowena uses random numbers to choose between her three remaining options, so that she chooses \(X , Y\) and \(Z\) with probabilities \(x , y\) and \(z\), respectively. Rowena then models the problem of which letter she should choose as the following LP. $$\begin{array} { c l } \text { Maximise } & M = m - 1 \\ \text { subject to } & m \leqslant 2 x + 6 y + z , \\ & m \leqslant 4 x + 2 y , \\ & m \leqslant 3 y + 2 z , \\ & m \leqslant 2 x + 2 z , \\ & x + y + z \leqslant 1 \\ \text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
3. Show how the expression \(2 x + 6 y + z\) was formed. The Simplex algorithm is used to solve the LP problem. The solution has \(x = 0.3 , y = 0.2\) and \(z = 0.5\).
4. Show that the optimal value of \(M\) is 0.6 . Colin then models the problem of which letter he should choose in a similar way. When Rowena plays using her optimal solution, from above, Colin finds that he should never choose the letter \(N\). Letting \(p , q\) and \(t\) denote the probabilities that he chooses \(P , Q\) and \(T\), respectively, Colin obtains the following equations. $$- 3 p + q - t = - 0.6 \quad - p - 2 q + t = - 0.6 \quad p - q - t = - 0.6 \quad p + q + t = 1$$
5. Explain how the equation \(- 3 p + q - t = - 0.6\) is obtained.
6. Use the third and fourth equations to find the value of \(p\). Hence find the values of \(q\) and \(t\).

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.
5. 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\).
6. 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\).
7. What does the table tell you about \(d\) with respect to the false proposition \(a\) ?
8. Explain why Russell introduced propositions \(b\) and \(c\) into his argument.
9. 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.
10. 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.