Programación lineal

La programación lineal ( PL ), también llamada optimización lineal , es un método para lograr el mejor resultado (como la máxima ganancia o el menor costo) en un modelo matemático cuyos requisitos y objetivo se representan mediante relaciones lineales . La programación lineal es un caso especial de la programación matemática (también conocida como optimización matemática ).

Formalmente, la programación lineal es una técnica para la optimización de una función objetivo lineal , sujeta a restricciones de igualdad y desigualdad lineales . Su región factible es un politopo convexo , que es un conjunto definido como la intersección de un número finito de semiplanos , cada uno de los cuales está definido por una desigualdad lineal . Su función objetivo es una función afín (lineal) de valores reales definida en este politopo. Un algoritmo de programación lineal encuentra un punto en el politopo donde esta función tiene el valor máximo (o mínimo), si dicho punto existe.

Los programas lineales son problemas que pueden expresarse en forma estándar como:

${\displaystyle {\begin{aligned}&{\text{Encuentra un vector}}&&\mathbf {x} \\&{\text{que maximiza}}&&\mathbf {c} ^{\mathsf {T}}\mathbf {x} \\&{\text{sujeto a}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{y}}&&\mathbf {x} \geq \mathbf {0}.\end{aligned}}}$

Aquí los componentes de${\displaystyle \mathbf {x} }$son las variables a determinar,${\displaystyle \mathbf {c} }$y${\displaystyle \mathbf {b} }$se dan vectores , y${\displaystyle A}$es una matriz dada . La función cuyo valor debe maximizarse (${\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x} }$en este caso) se denomina función objetivo . Las restricciones${\displaystyle A\mathbf {x} \leq \mathbf {b} }$y${\displaystyle \mathbf {x} \geq \mathbf {0} }$Especificar un politopo convexo sobre el cual se optimizará la función objetivo.

La programación lineal se puede aplicar a diversos campos de estudio. Se utiliza ampliamente en matemáticas y, en menor medida, en negocios, economía y algunos problemas de ingeniería. Existe una estrecha relación entre los programas lineales, las ecuaciones de autovalores, el modelo de equilibrio general de John von Neumann y los modelos de equilibrio estructural (véase el programa lineal dual para más detalles). ^{[ 1 ] [ 2 ] [ 3 ]} Entre las industrias que utilizan modelos de programación lineal se incluyen el transporte, la energía, las telecomunicaciones y la manufactura. Ha demostrado ser útil para modelar diversos tipos de problemas en planificación , enrutamiento , programación , asignación y diseño.

El problema de resolver un sistema de desigualdades lineales se remonta al menos a Fourier , quien en 1827 publicó un método para resolverlas, ^{[ 4 ]} y de quien toma su nombre el método de eliminación de Fourier-Motzkin .

A finales de la década de 1930, el matemático soviético Leonid Kantorovich y el economista estadounidense Wassily Leontief investigaron de forma independiente las aplicaciones prácticas de la programación lineal. Kantorovich se centró en la planificación de la producción, mientras que Leontief exploró sus aplicaciones económicas. Su innovador trabajo pasó prácticamente desapercibido durante décadas.

El punto de inflexión se produjo durante la Segunda Guerra Mundial, cuando la programación lineal se consolidó como una herramienta fundamental. Su uso se extendió a la resolución de complejos desafíos bélicos, como la logística del transporte, la planificación y la asignación de recursos. La programación lineal demostró ser invaluable para optimizar estos procesos, teniendo en cuenta restricciones críticas como los costos y la disponibilidad de recursos.

A pesar de su inicial desconocimiento, los éxitos obtenidos durante la guerra impulsaron la programación lineal a la palestra. Tras la Segunda Guerra Mundial, el método alcanzó un amplio reconocimiento y se convirtió en una piedra angular en diversos campos, desde la investigación operativa hasta la economía. Las contribuciones, a menudo ignoradas, de Kantorovich y Leontief a finales de la década de 1930 resultaron fundamentales para la mayor aceptación y utilización de la programación lineal en la optimización de los procesos de toma de decisiones. ^{[ 5 ]}

El trabajo de Kantorovich fue inicialmente ignorado en la URSS . ^{[ 6 ]} Casi al mismo tiempo que Kantorovich, el economista neerlandés-estadounidense TC Koopmans formuló problemas económicos clásicos como programas lineales. Kantorovich y Koopmans compartieron posteriormente el Premio Nobel de Economía de 1975. ^{[ 4 ]} En 1941, Frank Lauren Hitchcock también formuló problemas de transporte como programas lineales y dio una solución muy similar al posterior método simplex . ^{[ 7 ]} Hitchcock había fallecido en 1957, y el Premio Nobel no se otorga póstumamente.

