Algoritmo simplex

Algoritmo para programación lineal

En optimización matemática , el algoritmo simplex de Dantzig (o método simplex ) es un algoritmo popular para la programación lineal . ^[1]

El nombre del algoritmo se deriva del concepto de símplex y fue sugerido por TS Motzkin . ^[2] En realidad, no se utilizan símplices en el método, pero una interpretación del mismo es que opera sobre conos simpliciales , y estos se convierten en símplices propios con una restricción adicional. ^{[3] [4] [5] [6]} Los conos simpliciales en cuestión son las esquinas (es decir, las vecindades de los vértices) de un objeto geométrico llamado politopo . La forma de este politopo está definida por las restricciones aplicadas a la función objetivo.

Historia

George Dantzig trabajó en métodos de planificación para la Fuerza Aérea del Ejército de los EE. UU. durante la Segunda Guerra Mundial utilizando una calculadora de escritorio . Durante 1946, su colega lo desafió a mecanizar el proceso de planificación para distraerlo de aceptar otro trabajo. Dantzig formuló el problema como desigualdades lineales inspiradas en el trabajo de Wassily Leontief , sin embargo, en ese momento no incluyó un objetivo como parte de su formulación. Sin un objetivo, una gran cantidad de soluciones pueden ser factibles y, por lo tanto, para encontrar la "mejor" solución factible, se deben utilizar "reglas básicas" especificadas por los militares que describan cómo se pueden lograr los objetivos en lugar de especificar un objetivo en sí. La idea central de Dantzig fue darse cuenta de que la mayoría de estas reglas básicas se pueden traducir en una función objetivo lineal que debe maximizarse. ^[7] El desarrollo del método símplex fue evolutivo y se produjo durante un período de aproximadamente un año. ^[8]

Después de que Dantzig incluyera una función objetivo como parte de su formulación a mediados de 1947, el problema se volvió matemáticamente más manejable. Dantzig se dio cuenta de que uno de los problemas sin resolver que había tomado por error como tarea en la clase de su profesor Jerzy Neyman (y que en realidad resolvió más tarde), era aplicable para encontrar un algoritmo para programas lineales. Este problema implicaba encontrar la existencia de multiplicadores de Lagrange para programas lineales generales sobre un continuo de variables, cada una acotada entre cero y uno, y que satisfacían restricciones lineales expresadas en forma de integrales de Lebesgue . Dantzig publicó más tarde su "tarea" como tesis para obtener su doctorado. La geometría de columnas utilizada en esta tesis le dio a Dantzig una idea que le hizo creer que el método Simplex sería muy eficiente. ^[9]

Descripción general

Un sistema de inecuaciones lineales define un politopo como una región factible. El algoritmo símplex comienza en un vértice inicial y se desplaza a lo largo de los bordes del politopo hasta llegar al vértice de la solución óptima.

Algoritmo poliédrico del símplex en 3D

El algoritmo simplex opera en programas lineales en forma canónica

maximizar ${\textstyle \mathbf {c^{T}} \mathbf {x} }$

sujeto a y ${\displaystyle A\mathbf {x} \leq \mathbf {b} }$ ${\displaystyle \mathbf {x} \geq 0}$

con los coeficientes de la función objetivo, es la matriz transpuesta , y son las variables del problema, es una matriz p × n , y . Existe un proceso sencillo para convertir cualquier programa lineal en uno en forma estándar, por lo que el uso de esta forma de programas lineales no produce ninguna pérdida de generalidad. ${\displaystyle \mathbf {c} =(c_{1},\,\dots ,\,c_{n})}$ ${\displaystyle (\cdot )^{\mathrm {T} }}$ ${\displaystyle \mathbf {x} =(x_{1},\,\dots ,\,x_{n})}$ ${\displaystyle A}$ ${\displaystyle \mathbf {b} =(b_{1},\,\dots ,\,b_{p})}$

En términos geométricos, la región factible definida por todos los valores de tales que y es un politopo convexo (posiblemente ilimitado) . Un punto extremo o vértice de este politopo se conoce como solución factible básica (SBF). ${\displaystyle \mathbf {x} }$ ${\textstyle A\mathbf {x} \leq \mathbf {b} }$ ${\displaystyle \forall i,x_{i}\geq 0}$

Se puede demostrar que para un programa lineal en forma estándar, si la función objetivo tiene un valor máximo en la región factible, entonces tiene este valor en (al menos) uno de los puntos extremos. ^[10] Esto en sí mismo reduce el problema a un cálculo finito ya que hay un número finito de puntos extremos, pero el número de puntos extremos es inmanejablemente grande para todos, excepto los programas lineales más pequeños. ^[11]

