7.07b Simplex iterations: pivot choice and row operations

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

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)

3. 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. Write down the profit equation represented in the tableau.
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 value of the objective function and of each variable.

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)

5. In solving a three-variable maximising linear programming problem, the following tableau was obtained after the first iteration.

1. State which variable was increased first, giving a reason for your answer.
2. 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 the final values of each variable.

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.

4 A publisher is considering producing three books over the next week: a mathematics book, a novel and a biography. The mathematics book will sell at \(\pounds 10\) and costs \(\pounds 4\) to produce. The novel will sell at \(\pounds 5\) and costs \(\pounds 2\) to produce. The biography will sell at \(\pounds 12\) and costs \(\pounds 5\) to produce. The publisher wants to maximise profit, and is confident that all books will be sold. There are constraints on production. Each copy of the mathematics book needs 2 minutes of printing time, 1 minute of packing time, and \(300 \mathrm {~cm} ^ { 3 }\) of temporary storage space. Each copy of the novel needs 1.5 minutes of printing time, 0.5 minutes of packing time, and \(200 \mathrm {~cm} ^ { 3 }\) of temporary storage space. Each copy of the biography needs 2.5 minutes of printing time, 1.5 minutes of packing time, and \(400 \mathrm {~cm} ^ { 3 }\) of temporary storage space. There are 10000 minutes of printing time available on several printing presses, 7500 minutes of packing time, and \(2 \mathrm {~m} ^ { 3 }\) of temporary storage space.

1. Explain how the following initial feasible tableau models this problem.

   P	\(x\)	\(y\)	\(z\)	\(s 1\)	\(s 2\)	\(s 3\)	RHS
   1	- 6	- 3	- 7	0	0	0	0
   0	2	1.5	2.5	1	0	0	10000
   0	1	0.5	1.5	0	1	0	7500
   0	300	200	400	0	0	1	2000000

2. Use the simplex algorithm to solve your LP, and interpret your solution.
3. The optimal solution involves producing just one of the three books. By how much would the price of each of the other books have to be increased to make them worth producing? There is a marketing requirement to provide at least 1000 copies of the novel.
4. Show how to incorporate this constraint into the initial tableau ready for an application of the two-stage simplex method. Briefly describe how to use the modified tableau to solve the problem. You are NOT required to perform the iterations.

4 Colin has a hobby from which he makes a small income. He makes bowls, candle holders and key fobs.
The materials he uses include wood, metal parts, polish and sandpaper. They cost, on average, \(\pounds 15\) per bowl, \(\pounds 6\) per candle holder and \(\pounds 2\) per key fob. Colin has a monthly budget of \(\pounds 100\) for materials. Colin spends no more than 30 hours per month on manufacturing these objects. Each bowl takes 4 hours, each candle holder takes 2 hours and each key fob takes half an hour.

1. Let \(b\) be the number of bowls Colin makes in a month, \(c\) the number of candle holders and \(f\) the number of key fobs. Write out, in terms of these variables, two constraints corresponding to the limit on monthly expenditure on materials, and to the limit on Colin's time. Colin sells the objects at craft fairs. He charges \(\pounds 30\) for a bowl, \(\pounds 15\) for a candle holder and \(\pounds 3\) for a key fob.
2. Set up an initial simplex tableau for the problem of maximising Colin's monthly income subject to your constraints from part (i), assuming that he sells all that he produces.
3. Use the simplex algorithm to solve your LP, and interpret the solution from the simplex algorithm. Over a spell of several months Colin finds it difficult to sell bowls so he stops making them.
4. Modify and solve your LP, using simplex, to find how many candle holders and how many key fobs he should make, and interpret your solution. At the next craft fair Colin takes an order for 4 bowls. He promises to make exactly 4 bowls in the next month.
5. Set up this modified problem either as an application of two-stage simplex, or as an application of the big-M method. You are not required to solve the problem. The solution now is for Colin to produce 4 bowls, \(6 \frac { 2 } { 3 }\) candle holders and no key fobs.
6. What is Colin's best integer solution to the problem?
7. Your answer to part (vi) is not necessarily the integer solution giving the maximum profit for Colin. Explain why.

3 Three products, A, B and C are to be made.
Three supplements are included in each product. Product A has 10 g per kg of supplement \(\mathrm { X } , 5 \mathrm {~g}\) per kg of supplement Y and 5 g per kg of supplement Z . Product B has 5 g per kg of supplement \(\mathrm { X } , 5 \mathrm {~g}\) per kg of supplement Y and 3 g per kg of supplement Z .
Product C has 12 g per kg of supplement \(\mathrm { X } , 7 \mathrm {~g}\) per kg of supplement Y and 5 g per kg of supplement Z .
There are 12 kg of supplement X available, 12 kg of supplement Y , and 9 kg of supplement Z .
Product A will sell at \(\pounds 7\) per kg and costs \(\pounds 3\) per kg to produce. Product B will sell at \(\pounds 5\) per kg and costs \(\pounds 2\) per kg to produce. Product C will sell at \(\pounds 4\) per kg and costs \(\pounds 3\) per kg to produce. The profit is to be maximised.

