Explain unbounded solution

A question is this type if and only if it asks to explain why a linear programming problem has no finite maximum or why P can be increased without limit.

3 questions · Standard +0.6

7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations
Sort by: Default | Easiest first | Hardest first
OCR D1 2007 January Q6
18 marks Standard +0.8
6 Consider the linear programming problem: $$\begin{array} { l r } \text { maximise } & P = 3 x - 5 y + 4 z , \\ \text { subject to } & x + 2 y - 3 z \leqslant 12 , \\ & 2 x + 5 y - 8 z \leqslant 40 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
  1. Represent the problem as an initial Simplex tableau.
  2. Explain why it is not possible to pivot on the \(z\) column of this tableau. Identify the entry on which to pivot for the first iteration of the Simplex algorithm. Explain how you made your choice of column and row.
  3. Perform one iteration of the Simplex algorithm. Write down the values of \(x , y\) and \(z\) after this iteration.
  4. Explain why \(P\) has no finite maximum. The coefficient of \(z\) in the objective is changed from + 4 to - 40 .
  5. Describe the changes that this will cause to the initial Simplex tableau and the tableau that results after one iteration. What is the maximum value of \(P\) in this case? Now consider this linear programming problem: $$\begin{array} { l l } \text { maximise } & Q = 3 x - 5 y + 7 z , \\ \text { subject to } & x + 2 y - 3 z \leqslant 12 , \\ & 2 x - 7 y + 10 z \leqslant 40 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$ Do not use the Simplex algorithm for these parts.
  6. By adding the two constraints, show that \(Q\) has a finite maximum.
  7. There is an optimal point with \(y = 0\). By substituting \(y = 0\) in the two constraints, calculate the values of \(x\) and \(z\) that maximise \(Q\) when \(y = 0\).
OCR D1 2011 June Q4
13 marks Standard +0.8
4 Consider the following LP problem.
Maximise\(P = - 3 w + 5 x - 7 y + 2 z\),
subject to\(w + 2 x - 2 y - z \leqslant 10\),
\(2 w + 3 y - 4 z \leqslant 12\),
and\(4 w + 5 x + y \leqslant 30\),
\(w \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).
  1. Represent the problem as an initial Simplex tableau. Explain why the pivot can only be chosen from the \(x\) column.
  2. Perform one iteration of the Simplex algorithm. Show how each row was obtained and write down the values of \(w , x , y , z\) and \(P\) at this stage.
  3. Perform a second iteration of the Simplex algorithm. Write down the values of \(w , x , y , z\) and \(P\) at this stage and explain how you can tell from this tableau that \(P\) can be increased without limit. How could you have known from the LP formulation above that \(P\) could be increased without limit?
AQA D2 2009 January Q3
15 marks Standard +0.3
3
  1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 4 x - 5 y + 6 z \\ \text { subject to } & 6 x + 7 y - 4 z \leqslant 30 \\ & 2 x + 4 y - 5 z \leqslant 8 \\ & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
  2. The Simplex method is to be used to solve this problem.
    1. Explain why it is not possible to choose a pivot from the \(z\)-column initially.
    2. Identify the initial pivot and explain why this particular element should be chosen.
    3. Perform one iteration using your initial tableau from part (a).
    4. State the values of \(x , y\) and \(z\) after this first iteration.
    5. Without performing any further iterations, explain why \(P\) has no finite maximum value.
  3. Using the same inequalities as in part (a), the problem is modified to $$\text { Maximise } \quad Q = 4 x - 5 y - 20 z$$
    1. Write down a modified initial tableau and the revised tableau after one iteration.
    2. Hence find the maximum value of \(Q\).