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

6 Consider the linear programming problem:

1. Using slack variables, \(s\) and \(t\), express the non-trivial constraints as two equations.
2. Represent the problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm.
3. Use the Simplex algorithm to find the values of \(x , y\) and \(z\) for which \(P\) is maximised, subject to the constraints above.
4. The value 15 in the first constraint is increased to a new value \(k\). As a result the pivot for the first iteration changes. Show what effect this has on the final value of \(y\).

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

1. Represent the problem as an initial Simplex tableau.
2. Explain why it is not possible to pivot on the \(z\) column of this tableau. 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 one iteration of the Simplex algorithm. Write down the values of \(x , y\) and \(z\) after this iteration.
4. Explain why \(P\) has no finite maximum. The coefficient of \(z\) in the objective is changed from + 4 to - 40 .
5. Describe the changes that this will cause to the initial Simplex tableau and the tableau that results after one iteration. What is the maximum value of \(P\) in this case? Now consider this linear programming problem: $$\begin{array} { l l } \text { maximise } & Q = 3 x - 5 y + 7 z , \\ \text { subject to } & x + 2 y - 3 z \leqslant 12 , \\ & 2 x - 7 y + 10 z \leqslant 40 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$ Do not use the Simplex algorithm for these parts.
6. By adding the two constraints, show that \(Q\) has a finite maximum.
7. There is an optimal point with \(y = 0\). By substituting \(y = 0\) in the two constraints, calculate the values of \(x\) and \(z\) that maximise \(Q\) when \(y = 0\).

6 Consider the following LP problem.

1. Since \(a \leqslant 6\) it follows that \(6 - a \geqslant 0\), and similarly for \(b\) and \(c\). Let \(6 - a = x\) (so that \(a\) is replaced by \(6 - x ) , 8 - b = y\) and \(10 - c = z\) to show that the problem can be expressed as $$\begin{array} { l l } \text { Maximise } & 2 x - 4 y + 5 z , \\ \text { subject to } & 3 x + 2 y - z \leqslant 14 , \\ & 2 x - 4 z \leqslant 7 , \\ & - 4 x + y \leqslant 4 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
2. Represent the problem as an initial Simplex tableau. Perform two iterations of the Simplex algorithm, showing how each row was obtained. Hence write down the values of \(a , b\) and \(c\) after two iterations. Find the value of the objective for the original problem at this stage.
   [0pt] [10]

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 Consider the following LP problem.

1. Represent the problem as an initial Simplex tableau. Explain why the pivot can only be chosen from the \(x\) column.
2. Perform one iteration of the Simplex algorithm. Show how each row was obtained and write down the values of \(w , x , y , z\) and \(P\) at this stage.
3. Perform a second iteration of the Simplex algorithm. Write down the values of \(w , x , y , z\) and \(P\) at this stage and explain how you can tell from this tableau that \(P\) can be increased without limit. How could you have known from the LP formulation above that \(P\) could be increased without limit?

4 Consider the following linear programming problem. $$\begin{array} { l r } \text { Maximise } & P = - 5 x - 6 y + 4 z , \\ \text { subject to } & 3 x - 4 y + z \leqslant 12 , \\ & 6 x + 2 z \leqslant 20 , \\ & - 10 x - 5 y + 5 z \leqslant 30 , \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$

1. Use slack variables \(s , t\) and \(u\) to rewrite the first three constraints as equations. What restrictions are there on the values of \(s , t\) and \(u\) ?
2. Represent the problem as an initial Simplex tableau.
3. Show why the pivot for the first iteration of the Simplex algorithm must be the coefficient of \(z\) in the third constraint.
4. Perform one iteration of the Simplex algorithm, showing how the elements of the pivot row were calculated and how this was used to calculate the other rows.
5. Perform a second iteration of the Simplex algorithm and record the values of \(x , y , z\) and \(P\) at the end of this iteration.
6. Write down the values of \(s , t\) and \(u\) from your final tableau and explain what they mean in terms of the original constraints.

3 A problem to maximise \(P\) as a function of \(x , y\) and \(z\) is represented by the initial Simplex tableau below.

1. Write down \(P\) as a function of \(x , y\) and \(z\).
2. Write down the constraints as inequalities involving \(x , y\) and \(z\).
3. Carry out one iteration of the Simplex algorithm. After a second iteration of the Simplex algorithm the tableau is as given below.

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
   1	0	7.25	0	0.6	1.75	211
   0	1	0.75	0	0	0.25	25
   0	0	0.75	1	- 0.2	0.25	13

4. Explain how you know that the optimal solution has been achieved.
5. Write down the values of \(x , y\) and \(z\) that maximise \(P\). Write down the optimal value of \(P\).

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

1. 1. What name is given to the variables \(s , t\) and \(u\) ?
   2. Write down an equation involving \(x , y , z\) and \(s\) 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, stating the values of \(P , x , y\) and \(z\).

