Further Mathematics · OCR H245 · Option D · Topic 7.07

The simplex algorithm

Use a simplex tableau, terminology, graphical and algebraic interpretation of iterations.

  • 3 sub-topics
  • Taught in Year 13
  • 33 practice questions
  • 3 animated lessons
Practice questions (33) Lessons Worksheets coming soon All OCR Further Mathematics topics

What the specification says

Every sub-topic OCR can examine in this topic, with its reference number from the official specification. The Y12 and Y13 tags show when each sub-topic is usually taught.

  1. 7.07a-cUse a simplex tableauY13
  2. 7.07dTerminologyY13
  3. 7.07e-fGraphical and algebraic interpretation of iterationsY13

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 33 questions in this topic, free, no account needed.

Linear programming

Not needed for Year 12Easy

Recognising the optimal tableau · Year 13 · 1 mark

  1. How can you tell that a simplex tableau for a maximisation problem is optimal?
    (1)

Show worked solutionHide worked solution
  1. A negative entry in the objective row means that PP can still be increased.CC: There are no negative entries in the objective row

Total1

  • M
  • A
  • B
How did it go?

Report a problem with this question

Linear programming

Not needed for Year 12Medium

Slack variables and the initial tableau · Year 13 · 5 marks

Maximise P=4x+5yP = 4x + 5y subject to x+4y≤80x + 4y \leq 80, 2x+y≤802x + y \leq 80, x,y≥0x, y \geq 0.
  1. (a)
    Use slack variables ss and tt to write the constraints as equations, and explain what ss represents.
    (3)
  2. (b)
    Write down the initial Simplex tableau.
    (2)
Show worked solutionHide worked solution

Part (a)3 marks

  1. ss, t≥0t \ge 0.x+4y+sx + 4y + s=80,  2x+y+t{}= 80, \ \ 2x + y + t=80{}= 80
  2. ss is the unused amount of the first resource.

Part (b)2 marks

  1. The objective row is P−4x−5y=0P - 4x - 5y = 0.b.v.xystvalues141080t210180P−4−5000\begin{array}{c|ccccc} \text{b.v.} & x & y & s & t & \text{value} \\ \hline s & 1 & 4 & 1 & 0 & 80 \\ t & 2 & 1 & 0 & 1 & 80 \\ P & -4 & -5 & 0 & 0 & 0 \end{array}

Total5

  • M
  • A
  • B
How did it go?

Report a problem with this question

Linear programming

Not needed for Year 12Hard

The simplex algorithm · Year 13 · 7 marks

The initial tableau for a maximisation problem is shown. b.v.xystvalues141080t310190P−4−5000\begin{array}{c|ccccc} \text{b.v.} & x & y & s & t & \text{value} \\ \hline s & 1 & 4 & 1 & 0 & 80 \\ t & 3 & 1 & 0 & 1 & 90 \\ P & -4 & -5 & 0 & 0 & 0 \end{array}
  1. (a)
    Perform one iteration of the Simplex algorithm, explaining how you chose the pivot.
    (5)
  2. (b)
    State whether the tableau is now optimal, and write down the current values of PP, xx and yy.
    (2)
Show worked solutionHide worked solution

Part (a)5 marks

  1. Pivot column yy: the most negative entry in the objective row.
  2. Value ÷ pivot-column entry; choose the smallest positive.ratios: 20, 90\text{ratios: } 20, \ 90
  3. Divide the pivot row by the pivot, then clear the column.b.v.xystvaluey14114020t1140−14170P−1140540100\begin{array}{c|ccccc} \text{b.v.} & x & y & s & t & \text{value} \\ \hline y & \frac{1}{4} & 1 & \frac{1}{4} & 0 & 20 \\ t & \frac{11}{4} & 0 & - \frac{1}{4} & 1 & 70 \\ P & - \frac{11}{4} & 0 & \frac{5}{4} & 0 & 100 \end{array}

Part (b)2 marks

  1. Not optimal: there is still a negative entry in the objective row.
  2. Non-basic variables are 0.P=100, x=0, y=20P = 100, \ x = 0, \ y = 20

Total7

  • M
  • A
  • B
How did it go?

Report a problem with this question