Programación lineal

Método para resolver problemas de optimización.

Una representación pictórica de un programa lineal simple con dos variables y seis desigualdades. 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 es donde la línea roja cruza 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 mostrados). El problema de programación lineal consiste en encontrar un punto del poliedro que esté en el plano con el valor más alto posible.

La programación lineal ( LP ), 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 objetivo 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 a determinar, y se les dan vectores , y es una matriz dada . La función cuyo valor se quiere maximizar ( en este caso) se llama función objetivo . Las restricciones y especifican un politopo convexo sobre el cual se 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 utiliza mucho en matemáticas y, en menor medida, en negocios, economía y algunos problemas de ingeniería. Las industrias que utilizan modelos de programación lineal incluyen transporte, energía, telecomunicaciones y manufactura. 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, ^[1] y que da nombre al 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 profundizaron de forma independiente en las aplicaciones prácticas de la programación lineal. Kantorovich se centró en los cronogramas de fabricación, mientras Leontief exploraba aplicaciones económicas. Su trabajo innovador fue pasado por alto 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. Encontró un amplio uso para abordar desafíos complejos en tiempos de guerra, incluida la logística del transporte, la programación y la asignación de recursos. La programación lineal resultó invaluable para optimizar estos procesos teniendo en cuenta limitaciones críticas como los costos y la disponibilidad de recursos.

A pesar de su oscuridad inicial, los éxitos en tiempos de guerra impulsaron la programación lineal al centro de atención. Después de la Segunda Guerra Mundial, el método obtuvo un amplio reconocimiento y se convirtió en una piedra angular en diversos campos, desde la investigación de operaciones hasta la economía. Las contribuciones pasadas por alto de Kantorovich y Leontief a finales de la década de 1930 eventualmente se convirtieron en fundamentales para una aceptación y utilización más amplia de la programación lineal en la optimización de los procesos de toma de decisiones. ^[2]

El trabajo de Kantorovich fue inicialmente ignorado en la URSS . ^[3] Casi al mismo tiempo que Kantorovich, el economista holandés-estadounidense TC Koopmans formuló los problemas económicos clásicos como programas lineales. Kantorovich y Koopmans compartieron más tarde el Premio Nobel de Ciencias Económicas en 1975 . ^[1] En 1941, Frank Lauren Hitchcock también formuló problemas de transporte como programas lineales y dio una solución muy similar al método simplex posterior . ^[4] 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 EE. UU. ^[5] En 1947, Dantzig también inventó el método simplex que, por primera vez de manera eficiente, abordó el problema de programación lineal en la mayoría de los casos. ^[5] Cuando Dantzig organizó una reunión con John von Neumann para discutir su método simplex, Neumann inmediatamente conjeturó la teoría de la dualidad al darse cuenta de que el problema que había estado trabajando en la teoría de juegos era equivalente. ^[5] Dantzig proporcionó pruebas formales en un informe inédito "Un teorema sobre desigualdades lineales" el 5 de enero de 1948. ^[3] 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 sus 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 informática 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 toma un momento encontrar la solución óptima planteando el problema como un programa lineal y aplicando el algoritmo simplex . La teoría detrás de la programación lineal reduce drásticamente la cantidad de posibles soluciones que deben verificarse.

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

Usos

La programación lineal es un campo de optimización ampliamente utilizado por varias razones. Muchos problemas prácticos de la investigación de operaciones se pueden expresar como problemas de programación lineal. ^[3] 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 realizar 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ó mucho en la formación inicial 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 programación lineal para estabilizar los vídeos de YouTube. ^[8]

Forma 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 siguientes tres partes:

• 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 queda:

