Two-stage Simplex method

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.

7. A maximisation linear programming problem in \(x , y\) and \(z\) is to be solved using the two-stage simplex method. The partially completed initial tableau is shown below.

1. Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities.
2. Complete the bottom row of Table 1 in the answer book. You should make your method and working clear. The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.

   Basic variable	\(x\)	\(y\)	\(z\)	\(S _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(S _ { 1 }\)	0	\(\frac { 5 } { 6 }\)	0	1	\(\frac { 7 } { 12 }\)	\(\frac { 3 } { 4 }\)	\(- \frac { 7 } { 12 }\)	\(- \frac { 3 } { 4 }\)	\(\frac { 147 } { 4 }\)
   \(x\)	1	\(\frac { 2 } { 3 }\)	0	0	\(- \frac { 1 } { 3 }\)	0	\(\frac { 1 } { 3 }\)	0	3
   \(z\)	0	\(\frac { 1 } { 6 }\)	1	0	\(- \frac { 1 } { 12 }\)	\(- \frac { 1 } { 4 }\)	\(\frac { 1 } { 12 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 7 } { 4 }\)
   \(P\)	0	\(\frac { 5 } { 6 }\)	0	0	\(- \frac { 11 } { 12 }\)	\(- \frac { 3 } { 4 }\)	\(\frac { 11 } { 12 }\)	\(\frac { 3 } { 4 }\)	\(\frac { 45 } { 4 }\)
   A	0	0	0	0	0	0	1	1	0

3. 1. Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem.
   2. Write down the basic feasible solution for the second stage.
4. 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, \(T\). Make your method clear by stating the row operations you use.
5. 1. Explain, using \(T\), whether or not an optimal solution to the original linear programming problem has been found.
   2. Write down the value of the objective function.
   3. State the values of the basic variables.