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 programación lineal . ^[1]

El nombre del algoritmo se deriva del concepto de simplex y fue sugerido por TS Motzkin . ^[2] En realidad, los simples no se utilizan en el método, pero una interpretación del mismo es que opera en conos simpliciales , y estos se convierten en simples 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 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 inspirado 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 el ejército 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 esas reglas básicas pueden traducirse en una función objetivo lineal que debe maximizarse. ^[7] El desarrollo del método simplex fue evolutivo y ocurrió 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 no resueltos que había confundido con tarea en la clase de su profesor Jerzy Neyman (y que en realidad resolvió más tarde) era aplicable a la búsqueda de un algoritmo para programas lineales. Este problema implicó encontrar la existencia de multiplicadores de Lagrange para programas lineales generales sobre un continuo de variables, cada una limitada entre cero y uno, y satisfacer restricciones lineales expresadas en forma de integrales de Lebesgue . Dantzig publicó más tarde sus "deberes" como tesis para obtener su doctorado. La geometría de la columna 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 desigualdades lineales define un politopo como una región factible. El algoritmo simplex comienza en un vértice inicial y se mueve a lo largo de los bordes del politopo hasta llegar al vértice de la solución óptima.

Poliedro del algoritmo simplex 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 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 tal que y es un politopo convexo (posiblemente ilimitado) . Un punto extremo o vértice de este politopo se conoce como solución básica factible (BFS). ${\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 los programas lineales excepto los 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 un borde que contiene el punto de modo que el valor de la función objetivo aumenta estrictamente en el borde 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 arriba en la arista y el programa lineal no tiene solución. El algoritmo simplex aplica esta idea caminando a lo largo de los bordes 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 un borde ilimitado (concluyendo que el problema no tiene solución). El algoritmo siempre termina porque el número de vértices del 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 de partida. Dependiendo de la naturaleza del programa, esto puede resultar trivial, pero en general se puede resolver aplicando el algoritmo simplex a una versión modificada del programa original. Los posibles resultados de la Fase I son que se encuentre una solución básica factible 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 simplex utilizando la solución básica factible encontrada en la Fase I como punto de partida. Los posibles resultados de la Fase II son una solución básica factible óptima o un borde infinito en el que la función objetivo no está acotada arriba. ^{[13] [14] [15]}

Forma 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 puede entonces eliminarse mediante 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 se puede utilizar 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 con

${\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 manipulación algebraica de desigualdades de esta forma. En desigualdades donde aparece ≥ como la segunda, algunos autores se refieren a la variable introducida comovariable excedente .

En tercer lugar, cada variable no restringida se elimina del programa lineal. Esto se puede hacer de dos maneras, una es resolviendo 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, escriba ${\displaystyle z_{1}}$

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

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

Cuando se complete este proceso, 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 pueden eliminarse, o el sistema es inconsistente y el programa lineal no tiene solución. ^[17] ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

Cuadro simplex

Un programa lineal en forma estándar se puede representar como un cuadro de la forma

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\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 b (diferentes autores utilizan diferentes convenciones en cuanto al diseño exacto). Si las columnas de A se pueden reorganizar de modo que contenga la matriz identidad de orden p (el número de filas en A), entonces se dice que el cuadro está en forma canónica . ^[18] Las variables correspondientes a las columnas de la matriz identidad se denominan variables básicas mientras que el resto de variables 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 b y esta solución es una solución básica factible. 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, nos aseguramos en cada fila de que el valor de la variable representada por a en su columna sea igual al valor en esa fila. ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle p-1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle b}$

Por el contrario, dada una solución básica factible, las columnas correspondientes a las variables distintas de cero se pueden expandir a una matriz no singular. Si el cuadro correspondiente se multiplica por la inversa de esta matriz, entonces el resultado es un cuadro 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}}}$

ser un cuadro en forma canónica. Se pueden aplicar transformaciones adicionales de suma de filas para eliminar los coeficientes cTB
​ de la función objetivo. Este proceso se llama fijación de precios y da como resultado un cuadro canónico.

