Programación lineal

Método para resolver problemas de optimización

Representación gráfica de un programa lineal simple con dos variables y seis inecuaciones. El conjunto de soluciones factibles se representa en amarillo y forma un polígono , un politopo bidimensional . El óptimo de la función de costo lineal se encuentra donde la línea roja interseca el polígono. La línea roja es un conjunto de niveles de la función de costo y la flecha indica la dirección en la que estamos optimizando.

Una región factible cerrada de un problema con tres variables es un poliedro convexo . Las superficies que dan un valor fijo de la función objetivo son planos (no se muestran). El problema de programación lineal consiste en encontrar un punto en el poliedro que se encuentre en el plano con el valor más alto posible.

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 se pueden expresar 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 llama función objetivo . Las restricciones y especifican un politopo convexo sobre el cual 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.

Historia

Leonid Kantorovich

Juan von Neumann

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 Ciencias Económicas 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]

Usos

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]

Formulario estándar

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.

Ejemplo

Solución gráfica para el ejemplo del agricultor: después de sombrear las regiones que violan las condiciones, el vértice de la región no sombreada con la línea discontinua más alejada del origen da la combinación óptima (su ubicación sobre las líneas de tierra y pesticida implica que los ingresos están limitados por la tierra y el pesticida, no por el fertilizante).

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:

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}}.}$

Forma aumentada (forma holgada)

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}$

Ejemplo

El ejemplo anterior se convierte en la siguiente forma aumentada:

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.}$$

Dualidad

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.

Variaciones

Dualidades cubriendo/empacando

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 son no 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 son no negativos.

Ejemplos

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 cubrimiento.

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.

Holgura complementaria

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 primariamente y que y  = ( y ₁ ,  y ₂ , ... ,  y _m ) es factible dualmente. Sean ( w ₁ ,  w ₂ , ...,  w _m ) las variables de holgura primarias 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").

Teoría

Existencia de soluciones óptimas

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.

Vértices (y rayos) óptimos de poliedros

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.

Algoritmos

En un problema de programación lineal, una serie de restricciones lineales produce una región factible convexa de valores posibles para esas variables. En el caso de dos variables, esta región tiene la forma de un polígono simple convexo .

Algoritmos de intercambio de base

Algoritmo simplex de Dantzig

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.

Algoritmo entrecruzado

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]}

Punto interior

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.

Algoritmo del elipsoide, siguiendo a Khachiyan

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)}$

Algoritmo proyectivo de Karmarkar

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)}$

Algoritmo 87 de Vaidya

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

Algoritmo 89 de Vaidya

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}$

Algoritmos de tiempo de escasez de entrada

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)}$

Algoritmo actual de multiplicación de matrices

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)}$

Comparación de métodos de puntos interiores y algoritmos símplex

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]

Problemas abiertos y trabajos recientes

Problema sin resolver en informática :

¿La programación lineal admite un algoritmo de tiempo fuertemente polinomial?

(más problemas sin resolver en informática)

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 de elipsoide 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 algoritmo LP 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]

Incógnitas enteras

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 .

Programas lineales integrales

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 demostrar 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 incluyen 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.

Solucionadores y lenguajes de programación

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 :

Véase también

• Programación convexa
• Programación dinámica
• Déficit esperado § Optimización del déficit esperado
• Modelo de entrada-salida
• Programación de talleres de trabajo
• Desviaciones absolutas mínimas
• Análisis espectral de mínimos cuadrados
• Álgebra lineal
• Juego de producción lineal
• Programación lineal-fraccional (LFP)
• Problema de tipo LP
• Programación matemática
• Programación no lineal
• Algoritmo de probabilidades utilizado para resolver problemas de parada óptima
• Matroide orientado
• Programación cuadrática , un superconjunto de la programación lineal
• Programación semidefinida
• Precio sombra
• Algoritmo Simplex , utilizado para resolver problemas de PL

Notas

