7.07c Interpret simplex: values of variables, slack, and objective

8. A factory can process up to five units of carrots each month. Each unit can be sold fresh or frozen or canned.
The profits, in \(\pounds 100\) s, for the number of units sold, are shown in the table.
The total monthly profit is to be maximised. Use dynamic programming to determine how many of the five units should be sold fresh, frozen and canned in order to maximise the monthly profit. State the maximum monthly profit.
(Total 12 marks)

5. In solving a three-variable maximising linear programming problem, the following tableau was obtained after the first iteration.

1. State which variable was increased first, giving a reason for your answer.
2. Solve this linear programming problem. Make your method clear by stating the row operations you use.
3. State the final value of the objective function and the final values of each variable.

7. Nigel has a business renting out his fleet of bicycles to tourists. At the start of each year Nigel must decide on one of two actions:

• Keep his fleet of bicycles, incurring maintenance costs.
• Replace his fleet of bicycles.

The cost of keeping the fleet of bicycles, the cost of replacing the fleet of bicycles and the annual income are dependent on the age of the fleet of bicycles.
Table 1 shows these amounts, in \(\pounds 1000\) s. \begin{table}[h] \end{table} Nigel has a new fleet of bicycles now and wishes to maximise his total profit over the next four years. He is planning to sell his business at the end of the fourth year.
The amount Nigel will receive will depend on the age of his fleet of bicycles.
These amounts, in £1000s, are shown in Table 2. \begin{table}[h] \end{table} Complete the table in the answer book to determine Nigel's best strategy to maximise his total profit over the next four years. You must state the action he should take each year (keep or replace) and his total profit.
(Total 13 marks)

4. The tableau below is the initial tableau for a three-variable linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm to obtain tableau T. Make your method clear by stating the row operations you use.
2. Write down the profit equation given by T .
3. Use your answer to (b) to determine whether T is optimal, justifying your answer.

3. The tableau below is the initial tableau for a three-variable linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use.
2. State the final values of the objective function and each variable.

4. A three-variable linear programming problem in \(x , y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\). The following tableau is obtained after the first iteration.

1. State which variable was increased first, giving a reason for your answer.
2. Perform one complete iteration of the simplex algorithm, to obtain a new tableau, T. Make your method clear by stating the row operations you use.
3. Write down the profit equation given by T .
4. State whether T is optimal. You must use your answer to (c) to justify your answer.

6. The tableau below is the initial tableau for a maximising linear programming problem.

1. Write down the four equations represented in the initial tableau.
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the Simplex algorithm. State the row operations that you use.
3. State whether or not your last tableau is optimal. Give a reason for your answer.

7. D2 make industrial robots. They can make up to four in any one month, but if they make more than three they need to hire additional labour at a cost of \(\pounds 300\) per month. They can store up to three robots at a cost of \(\pounds 100\) per robot per month. The overhead costs are \(\pounds 500\) in any month in which work is done. The robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock at the end of May. The order book for January to May is: Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided in the answer book. State the minimum cost.
(Total 14 marks)

2. A three-variable linear programming problem in \(x , y\) and \(z\) is to be solved. The objective is to maximise the profit \(P\). The following initial tableau was obtained.

1. Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm, to obtain tableau \(T\). State the row operations that you use.
2. Write down the profit equation shown in tableau \(T\).
3. State whether tableau \(T\) is optimal. Give a reason for your answer.

4 The "Cuddly Friends Company" produces soft toys. For one day's production run it has available \(11 \mathrm {~m} ^ { 2 }\) of furry material, \(24 \mathrm {~m} ^ { 2 }\) of woolly material and 30 glass eyes. It has three soft toys which it can produce: The "Cuddly Aardvark", each of which requires \(0.5 \mathrm {~m} ^ { 2 }\) of furry material, \(2 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 3\). The "Cuddly Bear", each of which requires \(1 \mathrm {~m} ^ { 2 }\) of furry material, \(1.5 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 5\). The "Cuddly Cat", each of which requires \(1 \mathrm {~m} ^ { 2 }\) of furry material, \(1 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 2\). An analyst formulates the following LP to find the production plan which maximises profit. $$\begin{array} { l l } \text { Maximise } & 3 a + 5 b + 2 c \\ \text { subject to } & 0.5 a + b + c \leqslant 11 , \\ & 2 a + 1.5 b + c \leqslant 24 , \\ & 2 a + 2 b + 2 c \leqslant 30 . \end{array}$$

