Programación lineal

La programación lineal ( PL ), también llamada optimización lineal , es un método para lograr el mejor resultado (como el máximo beneficio o el menor coste) en un modelo matemático cuyos requisitos y objetivos están representados por relaciones lineales . La programación lineal es un caso especial de programación matemática (también conocida como optimización matemática ).

Más formalmente, la programación lineal es una técnica para la optimización de una función objetivo lineal , sujeta a restricciones de igualdad lineal y desigualdad lineal . Su región factible es un politopo convexo , que es un conjunto definido como la intersección de un número finito de semiespacios , cada uno de los cuales está definido por una desigualdad lineal. Su función objetivo es una función afín (lineal) de valor real definida en este politopo. Un algoritmo de programación lineal encuentra un punto en el politopo donde esta función tiene el valor más grande (o más pequeño) si tal punto existe.

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

${\displaystyle {\begin{aligned}&{\text{Find a vector}}&&\mathbf {x} \\&{\text{that maximizes}}&&\mathbf {c} ^{\mathsf {T}}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}}$

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

La programación lineal se puede aplicar a varios campos de estudio. Se usa ampliamente en matemáticas y, en menor medida, en negocios, economía y algunos problemas de ingeniería. Existe una estrecha conexión entre los programas lineales, las ecuaciones propias, el modelo de equilibrio general de John von Neumann y los modelos de equilibrio estructural (consulte el programa lineal dual para obtener más detalles). ^{[1] [2] [3]} Las industrias que utilizan modelos de programación lineal incluyen el transporte, la energía, las telecomunicaciones y la fabricación. 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 en cuyo honor se bautizó 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 se adentraron de forma independiente en las aplicaciones prácticas de la programación lineal. Kantorovich se centró en los cronogramas de fabricación, mientras que Leontief exploró las aplicaciones económicas. Su trabajo pionero pasó desapercibido durante décadas.

El punto de inflexión se produjo durante la Segunda Guerra Mundial, cuando la programación lineal surgió como una herramienta vital. Se utilizó ampliamente para abordar desafíos complejos en tiempos de guerra, como la logística del transporte, la programación y la asignación de recursos. La programación lineal resultó invaluable para optimizar estos procesos al tiempo que se tenían en cuenta restricciones críticas como los costos y la disponibilidad de recursos.

A pesar de su oscuridad inicial, los éxitos de la guerra impulsaron la programación lineal a la fama. Después de la Segunda Guerra Mundial, el método ganó un amplio reconocimiento y se convirtió en una piedra angular en varios campos, desde la investigación de operaciones hasta la economía. Las contribuciones olvidadas de Kantorovich y Leontief a fines de la década de 1930 finalmente se convirtieron en fundamentales para la aceptación y utilización más amplia 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 holandés-estadounidense TC Koopmans formuló problemas económicos clásicos como programas lineales. Kantorovich y Koopmans luego compartieron 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 método símplex posterior . ^[7] Hitchcock había muerto 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 de programación lineal general para utilizarla en problemas de planificación en la Fuerza Aérea de los EE. UU. ^[8] En 1947, Dantzig también inventó el método símplex que, por primera vez de manera eficiente, abordó 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 símplex, 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 la teoría de juegos era equivalente. ^[8] Dantzig proporcionó una prueba formal en un informe inédito "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 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 potencia 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, sólo se necesita un momento para encontrar la solución óptima planteando el problema como un programa lineal y aplicando el algoritmo símplex . La teoría que sustenta la programación lineal reduce drásticamente el número de posibles soluciones que deben comprobarse.

Leonid Khachiyan demostró por primera vez en 1979 que el problema de programación lineal se podía resolver en tiempo polinomial, ^[9] pero un avance teórico y práctico más grande en el 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 de operaciones se pueden expresar 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 productos , se consideran lo suficientemente importantes como para tener 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. Del mismo modo, la programación lineal se utilizó mucho en la formación temprana de la microeconomía y actualmente se utiliza en la gestión de empresas, como la planificación, la producción, el transporte y la tecnología. Aunque los problemas de gestión modernos cambian constantemente, a la mayoría de las empresas les gustaría 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 tres partes siguientes:

• Una función lineal (o afín) a 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 generalmente se expresa en forma matricial y luego se convierte en:

${\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 problemas de minimización, problemas con restricciones en formas alternativas y problemas que involucran variables negativas siempre pueden reescribirse en un problema equivalente en forma estándar.

Supongamos que un agricultor tiene una parcela de tierra de cultivo, digamos L hectáreas , para sembrar trigo o cebada o alguna combinación de los dos. El agricultor tiene F kilogramos de fertilizante y P kilogramos de pesticida. Cada hectárea de trigo requiere F ₁ kilogramos de fertilizante y P ₁ kilogramos de pesticida, mientras que cada hectárea de cebada requiere F ₂ kilogramos de fertilizante y P ₂ kilogramos de pesticida. Sea S ₁ el precio de venta del trigo y S ₂ el precio de venta de la cebada, por hectárea. Si denotamos el área de tierra sembrada con trigo y cebada por x ₁ y x ₂ respectivamente, entonces la ganancia se puede maximizar eligiendo valores óptimos para x ₁ y x ₂ . Este problema se puede expresar con el siguiente problema de programación lineal en la forma estándar:

Maximizar:	${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$	(maximizar los ingresos (las ventas totales de trigo más las ventas totales de cebada) – los ingresos son la "función objetivo")
Sujeto a:	${\displaystyle x_{1}+x_{2}\leq L}$	(límite de superficie total)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}$	(límite de fertilizante)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}$	(límite de pesticidas)
	${\displaystyle x_{1}\geq 0,x_{2}\geq 0}$	(no se puede plantar un área negativa).

En forma de matriz 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 símplex . Esta forma introduce variables de holgura no negativas para reemplazar desigualdades con igualdades en las restricciones. Los problemas se pueden escribir en la siguiente forma de matriz de bloques :

Maximizar :${\displaystyle z}$

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{\mathsf {T}}&0\\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 0,\mathbf {s} \geq 0}$

¿Dónde están las variables de holgura recién introducidas, son las variables de decisión y es la variable que se debe maximizar?${\displaystyle \mathbf {s} }$${\displaystyle \mathbf {x} }$${\displaystyle z}$

El ejemplo anterior se convierte en la siguiente forma aumentada:

Maximizar:${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(función objetivo)
sujeto a:	${\displaystyle x_{1}+x_{2}+x_{3}=L}$	(restricción aumentada)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F}$	(restricción aumentada)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P}$	(restricción aumentada)
	${\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.}$

donde son variables de holgura (no negativas), que representan en este ejemplo el área no utilizada, la cantidad de fertilizante no utilizado y la cantidad de pesticida no utilizado.${\displaystyle x_{3},x_{4},x_{5}}$

En forma de matriz esto se convierte en:

Maximizar :${\displaystyle z}$

$${\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.}$$

Todo problema de programación lineal, denominado problema primario , se puede convertir en un problema dual , que proporciona un límite superior al valor óptimo del problema primario. En forma matricial, podemos expresar el problema primario 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 primaria alternativa es:

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

con el correspondiente problema dual asimétrico ,

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

Hay dos ideas fundamentales para la teoría de la dualidad. Una es el hecho de que (para el dual simétrico) el dual de un programa lineal dual es el programa lineal primal original. Además, cada solución factible para un programa lineal da un límite al valor óptimo de la función objetivo de su dual. El teorema de dualidad débil establece que el valor de la función objetivo del dual en cualquier solución factible es siempre mayor o igual que el valor de la función objetivo del primal en cualquier solución factible. El teorema de dualidad fuerte establece que 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 ilimitado o inviable. La teoría de la dualidad nos dice que si el programa primario no tiene límites, entonces el dual es inviable según el teorema de dualidad débil. De la misma manera, si el dual no tiene límites, entonces el programa primario debe ser inviable. Sin embargo, es posible que tanto el dual como el programa primario sean inviables. Consulte el programa lineal dual para obtener más detalles y varios ejemplos más.