También se puede demostrar que, si un punto extremo no es un punto máximo de la función objetivo, entonces hay una arista que contiene el punto de modo que el valor de la función objetivo es estrictamente creciente en la arista que se aleja del punto. ^[12] Si la arista es finita, entonces la arista se conecta a otro punto extremo donde la función objetivo tiene un valor mayor, de lo contrario la función objetivo no está acotada por encima de la arista y el programa lineal no tiene solución. El algoritmo simplex aplica esta idea caminando a lo largo de las aristas del politopo hasta puntos extremos con valores objetivos cada vez mayores. Esto continúa hasta que se alcanza el valor máximo, o se visita una arista no acotada (concluyendo que el problema no tiene solución). El algoritmo siempre termina porque el número de vértices en el politopo es finito; además, dado que saltamos entre vértices siempre en la misma dirección (la de la función objetivo), esperamos que el número de vértices visitados sea pequeño. ^[12]

La solución de un programa lineal se logra en dos pasos. En el primer paso, conocido como Fase I, se encuentra un punto extremo inicial. Dependiendo de la naturaleza del programa esto puede ser trivial, pero en general se puede resolver aplicando el algoritmo símplex a una versión modificada del programa original. Los posibles resultados de la Fase I son que se encuentre una solución factible básica o que la región factible esté vacía. En este último caso el programa lineal se llama inviable . En el segundo paso, Fase II, se aplica el algoritmo símplex utilizando la solución factible básica encontrada en la Fase I como punto de partida. Los posibles resultados de la Fase II son una solución factible básica óptima o una arista infinita en la que la función objetivo no está acotada por encima. ^{[13] [14] [15]}

Formulario estándar

La transformación de un programa lineal a uno en forma estándar se puede realizar de la siguiente manera. ^[16] Primero, para cada variable con un límite inferior distinto de 0, se introduce una nueva variable que representa la diferencia entre la variable y el límite. La variable original se puede eliminar luego por sustitución. Por ejemplo, dada la restricción

${\displaystyle x_{1}\geq 5}$

Se introduce una nueva variable, , con ${\displaystyle y_{1}}$

${\displaystyle {\begin{aligned}y_{1}=x_{1}-5\\x_{1}=y_{1}+5\end{aligned}}}$

La segunda ecuación puede utilizarse para eliminar del programa lineal. De esta manera, todas las restricciones de límite inferior pueden cambiarse a restricciones de no negatividad. ${\displaystyle x_{1}}$

En segundo lugar, para cada restricción de desigualdad restante, se introduce una nueva variable, llamada variable de holgura , para cambiar la restricción a una restricción de igualdad. Esta variable representa la diferencia entre los dos lados de la desigualdad y se supone que no es negativa. Por ejemplo, las desigualdades

${\displaystyle {\begin{aligned}x_{2}+2x_{3}&\leq 3\\-x_{4}+3x_{5}&\geq 2\end{aligned}}}$

son reemplazados por

${\displaystyle {\begin{aligned}x_{2}+2x_{3}+s_{1}&=3\\-x_{4}+3x_{5}-s_{2}&=2\\s_{1},\,s_{2}&\geq 0\end{aligned}}}$

Es mucho más fácil realizar manipulaciones algebraicas en desigualdades en esta forma. En desigualdades donde ≥ aparece como la segunda, algunos autores se refieren a la variable introducida comoexcedente variable

En tercer lugar, se elimina cada variable no restringida del programa lineal. Esto se puede hacer de dos maneras: una es despejando la variable en una de las ecuaciones en las que aparece y luego eliminando la variable por sustitución. La otra es reemplazar la variable con la diferencia de dos variables restringidas. Por ejemplo, si no tiene restricciones, entonces se escribe ${\displaystyle z_{1}}$

${\displaystyle {\begin{aligned}&z_{1}=z_{1}^{+}-z_{1}^{-}\\&z_{1}^{+},\,z_{1}^{-}\geq 0\end{aligned}}}$

La ecuación puede utilizarse para eliminar del programa lineal. ${\displaystyle z_{1}}$

Cuando este proceso se complete, la región factible tendrá la forma

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} ,\,\forall \ x_{i}\geq 0}$

También es útil suponer que el rango de es el número de filas. Esto no produce pérdida de generalidad, ya que de lo contrario, el sistema tiene ecuaciones redundantes que se pueden descartar o el sistema es inconsistente y el programa lineal no tiene solución. ^[17] ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

Tabla simplex

Un programa lineal en forma estándar se puede representar como una tabla de la forma

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {A} &\mathbf {b} \end{bmatrix}}}$

