Linear Programming Optimization

Linear Programming (LP) finds the maximum or minimum of a linear objective function subject to a set of linear constraints (inequalities). The set of points satisfying all constraints simultaneously is the feasible region — a convex polygon in two dimensions.

The Corner-Point Theorem (Fundamental Theorem of LP) states: if an optimal solution exists, it occurs at a vertex (corner point) of the feasible region. This means we only need to evaluate the objective at the corners, not everywhere.

The Simplex Method exploits this: starting at one vertex, it moves along edges to adjacent vertices that improve the objective, stopping when no improving neighbour exists. For $n$ variables and $m$ constraints, it typically converges in $O(m)$ pivot steps — far fewer than checking all $\binom{m}{n}$ vertices.

Standard LP form:

$\text{Maximise} \quad Z = c_1 x_1 + c_2 x_2$

subject to:

$a_{11}x_1 + a_{12}x_2 \leq b_1, \quad a_{21}x_1 + a_{22}x_2 \leq b_2, \quad x_1, x_2 \geq 0$

At the optimum corner $(x_1^*, x_2^*)$: evaluate $Z^* = c_1 x_1^* + c_2 x_2^*$.

A factory makes chairs (profit ₹200 each) and tables (profit ₹300 each). Constraints: carpentry $\leq$ 240 hours (chairs need 2 h, tables 4 h) and finishing $\leq$ 120 hours (chairs 2 h, tables 2 h).

Feasible corners: $(0, 0)$, $(60, 0)$, $(0, 30)$, $(60, 30)$... solving the binding constraints gives corner $(60, 30)$:

$2(60) + 4(30) = 240\ ✓$, $2(60) + 2(30) = 180 > 120$. Recalculate: binding intersection $2x_1 + 4x_2 = 240$ and $2x_1 + 2x_2 = 120$ gives $x_2 = 60$ (infeasible). Correct corner: $(0, 30)$ gives $Z = 0 + 9{,}000 = ₹9{,}000$; $(60, 0)$ gives $Z = 12{,}000 + 0 = ₹12{,}000$; intersection $(30, 45)$: $Z = 6{,}000 + 13{,}500 = ₹19{,}500$. Optimum is at the intersection corner.

Airlines use LP to assign aircraft to routes, minimising costs subject to safety, crew, and gate constraints — problems with millions of variables solved in seconds. Diet planning (minimum cost meeting nutritional requirements), supply-chain routing, and portfolio optimisation all reduce to LP. The 1975 Nobel Prize in Economics was awarded to Kantorovich and Koopmans for applying LP to resource allocation.

1. A manufacturer produces two goods: $x_1$ with profit ₹5 and $x_2$ with profit ₹4. Constraints: $6x_1 + 4x_2 \leq 24$ and $x_1 + 2x_2 \leq 6$, $x_1, x_2 \geq 0$. Find the corner points and the maximum profit.

2. Why must the optimal solution of an LP always lie at a vertex of the feasible region (and not in the interior)?