7.07a Simplex tableau: initial setup in standard format

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.

8. Polly has a bird food stall at the local market. Each week she makes and sells three types of packs \(A , B\) and C. Pack \(A\) contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts.
Pack \(B\) contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts.
Pack \(C\) contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts.
Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs.
The profit made on each pack of \(A , B\) and \(C\) sold is \(\pounds 3.50 , \pounds 3.50\) and \(\pounds 6.50\) respectively. Polly sells every pack on her stall and wishes to maximise her profit, \(P\) pence. Let \(x , y\) and \(z\) be the numbers of packs \(A , B\) and \(C\) sold each week.
An initial Simplex tableau for the above situation is

1. Explain the meaning of the variables \(r , s\) and \(t\) in the context of this question.
2. Perform one complete iteration of the Simplex algorithm to form a new tableau \(T\). Take the most negative number in the profit row to indicate the pivotal column.
3. State the value of every variable as given by tableau \(T\).
4. Write down the profit equation given by tableau \(T\).
5. Use your profit equation to explain why tableau \(T\) is not optimal. Taking the most negative number in the profit row to indicate the pivotal column,
6. identify clearly the location of the next pivotal element.

8. The tableau below is the initial tableau for a linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\). Using the information in the tableau, write down

1. the objective function,
2. the three constraints as inequalities with integer coefficients. Taking the most negative number in the profit row to indicate the pivot column at each stage,
3. solve this linear programming problem. Make your method clear by stating the row operations you use.

   b.v.	x	y	z	r	s	t	Value	Row operations

   b.v.	x	y	z	r	s	t	Value	Row operations

   b.v.	x	y	z	r	s	t	Value	Row operations

   b.v.	x	y	z	r	s	t	Value	Row operations

4. State the final values of the objective function and each variable.
5. One of the constraints is not at capacity. Explain how it can be identified.

8. The tableau below is the initial tableau for a maximising linear programming problem in \(x , y\) and \(z\).

1. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm. State the row operations you use. You may not need to use all of these tableaux.

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	S	\(t\)	Value	Row operations
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations
   \includegraphics[max width=\textwidth, alt={}]{151644c7-edef-448e-ac2a-b374d79f264c-4_86_102_967_374}
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(S\)	\(t\)	Value	Row operations
   \(P\)

1. A company, Kleenitquick, has developed a new stain remover. To promote sales, three salespersons, Jess, Matt and Rachel, will be assigned to three of four department stores \(1,2,3\) and 4 , to demonstrate the stain remover. Each salesperson can only be assigned to one department store.

The table below shows the cost, in pounds, of assigning each salesperson to each department store.

1. Explain why a dummy row needs to be added to the table.
2. Complete Table 1 in the answer book.
3. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost of assigning salespersons to department stores. You must make your method clear and show the table after each iteration.
4. Find the minimum cost.
   

6. The table below shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { X } , \mathrm { Y }\) and Z to three demand points, \(\mathrm { A } , \mathrm { B }\) and C . It also shows the stock held at each supply point and the stock required at each demand point.

1. This is a balanced problem. Explain what this means.
2. Use the north west corner method to obtain a possible solution.
3. Taking ZA as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear and state your exiting cell.
4. Perform one more iteration of the stepping-stone method to find a further improved solution. You must make your shadow costs, improvement indices, entering cell, exiting cell and route clear.
5. State the cost of the solution you found in part (d).

2. A team of four workers, Harry, Jess, Louis and Saul, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to one task and each task must be done by just one worker. Jess cannot be assigned to task 4.
The amount, in pounds, that each person would earn while assigned to each task is shown in the table below.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total amount earned by the team. You must make your method clear and show the table after each stage.
2. State who should be assigned to each task and the total amount earned by the team.

3. The table below shows the cost of transporting one block of staging from each of two supply points, X and Y , to each of four concert venues, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . It also shows the number of blocks held at each supply point and the number of blocks required at each concert venue. A minimal cost solution is required.

1. Use the north-west corner method to obtain a possible solution.
   (1)
2. Taking the most negative improvement index to indicate the entering square, use the stepping stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells.
3. Is your current solution optimal? Give a reason for your answer.
   (1)

6. The tableau below is the initial tableau for a linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Write down the profit equation represented in the initial tableau.
   (1)
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use.
3. State the final value of the objective function and of each variable.
   (3)

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

1. Add a dummy demand point and appropriate values to Table 1 in the answer book. Table 2 shows an initial solution given by the north-west corner method.
   Table 3 shows some of the improvement indices for this solution. \begin{table}[h]

   	A	B	C	D
   1	20
   2	15	7
   3		18	2
   4			28	10

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table} \begin{table}[h]

   	A	B	C	D
   1		- 13		- 9
   2			- 11
   3
   4	1	- 7

   \captionsetup{labelformat=empty} \caption{Table 3}
   \end{table}
2. Calculate the shadow costs and the missing improvement indices and enter them into Table 3 in the answer book.
3. Taking the most negative improvement index to indicate the entering square, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.

6. Three workers, \(\mathrm { P } , \mathrm { Q }\) and R , are to be assigned to three tasks, A, B and C. Each worker must be assigned to just one task and each task must be assigned to just one worker.
Table 1 shows the cost of using each worker for each task. The total cost is to be minimised. \begin{table}[h] \end{table}

1. Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective and constraints clear.
   You are not required to solve the problem. Table 2 shows the profit gained by using each worker for each task. The total profit is to be maximised. \begin{table}[h]

   	Task A	Task B	Task C
   Worker P	33	37	31
   Worker Q	32	36	40
   Worker R	41	35	38

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
2. Modify Table 2 in the answer book so that the Hungarian Algorithm could be used to find the maximum total profit. You are not required to solve the problem.
   (2)
   (Total 9 marks)

1. Five workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , are to be assigned to five tasks, \(1,2,3,4\) and 5 . Each worker is to be assigned to one task and each task must be assigned to one worker.

The cost, in pounds, of assigning each person to each task is shown in the table below. The cost is to be minimised.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.
2. Find the minimum cost.
   

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)

4. The tableau below is the initial tableau for a three-variable linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm to obtain tableau T. Make your method clear by stating the row operations you use.
2. Write down the profit equation given by T .
3. Use your answer to (b) to determine whether T is optimal, justifying your answer.

3. The tableau below is the initial tableau for a three-variable linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use.
2. State the final values of the objective function and each variable.

1. The tableau below is the initial tableau for a linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Perform one iteration of the Simplex algorithm to obtain a new tableau, \(T\). State the row operations you use.
   (5)
2. Write down the profit equation given by \(T\) and state the current values of the slack variables.
   

4. 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 after the first iteration.

1. State which variable was increased first, giving a reason for your answer.
2. Perform one complete iteration of the simplex algorithm, to obtain a new tableau, T. Make your method clear by stating the row operations you use.
3. Write down the profit equation given by T .
4. State whether T is optimal. You must use your answer to (c) to justify your answer.

6. The tableau below is the initial tableau for a maximising linear programming problem.

1. Write down the four equations represented in the initial tableau.
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the Simplex algorithm. State the row operations that you use.
3. State whether or not your last tableau is optimal. Give a reason for your answer.

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)

2. 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 initial tableau was obtained.

1. Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm, to obtain tableau \(T\). State the row operations that you use.
2. Write down the profit equation shown in tableau \(T\).
3. State whether tableau \(T\) is optimal. Give a reason for your answer.

4 The "Cuddly Friends Company" produces soft toys. For one day's production run it has available \(11 \mathrm {~m} ^ { 2 }\) of furry material, \(24 \mathrm {~m} ^ { 2 }\) of woolly material and 30 glass eyes. It has three soft toys which it can produce: The "Cuddly Aardvark", each of which requires \(0.5 \mathrm {~m} ^ { 2 }\) of furry material, \(2 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 3\). The "Cuddly Bear", each of which requires \(1 \mathrm {~m} ^ { 2 }\) of furry material, \(1.5 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 5\). The "Cuddly Cat", each of which requires \(1 \mathrm {~m} ^ { 2 }\) of furry material, \(1 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 2\). An analyst formulates the following LP to find the production plan which maximises profit. $$\begin{array} { l l } \text { Maximise } & 3 a + 5 b + 2 c \\ \text { subject to } & 0.5 a + b + c \leqslant 11 , \\ & 2 a + 1.5 b + c \leqslant 24 , \\ & 2 a + 2 b + 2 c \leqslant 30 . \end{array}$$

1. Explain how this formulation models the problem, and say why the analyst has not simplified the last inequality to \(a + b + c \leqslant 15\).
2. The final constraint is different from the others in that the resource is integer valued. Explain why that does not impose an additional difficulty for this problem.
3. Solve this problem using the simplex algorithm. Interpret your solution and say what resources are left over. On a particular day an order is received for two Cuddly Cats, and the extra constraint \(c \geqslant 2\) is added to the formulation.
4. Set up an initial simplex tableau to deal with the modified problem using either the big-M approach or two-phase simplex. Do not perform any iterations on your tableau.
5. Show that the solution given by \(a = 8 , b = 2\) and \(c = 5\) uses all of the resources, but that \(a = 6 , b = 6\) and \(c = 2\) gives more profit. What resources are left over from the latter solution?

3 A farmer has 40 acres of land. Four crops, A, B, C and D are available.
Crop A will return a profit of \(\pounds 50\) per acre. Crop B will return a profit of \(\pounds 40\) per acre.
Crop C will return a profit of \(\pounds 40\) per acre. Crop D will return a profit of \(\pounds 30\) per acre.
The total number of acres used for crops A and B must not be greater than the total number used for crops C and D. The farmer formulates this problem as:
Maximise \(\quad 50 a + 40 b + 40 c + 30 d\),
subject to \(\quad a + b \leqslant 20\), \(a + b + c + d \leqslant 40\).

1. Explain what the variables \(a , b , c\) and \(d\) represent. Explain how the first inequality was obtained.
   Explain why expressing the constraint on the total area of land as an inequality will lead to a solution in which all of the land is used.
2. Solve the problem using the simplex algorithm. Suppose now that the farmer had formulated the problem as:
   Maximise \(\quad 50 a + 40 b + 40 c + 30 d\),
   subject to \(\quad a + b \leqslant 20\), \(a + b + c + d = 40\).
3. Show how to adapt this problem for solution either by the two-stage simplex method or the big-M method. In either case you should show the initial tableau and describe what has to be done next. You should not attempt to solve the problem.

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.