La primera fila define la función objetivo y las filas restantes especifican las restricciones. El cero en la primera columna representa el vector cero de la misma dimensión que el vector (diferentes autores usan diferentes convenciones en cuanto al diseño exacto). Si las columnas de se pueden reorganizar de modo que contengan la matriz identidad de orden (el número de filas en ), entonces se dice que la tabla está en forma canónica . ^[18] Las variables correspondientes a las columnas de la matriz identidad se denominan variables básicas, mientras que las variables restantes se denominan variables no básicas o libres . Si los valores de las variables no básicas se establecen en 0, entonces los valores de las variables básicas se obtienen fácilmente como entradas en y esta solución es una solución factible básica. La interpretación algebraica aquí es que los coeficientes de la ecuación lineal representada por cada fila son , , o algún otro número. Cada fila tendrá una columna con valor , columnas con coeficientes y las columnas restantes con algunos otros coeficientes (estas otras variables representan nuestras variables no básicas). Al establecer los valores de las variables no básicas en cero, garantizamos en cada fila que el valor de la variable representada por a en su columna sea igual al valor en esa fila. ${\displaystyle \mathbf {b} }$ ${\displaystyle \mathbf {A} }$ ${\displaystyle p}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {b} }$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle p-1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle b}$

Por el contrario, dada una solución factible básica, las columnas correspondientes a las variables no nulas se pueden expandir a una matriz no singular. Si la tabla correspondiente se multiplica por la inversa de esta matriz, el resultado es una tabla en forma canónica. ^[19]

Dejar

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} _{B}^{T}&-\mathbf {c} _{D}^{T}&0\\0&I&\mathbf {D} &\mathbf {b} \end{bmatrix}}}$

sea ​​una tabla en forma canónica. Se pueden aplicar transformaciones adicionales de adición de filas para eliminar los coeficientes cT.B.
​ de la función objetivo. Este proceso se denomina determinación de precios y da como resultado una tabla canónica

${\displaystyle {\begin{bmatrix}1&0&-{\bar {\mathbf {c} }}_{D}^{T}&z_{B}\\0&I&\mathbf {D} &\mathbf {b} \end{bmatrix}}}$

donde z _B es el valor de la función objetivo en la solución factible básica correspondiente. Los coeficientes actualizados, también conocidos como coeficientes de costo relativo , son las tasas de cambio de la función objetivo con respecto a las variables no básicas. ^[14]

Operaciones de pivote

La operación geométrica de pasar de una solución factible básica a una solución factible básica adyacente se implementa como una operación pivote . Primero, se selecciona un elemento pivote distinto de cero en una columna no básica. La fila que contiene este elemento se multiplica por su recíproco para cambiar este elemento a 1, y luego se suman múltiplos de la fila a las otras filas para cambiar las otras entradas en la columna a 0. El resultado es que, si el elemento pivote está en una fila r , entonces la columna se convierte en la r -ésima columna de la matriz identidad. La variable para esta columna es ahora una variable básica, que reemplaza a la variable que correspondía a la r -ésima columna de la matriz identidad antes de la operación. En efecto, la variable correspondiente a la columna pivote entra en el conjunto de variables básicas y se llama variable entrante , y la variable que se reemplaza sale del conjunto de variables básicas y se llama variable saliente . La tabla todavía está en forma canónica pero con el conjunto de variables básicas cambiado por un elemento. ^{[13] [14]}

Algoritmo

Sea un programa lineal dado por una tabla canónica. El algoritmo símplex procede realizando operaciones pivote sucesivas, cada una de las cuales da una solución factible básica mejorada; la elección del elemento pivote en cada paso está determinada en gran medida por el requisito de que este pivote mejore la solución.

Introducir selección de variables

Dado que la variable de entrada, en general, aumentará de 0 a un número positivo, el valor de la función objetivo disminuirá si la derivada de la función objetivo con respecto a esta variable es negativa. De manera equivalente, el valor de la función objetivo aumenta si se selecciona la columna pivote de modo que la entrada correspondiente en la fila objetivo de la tabla sea positiva.

Si hay más de una columna, de modo que la entrada en la fila objetivo es positiva, entonces la elección de cuál agregar al conjunto de variables básicas es algo arbitraria y se han desarrollado varias reglas de elección de variables de entrada ^[20], como el algoritmo Devex ^[21] .

Si todas las entradas en la fila objetivo son menores o iguales a 0, entonces no se puede elegir la variable de entrada y la solución es, de hecho, óptima. Se ve fácilmente que es óptima ya que la fila objetivo ahora corresponde a una ecuación de la forma

$${\displaystyle z(\mathbf {x} )=z_{B}+{\text{non-positive terms corresponding to non-basic variables}}}$$

Al cambiar la regla de elección de la variable entrante para que seleccione una columna donde la entrada en la fila objetivo sea negativa, se cambia el algoritmo para que encuentre el mínimo de la función objetivo en lugar del máximo.

Selección de variable de salida

Una vez que se ha seleccionado la columna pivote, la elección de la fila pivote está determinada en gran medida por el requisito de que la solución resultante sea factible. En primer lugar, solo se consideran las entradas positivas en la columna pivote, ya que esto garantiza que el valor de la variable entrante no será negativo. Si no hay entradas positivas en la columna pivote, entonces la variable entrante puede tomar cualquier valor no negativo y la solución seguirá siendo factible. En este caso, la función objetivo no está acotada por debajo y no hay un mínimo.

