7.07a Simplex tableau: initial setup in standard format

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 £3.50, £3.50 and £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]
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. [5]
3. State the value of every variable as given by tableau \(T\). [3]
4. Write down the profit equation given by tableau \(T\). [2]
5. Use your profit equation to explain why tableau \(T\) is not optimal. [1]

Taking the most negative number in the profit row to indicate the pivotal column,

1. identify clearly the location of the next pivotal element. [2]

(Total 15 marks)

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

1. Write down the four equations represented in the initial tableau above. [4]
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. [9]
3. State the values of the objective function and each variable. [3]

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\). $$\begin{array}{c|c|c|c|c|c|c|c} \text{basic variable} & x & y & z & r & s & t & \text{Value} \\ \hline r & 12 & 4 & 5 & 1 & 0 & 0 & 246 \\ \hline s & 9 & 6 & 3 & 0 & 1 & 0 & 153 \\ \hline t & 5 & 2 & -2 & 0 & 0 & 1 & 171 \\ \hline P & -2 & -4 & -3 & 0 & 0 & 0 & 0 \end{array}$$ Using the information in the tableau, write down

1. the objective function, [2]
2. the three constraints as inequalities with integer coefficients. [3]

Taking the most negative number in the profit row to indicate the pivot column at each stage,

1. solve this linear programming problem. Make your method clear by stating the row operations you use. [9]
2. State the final values of the objective function and each variable. [3]

One of the constraints is not at capacity.

1. Explain how it can be identified. [1]

(Total 18 marks)

Lucy is making party bags which she will sell to raise money for charity. She has three colours of party bag: red, yellow and blue. The bags contain balloons, sweets and toys. Lucy has a stock of 40 balloons, 80 sweets and 30 toys. The table shows how many balloons, sweets and toys are needed for one party bag of each colour.

Colour of party bag	Balloons	Sweets	Toys
Red	5	3	5
Yellow	4	7	2
Blue	6	6	3

Lucy will raise £1 for each bag that she sells, irrespective of its colour. She wants to calculate how many bags of each colour she should make to maximise the total amount raised for charity. Lucy has started to model the problem as an LP formulation. Maximise \quad \(P = x + y + z\), subject to \quad \(3x + 7y + 6z \leq 80\).

1. What does the variable \(x\) represent in Lucy's formulation? [1]
2. Explain why the constraint \(3x + 7y + 6z \leq 80\) must hold and write down another two similar constraints. [3]
3. What other constraints and restrictions apply to the values of \(x\), \(y\) and \(z\)? [1]
4. What assumption is needed for the objective to be valid? [1]
5. Represent the problem as an initial Simplex tableau. Do not carry out any iterations yet. [3]
6. Perform one iteration of the Simplex algorithm, choosing a pivot from the \(x\) column. Explain how the choice of pivot row was made and show how each row was calculated. [6]
7. Write down the values of \(x\), \(y\) and \(z\) from the first iteration of the Simplex algorithm and hence find the number of bags of each colour that Lucy should make according to this non-optimal tableau. [2]

In the optimal solution Lucy makes 10 bags.

1. Without carrying out further iterations of the Simplex algorithm, find a solution in which Lucy should make 10 bags. [1]

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)

A two person zero-sum game is represented by the following pay-off matrix for player \(A\).

	\(B\) plays 1	\(B\) plays 2	\(B\) plays 3
\(A\) plays 1	5	7	2
\(A\) plays 2	3	8	4
\(A\) plays 3	6	4	9

1. Formulate the game as a linear programming problem for player \(A\), writing the constraints as equalities and clearly defining your variables. [5]
2. Explain why it is necessary to use the simplex algorithm to solve this game theory problem. [1]
3. Write down an initial simplex tableau making your variables clear. [2]
4. Perform two complete iterations of the simplex algorithm, indicating your pivots and stating the row operations that you use. [8]

(Total 16 marks)

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

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	7	10	10	1	0	0	3600
\(s\)	6	9	12	0	1	0	3600
\(t\)	2	3	4	0	0	1	2400
\(P\)	-35	-55	-60	0	0	0	0

