7.07f Algebraic interpretation: explain simplex calculations

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

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)

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)

1. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of four demand points, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

\begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Taking DQ as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.
2. Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by stating the
   • shadow costs
   • improvement indices
   • route
   • entering cell and exiting cell.
   • Determine whether the solution obtained from this second iteration is optimal, giving a reason for your answer.
   • State the cost of the solution found in (b).

1. Four workers, Ted (T), Harold (H), James (J) and Margaret (M), are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.

The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.
2. Determine the resulting total profit.

3. The table below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to four sales points, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . It also shows the number of units held at each supply point and the number of units required at each sales point. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
2. Taking AS as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.
3. Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and stating the

3 The pay-off matrix for a zero-sum game is

1. Show that the game does not have a stable solution.
2. Use a graphical technique to find the optimal mixed strategy for the player on columns.
3. Formulate an initial simplex tableau for the problem of finding the optimal mixed strategy for the player on rows.

2. The table shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { A } , \mathrm { B }\) and C , to each of four demand points, \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
   (1)
2. Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
   (2)
3. Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
4. Determine whether your current solution is optimal, giving a reason for your answer.

1. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of four demand points, \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution to this transportation problem is required.

\begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Explain why a zero has been placed in cell C 2 in Table 2. State the other cell in Table 2 in which the zero could have been placed.
2. State the shadow costs clearly and enter the improvement indices into Table 3 in your answer book. Taking the most negative improvement index to indicate the entering cell,
   [0pt]
3. list the stepping-stone route that should be used to obtain the next solution. You should make clear the cells that are included in your route and state your entering and exiting cells. [You do not need to state the next solution. You do not need to solve this problem.]

2. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { A } , \mathrm { B }\) and C , to each of four demand points, 1, 2, 3 and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required. \begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
2. Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
3. Determine whether your current solution is optimal, giving a reason for your answer.
4. State the cost of your current solution.

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.

Janet and Samantha play a zero-sum game. The game is represented by the following pay-off matrix for Janet. Samantha

	Strategy	\(S_1\)	\(S_2\)	\(S_3\)
\multirow{4}{*}{Janet}	\(J_1\)	2	7	6
	\(J_2\)	5	5	1
	\(J_3\)	4	3	8
	\(J_4\)	1	6	4

1. Explain why Janet should never play strategy \(J_4\) [1 mark]
2. Janet wants to maximise her winnings from the game. She defines the following variables. \(p_1 = \) the probability of Janet playing strategy \(J_1\) \(p_2 = \) the probability of Janet playing strategy \(J_2\) \(p_3 = \) the probability of Janet playing strategy \(J_3\) \(v = \) the value of the game for Janet Janet then formulates her situation as the following linear programming problem. Maximise \(P = v\) subject to \(2p_1 + 5p_2 + 4p_3 \geq v\) \(7p_1 + 5p_2 + 3p_3 \geq v\) \(6p_1 + p_2 + 8p_3 \geq v\) and \(p_1 + p_2 + p_3 \leq 1\) \(p_1, p_2, p_3 \geq 0\)
   1. Complete the initial Simplex tableau for Janet's situation in the grid below. [2 marks]

      \(P\)	\(v\)	\(p_1\)	\(p_2\)	\(p_3\)			value

   2. Hence, perform one iteration of the Simplex algorithm, showing your answer on the grid below. [2 marks]

      \(P\)	\(v\)	\(p_1\)	\(p_2\)	\(p_3\)			value

3. Further iterations of the Simplex algorithm are performed until an optimal solution is reached. The grid below shows part of the final Simplex tableau.

   \(p_1\)	\(p_2\)	value
   1	0	\(\frac{1}{12}\)
   0	1	\(\frac{1}{2}\)

   Find the probability of Janet playing strategy \(J_3\) when she is playing to maximise her winnings from the game. [1 mark]