A continuación, se debe seleccionar la fila pivote de modo que todas las demás variables básicas permanezcan positivas. Un cálculo muestra que esto ocurre cuando el valor resultante de la variable entrante es mínimo. En otras palabras, si la columna pivote es c , entonces se elige la fila pivote r de modo que

${\displaystyle b_{r}/a_{rc}\,}$

es el mínimo sobre todo r de modo que a _rc > 0. Esto se llama prueba de razón mínima . ^[20] Si hay más de una fila para la que se alcanza el mínimo, se puede utilizar una regla de elección de variable eliminada ^{[22] para realizar la determinación.}

Ejemplo

Consideremos el programa lineal

Minimizar

${\displaystyle Z=-2x-3y-4z\,}$

Sujeto a

${\displaystyle {\begin{aligned}3x+2y+z&\leq 10\\2x+5y+3z&\leq 15\\x,\,y,\,z&\geq 0\end{aligned}}}$

Con la adición de las variables de holgura s y t , esto se representa mediante la tabla canónica

${\displaystyle {\begin{bmatrix}1&2&3&4&0&0&0\\0&3&2&1&1&0&10\\0&2&5&3&0&1&15\end{bmatrix}}}$

donde las columnas 5 y 6 representan las variables básicas s y t y la solución factible básica correspondiente es

${\displaystyle x=y=z=0,\,s=10,\,t=15.}$

Las columnas 2, 3 y 4 se pueden seleccionar como columnas pivote; en este ejemplo, se selecciona la columna 4. Los valores de z resultantes de la elección de las filas 2 y 3 como filas pivote son 10/1 = 10 y 15/3 = 5 respectivamente. De estos, el mínimo es 5, por lo que la fila 3 debe ser la fila pivote. Al realizar el pivote se obtiene

${\displaystyle {\begin{bmatrix}3&-2&-11&0&0&-4&-60\\0&7&1&0&3&-1&15\\0&2&5&3&0&1&15\end{bmatrix}}}$

Ahora las columnas 4 y 5 representan las variables básicas z y s y la solución factible básica correspondiente es

${\displaystyle x=y=t=0,\,z=5,\,s=5.}$

Para el siguiente paso, no hay entradas positivas en la fila de objetivos y, de hecho,

$${\displaystyle Z={\frac {-60+2x+11y+4t}{3}}=-20+{\frac {2x+11y+4t}{3}}}$$

Por lo tanto, el valor mínimo de Z es −20.

Encontrar un cuadro canónico inicial

En general, un programa lineal no se dará en la forma canónica y se debe encontrar una tabla canónica equivalente antes de que pueda comenzar el algoritmo simplex. Esto se puede lograr mediante la introducción de variables artificiales . Las columnas de la matriz identidad se agregan como vectores columna para estas variables. Si el valor b para una ecuación de restricción es negativo, la ecuación se niega antes de agregar las columnas de la matriz identidad. Esto no cambia el conjunto de soluciones factibles o la solución óptima, y ​​garantiza que las variables de holgura constituirán una solución factible inicial. La nueva tabla está en forma canónica pero no es equivalente al problema original. Por lo tanto, se introduce una nueva función objetivo, igual a la suma de las variables artificiales, y se aplica el algoritmo simplex para encontrar el mínimo; el programa lineal modificado se llama problema de la Fase I. ^[23]

El algoritmo simplex aplicado al problema de la Fase I debe terminar con un valor mínimo para la nueva función objetivo ya que, al ser la suma de variables no negativas, su valor está acotado por debajo de 0. Si el mínimo es 0, entonces las variables artificiales pueden eliminarse de la tabla canónica resultante produciendo una tabla canónica equivalente al problema original. El algoritmo simplex puede entonces aplicarse para encontrar la solución; este paso se llama Fase II . Si el mínimo es positivo, entonces no hay solución factible para el problema de la Fase I donde las variables artificiales son todas cero. Esto implica que la región factible para el problema original está vacía, y por lo tanto el problema original no tiene solución. ^{[13] [14] [24]}

Ejemplo

Consideremos el programa lineal

Minimizar

${\displaystyle Z=-2x-3y-4z\,}$

Sujeto a

${\displaystyle {\begin{aligned}3x+2y+z&=10\\2x+5y+3z&=15\\x,\,y,\,z&\geq 0\end{aligned}}}$

Esto está representado por la tabla (no canónica)

${\displaystyle {\begin{bmatrix}1&2&3&4&0\\0&3&2&1&10\\0&2&5&3&15\end{bmatrix}}}$

Introduzca las variables artificiales u y v y la función objetivo W  =  u  +  v , dando como resultado una nueva tabla

${\displaystyle {\begin{bmatrix}1&0&0&0&0&-1&-1&0\\0&1&2&3&4&0&0&0\\0&0&3&2&1&1&0&10\\0&0&2&5&3&0&1&15\end{bmatrix}}}$

La ecuación que define la función objetivo original se mantiene en previsión de la Fase II.

