7.07b Simplex iterations: pivot choice and row operations

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

1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), write down two inequalities involving \(x , y\) and \(z\) for this problem.
2. 1. The first pivot is chosen from the \(\boldsymbol { x }\)-column. Identify the pivot and perform one iteration of the Simplex method.
   2. Given that the optimal value of \(P\) has not been reached after this first iteration, find the possible values of \(k\).
3. Given that \(k = 10\) :
   1. perform one further iteration of the Simplex method;
   2. interpret the final tableau.

3

1. Given that \(k\) is a constant, complete the Simplex tableau below for the following linear programming problem. Maximise $$P = k x + 6 y + 5 z$$ subject to $$\begin{gathered} 2 x + y + 4 z \leqslant 11 \\ x + 3 y + 6 z \leqslant 18 \\ x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$
2. Use the Simplex method to perform one iteration of your tableau for part (a), choosing a value in the \(\boldsymbol { y }\)-column as pivot.
3. 1. In the case when \(k = 1\), explain why the maximum value of \(P\) has now been reached and write down this maximum value of \(P\).
   2. In the case when \(k = 3\), perform one further iteration and interpret your new tableau. \section*{Answer space for question 3}

      1. \(\boldsymbol { P }\)	\(\boldsymbol { x }\)	\(\boldsymbol { y }\)	\(\boldsymbol { Z }\)	\(s\)	\(\boldsymbol { t }\)	value
         1	\(- k\)	-6	-5	0	0	0
         0
         0

      2. \(\boldsymbol { P }\)	\(\boldsymbol { x }\)	\(\boldsymbol { y }\)	\(\boldsymbol { Z }\)	\(\boldsymbol { s }\)	\(\boldsymbol { t }\)	value

         \section*{Answer space for question 3}
      3. 1. \(\_\_\_\_\)

4

1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l c } \text { Maximise } & P = 3 x + 6 y + 2 z \\ \text { subject to } & x + 3 y + 2 z \leqslant 11 \\ & 3 x + 4 y + 2 z \leqslant 21 \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
2. The first pivot to be chosen is from the \(y\)-column. Perform one iteration of the Simplex method.
3. Perform one further iteration.
4. Interpret the tableau obtained in part (c) and state the values of your slack variables.

4

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

3
Maximise \(\quad P = 2 x - 3 y + 4 z\) subject to \(\quad x + 2 y + z \leqslant 20\) \(x - y + 3 z \leqslant 24\) \(3 x - 2 y + 2 z \leqslant 30\) and \(\quad x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).

1. Display the linear programming problem in a Simplex tableau.
2. 1. The first pivot to be chosen is from the \(z\)-column. Identify the pivot and explain why this particular value is chosen.
   2. Perform one iteration of the Simplex method.
   3. Perform one further iteration.
3. Interpret your final tableau and state the values of your slack variables.
   [0pt] [3 marks]

5. 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. Using the information in the tableau, write down
   1. the objective function,
   2. the three constraints as inequalities.
2. 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.
3. State the final values of the objective function and each variable.

5. The initial tableau for a linear programming problem in \(x , y\) and \(z\) is shown below. The objective function to be maximised is \(P = 4 x + 2 y + k z\), where \(k\) is a positive constant.

1. Using the information in the tableau, write down the three constraints as inequalities.
2. By increasing \(x\), perform one complete iteration of the simplex algorithm to obtain tableau \(T _ { 1 }\) and state the row operations you use.
3. Given that \(T _ { 1 }\) is not optimal, find an inequality for the value of \(k\).
4. Perform a second complete iteration of the simplex algorithm to obtain tableau \(T _ { 2 }\) and state the row operations you use.
5. Given that \(T _ { 2 }\) is optimal, find a second inequality for the value of \(k\).
6. State the final value of each variable and give an expression for the final value of \(P\) in terms of \(k\).
7. Hence find the range of possible values of \(P\).

5. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(P = 2 x + 3 y + z\) subject to \(\quad 2 y - 3 z \leqslant 30\) $$\begin{array} { r } - 3 x + y + z \leqslant 60 \\ x + 4 y - z \leqslant 80 \end{array}$$