1. von Neumann, J. (1945). "Un modelo de equilibrio económico general". The Review of Economic Studies . 13 : 1–9.
2. Kemeny, JG; Morgenstern, O.; Thompson, GL (1956). "Una generalización del modelo de von Neumann de una economía en expansión". Econometrica . 24 : 115–135.
3. Li, Wu (2019). Equilibrio general y dinámica estructural: perspectivas de la nueva economía estructural (en chino). Pekín: Economic Science Press. pp. 122–125. ISBN 978-7-5218-0422-5.
4. Gerard Sierksma; Yori Zwols (2015). Optimización lineal y entera: teoría y práctica (3.ª ed.). CRC Press. pág. 1. ISBN 978-1498710169.
5. "Programación lineal | Definición y hechos | Britannica". www.britannica.com . Consultado el 20 de noviembre de 2023 .
6. George B. Dantzig (abril de 1982). «Reminiscencias sobre los orígenes de la programación lineal» (PDF) . Operations Research Letters . 1 (2): 43–48. doi :10.1016/0167-6377(82)90043-8. Archivado desde el original el 20 de mayo de 2015.
7. Alexander Schrijver (1998). Teoría de la programación lineal y entera . John Wiley & Sons. pp. 221–222. ISBN 978-0-471-98232-6.
8. Dantzig, George B.; Thapa, Mukund Narain (1997). Programación lineal . Nueva York: Springer. p. xxvii. ISBN. 0387948333.OCLC 35318475  .
9. Leonid Khachiyan (1979). "Un algoritmo polinomial para programación lineal". Doklady Akademii Nauk SSSR . 224 (5): 1093–1096.
10. Narendra Karmarkar (1984). "Un nuevo algoritmo de tiempo polinomial para programación lineal". Combinatorica . 4 (4): 373–395. doi :10.1007/BF02579150. S2CID  7257867.
11. M. Grundmann; V. Kwatra; I. Essa (2011). "Estabilización de vídeo autodirigida con trayectorias de cámara óptimas L1 robustas". CVPR 2011 (PDF) . pp. 225–232. doi :10.1109/CVPR.2011.5995525. ISBN. 978-1-4577-0394-2. Número de identificación del sujeto  17707171.
12. Vazirani (2001, pág. 112)
13. Dantzig y Thapa (2003)
14. Padberg (1999)
15. Fukuda, Komei ; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos entrecruzados: una nueva visión de los algoritmos pivote". Programación matemática, serie B . 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373 . doi :10.1007/BF02614325. MR  1464775. S2CID  2794181. 
16. Borgwardt (1987)
17. Todd (2002)
18. Murty (1983)
19. Papadimitriou y Steiglitz
20. Roos, C. (1990). "Un ejemplo exponencial de la regla pivotante de Terlaky para el método símplex entrecruzado". Programación matemática . Serie A. 46 (1): 79–84. doi :10.1007/BF01585729. MR  1045573. S2CID  33463483.
21. Strang, Gilbert (1 de junio de 1987). "El algoritmo de Karmarkar y su lugar en las matemáticas aplicadas". The Mathematical Intelligencer . 9 (2): 4–10. doi :10.1007/BF03025891. ISSN  0343-6993. MR  0883185. S2CID  123541868.
22. Vaidya, Pravin M. (1987). Un algoritmo para programación lineal que requiere operaciones aritméticas . 28.º Simposio anual IEEE sobre fundamentos de la informática. FOCS. ${\displaystyle {O}(((m+n)n^{2}+(m+n)^{1.5}n)L)}$
23. Vaidya, Pravin M. (1989). "Aceleración de la programación lineal mediante multiplicación rápida de matrices". 30.º Simposio anual sobre fundamentos de la informática . 30.º Simposio anual sobre fundamentos de la informática. FOCS. págs. 332–337. doi :10.1109/SFCS.1989.63499. ISBN 0-8186-1982-1.
24. Lee, Yin-Tat; Sidford, Aaron (2015). Mantenimiento inverso eficiente y algoritmos más rápidos para programación lineal . FOCS '15 Fundamentos de la informática. arXiv : 1503.01752 .
25. Cohen, Michael B.; Lee, Yin-Tat; Song, Zhao (2018). Resolución de programas lineales en el tiempo de multiplicación de matrices actual . 51.° Simposio anual de la ACM sobre teoría de la computación. STOC'19. arXiv : 1810.07896 .
26. Lee, Yin-Tat; Song, Zhao; Zhang, Qiuyi (2019). Solución de la minimización del riesgo empírico en el tiempo actual de multiplicación de matrices . Conferencia sobre teoría del aprendizaje. COLT'19. arXiv : 1905.04447 .
27. Jiang, Shunhua; Song, Zhao; Weinstein, Omri; Zhang, Hengjie (2020). Matriz dinámica inversa más rápida para LP más rápidos . arXiv : 2004.07470 .
28. Illés, Tibor; Terlaky, Tamás (2002). "Métodos de pivote versus punto interior: pros y contras". Revista europea de investigación operativa . 140 (2): 170. CiteSeerX 10.1.1.646.3539 . doi :10.1016/S0377-2217(02)00061-9. 
29. Anstreicher, Kurt M.; Terlaky, Tamás (1994). "Un algoritmo simplex de acumulación monótona para programación lineal". Investigación de operaciones . 42 (3): 556–561. doi : 10.1287/opre.42.3.556 . ISSN  0030-364X. JSTOR  171894.
30. "Guía de referencia de lp_solve (5.5.2.5)". mit.edu . Consultado el 10 de agosto de 2023 .
31. "Interfaces de lenguaje externas" . Consultado el 3 de diciembre de 2021 .
32. "comando lp_solve" . Consultado el 3 de diciembre de 2021 .
33. "COR@L – Investigación en optimización computacional en Lehigh". lehigh.edu .
34. http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ utilizado en un modelo de optimización para líneas de montaje de modelos mixtos, Universidad de Münster
35. http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 Archivado el 29 de junio de 2011 en Wayback Machine OptimJ utilizado en una técnica de cálculo de equilibrio aproximado perfecto en subjuegos para juegos repetidos

