Interpret optimal tableau

3 A problem to maximise \(P\) as a function of \(x , y\) and \(z\) is represented by the initial Simplex tableau below.

1. Write down \(P\) as a function of \(x , y\) and \(z\).
2. Write down the constraints as inequalities involving \(x , y\) and \(z\).
3. Carry out one iteration of the Simplex algorithm. After a second iteration of the Simplex algorithm the tableau is as given below.

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
   1	0	7.25	0	0.6	1.75	211
   0	1	0.75	0	0	0.25	25
   0	0	0.75	1	- 0.2	0.25	13

4. Explain how you know that the optimal solution has been achieved.
5. Write down the values of \(x , y\) and \(z\) that maximise \(P\). Write down the optimal value of \(P\).

10. While solving a maximizing linear programming problem, the following tableau was obtained.

1. Explain why this is an optimal tableau.
2. Write down the optimal solution of this problem, stating the value of every variable.
3. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).

5. While solving a maximising linear programming problem, the following tableau was obtained.

1. Write down the values of \(\mathrm { x } , \mathrm { y }\) and z as indicated by this tableau.
2. Write down the profit equation from the tableau.

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.

5 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 \(\pounds 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. Initial tableau
Row 1
Row 2
Row 3
Row 4

1. Show how the constraint on the number of red tulips leads to one of the rows of the tableau. The tableau that results after the first iteration is shown below.
   After first iteration
   Row 5
   Row 6
   Row 7
   Row 8

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
   1	0	- 0.04	0.06	0	0	0.02	4.8
   0	0	1	- 1	1	0	0	5
   0	0	10.8	7.3	0	1	0.1	24
   0	1	0.96	1.06	0	0	0.02	4.8

2. Which cell was used as the pivot?
3. Explain why row 2 and row 6 are the same.
4. (a) Read off the values of \(x , y\) and \(z\) after the first iteration.
   (b) Interpret this solution in terms of the original problem.
5. 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. 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.
6. 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. A planar graph \(G\) is described by the adjacency matrix below. \(\quad\) \(A\) \(B\) \(C\) \(D\) \(E\) \(F\) \(\left( \begin{array} { c c c c c c } A & B & C & D & E & F \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \end{array} \right)\)
7. Draw the graph \(G\).
8. Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it.
9. Explain why graph \(G\) cannot have a Hamiltonian cycle that includes the edge \(A B\). Deduce how many Hamiltonian cycles graph \(G\) has. A colouring algorithm is given below. STEP 1: Choose a vertex, colour this vertex using colour 1. STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1 . STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2 . STEP 4: Go back to STEP 2.
10. Apply this algorithm to graph \(G\), starting at \(E\). Explain how the colouring shows you that graph \(G\) is not bipartite. By removing just one edge from graph \(G\) it is possible to make a bipartite graph.
11. Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. Graph \(G\) is augmented by the addition of a vertex \(X\) joined to each of \(A , B , C , D , E\) and \(F\).
12. Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2.

2. While solving a maximizing linear programming problem, the following tableau was obtained.

1. Explain why this is an optimal tableau.
2. Write down the optimal solution of this problem, stating the value of every variable.
3. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).

3 The Simplex tableau below is optimal. 3

1. Deduce the range of values that \(k\) must satisfy.
   3
2. Write down the value of the variable \(s\) which corresponds to the optimal value of \(P\).

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 was obtained.

1. State, giving your reason, whether this tableau represents the optimal solution. [1]
2. State the values of every variable. [3]
3. Calculate the profit made on each unit of \(y\). [2]

\includegraphics{figure_4} An engineering project is modelled by the activity network shown in Figure 4. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest time.

1. Calculate the early time and late time for each event. Write these in boxes in Diagram 1 in the answer book. [4]
2. State the critical activities. [1]
3. Find the total float on activities D and F. You must show your working. [3]
4. On the grid in the answer book, draw a cascade (Gantt) chart for this project. [4]

The chief engineer visits the project on day 15 and day 25 to check the progress of the work. Given that the project is on schedule,

1. which activities must be happening on each of these two days? [3]

While solving a maximizing linear programming problem, the following tableau was obtained.

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	0	0	\(1\frac{1}{3}\)	1	0	\(-\frac{1}{3}\)	\(\frac{5}{3}\)
\(y\)	0	1	\(3\frac{1}{3}\)	0	1	\(-\frac{1}{3}\)	\(\frac{1}{3}\)
\(x\)	1	0	\(-3\)	0	\(-1\)	\(\frac{1}{3}\)	1
\(P\)	0	0	1	0	1	1	11

1. Explain why this is an optimal tableau. [1]
2. Write down the optimal solution of this problem, stating the value of every variable. [3]
3. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\). [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 tableau was obtained.

1. State, giving your reason, whether this tableau represents the optimal solution. [1]
2. State the values of every variable. [3]
3. Calculate the profit made on each unit of \(y\). [2]

(Total 6 marks)