${\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 en un problema equivalente en forma estándar.

Ejemplo

Solución gráfica al 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 (que se encuentre sobre las líneas de pesticidas y tierra implica que los pesticidas y la tierra limitan los ingresos)

Supongamos que un agricultor tiene un terreno agrícola, digamos L km ² , para sembrar trigo o cebada o alguna combinación de ambos. El agricultor tiene una cantidad limitada de fertilizante, F kilogramos, y de pesticida, P kilogramos. Cada kilómetro cuadrado de trigo requiere _{1 kilogramo de fertilizante y 1 kilogramo} de pesticida , mientras que cada kilómetro cuadrado de cebada requiere ₂ kilogramos de fertilizante y 2 _kilogramos de pesticida. Sea S ₁ el precio de venta del trigo por kilómetro cuadrado y S ₂ el precio de venta de la cebada. Si denotamos el área de tierra plantada con trigo y cebada por x ₁ y x ₂ respectivamente, entonces se pueden maximizar las ganancias 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 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}}.}$

Forma aumentada (forma relajada)

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 desigualdades con igualdades en las restricciones. Luego, los problemas se pueden escribir en la siguiente forma matricial 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, las variables de decisión y la variable que se va a maximizar? ${\displaystyle \mathbf {s} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle z}$

Ejemplo

El ejemplo anterior se convierte a la siguiente forma aumentada:

donde están las 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 matricial 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 , lo que proporciona un límite superior al valor óptimo del problema primario. En forma matricial, podemos expresar el problema primal como:

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

con el correspondiente problema dual simétrico ,

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. Uno es el hecho de que (para el dual simétrico) el dual de un programa lineal dual es el programa lineal primario 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 la 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 la 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 primal no está acotado, entonces el dual es inviable según el teorema de la dualidad débil. Asimismo, si el dual es ilimitado, entonces el primal debe ser inviable. Sin embargo, es posible que tanto lo dual como lo primario sean inviables. Consulte el programa lineal dual para obtener detalles y varios ejemplos más.

Variaciones

Dualidades cobertura/embalaje

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

Minimizar: b ^T y ,

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

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

El dual de un LP de cobertura es un LP de empaque , un programa lineal de la forma:

Maximizar: c ^T x ,

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

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

Ejemplos

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

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

Laxitud complementaria

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

Supongamos que x  = ( x ₁ ,  x ₂ , ... ,  x _n ) es factible primal y que y  = ( y ₁ ,  y ₂ , ... ,  y _m ) es factible dual. Sea ( w ₁ ,  w ₂ , ...,  w _m ) las variables de holgura primarias correspondientes, y sea ( z ₁ ,  z ₂ , ...,  z _n ) las variables de holgura duales correspondientes. Entonces x e y son óptimos para sus respectivos problemas si y sólo si

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

Entonces, si la i -ésima variable de holgura del primal no es cero, entonces la i -ésima variable del dual es igual a cero. Del mismo modo, 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 optimización 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 "sobras"), entonces cantidades adicionales de ese recurso no deben tener valor. De la misma manera, si hay holgura en el requisito de no negatividad del precio dual (sombra), es decir, el precio no es cero, entonces debe haber oferta escasa (no "sobras").

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 cada 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. Primero, si las restricciones son inconsistentes, entonces no existe una solución factible: por ejemplo, las restricciones x  ≥ 2 y x  ≤ 1 no pueden satisfacerse 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 máximo para funciones convexas (alternativamente, por el principio mínimo para funciones cóncavas ) ya que lineal Las funciones son tanto convexas como cóncavas. Sin embargo, algunos problemas tienen distintas soluciones óptimas; por ejemplo, el problema de encontrar una solución factible a 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 como 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 básicas factibles . El motivo de esta elección de nombre es el 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 del LP, existe un conjunto de d (o menos) restricciones de desigualdad del LP tales que, cuando tratamos esas d restricciones como igualdades, la solución única es x ^* . De este modo podemos estudiar estos vértices observando ciertos subconjuntos del conjunto de todas las restricciones (un conjunto discreto), en lugar del continuo de soluciones LP. 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 bases

Algoritmo simplex de Dantzig