Un programa lineal de cobertura es un programa lineal de la forma:

Minimizar: b ^T y ,

sujeto a: A ^T y ≥ c , y ≥ 0 ,

de modo que la matriz A y los vectores b y c no son negativos.

El dual de un LP de recubrimiento es un LP de empaquetamiento , un programa lineal de la forma:

Maximizar: c ^T x ,

sujeto a: A x ≤ b , x ≥ 0 ,

de modo que la matriz A y los vectores b y c no son negativos.

Los LP de cubrimiento y empaquetamiento surgen comúnmente como una relajación de programación lineal de un problema combinatorio y son importantes en el estudio de algoritmos de aproximación . ^[12] Por ejemplo, las relajaciones de LP del problema de empaquetamiento de conjuntos , el problema de conjuntos independientes y el problema de emparejamiento son LP de empaquetamiento. Las relajaciones de LP del problema de cobertura de conjuntos , el problema de cobertura de vértices y el problema de conjuntos dominantes también son LP de cobertura.

Encontrar una coloración fraccionaria de un gráfico es otro ejemplo de PL de recubrimiento. En este caso, hay una restricción para cada vértice del gráfico y una variable para cada conjunto independiente del gráfico.

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

Supóngase 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 óptimas 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 .

Por lo tanto, si la i -ésima variable de holgura del primal no es cero, entonces la i -ésima variable del dual es igual a cero. Asimismo, si la j -ésima variable de holgura del dual no es cero, entonces la j -ésima variable del primal es igual a cero.

Esta condición necesaria para la optimalidad transmite un principio económico bastante simple. En forma estándar (cuando se maximiza), si hay holgura en un recurso primario restringido (es decir, hay "sobrantes"), entonces las cantidades adicionales de ese recurso no deben tener valor. De la misma manera, si hay holgura en el requisito de restricción de no negatividad del precio dual (sombra), es decir, el precio no es cero, entonces debe haber suministros escasos (no hay "sobrantes").

Geométricamente, las restricciones lineales definen la región factible , que es un politopo convexo . Una función lineal es una función convexa , lo que implica que todo mínimo local es un mínimo global ; de manera similar, una función lineal es una función cóncava , lo que implica que todo máximo local es un máximo global .

No es necesario que exista una solución óptima por dos razones. En primer lugar, si las restricciones son inconsistentes, entonces no existe una solución factible: por ejemplo, las restricciones x  ≥ 2 y x  ≤ 1 no se pueden satisfacer conjuntamente; en este caso, decimos que el PL es inviable . En segundo lugar, cuando el politopo no está acotado en la dirección del gradiente de la función objetivo (donde el gradiente de la función objetivo es el vector de los coeficientes de la función objetivo), entonces no se alcanza ningún valor óptimo porque siempre es posible hacerlo mejor que cualquier valor finito de la función objetivo.

De lo contrario, si existe una solución factible y si el conjunto de restricciones está acotado, entonces el valor óptimo siempre se alcanza en el límite del conjunto de restricciones, por el principio de máximo para funciones convexas (alternativamente, por el principio de mínimo para funciones cóncavas ) ya que las funciones lineales son tanto convexas como cóncavas. Sin embargo, algunos problemas tienen soluciones óptimas distintas; por ejemplo, el problema de encontrar una solución factible para un sistema de desigualdades lineales es un problema de programación lineal en el que la función objetivo es la función cero (es decir, la función constante que toma el valor cero en todas partes). Para este problema de viabilidad con la función cero para su función objetivo, si hay dos soluciones distintas, entonces cada combinación convexa de las soluciones es una solución.

