Back to the on-screen lesson ·
Infeasible, unbounded, tied and degenerate: what each verdict says, and which of them are answers.
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 tell the four outcomes of a linear program apart, say which of them leave no optimal solution and which leave too many, find the objective coefficient at which a tie occurs, and put the questions of feasibility, improvement, limit and tie into the order an algorithm can answer them.
You can find a feasible region and the best corner of it. This lesson is about the programs where that sentence does not apply — and three of the four cases are still answers worth reporting.
Infeasible: no point satisfies every constraint. Unbounded: feasible points exist and the objective improves without limit. Multiple optima: a whole edge or face of equally good plans. Degenerate: an optimal corner where more constraints are active than the number of variables requires.
Solving a linear program does not always end with one plan, and the ways it can end otherwise are worth knowing by name.
Infeasible is a statement about the constraints: they contradict each other, and no objective can rescue that. Unbounded is a statement about the pair of objective and region: the improving direction runs off for ever. Both are proofs, and both usually mean a constraint was left out — real resources are finite, so an unbounded model is nearly always an incomplete one.
Multiple optima happen when the level lines are parallel to a binding edge. Far from being a failure, this is room to choose on grounds the model never held: which plan is easier, safer, more familiar.
Degeneracy is the odd one out. The answer is fine; what is at risk is the algorithm, which can change basis without moving and, in principle, cycle for ever. Unit 3 says what is done about it.
Another way: steps
Another way: picture
Four sketches on the same axes: an empty overlap; a wedge open to the north-east with the ruler sliding out of the page; a ruler lying flat along one edge; and three lines meeting at one corner where two would have done.
An unbounded region is read as an unbounded problem. Minimising a cost over the whole first quadrant is perfectly bounded, and it is the direction the objective improves in that decides. The second error is treating a tie as a failure to solve, when it is an abundance of solutions; the third is reading degeneracy as a wrong answer, when it is a remark about which constraints happen to meet.
Minimise $2x + 3y$ over $x \ge 0$, $y \ge 0$: the region runs off to infinity in both directions.
The region is unbounded.
But the objective improves by going down, and both variables are bounded below by zero.
The improving direction is bounded.
So the optimum is $0$ at the origin. Unbounded region, single optimal corner.
Two different claims.
The level lines of $3x + 3y$ have slope $-1$, and so does the edge $x + y = 7$.
Parallel to a binding edge.
So every point of that edge is optimal and the value is $21$: multiple optima, with two optimal corners.
Match each program to what happens when it is solved.
| The objective improves without limit | No point satisfies every constraint | A whole edge of optimal points | An optimal corner with a constraint to spare | |
|---|---|---|---|---|
| maximise $x + y$ subject to $x \ge 0$, $y \ge 0$ | ||||
| maximise $x$ subject to $x \le 1$ and $x \ge 4$ | ||||
| maximise $2x + 2y$ subject to $x + y \le 9$, $x, y \ge 0$ | ||||
| maximise $x + 2y$ subject to $x + y \le 9$, $y \le 9$, $x, y \ge 0$ |
Which special case is this: maximise $x - y$ subject to $x - y \le 3$, $x, y \ge 0$?
A bounded feasible polygon has $5$ corners, and the objective's level lines are parallel to one of its edges, which is where the optimum lies. How many of the corners are optimal?
Answer:
Select every program below that has no optimal solution at all.
This task has no paper form; do it on a device.
The binding constraint is $3x + 7y \le m$ and the objective is $12x + cy$. For which $c$ are the objective's level lines parallel to that constraint? Give the answer as a set.
This task has no paper form; do it on a device.
A solver is handed a program with $5$ constraints and must report one of the four outcomes. Put its questions into the order it can answer them.
Number the steps in order (write the number in the box):
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Match each program to what happens when it is solved.
| The objective improves without limit | No point satisfies every constraint | A whole edge of optimal points | An optimal corner with a constraint to spare | |
|---|---|---|---|---|
| maximise $x + y$ subject to $x \ge 0$, $y \ge 0$ | ||||
| maximise $x$ subject to $x \le 2$ and $x \ge 5$ | ||||
| maximise $4x + 4y$ subject to $x + y \le 9$, $x, y \ge 0$ | ||||
| maximise $x + 2y$ subject to $x + y \le 9$, $y \le 9$, $x, y \ge 0$ |
You can name the four outcomes of a linear program and say what each one reports. Say in your own words why an unbounded feasible region does not make a program unbounded.
7. Your turn: maximise $3x + 3y$ subject to $x + y \le 7$, $x, y \ge 0$, step 2