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

Plot \(x+y\le6,\ x\ge0,\ y\ge0\). List feasible vertices.

Answer: Vertices: \((0,0)\), \((6,0)\), \((0,6)\).

Maximize \(P=2x+y\) on vertices \((0,0)\), \((4,0)\), \((1,3)\), \((0,3)\).

Answer: Values \(0,8,5,3\). Maximum \(8\) at \((4,0)\).

Minimize \(C=5x+3y\) with feasible vertices \((0,2)\), \((2,1)\), \((3,4)\).

Answer: \(C=6,13,27\). Minimum \(6\) at \((0,2)\).

In a model, why are \(x\ge0,\ y\ge0\) often included?

Answer: Quantities like items, time, or material cannot be negative.

How can you detect possible multiple optimal solutions graphically?

Answer: Objective line is parallel to a boundary edge where both edge endpoints give the same optimum value.

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.