De 1946 a 1947, George B. Dantzig desarrolló de forma independiente una formulación general de programación lineal para su uso en problemas de planificación en la Fuerza Aérea de los Estados Unidos. ^{[ 8 ]} En 1947, Dantzig también inventó el método simplex que, por primera vez, abordó eficientemente el problema de programación lineal en la mayoría de los casos. ^{[ 8 ]} Cuando Dantzig organizó una reunión con John von Neumann para discutir su método simplex, von Neumann inmediatamente conjeturó la teoría de la dualidad al darse cuenta de que el problema en el que había estado trabajando en teoría de juegos era equivalente. ^{[ 8 ]} Dantzig proporcionó una prueba formal en un informe inédito titulado "Un teorema sobre desigualdades lineales" el 5 de enero de 1948. ^{[ 6 ]} El trabajo de Dantzig se puso a disposición del público en 1951. En los años de la posguerra, muchas industrias lo aplicaron en su planificación diaria.

El ejemplo original de Dantzig consistía en encontrar la mejor asignación de 70 personas a 70 puestos de trabajo. La capacidad de cálculo necesaria para probar todas las permutaciones y seleccionar la mejor asignación es enorme; el número de configuraciones posibles supera el número de partículas en el universo observable . Sin embargo, basta con un instante para encontrar la solución óptima planteando el problema como un programa lineal y aplicando el algoritmo simplex . La teoría de la programación lineal reduce drásticamente el número de soluciones posibles que deben comprobarse.

Leonid Khachiyan demostró por primera vez en 1979 que el problema de programación lineal podía resolverse en tiempo polinomial, ^{[ 9 ]} pero un avance teórico y práctico más significativo en este campo se produjo en 1984, cuando Narendra Karmarkar introdujo un nuevo método de punto interior para resolver problemas de programación lineal. ^{[ 10 ]}

La programación lineal es un campo de optimización ampliamente utilizado por varias razones. Muchos problemas prácticos en la investigación operativa pueden expresarse como problemas de programación lineal. ^{[ 6 ]} Ciertos casos especiales de programación lineal, como los problemas de flujo de red y los problemas de flujo de múltiples mercancías , se consideran lo suficientemente importantes como para que exista mucha investigación sobre algoritmos especializados. Varios algoritmos para otros tipos de problemas de optimización funcionan resolviendo problemas de programación lineal como subproblemas. Históricamente, las ideas de la programación lineal han inspirado muchos de los conceptos centrales de la teoría de la optimización, como la dualidad, la descomposición y la importancia de la convexidad y sus generalizaciones. Asimismo, la programación lineal se utilizó ampliamente en la formación inicial de la microeconomía y actualmente se utiliza en la gestión empresarial, por ejemplo, en la planificación, la producción, el transporte y la tecnología. Aunque los problemas de gestión modernos están en constante cambio, la mayoría de las empresas buscan maximizar las ganancias y minimizar los costos con recursos limitados. Google también utiliza la programación lineal para estabilizar los videos de YouTube. ^{[ 11 ]}

La forma estándar es la forma habitual y más intuitiva de describir un problema de programación lineal. Consta de las siguientes tres partes:

• Una función lineal (o afín) que se desea maximizar.

p.ej${\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}}$

• Restricciones del problema de la siguiente forma

p.ej

${\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}}$

• Variables no negativas

p.ej

${\displaystyle {\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}}$

El problema se suele expresar en forma matricial y, por lo tanto, queda así:

${\displaystyle \max\{\,\mathbf {c} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}}$

Otras formas, como los problemas de minimización, los problemas con restricciones en formas alternativas y los problemas que involucran variables negativas , siempre se pueden reescribir como un problema equivalente en forma estándar.

Ejemplo

Supongamos que un agricultor tiene una parcela de tierra agrícola, digamos L hectáreas , para sembrar trigo, cebada o una combinación de ambos. El agricultor dispone de _F kilogramos de fertilizante y P kilogramos de pesticida. Cada hectárea de trigo requiere F1 kilogramos de fertilizante y P1 _kilogramos de pesticida, mientras que cada hectárea de cebada requiere F2 _kilogramos de fertilizante y P2 kilogramos de pesticida. Sea S1 _{el precio} de venta del trigo y S2 _{el precio de venta de la cebada por hectárea. Si denotamos la superficie sembrada con trigo y cebada por x1 y x2} respectivamente , entonces el beneficio se puede maximizar eligiendo valores óptimos para x1 _y x2 . Este problema se puede expresar con el siguiente problema de programación lineal en su forma estándar _:

