3D.5.4 Two-stage Simplex and big-M methods Quiz: Pearson Edexcel Further Maths, Unit 39

The 20 questions

1. In a constraint written as x + y - s + t = 5, what is the purpose of the artificial variable t?

   • It replaces the objective function during the iterations.
   • It measures the unused amount of a resource in a ≤ constraint.
   • It records the surplus amount above the minimum requirement.
   • It provides a starting basic variable so an initial feasible solution can be found.

2. In the constraint x + y ≥ 5 written in standard form, what sign does the surplus variable have?

   • It is added and s is an artificial variable with coefficient M.
   • It is added: x + y + s = 5 with s ≥ 0.
   • It is subtracted with s ≤ 0.
   • It is subtracted: x + y - s = 5 with s ≥ 0.

3. In the big-M method for a maximisation problem, what coefficient does an artificial variable receive in the objective function?

   • 0, because artificial variables are ignored.
   • +1, so that t is pushed to be as large as possible.
   • +M, a large positive reward.
   • -M, a large negative penalty.

4. In stage one of the two-stage Simplex method, what quantity is minimised?

   • The objective function P of the original problem.
   • The number of slack variables in the tableau.
   • The sum of the surplus variables only.
   • The sum of the artificial variables.

5. At the end of stage one the minimum sum of the artificial variables is zero. What does this tell you?

   • The original problem is unbounded above.
   • Every constraint is an equality with zero slack.
   • The original problem has no feasible solution.
   • A feasible solution to the original problem has been found, so stage two can start.

6. Why does the basic Simplex method alone fail for a ≥ constraint with a positive right-hand side?

   • The origin violates the constraint, so the slack variables do not give a feasible starting solution.
   • The constraint makes the objective row negative at the origin.
   • The tableau cannot hold more than two variables.
   • Surplus variables must be positive, which the tableau forbids.

7. In the big-M method, what does the value M represent?

   • A very large positive number chosen so that artificial variables are driven to zero at the optimum.
   • The maximum value attainable by P in any problem.
   • The number of constraints in the problem.
   • The initial value of the surplus variable.

8. Minimise C = 2x + 3y subject to x + y ≥ 4 and x + 3y ≥ 6 with x, y ≥ 0. What is the minimum value of C?

   • 12
   • 9
   • 10
   • 8

9. For minimise C = 2x + 3y subject to x + y ≥ 4 and x + 3y ≥ 6 with x, y ≥ 0, at which point is the minimum attained?

   • (3, 1)
   • (6, 0)
   • (4, 0)
   • (0, 4)

10. What is the maximum of P = x + 2y subject to x + y ≤ 5 and x + y ≥ 1 with x, y ≥ 0?

    • 5
    • 10
    • 12
    • 8

11. What is the maximum of P = x + y subject to x + 2y ≥ 4 and 3x + y ≤ 9 with x, y ≥ 0?

    • 9
    • 3.4
    • 6
    • 4

12. A maximisation problem has two ≥ constraints and one ≤ constraint. How many artificial variables are needed?

    • 0
    • 1
    • 2
    • 3

13. For x + y ≥ 4 and x + y ≤ 3 with x, y ≥ 0, what is the minimum possible sum of the artificial variables in stage one?

    • 4
    • 3
    • 0
    • 1

14. Write 2x + 3y ≥ 6 in standard form with surplus variable s and artificial variable t.

    • 2x + 3y - s + t = 6
    • 2x + 3y + s - t = 6
    • 2x + 3y + s + t = 6
    • 2x + 3y - s - t = 6

15. Maximise P = 2x + y subject to x + y ≥ 1 and x + y ≤ 4 with x, y ≥ 0. What is the maximum?

    • 4
    • 6
    • 2
    • 8

16. Why must M in the big-M method be chosen very large?

    • So that the surplus variables can be ignored.
    • So that M divides the Value column evenly at each pivot.
    • So that the objective row always stays positive.
    • So that any positive artificial variable costs so much that the optimum drives it to zero if a feasible solution exists.

17. At the optimum of a big-M problem an artificial variable is still basic with a positive value. What does this mean?

    • The problem is unbounded above.
    • M must be increased and the method rerun with no other change.
    • The solution is degenerate but feasible.
    • The original problem has no feasible solution.

18. Stage one ends with all artificial variables zero. What is done with the artificial columns in stage two?

    • They are doubled to restore feasibility.
    • They are dropped, and the original objective function is used.
    • They become the new slack variables.
    • They are kept with coefficient M in the objective.

19. A student uses +M instead of -M for the artificial variable in a maximisation problem. What goes wrong?

    • The Simplex method would stop immediately at the origin.
    • The method would reward artificial variables and push them large, giving an incorrect solution.
    • Nothing changes because M is only a label.
    • The surplus variables would become negative.

20. For a ≥ constraint with a positive right-hand side, why is the origin infeasible?

    • Substituting gives a zero objective, which is never allowed.
    • Substituting gives a negative slack value, which the tableau cannot hold.
    • The origin always lies on the boundary of ≥ constraints.
    • Substituting x = y = 0 gives 0 ≥ positive, which is false.

Related quizzes

• Formulating linear programs Quiz · 3D.5.1 · 20 questions
• Graphical solution of two variable problems Quiz · 3D.5.2 · 20 questions
• The Simplex algorithm for maximising and minimising Quiz · 3D.5.3 · 20 questions
• Proof by mathematical induction Quiz · 1.1 · 20 questions
• Quadratic equations and complex arithmetic Quiz · 2.1-2.2 · 20 questions
• Matrix arithmetic and inverses Quiz · 3.1-3.2 · 20 questions
• Expectation of discrete random variables Quiz · 3B.1.1 · 20 questions
• The Poisson distribution Quiz · 3B.2.1 · 20 questions
• Geometric and negative binomial models Quiz · 3B.3.1 · 20 questions
• Hypothesis tests for the Poisson distribution Quiz · 3B.4.1 · 20 questions