Practice: The Feasible Region of a Linear Program

Recognition · Classification

Which information is needed to determine whether a linear program's feasible region is empty, bounded, or unbounded?

1 hint available, least help first.

Hint 1: Retrieval cue

What does a point have to satisfy in order to be called feasible?

Classification

Consider the set defined by

x_{1} + x_{2} \geq 2, x_{1}, x_{2} \geq 0.

Select every statement that correctly describes this feasible region.

Select every option that applies

Every option that applies, and only those. The set is checked as a whole.

The region is nonempty.
The region is unbounded.
The region is empty, because the constraints conflict.
The region is bounded, because the variables are restricted to be nonnegative.
Every linear objective attains a finite optimum over this region.

Classification · Explanation

Classify each feasible region below as empty, bounded, or unbounded. For each one, name the constraints that produce your answer.

(a) $2 x_{1} + x_{2} \leq 6$ , $x_{1} \geq 0$ , $x_{2} \geq 0$

(b) $x_{1} - x_{2} \geq 2$ , $x_{1} + x_{2} \geq 4$ , $x_{1} \geq 0$ , $x_{2} \geq 0$

(c) $x_{1} + x_{2} \leq 2$ , $x_{1} \geq 3$ , $x_{2} \geq 0$

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, ask first whether any point satisfies all the constraints at once.

Hint 2: Strategy cue

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

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) Bounded. Nonnegativity gives $x_{1}, x_{2} \geq 0$ , and $2 x_{1} + x_{2} \leq 6$ forces $x_{1} \leq 3$ and $x_{2} \leq 6$ , so the region sits inside a finite box. (b) Unbounded. The point $(t, 0)$ satisfies $x_{1} - x_{2} = t \geq 2$ and $x_{1} + x_{2} = t \geq 4$ for every $t \geq 4$ , so the region extends without limit as $x_{1}$ grows. (c) Empty. $x_{1} \geq 3$ and $x_{2} \geq 0$ give $x_{1} + x_{2} \geq 3$ , which contradicts $x_{1} + x_{2} \leq 2$ , so no point is feasible.

A complete answer does each of these:

constraint justification
correct classification
objective independence

Error diagnosis · Explanation

A student writes:

"The feasible region of this program is unbounded, so the program has no optimal solution.

minimise $x_{1} + x_{2}$ subject to $x_{1} - x_{2} \leq 1$ , $x_{1} \geq 0$ , $x_{2} \geq 0$ "

The student is right that the region is unbounded. Explain why the conclusion does not follow, and state what the program's optimal value actually is.

Write your answer

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

2 hints available, least help first.

Hint 1: Retrieval cue

Is the objective being minimized or maximized, and does the region extend in a direction that helps?

Hint 2: Concept cue

Both variables are nonnegative. What is the smallest value $x_{1} + x_{2}$ can take, and is that point 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 region is indeed unbounded: $(0, t)$ is feasible for every $t \geq 0$ . But unboundedness of the region does not imply the objective is unbounded, because that also depends on the objective and the direction of optimization. Here the objective $x_{1} + x_{2}$ is nonnegative on the region since both variables are nonnegative, and it takes the value $0$ at $(0, 0)$ , which is feasible. So the minimum is $0$ , attained at $(0, 0)$ . The region extends without limit in directions along which this objective increases, not decreases.

A complete answer does each of these:

correct classification
objective independence
constraint justification

Practice: The Feasible Region of a Linear Program

Recognition · Classification

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