Por construcción, u y v son ambas variables básicas ya que forman parte de la matriz de identidad inicial. Sin embargo, la función objetivo W actualmente supone que u y v son ambas 0. Para ajustar la función objetivo para que sea el valor correcto donde u  = 10 y v  = 15, agregue la tercera y cuarta filas a la primera fila dando

${\displaystyle {\begin{bmatrix}1&0&5&7&4&0&0&25\\0&1&2&3&4&0&0&0\\0&0&3&2&1&1&0&10\\0&0&2&5&3&0&1&15\end{bmatrix}}}$

Seleccione la columna 5 como columna pivote, de modo que la fila pivote debe ser la fila 4 y la tabla actualizada sea

${\displaystyle {\begin{bmatrix}3&0&7&1&0&0&-4&15\\0&3&-2&-11&0&0&-4&-60\\0&0&7&1&0&3&-1&15\\0&0&2&5&3&0&1&15\end{bmatrix}}}$

Ahora seleccione la columna 3 como columna pivote, para lo cual la fila 3 debe ser la fila pivote, para obtener

${\displaystyle {\begin{bmatrix}7&0&0&0&0&-7&-7&0\\0&7&0&-25&0&2&-10&-130\\0&0&7&1&0&3&-1&15\\0&0&0&11&7&-2&3&25\end{bmatrix}}}$

Las variables artificiales ahora son 0 y pueden eliminarse, obteniendo una tabla canónica equivalente al problema original:

${\displaystyle {\begin{bmatrix}7&0&-25&0&-130\\0&7&1&0&15\\0&0&11&7&25\end{bmatrix}}}$

Esto, fortuitamente, ya es óptimo y el valor óptimo para el programa lineal original es −130/7.

Temas avanzados

Implementación

La forma de tabla utilizada anteriormente para describir el algoritmo se presta a una implementación inmediata en la que la tabla se mantiene como una matriz rectangular ( m  + 1) por ( m  +  n  + 1). Es sencillo evitar el almacenamiento de las m columnas explícitas de la matriz de identidad que aparecerán dentro de la tabla en virtud de que B es un subconjunto de las columnas de [ A ,  I ]. Esta implementación se conoce como el " algoritmo simplex estándar ". La sobrecarga de almacenamiento y cálculo es tal que el método simplex estándar es un enfoque prohibitivamente costoso para resolver grandes problemas de programación lineal.

En cada iteración simplex, los únicos datos requeridos son la primera fila de la tabla, la columna (pivotal) de la tabla correspondiente a la variable entrante y el lado derecho. Este último se puede actualizar utilizando la columna pivotal y la primera fila de la tabla se puede actualizar utilizando la fila (pivotal) correspondiente a la variable saliente. Tanto la columna pivotal como la fila pivotal se pueden calcular directamente utilizando las soluciones de sistemas lineales de ecuaciones que involucran la matriz B y un producto matriz-vector utilizando A . Estas observaciones motivan el " algoritmo simplex revisado ", para el cual las implementaciones se distinguen por su representación invertible de  B . ^[25]

En los grandes problemas de programación lineal, A es típicamente una matriz dispersa y, cuando se aprovecha la dispersión resultante de B al mantener su representación invertible, el algoritmo símplex revisado es mucho más eficiente que el método símplex estándar. Los solucionadores símplex comerciales se basan en el algoritmo símplex revisado. ^{[24] [25] [26] [27] [28]}

Degeneración: estancamiento y ciclo

Si los valores de todas las variables básicas son estrictamente positivos, entonces un pivote debe resultar en una mejora en el valor objetivo. Cuando este es siempre el caso, ningún conjunto de variables básicas ocurre dos veces y el algoritmo símplex debe terminar después de un número finito de pasos. Las soluciones factibles básicas donde al menos una de las variables básicas es cero se denominan degeneradas y pueden dar lugar a pivotes para los que no hay una mejora en el valor objetivo. En este caso, no hay un cambio real en la solución, sino solo un cambio en el conjunto de variables básicas. Cuando varios de estos pivotes ocurren en sucesión, no hay ninguna mejora; en grandes aplicaciones industriales, la degeneración es común y este " estancamiento " es notable. Peor que el estancamiento es la posibilidad de que el mismo conjunto de variables básicas ocurra dos veces, en cuyo caso, las reglas de pivote deterministas del algoritmo símplex producirán un bucle infinito o "ciclo". Si bien la degeneración es la regla en la práctica y el estancamiento es común, el ciclo es poco común en la práctica. En Padberg se presenta una discusión de un ejemplo de ciclo práctico . ^[24] La regla de Bland evita los ciclos y, por lo tanto, garantiza que el algoritmo simplex siempre termine. ^{[24] [29] [30]} Otro algoritmo pivotante, el algoritmo criss-cross nunca realiza ciclos en programas lineales. ^[31]

Las reglas de pivote basadas en la historia, como la regla de Zadeh y la regla de Cunningham, también intentan evitar el problema del estancamiento y el ciclo haciendo un seguimiento de la frecuencia con la que se utilizan determinadas variables y luego favorecen las variables que se han utilizado con menos frecuencia.

