7.07a Simplex tableau: initial setup in standard format

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.

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:

5 A garden centre sells tulip bulbs in mixed packs. The cost of each pack and the number of tulips of each colour are given in the table. Dirk is designing a floral display in which he will need the number of red tulips to be at most 50 more than the number of white tulips, and the number of white tulips to be less than or equal to twice the number of pink tulips. He has a budget of \(\pounds 240\) and wants to find out which packs to buy to maximise the total number of bulbs. Dirk uses the variables \(x , y\) and \(z\) to represent, respectively, how many of pack A , pack B and pack C he buys. He sets up his problem as an initial simplex tableau, which is shown below. Initial tableau
Row 1
Row 2
Row 3
Row 4

1. Show how the constraint on the number of red tulips leads to one of the rows of the tableau. The tableau that results after the first iteration is shown below.
   After first iteration
   Row 5
   Row 6
   Row 7
   Row 8

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
   1	0	- 0.04	0.06	0	0	0.02	4.8
   0	0	1	- 1	1	0	0	5
   0	0	10.8	7.3	0	1	0.1	24
   0	1	0.96	1.06	0	0	0.02	4.8

2. Which cell was used as the pivot?
3. Explain why row 2 and row 6 are the same.
4. (a) Read off the values of \(x , y\) and \(z\) after the first iteration.
   (b) Interpret this solution in terms of the original problem.
5. Identify the variable that has become non-basic. Use the pivot row of the initial tableau to eliminate \(x\) algebraically from the equation represented by Row 1 of the initial tableau. The feasible region can be represented graphically in three dimensions, with the variables \(x , y\) and \(z\) corresponding to the \(x\)-axis, \(y\)-axis and \(z\)-axis respectively. The boundaries of the feasible region are planes. Pairs of these planes intersect in lines and at the vertices of the feasible region these lines intersect.
6. The planes defined by each of the new basic variables being set equal to 0 intersect at a point. Show how the equations from part (v) are used to find the values \(P\) and \(x\) at this point. A planar graph \(G\) is described by the adjacency matrix below. \(\quad\) \(A\) \(B\) \(C\) \(D\) \(E\) \(F\) \(\left( \begin{array} { c c c c c c } A & B & C & D & E & F \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \end{array} \right)\)
7. Draw the graph \(G\).
8. Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it.
9. Explain why graph \(G\) cannot have a Hamiltonian cycle that includes the edge \(A B\). Deduce how many Hamiltonian cycles graph \(G\) has. A colouring algorithm is given below. STEP 1: Choose a vertex, colour this vertex using colour 1. STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1 . STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2 . STEP 4: Go back to STEP 2.
10. Apply this algorithm to graph \(G\), starting at \(E\). Explain how the colouring shows you that graph \(G\) is not bipartite. By removing just one edge from graph \(G\) it is possible to make a bipartite graph.
11. Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. Graph \(G\) is augmented by the addition of a vertex \(X\) joined to each of \(A , B , C , D , E\) and \(F\).
12. Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2.

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.

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.

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.

7. A maximisation linear programming problem in \(x , y\) and \(z\) is to be solved using the two-stage simplex method. The partially completed initial tableau is shown below.

1. Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities.
2. Complete the bottom row of Table 1 in the answer book. You should make your method and working clear. The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.

   Basic variable	\(x\)	\(y\)	\(z\)	\(S _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(S _ { 1 }\)	0	\(\frac { 5 } { 6 }\)	0	1	\(\frac { 7 } { 12 }\)	\(\frac { 3 } { 4 }\)	\(- \frac { 7 } { 12 }\)	\(- \frac { 3 } { 4 }\)	\(\frac { 147 } { 4 }\)
   \(x\)	1	\(\frac { 2 } { 3 }\)	0	0	\(- \frac { 1 } { 3 }\)	0	\(\frac { 1 } { 3 }\)	0	3
   \(z\)	0	\(\frac { 1 } { 6 }\)	1	0	\(- \frac { 1 } { 12 }\)	\(- \frac { 1 } { 4 }\)	\(\frac { 1 } { 12 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 7 } { 4 }\)
   \(P\)	0	\(\frac { 5 } { 6 }\)	0	0	\(- \frac { 11 } { 12 }\)	\(- \frac { 3 } { 4 }\)	\(\frac { 11 } { 12 }\)	\(\frac { 3 } { 4 }\)	\(\frac { 45 } { 4 }\)
   A	0	0	0	0	0	0	1	1	0

3. 1. Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem.
   2. Write down the basic feasible solution for the second stage.
4. 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, \(T\). Make your method clear by stating the row operations you use.
5. 1. Explain, using \(T\), whether or not an optimal solution to the original linear programming problem has been found.
   2. Write down the value of the objective function.
   3. State the values of the basic variables.

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.

4. A linear programming problem in \(x , y\) and \(z\) is to be solved using the big-M method. The initial tableau is shown below.

1. Using the information in the above tableau, formulate the linear programming problem. You should
   \section*{Please turn over for Question 5}

7. \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. The objective is to maximise \(P = x + k y\), where \(k\) is a positive constant.
The optimal vertex of \(R\) is to be found using the Simplex algorithm.

1. Set up an initial tableau for solving this linear programming problem using the Simplex algorithm. After two iterations of the Simplex algorithm a possible tableau \(T\) is

   b.v.	\(x\)	\(y\)	\(S _ { 1 }\)	\(s _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	Value
   \(s _ { 1 }\)	0	0	1	\(- \frac { 3 } { 5 }\)	0	\(\frac { 1 } { 5 }\)	1
   \(x\)	1	0	0	\(\frac { 1 } { 5 }\)	0	\(- \frac { 2 } { 5 }\)	2
   \(S _ { 3 }\)	0	0	0	\(- \frac { 11 } { 5 }\)	1	\(\frac { 12 } { 5 }\)	22
   \(y\)	0	1	0	\(\frac { 2 } { 5 }\)	0	\(\frac { 1 } { 5 }\)	5
   \(P\)	0	0	0	\(\frac { 1 } { 5 } + \frac { 2 } { 5 } k\)	0	\(- \frac { 2 } { 5 } + \frac { 1 } { 5 } k\)	\(5 k + 2\)

2. State the value of each variable after the second iteration.
   (1) It is given that \(T\) does not give an optimal solution to the linear programming problem.
   After a third iteration of the Simplex algorithm the resulting tableau does give an optimal solution to the problem.
3. Perform the third iteration of the Simplex algorithm and hence determine the range of possible values for \(P\). You should state the row operations you use and make your method and working clear.
   (9)

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

7. A maximisation linear programming problem in \(x , y\) and \(z\) is to be solved using the Simplex method. The tableau after the 1st iteration is shown below.

1. State the column that contains the pivot value for the 1st iteration. You must give a reason for your answer.
2. By considering the equations represented in the above tableau, formulate the linear programming problem in \(x , y\) and \(z\) only. State the objective and list the constraints as inequalities with integer coefficients.
3. Taking the most negative number in the profit row to indicate the pivot column, perform the 2nd iteration of the Simplex algorithm, to obtain a new tableau, T . Make your method clear by stating the row operations you use.
4. 1. Explain, using T, how you know that an optimal solution to the original linear programming problem has not been found after the 2nd iteration.
   2. State the values of the basic variables after the 2nd iteration. A student attempts the 3rd iteration of the Simplex algorithm and obtains the tableau below.

      b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(\mathrm { S } _ { 3 }\)	Value
      z	0	0	1	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 4 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 43 } { 2 }\)
      \(x\)	1	0	0	\(\frac { 1 } { 4 }\)	\(\frac { 1 } { 8 }\)	\(- \frac { 1 } { 8 }\)	\(\frac { 57 } { 4 }\)
      \(y\)	0	1	0	\(- \frac { 1 } { 2 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 3 } { 4 }\)	\(\frac { 9 } { 2 }\)
      \(P\)	0	1	0	\(\frac { 5 } { 4 }\)	\(\frac { 1 } { 8 }\)	\(\frac { 7 } { 8 }\)	\(\frac { 361 } { 4 }\)

5. Explain how you know that the student's attempt at the 3rd iteration is not correct.

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

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

