Solving a Linear Programming Problem

A linear programming problem is not solved by guesswork — it is solved by systematically exploring the feasible region. The key idea is that the optimal value of the objective function, if it exists, always occurs at one of the corner points (vertices) of this region. So instead of checking every possible point, we only need to evaluate the objective function at these vertices. This is the foundation of the corner point method, which we will now apply step by step.

Key terms used when solving an LPP

Before applying the method, the book fixes five terms precisely — these are the vocabulary every later step relies on:

• Solution. Any set of values of the decision variables that satisfies the constraints of the LPP.
• Feasible solution. A solution that also satisfies the non-negativity restrictions ($x, y \ge 0$) — i.e. a set of values meeting every constraint together with $x, y \ge 0$.
• Infeasible solution. A set of values of the decision variables that does not satisfy all the constraints and the non-negativity condition — a point lying outside the feasible region.
• Feasible region. The common region determined by all the constraints, including the non-negativity conditions; every point of this region is a feasible solution of the LPP. …