En forma matricial, esto se convierte en:

maximizar${\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}$

sujeto a${\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.}$

Los problemas de programación lineal se pueden convertir a una forma aumentada para aplicar la forma común del algoritmo simplex . Esta forma introduce variables de holgura no negativas para reemplazar las desigualdades por igualdades en las restricciones. Los problemas se pueden escribir entonces en la siguiente forma de matriz de bloques :

Maximizar${\displaystyle z}$:

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{\mathsf {T}}&\mathbf {0} ^{\mathsf {T}}\\\mathbf {0} &\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}}$

${\displaystyle \mathbf {x} \geq \mathbf {0} ,\mathbf {s} \geq \mathbf {0} }$

dónde${\displaystyle \mathbf {s} }$son las variables de holgura recientemente introducidas,${\displaystyle \mathbf {x} }$son las variables de decisión, y${\displaystyle z}$es la variable que se va a maximizar.

Todo problema de programación lineal, denominado problema primal , puede convertirse en un problema dual , que proporciona una cota superior para el valor óptimo del problema primal. En forma matricial, podemos expresar el problema primal como:

Maximizar c ^T x sujeto a A x ≤ b , x ≥ 0;

con el problema dual simétrico correspondiente,

Minimizar b ^T y sujeto a A ^T y ≥ c , y ≥ 0.

Una formulación primal alternativa es:

Maximizar c ^T x sujeto a A x ≤ b ;

con el problema dual asimétrico correspondiente,

Minimizar b ^T y sujeto a A ^T y = c , y ≥ 0.

Una idea fundamental de la teoría de la dualidad es el hecho de que (para el dual simétrico) el dual de un programa lineal dual es el programa lineal primal original.

Las variables duales${\displaystyle \mathbf {y} }$pueden entenderse como coeficientes en una combinación lineal de desigualdades del problema primal, formadas con la esperanza de obtener una cota para la función objetivo. Dichos coeficientes deben ser no negativos, ya que de lo contrario las desigualdades se invertirían, de donde requerimos${\displaystyle \mathbf {y} \geq \mathbf {0} }$. Si además${\displaystyle \mathbf {c} ^{\top }\leq \mathbf {y} ^{\top }\!A}$Entonces se deduce que $${\displaystyle \mathbf {c} ^{\top }\mathbf {x} \leq \mathbf {y} ^{\top }\!A\mathbf {x} \leq \mathbf {y} ^{\top }\mathbf {b} =\mathbf {b} ^{\top }\mathbf {y} {\text{,}}}$$ es decir, el valor de la función objetivo dual${\displaystyle \mathbf {b} ^{\top }\mathbf {y} }$en cualquier punto dual factible${\displaystyle \mathbf {y} }$es un límite superior para el valor de la función objetivo primal${\displaystyle \mathbf {c} ^{\top }\mathbf {x} }$en cualquier punto primigenio factible${\displaystyle \mathbf {x} }$. Este es el principio de dualidad débil . El teorema de dualidad fuerte establece que esta cota es de hecho ajustada: si el primal tiene una solución óptima, x ^* , entonces el dual también tiene una solución óptima, y ^​​* , y c ^T x ^* = b ^T y ^* .

Un programa lineal también puede ser no acotado o infactible. La teoría de la dualidad establece que si el problema primal no está acotado, entonces el dual es infactible según el teorema de dualidad débil. Del mismo modo, si el dual no está acotado, entonces el primal debe ser infactible. Sin embargo, es posible que tanto el dual como el primal sean infactibles. Consulte el apartado de programación lineal dual para obtener más detalles y varios ejemplos adicionales.

Es posible obtener una solución óptima para el problema dual cuando solo se conoce una solución óptima para el problema primal utilizando el teorema de holgura complementaria. El teorema establece:

Supongamos que x  =  ( x ₁ , x ₂ , ... , x _n ) es factible primalmente y que y = ( y ₁ , y ₂ , ... , y _m ) es factible dualmente. Sean ( w ₁ , w ₂ , ..., w _m ) las variables de holgura primales correspondientes, y sean ( z ₁ , z ₂ , ... , z _n ) las variables de holgura duales correspondientes. Entonces x e y son óptimos para sus respectivos problemas si y solo si                 