1. Explain why the Simplex algorithm cannot be used to solve this linear programming problem. The big-M method is to be used to solve this linear programming problem.
2. Define, in this context, what M represents. You must use correct mathematical language in your answer. The initial tableau for a big-M solution to the problem is shown below.

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(s _ { 2 }\)	\(s _ { 3 }\)	\(t _ { 1 }\)	Value
   \(s _ { 1 }\)	2	2	1	1	0	0	0	25
   \(s _ { 2 }\)	1	4	0	0	1	0	0	15
   \(t _ { 1 }\)	1	0	0	0	0	-1	1	3
   \(P\)	\(- ( 3 + M )\)	-2	-2	0	0	M	0	\(- 3 M\)

3. Explain clearly how the equation represented in the b.v. \(t _ { 1 }\) row was derived.
4. Show how the equation represented in the b.v. \(P\) row was derived. The tableau obtained from the first iteration of the big-M method is shown below.

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(s _ { 2 }\)	\(s _ { 3 }\)	\(t _ { 1 }\)	Value
   \(s _ { 1 }\)	0	2	1	1	0	2	-2	19
   \(s _ { 2 }\)	0	4	0	0	1	1	-1	12
   \(x\)	1	0	0	0	0	-1	1	3
   P	0	-2	-2	0	0	-3	\(3 +\) M	9

5. Solve the linear programming problem, starting from this second tableau. You must

4 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a minimax problem.

1. On the insert, complete the last two columns of the table.
2. State the minimax value and write down the minimax route.
3. Complete the diagram on the insert to show the network that is represented by the table.

6 Kai mixes hot drinks using coffee and steamed milk.
The amounts ( ml ) needed and profit ( \(\pounds\) ) for a standard sized cup of four different drinks are given in the table. The table also shows the amount of the ingredients available. Kai makes the equivalent of \(w\) standard sized americanos, \(x\) standard sized cappuccinos, \(y\) standard sized flat whites and \(z\) standard sized lattes. He can make different sized drinks so \(w , x , y , z\) need not be integers. Kai wants to find the maximum profit that he can make, assuming that the customers want to buy the drinks he has made.

1. What is the minimum value of X for it to be worthwhile for Kai to make cappuccinos? Kai makes no cappuccinos.
2. Use the simplex algorithm to solve Kai's problem. The grids in the Printed Answer Booklet should have at least enough rows and columns and there should be at least enough grids to show all the iterations needed. Only record the output from each iteration, not any intermediate stages.
   Interpret the solution and state the maximum profit that Kai can make.

6 Jack is making pizzas for a party. He can make three types of pizza:

• There is enough dough to make 30 pizzas.
• Type Z pizzas use vegan cheese. Jack only has enough vegan cheese to make 2 type Z pizzas.
• At least half the pizzas made must be suitable for vegetarians.
• Jack has enough onions to make 50 type X pizzas or 20 type Y pizzas or 20 type Z pizzas or some mixture of the three types.

Suppose that Jack makes \(x\) type X pizzas, \(y\) type Y pizzas and \(z\) type Z pizzas.

1. Formulate the constraints above in terms of the non-negative, integer valued variables \(x , y\) and \(z\), together with non-negative slack variables \(s , t , u\) and \(v\). Jack wants to find out the maximum total number of pizzas that he can make.
2. 1. Set up an initial simplex tableau for Jack's problem.
   2. Carry out one iteration of the simplex algorithm, choosing your pivot so that \(x\) becomes a basic variable. When Jack carries out the simplex algorithm his final tableau is:

      \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
      1	0	0	0	0	0	\(\frac { 3 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(28 \frac { 4 } { 7 }\)
      0	0	0	0	1	0	\(- \frac { 3 } { 7 }\)	\(- \frac { 2 } { 7 }\)	\(1 \frac { 3 } { 7 }\)
      0	0	0	1	0	1	0	0	2
      0	1	0	0	0	0	\(\frac { 5 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(14 \frac { 2 } { 7 }\)
      0	0	1	1	0	0	\(- \frac { 2 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(14 \frac { 2 } { 7 }\)

3. Use this final tableau to deduce how many pizzas of each type Jack should make. Jack knows that some of the guests are vegans. He decides to make 2 pizzas of type \(Z\).
4. 1. Plot the feasible region for \(x\) and \(y\).
   2. Complete the branch-and-bound formulation in the Printed Answer Booklet to find the number of pizzas of each type that Jack should make.
      You should branch on \(x\) first. \section*{END OF QUESTION PAPER}