RESUMEN DEL CAPITULO

RESUMEN CAPITULO

EL MÉTODO SIMPLEX

“EL método simplex es un procedimiento algebraico. Sin embargo sus conceptos fundamentales son geométricos” (Pág. 109). Este método es un algoritmo que nos permite resolver problemas de programación lineal y hacer análisis posóptimos y se hace mucho más fácil de entender basándose en los conceptos geométricos como son: el análisis de las soluciones FEV, la aplicación de un procedimiento sistematizado, la toma de sus variables de decisión iguales a cero, el seguimiento de una trayectoria lo largo de las aristas de la región factible para hallar una solución óptima, identificación de la tasa de mejoramiento en Z que se mueve por la arista que más aumenta su valor y la verificación de sí la tasa de mejoramiento en Z es positiva o negativa para determinar si se mueve por esta o por su adyacente.

En programación lineal cualquier problema con n variables de decisión posee dos soluciones FEV adyacentes entre sí si comparten n-1 fronteras de restricción. Las soluciones FEV adyacentes se conectan mediante una recta ubicada en las fronteras de restricción compartida, a esta recta se le llama orilla o arista de la región factible.

Fases:

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2. Igualar la función objetivo a cero

3. Escribir la tabla inicial simplex

En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:

4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base

   1. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).

      Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos.

      Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos.

      La columna de la variable que entra en la base se llama columna pivote (En color azulado).

   

   2. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero.

      Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.

      Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes puede salir de la base. 

      

   3. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional

5. Encontrar los coeficientes de la nueva tabla.

Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, que es el que hay que convertir en 1.

A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z. 

IDENTIFICANDO CASOS ANÓMALOS Y SOLUCIONES

Obtención de la solución: Cuando se ha dado la condición de parada, obtenemos el valor de las variables básicas que están en la base y el valor óptimo que toma la función que están en la base mirando la columna P0. En el caso de que estemos minimizando, se multiplicará por "-1" el valor óptimo.

Infinitas soluciones: Cumplida la condición de parada, si se observa que alguna variable que no está en la base, tiene un 0 en la fila Z, quiere decir que existe otra solución que da el mismo valor óptimo para la función objetivo. Si estamos ante este caso, estamos ante un problema que admite infinitas soluciones, todas ellas comprendidas dentro del segmento (o porción del plano, o región del espacio, dependiendo del número de variables del problema) que define Ax+By=Z0. Si se desea se puede hacer otra iteración haciendo entrar en la base a la variable que tiene el 0 en la fila Z, y se obtendrá otra solución.

Solución ilimitada: Si al intentar buscar la variable que debe abandonar la base, nos encontramos que toda la columna de la variable entrante tiene todos sus elementos negativos o nulos, estamos ante un problema que tiene solución ilimitada. No hay valor óptimo concreto, ya que al aumentar el valor de las variables se aumenta el valor de la función objetivo, y no viola ninguna restricción.

No existe solución: En el caso de que no exista solución, seguro que tendremos que realizar las dos fases, por lo que al término de la primera sabremos si estamos en tal situación.

Empate de variable entrante: Se puede optar por cualquiera de ellas, sin que afecte a la solución final, el inconveniente que presenta es que según por cual se opte se harán más o menos iteraciones. Se aconseja que se opte a favor de las variables básicas, ya que son aquellas las que quedarán en la base cuando se alcance la solución con estos métodos.

Empate de variable saliente: Se puede nuevamente optar por cualquiera de ellas, aunque se puede dar el caso degenerado y entrar en ciclos perpetuos. Para evitarlos en la medida de lo posible, discriminaremos a favor de las variables básicas haciendo que se queden en la base. Ante el caso de estar en la primera fase (del método de las Dos Fases), se optará por sacar en caso de empate las variables artificiales.

Curiosidad Fase 1: Al finalizar la fase 1, si el problema original tiene solución, todas las variables artificiales, en la fila Z deben tener el valor "1".

¿Pivote puede ser 0?: No, ya que siempre se realizan los cocientes entre valores no negativos y mayores que cero.