Eficiencia en el peor de los casos

El método simplex es notablemente eficiente en la práctica y fue una gran mejora con respecto a métodos anteriores como la eliminación de Fourier-Motzkin . Sin embargo, en 1972, Klee y Minty ^[32] dieron un ejemplo, el cubo de Klee-Minty , que mostraba que la complejidad del peor caso del método simplex tal como lo formuló Dantzig es el tiempo exponencial . Desde entonces, para casi todas las variaciones del método, se ha demostrado que existe una familia de programas lineales para los que funciona mal. Es una pregunta abierta si existe una variación con el tiempo polinomial , aunque se conocen reglas de pivote subexponenciales. ^[33]

En 2014, se demostró ^{[ cita requerida ]} que una variante particular del método simplex es NP-poderosa, es decir, se puede utilizar para resolver, con sobrecarga polinómica, cualquier problema en NP implícitamente durante la ejecución del algoritmo. Además, decidir si una variable dada alguna vez entra en la base durante la ejecución del algoritmo en una entrada dada, y determinar el número de iteraciones necesarias para resolver un problema dado, son ambos problemas NP-difíciles . ^[34] Casi al mismo tiempo se demostró que existe una regla pivote artificial para la cual el cálculo de su salida es PSPACE-completo . ^[35] En 2015, esto se fortaleció para mostrar que el cálculo de la salida de la regla pivote de Dantzig es PSPACE-completo . ^[36]

Eficiencia en la práctica

El análisis y la cuantificación de la observación de que el algoritmo simplex es eficiente en la práctica a pesar de su complejidad exponencial en el peor de los casos ha llevado al desarrollo de otras medidas de complejidad. El algoritmo simplex tiene una complejidad de caso promedio en tiempo polinomial bajo varias distribuciones de probabilidad , y el desempeño promedio preciso del algoritmo simplex depende de la elección de una distribución de probabilidad para las matrices aleatorias . ^{[37] [38]} Otro enfoque para estudiar los " fenómenos típicos " utiliza la teoría de categorías de Baire a partir de la topología general y muestra que (topológicamente) "la mayoría" de las matrices se pueden resolver mediante el algoritmo simplex en un número polinomial de pasos. ^{[ cita requerida ]}

Otro método para analizar el desempeño del algoritmo simplex estudia el comportamiento de los peores escenarios bajo pequeñas perturbaciones: ¿son los peores escenarios estables bajo un pequeño cambio (en el sentido de estabilidad estructural ), o se vuelven manejables? Esta área de investigación, llamada análisis suavizado , se introdujo específicamente para estudiar el método simplex. De hecho, el tiempo de ejecución del método simplex en la entrada con ruido es polinomial en el número de variables y la magnitud de las perturbaciones. ^{[39] [40]}

Otros algoritmos

Otros algoritmos para resolver problemas de programación lineal se describen en el artículo de programación lineal . Otro algoritmo de pivote de intercambio de base es el algoritmo criss-cross . ^{[41] [42]} Existen algoritmos de tiempo polinomial para programación lineal que utilizan métodos de puntos interiores: estos incluyen el algoritmo elipsoidal de Khachiyan , el algoritmo proyectivo de Karmarkar y los algoritmos de seguimiento de trayectorias . ^[15] El método Big-M es una estrategia alternativa para resolver un programa lineal, utilizando un símplex monofásico.

Programación lineal-fraccional

La programación lineal-fraccional (LFP) es una generalización de la programación lineal (PL). En la PL, la función objetivo es una función lineal , mientras que la función objetivo de un programa lineal-fraccional es un cociente de dos funciones lineales. En otras palabras, un programa lineal es un programa lineal-fraccional en el que el denominador es la función constante que tiene el valor uno en todas partes. Un programa lineal-fraccional se puede resolver mediante una variante del algoritmo simplex ^{[43] [44] [45] [46]} o mediante el algoritmo criss-cross ^[47] .

Véase también

• Regla de pivote de Bland , que evita el ciclado
• Algoritmo entrecruzado
• Método del plano de corte
• Algoritmo Devex
• Eliminación de Fourier-Motzkin
• Descenso de gradiente
• Algoritmo de Karmarkar
• Heurística simplicial de Nelder-Mead
• Funciones de pérdida : un tipo de función objetivo

Notas

