The Chapter in One Sweep

A Linear Programming Problem: find the optimal (maximum or minimum) value of a linear objective function Z=ax+byZ = ax + by subject to linear constraints and the non-negative restrictions x,y≥0x, y \geq 0. The x,yx, y are decision variables; formulation is the four-move recipe — name variables, write ZZ, translate each resource (≤\leq) or requirement (≥\geq) into an inequality, add non-negativity.

Feasible region OABC for the furniture dealer problem with optimum corner

The engine

The constraints carve out the feasible region — the convex common region of all half-planes. Theorem 1: an optimal value, when it exists, occurs at a corner point. Theorem 2: a bounded region guarantees both a maximum and a minimum, at corners.

The Corner Point Method: draw the region → find the corners (solve intersecting line pairs) → tabulate ZZ at each corner → largest is MM, smallest is mm → bounded: done; unbounded: run the half-plane test.

Bounded region with corner values and unbounded region needing the half plane test

The decision table

Region Maximum Minimum
Bounded MM, at a corner mm, at a corner
Unbounded MM only if ax+by>Max + by > M misses the region; else none mm only if ax+by<max + by < m misses the region; else none
Empty no feasible solution no feasible solution

Ties: equal optimal values at two corners extend to every point of the joining segment — infinitely many optimal solutions, occurring when the objective line is parallel to that edge.

Applied Problems, and the Mistake Checklist

The three applied archetypes

  1. Diet (minimise cost; nutrient floors, ≥\geq; region unbounded — test mandatory).
  2. Manufacturing (maximise profit; resource ceilings, ≤\leq; region bounded).
  3. Allocation (capital + space/count ceilings; maximise profit or item count).

Conclude applied answers in the story's language: items, rupees, kilograms — not bare coordinates.

The mistake checklist — run it before submitting

  1. Shaded the right side? Test each half-plane with the origin (or any convenient point off the line).
  2. All corners found? Every pair of adjacent boundary lines meets at one — including the axis intercepts.
  3. Evaluated only at feasible corners? A tempting point that violates one constraint is worthless.
  4. Region unbounded? Then the corner table alone proves nothing — write the half-plane test.
  5. Tie in the table? Report the whole segment, not one endpoint.
  6. Units consistent? Convert kg to g, rupees to the same scale, before writing constraints.
  7. Non-negativity written? x≥0,y≥0x \geq 0, y \geq 0 appears in every formulation, every time.
  8. Conclusion sentence naming the optimal value AND where it occurs (in context for word problems).

Where each skill was built

Formulation and vocabulary — Section 1. The graphical method and theorems — Section 2. Graded worked problems — Section 3. Board practice — Section 4. Diet, manufacturing and allocation word problems — Section 5. Full drill — Section 6.