Algoritmo simplex - Simplex algorithm

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

El nombre del algoritmo se deriva del concepto de simplex y fue sugerido por TS Motzkin . En realidad, los simples no se utilizan en el método, pero una interpretación del mismo es que opera sobre conos simples , y estos se convierten en simples simples con una restricción adicional. 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 tomar 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 las metas en lugar de especificar una meta 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 objetiva lineal que debe maximizarse. El desarrollo del método simplex fue evolutivo y ocurrió durante un período de aproximadamente un año.

Después de que Dantzig incluyó una función objetiva como parte de su formulación a mediados de 1947, el problema fue matemáticamente más manejable. Dantzig se dio cuenta de que uno de los problemas no resueltos que había confundido con una tarea en la clase de su profesor Jerzy Neyman (y que de hecho lo 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 acotada entre cero y uno, y satisfacer 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 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.

Visió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 que alcanza el vértice de la solución óptima.

Poliedro de 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 da como resultado una 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 o vértice extremo de este politopo se conoce como solución factible básica (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. 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 inmanejable para todos los programas lineales excepto los más pequeños.

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. Si el borde es finito, entonces el borde se conecta a otro punto extremo donde la función objetivo tiene un valor mayor; de lo contrario, la función objetivo es ilimitada por encima del borde y el programa lineal no tiene solución. El algoritmo simplex aplica esta información al caminar 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 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.

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 ser 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 encuentra una solución factible básica o que la región factible está vacía. En el último caso, el programa lineal se denomina inviable . En el segundo paso, la 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 factible básica óptima o un borde infinito en el que la función objetivo es ilimitada arriba.

Forma estándar

La transformación de un programa lineal en uno en forma estándar se puede lograr de la siguiente manera. 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. Luego, la variable original se puede eliminar mediante sustitución. Por ejemplo, dada la restricción

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

una nueva variable`` se introduce con ${\ Displaystyle y_ {1}}$

${\ Displaystyle {\ begin {alineado} y_ {1} = x_ {1} -5 \\ x_ {1} = y_ {1} +5 \ end {alineado}}}$

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 {alineado} x_ {2} + 2x_ {3} y \ leq 3 \\ - x_ {4} + 3x_ {5} y \ geq 2 \ end {alineado}}}$

son reemplazados con

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

Es mucho más fácil realizar manipulación algebraica en desigualdades en 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. El otro es reemplazar la variable con la diferencia de dos variables restringidas. Por ejemplo, si no está restringido, escriba ${\ Displaystyle z_ {1}}$

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

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

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

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

También es útil suponer que el rango de es el número de filas. Esto no da como resultado una pérdida de generalidad, ya que de lo contrario el sistema tiene ecuaciones redundantes que pueden descartarse o el sistema es inconsistente y el programa lineal no tiene solución. ${\ 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 usan diferentes convenciones en cuanto al diseño exacto). Si las columnas de A se pueden reorganizar para que contengan la matriz de identidad de orden p (el número de filas en A), se dice que el cuadro está en forma canónica . Las variables correspondientes a las columnas de la matriz de 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 by esta solución es una solución básica factible. La interpretación algebraica aquí es que los coeficientes de la ecuación lineal representados por cada fila son o bien , 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, el resultado es un cuadro en forma canónica.

Dejar

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

Sea un cuadro en forma canónica. Se pueden aplicar transformaciones adicionales de suma de filas para eliminar los coeficientes cT
B de la función objetivo. Este proceso se denomina precio de salida 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 correspondiente solución básica factible. 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.

Operaciones 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 en 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 es ahora una variable básica, reemplazando 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 de entrada , y la variable que se reemplaza sale del conjunto de variables básicas y se llama variable saliente . El cuadro todavía está en forma canónica pero con el conjunto de variables básicas cambiado por un elemento.

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 de pivote en cada paso está determinada en gran medida por el requisito de que este pivote mejore la solución.

Entrar en la selección de variables

Dado que la variable que ingresa, 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 del cuadro sea positiva.

Si hay más de una columna de modo que la entrada en la fila del 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 , como el algoritmo Devex .

Si todas las entradas en la fila del objetivo son menores o iguales a 0, entonces no se puede elegir la variable de entrada y, de hecho, la solución es ó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 {términos no negativos correspondientes a variables no básicas}}}$

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

Dejando la selección de variables

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. Primero, solo se consideran las entradas positivas en la columna dinámica, ya que esto garantiza que el valor de la variable que ingresa no será negativo. Si no hay entradas positivas en la columna dinámica, la variable que ingresa puede tomar cualquier valor no negativo y la solución sigue siendo factible. En este caso, la función objetivo es ilimitada por debajo y no hay un mínimo.

A continuación, se debe seleccionar la fila pivote 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 de entrada 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 de modo que a _rc > 0. Esto se denomina prueba de relación mínima . Si hay más de una fila para la que se alcanza el mínimo, se puede usar una regla de elección de variable de eliminación para tomar la determinación.

Ejemplo

Considere el programa lineal

Minimizar

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

Sujeto a

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

Con la adición de las variables de holgura s y t , esto está representado por 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 pivote, para 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 de 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 del objetivo y, de hecho,

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

por lo que 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 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 de identidad se agregan como vectores de columna para estas variables. Si el valor de b para una ecuación de restricción es negativo, la ecuación se niega antes de agregar las columnas de la matriz de identidad. Esto no cambia el conjunto de soluciones factibles o la solución óptima, y ​​asegura que las variables de holgura constituirán una solución factible inicial. El nuevo cuadro está en 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 denomina problema de fase I.

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 las variables no negativas, su valor está acotado por debajo de 0. Si el mínimo es 0 entonces las variables artificiales se pueden eliminar de el cuadro canónico resultante produce un cuadro canónico equivalente al problema original. A continuación, 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 una 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, por lo que el problema original no tiene solución.