1. Murty, Katta G. (2000). Programación lineal. John Wiley & Sons.
2. Murty (1983, Comentario 2.2)
3. Murty (1983, Nota 3.9)
4. Stone, Richard E.; Tovey, Craig A. (1991). "Los algoritmos de escalamiento simplex y proyectivo como métodos de mínimos cuadrados iterativamente reponderados". SIAM Review . 33 (2): 220–237. doi :10.1137/1033049. JSTOR  2031142. MR  1124362.
5. Stone, Richard E.; Tovey, Craig A. (1991). "Fe de erratas: Los algoritmos de escalamiento simplex y proyectivo como métodos de mínimos cuadrados reponderados iterativamente". SIAM Review . 33 (3): 461. doi :10.1137/1033100. JSTOR  2031443. MR  1124362.
6. 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.
7. Dantzig, George B. (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.
8. Albers y Reid (1986). "Una entrevista con George B. Dantzig: el padre de la programación lineal". Revista de matemáticas universitarias . 17 (4): 292–314. doi :10.1080/07468342.1986.11972971.
9. Dantzig, George (mayo de 1987). "Orígenes del método símplex" (PDF) . En Nash, Stephen G. (ed.). Una historia de la computación científica . Association for Computing Machinery. págs. 141–151. doi :10.1145/87252.88081. ISBN . 978-0-201-50814-7. Archivado (PDF) del original el 29 de mayo de 2015.
10. Murty (1983, Teorema 3.3)
11. Murty (1983, pág. 143, Sección 3.13)
12. Murty (1983, pág. 137, Sección 3.8)
13. George B. Dantzig y Mukund N. Thapa. 1997. Programación lineal 1: Introducción . Springer-Verlag.
14. Evar D. Nering y Albert W. Tucker , 1993, Programas lineales y problemas relacionados , Academic Press. (primaria)
15. Robert J. Vanderbei, Programación lineal: fundamentos y extensiones, 3.ª ed., Serie internacional en investigación de operaciones y ciencia de la gestión, vol. 114, Springer Verlag, 2008. ISBN 978-0-387-74387-5 . 
16. Murty (1983, Sección 2.2)
17. Murty (1983, pág. 173)
18. Murty (1983, sección 2.3.2)
19. Murty (1983, sección 3.12)
20. Murty (1983, pág. 66)
21. Harris, Paula MJ. "Métodos de selección de pivotes del código Devex LP". Programación matemática 5.1 (1973): 1–28
22. Murty (1983, pág. 67)
23. Murty (1983, pág. 60)
24. Padberg, M. (1999). Optimización lineal y extensiones (segunda edición). Springer-Verlag. ISBN 3-540-65833-5.
25. Dantzig, George B. ; Thapa, Mukund N. (2003). Programación lineal 2: teoría y extensiones . Springer-Verlag.
26. Alevrás, Dmitris; Padberg, Manfred W. (2001). Optimización lineal y extensiones: problemas y soluciones . Texto universitario. Springer-Verlag. ISBN 3-540-41744-3.(Problemas de Padberg con soluciones.)
27. Maros, István; Mitra, Gautam (1996). "Algoritmos simplex". En JE Beasley (ed.). Avances en programación lineal y entera . Oxford Science. págs. 1–46. MR  1438309.
28. Maros, István (2003). Técnicas computacionales del método símplex . International Series in Operations Research & Management Science. Vol. 61. Boston, MA: Kluwer Academic Publishers. pp. xx+325. ISBN 978-1-4020-7332-8.Sr. 1960274  .
29. Bland, Robert G. (mayo de 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. MR  0459599. S2CID  18493293.
30. Murty (1983, pág. 79)
31. Existen problemas de optimización abstractos, llamados programas matroides orientados , en los que la regla de Bland cicla (incorrectamente) mientras que el algoritmo entrecruzado termina correctamente.
32. Klee, Victor ; Minty, George J. (1972). "¿Qué tan bueno es el algoritmo simplex?". En Shisha, Oved (ed.). Inequalities III (Actas del Tercer Simposio sobre Inequalities celebrado en la Universidad de California, Los Ángeles, California, del 1 al 9 de septiembre de 1969, dedicado a la memoria de Theodore S. Motzkin) . Nueva York-Londres: Academic Press. págs. 159-175. MR  0332165.
33. Hansen, Thomas; Zwick, Uri (2015), "Una versión mejorada de la regla de pivoteo de facetas aleatorias para el algoritmo Simplex", Actas del cuadragésimo séptimo simposio anual de la ACM sobre teoría de la computación , págs. 209-218, CiteSeerX 10.1.1.697.2526 , doi :10.1145/2746539.2746557, ISBN  9781450335362, S2CID1980659 ​
34. Disertar, Yann; Skutella, Martín (1 de noviembre de 2018). "El algoritmo simplex es NP-poderoso". Transmisión ACM. Algoritmos . 15 (1): 5:1–5:19. arXiv : 1311.5935 . doi :10.1145/3280847. ISSN  1549-6325. S2CID  54445546.
35. Adler, Ilan; Christos, Papadimitriou ; Rubinstein, Aviad (2014), "Sobre las reglas de pivoteo simplex y la teoría de la complejidad", Programación entera y optimización combinatoria , Lecture Notes in Computer Science, vol. 17, págs. 13-24, arXiv : 1404.3320 , doi : 10.1007/978-3-319-07557-0_2, ISBN 978-3-319-07556-3, Número de identificación del sujeto  891022
36. Fearnly, John; Savani, Rahul (2015), "La complejidad del método Simplex", Actas del cuadragésimo séptimo simposio anual de la ACM sobre teoría de la computación , págs. 201-208, arXiv : 1404.0605 , doi : 10.1145/2746539.2746558, ISBN 9781450335362, S2CID2116116 ​
37. Alexander Schrijver , Teoría de la programación lineal y entera . John Wiley & sons, 1998, ISBN 0-471-98232-6 (matemática) 
38. El algoritmo simplex toma en promedio D pasos para un cubo. Borgwardt (1987): Borgwardt, Karl-Heinz (1987). El método simplex: un análisis probabilístico . Algoritmos y combinatoria (textos de estudio e investigación). Vol. 1. Berlín: Springer-Verlag. pp. xii+268. ISBN 978-3-540-17096-9.Sr. 0868467  .
39. Spielman, Daniel; Teng, Shang-Hua (2001). "Análisis suavizado de algoritmos: por qué el algoritmo símplex suele tardar un tiempo polinomial". Actas del Trigésimo Tercer Simposio Anual de la ACM sobre Teoría de la Computación . ACM. págs. 296–305. arXiv : cs/0111050 . doi :10.1145/380752.380813. ISBN . 978-1-58113-349-3. Número de identificación del sujeto  1471.
40. Dadush, Daniel; Huiberts, Sophie (1 de enero de 2020). "Un análisis suavizado y amigable del método símplex". Revista SIAM de informática . 49 (5): STOC18–449. arXiv : 1711.05667 . doi :10.1137/18M1197205. ISSN  0097-5397. S2CID  226351624.
41. Terlaky, Tamás; Zhang, Shu Zhong (1993). "Reglas de pivote para programación lineal: una encuesta sobre desarrollos teóricos recientes". Anales de investigación de operaciones . 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658 . doi :10.1007/BF02096264. ISSN  0254-5330. MR  1260019. S2CID  6058077. 
42. 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). Ámsterdam: North-Holland Publishing: 369–395. doi :10.1007/BF02614325. MR  1464775. S2CID  2794181.
43. Murty (1983, Capítulo 3.20 (pp. 160-164) y pp. 168 y 179)
44. Capítulo cinco: Craven, BD (1988). Programación fraccionaria . Serie Sigma en Matemáticas Aplicadas. Vol. 4. Berlín: Heldermann Verlag. p. 145. ISBN 978-3-88538-404-5.Sr .  0949209.
45. Kruk, Serge; Wolkowicz, Henry (1999). "Programación pseudolineal". SIAM Review . 41 (4): 795–805. Bibcode :1999SIAMR..41..795K. CiteSeerX 10.1.1.53.7355 . doi :10.1137/S0036144598335259. JSTOR  2653207. MR  1723002. 
46. Mathis, Frank H.; Mathis, Lenora Jane (1995). "Un algoritmo de programación no lineal para la gestión hospitalaria". SIAM Review . 37 (2): 230–234. doi :10.1137/1037046. JSTOR  2132826. MR  1343214. S2CID  120626738.
47. Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "El método entrecruzado finito para la programación hiperbólica". Revista europea de investigación operativa . 114 (1): 198–214. CiteSeerX 10.1.1.36.7090 . doi :10.1016/S0377-2217(98)00049-6. ISSN  0377-2217. 

Referencias

• Murty, Katta G. (1983). Programación lineal . Nueva York: John Wiley & Sons, Inc., págs. xix+482. ISBN 978-0-471-09725-9.Sr. 0720547  .

Lectura adicional

Estas introducciones están escritas para estudiantes de informática e investigación de operaciones :

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sección 29.3: El algoritmo símplex, págs. 790–804. 
• Frederick S. Hillier y Gerald J. Lieberman: Introducción a la investigación de operaciones , 8.ª edición. McGraw-Hill. ISBN 0-07-123828-X 
• Rardin, Ronald L. (1997). Optimización en la investigación de operaciones . Prentice Hall. pág. 919. ISBN 978-0-02-398415-0.

Enlaces externos

• Introducción a la programación lineal y al algoritmo Simplex por Spyros Reveliotis del Instituto de Tecnología de Georgia.
• Greenberg, Harvey J., El politopo Klee-Minty muestra la complejidad temporal exponencial del método Simplex de la Universidad de Colorado en Denver (1997) Descargar PDF
• Método Simplex Un tutorial para el método Simplex con ejemplos (también de dos fases y método M).
• Calculadora Simplex de Mathstools de www.mathstools.com
• Ejemplo de procedimiento Simplex para un problema de programación lineal estándar por Thomas McFarland de la Universidad de Wisconsin-Whitewater.
• PHPSimplex: herramienta online para resolver problemas de programación lineal por Daniel Izquierdo y Juan José Ruiz de la Universidad de Málaga (UMA, España)
• Solucionador de problemas simples en línea simplex-m