Practice: Feasible Sets

Recognition · Classification

Which of the following sets of restrictions permits no choice at all?

1 hint available, least help first.

Hint 1: Retrieval cue

Look for two restrictions that cannot hold at the same time.

Classification · Explanation

Classify each feasible set as empty, non-empty and bounded, or non-empty and unbounded. Justify each answer by exhibiting a feasible point, a contradiction, or a family of feasible points that grows without limit.

(a) $x + y \leq 5$ , $x \geq 0$ , $y \geq 0$

(b) $x - y \geq 1$ , $y - x \geq 1$

(d) $x^{2} + y^{2} \leq 4$ , $x \geq 3$

Write your answer

Write your answer, then compare it with the worked solution.

2 hints available, least help first.

Hint 1: Retrieval cue

For each part, first try to find one point that satisfies every restriction.

Hint 2: Strategy cue

To show emptiness, combine restrictions into a contradiction. To show unboundedness, produce a family of feasible points with a coordinate that grows without limit.

Compare with the worked solution

Comparing does not record a result. Judging your own written answer cannot show that you can do this without help.

(a) Non-empty and bounded. $(0, 0)$ is feasible. Nonnegativity plus $x + y \leq 5$ forces $0 \leq x \leq 5$ and $0 \leq y \leq 5$ , so the set fits in a finite box.

(b) Empty. Adding the two restrictions gives $0 \geq 2$ , a contradiction, so no point satisfies both.

(c) Non-empty and unbounded. $(t, 1 / t)$ is feasible for every $t > 0$ , and letting $t$ grow gives feasible points arbitrarily far from the origin.

(d) Empty. $x \geq 3$ forces $x^{2} \geq 9 > 4$ , so $x^{2} + y^{2} \leq 4$ cannot hold.

A complete answer does each of these:

correct classification
justification exhibited
objective independence

Error diagnosis · Explanation

A student writes:

The feasible set is $x \geq 0$ , which is unbounded. An unbounded feasible set means the problem has no optimal solution, so minimizing $x$ here has no answer.

Say precisely what is wrong with this reasoning, and give the correct answer.

Write your answer

Write your answer, then compare it with the worked solution.

2 hints available, least help first.

Hint 1: Retrieval cue

Ask whether the set being unbounded and the objective being unbounded are the same claim.

Hint 2: Next step

Try to find the smallest value $x$ can take while remaining feasible.

Compare with the worked solution

Comparing does not record a result. Judging your own written answer cannot show that you can do this without help.

The classification is right and the inference is wrong. The feasible set $x \geq 0$ is indeed unbounded, but boundedness of the set and existence of an optimum are separate questions. Minimising $x$ over $x \geq 0$ has the optimal solution $x = 0$ with optimal value 0.

An unbounded feasible set only permits the objective to be unimproved without limit; whether it actually is depends on the objective and its direction. Minimising $x$ is bounded below by 0; maximizing $x$ over the same set would have no optimum.

A complete answer does each of these:

correct classification
justification exhibited
objective independence

Practice data

Your practice record is stored in this browser only. Clearing it removes every answer and every scheduled review, and cannot be undone.

Practice: Feasible Sets

Recognition · Classification

Classification · Explanation

Error diagnosis · Explanation

Session complete

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history