Ejemplo

Considere el programa lineal

Minimizar

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

Sujeto a

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

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

Introduzca las 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 previsión de la Fase II.

Por construcción, u y v son ambas variables básicas, ya que son parte de la matriz de identidad inicial. Sin embargo, la función objetivo W actualmente asume que U y V son ambos 0. Con el fin de ajustar la función objetivo que es el valor correcto cuando u  = 10 y v  = 15, añadir la tercera y cuarta filas a la primera fila de entrega

${\ 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 pivote, para la 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 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}}}$

Esto, fortuitamente, 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 de identidad que se producirán dentro del cuadro 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 caro 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 (fundamental) del cuadro correspondiente a la variable de entrada y el lado derecho. Este último puede actualizarse usando la columna pivotal y la primera fila del cuadro se puede actualizar usando la fila (pivotal) correspondiente a la variable saliente. Tanto la columna central y la fila central se pueden calcular utilizando directamente las soluciones de sistemas lineales de ecuaciones con la matriz B y un producto matriz-vector usando A . Estas observaciones motivan la " revisado algoritmo simplex ", para los que las implementaciones se distinguen por su representación invertible de  B .

En grandes problemas de programación lineal, A es típicamente una matriz dispersa y, cuando la escasez resultante de B se explota al mantener su representación invertible, el algoritmo simplex revisado es mucho más eficiente que el método simplex estándar. Los solucionadores de símplex comerciales se basan en el algoritmo de símplex revisado.

Degeneración: estancamiento y ciclismo

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 simplex debe terminar después de un número finito de pasos. Las soluciones factibles básicas en las que al menos una de las variables básicas es cero se denominan degeneradas y pueden dar lugar a pivotes para los que no hay mejora en el valor objetivo. En este caso, no hay ningún cambio real en la solución, sino solo un cambio en el conjunto de variables básicas. Cuando ocurren varios de estos pivotes en sucesión, no hay mejora; en grandes aplicaciones industriales, la degeneración es común y tal " 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 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 raro en la práctica. En Padberg se analiza un ejemplo de ciclismo práctico . La regla de Bland evita el ciclo y, por lo tanto, garantiza que el algoritmo simplex siempre termine. Otro algoritmo pivotante, el algoritmo entrecruzado nunca circula en programas lineales.

Normas basadas en el historial de pivote, como la regla de Zadeh y la regla de Cunningham también tratar de eludir el problema de estancamiento y en bicicleta llevando un registro de la frecuencia con variables particulares se están utilizando y luego a favor de tales variables que se han utilizado menos a menudo.

Eficiencia

El método simplex es notablemente eficaz en la práctica y supuso una gran mejora con respecto a los métodos anteriores, como la eliminación de Fourier-Motzkin . Sin embargo, en 1972, Klee y Minty dieron un ejemplo, el cubo de Klee-Minty , que muestra 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 para los que funciona mal. Es una pregunta abierta si existe una variación con el tiempo polinomial , aunque se conocen reglas de pivote sub-exponenciales.

En 2014 se comprobó que una variante particular del método simplex es NP-mighty , es decir, se puede utilizar para resolver, con sobrecarga polinomial, cualquier problema en NP implícitamente durante la ejecución del algoritmo. Además, decidir si una variable determinada entra en la base durante la ejecución del algoritmo en una entrada determinada, y determinar el número de iteraciones necesarias para resolver un problema dado, son problemas NP difíciles . Aproximadamente al mismo tiempo, se demostró que existe una regla de pivote artificial para la cual el cálculo de su salida es PSPACE completo . En 2015, esto se reforzó para mostrar que el cálculo de la salida de la regla de pivote de Dantzig es PSPACE completo .

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 casos promedio en tiempo polinómico bajo varias distribuciones de probabilidad , con el rendimiento de caso promedio preciso del algoritmo simplex dependiendo de la elección de una distribución de probabilidad para las matrices aleatorias . Otro enfoque para estudiar " 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 pueden resolverse mediante el algoritmo simplex en un número polinomial de pasos. 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 ante 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.

Otros algoritmos

Otros algoritmos para resolver problemas de programación lineal se describen en el artículo de programación lineal . Otro algoritmo pivotante de intercambio de bases es el algoritmo entrecruzado . Hay algoritmos de tiempo polinómico para la programación lineal que utilizan métodos de punto interior: estos incluyen Khachiyan 's algoritmo elipsoidal , Karmarkar ' s algoritmo proyectiva , y algoritmos de seguimiento de camino .

Programación lineal-fraccionaria

La programación lineal-fraccionaria (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-fraccionario es una relación 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 puede resolverse mediante una variante del algoritmo simplex o mediante el algoritmo entrecruzado .

Ver también

Notas

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 investigación de operaciones . Prentice Hall. pag. 919. ISBN 978-0-02-398415-0.

enlaces externos

• Introducción a la programación lineal y el algoritmo simplex por Spyros Reveliotis del Instituto de Tecnología de Georgia.
• Greenberg, Harvey J., Klee-Minty Polytope muestra la complejidad temporal exponencial del método simplex la Universidad de Colorado en Denver (1997) Descargar PDF
• Método Simplex Un tutorial para el Método Simplex con ejemplos (también método bifásico y 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