• x _j z _j  =  0, para j  =  1,  2,  ...  , n y 
• w _i y _i  =  0, para i  =  1,  2,  ...  , m . 

Así, si la i -ésima variable de holgura del problema primal no es cero, entonces la i -ésima variable del problema dual es igual a cero. Del mismo modo, si la j -ésima variable de holgura del problema dual no es cero, entonces la j -ésima variable del problema primal es igual a cero.

Esta condición necesaria para la optimalidad transmite un principio económico bastante simple. En su forma estándar (al maximizar), si existe holgura en un recurso primario restringido (es decir, hay "sobrantes"), entonces las cantidades adicionales de ese recurso no deben tener valor. Del mismo modo, si existe holgura en el requisito de no negatividad del precio dual (o sombra), es decir, el precio no es cero, entonces debe haber escasez de suministros (no hay "sobrantes").

Existen varios problemas abiertos en la teoría de la programación lineal, cuya solución representaría avances fundamentales en matemáticas y, potencialmente, grandes progresos en nuestra capacidad para resolver programas lineales a gran escala.

• ¿Admite la programación lineal un algoritmo de tiempo fuertemente polinomial ?
• ¿Admite la programación lineal un algoritmo de tiempo fuertemente polinomial para encontrar una solución estrictamente complementaria?
• ¿Admite la programación lineal un algoritmo de tiempo polinomial en el modelo de computación de números reales (coste unitario)?

Este conjunto de problemas estrechamente relacionados ha sido citado por Stephen Smale como uno de los 18 mayores problemas sin resolver del siglo XXI. En palabras de Smale, la tercera versión del problema "es el principal problema sin resolver de la teoría de la programación lineal". Si bien existen algoritmos para resolver la programación lineal en tiempo débilmente polinomial , como los métodos elipsoidales y las técnicas de punto interior , aún no se han encontrado algoritmos que permitan un rendimiento en tiempo fuertemente polinomial en cuanto al número de restricciones y el número de variables. El desarrollo de tales algoritmos sería de gran interés teórico y, quizás, también permitiría obtener ventajas prácticas en la resolución de grandes problemas de programación lineal.

Aunque la conjetura de Hirsch fue refutada recientemente para dimensiones superiores, aún deja abiertas las siguientes preguntas.

• ¿Existen reglas de pivote que den lugar a variantes del simplex de tiempo polinomial?
• ¿Todos los grafos politópicos tienen un diámetro acotado polinómicamente?

Estas preguntas se refieren al análisis del rendimiento y al desarrollo de métodos tipo simplex. La enorme eficiencia del algoritmo simplex en la práctica, a pesar de su rendimiento teórico exponencial, sugiere que podrían existir variantes que se ejecuten en tiempo polinomial o incluso fuertemente polinomial. Sería de gran importancia práctica y teórica saber si existen tales variantes, especialmente como método para determinar si la programación lineal puede resolverse en tiempo fuertemente polinomial.

El algoritmo simplex y sus variantes pertenecen a la familia de algoritmos de seguimiento de aristas, llamados así porque resuelven problemas de programación lineal moviéndose de vértice a vértice a lo largo de las aristas de un politopo. Esto significa que su rendimiento teórico está limitado por el número máximo de aristas entre dos vértices cualesquiera del politopo LP. Por consiguiente, nos interesa conocer el diámetro máximo teórico de grafos de los grafos politópicos . Se ha demostrado que todos los politopos tienen un diámetro subexponencial. La reciente refutación de la conjetura de Hirsch es el primer paso para demostrar si algún politopo tiene un diámetro superpolinomial. Si existen tales politopos, entonces ninguna variante de seguimiento de aristas puede ejecutarse en tiempo polinomial. Las cuestiones sobre el diámetro de los politopos tienen un interés matemático independiente.

Los métodos de pivote simplex preservan la factibilidad primal (o dual). Por otro lado, los métodos de pivote cruzado no preservan la factibilidad (primal o dual) ; pueden visitar bases primal factibles, duales factibles o primal y dual infactibles en cualquier orden. Los métodos de pivote de este tipo se han estudiado desde la década de 1970. ^{[ 29 ]} Esencialmente, estos métodos intentan encontrar la ruta de pivote más corta en el politopo de arreglo bajo el problema de programación lineal. A diferencia de los grafos politópicos, se sabe que los grafos de politopos de arreglo tienen un diámetro pequeño, lo que permite la posibilidad de un algoritmo de pivote cruzado de tiempo fuertemente polinomial sin resolver cuestiones sobre el diámetro de los politopos generales. ^{[ 15 ]} 

