What does "optimising" actually mean?
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 →
Every problem in this field has exactly three parts, and once you see the pattern you cannot unsee it: the choices (what am I allowed to decide?), the limits (what stops me?), and the goal (what does better mean, as one number?).
Nurse rostering, parcel routing, factory scheduling, portfolio construction and airline crew pairing are the same three questions wearing different clothes. The feasible region is just the honest name for "the plans that are not fantasy".
The skill that takes longest to learn is not the solving: solvers are free and somebody else wrote them. It is writing the problem down correctly: noticing that "we should keep customers happy" is not yet a number, that "a driver cannot work 14 hours" is a constraint you forgot, and that the objective everyone agreed on in the meeting quietly rewards the wrong behaviour. Most failed optimisation projects failed here, not in the mathematics.
A linear program in standard form is:
maximise c₁x₁ + c₂x₂ + … + cₙxₙ
subject to a₁₁x₁ + … + a₁ₙxₙ ≤ b₁
a₂₁x₁ + … + a₂ₙxₙ ≤ b₂
⋮
x₁, x₂, …, xₙ ≥ 0
Each inequality is a half-space. The feasible region is the intersection of all of them, which makes it a convex polytope: convex meaning that if two plans are feasible, so is every blend of them. That single property is what the whole of linear programming rests on, and it is why the picture above has flat sides and sharp corners rather than curves.
Three things can happen. The region can be empty (infeasible. Your constraints contradict each other, which is a finding about your problem, not a failure of the solver). It can be unbounded in the direction you are pushing (you forgot a limit). Or it has an optimum, which is the interesting case and the subject of topic 02.
Refinery blending, since 1952 The first great industrial application, and still one of the largest. A refinery takes several crude streams with different sulphur, octane and density, and blends them into petrol, diesel and jet fuel that must each meet a specification. Choices: how much of each stream into each product. Limits: the specifications, the tank capacities, the demand. Objective: margin. Refineries have run linear programs for this since the 1950s, and the margins such a model finds are the difference between a profitable plant and a marginal one.
Check yourself
A solver reports that your linear program is infeasible. What does that tell you?
An empty feasible region means no plan satisfies every limit at once. That is information about the model (or the world), not about the solver.