Back to the on-screen lesson ·
Solve each pair of boundary lines, then test the answer against everything the pair left out.
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 find every corner of a two-variable feasible region by solving each pair of active constraints and testing the result against the remaining rows, write the coefficient matrix of an active pair and use its determinant to say whether the lines cross, and recognise a point that several pairs name at once as a degenerate corner.
You can solve a pair of simultaneous linear equations, and you can draw a feasible region. A corner is the meeting point of those two abilities: solve the pair, then test the answer against everything the pair left out.
A constraint is active at a point when it holds with equality there. A candidate is the crossing of two boundary lines — the solution of the pair, before anything is checked. A candidate that satisfies every remaining constraint is a corner; one that does not is simply a point outside the region.
Finding the corners of a two-variable region is two steps that must not be run together. Solve: pick two boundary lines, set both constraints to equality, and solve the $2 \times 2$ system. The pair has exactly one solution when its coefficient determinant is non-zero, and none or infinitely many when the lines are parallel. Test: substitute that point into every other row. It is a corner only if all of them hold.
With $n$ boundary lines there are $\tfrac{n(n-1)}{2}$ pairs, so the candidate list is short and mechanical to build. Most of it is thrown away, and that is normal rather than a sign of error.
Two things can go wrong with the count. Parallel lines give no candidate at all. Three or more lines through one point give the same candidate several times over — a degenerate corner, which is harmless here and troublesome in unit 3.
Another way: steps
Another way: example
$2x_1 + 5x_2 = 100$ with $3x_1 + 2x_2 = 60$: the determinant is $4 - 15 = -11$, so there is one solution, $(\tfrac{100}{11}, \tfrac{180}{11})$. Both coordinates are positive, so it survives non-negativity and is a corner.
The test is skipped, and a crossing far outside the region is carried into the list of corners — where, being far out, it often has the best objective value of all. The second habit is solving a pair by substituting a guessed value rather than eliminating an unknown, which works until the coordinates stop being whole numbers.
Region $x \ge 0$, $y \ge 0$, $x \le 4$, $y \le 5$, $x + y \le 6$. Take the pair $x = 4$ and $y = 5$.
Two boundary lines.
They cross at $(4, 5)$ with no work at all: each line names one coordinate.
Solve the pair.
But $4 + 5 = 9$, which is more than $6$. The candidate fails the third row and is not a corner.
Test against what the pair left out.
Add the two equations: $2x = 14$, so $x = 7$.
Adding removes $y$.
Then $y = 10 - 7 = 3$, so the crossing is $(7, 3)$ — a candidate, until the other rows are checked.
The region is $x \ge 0$, $y \ge 0$, $x \le 8$, $y \le 5$, $x + y \le 12$. Solve each pair of boundary lines.
| $x$ at the crossing | $y$ at the crossing | |
|---|---|---|
| $x + y = 12$ with $x = 8$ | ||
| $x + y = 12$ with $y = 5$ | ||
| $x = 8$ with $y = 5$ |
At a corner the rows $x + 5y \le k$ and $4x + 2y \le m$ both hold with equality. Write the coefficient matrix of that pair, $x$ column first.
This task has no paper form; do it on a device.
The rows $3x + 2y = 17$ and $4x + y = 21$ are both active. Give the coordinates of the crossing.
Two constraint lines, both active at the point in question.
$x$ at the crossing:
$y$ at the crossing:
A two-variable program has $7$ boundary lines, counting the axes. Two of them cross. When is that crossing a corner of the feasible region?
You are given a two-variable program with $8$ constraints. Put the steps of solving it graphically into order.
Number the steps in order (write the number in the box):
In a two-variable program, $5$ boundary lines all pass through the same point. How many of the pairs of lines name that one point?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The region is $x \ge 0$, $y \ge 0$, $x \le 8$, $y \le 4$, $x + y \le 9$. Solve each pair of boundary lines.
| $x$ at the crossing | $y$ at the crossing | |
|---|---|---|
| $x + y = 9$ with $x = 8$ | ||
| $x + y = 9$ with $y = 4$ | ||
| $x = 8$ with $y = 4$ |
You can find the corners of a two-variable region by solving pairs and testing the answers. Say in your own words why solving a pair of constraints is not yet enough to call the answer a corner.
7. Your turn: where do $x + y = 10$ and $x - y = 4$ cross?, step 2