1. Explain how this formulation models the problem, and say why the analyst has not simplified the last inequality to \(a + b + c \leqslant 15\).
2. The final constraint is different from the others in that the resource is integer valued. Explain why that does not impose an additional difficulty for this problem.
3. Solve this problem using the simplex algorithm. Interpret your solution and say what resources are left over. On a particular day an order is received for two Cuddly Cats, and the extra constraint \(c \geqslant 2\) is added to the formulation.
4. Set up an initial simplex tableau to deal with the modified problem using either the big-M approach or two-phase simplex. Do not perform any iterations on your tableau.
5. Show that the solution given by \(a = 8 , b = 2\) and \(c = 5\) uses all of the resources, but that \(a = 6 , b = 6\) and \(c = 2\) gives more profit. What resources are left over from the latter solution?

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

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

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

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

4 A publisher is considering producing three books over the next week: a mathematics book, a novel and a biography. The mathematics book will sell at \(\pounds 10\) and costs \(\pounds 4\) to produce. The novel will sell at \(\pounds 5\) and costs \(\pounds 2\) to produce. The biography will sell at \(\pounds 12\) and costs \(\pounds 5\) to produce. The publisher wants to maximise profit, and is confident that all books will be sold. There are constraints on production. Each copy of the mathematics book needs 2 minutes of printing time, 1 minute of packing time, and \(300 \mathrm {~cm} ^ { 3 }\) of temporary storage space. Each copy of the novel needs 1.5 minutes of printing time, 0.5 minutes of packing time, and \(200 \mathrm {~cm} ^ { 3 }\) of temporary storage space. Each copy of the biography needs 2.5 minutes of printing time, 1.5 minutes of packing time, and \(400 \mathrm {~cm} ^ { 3 }\) of temporary storage space. There are 10000 minutes of printing time available on several printing presses, 7500 minutes of packing time, and \(2 \mathrm {~m} ^ { 3 }\) of temporary storage space.

1. Explain how the following initial feasible tableau models this problem.

   P	\(x\)	\(y\)	\(z\)	\(s 1\)	\(s 2\)	\(s 3\)	RHS
   1	- 6	- 3	- 7	0	0	0	0
   0	2	1.5	2.5	1	0	0	10000
   0	1	0.5	1.5	0	1	0	7500
   0	300	200	400	0	0	1	2000000

2. Use the simplex algorithm to solve your LP, and interpret your solution.
3. The optimal solution involves producing just one of the three books. By how much would the price of each of the other books have to be increased to make them worth producing? There is a marketing requirement to provide at least 1000 copies of the novel.
4. Show how to incorporate this constraint into the initial tableau ready for an application of the two-stage simplex method. Briefly describe how to use the modified tableau to solve the problem. You are NOT required to perform the iterations.

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

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

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

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

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

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

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

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

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

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

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

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

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

3 A problem is represented as the initial simplex tableau below.

1. Write the problem as a linear programming formulation in the standard algebraic form with no slack variables.
2. Carry out one iteration of the simplex algorithm.
3. Show algebraically how each row of the tableau found in part (b) is calculated.

6 A linear programming problem is
Maximise \(\mathrm { P } = 2 \mathrm { x } - \mathrm { y }\) subject to $$\begin{aligned} 3 x + y - 4 z & \leqslant 24 \\ 5 x - 3 z & \leqslant 60 \\ - x + 2 y + 3 z & \leqslant 12 \end{aligned}$$ and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)

1. 1. Represent this problem as an initial simplex tableau.
   2. Carry out one iteration of the simplex algorithm. After two iterations the resulting tableau is

      \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
      1	0	\(\frac { 5 } { 11 }\)	0	\(- \frac { 6 } { 11 }\)	\(\frac { 8 } { 11 }\)	0	\(30 \frac { 6 } { 11 }\)
      0	1	\(- \frac { 3 } { 11 }\)	0	\(- \frac { 3 } { 11 }\)	\(\frac { 4 } { 11 }\)	0	\(15 \frac { 3 } { 11 }\)
      0	0	\(- \frac { 5 } { 11 }\)	1	\(- \frac { 5 } { 11 }\)	\(\frac { 3 } { 11 }\)	0	\(5 \frac { 5 } { 11 }\)
      0	0	\(\frac { 34 } { 11 }\)	0	\(\frac { 12 } { 11 }\)	\(- \frac { 5 } { 11 }\)	1	\(10 \frac { 10 } { 11 }\)