Referencias

• Kantorovich, LV (1940). "Об одном эффективном методе решения некоторых классов экстремальных проблем" [Un nuevo método para resolver algunas clases de problemas extremos]. Doklady Akad Sci SSSR . 28 : 211–214.
• FL Hitchcock: La distribución de un producto de varias fuentes a numerosas localidades , Journal of Mathematics and Physics, 20, 1941, 224–230.
• GB Dantzig: Maximización de una función lineal de variables sujetas a desigualdades lineales , 1947. Publicado pp. 339–347 en TC Koopmans (ed.): Análisis de la actividad de la producción y asignación , Nueva York-Londres 1951 (Wiley & Chapman-Hall)
• JE Beasley, editor. Avances en programación lineal y entera . Oxford Science, 1996. (Colección de encuestas)
• Bland, Robert G. (1977). "Nuevas reglas de pivoteo finito para el método símplex". Matemáticas de la investigación de operaciones . 2 (2): 103–107. doi :10.1287/moor.2.2.103. JSTOR  3689647.
• Borgwardt, Karl-Heinz (1987). El algoritmo Simplex: un análisis probabilístico . Algoritmos y combinatoria. Vol. 1. Springer-Verlag.(Comportamiento promedio en problemas aleatorios)
• Richard W. Cottle, ed. The Basic George B. Dantzig . Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Artículos seleccionados de George B. Dantzig )
• George B. Dantzig y Mukund N. Thapa. 1997. Programación lineal 1: Introducción . Springer-Verlag.
• Dantzig, George B.; Thapa, Mukund N. (2003). Programación lineal 2: teoría y extensiones . Springer-Verlag.(Exhaustivo, cubre, por ejemplo, algoritmos de pivote y de punto interior, problemas a gran escala, descomposición siguiendo Dantzig-Wolfe y Benders , e introduce la programación estocástica ).
• Edmonds, Jack; Giles, Rick (1977). "Una relación mín-máx para funciones submodulares en gráficos". Estudios de programación entera . Anales de matemáticas discretas. Vol. 1. págs. 185–204. doi :10.1016/S0167-5060(08)70734-9. ISBN . 978-0-7204-0765-5.
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos entrecruzados: una nueva visión de los algoritmos pivote". Programación matemática, serie B . 79 (1–3): 369–395. CiteSeerX  10.1.1.36.9373 . doi :10.1007/BF02614325. MR  1464775. S2CID  2794181.
• Gondzio, Jacek; Terlaky, Tamás (1996). "3 Una visión computacional de los métodos de puntos interiores". En JE Beasley (ed.). Avances en programación lineal y entera . Oxford Lecture Series in Mathematics and its Applications. Vol. 4. Nueva York: Oxford University Press. págs. 103–144. MR  1438311. Archivo Postscript en el sitio web de Gondzio y en el sitio web de la Universidad McMaster de Terlaky.
• Murty, Katta G. (1983). Programación lineal . Nueva York: John Wiley & Sons, Inc., págs. xix+482. ISBN 978-0-471-09725-9. MR  0720547. (referencia amplia a los enfoques clásicos).
• Evar D. Nering y Albert W. Tucker , 1993, Programas lineales y problemas relacionados , Academic Press. (primaria)
• Padberg, M. (1999). Optimización lineal y extensiones, segunda edición . Springer-Verlag.(Relato cuidadosamente escrito de algoritmos símplex primarios y duales y algoritmos proyectivos, con una introducción a la programación lineal entera, que incluye el problema del viajante de comercio para Odiseo ).
• Papadimitriou, Christos H. ; Steiglitz, Kenneth. Optimización combinatoria: algoritmos y complejidad (reedición corregida con un nuevo prefacio). Dover.(Ciencias de la Computación)
• Todd, Michael J. (febrero de 2002). "Las múltiples facetas de la programación lineal". Programación matemática . 91 (3): 417–436. doi :10.1007/s101070100261. S2CID  6464735.(Encuesta por invitación, del Simposio Internacional de Programación Matemática.)
• Vanderbei, Robert J. (2001). Programación lineal: fundamentos y extensiones . Springer Verlag.
• Vazirani, Vijay V. (2001). Algoritmos de aproximación . Springer-Verlag. ISBN 978-3-540-65367-7.(Ciencias de la Computación)