El algoritmo simplex , desarrollado por George Dantzig en 1947, resuelve problemas de PL construyendo una solución factible en un vértice del politopo y luego caminando por un camino en los bordes del politopo hasta los vértices con valores no decrecientes de la función objetivo hasta que se alcanza un El óptimo se alcanza con seguridad. En muchos problemas prácticos se produce una " estancamiento ": se realizan muchos pivotes sin aumentar la función objetivo. ^{[10] [11]} En problemas prácticos raros, las versiones habituales del algoritmo simplex pueden en realidad "ciclar". ^[11] Para evitar ciclos, los investigadores desarrollaron nuevas reglas pivotantes. ^[12]

En la práctica, el algoritmo simplex es bastante eficiente y se puede garantizar que encontrará el óptimo global si se toman ciertas precauciones contra el ciclismo . Se ha demostrado que el algoritmo simplex resuelve problemas "aleatorios" de manera eficiente, es decir, en un número cúbico de pasos, ^[13] que es similar a su comportamiento en problemas prácticos. ^{[10] [14]}

Sin embargo, el algoritmo simplex tiene un comportamiento deficiente 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 exponenciales en el tamaño del problema. ^{[10] [15] [16]} De hecho, durante algún tiempo no se sabía si el problema de programación lineal era solucionable en tiempo polinómico , es decir, de clase de complejidad P.

Algoritmo entrecruzado

Al igual que el algoritmo simplex de Dantzig, el algoritmo entrecruzado es un algoritmo de intercambio de bases que pivota entre bases. Sin embargo, el algoritmo entrecruzado no necesita mantener la viabilidad, sino que puede pasar de una base factible a una base inviable. El algoritmo entrecruzado no tiene complejidad de tiempo polinomial para la programación lineal. Ambos algoritmos visitan todas las esquinas 2D ^de un cubo (perturbado) en la dimensión  D , el cubo de Klee-Minty , en el peor de los casos . ^{[12] [17]}

Punto interior

A diferencia del algoritmo simplex, que encuentra una solución óptima atravesando las aristas 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 elipsoide, siguiendo a Khachiyan

