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. L'conjunto elegible Por tanto, el problema es un poliedro convexo.
Método
El método símplex es un método iterativo que atraviesa los vértices del poliedro convexo hasta que ya no se puede mejorar la función objetivo. 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 – 0x3 – 0x4 – 0x5 = 0. Es decir que las variables del programa canónico están a cero, las variables de desviaciones son iguales al elemento de la derecha (b). A partir de ahora, es posible inicializar la matriz del método simplex.
La tabla inicial del método simplex está compuesta por todos los coeficientes de las variables de decisión del problema original y las variables de desviación.
| 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 simplex, ninguna base encontrada es degenerada, entonces el algoritmo termina en un número finito de iteraciones. Si hay una base degenerada, entonces podemos encontrarnos con un posible ciclo del algoritmo: encontramos una base ya encontrada y hacemos un bucle 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 con un coeficiente de -3. La columna de la variable que entra en la base, que se llama columna de pivote (en verde).
Se elige esta variable porque su impacto en el valor de Z es mayor (mayor gradiente). Introducir esta variable en la base de datos consiste en encontrar una solución en el espacio de soluciones siguiendo el gradiente de esta variable. En el siguiente diagrama, la ordenada tiene la mayor pendiente con respecto a 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 en la base la variable de entrada, se determina cuál será la variable de salida. La decisión se toma sobre la base de un cálculo simple: dividir cada término independiente (columna b) entre el elemento correspondiente de la 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. EL 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 son 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 distinto de cero más pequeño en la división anterior indica la fila de la variable de holgura que sale de la base. En este caso, resulta x5, con coeficiente 3. Esta recta 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): Elemento de línea nueva = Elemento de línea anterior – (Proyección de línea de pivote anterior * Proyección de columna de pivote anterior / Elemento de pivote anterior).
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 |
PARADA: 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 gradiente que mejore la solución), obtenemos la condición de parada.
El valor de Z (columna B) es la solución óptima al problema.
Cuando esta condición no se cumple, los procesos se vuelven a ejecutar iterativamente.
| 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 holgura x5) no está saturado con 3 márgenes.
Abstracto
Casos particulares
- Soluciones infinitas: cuando el simplex se detiene y las variables no básicas tienen un valor de 0 en la fila Z, significa que hay un número infinito de soluciones. Para conocer los límites del hiperplano (o del segmento) de soluciones, basta con recalcular el símplex 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 entrantes (mismo valor), se debe elegir una variable básica del programa lineal como prioridad.
- Elección de la variable saliente: cuando hay una elección entre las variables salientes, se eligen primero las variables artificiales, luego las variables de exceso, luego las variables de desviación y finalmente las variables básicas.
- Solución degenerada: si la solución óptima tiene variables base nulas, 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 desviaciones en 500 y en 100) ; la función objetivo es 350000.