1. Write down the four equations represented in the initial tableau above. [4]
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. State the row operations that you use. [9]
3. State the values of the objective function and each variable. [3]

(Total 16 marks)

Kassi and Theo are discussing how much oil and how much vinegar to use to dress their salad. They agree to use between 5 and 10ml of oil and between 3 and 6ml of vinegar and that the amount of oil should not exceed twice the amount of vinegar. Theo prefers to have more oil than vinegar. He formulates the following problem to maximise the proportion of oil: Maximise \(\frac{x}{x + y}\) subject to \(0 \leq x \leq 10\), \(0 \leq y \leq 6\), \(x - 2y \leq 0\).

1. Explain why this problem is not an LP. [1]
2. Use the simplex method to solve the following LP. Maximise \(x - y\) subject to \(0 \leq x \leq 10\), \(0 \leq y \leq 6\), \(x - 2y \leq 0\). [7]
3. Kassi prefers to have more vinegar than oil. She formulates the following LP. Maximise \(y - x\) subject to \(5 \leq x \leq 10\), \(3 \leq y \leq 6\), \(x - 2y \leq 0\). Draw separate graphs to show the feasible regions for this problem and for the problem in part (ii). [5]
4. Explain why the formulation in part (ii) produced a solution for Theo's problem, and why it is more difficult to use the simplex method to solve Kassi's problem in part (iii). [2]
5. Produce an initial tableau for using the two-stage simplex method to solve Kassi's problem. Explain briefly how to proceed. [5]

A linear programming problem is \begin{align} \text{Maximise } P &= 4x - y - 2z
\text{subject to } x + 5y + 3z &\leq 60
2x - 5y &\leq 80
2y + z &\leq 10
x \geq 0, y &\geq 0, z \geq 0 \end{align}

1. Use the simplex algorithm to solve the problem. [7]

In the case when \(z = 0\) the feasible region can be represented graphically. \includegraphics{figure_1} The vertices of the feasible region are \((0, 0)\), \((40, 0)\), \((46.67, 2.67)\), \((35, 5)\) and \((0, 5)\), where non-integer values are given to 2 decimal places. The linear programming problem is given the additional constraint that \(x\) and \(y\) are integers.

1. Use branch-and-bound, branching on \(x\) first, to show that the optimum solution with this additional constraint is \(x = 45, y = 2\). [7]

A garden centre sells tulip bulbs in mixed packs. The cost of each pack and the number of tulips of each colour are given in the table. Dirk is designing a floral display in which he will need the number of red tulips to be at most 50 more than the number of white tulips, and the number of white tulips to be less than or equal to twice the number of pink tulips. He has a budget of £240 and wants to find out which packs to buy to maximise the total number of bulbs. Dirk uses the variables \(x\), \(y\) and \(z\) to represent, respectively, how many of pack A, pack B and pack C he buys. He sets up his problem as an initial simplex tableau, which is shown below.

1. Show how the constraint on the number of red tulips leads to one of the rows of the tableau. [3]

The tableau that results after the first iteration is shown below.

1. Which cell was used as the pivot? [1]
2. Explain why row 2 and row 6 are the same. [1]
3. 1. Read off the values of \(x\), \(y\) and \(z\) after the first iteration. [1]
   2. Interpret this solution in terms of the original problem. [2]
4. Identify the variable that has become non-basic. Use the pivot row of the initial tableau to eliminate \(x\) algebraically from the equation represented by Row 1 of the initial tableau. [3]

The feasible region can be represented graphically in three dimensions, with the variables \(x\), \(y\) and \(z\) corresponding to the \(x\)-axis, \(y\)-axis and \(z\)-axis respectively. The boundaries of the feasible region are planes. Pairs of these planes intersect in lines and at the vertices of the feasible region these lines intersect.

1. The planes defined by each of the new basic variables being set equal to 0 intersect at a point. Show how the equations from part (v) are used to find the values \(P\) and \(x\) at this point. [2]