7.06b Slack variables: converting inequalities to equations

9 A company producing chicken food makes three products, Basic, Premium and Supreme, from wheat, maize and barley. A tonne \(( 1000 \mathrm {~kg} )\) of Basic uses 400 kg of wheat, 200 kg of maize and 400 kg of barley.
A tonne of Premium uses 400 kg of wheat, 500 kg of maize and 100 kg of barley.
A tonne of Supreme uses 600 kg of wheat, 200 kg of maize and 200 kg of barley.
The company has 130 tonnes of wheat, 70 tonnes of maize and 72 tonnes of barley available. The company must make at least 75 tonnes of Supreme.
The company makes \(\pounds 50\) profit per tonne of Basic, \(\pounds 100\) per tonne of Premium and \(\pounds 150\) per tonne of Supreme. They plan to make \(x\) tonnes of Basic, \(y\) tonnes of Premium and \(z\) tonnes of Supreme.

1. Write down four inequalities representing the constraints (in addition to \(x , y \geqslant 0\) ).
   [0pt] [4 marks]
2. The company want exactly half the production to be Supreme. Show that the constraints in part (a) become $$\begin{aligned} x + y & \leqslant 130 \\ 4 x + 7 y & \leqslant 700 \\ 2 x + y & \leqslant 240 \\ x + y & \geqslant 75 \\ x & \geqslant 0 \\ y & \geqslant 0 \end{aligned}$$
3. On the grid opposite, illustrate all the constraints and label the feasible region.
4. Write an expression for \(P\), the profit for the whole production, in terms of \(x\) and \(y\) only.
   [0pt] [2 marks]
5. 1. By drawing an objective line on your graph, or otherwise, find the values of \(x\) and \(y\) which give the maximum profit.
      [0pt] [2 marks]
   2. State the maximum profit and the amount of each product that must be made.
      [0pt] [2 marks] \section*{Answer space for question 9}
      \includegraphics[max width=\textwidth, alt={}]{f5890e58-38c3-413c-8762-6f80ce6dcec7-21_1349_1728_310_148}
      QUESTION
      PART
      REFERENCE \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-24_2488_1728_219_141}

8 Nerys runs a cake shop. In November and December she sells Christmas hampers. She makes up the hampers herself, in two sizes: Luxury and Special. Each day, Nerys prepares \(x\) Luxury hampers and \(y\) Special hampers.
It takes Nerys 10 minutes to prepare a Luxury hamper and 15 minutes to prepare a Special hamper. She has 6 hours available, each day, for preparing hampers. From past experience, Nerys knows that each day:

• she will need to prepare at least 5 hampers of each size
• she will prepare at most a total of 32 hampers
• she will prepare at least twice as many Luxury hampers as Special hampers.

Each Luxury hamper that Nerys prepares makes her a profit of \(\pounds 15\); each Special hamper makes a profit of \(\pounds 20\). Nerys wishes to maximise her daily profit, \(\pounds P\).

1. Show that \(x\) and \(y\) must satisfy the inequality \(2 x + 3 y \leqslant 72\).
2. In addition to \(x \geqslant 5\) and \(y \geqslant 5\), write down two more inequalities that model the constraints above.
3. On the grid opposite draw a suitable diagram to enable this problem to be solved graphically. Indicate a feasible region and the direction of an objective line.
4. 1. Use your diagram to find the number of each type of hamper that Nerys should prepare each day to achieve a maximum profit.
   2. Calculate this profit.
      \includegraphics[max width=\textwidth, alt={}]{fb95068f-f76d-492a-b385-bce17b26ae30-27_2490_1719_217_150}
      \section*{DO NOT WRITE ON THIS PAGE ANSWER IN THE SPACES PROVIDED}

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.

8 A family business makes and sells two kinds of kitchen table.
Each pine table takes 6 hours to make and the cost of materials is \(\pounds 30\).
Each oak table takes 10 hours to make and the cost of materials is \(\pounds 70\).
Each month, the business has 360 hours available for making the tables and \(\pounds 2100\) available for the materials.
Each month, the business sells all of its tables to a wholesaler.
The wholesaler specifies that it requires at least 10 oak tables per month and at least as many pine tables as oak tables. Each pine table sold gives the business a profit of \(\pounds 40\) and each oak table sold gives the business a profit of \(\pounds 75\). Use a graphical method to find the number of each type of table the business should make each month, in order to maximise its total profit. Show clearly how you obtain your answer.
[0pt] [8 marks]

5. A standard transportation problem is described in the linear programming formulation below. Let \(X _ { i j }\) be the number of units transported from \(i\) to \(j\) where \(i \in \{ \mathrm {~A} , \mathrm {~B} , \mathrm { C } , \mathrm { D } \}\) $$j \in \{ \mathrm { R } , \mathrm {~S} , \mathrm {~T} \} \text { and } x _ { i j } \geqslant 0$$ Minimise \(P = 23 x _ { \mathrm { AR } } + 17 x _ { \mathrm { AS } } + 24 x _ { \mathrm { AT } } + 15 x _ { \mathrm { BR } } + 29 x _ { \mathrm { BS } } + 32 x _ { \mathrm { BT } }\) $$+ 25 x _ { \mathrm { CR } } + 25 x _ { \mathrm { CS } } + 27 x _ { \mathrm { CT } } + 19 x _ { \mathrm { DR } } + 20 x _ { \mathrm { DS } } + 25 x _ { \mathrm { DT } }$$ subject to $$\begin{aligned} & \sum x _ { \mathrm { A } j } \leqslant 34 \\ & \sum x _ { \mathrm { B } j } \leqslant 27 \\ & \sum x _ { \mathrm { C } j } \leqslant 41 \\ & \sum x _ { \mathrm { D } j } \leqslant 18 \\ & \sum x _ { i \mathrm { R } } \geqslant 44 \\ & \sum x _ { i \mathrm {~S} } \geqslant 37 \\ & \sum x _ { i \mathrm {~T} } \geqslant k \end{aligned}$$ Given that the problem is balanced,

1. state the value of \(k\).
2. Explain precisely what the constraint \(\sum x _ { i \mathrm { R } } \geqslant 44\) means in the transportation problem.
3. Use the north-west corner method to obtain the cost of an initial solution to this transportation problem.
4. Perform one iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and the

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]

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)