Los vértices del politopo también se denominan soluciones factibles básicas . La razón de esta elección de nombre es la siguiente. Sea d el número de variables. Entonces, el teorema fundamental de las desigualdades lineales implica (para problemas factibles) que para cada vértice x ^* de la región factible de PL, existe un conjunto de d (o menos) restricciones de desigualdad del PL tales que, cuando tratamos esas d restricciones como igualdades, la única solución es x ^* . Por lo tanto, podemos estudiar estos vértices mediante la observación de ciertos subconjuntos del conjunto de todas las restricciones (un conjunto discreto), en lugar del continuo de soluciones de PL. Este principio subyace al algoritmo simplex para resolver programas lineales.

El algoritmo simplex , desarrollado por George Dantzig en 1947, resuelve problemas de programación lineal construyendo una solución factible en un vértice del politopo y luego recorriendo un camino por los bordes del politopo hasta los vértices con valores no decrecientes de la función objetivo hasta que se alcanza un óptimo con seguridad. En muchos problemas prácticos, se produce un " bloqueo ": se realizan muchos pivotes sin aumento de la función objetivo. ^{[13] [14]} En problemas prácticos poco frecuentes, las versiones habituales del algoritmo simplex pueden en realidad "ciclar". ^[14] Para evitar los ciclos, los investigadores desarrollaron nuevas reglas de pivote. ^[15]

En la práctica, el algoritmo símplex es bastante eficiente y se puede garantizar que encuentre el óptimo global si se toman ciertas precauciones contra los ciclos . Se ha demostrado que el algoritmo símplex resuelve problemas "aleatorios" de manera eficiente, es decir, en un número cúbico de pasos, ^[16] lo que es similar a su comportamiento en problemas prácticos. ^{[13] [17]}

Sin embargo, el algoritmo simplex tiene un comportamiento pobre en el peor de los casos: Klee y Minty construyeron una familia de problemas de programación lineal para los cuales el método simplex toma un número de pasos exponencial en el tamaño del problema. ^{[13] [18] [19]} De hecho, durante algún tiempo no se supo si el problema de programación lineal era solucionable en tiempo polinomial , es decir, de clase de complejidad P.

Al igual que el algoritmo simplex de Dantzig, el algoritmo criss-cross es un algoritmo de intercambio de bases que pivotea entre bases. Sin embargo, el algoritmo criss-cross no necesita mantener la viabilidad, sino que puede pivotar de una base factible a una base infactible. El algoritmo criss-cross no tiene complejidad temporal polinómica para la programación lineal. Ambos algoritmos visitan las 2 ^D esquinas de un cubo (perturbado) de dimensión  D , el cubo de Klee-Minty , en el peor de los casos . ^{[15] [20]}

A diferencia del algoritmo simplex, que encuentra una solución óptima recorriendo los bordes entre los vértices de un conjunto poliédrico, los métodos de punto interior se mueven a través del interior de la región factible.

Este es el primer algoritmo de tiempo polinomial en el peor de los casos jamás encontrado para la programación lineal. Para resolver un problema que tiene n variables y puede codificarse en L bits de entrada, este algoritmo se ejecuta en el tiempo. ^[9] Leonid Khachiyan resolvió este antiguo problema de complejidad en 1979 con la introducción del método del elipsoide . El análisis de convergencia tiene predecesores (en números reales), en particular los métodos iterativos desarrollados por Naum Z. Shor y los algoritmos de aproximación de Arkadi Nemirovski y D. Yudin.${\displaystyle O(n^{6}L)}$

El algoritmo de Khachiyan fue de importancia fundamental para establecer la resolubilidad en tiempo polinómico de programas lineales. El algoritmo no fue un gran avance computacional, ya que el método símplex es más eficiente para todos los programas lineales, salvo para familias especialmente construidas.