4 The Simplex method is to be used to maximise \(P = 3 x + 2 y + z\) subject to the constraints $$\begin{aligned} - x + y + z & \leqslant 4 \\ 2 x + y + 4 z & \leqslant 10 \\ 4 x + 2 y + 3 z & \leqslant 21 \end{aligned}$$ The initial Simplex tableau is given below.

1. 1. The first pivot is to be chosen from the \(x\)-column. Identify the pivot and explain why this particular value is chosen.
   2. Perform one iteration of the Simplex method and explain how you know that the optimal value has not been reached.
2. 1. Perform one further iteration.
   2. Interpret the final tableau and write down the initial inequality that still has slack.
      \includegraphics[max width=\textwidth, alt={}]{172c5c92-4254-4593-b741-1caa83a1e833-11_2486_1714_221_153}

4 A linear programming problem consists of maximising an objective function \(P\) involving three variables, \(x , y\) and \(z\), subject to constraints given by three inequalities other than \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\). Slack variables \(s , t\) and \(u\) are introduced and the Simplex method is used to solve the problem. One iteration of the method leads to the following tableau.

1. 1. State the column from which the pivot for the next iteration should be chosen. Identify this pivot and explain the reason for your choice.
   2. Perform the next iteration of the Simplex method.
2. 1. Explain why you know that the maximum value of \(P\) has been achieved.
   2. State how many of the three original inequalities still have slack.
3. 1. State the maximum value of \(P\) and the values of \(x , y\) and \(z\) that produce this maximum value.
   2. The objective function for this problem is \(P = k x - 2 y + 3 z\), where \(k\) is a constant. Find the value of \(k\).
      
      \includegraphics[max width=\textwidth, alt={}]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-11_2486_1714_221_153}

5

1. Display the following linear programming problem in a Simplex tableau.
   Maximise \(\quad P = x - 2 y + 3 z\) subject to $$\begin{array} { r } x + y + z \leqslant 16 \\ x - 2 y + 2 z \leqslant 17 \\ 2 x - y + 2 z \leqslant 19 \end{array}$$ and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).
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 the tableau that you obtained in part (c)(i) and state the values of your slack variables.

3

1. Given that \(k\) is a constant, display the following linear programming problem in a Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 6 x + 5 y + 3 z \\ \text { subject to } & x + 2 y + k z \leqslant 8 \\ & 2 x + 10 y + z \leqslant 17 \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
2. 1. Use the Simplex method to perform one iteration of your tableau for part (a), choosing a value in the \(x\)-column as pivot.
   2. Given that the maximum value of \(P\) has not been achieved after this first iteration, find the range of possible values of \(k\).
3. In the case where \(k = - 1\), perform one further iteration and interpret your final tableau.
   
   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-07_2484_1707_223_155}

4 A linear programming problem involving variables \(x , y\) and \(z\) is to be solved. The objective function to be maximised is \(P = 2 x + 6 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 , z \geqslant 0\), write down three inequalities involving \(x , y\) and \(z\) for this problem.
2. 1. By choosing the first pivot from the \(\boldsymbol { y }\)-column, perform one iteration of the Simplex method.
   2. Given that the optimal value has not been reached, find the possible values of \(k\).
3. In the case when \(k = 20\) :
   1. perform one further iteration;
   2. interpret the final tableau and state the values of the slack variables.

6

1. Display the following linear programming problem in a Simplex tableau.
   Maximise \(\quad P = 4 x + 3 y + z\) subject to $$\begin{aligned} & 2 x + y + z \leqslant 25 \\ & x + 2 y + z \leqslant 40 \\ & x + y + 2 z \leqslant 30 \end{aligned}$$ and \(x \geqslant 0 , \quad y \geqslant 0 , \quad z \geqslant 0\).
2. The first pivot to be chosen is from the \(x\)-column. 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.

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

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

8. 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.
2. Solve this linear programming problem. You may not need to use all of these tableaux.

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value
   \(P\)

3. State the final value of \(P\), the objective function, and of each of the variables.

8. 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. You may not need to use all of these tableaux.

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	S	\(t\)	Value	Row operations
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations
   \includegraphics[max width=\textwidth, alt={}]{151644c7-edef-448e-ac2a-b374d79f264c-4_86_102_967_374}
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(S\)	\(t\)	Value	Row operations
   \(P\)

5. While solving a maximising linear programming problem, the following tableau was obtained.

1. Write down the values of \(\mathrm { x } , \mathrm { y }\) and z as indicated by this tableau.
2. Write down the profit equation from the tableau.

6. 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. Write down the profit equation represented in the initial tableau.
   (1)
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 value of the objective function and of each variable.
   (3)

3. 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. Write down the profit equation represented in the tableau.
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 value of the objective function and of each variable.

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.

8. A company makes industrial robots. They can make up to four robots in any one month, but if they make more than three they will have to hire additional labour at a cost of \(\pounds 400\) per month.
They can store up to two robots at a cost of \(\pounds 150\) per robot per month.
The overhead costs are \(\pounds 300\) in any month in which work is done.
Robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock after the April delivery. The order book for robots is Use dynamic programming to determine the production schedule which minimises the costs, showing your working in the table provided in the answer book.
(Total 12 marks)

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.