Linear Programming — Optimizing Linear Objectives Under Linear Constraints

Both the objective function and every constraint must be linear — meaning each term is a constant multiplied by a single decision variable, with no products of variables, no exponents, and no nonlinear functions. If even one constraint or the objective involves, say, x times y or x squared, standard LP no longer applies and a nonlinear or quadratic programming solver is needed.

The feasible region defined by linear constraints is a convex polyhedron (or polytope). A linear objective function is itself linear, so it cannot be 'pulled' toward the interior of a convex set — it always achieves its extreme value on the boundary, and specifically at a vertex (corner point). This is the geometric insight underlying the Simplex method's vertex-to-vertex strategy.

Whenever one or more decision variables must take integer or binary (0/1) values — for example, whether to open a facility (yes/no), how many trucks to dispatch (whole numbers), or which items to include in a selection. Simply solving the LP and rounding the continuous solution is not reliable: rounded solutions can be infeasible or far from optimal. Integer programming handles integrality correctly, at greater computational cost.

A shadow price (dual variable) for a binding constraint indicates how much the optimal objective value would improve if that constraint's right-hand-side were relaxed by one unit, holding everything else constant. For example, a shadow price of 3 on a labour-hours constraint means that adding one more hour of labour would improve the objective by 3 units. Constraints that are not binding have a shadow price of zero — they are not limiting the current optimum.