Sin embargo, el algoritmo de Khachiyan inspiró nuevas líneas de investigación en programación lineal. En 1984, N. Karmarkar propuso un método proyectivo para programación lineal. El algoritmo de Karmarkar ^[10] mejoró el límite polinomial del peor caso de Khachiyan ^[9] (dando ). Karmarkar afirmó que su algoritmo era mucho más rápido en programación lineal práctica que el método símplex, una afirmación que creó un gran interés en los métodos de punto interior. ^[21] Desde el descubrimiento de Karmarkar, se han propuesto y analizado muchos métodos de punto interior.${\displaystyle O(n^{3.5}L)}$

En 1987, Vaidya propuso un algoritmo que se ejecuta en el tiempo. ^[22]${\displaystyle O(n^{3})}$

En 1989, Vaidya desarrolló un algoritmo que se ejecuta en el tiempo. ^[23] Formalmente hablando, el algoritmo realiza operaciones aritméticas en el peor de los casos, donde es el número de restricciones, es el número de variables y es el número de bits.${\displaystyle O(n^{2.5})}$${\displaystyle O((n+d)^{1.5}nL)}$${\displaystyle d}$${\displaystyle n}$${\displaystyle L}$

En 2015, Lee y Sidford demostraron que la programación lineal se puede resolver en el tiempo, ^[24] donde denota la notación suave O , y representa el número de elementos distintos de cero, y permanece siendo constante en el peor de los casos.${\displaystyle {\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)}$${\displaystyle {\tilde {O}}}$${\displaystyle nnz(A)}$${\displaystyle O(n^{2.5}L)}$

En 2019, Cohen, Lee y Song mejoraron el tiempo de ejecución a tiempo, es el exponente de la multiplicación de matrices y es el exponente dual de la multiplicación de matrices . ^[25] se define (aproximadamente) como el número más grande tal que uno puede multiplicar una matriz por una matriz en el tiempo. En un trabajo de seguimiento de Lee, Song y Zhang, reproducen el mismo resultado a través de un método diferente. ^[26] Estos dos algoritmos permanecen cuando y . El resultado debido a Jiang, Song, Weinstein y Zhang mejoró a . ^[27]${\displaystyle {\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)}$${\displaystyle \omega }$${\displaystyle \alpha }$ ${\displaystyle \alpha }$${\displaystyle n\times n}$${\displaystyle n\times n^{\alpha }}$${\displaystyle O(n^{2})}$${\displaystyle {\tilde {O}}(n^{2+1/6}L)}$${\displaystyle \omega =2}$${\displaystyle \alpha =1}$${\displaystyle {\tilde {O}}(n^{2+1/6}L)}$${\displaystyle {\tilde {O}}(n^{2+1/18}L)}$

La opinión actual es que las eficiencias de las buenas implementaciones de los métodos basados ​​en símplex y los métodos de punto interior son similares para las aplicaciones rutinarias de programación lineal. Sin embargo, para tipos específicos de problemas de programación lineal, puede ser que un tipo de solucionador sea mejor que otro (a veces mucho mejor), y que la estructura de las soluciones generadas por los métodos de punto interior versus los métodos basados ​​en símplex sean significativamente diferentes, siendo el conjunto de soporte de variables activas típicamente más pequeño para estos últimos. ^[28]

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

• ¿LP admite un algoritmo de tiempo fuertemente polinomial ?
• ¿LP admite un algoritmo de tiempo fuertemente polinomial para encontrar una solución estrictamente complementaria?
• ¿LP admite un algoritmo de tiempo polinomial en el modelo de cálculo de números reales (costo unitario)?

Este conjunto de problemas, estrechamente relacionados, ha sido citado por Stephen Smale como uno de los 18 problemas sin resolver más importantes del siglo XXI. En palabras de Smale, la tercera versión del problema "es el principal problema sin resolver de la teoría de 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 el 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 ganancias prácticas en la resolución de grandes LP.

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

