Why can you skip infinitely many points?
Start with what a feasible region is (topic 01) and why the best point of a linear problem sits at one of its corners (02). Topic 16 is the algorithm that walks from corner to corner to find it, topic 03 shows that every such problem has a mirror problem whose answer is the price of each limit, and topic 17 lets the objective curve, ending at Goemans–Williamson's semidefinite relaxation of Max-Cut, the classical result that QAOA on the quantum side has to beat. Turn six of these shapes over in 3D →
Here is the thing that should bother you about the picture in topic 01: the feasible region contains infinitely many points. Any of them could be your plan. So how does anything ever get solved?
Because you never have to look inside. Push the objective line outward and it leaves the region at a corner. There are finitely many corners, so an infinite search collapses into a finite one. That collapse is the single most important fact in linear programming, and it is why a field about continuous quantities is computable at all.
The simplex method (Dantzig, 1947) simply walks from corner to neighbouring corner, never downhill, and stops when no neighbour is better. (Never downhill rather than always uphill: when a vertex is degenerate a step can move sideways for no gain, which is why anti-cycling rules exist.) Because the region is convex, no-better-than-any-neighbour means genuinely best. There are no local traps to get stuck in. That is a luxury you lose the moment the problem stops being convex, which is topic 04 and, later, topic 10.
The result being used is the fundamental theorem of linear programming: if a linear program has an optimal solution, then it has one at an extreme point (a vertex) of the feasible region.
The reason is convexity. Take any feasible point x that is not a vertex. Then x lies on a segment between two other feasible points, so it can be written as a blend:
x = λu + (1 − λ)v , 0 < λ < 1 , u, v feasible
so cᵀx = λ·cᵀu + (1 − λ)·cᵀv ≤ max(cᵀu, cᵀv)
A weighted average never exceeds its largest ingredient. So x is never strictly better than both of its neighbours, and you can always slide to an endpoint without losing anything. Repeat and you arrive at a vertex.
Complexity. Simplex is exponential in the worst case (Klee–Minty, 1972, constructed a cube whose every corner it visits under the standard pivot rule) and almost never behaves that way in practice. Linear programming as a problem is nonetheless in P: Khachiyan (1979) proved it with the ellipsoid method, which was theoretically decisive and practically useless, and Karmarkar (1984) gave the first polynomial algorithm that was also fast. Modern solvers run both simplex and interior-point and pick per instance.
Airline crew pairing An airline must cover every flight with a crew, obeying rest rules, base assignments, licence types and duty-hour limits, at minimum cost. The natural formulation has one variable per legal pairing (a multi-day sequence of flights that starts and ends at a crew base) and there can be billions of them. Nobody enumerates them. Instead the LP is solved over a small subset, and the dual prices from that solve are used to ask "does any pairing we have not generated look attractive?" That is column generation, and it is duality (topic 03) used as a search strategy. Crew is one of an airline's largest controllable costs, which is why a percent found here is worth a great deal.
Check yourself
A linear program's feasible region contains infinitely many plans. Why can it still be solved in finite time?
If an optimum exists, one exists at an extreme point (convexity: a blend of two plans is never better than the better of the two), so the search collapses to the finitely many corners.