Back to the on-screen lesson ·
Every constraint keeps one side of a line; what survives is convex, closed, and sometimes empty or unbounded.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to draw the feasible region of a two-variable program as an intersection of half-planes, decide whether a given point is feasible by testing every row including non-negativity, compute each row's slack at a point, locate the corners of the region, and say which properties every feasible region has and which it may fail.
You can draw the line $ax + by = c$ and decide which side of it an inequality allows. A feasible region is nothing more than every such side, laid over one another.
Each constraint allows a half-plane: everything on one side of its boundary line. The feasible region is the intersection of them all. A constraint is binding at a point when it holds with equality there, and a corner — the word this course uses interchangeably with vertex — is a feasible point where two boundary lines cross.
With two variables, each row $ax + by \le c$ draws a line and keeps one side of it. Doing that for every row, non-negativity included, leaves a convex polygon — possibly unbounded, possibly empty.
Convex is the property everything later rests on: the segment joining any two feasible points is feasible, because each row is satisfied at both ends and a linear function between two values it accepts stays in between. Closed matters too, because the rows are $\le$ and $\ge$ rather than $<$ and $>$, so a best point that exists is actually reached.
What the region need not be is bounded, non-empty, or possessed of a single corner. Those three failures are answers in their own right, and lesson 8 is about reading them.
Another way: steps
Another way: picture
Lay three sheets of tracing paper over the same axes, each shaded on one side of a line. Hold them up together: the part that is dark on all three is the feasible region, and it turns a corner wherever two of the lines cross inside it.
Non-negativity is forgotten, which quietly admits a whole quadrant that the problem never allowed. The other habit worth breaking is treating every crossing of two boundary lines as a corner: most of them fall outside the region, and a crossing is only a corner if it satisfies every other row as well.
$2x_1 + 5x_2 \le 100$ and $3x_1 + 2x_2 \le 60$ with $x \ge 0$: four lines, four half-planes.
Two limits and two axes.
The axes give $(0, 0)$, and each limit crosses an axis at $(20, 0)$ and $(0, 20)$ respectively.
Crossings with the axes.
The two limits cross each other at $(\tfrac{100}{11}, \tfrac{180}{11})$, which satisfies both, so it is the fourth corner.
Four corners in all.
The first two rows want $x$ at least $2$ and at most $1$ at the same time.
Two half-planes that do not overlap.
No value of $x$ does both, so the region is empty and the program is infeasible whatever the objective says.
Plot every corner of the region $x \ge 0$, $y \ge 0$, $x \le 4$, $y \le 7$, $x + y \le 10$.
Plot your answer on the grid:
How many corners does this feasible region have: $x \ge 0$, $y \ge 0$, $x + y \le 4$?
Answer:
In the region $x \ge 0$, $y \ge 4$, $x + y \le 16$, which values of $x$ occur at some feasible point? Give the interval.
This task has no paper form; do it on a device.
Is this point feasible: $(5, 0)$ for $x + y \le 5$, $x \le 4$, $x, y \ge 0$?
Test the point $(2, 4)$ against $x + y \le 10$, $x \le 6$ and $y \le 8$. Fill in each row's left-hand side and its slack.
| Left-hand side | Limit | Slack | |
|---|---|---|---|
| $x + y \le 10$ | 10 | ||
| $x \le 6$ | 6 | ||
| $y \le 8$ | 8 |
Select every statement that is true of the feasible region of every linear program.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Plot every corner of the region $x \ge 0$, $y \ge 0$, $x \le 8$, $y \le 9$, $x + y \le 10$.
Plot your answer on the grid:
You can draw a feasible region, test a point against every row, and find the corners that survive. Say in your own words why the segment between two feasible points is always feasible.
7. Your turn: is the region $x \ge 2$, $x \le 1$, $y \ge 0$ empty?, step 2