7.07d Simplex terminology: basic feasible solution, basic/non-basic variable

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}

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

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.

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.

8. A factory can process up to five units of carrots each month. Each unit can be sold fresh or frozen or canned.
The profits, in \(\pounds 100\) s, for the number of units sold, are shown in the table.
The total monthly profit is to be maximised. Use dynamic programming to determine how many of the five units should be sold fresh, frozen and canned in order to maximise the monthly profit. State the maximum monthly profit.
(Total 12 marks)

7. Nigel has a business renting out his fleet of bicycles to tourists. At the start of each year Nigel must decide on one of two actions:

• Keep his fleet of bicycles, incurring maintenance costs.
• Replace his fleet of bicycles.

The cost of keeping the fleet of bicycles, the cost of replacing the fleet of bicycles and the annual income are dependent on the age of the fleet of bicycles.
Table 1 shows these amounts, in \(\pounds 1000\) s. \begin{table}[h] \end{table} Nigel has a new fleet of bicycles now and wishes to maximise his total profit over the next four years. He is planning to sell his business at the end of the fourth year.
The amount Nigel will receive will depend on the age of his fleet of bicycles.
These amounts, in £1000s, are shown in Table 2. \begin{table}[h] \end{table} Complete the table in the answer book to determine Nigel's best strategy to maximise his total profit over the next four years. You must state the action he should take each year (keep or replace) and his total profit.
(Total 13 marks)

7. D2 make industrial robots. They can make up to four in any one month, but if they make more than three they need to hire additional labour at a cost of \(\pounds 300\) per month. They can store up to three robots at a cost of \(\pounds 100\) per robot per month. The overhead costs are \(\pounds 500\) in any month in which work is done. The 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 at the end of May. The order book for January to May is: Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided in the answer book. State the minimum cost.
(Total 14 marks)

6 A linear programming problem is
Maximise \(\mathrm { P } = 2 \mathrm { x } - \mathrm { y }\) subject to $$\begin{aligned} 3 x + y - 4 z & \leqslant 24 \\ 5 x - 3 z & \leqslant 60 \\ - x + 2 y + 3 z & \leqslant 12 \end{aligned}$$ and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)

1. 1. Represent this problem as an initial simplex tableau.
   2. Carry out one iteration of the simplex algorithm. After two iterations the resulting tableau is

      \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
      1	0	\(\frac { 5 } { 11 }\)	0	\(- \frac { 6 } { 11 }\)	\(\frac { 8 } { 11 }\)	0	\(30 \frac { 6 } { 11 }\)
      0	1	\(- \frac { 3 } { 11 }\)	0	\(- \frac { 3 } { 11 }\)	\(\frac { 4 } { 11 }\)	0	\(15 \frac { 3 } { 11 }\)
      0	0	\(- \frac { 5 } { 11 }\)	1	\(- \frac { 5 } { 11 }\)	\(\frac { 3 } { 11 }\)	0	\(5 \frac { 5 } { 11 }\)
      0	0	\(\frac { 34 } { 11 }\)	0	\(\frac { 12 } { 11 }\)	\(- \frac { 5 } { 11 }\)	1	\(10 \frac { 10 } { 11 }\)

2. 1. Write down the basic variables after two iterations.
   2. Write down the exact values of the basic feasible solution for \(x , y\) and \(z\) after two iterations.
   3. State what you can deduce about the optimal value of the objective for the original problem. You are now given that, in addition to the constraints above, \(\mathrm { x } + \mathrm { y } + \mathrm { z } = 9\).
3. Use the additional constraint to rewrite the original constraints in terms of \(x\) and \(y\) but not \(z\).
4. Explain why the simplex algorithm cannot be applied to this new problem without some modification.

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

1. A linear programming problem is defined as follows:

$$\begin{array} { l l } \text { Maximise } & P = 3 x + 3 y + 4 z \\ \text { subject to } & x + 2 y + z \leq 30 \\ & 5 x + y + 3 z \leq 60 \\ \text { and } & x \geq 0 , y \geq 0 , z \geq 0 . \end{array}$$

1. Display the problem in a Simplex Tableau.
2. Starting with a pivot chosen from the \(z\)-column, perform one iteration of your tableau.
3. Write down the resulting values of \(x , y , z\) and \(P\) and state with a reason whether or not these values give an optimal solution.

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

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	0	0	\(1\frac{1}{3}\)	1	0	\(-\frac{1}{3}\)	\(\frac{5}{3}\)
\(y\)	0	1	\(3\frac{1}{3}\)	0	1	\(-\frac{1}{3}\)	\(\frac{1}{3}\)
\(x\)	1	0	\(-3\)	0	\(-1\)	\(\frac{1}{3}\)	1
\(P\)	0	0	1	0	1	1	11

1. Explain why this is an optimal tableau. [1]
2. Write down the optimal solution of this problem, stating the value of every variable. [3]
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\). [2]