math concept
8 topics use this
Math concept
Linear Programming
Core equation
$$\min\, c^\top x \;\text{s.t.}\; Ax = b,\; x \geq 0$$
Linear programming optimises a linear objective over a polytope defined by linear constraints. The simplex algorithm and interior-point methods solve it in practice; duality theory gives deep economic interpretations.
Standard form
\[\min_{x} c^\top x \quad \text{subject to} \quad Ax = b, \quad x \geq 0\]Every LP can be put in this form. The feasible region is a polytope; the optimum (if it exists) lies at a vertex.
The simplex algorithm
Move between adjacent vertices of the feasible polytope, always decreasing the objective. Worst-case exponential but polynomial in practice — runs in $O(m^2 n)$ per pivot on $m$ constraints and $n$ variables.
LP duality
The dual of the standard-form LP is:
\[\max_y b^\top y \quad \text{subject to} \quad A^\top y \leq c\]Strong duality: primal and dual optima are equal. The dual variables $y^*$ are shadow prices — the marginal value of relaxing each constraint.
Applications
LP solves network flow, scheduling, resource allocation, and is a subroutine in branch-and-bound for integer programs and column generation for large-scale problems.
Fields that use this concept
Life sciences
Bioinformatics
Cooperative Games
Games where players form coalitions and share payoffs according to fairness axioms.
Nash Equilibrium
A strategy profile where no player can benefit by unilaterally deviating.
Engineering & CS
Operations research
Integer Programming
Optimization over integer or binary decision variables, essential for combinatorial problems in scheduling, routing, and resource allocation.
Linear Programming
Optimising a linear objective over a polytope. The simplex algorithm and interior-point methods are the two main solution approaches.
Network Flow
Optimising flows through networks — transportation, logistics, matching, and scheduling all reduce to network flow problems.
Job Scheduling
Minimizing makespan and completion times in single-machine, multi-machine, and project scheduling settings.
Traveling Salesman Problem
Find the shortest tour visiting all cities exactly once — a canonical NP-hard problem driving advances in combinatorial optimization and approximation algorithms.