Linear programming finds the best value (maximum or minimum) of a linear objective under linear constraints. In high school, we solve two-variable problems graphically.

Core idea

Optimize an objective like \[ P=ax+by \] subject to inequalities such as \(x+y\le 12\), \(x\ge0\), \(y\ge0\).

Modeling from context

Typical setup:

1. Define variables (\(x,y\)).
2. Write constraints from limits/resources.
3. Write objective function (profit, cost, time, etc.).
4. Graph constraints and find feasible region.

Graphing constraints

For each inequality:

• Draw boundary line (use solid line for \(\le,\ge\); dashed for \(<,>\)).
• Test a point (often origin) to choose correct side.
• Combine all valid half-planes.

Include non-negativity constraints \(x\ge0,y\ge0\) unless problem states otherwise.

Feasible region

The feasible region is where all constraints hold at once. In school-level cases, it is usually a polygon (possibly unbounded).

Corner-point principle

If an optimum exists for a bounded feasible region, it occurs at a vertex (corner point).

So compute all feasible vertices, then evaluate objective at each.

Worked example

Maximize \(P=3x+2y\) subject to:

\[ x+y\le 8,\quad x+3y\le 12,\quad x\ge0,\ y\ge0. \]

Vertices are \((0,0)\), \((8,0)\), \((0,4)\), and intersection of \(x+y=8\) with \(x+3y=12\), which is \((6,2)\).

Evaluate:

• \((0,0)\Rightarrow P=0\)
• \((8,0)\Rightarrow P=24\)
• \((0,4)\Rightarrow P=8\)
• \((6,2)\Rightarrow P=22\)

Maximum is \(24\) at \((8,0)\).

Special cases

• No feasible region: constraints are inconsistent.
• Unbounded region: objective may have no maximum/minimum.
• Multiple optima: objective line parallel to a feasible edge.

Exam strategy

• Label all boundary lines and intercepts clearly.
• Show shading logic for each inequality.
• List vertex coordinates before evaluating objective.
• Give final answer with units and variable interpretation.