1. Complete the initial tableau in the answer book for this linear programming problem.
   (3)
2. Taking the most negative number in the profit row to indicate the pivot column, 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.
   (5)
3. Write down the profit equation given by T and state the values of the slack variables given by T . The following tableau is obtained after further iterations.

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	0	2	-3	1	0	0	30
   \(s\)	0	13	-2	0	1	3	300
   \(x\)	1	4	-1	0	0	1	80
   \(P\)	0	5	-3	0	0	2	160

4. Explain why no optimal solution can be found by applying the simplex algorithm to the above tableau.

1. A linear programming problem is defined as follows:

$$\begin{array} { l l } \text { Maximise } & P = 3 x + 3 y + 4 z \\ \text { subject to } & x + 2 y + z \leq 30 \\ & 5 x + y + 3 z \leq 60 \\ \text { and } & x \geq 0 , y \geq 0 , z \geq 0 . \end{array}$$

1. Display the problem in a Simplex Tableau.
2. Starting with a pivot chosen from the \(z\)-column, perform one iteration of your tableau.
3. Write down the resulting values of \(x , y , z\) and \(P\) and state with a reason whether or not these values give an optimal solution.
   

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

1. Model this as a linear programming problem. Using the Simplex algorithm the following initial tableau is obtained:

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

2. Explain the purpose of the variables \(s , t\) and \(u\).
3. By increasing the value of \(y\) first, work out the next two complete tableaus.
4. Explain how you know that your final tableau gives an optimal solution and state this solution in practical terms.

3 The Simplex tableau below is optimal. 3

1. Deduce the range of values that \(k\) must satisfy.
   3
2. Write down the value of the variable \(s\) which corresponds to the optimal value of \(P\).

5 A student is solving the following linear programming problem. $$\begin{array} { l r } \text { Minimise } & Q = - 4 x - 3 y \\ \text { subject to } & x + y \leq 520 \\ & 2 x - 3 y \leq 570 \\ \text { and } & x \geq 0 , y \geq 0 \end{array}$$ 5

1. The student wants to use the simplex algorithm to solve the linear programming problem. They modify the linear programming problem by introducing the objective function $$P = 4 x + 3 y$$ and the slack variables \(r\) and \(s\) State one further modification that must be made to the linear programming problem so that it can be solved using the simplex algorithm. 5
2. (i) Complete the initial simplex tableau for the modified linear programming problem.
   [0pt] [2 marks]

   \(P\)	\(x\)	\(y\)	\(r\)	\(S\)	value

   5 (b) (ii) Hence, perform one iteration of the simplex algorithm.

   \(P\)	\(x\)	\(y\)	\(r\)	\(s\)	value

   5
3. The student performs one further iteration of the simplex algorithm, which results in the following correct simplex tableau.

   \(P\)	\(x\)	\(y\)	\(r\)	\(s\)	value
   1	0	0	\(\frac { 18 } { 5 }\)	\(\frac { 1 } { 5 }\)	1986
   0	0	1	\(\frac { 2 } { 5 }\)	\(- \frac { 1 } { 5 }\)	94
   0	1	0	\(\frac { 3 } { 5 }\)	\(\frac { 1 } { 5 }\)	426

   5 (c) (i) Explain how the student can tell that the optimal solution to the modified linear programming problem can be determined from the above simplex tableau.
   5 (c) (ii) Find the optimal solution of the original linear programming problem.

A tailor makes two types of garment, A and B. He has available 70 m² of cotton fabric and 90 m² of woollen fabric. Garment A requires 1 m² of cotton fabric and 3 m² of woollen fabric. Garment B requires 2 m² 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 $$x + 2y \leq 70,$$ $$3x + 2y \leq 90,$$ $$x \geq 0, y \geq 0.$$ [2 marks]

The tailor sells type A for £30 and type B for £40. All garments made are sold. The tailor wishes to maximise his total income.

