Big-M method setup

6. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(\quad P = 2 x + 2 y - z\) subject to \(\quad 3 x + y + 2 z \leqslant 30\) $$\begin{aligned} x - y + z & \geqslant 8 \\ 4 y + 2 z & \geqslant 15 \\ x , y , z & \geqslant 0 \end{aligned}$$

1. Explain why the Simplex algorithm cannot be used to solve this linear programming problem.
2. Set up the initial tableau for solving this linear programming problem using the big-M method. After a first iteration of the big-M method, the tableau is

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(s _ { 1 }\)	3	0	1.5	1	0	0.25	0	-0.25	26.25
   \(a _ { 1 }\)	1	0	1.5	0	-1	-0.25	1	0.25	11.75
   \(y\)	0	1	0.5	0	0	-0.25	0	0.25	3.75
   \(P\)	\(- ( 2 + M )\)	0	2-1.5M	0	M	\(- 0.5 + 0.25 M\)	0	\(0.5 + 0.75 M\)	7.5-11.75M

3. State the value of each variable after the first iteration.
4. Explain why the solution given by the first iteration is not feasible. Taking the most negative entry in the profit row to indicate the pivot column,
5. obtain the most efficient pivot for a second iteration. You must give reasons for your answer.

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}

5. Two friends, Anaira and Tommi, play a game involving two positive numbers \(x\) and \(y\) Anaira gives Tommi the following clues to see if he can correctly determine the value of \(x\) and the value of \(y\)

• \(x\) is greater than \(y\) and the difference between the two is at least 100
• \(x\) is at most 5 times as large as \(y\)
• the sum of \(2 x\) and \(3 y\) is at least 350
• the sum of \(x\) and \(y\) is as small as possible

Tommi decides to solve this problem by using the big-M method.

1. Set up an initial tableau for solving this problem using the big-M method. As part of your solution, you must show
   • how the constraints were made into equations using one slack variable, exactly two surplus variables and exactly two artificial variables
   • how the objective function was formed
   The big-M method is applied until the tableau containing the optimal solution to the problem is found. One row of this final tableau is as follows.

   b.v.	\(x\)	\(y\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(\mathrm { S } _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(x\)	1	0	\(- \frac { 3 } { 5 }\)	0	\(- \frac { 1 } { 5 }\)	\(\frac { 3 } { 5 }\)	\(\frac { 1 } { 5 }\)	130

2. 1. State the value of \(x\)
   2. Hence deduce the value of \(y\), making your reasoning clear.

7. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(P = 3 x + 2 y + 2 z\) subject to $$\begin{aligned} & 2 x + 2 y + z \leqslant 25 \\ & x + 4 y \leqslant 15 \\ & x \geqslant 3 \end{aligned}$$

1. Explain why the Simplex algorithm cannot be used to solve this linear programming problem. The big-M method is to be used to solve this linear programming problem.
2. Define, in this context, what M represents. You must use correct mathematical language in your answer. The initial tableau for a big-M solution to the problem is shown below.

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(s _ { 2 }\)	\(s _ { 3 }\)	\(t _ { 1 }\)	Value
   \(s _ { 1 }\)	2	2	1	1	0	0	0	25
   \(s _ { 2 }\)	1	4	0	0	1	0	0	15
   \(t _ { 1 }\)	1	0	0	0	0	-1	1	3
   \(P\)	\(- ( 3 + M )\)	-2	-2	0	0	M	0	\(- 3 M\)

3. Explain clearly how the equation represented in the b.v. \(t _ { 1 }\) row was derived.
4. Show how the equation represented in the b.v. \(P\) row was derived. The tableau obtained from the first iteration of the big-M method is shown below.

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(s _ { 2 }\)	\(s _ { 3 }\)	\(t _ { 1 }\)	Value
   \(s _ { 1 }\)	0	2	1	1	0	2	-2	19
   \(s _ { 2 }\)	0	4	0	0	1	1	-1	12
   \(x\)	1	0	0	0	0	-1	1	3
   P	0	-2	-2	0	0	-3	\(3 +\) M	9

5. Solve the linear programming problem, starting from this second tableau. You must