7.07c Interpret simplex: values of variables, slack, and objective

A tailor makes two types of garment, A and B. He has available 70 m² of cotton fabric and 90 m² of woollen fabric. Garment A requires 1 m² of cotton fabric and 3 m² of woollen fabric. Garment B requires 2 m² of each fabric. The tailor makes \(x\) garments of type A and \(y\) garments of type B.

1. Explain why this can be modelled by the inequalities $$x + 2y \leq 70,$$ $$3x + 2y \leq 90,$$ $$x \geq 0, y \geq 0.$$ [2 marks]

The tailor sells type A for £30 and type B for £40. All garments made are sold. The tailor wishes to maximise his total income.

1. Set up an initial Simplex tableau for this problem. [3 marks]
2. Solve the problem using the Simplex algorithm. [8 marks]

Figure 4 shows a graphical representation of the feasible region for this problem. \includegraphics{figure_4}

1. Obtain the coordinates of the points A, C and D. [4 marks]
2. Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4. [3 marks]

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.

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	Value
\(r\)	2	0	4	1	0	80
\(s\)	1	4	2	0	1	160
\(P\)	\(-2\)	\(-8\)	\(-20\)	0	0	0

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. (5)
2. Write down the profit equation shown in tableau \(T\). (1)
3. State whether tableau \(T\) is optimal. Give a reason for your answer. (1)

(Total 7 marks)

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)

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]

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)

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]