Summary

Linear programming. A linear programming problem (LPP) optimizes (maximizes or minimizes) a linear objective function $Z=ax+by$ in decision variables $x,y$, subject to linear constraints (each of $\le$ or $\ge$ type, arising from resource limits or minimum requirements) and the non-negative restrictions $x\ge0,\ y\ge0$. This chapter works with up to three non-trivial constraints, so the resulting feasible region -- a triangle, quadrilateral, or pentagon -- can be drawn and solved accurately by hand.

Formulating an LPP. Name the decision variables, write the quantity to be optimized as $Z=ax+by$ using the given per-unit rates, translate each resource limit or requirement into one linear inequality using the given per-unit figures, and append $x,y\ge0$.

Graphical method. For each constraint $px+qy\le H$ (or $\ge$), plot the boundary line $px+qy=H$ (via its intercepts $x=H/p,\ y=H/q$), use a test point (usually the origin) to decide which half-plane satisfies the inequality, and shade the region common to every required half-plane -- the feasible region. Its corner points are found by solving pairs of boundary equations simultaneously, keeping only intersections that also satisfy every other constraint.

Bounded vs. unbounded regions.

For a bounded region, the optimal value is guaranteed to occur at a corner point. For an unbounded region, a candidate optimal value from the corners must be confirmed by the half-plane test: if the open half-plane $\{ax+by>k\}$ (for a maximum) or $\{ax+by<k\}$ (for a minimum) shares no point with the feasible region, $k$ is the genuine optimal value; otherwise no such optimal value exists (commonly: a minimum exists but a maximum does not, when $a,b>0$ and the region recedes outward).

Feasible vs. infeasible solutions. A feasible solution is any single point satisfying every constraint at once; an infeasible solution violates at least one constraint (it may satisfy all the others). The feasible region is the entire set of feasible solutions; a feasible solution is one point of that set. …