${\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 básica factible 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 básica factible a una solución básica factible adyacente se implementa como una operación de 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 agregan múltiplos de la fila a las otras filas para cambiar las otras entradas de la columna a 0. El resultado es que, si el elemento pivote es en una fila r , entonces la columna se convierte en la r -ésima columna de la matriz identidad. La variable para esta columna ahora es una variable básica, reemplazando la variable que correspondía a la r -ésima columna de la matriz de identidad antes de la operación. En efecto, la variable correspondiente a la columna dinámica ingresa al conjunto de variables básicas y se denomina variable entrante , y la variable que se reemplaza sale del conjunto de variables básicas y se denomina variable saliente . El cuadro todavía está en forma canónica pero con el conjunto de variables básicas cambiado en un elemento. ^{[13] [14]}

Algoritmo

Sea un programa lineal dado por un cuadro canónico. El algoritmo simplex procede realizando sucesivas operaciones de pivote, cada una de las cuales proporciona una solución básica factible 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 la selección de variables

Dado que la variable entrante, 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 dinámica de modo que la entrada correspondiente en la fila objetivo del cuadro sea positiva.

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

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 óptimo 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, el algoritmo cambia para que encuentre el mínimo de la función objetivo en lugar del máximo.

Salir de la selección de variables

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

A continuación, se debe seleccionar la fila dinámica para que todas las demás variables básicas sigan siendo 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 la fila pivote r se elige de modo que

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

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

Ejemplo

Considere 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 holgadas s y t , esto se representa en el cuadro canónico

${\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 básica factible correspondiente es

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

Las columnas 2, 3 y 4 se pueden seleccionar como columnas dinámicas; 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. Realizar el pivote produce

${\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 básica factible 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}}}$$

entonces el valor mínimo de Z es −20.

Encontrar un cuadro canónico inicial

En general, un programa lineal no se dará en forma canónica y se debe encontrar un cuadro canónico 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 de columna para estas variables. Si el valor b de una ecuación de restricción es negativo, la ecuación se niega antes de sumar las columnas de la matriz identidad. Esto no cambia el conjunto de soluciones factibles ni la solución óptima, y ​​garantiza que las variables de holgura constituirán una solución factible inicial. El nuevo cuadro tiene forma canónica pero no es equivalente al problema original. Entonces 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 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 el cuadro canónico resultante produce un cuadro canónico equivalente al problema original. Luego se puede aplicar el algoritmo simplex 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 todas las variables artificiales son cero. Esto implica que la región factible del problema original está vacía y, por tanto, el problema original no tiene solución. ^{[13] [14] [24]}

Ejemplo

Considere 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 el cuadro (no canónico)

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

Introducir variables artificiales u y v y la función objetivo W  =  u  +  v , dando un nuevo cuadro

