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,
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:
- El problema está escrito debajo forma estándar.
- Se encuentra una solución.
- Encuentra la columna de pivote.
- 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:
| Maximizar | Z = 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 | 3 | 2 | |||||
| Basado | Cb | B | X1 | X2 | X3 | X4 | X5 |
| X3 | 9 | 18 | 2 | 1 | 1 | 0 | 0 |
| X4 | 21 | 42 | 2 | 3 | 0 | 1 | 0 |
| X5 | 8 | 24 | 3 | 1 | 0 | 0 | 1 |
| Z | 0 | -3 | -2 | 0 | 0 | 0 |
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.
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 x4 | 42 | 2 | 3 | 0 | 1 | 0 |
| – | – | – | – | – | ||
| proyección | 2*24 | 2*1 | 2*0 | 2*0 | 2*1 | |
| / | / | / | / | / | ||
| pivote | 3 | 3 | 3 | 3 | 3 | |
| = | se convierte en | = | = | = | = | |
| Nueva línea x4 | 26 | 0 | 7/3 | 0 | 1 | -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 | |||||||
|---|---|---|---|---|---|---|---|
| 3 | 2 | 0 | 0 | 0 | |||
| Basado | Cb | B | X1 | X2 | X3 | X4 | X5 |
| X3 | 2 | 0 | 1/3 | 1 | 0 | -2/3 | |
| X4 | 26 | 0 | 7/3 | 0 | 1 | -2/3 | |
| X1 | 8 | 1 | 1/3 | 0 | 0 | 1/3 | |
| Z | 24 | 0 | -1 | 0 | 0 | 1 |
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 | |||||||
|---|---|---|---|---|---|---|---|
| 3 | 2 | 0 | 0 | 0 | |||
| Basado | Cb | B | X1 | X2 | X3 | X4 | X5 |
| X2 | 0 | 12 | 0 | 1 | -1/2 | 1/2 | 0 |
| X5 | 0 | 3 | 0 | 0 | -7/4 | 1/4 | 1 |
| X1 | 0 | 3 | 1 | 0 | 3/4 | -1/4 | 0 |
| Z | 33 | 0 | 0 | 5/4 | 1/4 | 0 |
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
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:
Primera iteración:
Lo que da después de pivote:
Aquí está la segunda iteración antes y después del pivote:
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.
ES 
FR 
EN