Complete Simplex solution

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

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.

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}

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.

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.

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. 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 \(\pounds 3.50 , \pounds 3.50\) and \(\pounds 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. 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.
3. State the value of every variable as given by tableau \(T\).
4. Write down the profit equation given by tableau \(T\).
5. Use your profit equation to explain why tableau \(T\) is not optimal. Taking the most negative number in the profit row to indicate the pivotal column,
6. identify clearly the location of the next pivotal element.

8. 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\). Using the information in the tableau, write down

1. the objective function,
2. the three constraints as inequalities with integer coefficients. Taking the most negative number in the profit row to indicate the pivot column at each stage,
3. solve this linear programming problem. Make your method clear by stating the row operations you use.

   b.v.	x	y	z	r	s	t	Value	Row operations

   b.v.	x	y	z	r	s	t	Value	Row operations

   b.v.	x	y	z	r	s	t	Value	Row operations

   b.v.	x	y	z	r	s	t	Value	Row operations

4. State the final values of the objective function and each variable.
5. One of the constraints is not at capacity. Explain how it can be identified.

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

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.

5. In solving a three-variable maximising linear programming problem, the following tableau was obtained after the first iteration.

1. State which variable was increased first, giving a reason for your answer.
2. 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 the final values of each variable.

3. 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, solve this linear programming problem. Make your method clear by stating the row operations you use.
2. State the final values of the objective function and each variable.

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

1. Write down the four equations represented in the initial tableau.
2. 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 that you use.
3. State whether or not your last tableau is optimal. Give a reason for your answer.

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.

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.

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)

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.

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

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.