Este es el primer algoritmo de tiempo polinomial en el peor de los casos jamás encontrado para 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. ^[6] Leonid Khachiyan resolvió este problema de complejidad de larga data en 1979 con la introducción del método del elipsoide . El análisis de convergencia tiene predecesores (de 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 gran importancia para establecer la solubilidad en tiempo polinomial de programas lineales. El algoritmo no fue un gran avance computacional, ya que el método simplex es más eficiente para todos, excepto para familias de programas lineales 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 la programación lineal. El algoritmo de Karmarkar ^[7] mejoró el límite polinomial del peor de los casos de Khachiyan ^[6] (dando ). Karmarkar afirmó que su algoritmo era mucho más rápido en la LP práctica que el método simplex, afirmación que generó un gran interés en los métodos de punto interior. ^[18] Desde el descubrimiento de Karmarkar, se han propuesto y analizado muchos métodos de puntos interiores. ${\displaystyle O(n^{3.5}L)}$

Algoritmo 87 de Vaidya

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

Algoritmo 89 de Vaidya

En 1989, Vaidya desarrolló un algoritmo que se ejecuta en el tiempo. ^[20] Hablando formalmente, el algoritmo toma 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, ^[21] donde representa el número de elementos distintos de cero y se mantiene en el peor de los casos. ${\displaystyle {\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)}$ ${\displaystyle nnz(A)}$ ${\displaystyle O(n^{2.5}L)}$

Algoritmo de tiempo de multiplicación de matrices actual

En 2019, Cohen, Lee y Song mejoraron el tiempo de ejecución , es el exponente de la multiplicación de matrices y es el exponente dual de la multiplicación de matrices . ^[22] se define (aproximadamente) como el número más grande tal que se puede multiplicar una matriz por una matriz en el tiempo. En un trabajo de seguimiento de Lee, Song y Zhang, reproducen el mismo resultado mediante un método diferente. ^[23] Estos dos algoritmos permanecen cuando y . El resultado gracias a Jiang, Song, Weinstein y Zhang mejoró a . ^[24] ${\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 punto interior y algoritmos simplex.

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

Problemas abiertos y trabajos recientes.

Problema no resuelto 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 avances potencialmente 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 mayores problemas sin resolver del siglo XXI. En palabras de Smale, la tercera versión del problema "es el principal problema no resuelto 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 de elipsoides 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, todavía deja abiertas las siguientes preguntas.

• ¿Existen reglas de pivote que conduzcan a variantes símplex en tiempo polinomial?
• ¿Todos los gráficos 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 simplex. La inmensa eficiencia del algoritmo simplex en la práctica a pesar de su rendimiento teórico en tiempo exponencial sugiere que puede haber variaciones del algoritmo simplex que se ejecutan en tiempo polinomial o incluso fuertemente polinomial. Sería de gran importancia práctica y teórica saber si existen tales variantes, particularmente como método para decidir si LP 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 un vértice a otro 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, estamos interesados ​​en conocer el diámetro máximo teórico de los gráficos 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 superpolinómico. Si existen tales politopos, entonces ninguna variante de seguimiento de bordes 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 viabilidad primaria (o dual). Por otro lado, los métodos de pivote entrecruzado no preservan la viabilidad (primaria o dual): pueden visitar bases primariamente factibles, duales factibles o primarias y duales inviables en cualquier orden. Los métodos de pivote de este tipo se han estudiado desde los años 1970. ^[26] Esencialmente, estos métodos intentan encontrar la ruta de pivote más corta en el politopo de disposición bajo el problema de programación lineal. A diferencia de los gráficos politópicos, se sabe que los gráficos de disposición de politopos tienen un diámetro pequeño, lo que permite la posibilidad de un algoritmo de pivote entrecruzado en tiempo fuertemente polinomial sin resolver preguntas sobre el diámetro de los politopos generales. ^[12]

Incógnitas enteras

Si se requiere que todas las variables desconocidas sean números enteros, entonces el problema se denomina problema de programación entera (IP) o de programación lineal entera (ILP). 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 (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-difícil 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). Por lo general, estos también son NP-difíciles 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 eficientemente, en particular problemas en los que la matriz de restricciones es totalmente unimodular y los lados derechos de las restricciones son números enteros o, más en general, en los que el sistema tiene la integralidad dual total. (TDI) propiedad.

Los algoritmos avanzados para resolver programas lineales enteros incluyen:

• método del plano de corte
• Rama y atado
• Rama y corte
• Sucursal y precio
• Si el problema tiene alguna estructura adicional, es posible aplicar la generación retrasada de columnas .

Padberg y Beasley analizan estos algoritmos de programación entera .

Programas lineales integrales

Un programa lineal en variables reales se dice que es integral si tiene al menos una solución óptima que sea integral, es decir, formada únicamente por valores enteros. Asimismo, se dice que un poliedro es integral si para todas las funciones objetivo factibles acotadas c , el programa lineal tiene un óptimo con coordenadas enteras. Como observaron Edmonds y Giles en 1977, se puede decir de manera equivalente que el poliedro es integral si para cada función objetivo integral factible acotada c , el valor óptimo del programa lineal es un número 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 cáscara convexa de las soluciones es un poliedro integral; Si este poliedro tiene una descripción agradable/compacta, entonces podemos encontrar eficientemente la solución óptima factible 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 capa convexa de 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 obligadas 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 obligadas a ser números enteros, sino que se ha demostrado de alguna manera que el problema continuo siempre tiene un valor óptimo integral (asumiendo que c es integral), y este valor óptimo se puede encontrar eficientemente 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 que incluyen la propiedad de descomposición de números enteros y la integralidad dual total . Otros LP integrales específicos y 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, ver Schrijver 2003.

Solvers y lenguajes de scripting (programación)

Licencias permisivas :

Licencias copyleft (recíprocas) :

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

Licencias propietarias :

Ver también

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

Notas

1. Gerard Sierksma; Yori Zwols (2015). Optimización lineal y entera: teoría y práctica (3ª ed.). Prensa CRC. pag. 1.ISBN _ 978-1498710169.
2. "Programación lineal | Definición y hechos | Britannica". www.britannica.com . Consultado el 20 de noviembre de 2023 .
3. George B. Dantzig (abril de 1982). «Reminiscencias sobre los orígenes de la programación lineal» (PDF) . Cartas de investigación operativa . 1 (2): 43–48. doi :10.1016/0167-6377(82)90043-8. Archivado desde el original el 20 de mayo de 2015.
4. Alejandro Schrijver (1998). Teoría de la Programación Lineal y Entera . John Wiley e hijos. págs. 221–222. ISBN 978-0-471-98232-6.
5. Dantzig, George B.; Thapa, Mukund Narain (1997). Programación lineal . Nueva York: Springer. pag. xxvii. ISBN 0387948333. OCLC  35318475.
6. Leonid Khachiyan (1979). "Un algoritmo polinomial para programación lineal". Doklady Akademii Nauk SSSR . 224 (5): 1093–1096.
7. Narendra Karmarkar (1984). "Un nuevo algoritmo de tiempo polinomial para programación lineal". Combinatoria . 4 (4): 373–395. doi :10.1007/BF02579150. S2CID  7257867.
8. M. Grundmann; V. Kwatra; I. Essa (2011). "Estabilización de vídeo dirigida automáticamente con trayectorias de cámara óptimas y robustas L1". CVPR 2011 (PDF) . págs. 225-232. doi :10.1109/CVPR.2011.5995525. ISBN 978-1-4577-0394-2. S2CID  17707171.
9. Vazirani (2001, pág.112)
10. Dantzig y Thapa (2003)
11. Padberg (1999)
12. Fukuda, Komei ; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos entrecruzados: una nueva visión de los algoritmos de pivote". Programación Matemática, Serie B. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373 . doi :10.1007/BF02614325. SEÑOR  1464775. S2CID  2794181. 
13. Borgwardt (1987)
14. Todd (2002)
15. Murty (1983)
16. Papadimitriou y Steiglitz
17. Roos, C. (1990). "Un ejemplo exponencial de la regla pivotante de Terlaky para el método simplex entrecruzado". Programación Matemática . Serie A. 46 (1): 79–84. doi :10.1007/BF01585729. SEÑOR  1045573. S2CID  33463483.
18. Strang, Gilbert (1 de junio de 1987). "El algoritmo de Karmarkar y su lugar en las matemáticas aplicadas". El inteligente matemático . 9 (2): 4–10. doi :10.1007/BF03025891. ISSN  0343-6993. SEÑOR  0883185. S2CID  123541868.
19. Vaidya, Pravin M. (1987). Un algoritmo para programación lineal que requiere operaciones aritméticas . 28º Simposio anual del IEEE sobre fundamentos de la informática. FOCS. ${\displaystyle {O}(((m+n)n^{2}+(m+n)^{1.5}n)L)}$
20. Vaidya, Pravin M. (1989). "Acelerar la programación lineal mediante la 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.
21. 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 .
22. Cohen, Michael B.; Lee, Yin-Tat; Canción, Zhao (2018). Resolución de programas lineales en el tiempo de multiplicación de matrices actuales . 51º Simposio Anual ACM sobre Teoría de la Computación. STOC'19. arXiv : 1810.07896 .
23. Lee, Yin-Tat; Canción, Zhao; Zhang, Qiuyi (2019). Resolviendo la minimización empírica del riesgo en el tiempo de multiplicación de la matriz actual . Jornada sobre Teoría del Aprendizaje. COLT'19. arXiv : 1905.04447 .
24. Jiang, Shunhua; Canción, Zhao; Weinstein, Omri; Zhang, Hengjie (2020). "Matriz dinámica inversa más rápida para LP más rápidos ". arXiv : 2004.07470 .
25. 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. 
26. Anstreicher, Kurt M.; Terlaky, Tamás (1994). "Un algoritmo simplex de acumulación monótona para programación lineal". La investigación de operaciones . 42 (3): 556–561. doi : 10.1287/opre.42.3.556 . ISSN  0030-364X. JSTOR  171894.
27. "Guía de referencia de lp_solve (5.5.2.5)". mit.edu . Consultado el 10 de agosto de 2023 .
28. "Interfaces de idiomas externos" . Consultado el 3 de diciembre de 2021 .
29. "comando lp_solve" . Consultado el 3 de diciembre de 2021 .
30. "COR@L - Investigación de optimización computacional en Lehigh". lehigh.edu .
31. 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
32. 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 aproximada de cálculo del equilibrio 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 págs. 339–347 en TC Koopmans (ed.): Activity Analysis of Production and Allocation , Nueva York-Londres 1951 (Wiley & Chapman-Hall)
• JE Beasley, editor. Avances en Programación Lineal y Entera . Oxford Science, 1996. (Colección de encuestas)
• Suave, Robert G. (1977). "Nuevas reglas de pivote finito para el método simplex". 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. Lo básico 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.(Completo, que cubre, por ejemplo, algoritmos de pivote y de punto interior, problemas a gran escala, descomposición siguiendo a Dantzig-Wolfe y Benders , e introducción a la programación estocástica ).
• Edmonds, Jack; Giles, Rick (1977). "Una relación mínimo-máximo para funciones submodulares en gráficos". Estudios en 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 de pivote". Programación Matemática, Serie B. 79 (1–3): 369–395. CiteSeerX  10.1.1.36.9373 . doi :10.1007/BF02614325. SEÑOR  1464775. S2CID  2794181.
• Gondzio, Jacek; Terlaky, Tamás (1996). "3 Una vista computacional de los métodos de puntos interiores". En JE Beasley (ed.). Avances en programación lineal y entera . Serie de conferencias de Oxford sobre matemáticas y sus aplicaciones. vol. 4. Nueva York: Oxford University Press. págs. 103-144. MR  1438311. Archivo posdata en el sitio web de Gondzio y en el sitio web de Terlaky de la Universidad McMaster.
• Murty, Katta G. (1983). Programación lineal . Nueva York: John Wiley & Sons, Inc. págs. xix+482. ISBN 978-0-471-09725-9. SEÑOR  0720547. (referencia completa a los enfoques clásicos).
• Evar D. Nering y Albert W. Tucker , 1993, Programas lineales y problemas relacionados , Academic Press. (elemental)
• Padberg, M. (1999). Optimización lineal y extensiones, segunda edición . Springer-Verlag.(Relato cuidadosamente escrito de algoritmos simplex primarios y duales y algoritmos proyectivos, con una introducción a la programación lineal entera, que presenta el problema del viajante de Ulises ).
• Papadimitriou, Christos H .; Steiglitz, Kenneth. Optimización combinatoria: algoritmos y complejidad (reedición corregida con una nueva edición del 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 invitada, del Simposio Internacional sobre 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)

Otras lecturas

• 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–94. Describe un algoritmo de intersección aleatoria 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 integridad NP . 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)
• Alejandro Schrijver (2003). Optimización combinatoria: poliedros y eficiencia . Saltador.
• Alexander Schrijver, Teoría de la programación lineal y entera . John Wiley e hijos, 1998, ISBN 0-471-98232-6 (matemático) 
• Gerard Sierksma; Yori Zwols (2015). Optimización lineal y entera: teoría y práctica . Prensa CRC. ISBN 978-1-498-71016-9.
• Gerard Sierksma; Diptesh Ghosh (2010). Redes en Acción; Ejercicios de texto e ordenador en optimización de redes . Saltador. ISBN 978-1-4419-5512-8.(modelado de optimización lineal)
• HP Williams, Construcción de modelos en programación matemática , quinta edición, 2013. (Modelado)
• Stephen J. Wright, 1997, Métodos de punto interior dual-primario , 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 a 3 y 6 a 7 en Lectures on Polytopes , Springer-Verlag, Nueva York, 1994. (Geometría)

enlaces externos

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