Perform one Simplex iteration

4

1. Represent the linear programming problem below by an initial Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 5 x - 4 y - 3 z , \\ \text { subject to } & 2 x - 3 y + 4 z \leqslant 10 , \\ & 6 x + 5 y + 4 z \leqslant 60 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
2. Perform one iteration of the Simplex algorithm and write down the values of \(x , y , z\) and \(P\) that result from this iteration.

5 Consider the linear programming problem:

1. Using slack variables, \(s \geqslant 0\) and \(t \geqslant 0\), express the two non-trivial constraints as equations.
2. Represent the problem as an initial Simplex tableau.
3. Explain why the pivot element must be chosen from the \(x\)-column and show the calculations that are used to choose the pivot.
4. Perform one iteration of the Simplex algorithm. Show how you obtained each row of your tableau and write down the values of \(x , y , z\) and \(P\) that result from this iteration. State whether or not this is the maximum feasible value of \(P\) and describe how you know this from the values in the tableau.

4 Consider the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = 3 x - 5 y , \\ \text { subject to } & x + 5 y \leqslant 12 , \\ & x - 5 y \leqslant 10 , \\ & 3 x + 10 y \leqslant 45 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 . \end{array}$$

1. Represent the problem as an initial Simplex tableau.
2. Identify the entry on which to pivot for the first iteration of the Simplex algorithm. Explain how you made your choice of column and row.
3. Perform oneiteration of the Simplex algorithm. Write down the values of \(\mathrm { x } , \mathrm { y }\) and P after this iteration.
4. Show that \(\mathrm { x } = 11 , \mathrm { y } = 0.2\) is a feasible solution and that it gives a bigger value of P than that in part (iii).

4. The tableau below is the initial tableau for a maximising linear programming problem in \(x , y\) and \(z\) which is to be solved.

1. Starting by increasing \(y\), perform one complete iteration of the simplex algorithm, to obtain tableau T. State the row operations you use.
2. Write down the profit equation given by tableau T .
3. Use the profit equation from part (b) to explain why tableau T is optimal.

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

1. Starting by increasing \(y\), perform one complete iteration of the Simplex algorithm, to obtain a new tableau, T. State the row operations you use.
2. Write down the profit equation given by T .
3. Use the profit equation from part (b) to explain why T is optimal.

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

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

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

1. Perform one iteration of the Simplex algorithm to obtain a new tableau, \(T\). State the row operations you use.
   (5)
2. Write down the profit equation given by \(T\) and state the current values of the slack variables.

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

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

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

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

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:

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