7.07b Simplex iterations: pivot choice and row operations

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:

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.

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)

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

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

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

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

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

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

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

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

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

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.

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}

7. A tailor makes two types of garment, \(A\) and \(B\). He has available \(70 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(90 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(A\) requires \(1 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(3 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(B\) requires \(2 \mathrm {~m} ^ { 2 }\) of each fabric. The tailor makes \(x\) garments of type \(A\) and \(y\) garments of type \(B\).

1. Explain why this can be modelled by the inequalities $$\begin{aligned} & x + 2 y \leq 70 \\ & 3 x + 2 y \leq 90 \\ & x \geq 0 , y \geq 0 \end{aligned}$$ (2 marks)
   The tailor sells type \(A\) for \(\pounds 30\) and type \(B\) for \(\pounds 40\). All garments made are sold. The tailor wishes to maximise his total income.
2. Set up an initial Simplex tableau for this problem.
   (3 marks)
3. Solve the problem using the Simplex algorithm.
   (8 marks) Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-004_452_828_995_356} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Obtain the coordinates of the points A, \(C\) and \(D\).
5. Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4.
   (3 marks) Answer Book (AB12)
   Graph Paper (ASG2) Items included with question papers Answer booklet

7. A tailor makes two types of garment, \(A\) and \(B\). He has available \(70 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(90 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(A\) requires \(1 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(3 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(B\) requires \(2 \mathrm {~m} ^ { 2 }\) of each fabric. The tailor makes \(x\) garments of type \(A\) and \(y\) garments of type \(B\).

1. Explain why this can be modelled by the inequalities $$\begin{aligned} & x + 2 y \leq 70 \\ & 3 x + 2 y \leq 90 \\ & x \geq 0 , y \geq 0 \end{aligned}$$ The tailor sells type \(A\) for \(\pounds 30\) and type \(B\) for \(\pounds 40\). All garments made are sold. The tailor wishes to maximise his total income.
2. Set up an initial Simplex tableau for this problem.
3. Solve the problem using the Simplex algorithm. Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-008_686_1277_1319_453} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Obtain the coordinates of the points A, \(C\) and \(D\).
5. Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4. 6689 Decision Mathematics 1 (New Syllabus) Order of selecting edges
   Final tree
   (b) Minimum total length of cable
   Question 4 to be answered on this page
   (a) \(A\)
   • Monday (M) \(B\) ◯
   • Tuesday (Tu) \(C \odot\)
   • Wednesday (W) \(D\) ◯
   • Thursday (Th) \(E\) -
   • Friday (F)
     (b)
     (c)
   Question 5 to be answered on this page
   Key
   (a) Early
   Time
   Late
   Time \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_433_227_534_201} \(F ( 3 )\) \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_117_222_1016_992}
   H(4) K(6)
   (b) Critical activities
   Length of critical path \(\_\_\_\_\) (c) \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_492_1604_1925_266} Question 6 to be answered on pages 4 and 5
   (a)
   1. SAET \(\_\_\_\_\)
   2. SBDT \(\_\_\_\_\)
   3. SCFT \(\_\_\_\_\)
   
   (b) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-012_691_1307_893_384} \captionsetup{labelformat=empty} \caption{Diagram 1}
   \end{figure} (c) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_699_1314_167_382} \captionsetup{labelformat=empty} \caption{Diagram 2}
   \end{figure} Flow augmenting routes
   (d) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_693_1314_1368_382} \captionsetup{labelformat=empty} \caption{Diagram 3}
   \end{figure} (e) \(\_\_\_\_\)

5

1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l c } \text { Maximise } & P = 3 x + 2 y + 4 z \\ \text { subject to } & x + 4 y + 2 z \leqslant 8 \\ & 2 x + 7 y + 3 z \leqslant 21 \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
2. Use the Simplex method to perform one iteration of your tableau for part (a), choosing a value in the \(z\)-column as pivot.
3. 1. Perform one further iteration.
   2. State whether or not this is the optimal solution, and give a reason for your answer.

3

1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 5 x + 8 y + 7 z \\ \text { subject to } & 3 x + 2 y + z \leqslant 12 \\ & 2 x + 4 y + 5 z \leqslant 16 \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
2. The Simplex method is to be used by initially choosing a value in the \(y\)-column as a pivot.
   1. Explain why the initial pivot is 4 .
   2. Perform two iterations of your tableau from part (a) using the Simplex method.
   3. State the values of \(P , x , y\) and \(z\) after your second iteration.
   4. State, giving a reason, whether the maximum value of \(P\) has been achieved.

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

1. In addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), write down three inequalities involving \(x , y\) and \(z\) for this problem.
2. 1. By choosing the first pivot from the \(z\)-column, perform one iteration of the Simplex method.
   2. Explain how you know that the optimal value has not been reached.
3. 1. Perform one further iteration.
   2. Interpret the final tableau and state the values of the slack variables.

3

1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 4 x - 5 y + 6 z \\ \text { subject to } & 6 x + 7 y - 4 z \leqslant 30 \\ & 2 x + 4 y - 5 z \leqslant 8 \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
2. The Simplex method is to be used to solve this problem.
   1. Explain why it is not possible to choose a pivot from the \(z\)-column initially.
   2. Identify the initial pivot and explain why this particular element should be chosen.
   3. Perform one iteration using your initial tableau from part (a).
   4. State the values of \(x , y\) and \(z\) after this first iteration.
   5. Without performing any further iterations, explain why \(P\) has no finite maximum value.
3. Using the same inequalities as in part (a), the problem is modified to $$\text { Maximise } \quad Q = 4 x - 5 y - 20 z$$
   1. Write down a modified initial tableau and the revised tableau after one iteration.
   2. Hence find the maximum value of \(Q\).

5 A linear programming problem involving variables \(x\) and \(y\) is to be solved. The objective function to be maximised is \(P = 4 x + 9 y\). The initial Simplex tableau is given below.

1. Write down the three inequalities in \(x\) and \(y\) represented by this tableau.
2. The Simplex method is to be used to solve this linear programming problem by initially choosing a value in the \(x\)-column as the pivot.
   1. Explain why the initial pivot has value 1.
   2. Perform two iterations using the Simplex method.
   3. Comment on how you know that the optimum solution has been achieved and state your final values of \(P , x\) and \(y\).

4 A linear programming problem involving variables \(x\) and \(y\) is to be solved. The objective function to be maximised is \(P = 3 x + 5 y\). The initial Simplex tableau is given below.

1. In addition to \(x \geqslant 0 , y \geqslant 0\), write down three inequalities involving \(x\) and \(y\) for this problem.
2. 1. By choosing the first pivot from the \(\boldsymbol { y }\)-column, perform one iteration of the Simplex method.
   2. Explain how you know that the optimal value has not been reached.
3. 1. Perform one further iteration.
   2. Interpret the final tableau and state the values of the slack variables.

4 A linear programming problem consists of maximising an objective function \(P\) involving three variables \(x , y\) and \(z\). Slack variables \(s , t , u\) and \(v\) are introduced and the Simplex method is used to solve the problem. Several iterations of the method lead to the following tableau.

1. 1. The pivot for the next iteration is chosen from the \(\boldsymbol { y }\)-column. State which value should be chosen and explain the reason for your choice.
   2. Perform the next iteration of the Simplex method.
2. Explain why your new tableau solves the original problem.
3. State the maximum value of \(P\) and the values of \(x , y\) and \(z\) that produce this maximum value.
4. State the values of the slack variables at the optimum point. Hence determine how many of the original inequalities still have some slack when the optimum is reached.