${\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 anticipación de la Fase II.

Por construcción, u y v son variables básicas ya que forman parte de la matriz identidad inicial. Sin embargo, la función objetivo W actualmente supone que u y v son ambos 0. Para ajustar la función objetivo para que tenga el valor correcto donde u  = 10 y v  = 15, agregue las filas tercera y cuarta 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 dinámica, por lo que la fila dinámica debe ser la fila 4 y el cuadro actualizado es

${\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 dinámica, para la cual la fila 3 debe ser la fila dinámica, 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 se pueden eliminar dando un cuadro canónico equivalente al problema original:

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

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

Temas avanzados

Implementación

La forma de cuadro utilizada anteriormente para describir el algoritmo se presta a una implementación inmediata en la que el cuadro se mantiene como una matriz rectangular ( m  + 1) por ( m  +  n  + 1). Es sencillo evitar almacenar las m columnas explícitas de la matriz identidad que aparecerán dentro del cuadro en virtud de que B es un subconjunto de las columnas de [ A ,  I ]. Esta implementación se conoce como " 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 del cuadro, la columna (pivotal) del cuadro correspondiente a la variable entrante y el lado derecho. Este último se puede actualizar usando la columna fundamental y la primera fila del cuadro se puede actualizar usando la fila (pivotal) correspondiente a la variable saliente. Tanto la columna fundamental como la fila fundamental se pueden calcular directamente utilizando las soluciones de sistemas lineales de ecuaciones que involucran la matriz B y un producto matriz-vector usando A. Estas observaciones motivan el " algoritmo simplex revisado ", cuyas implementaciones se distinguen por su representación invertible  de B. ^[25]

En grandes problemas de programación lineal, A suele ser una matriz dispersa y, cuando se aprovecha la escasez resultante de B manteniendo su representación invertible, el algoritmo simplex revisado es mucho más eficiente que el método simplex estándar. Los solucionadores simplex comerciales se basan en el algoritmo simplex 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 dar como resultado 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 simplex debe terminar después de un número finito de pasos. Las soluciones básicas factibles donde al menos una de las variables básicas es cero se denominan degeneradas y pueden dar lugar a pivotes para los cuales no hay mejora en el valor objetivo. En este caso no hay ningún cambio real en la solución sino sólo un cambio en el conjunto de variables básicas. Cuando se producen varios de estos pivotes sucesivamente, no hay mejora; en grandes aplicaciones industriales, la degeneración es común y ese " estancamiento " es notable. Peor que estancarse 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 simplex 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 ciclismo es poco común en la práctica. En Padberg se discute un ejemplo de ciclismo práctico . ^[24] La regla de Bland evita el ciclo y, por lo tanto, garantiza que el algoritmo simplex siempre termina. ^{[24] [29] [30]} Otro algoritmo pivotante, el algoritmo entrecruzado, 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 de la pérdida y el ciclo al realizar un seguimiento de la frecuencia con la que se utilizan variables particulares y luego favorecer 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 supuso 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 , mostrando que la complejidad del peor de los casos del método simplex formulado por 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 en los que funciona mal. Es una cuestión abierta si existe una variación con el tiempo polinómico , aunque se conocen reglas de pivote subexponenciales. ^[33]

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

Eficiencia en la práctica

Analizar y cuantificar 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 rendimiento preciso del caso promedio 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 de la topología general y para mostrar que (topológicamente) "la mayoría" de las matrices se pueden resolver mediante el algoritmo simplex en un número polinómico de pasos. ^{[ cita necesaria ]}

Otro método para analizar el rendimiento del algoritmo simplex estudia el comportamiento de los peores escenarios bajo una pequeña perturbación: ¿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 entrada con ruido es polinomio en el número de variables y la magnitud de las perturbaciones. ^{[39] [40]}

Otros algoritmos

En el artículo sobre programación lineal se describen otros algoritmos para resolver problemas de programación lineal . Otro algoritmo pivotante de intercambio de bases es el algoritmo entrecruzado . ^{[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 ruta . ^[15]

Programación lineal-fraccional

La programación lineal-fraccional (LFP) es una generalización de la programación lineal (LP). En LP, la función objetivo es una función lineal , mientras que la función objetivo de un programa lineal-fraccional es una relación de dos funciones lineales. En otras palabras, un programa lineal es un programa lineal fraccionario 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 entrecruzado . ^[47]

Ver también

• Algoritmo entrecruzado
• Método del plano de corte
• algoritmo devex
• Eliminación de Fourier-Motzkin
• Descenso de gradiente
• algoritmo de karmarkar
• Heurística simplista de Nelder-Mead
• Regla pivotante de Bland , que evita el ciclismo

Notas

1. Murty, Katta G. Programación lineal. John Wiley & Sons Inc.1, 2000.
2. Murty (1983, comentario 2.2)
3. Murty (1983, nota 3.9)
4. Piedra, Richard E.; Tovey, Craig A. (1991). "Los algoritmos de escala proyectivo y simplex como métodos de mínimos cuadrados reponderados iterativamente". Revisión SIAM . 33 (2): 220–237. doi :10.1137/1033049. JSTOR  2031142. SEÑOR  1124362.
5. Piedra, Richard E.; Tovey, Craig A. (1991). "Errata: los algoritmos de escala proyectivo y simplex como métodos de mínimos cuadrados reponderados iterativamente". Revisión SIAM . 33 (3): 461. doi : 10.1137/1033100. JSTOR  2031443. SEÑOR  1124362.
6. 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.
7. Dantzig, George B. (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.
8. Albers y Reid (1986). "Una entrevista con George B. Dantzig: el padre de la programación lineal". Revista universitaria de matemáticas . 17 (4): 292–314. doi :10.1080/07468342.1986.11972971.
9. Dantzig, George (mayo de 1987). Nash, Stephen G. (ed.). Orígenes del método simplex (PDF) . Asociación para Maquinaria de Computación. págs. 141-151. doi : 10.1145/87252.88081. ISBN 978-0-201-50814-7. Archivado (PDF) desde el original el 29 de mayo de 2015. {{cite encyclopedia}}: |work=ignorado ( ayuda )
10. Murty (1983, teorema 3.3)
11. Murty (1983, p.143, sección 3.13)
12. Murty (1983, p. 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. (elemental)
15. Robert J. Vanderbei, Programación lineal: fundamentos y extensiones, 3.ª ed., Serie internacional sobre 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 pivote 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 ed.). 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 simples". En JE Beasley (ed.). Avances en programación lineal y entera . Ciencia de Oxford. págs. 1–46. SEÑOR  1438309.
28. Maros, István (2003). Técnicas computacionales del método simplex . Serie internacional en investigación de operaciones y ciencias de la gestión. vol. 61. Boston, MA: Editores académicos de Kluwer. págs.xx+325. ISBN 978-1-4020-7332-8. SEÑOR  1960274.
29. Bland, Robert G. (mayo de 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. SEÑOR  0459599. S2CID  18493293.
30. Murty (1983, pág.79)
31. Hay problemas de optimización abstractos, llamados programas matroides orientados , en los que la regla de Bland realiza un ciclo (incorrectamente) mientras que el algoritmo entrecruzado termina correctamente.
32. Klee, Víctor ; Minty, George J. (1972). "¿Qué tan bueno es el algoritmo simplex?". En Shisha, Oved (ed.). Desigualdades III (Actas del Tercer Simposio sobre Desigualdades 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. SEÑOR  0332165.
33. Hansen, Thomas; Zwick, Uri (2015), "Una versión mejorada de la regla de pivote de facetas aleatorias para el algoritmo simplex", Actas del cuadragésimo séptimo simposio anual de 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, S2CID  1980659{{citation}}: CS1 maint: date and year (link)
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, Ilán; Christos, Papadimitriou ; Rubinstein, Aviad (2014), "Sobre las reglas pivotantes simples y la teoría de la complejidad", Programación entera y optimización combinatoria , Apuntes de conferencias sobre informática, vol. 17, págs. 13-24, arXiv : 1404.3320 , doi : 10.1007/978-3-319-07557-0_2, ISBN 978-3-319-07556-3, S2CID  891022
36. Con miedo, John; Savani, Rahul (2015), "La complejidad del método simplex", Actas del cuadragésimo séptimo simposio anual ACM sobre teoría de la computación , págs. 201-208, arXiv : 1404.0605 , doi : 10.1145/2746539.2746558, ISBN 9781450335362, S2CID  2116116{{citation}}: CS1 maint: date and year (link)
37. Alexander Schrijver , Teoría de la programación lineal y entera . John Wiley e hijos, 1998, ISBN 0-471-98232-6 (matemático) 
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. págs. xii+268. ISBN 978-3-540-17096-9. SEÑOR  0868467.
39. Spielman, Daniel; Teng, Shang-Hua (2001). "Análisis suavizado de algoritmos: por qué el algoritmo simplex suele tomar tiempo polinómico". Actas del trigésimo tercer simposio anual 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. S2CID  1471.
40. Dadush, Daniel; Huiberts, Sophie (1 de enero de 2020). "Un análisis amigable y suavizado del método simplex". Revista SIAM de Computación . 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 la programación lineal: un estudio 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. SEÑOR  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 de pivote". Programación Matemática, Serie B. Ámsterdam: Editorial de Holanda Septentrional. 79 (1–3): 369–395. doi :10.1007/BF02614325. SEÑOR  1464775. S2CID  2794181.
43. Murty (1983, capítulo 3.20 (págs. 160-164) y págs. 168 y 179)
44. Capítulo cinco: Craven, BD (1988). Programación fraccionada . Serie Sigma en Matemática Aplicada. vol. 4. Berlín: Heldermann Verlag. pag. 145.ISBN​ 978-3-88538-404-5. SEÑOR  0949209.
45. Kruk, Serge; Wolkowicz, Henry (1999). "Programación pseudolineal". Revisión SIAM . 41 (4): 795–805. Código Bib : 1999SIAMR..41..795K. CiteSeerX 10.1.1.53.7355 . doi :10.1137/S0036144598335259. JSTOR  2653207. SEÑOR  1723002. 
46. Mathis, Frank H.; Mathis, Lenora Jane (1995). "Un algoritmo de programación no lineal para la gestión hospitalaria". Revisión SIAM . 37 (2): 230–234. doi :10.1137/1037046. JSTOR  2132826. SEÑOR  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. SEÑOR  0720547.

Otras lecturas

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 simplex, págs. 790–804. 
• Frederick S. Hillier y Gerald J. Lieberman: Introducción a la investigación de operaciones , octava edición. McGraw-Hill. ISBN 0-07-123828-X 
• Rardin, Ronald L. (1997). Optimización en la investigación de operaciones . Prentice Hall. pag. 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., Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method the University of Colorado at 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 Mathstools Simplex 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)
• simplex-m Solucionador simplex en línea