Formulate LP from context

9. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne. The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x , y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.

1. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities.
   (4) An initial Simplex tableau for the above situation is

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	3	2	4	1	0	0	35
   \(s\)	1	3	2	0	1	0	20
   \(t\)	2	4	3	0	0	1	24
   \(P\)	- 4	- 5	- 3	0	0	0	0

2. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage. T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.
3. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.

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.
5. 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\).
6. 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\).
7. What does the table tell you about \(d\) with respect to the false proposition \(a\) ?
8. Explain why Russell introduced propositions \(b\) and \(c\) into his argument.
9. 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.
10. 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

8. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne. The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x , y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.

1. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities.
   (4) An initial Simplex tableau for the above situation is

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	3	2	4	1	0	0	35
   \(s\)	1	3	2	0	1	0	20
   \(t\)	2	4	3	0	0	1	24
   \(P\)	- 4	- 5	- 3	0	0	0	0

2. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage. T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.
3. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.
   (2)

7. A publisher plans to produce three versions of the same book: a paperback, a hardcover, and a deluxe edition.

• Each paperback takes 4 minutes to print and 1 minute to bind
• Each hardcover takes 8 minutes to print and 5 minutes to bind
• Each deluxe edition takes 15 minutes to print and 12 minutes to bind

The printing machine is available for at most 150 hours and the binding machine must be used for at least 60 hours. The publisher decides to produce

• at least 1600 books in total
• at least three times as many paperbacks as hardcovers

The profit on each paperback sold is \(\pounds 8\), the profit on each hardcover sold is \(\pounds 20\) and the profit on each deluxe edition sold is \(\pounds 40\) Let \(x , y\) and \(z\) represent the number of paperbacks, hardcovers and deluxe editions produced.

1. Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. The publisher decides to solve this linear programming problem by using the two-stage simplex method.
2. Set up an initial tableau for solving this problem using the two-stage simplex method. As part of your solution, you must show how
   • the constraints have been made into equations by using slack variables, exactly two surplus variables and exactly two artificial variables
   • the rows for the two objective functions are formed
   The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.

   b.v.	\(x\)	\(y\)	\(z\)	\(\mathrm { S } _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(\mathrm { S } _ { 1 }\)	0	0	0	1	1	3	0	-1	-3	600
   \(z\)	0	\(\frac { 4 } { 11 }\)	1	0	\(- \frac { 1 } { 11 }\)	\(\frac { 1 } { 11 }\)	0	\(\frac { 1 } { 11 }\)	\(- \frac { 1 } { 11 }\)	\(\frac { 2000 } { 11 }\)
   \(x\)	1	\(\frac { 7 } { 11 }\)	0	0	\(\frac { 1 } { 11 }\)	\(- \frac { 12 } { 11 }\)	0	\(- \frac { 1 } { 11 }\)	\(\frac { 12 } { 11 }\)	\(\frac { 15600 } { 11 }\)
   \(s _ { 4 }\)	0	\(\frac { 40 } { 11 }\)	0	0	\(\frac { 1 } { 11 }\)	\(- \frac { 12 } { 11 }\)	1	\(- \frac { 1 } { 11 }\)	\(\frac { 12 } { 11 }\)	\(\frac { 15600 } { 11 }\)
   \(P\)	0	\(- \frac { 4 } { 11 }\)	0	0	\(- \frac { 32 } { 11 }\)	\(- \frac { 56 } { 11 }\)	0	\(\frac { 32 } { 11 }\)	\(\frac { 56 } { 11 }\)	\(\frac { 204800 } { 11 }\)
   I	0	0	0	0	0	0	0	1	1	0

3. Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method to obtain a new tableau. Make your method clear by stating the row operations you use. After three iterations of the second stage of the two-stage simplex method, the following tableau is obtained.

   b.v.	\(x\)	\(y\)	\(z\)	\(\mathrm { S } _ { 1 }\)	\(S _ { 2 }\)	\(S _ { 3 }\)	\(s _ { 4 }\)	Value
   \(s _ { 2 }\)	0	0	0	1	1	3	0	600
   \(z\)	0	0	1	\(\frac { 1 } { 10 }\)	0	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 10 }\)	100
   \(x\)	1	0	0	\(- \frac { 3 } { 40 }\)	0	\(- \frac { 9 } { 8 }\)	\(- \frac { 7 } { 40 }\)	1125
   \(y\)	0	1	0	\(- \frac { 1 } { 40 }\)	0	\(- \frac { 3 } { 8 }\)	\(\frac { 11 } { 40 }\)	375
   \(P\)	0	0	0	\(\frac { 29 } { 10 }\)	0	\(\frac { 7 } { 2 }\)	\(\frac { 1 } { 10 }\)	20500

   Given that the publisher produces the optimal number of each version of the book,
4. 1. state the maximum profit the publisher can earn,
   2. find the number of hours the binding machine will be used.
5. Give a reason why the publisher may not earn the profit stated in (d)(i).