Si todas las variables desconocidas deben ser números enteros, el problema se denomina programación entera (PI) o programación lineal entera (PLI). A diferencia de la programación lineal, que puede resolverse eficientemente en el peor de los casos, los problemas de programación entera son, en muchas situaciones prácticas (aquellas con variables acotadas), NP-difíciles . La programación entera 0-1 o programación entera binaria (PIB) es un caso especial de programación entera donde las variables deben ser 0 o 1 (en lugar de enteros arbitrarios). Este problema también se clasifica como NP-difícil, y de hecho, la versión de decisión fue uno de los 21 problemas NP-completos de Karp .

Si solo algunas de las variables desconocidas deben ser números enteros, el problema se denomina programación lineal entera mixta (MIP o MILP). Estos problemas suelen ser NP-difíciles, ya que son aún más generales que los programas de programación lineal entera (ILP).

Sin embargo, existen algunas subclases importantes de problemas de programación entera y programación entera mixta que se pueden resolver de manera eficiente, sobre todo los problemas en los que la matriz de restricciones es totalmente unimodular y los lados derechos de las restricciones son enteros o, de forma más general, en los que el sistema tiene la propiedad de integralidad dual total (TDI).

Los algoritmos avanzados para resolver programas lineales enteros incluyen:

• método del plano de corte
• Ramificar y enlazar
• Rama y corte
• Sucursal y precio
• Si el problema tiene alguna estructura adicional, puede ser posible aplicar la generación diferida de columnas .

Padberg y Beasley analizan este tipo de algoritmos de programación entera .

Se dice que un programa lineal en variables reales es integral si tiene al menos una solución óptima que es integral, es decir, formada únicamente por valores enteros ( que no debe confundirse con integrales ). Del mismo modo, un poliedro${\displaystyle P=\{x\mid Ax\geq 0\}}$Se dice que es integral si para todas las funciones objetivo factibles acotadas c , el programa lineal${\displaystyle \{\max cx\mid x\in P\}}$tiene un óptimo${\displaystyle x^{*}}$con coordenadas enteras. Como observaron Edmonds y Giles en 1977, se puede decir equivalentemente que el poliedro${\displaystyle P}$es integral si para cada función objetivo integral factible acotada c , el valor óptimo del programa lineal${\displaystyle \{\max cx\mid x\in P\}}$es un número entero.

Los programas lineales integrales son de vital importancia en el aspecto poliédrico de la optimización combinatoria, ya que proporcionan una caracterización alternativa de un problema. Específicamente, para cualquier problema, la envoltura convexa de las soluciones es un poliedro integral; si este poliedro tiene una descripción adecuada y compacta, podemos encontrar eficientemente la solución factible óptima bajo cualquier objetivo lineal. A la inversa, si podemos demostrar que una relajación de programación lineal es integral, entonces constituye la descripción deseada de la envoltura convexa de las soluciones factibles (integrales).

La terminología no es consistente en toda la literatura, por lo que se debe tener cuidado al distinguir los dos conceptos siguientes:

• En un programa lineal entero, descrito en la sección anterior, las variables están restringidas forzosamente a ser números enteros, y este problema es NP-difícil en general.
• En un programa lineal integral, descrito en esta sección, las variables no están restringidas a ser números enteros, sino que se ha demostrado de alguna manera que el problema continuo siempre tiene un valor óptimo entero (suponiendo que c es entero), y este valor óptimo se puede encontrar de manera eficiente ya que todos los programas lineales de tamaño polinomial se pueden resolver en tiempo polinomial.

Una forma común de demostrar que un poliedro es integral es mostrar que es totalmente unimodular . Existen otros métodos generales, como la propiedad de descomposición entera y la integralidad dual total . Otros problemas de programación lineal integrales bien conocidos incluyen el politopo de emparejamiento, los poliedros reticulares, los poliedros de flujo submodulares y la intersección de dos polimatroides generalizados/ g -polimatroides (véase, por ejemplo, Schrijver, 2003).

Licencias permisivas :

Licencias Copyleft (recíprocas) :

MINTO (Mixed Integer Optimizer, un solucionador de programación entera que utiliza el algoritmo de ramificación y acotación) tiene código fuente disponible públicamente ^{[ 33 ]} pero no es de código abierto.

Licencias de propiedad :

• Guía para la formulación de problemas de programación lineal
• Glosario de programación matemática
• Preguntas frecuentes sobre programación lineal
• Criterios de referencia para software de optimización