1. Explain how the initial feasible tableau shown in Fig. 3 models this problem. \begin{table}[h]

   P	a	b	c	s 1	s 2	s 3	RHS
   1	- 4	- 3	- 1	0	0	0	0
   0	10	5	12	1	0	0	12000
   0	5	5	7	0	1	0	12000
   0	5	3	5	0	0	1	9000

   \captionsetup{labelformat=empty} \caption{Fig. 3}
   \end{table}
2. Use the simplex algorithm to solve this problem, and interpret the solution.
3. In the solution, one of the basic variables appears at a value of 0 . Explain what this means. There is a contractual requirement to provide at least 500 kg of product A .
4. Show how to incorporate this constraint into the initial tableau ready for an application of the two-stage simplex method. Briefly describe how the method works. You are not required to perform the iterations.

1 A furniture manufacturer is planning a production run. He will be making wardrobes, drawer units and desks. All can be manufactured from the same wood. He has available \(200 \mathrm {~m} ^ { 2 }\) of wood for the production run. Allowing for wastage, a wardrobe requires \(5 \mathrm {~m} ^ { 2 }\), a drawer unit requires \(3 \mathrm {~m} ^ { 2 }\), and a desk requires \(2 \mathrm {~m} ^ { 2 }\). He has 200 hours available for the production run. A wardrobe requires 4.5 hours, a drawer unit requires 5.2 hours, and a desk requires 3.8 hours. The completed furniture will have to be stored at the factory for a short while before being shipped. The factory has \(50 \mathrm {~m} ^ { 3 }\) of storage space available. A wardrobe needs \(1 \mathrm {~m} ^ { 3 }\), a drawer unit needs \(0.75 \mathrm {~m} ^ { 3 }\), and a desk needs \(0.5 \mathrm {~m} ^ { 3 }\). The manufacturer needs to know what he should produce to maximise his income. He sells the wardrobes at \(\pounds 80\) each, the drawer units at \(\pounds 65\) each and the desks at \(\pounds 50\) each.

1. Formulate the manufacturer's problem as an LP.
2. Use the Simplex algorithm to solve the LP problem.
3. Interpret the results.
4. An extra \(25 \mathrm {~m} ^ { 2 }\) of wood is found and is to be used. The new optimal solution is to make 44 wardrobes, no drawer units and no desks. However, this leaves some of each resource (wood, hours and space) left over. Explain how this can be possible.

1. Given that \(x\) and \(y\) are propositions, draw a 4-line truth table for \(x \Rightarrow y\), allowing \(x\) and \(y\) to take all combinations of truth values. If \(x\) is false and \(x \Rightarrow y\) is true, what can be deduced about the truth value of \(y\) ? A story has it that, in a lecture on logic, the philosopher Bertrand Russell (1872-1970) mentioned that a false proposition implies any proposition. A student challenged this, saying "In that case, given that \(1 = 0\), prove that you are the Pope."
   Russell immediately replied, "Add 1 to both sides of the equation: then we have \(2 = 1\). The set containing just me and the Pope has 2 members. But \(2 = 1\), so the set has only 1 member; therefore, I am the Pope." Russell's string of statements is an example of a deductive sequence. Let \(a\) represent " \(1 = 0\) ", \(b\) represent " \(2 = 1\) ", \(c\) represent "Russell and the Pope are 2" and \(d\) represent "Russell and the Pope are 1". Then Russell's deductive sequence can be written as \(( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d\).
2. Assuming that \(a\) is false, \(b\) is false, \(a \Rightarrow b\) is true, \(c\) is true, and that \(d\) can take either truth value, draw a 2-line truth table for \(( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d\).
3. What does the table tell you about \(d\) with respect to the false proposition \(a\) ?
4. Explain why Russell introduced propositions \(b\) and \(c\) into his argument.
5. Russell could correctly have started a deductive sequence: \(a \wedge [ a \Rightarrow ( ( 0.5 = - 0.5 ) \Rightarrow ( 0.25 = 0.25 ) ) ]\).
   Had he have done so could he correctly have continued it to end at \(d\) ?
   Justify your answer.
6. Draw a combinatorial circuit to represent \(( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d\). 3 Floyd's algorithm is applied to the incomplete network on 4 nodes drawn below. The weights on the arcs represent journey times. \includegraphics[max width=\textwidth, alt={}, center]{4b5bc097-1052-4e44-8623-a84ceaab0289-4_400_558_347_751} The final matrices are shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{final time matrix}

   \cline { 2 - 5 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)
   \(\mathbf { 1 }\)	6	5	3	10