5. A garden centre makes hanging baskets to sell to its customers. Three types of hanging basket are made, Sunshine, Drama and Peaceful. The plants used are categorised as Impact, Flowering or Trailing. Each Sunshine basket contains 2 Impact plants, 4 Flowering plants and 3 Trailing plants. Each Drama basket contains 3 Impact plants, 2 Flowering plants and 4 Trailing plants. Each Peaceful basket contains 1 Impact plant, 3 Flowering plants and 2 Trailing plants. The garden centre can use at most 80 Impact plants, at most 140 Flowering plants and at most 96 Trailing plants each day. The profit on Sunshine, Drama and Peaceful baskets are \(\pounds 12 , \pounds 20\) and \(\pounds 16\) respectively. The garden centre wishes to maximise its profit. Let \(x , y\) and \(z\) be the number of Sunshine, Drama and Peaceful baskets respectively, produced each day.

1. Formulate this situation as a linear programming problem, giving your constraints as inequalities.
2. State the further restriction that applies to the values of \(x , y\) and \(z\) in this context. The Simplex algorithm is used to solve this problem. After one iteration, the tableau is

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(- \frac { 1 } { 4 }\)	0	\(- \frac { 1 } { 2 }\)	1	0	\(- \frac { 3 } { 4 }\)	8
   \(s\)	\(\frac { 5 } { 2 }\)	0	2	0	1	\(- \frac { 1 } { 2 }\)	92
   \(y\)	\(\frac { 3 } { 4 }\)	1	\(\frac { 1 } { 2 }\)	0	0	\(\frac { 1 } { 4 }\)	24
   \(P\)	3	0	-6	0	0	5	480

3. State the variable that was increased in the first iteration. Justify your answer.
4. Determine how many plants in total are being used after only one iteration of the Simplex algorithm.
5. Explain why for a second iteration of the Simplex algorithm the 2 in the \(z\) column is the pivot value. After a second iteration, the tableau is

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(\frac { 3 } { 8 }\)	0	0	1	\(\frac { 1 } { 4 }\)	\(- \frac { 7 } { 8 }\)	31
   \(s\)	\(\frac { 5 } { 4 }\)	0	1	0	\(\frac { 1 } { 2 }\)	\(- \frac { 1 } { 4 }\)	46
   \(y\)	\(\frac { 1 } { 8 }\)	1	0	0	\(- \frac { 1 } { 4 }\)	\(\frac { 3 } { 8 }\)	1
   \(P\)	\(\frac { 21 } { 2 }\)	0	0	0	3	\(\frac { 7 } { 2 }\)	756

6. Use algebra to explain why this tableau is optimal.
7. State the optimal number of each type of basket that should be made. The manager of the garden centre is able to increase the number of Impact plants available each day from 80 to 100 . She wants to know if this would increase her profit.
8. Use your final tableau to determine the effect of this increase. (You should not carry out any further calculations.)

5. A leisure company owns boats of each of the following types: 2-person boats which are 4 metres long and weigh 50 kg .
4-person boats which are 3 metres long and weigh 20 kg .
8-person boats which are 14 metres long and weigh 100 kg .
The leisure company is willing to donate boats to a local sports club to accommodate up to 40 people at any one time. However, storage facilities mean that the combined length of the boats must not be more than 75 metres. Also, it must be possible to transport all the boats on a single trailer which has a maximum load capacity of 600 kg . The club intends to hire the boats out to help with the cost of maintaining them. It plans to charge \(\pounds 10 , \pounds 12\) and \(\pounds 8\) per day, for the 2 -, 4 - and 8 -person boats respectively and wishes to maximise its daily revenue ( \(\pounds R\) ). Let \(x , y\) and \(z\) represent the number of 2-, 4- and 8-person boats respectively given to the club.

1. Model this as a linear programming problem. Using the Simplex algorithm the following initial tableau is obtained:

   \(R\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)
   1	\({ } ^ { - } 10\)	\({ } ^ { - } 12\)	\({ } ^ { - } 8\)	0	0	0	0
   0	1	2	4	1	0	0	20
   0	4	3	14	0	1	0	75
   0	5	2	10	0	0	1	60

2. Explain the purpose of the variables \(s , t\) and \(u\).
3. By increasing the value of \(y\) first, work out the next two complete tableaus.
4. Explain how you know that your final tableau gives an optimal solution and state this solution in practical terms.

Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool. For each roll of carpet, the Lincoln requires 1 unit of black, 1 of green and 3 of red, the Norfolk requires 1 unit of black, 2 of green and 2 of red, and the Suffolk requires 2 units of black, 1 of green and 1 of red. There are up to 30 units of black, 40 units of green and 50 units of red available each day. Profits of £50, £80 and £60 are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit. Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x\), \(y\) and \(z\) respectively.

1. Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. [4]

This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.

1. Stating your row operations, show that after one complete iteration the tableau becomes

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(\frac{1}{2}\)	0	\(1\frac{1}{2}\)	1	\(-\frac{1}{2}\)	0	10
   \(y\)	\(\frac{1}{2}\)	1	\(\frac{1}{2}\)	0	\(\frac{1}{2}\)	0	20
   \(t\)	2	0	0	0	\(-1\)	1	10
   \(P\)	\(-10\)	0	\(-20\)	0	40	0	1600

   [4]
