Hispanopedia Wiki
Articulo de referencia

Algoritmo simplex

El gráfico ilustra cómo el algoritmo Simplex resuelve un problema de programación lineal con dos variables. En optimización matemática , el algoritmo simplex de Dantzig (o métod...

Hispanopedia WikiContenido en espanolLectura gratuita
El gráfico ilustra cómo el algoritmo Simplex resuelve un problema de programación lineal con dos variables.
El gráfico ilustra cómo el algoritmo Simplex resuelve un problema de programación lineal con dos variables.

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

El nombre del algoritmo deriva del concepto de simplex y fue sugerido por TS Motzkin . [ 2 ] En realidad, los símplices no se utilizan en el método, pero una interpretación es que opera sobre conos simpliciales , y estos se convierten en símplices propiamente dichos con una restricción adicional. [ 3 ] [ 4 ] [ 5 ] [ 6 ] Los conos simpliciales en cuestión son las esquinas (es decir, los vecindarios 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 . En 1946, un colega lo retó 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 en su formulación. Sin un objetivo, un gran número de soluciones pueden ser factibles, por lo que 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í mismo. 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 simplex 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 en 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 confundido con una tarea en la clase de su profesor Jerzy Neyman (y que de hecho resolvió más tarde), era aplicable a la búsqueda de un algoritmo para programas lineales. Este problema consistía en 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 satisficiera restricciones lineales expresadas en forma de integrales de Lebesgue . Posteriormente, Dantzig publicó su "tarea" como tesis para obtener su doctorado. La geometría de columnas utilizada en esta tesis le proporcionó a Dantzig una perspectiva 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 recorre las aristas del politopo hasta alcanzar el vértice de la solución óptima.
Poliedro del algoritmo simplex en 3D

El algoritmo simplex opera sobre programas lineales en su forma canónica.

maximizardoTincógnita{\textstyle \mathbf {c^{T}} \mathbf {x} }
sujeto aAincógnita≤b{\displaystyle A\mathbf {x} \leq \mathbf {b} }yincógnita≥0{\displaystyle \mathbf {x} \geq 0}

condo=(do1,…,donorte){\displaystyle \mathbf {c} =(c_{1},\,\dots ,\,c_{n})}los coeficientes de la función objetivo,(⋅)T{\displaystyle (\cdot )^{\mathrm {T} }}es la transpuesta de la matriz con un marcador de posición de punto , yincógnita=(incógnita1,…,incógnitanorte){\displaystyle \mathbf {x} =(x_{1},\,\dots ,\,x_{n})}son las variables del problema,A{\displaystyle A}es una matriz p × n , yb=(b1,…,bpag){\displaystyle \mathbf {b} =(b_{1},\,\dots ,\,b_{p})}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 conlleva ninguna pérdida de generalidad.

En términos geométricos, la región factible definida por todos los valores deincógnita{\displaystyle \mathbf {x} }de tal manera queAincógnita≤b{\textstyle A\mathbf {x} \leq \mathbf {b} }y∀i,incógnitai≥0{\displaystyle \forall i,x_{i}\geq 0}es un politopo convexo (posiblemente no acotado) . Un punto extremo o vértice de este politopo se conoce como solución factible básica (SFB).

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, por sí solo, reduce el problema a un cálculo finito, ya que existe un número finito de puntos extremos; sin embargo, 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 existe una arista que contiene el punto de tal manera 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 conecta con otro punto extremo donde la función objetivo tiene un valor mayor; de lo contrario, la función objetivo no está acotada superiormente en la arista y el programa lineal no tiene solución. El algoritmo simplex aplica esta idea recorriendo las aristas del politopo hasta puntos extremos con valores de la función objetivo 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, como 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 realiza 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 simplex a una versión modificada del programa original. Los posibles resultados de la Fase I son encontrar una solución básica factible o que la región factible esté vacía. En este último caso, el programa lineal se denomina infactible . 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 una arista infinita en la que la función objetivo no está acotada superiormente. [ 13 ] [ 14 ] [ 15 ]

Formato estándar

La transformación de un programa lineal a uno en forma estándar puede realizarse 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 eliminarse mediante sustitución. Por ejemplo, dada la restricción

incógnita1≥5{\displaystyle x_{1}\geq 5}

una nueva variable,y1{\displaystyle y_{1}}, se introduce con

y1=incógnita1−5incógnita1=y1+5{\displaystyle {\begin{aligned}y_{1}=x_{1}-5\\x_{1}=y_{1}+5\end{aligned}}}

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

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 es no negativa. Por ejemplo, las desigualdades

incógnita2+2incógnita3≤3−incógnita4+3incógnita5≥2{\displaystyle {\begin{aligned}x_{2}+2x_{3}&\leq 3\\-x_{4}+3x_{5}&\geq 2\end{aligned}}}

son reemplazados por

incógnita2+2incógnita3+s1=3−incógnita4+3incógnita5−s2=2s1,s2≥0{\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 en desigualdades de esta forma. En desigualdades donde aparece ≥ como la segunda, algunos autores se refieren a la variable introducida como unavariable excedente .

En tercer lugar, cada variable no restringida se elimina 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 eliminándola por sustitución. La otra es reemplazar la variable con la diferencia de dos variables restringidas. Por ejemplo, siz1{\displaystyle z_{1}}Si no está restringido, entonces escribe

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

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

Cuando este proceso esté completo, la región factible estará en la forma

Aincógnita=b,∀ incógnitai≥0{\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} ,\,\forall \ x_{i}\geq 0}

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

Tabla simple

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

[1−doT00Ab]{\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.b{\displaystyle \mathbf {b} }(diferentes autores utilizan diferentes convenciones en cuanto al diseño exacto). Si las columnas deA{\displaystyle \mathbf {A} }puede reorganizarse de manera que contenga la matriz identidad de ordenpag{\displaystyle p}(el número de filas enA{\displaystyle \mathbf {A} }) entonces se dice que el tableau está en forma canónica . [ 18 ] Las variables correspondientes a las columnas de la matriz identidad se llaman variables básicas, mientras que las variables restantes se llaman 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 enb{\displaystyle \mathbf {b} }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 bien0{\displaystyle 0},1{\displaystyle 1}, o algún otro número. Cada fila tendrá1{\displaystyle 1}columna con valor1{\displaystyle 1},pag−1{\displaystyle p-1}columnas con coeficientes0{\displaystyle 0}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 a cero, nos aseguramos en cada fila de que el valor de la variable representada por una1{\displaystyle 1}en su columna es igual a lab{\displaystyle b}valor en esa fila.

Por el contrario, dada una solución factible básica, las columnas correspondientes a las variables no nulas pueden expandirse a una matriz no singular.B{\displaystyle B}. Si el cuadro correspondiente se multiplica por el inverso deB{\displaystyle B}, entonces el resultado es un cuadro en forma canónica. [ 19 ]

Dejar

[1−doBT−doDT00IDb^]{\displaystyle {\begin{bmatrix}1&-\mathbf {c} _{B}^{T}&-\mathbf {c} _{D}^{T}&0\\0&I&\mathbf {D} &{\widehat {\mathbf {b} }}\end{bmatrix}}}

ser un cuadro en forma canónica, dondeb^=B−1b{\displaystyle {\widehat {\mathbf {b} }}=B^{-1}\mathbf {b} }Se pueden aplicar transformaciones adicionales de adición de filas para eliminar los coeficientes c T B  de la función objetivo. Este proceso se llama precio de salida y da como resultado una tabla canónica.

[10−do¯DTzB0IDb^]{\displaystyle {\begin{bmatrix}1&0&-{\bar {\mathbf {c} }}_{D}^{T}&z_{B}\\0&I&\mathbf {D} &{\widehat {\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 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 suman múltiplos de la fila a las demás filas para cambiar las demás entradas de 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 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 denomina variable entrante , y la variable que se reemplaza sale del conjunto de variables básicas y se denomina variable saliente . El tableau sigue en forma canónica, pero con el conjunto de variables básicas cambiado en un elemento. [ 13 ] [ 14 ]

Algoritmo

Consideremos un programa lineal representado por una tabla canónica. 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 principalmente por el requisito de que este pivote mejore la solución.

Las siguientes secciones se centran en hallar el máximo de la función objetivo. Si, en cambio, se desea hallar el mínimo, el algoritmo puede modificarse negando todas las referencias a la función objetivo.

Introduciendo la 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 aumentará (y se acercará al máximo) si la derivada (es decir, los coeficientesdo¯T{\displaystyle {\bar {\mathbf {c} }}^{\mathrm {T} }}) de la función objetivo con respecto a esta variable es positivo. Por lo tanto, se debe seleccionar una columna pivote cuya entrada correspondiente en la fila objetivo (−do¯T{\displaystyle -{\bar {\mathbf {c} }}^{\mathrm {T} }}) del tableau es negativo. (Si se desea minimizar la función objetivo, se seleccionaría una columna donde la entrada en la fila objetivo sea positiva).

Normalmente hay más de una columna con una entrada negativa en la fila del objetivo, y la elección de cuál agregar al conjunto de variables básicas se guía por una de varias reglas de elección de variables de entrada [ 20 ] como el algoritmo Devex [ 21 ] .

Si ninguna de las entradas en la fila objetivo es negativa, entonces no se puede elegir ninguna variable de entrada y la solución es, de hecho, el máximo. Es fácil ver que es máximo ya que la fila objetivo ahora corresponde a una ecuación de la forma

z(incógnita)=zB+términos no positivos correspondientes a variables no básicas{\displaystyle z(\mathbf {x} )=z_{B}+{\text{términos no positivos correspondientes a variables no básicas}}}

Selección de variables de salida

Una vez seleccionada la columna pivote, la elección de la fila pivote viene determinada principalmente por el requisito de que la solución resultante sea factible. En primer lugar, solo se consideran los valores positivos en la columna pivote, ya que solo estos imponen límites al valor de la variable de entrada. Si no hay valores positivos en la columna pivote, la variable de entrada puede tomar cualquier valor no negativo sin que la solución deje de ser factible. En este caso, la función objetivo no tiene límite superior y no existe un máximo.

A continuación, debe seleccionarse la fila pivote de modo que la variable de entrada (y por lo tanto la mejora en el objetivo) tenga el valor máximo sujeto a que todas las demás variables básicas permanezcan no negativas. Si la columna pivote es c , entonces esto se logra si la fila pivote r se elige de modo que

b^r/a^rdo{\displaystyle {\hat {b}}_{r}/{\hat {a}}_{rc}\,}

es el mínimo sobre todos los r tales quea^rdo{\displaystyle {\hat {a}}_{rc}}> 0. Esto se denomina 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 de eliminación [ 22 ] para hacer la determinación.

Ejemplo

Consideremos el programa lineal.

Maximizar
Z=2incógnita+3y+4z{\displaystyle Z=2x+3y+4z}
Sujeto a
3incógnita+2y+z≤102incógnita+5y+3z≤15incógnita,y,z≥0{\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 el cuadro canónico.

[1−2−3−40000321101002530115]{\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

incógnita=y=z=0,s=10,t=15.{\displaystyle x=y=z=0,\,s=10,\,t=15.}

Las columnas 2, 3 y 4 se pueden seleccionar como columnas pivote. Para este ejemplo, supongamos que 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

[1231130043200731301−1350235310135]{\displaystyle {\begin{bmatrix}1&{\frac {2}{3}}&{\frac {11}{3}}&0&0&{\frac {4}{3}}&20\\0&{\frac {7}{3}}&{\frac {1}{3}}&0&1&-{\frac {1}{3}}&5\\0&{\frac {2}{3}}&{\frac {5}{3}}&1&0&{\frac {1}{3}}&5\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

incógnita=y=t=0,z=5,s=5.{\displaystyle x=y=t=0,\,z=5,\,s=5.}

Para el siguiente paso, no hay entradas negativas en la fila del objetivo y, de hecho,

Z=20−23incógnita−113y−43t{\displaystyle Z=20-{\frac {2}{3}}x-{\frac {11}{3}}y-{\frac {4}{3}}t}

Por lo tanto, el valor máximo de Z es 20.

Encontrar un cuadro canónico inicial

En general, un programa lineal no se presenta en forma canónica, por lo que es necesario encontrar un tableau canónico equivalente antes de que pueda comenzar el algoritmo simplex. Esto se logra mediante la introducción de variables artificiales . Se añaden columnas de la matriz identidad como vectores columna para estas variables. Si el valor b de una ecuación de restricción es negativo, la ecuación se niega antes de añadir las columnas de la matriz identidad. Esto no modifica el conjunto de soluciones factibles ni la solución óptima, y ​​garantiza que las variables de holgura constituyan una solución factible inicial. El nuevo tableau 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 denomina problema de Fase  I. [ 23 ]

El algoritmo simplex aplicado al problema de la Fase I debe finalizar 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 inferiormente por 0. Si el mínimo es 0, las variables artificiales pueden eliminarse del tableau canónico resultante, produciendo un tableau canónico equivalente al problema original. A continuación, se puede aplicar el algoritmo simplex para encontrar la solución; este paso se denomina Fase  II . Si el mínimo es positivo, no existe una solución factible para el problema de la Fase I donde todas las variables artificiales son 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.

Maximizar
Z=2incógnita+3y+4z{\displaystyle Z=2x+3y+4z}
Sujeto a
3incógnita+2y+z=102incógnita+5y+3z=15incógnita,y,z≥0{\displaystyle {\begin{aligned}3x+2y+z&=10\\2x+5y+3z&=15\\x,\,y,\,z&\geq 0\end{aligned}}}

Se diferencia del ejemplo anterior por tener restricciones de igualdad en lugar de desigualdad. La solución anteriorincógnita=y=0,z=5{\displaystyle x=y=0\,,z=5}viola la primera restricción. Este nuevo problema está representado por el tableau (no canónico)

[1−2−3−40032110025315]{\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 función objetivo W  = u + v , dando como resultado un nuevo tableau.   

[10000−1−1001−2−3−4000003211010002530115]{\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 conserva en previsió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 asume que u y v son ambas  0. Para ajustar la función objetivo al valor correcto donde u  =  10 y v  =  15, agregue la tercera y cuarta fila a la primera fila dando

[10574002501−2−3−4000003211010002530115]{\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, por lo que la fila pivote debe ser la fila 4, y la tabla actualizada es

[307100−4150321100460007103−115002530115]{\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

[70000−7−70070250−210130007103−115000117−2325]{\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, lo que da como resultado un tableau canónico equivalente al problema original:

[702501300710150011725]{\displaystyle {\begin{bmatrix}7&0&25&0&130\\0&7&1&0&15\\0&0&11&7&25\end{bmatrix}}}

Por fortuna, este valor ya es óptimo, por lo que el valor óptimo para el programa lineal original es 130/7. Este valor es "peor" que 20, lo cual es de esperar en un problema con mayores restricciones.

Temas avanzados

Implementación

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

En cada iteración del simplex, los únicos datos requeridos son la primera fila del tableau, la columna (pivotal) del tableau correspondiente a la variable entrante y el lado derecho. Este último se puede actualizar utilizando la columna pivotal, y la primera fila del tableau 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 de ecuaciones lineales que involucran la matriz B y un producto matriz-vector utilizando A. Estas observaciones motivan el " algoritmo simplex revisado ", cuyas implementaciones se distinguen por su representación invertible de B. [ 25 ] 

En problemas de programación lineal de gran tamaño, A suele ser una matriz dispersa y, cuando se aprovecha la dispersión resultante de B al mantener su representación invertible, el algoritmo simplex revisado resulta 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 resultar en una mejora en el valor objetivo. Cuando esto siempre es así, ningún conjunto de variables básicas aparece dos veces y el algoritmo simplex 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 resultar en pivotes para los cuales no hay 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 sucesivamente, no hay 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 aparezca dos veces, en cuyo caso, las reglas de pivoteo 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 ciclo es raro en la práctica. Una discusión de un ejemplo de ciclo práctico se encuentra en Padberg . [ 24 ] La regla de Bland evita el ciclo y, por lo tanto, garantiza que el algoritmo simplex siempre termina. [ 24 ] [ 29 ] [ 30 ] Otro algoritmo de pivoteo, el algoritmo de cruce, nunca entra en ciclo en programas lineales. [ 31 ]

Las reglas de pivote basadas en el historial, como la regla de Zadeh y la regla de Cunningham, también intentan sortear el problema del estancamiento y el ciclo haciendo un seguimiento de la frecuencia con la que se utilizan determinadas variables y, a continuación, favoreciendo aquellas 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 respecto a métodos anteriores como la eliminación de Fourier-Motzkin . Sin embargo, en 1972, Klee y Minty [ 32 ] presentaron un ejemplo, el cubo de Klee-Minty , que demostró que la complejidad en el peor de los casos del método simplex, tal como lo formuló Dantzig, es exponencial . Desde entonces, para casi todas las variaciones del método, se ha demostrado que existe una familia de programas lineales para los que su rendimiento es deficiente. Sigue siendo una incógnita si existe una variación con tiempo polinomial , aunque se conocen reglas de pivote subexponenciales. [ 33 ]

En 2014, se demostró [ 34 ] 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 dada entra alguna vez en la base durante la ejecución del algoritmo sobre 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 de pivote artificial para la cual el cálculo de su salida es PSPACE-completo . [ 35 ] En 2015, esto se reforzó para demostrar que el cálculo de la salida 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 promedio de tiempo polinomial bajo varias distribuciones de probabilidad , y el rendimiento 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 " 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 ser resueltas por 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 pequeñas perturbaciones: ¿son estables los peores escenarios ante un pequeño cambio (en el sentido de estabilidad estructural ) o se vuelven manejables? Esta área de investigación, denominada análisis suavizado , se introdujo específicamente para estudiar el método simplex. De hecho, el tiempo de ejecución del método simplex con 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 pivoteo de intercambio de bases es el algoritmo criss-cross . [ 41 ] [ 42 ] Hay algoritmos de tiempo polinomial para programación lineal que utilizan métodos de punto interior: estos incluyen el algoritmo elipsoidal de Khachiyan , el algoritmo proyectivo de Karmarkar y algoritmos de seguimiento de caminos . [ 15 ] El método Big-M es una estrategia alternativa para resolver un programa lineal, utilizando un simplex de una sola fase. Cohen et al. [ 43 ] es el representante de una rama de algoritmos que aplican algoritmos rápidos de multiplicación de matrices a programas lineales.

Programación lineal fraccionaria

La programación lineal fraccionaria (PLF) es una generalización de la programación lineal (PL). En PL, la función objetivo es una función lineal , mientras que la función objetivo de un programa lineal fraccionario es una razón de dos funciones lineales. En otras palabras, un programa lineal es un programa lineal fraccionario en el que el denominador es una función constante con valor uno en todas partes. Un programa lineal fraccionario puede resolverse mediante una variante del algoritmo simplex [ 44 ] [ 45 ] [ 46 ] [ 47 ] o mediante el algoritmo de cruce [ 48 ] .

Véase también

Referencias

  1. ↑ Murty (1983 , págs. 52–53, Sección 2.1) 
  2. ↑ Murty (1983 , Comentario 2.2)
  3. ↑ Murty (1983 , Nota 3.9)
  4. ↑ Stone, Richard E.; Tovey, Craig A. (1991). "Los algoritmos de escalado simplex y proyectivo como métodos de mínimos cuadrados ponderados iterativamente". SIAM Review . 33 (2): 220– 237. doi : 10.1137/1033049 . JSTOR 2031142 . MR 1124362 .  
  5. ↑ Stone, Richard E.; Tovey, Craig A. (1991). "Erratum: Los algoritmos de escalado simplex y proyectivo como métodos de mínimos cuadrados ponderados 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 del 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" . College Mathematics Journal . 17 (4): 292– 314. doi : 10.1080/07468342.1986.11972971 .
  9. ↑ Dantzig, George (mayo de 1987). «Orígenes del método simplex» (PDF) . En Nash, Stephen G. (ed.). 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-7Archivado (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. 1 2 Murty (1983 , pág. 137, Sección 3.8) 
  13. 1 2 3 George B. Dantzig y Mukund N. Thapa. 1997. Programación lineal 1: Introducción . Springer-Verlag.
  14. 1 2 3 4 Evar D. Nering y Albert W. Tucker , 1993, Programas lineales y problemas relacionados , Academic Press. (elemental)
  15. 1 2 Robert J. Vanderbei, Programación lineal: Fundamentos y extensiones , 3.ª ed., Serie internacional en investigación operativa y ciencias 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. 1 2 Murty (1983 , pág. 66) 
  21. ↑ Harris, Paula MJ. "Métodos de selección de pivotes del código LP de Devex." 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. 1 2 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 sus soluciones.)
  27. ↑ Maros, István; Mitra, Gautam (1996). "Algoritmos simplex". En JE Beasley (ed.). Avances en programación lineal y entera . Oxford Science. pp. 1– 46. MR 1438309 .  
  28. ↑ Maros, István (2003). Técnicas computacionales del método simplex . Serie internacional en investigación operativa y ciencias de la gestión. Vol. 61. Boston, MA: Kluwer Academic Publishers. pp. xx+325. ISBN   978-1-4020-7332-8. MR 1960274 . 
  29. ↑ Bland, Robert G. ( mayo de 1977). "Nuevas reglas de pivoteo finito para el método simplex". Mathematics of Operations Research . 2 (2): 103– 107. doi : 10.1287/moor.2.2.103 . JSTOR 3689647. MR 0459599. S2CID 18493293 .   
  30. ↑Murty (1983, p. 79)
  31. ↑There are abstract optimization problems, called oriented matroid programs, on which Bland's rule cycles (incorrectly) while the criss-cross algorithm terminates correctly.
  32. ↑Klee, Victor; Minty, George J. (1972). "How good is the simplex algorithm?". In Shisha, Oved (ed.). Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin). New York-London: Academic Press. pp. 159–175. MR 0332165.
  33. ↑Hansen, Thomas; Zwick, Uri (2015), "An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm", Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pp. 209–218, CiteSeerX 10.1.1.697.2526, doi:10.1145/2746539.2746557, ISBN 9781450335362, S2CID 1980659
  34. 12Disser, Yann; Skutella, Martin (2018-11-01). "The Simplex Algorithm Is NP-Mighty". ACM Trans. Algorithms. 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), "On Simplex Pivoting Rules and Complexity Theory", Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 17, pp. 13–24, arXiv:1404.3320, doi:10.1007/978-3-319-07557-0_2, ISBN 978-3-319-07556-3, S2CID 891022
  36. ↑Fearnly, John; Savani, Rahul (2015), "The Complexity of the Simplex Method", Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pp. 201–208, arXiv:1404.0605, doi:10.1145/2746539.2746558, ISBN 9781450335362, S2CID 2116116
  37. ↑Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6 (mathematical)
  38. ↑ El algoritmo simplex requiere 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 simplex 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. S2CID 1471 . 
  40. ↑ Dadush, Daniel; Huiberts, Sophie (2020-01-01). "Un análisis suavizado amigable del método simplex" . SIAM Journal on Computing . 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 revisión de los desarrollos teóricos recientes". Annals of Operations Research . 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 cruzados: una nueva perspectiva sobre los algoritmos de pivote" . Mathematical Programming, Series B. 79 ( 1–3 ) . Ámsterdam: North-Holland Publishing: 369–395 . doi : 10.1007/BF02614325 . MR 1464775. S2CID 2794181 .  
  43. ↑ Cohen, Michael B.; Lee, Yin-Tat; Song, Zhao (2018). Solving Linear Programs in the Current Matrix Multiplication Time . 51st Annual ACM Symposium on the Theory of Computing. STOC'19. arXiv : 1810.07896 .
  44. ↑ Murty (1983 , Capítulo 3.20 (págs. 160–164) y págs. 168 y 179)
  45. ↑ Capítulo cinco: Craven, BD (1988). Programación fraccionaria . Serie Sigma en Matemáticas Aplicadas. Vol. 4. Berlín: Heldermann Verlag. pág. 145. ISBN   978-3-88538-404-5. SR 0949209 . 
  46. ↑ 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 .   
  47. ↑ 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 .   
  48. ↑ 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 .  

Obras citadas

Murty, Katta G. (1983). Programación lineal . Nueva York: John Wiley & Sons, Inc. ISBN 978-0471097259MR 0720547 .​ 

Lecturas adicionales

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

  • 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-7Sección 29.3: El algoritmo simplex, págs.  790 – 804.
  • Frederick S. Hillier y Gerald J. Lieberman: Introducción a la investigación operativa , 8.ª edición. McGraw-Hill. ISBN 0-07-123828-X
  • Rardin, Ronald L. (1997). Optimización en la investigación operativa . Prentice Hall. pág.  919. ISBN 978-0-02-398415-0.
  • Introducción a la programación lineal y al algoritmo simplex, por Spyros Reveliotis del Instituto Tecnológico de Georgia.
  • Greenberg, Harvey J., El politopo de Klee-Minty muestra la complejidad temporal exponencial del método simplex, Universidad de Colorado en Denver (1997) Descarga en PDF
  • Método Simplex Un tutorial sobre el método Simplex con ejemplos (también incluye el método de dos fases y el método M).
  • Calculadora Simplex de Mathstools de www.mathstools.com
  • Ejemplo del procedimiento Simplex para un problema estándar de programación lineal, por Thomas McFarland de la Universidad de Wisconsin-Whitewater.
  • PHPSimplex: herramienta online para resolver problemas de programación lineal, creada por Daniel Izquierdo y Juan José Ruiz de la Universidad de Málaga (UMA, España).
  • simplex-m Solucionador Simplex en línea
Lecturas relacionadas
6 articulos
Optimización matemáticaOptimización matemáticaLa optimización matemática (también llamada optimización ) o programación matemática es la selección del mejor elemento, con respecto a ciertos cri...Jorge DantzigJorge DantzigGeorge Bernard Dantzig ( / ˈdæntsɪɡ / ; 8 de noviembre de 1914 - 13 de mayo de 2005) fue un científico matemático estadounidense que hizo contribuc...AlgoritmoAlgoritmoEn matemáticas y ciencias de la computación , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigu...Programación linealProgramación linealLa programación lineal ( PL ), también llamada optimización lineal , es un método para lograr el mejor resultado (como el máximo beneficio o el men...Los cuatro símplex que pueden representarse completamente en el espacio 3D.SimplexEn geometría , un símplex (plural: símplexes o simplices ) es una generalización de la noción de triángulo o tetraedro a dimensiones arbitrarias . ...Teodoro MotzkinTheodore Samuel Motzkin (26 de marzo de 1908 - 15 de diciembre de 1970) fue un matemático israelí - estadounidense . [1] Biografía El padre de Motz...