The Simplex Algorithm

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.

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.

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.

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.

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

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.

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

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

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

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.

7. A publisher plans to produce three versions of the same book: a paperback, a hardcover, and a deluxe edition.

• Each paperback takes 4 minutes to print and 1 minute to bind
• Each hardcover takes 8 minutes to print and 5 minutes to bind
• Each deluxe edition takes 15 minutes to print and 12 minutes to bind

The printing machine is available for at most 150 hours and the binding machine must be used for at least 60 hours. The publisher decides to produce

• at least 1600 books in total
• at least three times as many paperbacks as hardcovers

The profit on each paperback sold is \(\pounds 8\), the profit on each hardcover sold is \(\pounds 20\) and the profit on each deluxe edition sold is \(\pounds 40\) Let \(x , y\) and \(z\) represent the number of paperbacks, hardcovers and deluxe editions produced.

1. Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. The publisher decides to solve this linear programming problem by using the two-stage simplex method.
2. Set up an initial tableau for solving this problem using the two-stage simplex method. As part of your solution, you must show how
   • the constraints have been made into equations by using slack variables, exactly two surplus variables and exactly two artificial variables
   • the rows for the two objective functions are formed
   The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.

   b.v.	\(x\)	\(y\)	\(z\)	\(\mathrm { S } _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(\mathrm { S } _ { 1 }\)	0	0	0	1	1	3	0	-1	-3	600
   \(z\)	0	\(\frac { 4 } { 11 }\)	1	0	\(- \frac { 1 } { 11 }\)	\(\frac { 1 } { 11 }\)	0	\(\frac { 1 } { 11 }\)	\(- \frac { 1 } { 11 }\)	\(\frac { 2000 } { 11 }\)
   \(x\)	1	\(\frac { 7 } { 11 }\)	0	0	\(\frac { 1 } { 11 }\)	\(- \frac { 12 } { 11 }\)	0	\(- \frac { 1 } { 11 }\)	\(\frac { 12 } { 11 }\)	\(\frac { 15600 } { 11 }\)
   \(s _ { 4 }\)	0	\(\frac { 40 } { 11 }\)	0	0	\(\frac { 1 } { 11 }\)	\(- \frac { 12 } { 11 }\)	1	\(- \frac { 1 } { 11 }\)	\(\frac { 12 } { 11 }\)	\(\frac { 15600 } { 11 }\)
   \(P\)	0	\(- \frac { 4 } { 11 }\)	0	0	\(- \frac { 32 } { 11 }\)	\(- \frac { 56 } { 11 }\)	0	\(\frac { 32 } { 11 }\)	\(\frac { 56 } { 11 }\)	\(\frac { 204800 } { 11 }\)
   I	0	0	0	0	0	0	0	1	1	0

3. 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. Make your method clear by stating the row operations you use. After three iterations of the second stage of the two-stage simplex method, the following tableau is obtained.

   b.v.	\(x\)	\(y\)	\(z\)	\(\mathrm { S } _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	Value
   \(s _ { 2 }\)	0	0	0	1	1	3	0	600
   \(z\)	0	0	1	\(\frac { 1 } { 10 }\)	0	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 10 }\)	100
   \(x\)	1	0	0	\(- \frac { 3 } { 40 }\)	0	\(- \frac { 9 } { 8 }\)	\(- \frac { 7 } { 40 }\)	1125
   \(y\)	0	1	0	\(- \frac { 1 } { 40 }\)	0	\(- \frac { 3 } { 8 }\)	\(\frac { 11 } { 40 }\)	375
   \(P\)	0	0	0	\(\frac { 29 } { 10 }\)	0	\(\frac { 7 } { 2 }\)	\(\frac { 1 } { 10 }\)	20500

   Given that the publisher produces the optimal number of each version of the book,
4. 1. state the maximum profit the publisher can earn,
   2. find the number of hours the binding machine will be used.
5. Give a reason why the publisher may not earn the profit stated in (d)(i).

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]

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 in \(x , y\) and \(z\) is to be solved using the big-M method. The initial tableau is shown below.

1. Using the information in the above tableau, formulate the linear programming problem. You should
   \section*{Please turn over for Question 5}

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?

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]

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.

4 A small alpine hotel is planned. Permission has been obtained for no more than 60 beds, and these can be accommodated in rooms containing one, two or four beds. The total floor areas needed are \(15 \mathrm {~m} ^ { 2 }\) for a one-bed room, \(25 \mathrm {~m} ^ { 2 }\) for a two-bed room and \(40 \mathrm {~m} ^ { 2 }\) for a four-bed room. The total floor area of the bedrooms must not exceed \(700 \mathrm {~m} ^ { 2 }\). Marginal profit contributions per annum, in thousands of euros, are estimated to be 5 for a one-bed room, 9 for a two-bed room and 15 for a four-bed room.

1. Formulate a linear programming problem to find the mix of rooms which will maximise the profit contribution within the two constraints.
2. Use the simplex algorithm to solve the problem, and interpret your solution. It is decided that, for marketing reasons, at least 5 one-bed rooms must be provided.
3. Solve this modified problem using either the two-stage simplex method or the big-M method. You may wish to adapt your final tableau from part (ii) to produce an initial tableau, but you are not required to do so.
4. The simplex solution to the revised problem is to provide 5 one-bed rooms, 15 two-bed rooms and 6.25 four-bed rooms, giving a profit contribution of \(€ 253750\). Interpret this solution in terms of the real world problem.
5. Compare the following solution to your answer to part (iv): 8 one-bed rooms, 12 two-bed rooms and 7 four-bed rooms. Explain your findings.

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]

8. A two-person zero-sum game is represented by the pay-off matrix for player A shown below. \section*{Player B} Player A

1. Verify that there is no stable solution to this game.
2. Explain why player A should never play option T. You must make your reasoning clear. Player A intends to make a random choice between options \(\mathrm { Q } , \mathrm { R }\) and S , choosing option \(Q\) with probability \(p _ { 1 }\), option \(R\) with probability \(p _ { 2 }\) and option \(S\) with probability \(p _ { 3 }\) Player A wants to calculate the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm.
3. 1. Formulate the game as a linear programming problem for player A. You should write the constraints as equations.
   2. Write down an initial Simplex tableau for this linear programming problem, making your variables clear. The linear programming problem is solved using the Simplex algorithm. The optimal value of \(p _ { 1 }\) is \(\frac { 6 } { 11 }\) and the optimal value of \(p _ { 2 }\) is 0
4. Find the best strategy for player B, defining any variables you use.

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

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.