2. Explain the practical meaning of the value 10 in the top row. [2]
3. 1. Perform one further complete iteration of the Simplex algorithm.
   2. State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
   3. Interpret your current tableau, giving the value of each variable. [8]

Badgers is a small company that makes badges to customers' designs. Each badge must pass through four stages in its production: printing, stamping out, fixing pin and checking. The badges can be laminated, metallic or plastic. The times taken for 100 badges of each type to pass through each of the stages and the profits that Badgers makes on every 100 badges are shown in the table below. The table also shows the total time available for each of the production stages. Suppose that the company makes \(x\) hundred laminated badges, \(y\) hundred metallic badges and \(z\) hundred plastic badges.

1. Show that the printing time leads to the constraint \(x + y + 2z \leq 600\). Write down and simplify constraints for the time spent on each of the other production stages. [4]
2. What other constraint is there on the values of \(x\), \(y\) and \(z\)? [1]

The company wants to maximise the profit from the sale of badges.

1. Write down an appropriate objective function, to be maximised. [1]
2. Represent Badgers' problem as an initial Simplex tableau. [4]
3. Use the Simplex algorithm, pivoting first on a value chosen from the \(x\)-column and then on a value chosen from the \(y\)-column. Interpret your solution and the values of the slack variables in the context of the original problem. [9]

An engineer makes three components \(X\), \(Y\) and \(Z\). Relevant details are as follows: Component \(X\) requires 6 minutes turning, 3 minutes machining and 1 minute finishing. Component \(Y\) requires 15 minutes turning, 3 minutes machining and 4 minutes finishing. Component \(Z\) requires 12 minutes turning, 1 minute machining and 4 minutes finishing. The engineer gets access to 185 minutes turning, 30 minutes machining and 60 minutes finishing each day. The profits from selling components \(X\), \(Y\) and \(Z\) are £40, £90 and £60 respectively and the engineer wishes to maximise the profit from her work each day. Let the number of components \(X\), \(Y\) and \(Z\) the engineer makes each day be \(x\), \(y\) and \(z\) respectively.

1. Write down the 3 inequalities that apply in addition to \(x \geq 0\), \(y \geq 0\) and \(z \geq 0\). [3 marks]
2. Explain why it is not appropriate to use a graphical method to solve the problem. [1 mark]

It is decided to use the simplex algorithm to solve the problem.

1. Show that a possible initial tableau is:

   Basic Variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	6	15	12	1	0	0	185
   \(s\)	3	3	1	0	1	0	30
   \(t\)	1	4	4	0	0	1	60
   \(P\)	\(-4\)	\(-9\)	\(-6\)	0	0	0	0

   [2 marks]

It is decided to increase \(y\) first.

1. Perform sufficient complete iterations to obtain a final tableau and explain how you know that your solution is optimal. You may assume that work in progress is allowed. [9 marks]
2. State the number of each component that should be made per day and the total daily profit that this gives, assuming that all items can be sold. [1 mark]
3. If work in progress is not practicable, explain how you would obtain an integer solution to this problem. You are not expected to find this solution. [2 marks]

T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne.

	Processing	Blending	Packing	Profit (£100)
Morning blend	3	1	3	4
Afternoon blend	2	3	4	5
Evening blend	4	2	3	3

The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x\), \(y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.

1. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities. [4]

An initial Simplex tableau for the above situation is

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	3	2	4	1	0	0	35
\(s\)	1	3	2	0	1	0	20
\(t\)	2	4	3	0	0	1	24
\(P\)	\(-4\)	\(-5\)	\(-3\)	0	0	0	0

1. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage. [11]

T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.

1. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available. [2]

Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool. For each roll of carpet, the Lincoln requires 1 unit of black, 1 of green and 3 of red, the Norfolk requires 1 unit of black, 2 of green and 2 of red, and the Suffolk requires 2 units of black, 1 of green and 1 of red. There are up to 30 units of black, 40 units of green and 50 units of red available each day. Profits of £50, £80 and £60 are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit. Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x\), \(y\) and \(z\) respectively.

1. Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. [4]

This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.

1. Stating your row operations, show that after one complete iteration the tableau becomes

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(\frac{1}{2}\)	0	\(1\frac{1}{2}\)	1	\(-\frac{1}{2}\)	0	10
   \(y\)	\(\frac{1}{2}\)	1	\(\frac{1}{2}\)	0	\(\frac{1}{2}\)	0	20
   \(t\)	2	0	0	0	\(-1\)	1	10
   P	\(-10\)	0	\(-20\)	0	40	0	1600

   [4]

You may not need to use all of the tableaux.

1. Explain the practical meaning of the value 10 in the top row. [2]
2. 1. Perform one further complete iteration of the Simplex algorithm.

      Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations

      Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations

   2. State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
   3. Interpret your current tableau, giving the value of each variable. [8]

(Total 18 marks)