La programación lineal (LP, también conocida como optimización lineal) es el campo de la programación matemática dedicado a maximizar o minimizar (optimizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones expresadas mediante un sistema de ecuaciones o inecuaciones también lineales. El método tradicionalmente usado para resolver problemas de programación lineal es el Método Simplex.

Los programas lineales son problemas que pueden ser expresados en su forma canónica como

${\displaystyle {\begin{array}{ll}{\text{Encontrar un vector }}&{\mathbf {x}}\\{\text{que maximice }}&{\mathbf {c}}^{T}{\mathbf {x}}\\{\text{sujeto a}}&A{\mathbf {x}}\leq {\mathbf {b}}\\{\text{y}}&{\mathbf {x}}\geq {\mathbf {0}}\end{array}}}$

donde ${\displaystyle {\mathbf {x}}}$ es el vector de variables que se desea determinar, ${\displaystyle {\mathbf {c}}}$ y ${\displaystyle {\mathbf {b}}}$ son vectores dados (con ${\displaystyle {\mathbf {c}}^{T}}$ indicando que los coeficientes de ${\displaystyle {\mathbf {c}}}$ son usados como una matriz de un solo renglón para que el producto matricial esté definido) y ${\displaystyle A}$ es una matriz dada. La función cuyo valor se va a maximizar o minimizar (en este caso ${\displaystyle {\mathbf {x}}\mapsto {\mathbf {c}}^{T}{\mathbf {x}}}$) es llamada función objetivo. Las desigualdades ${\displaystyle A{\mathbf {x}}\leq {\mathbf {b}}}$ y ${\displaystyle {\mathbf {x}}\geq {\mathbf {0}}}$ son las restricciones y forman la región factible o también conocida como región de factibilidad.