Método simplex

Método simplex

El método del simplex fue introducido por George Danzig de 1946. Es un algoritmo resolución de problemas de optimización lineal.

Consiste en minimizar una función lineal de no variables reales,

método dantzig simplex programación lineal variable entrante variable saliente
método dantzig simplex programación lineal variable entrante variable saliente

donde, en un conjunto definido por medio de restricciones afines (o lineales) de igualdad y desigualdad. LOS'conjunto elegible Por tanto, el problema es un poliedro convexo.

Método

El método simplex es un método iterativo que atraviesa los vértices del poliedro convexo hasta que la función objetivo ya no se puede mejorar. El proceso de resolución es el siguiente:

  1. El problema está escrito debajo forma estándar.
  2. Se encuentra una solución.
  3. Encuentra la columna de pivote.
  4. Encuentre la línea del pivote y realice el método de Gauss
  • PARADA. Solución óptima encontrada o ninguna solución posible.

Resolución de ejemplo

Considere el siguiente problema para aplicar el método simplex:

MaximizarZ = 3x + 2y
bajo las limitaciones:2x + y ≤ 18
 2x + 3y ≤ 42
 3x + y ≤ 24
 x ≥ 0, y ≥ 0

Paso 1: escriba en forma estándar y solución básica

Transformamos las desigualdades en ecuaciones con la suma de variables.

Para ello, presentamos un variable de holgura (X3, X4, X5) en cada una de las restricciones de la forma ≤, para transformarlas en igualdades (ver lección sobre la forma estándar):

2 x1 + x2 + x3 = 18
2 x1 + 3 x2 + x4 = 42
3 veces1 + x2 + x5 = 24

Luego, ajustamos la función objetivo a cero: Z - 3 x1 - X2 - 0 x3 - 0 x4 - 0 x5 = 0. Es decir que las variables canónicas del programa están en cero, las variables de desviación son iguales al elemento de la derecha (b). A partir de ahora, es posible inicializar la tabla del método simplex.

La tabla inicial del método símplex está formada por todos los coeficientes de las variables de decisión del problema original y las variables de diferencia.

1ra iteración
 vs  32   
BasadoCbBX1X2X3X4X5
X391821100
X4214223010
X582431001
Z 0-3-2000

Aparte: degeneración del simplex

Se dice que una solución básica factible es degenerada si al menos una de las variables básicas es cero. Si durante el algoritmo símplex no se degenera ninguna base encontrada, entonces el algoritmo termina en un número finito de iteraciones. Si existe una base degenerada, entonces se puede encontrar un posible ciclo del algoritmo: se encuentra una base ya encontrada y se repite indefinidamente. Para tratar casos de degeneración, podemos aplicar la regla de Bland (1977) que asegura que el algoritmo se detiene en un número finito de iteraciones. Cuando es probable que varias variables entren o salgan de la base, siempre elegimos la que tiene el índice más pequeño.

Paso 2-3: elección de la variable de entrada y salida de la base de datos

Primero, establecemos la variable que entra en la base. Para ello, elegimos la columna cuyo valor en la fila Z es el más bajo de todos los negativos. En este caso, esa sería la variable x1 del coeficiente -3. La columna de la variable que entra en la base que llamamos columna de pivote (en verde).

Se elige esta variable porque su impacto en el valor de Z es el mayor (mayor gradiente). Introducir esta variable en la base consiste en encontrar una solución en el espacio de soluciones siguiendo el gradiente de esta variable. En el siguiente diagrama, la ordenada tiene el mayor gradiente en comparación con la solución Z = 0, por lo que seguiremos su eje (considere max z = xB) hasta que ya no pueda mejorar la solución.

método dantzig simplex programación lineal variable entrante variable saliente

Una vez obtenida la variable entrante en la base de datos, determinamos cuál será la variable saliente. Tomamos la decisión sobre la base de un cálculo simple: dividir cada término independiente (columna b) entre el elemento correspondiente del columna de pivote, siempre que ambos elementos sean estrictamente positivos (mayores que cero).

Esto equivale a considerar que nuestra variable saliente hará un pivote gaussiano con la variable entrante. En otras palabras, la variable entrante tomará un valor distinto de cero mientras que la variable saliente se convertirá en cero.

Optamos por la línea cuyo resultado es mínimo. De hecho, este cálculo permite saber hasta qué valor se puede aumentar la variable entrante. la programa lineal teniendo restricciones, no es posible exceder la restricción más “restrictiva”, es decir, limitando al máximo el valor de la variable entrante.

