Mathematics · Ch 13 — Linear Programming
Feasible and Infeasible Solutions
Feasible and Infeasible Solutions
Feasible solution. A feasible solution to a linear programming problem is any single point that satisfies EVERY constraint of the problem at once -- both the non-trivial constraints and the non-negative restrictions. This is a much broader notion than a corner point: every point lying anywhere inside the shaded feasible region, on its boundary edges, or at one of its corners, is a feasible solution -- there are, in general, infinitely many feasible solutions to any LPP whose feasible region is not a single point.
Infeasible solution. A point is called an infeasible solution if it fails to satisfy at least one constraint of the problem -- it need not fail all of them. This is an important distinction to keep straight: a point can satisfy three out of four constraints perfectly and still be infeasible overall, because an LPP requires ALL of its constraints to hold simultaneously, not merely most of them (Example 2 illustrates exactly this, with a point that satisfies the sum constraint but fails the bound on alone).
Checking feasibility of a given point. Given a specific candidate point and a list of constraints, feasibility is checked mechanically: substitute the point's coordinates into every constraint in turn (including ), and confirm that every single one holds. If even one constraint fails, the point is declared infeasible immediately -- there is no need to check the remaining constraints once a single failure is found, though identifying every constraint the point violates (not just the first one found) is often useful when explaining WHY a point is infeasible.
Feasible solution versus feasible region. The feasible region (Section 4) is the entire set of all feasible solutions considered together -- the shaded area itself. A feasible solution is a single point belonging to that set. This distinction matters because a question may ask either "is this particular point feasible?" (a Section-5 question about one solution) or "describe/shade the feasible region" (a Section-4 question about the whole set) -- and, most importantly for Section 6, the objective function can in principle be evaluated at ANY feasible solution, not only at a corner point, but it is only at the corner points that the OPTIMAL value (the largest or smallest value can take over the whole region) is guaranteed to occur. …