2. 1. Write down the basic variables after two iterations.
   2. Write down the exact values of the basic feasible solution for \(x , y\) and \(z\) after two iterations.
   3. State what you can deduce about the optimal value of the objective for the original problem. You are now given that, in addition to the constraints above, \(\mathrm { x } + \mathrm { y } + \mathrm { z } = 9\).
3. Use the additional constraint to rewrite the original constraints in terms of \(x\) and \(y\) but not \(z\).
4. Explain why the simplex algorithm cannot be applied to this new problem without some modification.

3 An initial simplex tableau is given below.

1. Carry out two iterations of the simplex algorithm, choosing the first pivot from the \(x\) column. After three iterations the resulting tableau is as follows.

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
   1	3	- 1	0	1	0	20
   0	5	- 4	1	1	0	20
   0	2	- 1	0	0	1	6

2. State the values of \(P , x , y , z , s\) and \(t\) that result from these three iterations.
3. Explain why no further iterations are possible. The initial simplex tableau is changed to the following, where \(k\) is a positive real value.

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
   1	2	- 3	1	0	0	0
   0	5	\(k\)	1	1	0	20
   0	2	- 1	0	0	1	6

   After one iteration of the simplex algorithm the value of \(P\) is 500 .
4. Deduce the value of \(k\).

2 A linear programming problem is Maximise \(\mathrm { P } = 2 \mathrm { x } - \mathrm { y } + \mathrm { z }\) subject to \(3 x - 4 y - z \leqslant 30\) \(x - y \leqslant 6\) \(x - 3 y + 2 z \geqslant - 2\) and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)

1. Complete the table in the Printed Answer Booklet to represent the problem as an initial simplex tableau.
2. Carry out one iteration of the simplex algorithm.
3. State the values of \(x , y\) and \(z\) that result from your iteration. After two iterations the resulting tableau is

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
   1	0	0	-2	0	2.5	0.5	16
   0	0	0	-2	1	-2.5	0.5	16
   0	1	0	-1	0	1.5	0.5	10
   0	0	1	-1	0	0.5	0.5	4

   The boundaries of the feasible region are planes, with edges each defined by two of \(x , y , z , s , t , u\) being zero.
   At each vertex of the feasible region there are three basic variables and three non-basic variables.
4. Interpret the second iteration geometrically by stating which edge of the feasible region is being moved along. As part of your geometrical interpretation, you should state the beginning vertex and end vertex of the second iteration.

3 An initial simplex tableau is shown below.

1. Write down the objective for the problem that is represented by this initial tableau. Variables \(s\) and \(t\) are slack variables.
2. Use the final row of the initial tableau to explain what a slack variable is.
3. Carry out one iteration of the simplex algorithm and hence:

7. This question is to be answered on the sheet provided in the answer booklet. A chemical company makes 3 products \(X , Y\) and \(Z\). It wishes to maximise its profit \(\pounds P\). The manager considers the limitations on the raw materials available and models the situation with the following Linear Programming problem. Maximise $$\begin{gathered} P = 3 x + 6 y + 4 z \\ x \quad + \quad z \leq 4 \\ x + 4 y + 2 z \leq 6 \\ x + y + 2 z \leq 12 \\ x \geq 0 , \quad y \geq 0 , \quad z \geq 0 \end{gathered}$$ subject to
where \(x , y\) and \(z\) are the weights, in kg , of products \(X , Y\) and \(Z\) respectively.
A possible initial tableau is

1. Explain
   1. the purpose of the variables \(r , s\) and \(t\),
   2. the final row of the tableau.
2. Solve this Linear Programming problem by using the Simplex alogorithm. Increase \(y\) for your first iteration and than increase \(x\) for your second iteration.
3. Interpret your solution.

2. While solving a maximizing linear programming problem, the following tableau was obtained.

1. Explain why this is an optimal tableau.
2. Write down the optimal solution of this problem, stating the value of every variable.
3. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).

6. The tableau below is the initial tableau for a maximising linear programming problem in \(x , y\) and \(z\).

1. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use.
   (9)
2. Explain how you know that your solution is not optimal.
   (1)