En este ejemplo: Cb: = 18/2, 42/2 y 24/3.
Si hubiera un elemento menor o igual a cero, este cociente no se realiza. Cuando todos los elementos del columna de pivote fuera de esta condición habríamos cumplido la condición de parada y el problema tendría solución sin parte acotada.

El término de la columna de pivote que resultó en el cociente positivo más pequeño distinto de cero en la división anterior indica la fila de la variable de brecha que sale de la base. En este caso, resulta x5, de coeficiente 3. Esta línea se llama línea pivote (en rojo).

La intersección de la línea de pivote y la columna de pivote Destacar el elemento pivote, en este caso el 3.

Paso 3: actualiza la tabla

Se calculan los nuevos coeficientes de la tabla de la siguiente manera (pivote gaussiano):

  • En la fila del elemento pivote, cada nuevo elemento se calcula como: Elemento de línea de pivote = Elemento de línea de pivote / pivote antiguo
  • En la columna de pivote: 0 excepto el pivote en 1.
  • En las líneas restantes se calcula cada elemento (producto cruzado): Nuevo elemento de fila = Elemento de fila antiguo - (Proyección de línea de pivote antigua * Proyección de columna de pivote antigua / Elemento de pivote antiguo).

Mostramos los cálculos para la línea x4 :

Línea antigua x44223010
  
proyección2*24 2*12*02*02*1
 / ////
pivote3 3333
 =se convierte en====
Nueva línea x42607/301-2/3

La tabla correspondiente a esta segunda iteración es (tenga en cuenta que x5 está fuera y que x1 ha vuelto a su lugar, además, la función objetivo ya no se expresa en x1 pero en x5, y su valor es 24):

Iniciar iteración 2-th
   32000
BasadoCbBX1X2X3X4X5
X3 201/310-2/3
X4 2607/301-2/3
X1 811/3001/3
Z 240-1001

STOP: condiciones de parada

Si el objetivo es la maximización, cuando en la última línea (línea indicadora) no hay un valor negativo entre los costos (no hay una variable con un gradiente que mejore la solución), obtenemos la condición de stop.

El valor de Z (columna B) es la solución óptima al problema.

Cuando no se cumple esta condición, los procesos se vuelven a ejecutar de forma iterativa.

Inicio de la cuarta iteración
   32000
BasadoCbBX1X2X3X4X5
X201201-1/21/20
X50300-7/41/41
X103103/4-1/40
Z 33005/41/40

Descubrimos que en la última línea todos los coeficientes son positivos. La solución óptima es: 33 con el vector solución (12, 3, 0, 0, 3). El vector solución está determinado por el valor de B en las filas de variables básicas. Tenga en cuenta que x5 = 3, es decir, la restricción 3 (que contiene la variable de diferencia x5) no está saturado con un margen 3.

Abstracto

método dantzig simplex programación lineal variable entrante variable saliente

Casos particulares

  • Soluciones infinitas: cuando el simplex se detiene y las variables no base tienen un valor de 0 en la fila Z, significa que hay una solución infinita. Para conocer los límites del hiperplano (o del segmento) de soluciones, basta con volver a calcular el simplex ingresando la (s) variable (s) en la base.
  • Sin solución : con el metodo de gran M, es posible que el campo de definición estar vacío En este caso, durante el cálculo de la M grande, ciertas variables artificiales tienen un valor distinto de cero.
  • Elección de la variable de entrada: cuando hay una elección entre las variables de entrada (mismo valor), se debe elegir como prioridad una variable básica del programa lineal.
  • Elección de la variable saliente: cuando hay una elección entre las variables salientes, primero se eligen las variables artificiales, luego las variables en exceso, luego las variables diferenciales y finalmente las variables básicas.
  • Solución degenerada: si la solución óptima tiene cero variables base, entonces se dice que es degenerada, este es el caso cuando hay más variables base que restricciones.

Ejemplo

Nótese que en ocasiones la tabla se escribe con el valor de -Z con los coeficientes de c, en este caso la solución óptima se obtiene cuando todos los coeficientes son negativos. Considere el siguiente programa lineal:

método dantzig simplex programación lineal variable entrante variable saliente

Primera iteración:

método dantzig simplex programación lineal variable entrante variable saliente

Lo que da después de pivote:

método dantzig simplex programación lineal variable entrante variable saliente

Aquí está la segunda iteración antes y después del pivote:

método dantzig simplex programación lineal variable entrante variable saliente

Todos los términos de -Z son negativos, por lo que tenemos una solución óptima (0, 250, 0, 200, 500, 0, 100, 0), la primera y la tercera restricción no están saturadas (variables de desviación en 500 y en 100); la función objetivo vale 350.000.

Compartir, repartir