1. Set up an initial Simplex tableau for this problem. [3 marks]
2. Solve the problem using the Simplex algorithm. [8 marks]

Figure 4 shows a graphical representation of the feasible region for this problem. \includegraphics{figure_4}

1. Obtain the coordinates of the points A, C and D. [4 marks]
2. Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4. [3 marks]

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

1. For this problem \(x \geq 0\), \(y \geq 0\), \(z \geq 0\). Write down the other two inequalities and the objective function. [3]
2. Solve this linear programming problem. [8]
3. State the final value of \(P\), the objective function, and of each of the variables. [3]

Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool. For each roll of carpet, the Lincoln requires 1 unit of black, 1 of green and 3 of red, the Norfolk requires 1 unit of black, 2 of green and 2 of red, and the Suffolk requires 2 units of black, 1 of green and 1 of red. There are up to 30 units of black, 40 units of green and 50 units of red available each day. Profits of £50, £80 and £60 are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit. Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x\), \(y\) and \(z\) respectively.

1. Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. [4]

This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.

1. Stating your row operations, show that after one complete iteration the tableau becomes

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(\frac{1}{2}\)	0	\(1\frac{1}{2}\)	1	\(-\frac{1}{2}\)	0	10
   \(y\)	\(\frac{1}{2}\)	1	\(\frac{1}{2}\)	0	\(\frac{1}{2}\)	0	20
   \(t\)	2	0	0	0	\(-1\)	1	10
   \(P\)	\(-10\)	0	\(-20\)	0	40	0	1600

   [4]
2. Explain the practical meaning of the value 10 in the top row. [2]
3. 1. Perform one further complete iteration of the Simplex algorithm.
   2. State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
   3. Interpret your current tableau, giving the value of each variable. [8]

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.

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value
\(r\)	2	0	4	1	0	80
\(s\)	1	4	2	0	1	160
\(P\)	\(-2\)	\(-8\)	\(-20\)	0	0	0

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. (5)
2. Write down the profit equation shown in tableau \(T\). (1)
3. State whether tableau \(T\) is optimal. Give a reason for your answer. (1)

(Total 7 marks)

Polly has a bird food stall at the local market. Each week she makes and sells three types of packs \(A\), \(B\) and \(C\). Pack \(A\) contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts. Pack \(B\) contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts. Pack \(C\) contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts. Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs. The profit made on each pack of \(A\), \(B\) and \(C\) sold is £3.50, £3.50 and £6.50 respectively. Polly sells every pack on her stall and wishes to maximise her profit, \(P\) pence. Let \(x\), \(y\) and \(z\) be the numbers of packs \(A\), \(B\) and \(C\) sold each week. An initial Simplex tableau for the above situation is

1. Explain the meaning of the variables \(r\), \(s\) and \(t\) in the context of this question. [2]
2. Perform one complete iteration of the Simplex algorithm to form a new tableau \(T\). Take the most negative number in the profit row to indicate the pivotal column. [5]
3. State the value of every variable as given by tableau \(T\). [3]
4. Write down the profit equation given by tableau \(T\). [2]
5. Use your profit equation to explain why tableau \(T\) is not optimal. [1]

Taking the most negative number in the profit row to indicate the pivotal column,

1. identify clearly the location of the next pivotal element. [2]

(Total 15 marks)

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

1. Write down the four equations represented in the initial tableau above. [4]
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. [9]
3. State the values of the objective function and each variable. [3]

The tableau below is the initial tableau for a linear programming problem in \(x\), \(y\) and \(z\). The objective is to maximise the profit, \(P\). $$\begin{array}{c|c|c|c|c|c|c|c} \text{basic variable} & x & y & z & r & s & t & \text{Value} \\ \hline r & 12 & 4 & 5 & 1 & 0 & 0 & 246 \\ \hline s & 9 & 6 & 3 & 0 & 1 & 0 & 153 \\ \hline t & 5 & 2 & -2 & 0 & 0 & 1 & 171 \\ \hline P & -2 & -4 & -3 & 0 & 0 & 0 & 0 \end{array}$$ Using the information in the tableau, write down

