Back to the on-screen lesson ·
Which points are allowed, why an optimum sits at a corner, and what infeasible and unbounded are telling you.
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 decide whether a point is feasible by checking every constraint, draw and describe a feasible region from linear inequalities, find a two-variable linear optimum by evaluating the objective at each vertex, and say why an interior point can never be optimal. You will also be able to read the four things a solver can report — optimal, many optima, unbounded, infeasible — and say which of them are solutions and which are diagnoses of your own formulation.
You can write a model in standard form and compute slack. You have also shaded regions defined by linear inequalities on a plane. This lesson puts those together: the constraints define a region, the objective is a family of parallel lines sweeping across it, and where the sweep stops is the answer.
Feasible region: the set of points satisfying every constraint at once — the intersection of what each one allows.
Vertex (corner): a feasible point where two boundary lines meet. A two-variable region has finitely many, and they are the only points a linear objective needs tested at.
Interior point: a feasible point with slack in every constraint. Every direction from it is still allowed.
Bounded: the region fits inside some large box. An unbounded region may still have an optimum; it depends on the objective.
Infeasible: the region is empty. The constraints contradict one another.
Unbounded: the region runs off in a direction the objective improves along for ever.
Half-space: the set of points on one side of a line, which is what a single linear inequality allows.
A point is feasible when it satisfies every constraint — every one, not most. The feasible region is the set of all feasible points, and for linear constraints it is a polyhedron: an intersection of half-spaces, with flat faces and sharp corners.
The objective is not a point but a direction. The set of points where $5x + 4y = c$ is a straight line, and different $c$ give parallel lines. Maximising means pushing that line as far as it goes while it still touches the region.
The fundamental theorem of linear programming. If a linear program has an optimal solution, one of the vertices of its feasible region is optimal.
That is a strong statement and it is why linear programs are solvable at all: a region with infinitely many points has finitely many corners, and only the corners need checking. For two variables this gives a complete method — list the corners, evaluate, compare.
Four outcomes.
| Outcome | The region | The objective |
|---|---|---|
| Optimal | non-empty | bounded on it |
| Many optima | non-empty | bounded, and parallel to a binding face |
| Unbounded | non-empty, unbounded | improves for ever |
| Infeasible | empty | nothing to evaluate |
Another way: picture
A shaded polygon with a ruler laid across it at a fixed angle. Slide the ruler, keeping its angle, in the direction the objective improves. The last position where it still touches the polygon is the optimum, and it touches at a corner unless the ruler happens to lie flat along an edge — in which case the whole edge is optimal.
Another way: steps
To solve a two-variable linear program by hand:
At an interior point, every constraint has slack, so a small step in any direction stays feasible — including the direction the objective improves along. So no interior point is optimal.
On a face but not at a corner, the same argument runs along the face: there is still a feasible direction that improves, unless the objective happens to be constant along that face. So the search comes to rest at a corner, or along an entire edge where the objective is flat.
This is the first place convexity does work, though it has not been named yet. The argument depends on the region having no dents: on a non-convex region a step towards a better point can leave the set, and the corners stop being enough. Unit 2 is where that becomes the organising idea of the course.
Checking one constraint. Feasibility is an and. A point that satisfies four constraints and violates the fifth is infeasible, and the objective value there is meaningless.
Treating a crossing point as a vertex. Two constraint lines always cross somewhere, but the crossing is a vertex only if it is feasible. Half the crossings in a typical problem are outside the region.
Reading unbounded as a big answer. Unbounded does not mean large; it means there is no answer. The correct response is to find the constraint that was left out.
Reading infeasible as bad news about the world. Far more often it means two constraints were written from the same rule, or a sign is wrong. A real workshop's schedule is always feasible — doing nothing is feasible.
They sound like two ends of a scale and they are not. Infeasible says the constraints cannot all hold at once — the region is empty, and there is nothing to evaluate anywhere. Unbounded says the region is perfectly fine and large, and the objective runs off along it. A model can also be neither, and a model cannot be both. The useful habit is that each points at a different repair: infeasible means a constraint is wrong or one too many, unbounded means one is missing. Reaching for the solver's settings in either case is reaching for the wrong thing.
Constraints $6x + 4y \le 24$, $x + 2y \le 6$, $x, y \ge 0$. Corners: $(0,0)$, $(4,0)$, $(0,3)$, and where the two lines cross.
List the candidates.
Solving $6x + 4y = 24$ with $x + 2y = 6$: double the second to $2x + 4y = 12$ and subtract, giving $4x = 12$, so $x = 3$ and $y = 1.5$.
The interesting corner.
Objective $5x + 4y$ at the four: $0$, $20$, $12$, $21$. The optimum is $21$ at $(3, 1.5)$, where both constraints bind. Four evaluations settled a region with infinitely many points.
Corners are enough.
$\max\ x + y$ subject to $x - y \le 1$, $x, y \ge 0$. The region is non-empty: $(0,0)$ is in it.
Feasible, so not the empty case.
Take $x = t$ and $y = t$ for any $t \ge 0$: the constraint reads $0 \le 1$, always true, and the objective is $2t$, which grows without limit.
A feasible ray along which the objective improves for ever.
So the model is unbounded. In a real problem this never means infinite profit; it means nothing said that a resource runs out. The fix is a constraint, not a solver setting.
Unbounded is a diagnosis.
It is feasible: $2 + 2 = 4 \le 4$, and both are non-negative. The first constraint is binding.
Feasibility first, then optimality.
The objective there is $12$. At $(4, 0)$ it is also $12$, and at $(0, 4)$ also $12$.
So yes, it is optimal — and so is every point of the edge between $(4,0)$ and $(0,4)$, because the objective $3x + 3y$ is parallel to the constraint $x + y \le 4$. This is the many-optima case, and it is a piece of information worth passing on: the person who asked now has a free choice among equally good plans.
Match each solver status to the response it calls for.
| Use the feasible best decision | Find a contradictory or over-tight constraint | Find the missing real-world limit | |
|---|---|---|---|
| Optimal | |||
| Infeasible | |||
| Unbounded |
Test the point $x = 4$, $y = 5$ against $2x + 1y \le 10$ and $1x + 1y \le 6$. Fill in what the point uses of each resource, and what is left.
| used at the point | available | left over | |
|---|---|---|---|
| First resource | 10 | ||
| Second resource | 6 |
Maximise $4x + 2y$ over $1x + 0y \le 4$, $3x + 2y \le 18$, $x, y \ge 0$. What is the optimal value?
Answer:
Put the steps of solving $\max\ 2x + 3y$ over $1x + 1y \le 4$, $1x + 3y \le 6$, $x, y \ge 0$ by hand into order.
Number the steps in order (write the number in the box):
With $y$ fixed at $0$, which values of $x$ satisfy $1x \le 5$ and $x \ge 0$?
This task has no paper form; do it on a device.
Why can an interior point of the feasible region never be optimal for the objective $4x + 3y$?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Maximise $5x + 4y$ over $6x + 4y \le 22$, $1x + 2y \le 5$, $x, y \ge 0$. What is the optimal value?
Answer:
You can check feasibility against every constraint, find an optimum at a vertex, and say what unbounded and infeasible tell you about the model. Next: models with many variables, written with indices instead of names.
10. Your turn: is $(2, 2)$ optimal for $\max\ 3x + 3y$ over $x + y \le 4$, $x, y \ge 0$?, step 3