• ¿Existen reglas de pivote que conducen a variantes símplex en tiempo polinomial?
• ¿Todos los grafos politópicos tienen un diámetro acotado polinomialmente?

Estas preguntas se relacionan con el análisis del desempeño y el desarrollo de métodos similares al símplex. La inmensa eficiencia del algoritmo símplex en la práctica, a pesar de su desempeño teórico en tiempo exponencial, sugiere que puede haber variaciones del símplex 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, particularmente como un enfoque para decidir si el PL se puede resolver 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 en el politopo LP. Como resultado, nos interesa conocer el diámetro máximo teórico de 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 existe algún politopo de este tipo, entonces ninguna variante de seguimiento de aristas puede ejecutarse en tiempo polinomial. Las preguntas sobre el diámetro del politopo son de interés matemático independiente.

Los métodos de pivote simplex preservan la factibilidad primaria (o dual). Por otro lado, los métodos de pivote entrecruzado no preservan la factibilidad (primaria o dual): pueden visitar bases factibles primarias, factibles duales o infactibles primarias y duales en cualquier orden. Los métodos de pivote de este tipo se han estudiado desde la década de 1970. ^[29] Básicamente, 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 entrecruzado de tiempo fuertemente polinomial sin resolver cuestiones sobre el diámetro de los politopos generales. ^[15]

Si se requiere que todas las variables desconocidas sean números enteros, entonces el problema se llama un problema de programación entera (IP) o programación lineal entera (ILP). A diferencia de la programación lineal, que se puede resolver de manera eficiente en el peor de los casos, los problemas de programación entera son en muchas situaciones prácticas (aquellas con variables acotadas) NP-hard . La programación entera 0-1 o programación entera binaria (BIP) es el caso especial de programación entera donde se requiere que las variables sean 0 o 1 (en lugar de números enteros arbitrarios). Este problema también se clasifica como NP-hard, y de hecho la versión de decisión fue uno de los 21 problemas NP-completos de Karp .

Si solo se requiere que algunas de las variables desconocidas sean números enteros, entonces el problema se denomina problema de programación entera mixta (lineal) (MIP o MILP). Estos también suelen ser NP-hard porque son incluso más generales que los programas ILP.

Sin embargo, existen algunas subclases importantes de problemas IP y MIP que se pueden resolver de manera eficiente, en particular los problemas en los que la matriz de restricciones es totalmente unimodular y los lados derechos de las restricciones son números enteros o, de manera 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
• Rama y límite
• Ramificar y cortar
• Sucursal y precio
• Si el problema tiene alguna estructura adicional, puede ser posible aplicar la generación de columnas retrasada .

Padberg y Beasley analizan estos algoritmos de programación de números enteros .

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

Los programas lineales integrales son de importancia central 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 agradable/compacta, entonces podemos encontrar eficientemente la solución factible óptima bajo cualquier objetivo lineal. Por el contrario, si podemos probar que una relajación de programación lineal es integral, entonces es la descripción deseada de la envoltura convexa de soluciones factibles (integrales).

La terminología no es consistente en toda la literatura, por lo que se debe tener cuidado de 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-hard 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, de alguna manera, se ha demostrado que el problema continuo siempre tiene un valor integral óptimo (asumiendo que c es integral), 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 demostrar que es totalmente unimodular . Existen otros métodos generales, como la propiedad de descomposición entera y la integralidad dual total . Otros poliedros integrales bien conocidos son el politopo coincidente, los poliedros reticulares, los poliedros de flujo submodular y la intersección de dos polimatroides generalizados/ g -polimatroides; por ejemplo, véase Schrijver 2003.

Licencias permisivas :

Licencias copyleft (recíprocas) :

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

Licencias propietarias :

Wikimedia Commons tiene medios relacionados con Programación lineal .

• Orientación para la formulación de problemas de PL
• Glosario de programación matemática
• Preguntas frecuentes sobre programación lineal
• Puntos de referencia para el software de optimización