Linear programming

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.

History

Linear programming developed in the 20th century for resource allocation and planning. George Dantzig's simplex method made large optimization problems practical in economics and operations research.

Derivation and reasoning

Why corner points matter

Objective lines \(ax+by=c\) are parallel for different \(c\). Sliding this line across a polygonal feasible region reaches the last contact at a vertex (or an entire edge in tie cases).

Checkpoints

Applications

• Production planning: maximize profit under labor and material limits.
• Transport/logistics: minimize cost with capacity constraints.
• Scheduling: optimize time allocation under availability rules.

References

• Standard high-school extension units on graphical linear programming.
• Introductory operations research texts on feasible regions and corner-point optimization.