Lectura adicional

• Dmitris Alevras y Manfred W. Padberg, Optimización lineal y extensiones: problemas y soluciones , Universitext, Springer-Verlag, 2001. (Problemas de Padberg con soluciones).
• de Berg, Mark; van Kreveld, Marc; Overmars, Marcos ; Schwarzkopf, Otfried (2000). Geometría computacional (2ª edición revisada). Springer-Verlag . ISBN 978-3-540-65620-3.Capítulo 4: Programación lineal: págs. 63 a 94. Describe un algoritmo aleatorio de intersección de semiplanos para programación lineal.
• Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman. ISBN 978-0-7167-1045-5.A6: MP1: PROGRAMACIÓN ENTERA, pág. 245. (informática, teoría de la complejidad)
• Gartner, Bernd; Matoušek, Jiří (2006). Comprensión y uso de la programación lineal . Berlín: Springer. ISBN 3-540-30697-8.(Introducción elemental para matemáticos e informáticos)
• Cornelis Roos, Tamás Terlaky, Jean-Philippe Vial, Métodos de puntos interiores para optimización lineal , segunda edición, Springer-Verlag, 2006. (Nivel de posgrado)
• Alexander Schrijver (2003). Optimización combinatoria: poliedros y eficiencia . Springer.
• Alexander Schrijver, Teoría de la programación lineal y entera . John Wiley & sons, 1998, ISBN 0-471-98232-6 (matemática) 
• Gerard Sierksma; Yori Zwols (2015). Optimización lineal y entera: teoría y práctica . CRC Press. ISBN 978-1-498-71016-9.
• Gerard Sierksma; Diptesh Ghosh (2010). Redes en acción; ejercicios de texto y computadora sobre optimización de redes . Springer. ISBN 978-1-4419-5512-8.(modelado de optimización lineal)
• HP Williams, Model Building in Mathematical Programming , Quinta edición, 2013. (Modelado)
• Stephen J. Wright, 1997, Métodos de puntos interiores duales primarios , SIAM. (Nivel de posgrado)
• Yinyu Ye , 1997, Algoritmos de puntos interiores: teoría y análisis , Wiley. (Nivel de posgrado avanzado)
• Ziegler, Günter M. , Capítulos 1-3 y 6-7 en Lectures on Polytopes , Springer-Verlag, Nueva York, 1994. (Geometría)

Enlaces externos

• 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