1. the objective function, [2]
2. the three constraints as inequalities with integer coefficients. [3]

Taking the most negative number in the profit row to indicate the pivot column at each stage,

1. solve this linear programming problem. Make your method clear by stating the row operations you use. [9]
2. State the final values of the objective function and each variable. [3]

One of the constraints is not at capacity.

1. Explain how it can be identified. [1]

(Total 18 marks)

Lucy is making party bags which she will sell to raise money for charity. She has three colours of party bag: red, yellow and blue. The bags contain balloons, sweets and toys. Lucy has a stock of 40 balloons, 80 sweets and 30 toys. The table shows how many balloons, sweets and toys are needed for one party bag of each colour.

Colour of party bag	Balloons	Sweets	Toys
Red	5	3	5
Yellow	4	7	2
Blue	6	6	3

Lucy will raise £1 for each bag that she sells, irrespective of its colour. She wants to calculate how many bags of each colour she should make to maximise the total amount raised for charity. Lucy has started to model the problem as an LP formulation. Maximise \quad \(P = x + y + z\), subject to \quad \(3x + 7y + 6z \leq 80\).

1. What does the variable \(x\) represent in Lucy's formulation? [1]
2. Explain why the constraint \(3x + 7y + 6z \leq 80\) must hold and write down another two similar constraints. [3]
3. What other constraints and restrictions apply to the values of \(x\), \(y\) and \(z\)? [1]
4. What assumption is needed for the objective to be valid? [1]
5. Represent the problem as an initial Simplex tableau. Do not carry out any iterations yet. [3]
6. Perform one iteration of the Simplex algorithm, choosing a pivot from the \(x\) column. Explain how the choice of pivot row was made and show how each row was calculated. [6]
7. Write down the values of \(x\), \(y\) and \(z\) from the first iteration of the Simplex algorithm and hence find the number of bags of each colour that Lucy should make according to this non-optimal tableau. [2]

In the optimal solution Lucy makes 10 bags.

1. Without carrying out further iterations of the Simplex algorithm, find a solution in which Lucy should make 10 bags. [1]

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.

	Processing	Blending	Packing	Profit (£100)
Morning blend	3	1	3	4
Afternoon blend	2	3	4	5
Evening blend	4	2	3	3

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

1. 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. [11]

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.

1. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available. [2]

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

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	7	10	10	1	0	0	3600
\(s\)	6	9	12	0	1	0	3600
\(t\)	2	3	4	0	0	1	2400
\(P\)	-35	-55	-60	0	0	0	0

1. Write down the four equations represented in the initial tableau above. [4]
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. [9]
3. State the values of the objective function and each variable. [3]

(Total 16 marks)

A linear programming problem is \begin{align} \text{Maximise } P &= 4x - y - 2z
\text{subject to } x + 5y + 3z &\leq 60
2x - 5y &\leq 80
2y + z &\leq 10
x \geq 0, y &\geq 0, z \geq 0 \end{align}

1. Use the simplex algorithm to solve the problem. [7]

In the case when \(z = 0\) the feasible region can be represented graphically. \includegraphics{figure_1} The vertices of the feasible region are \((0, 0)\), \((40, 0)\), \((46.67, 2.67)\), \((35, 5)\) and \((0, 5)\), where non-integer values are given to 2 decimal places. The linear programming problem is given the additional constraint that \(x\) and \(y\) are integers.

1. Use branch-and-bound, branching on \(x\) first, to show that the optimum solution with this additional constraint is \(x = 45, y = 2\). [7]

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

1. Show how the constraint on the number of red tulips leads to one of the rows of the tableau. [3]

The tableau that results after the first iteration is shown below.

1. Which cell was used as the pivot? [1]
2. Explain why row 2 and row 6 are the same. [1]
3. 1. Read off the values of \(x\), \(y\) and \(z\) after the first iteration. [1]
   2. Interpret this solution in terms of the original problem. [2]
4. 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. [3]

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.

1. 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. [2]