A linear programming problem has the constraints \(x + y \le 6\), \(x \le 4\), \(y \le 5\), \(x + 2y \le 20\), \(x \ge 0\), \(y \ge 0\). Which of the following constraints can be removed without changing the feasible region?
Answer & explanation
Correct answer: option 4
The correct answer is Option (4) → \(x + 2y \le 20\)
The first three constraints, with \(x \ge 0, y \ge 0\), give the region with corner points
(0, 0), (4, 0), (4, 2), (1, 5), (0, 5)
On this region, x + 2y is largest at a corner:
\(x + 2y\) at the corners: 0, 4, 8, 11, 10
So every point of the region already has \(x + 2y \le 11 \lt 20\). The constraint \(x + 2y \le 20\) cuts nothing off; it is a redundant constraint and can be removed.
Why the other options are incorrect
Option (1) \(x + y \le 6\) — Incorrect. Without it, (4, 5) would become feasible, since it meets all the other constraints.
Option (2) \(x \le 4\) — Incorrect. Without it, (6, 0) would become feasible.
Option (3) \(y \le 5\) — Incorrect. Without it, (0, 6) would become feasible.