Método de las Dos Fases


 

Para la comprensión de éste algoritmo es preferible entender primero el Método de la Gran M, aunque no es estrictamente necesario.


Este método es sumamente sencillo.  Se usa ante la presencia de variables artificiales en el modelo a solucionar y su objetivo es eludir el uso de la constante M, aquella que definimos como un número muy grande aunque finito, supuestamente por problemas de redondeo o de escala.  Debo decir, entre paréntesis, que esta motivación hoy en día se me antoja como equivocada.  Como desarrollador de software, sé que el algoritmo puede tratar a la M como una constante si se le asigna un valor, o como una variable a la que se le asigne el valor requerido (que respete la definición) en cada comparación, como lo hacen las personas que resuelven a mano. Esto hace que hoy en día esta motivación no sea muy válida.  Habría más bien que comparar la eficiencia de los algoritmos a nivel de volumen de cálculos, de número de tableros, etc., para decantarse por uno u otro. Es mi humilde opinión.
 
A continuación la explicación del algoritmo: 


Primera Fase:


Se reemplaza la función objetivo del programa lineal a solucionar por la minimización de la suma de las variables artificiales encontradas en la normalización del modelo y se resuelve. Si en la minimización Z = 0 entonces se puede proceder a la Segunda Fase, de lo contrario el problema no es factible, por lo tanto, no tiene solución.
 
 

Segunda Fase:

 

Se inicia con base en el tablero final de la Primera Fase, se retoma la función objetivo del programa, haciendo todas las variables artificiales iguales a cero y eliminándolas de las restricciones.

 

Ejemplo:
 
Min Z  = 2X1 X2 + 3X3
Sujeto a:
                  3X1 +   X2 + 2X3   <=  10
                    X1 -  2X2 + 3X3   >=  6
                  2X1 +  3X2X3   <=  9                   
                    X1 X2  +  2X3  =  7          
C.N.N
 
1. Convertir al Modelo Estándar:
 
Cada restricción debe ser convertida de inecuación a una igualdad, agregando variables como se requiera. Con las restricciones de tipo <=, es supremamente fácil. Simplemente se agrega una en cada restricción con coeficiente 1 en la misma restricción y con coeficiente cero en la función objetivo. Por ejemplo:
 
                    3X1 +   X2 + 2X3   <=    10 queda:
                    3X1 +   X2 + 2X3 + S1  =    10
 
Se puede leer así:  el uso de la primera restricción no puede superar la disponibilidad de 10 unidades, lo que equivale a decir que lo usado mas lo que sobre (s1) es igual a 10. Para las restricciones de tipo mayor o igual, la lógica es la misma, de esta manera decir:
 
                    X1 -  2X2 + 3X3    >=     6
 
Se puede leer como: el uso de la restricción 2 debe ser como mínimo 6 unidades. Eso significa que el uso podría ser 6.1 o tal vez 7 u 8... etc. Podríamos escribirlo también como 6+0.1 o 6+1 o 6+2 ... o en términos generales:
 
                    X1 -  2X2 + 3X3    =     6   + S2 que es equivalente a decir: lo usado en la restricción2es igual al mínimo requerido que es 6 mas el adicional que está en S2. Esto lo podemos reescribir como:
 
                    X1 -  2X2 + 3X3  - S2   =     6  
 
Sin embargo para el método simplex, cuando aparece esta restricción tipo >= es necesario adicionar una variable comodín, llamada Variable Artificial, sin ningún significado físico, sólo como artificio matemático. Lo sumamos al lado izquierdo de la restricción como se muestra a continuación:
 
                    X1 -  2X2 + 3X3  - S2   + A1 =     6 
 
Al usar una variable artificial debemos penalizar la función objetivo allí la vamos a incluir con un coeficiente muy grande, llamado M, al estar minimizando la sumamos  + .MA1.
 
La tercera restricción es de tipo <=, por lo que no tenemos ningún problema con ella:
 
                  2X1 + 3X2 -    X3    <=     9   queda
                  2X1 + 3X2 -    X3  + S3  =     9  
 
La cuarta restricción es de tipo =. Para  este tipo de restricción simplemente adicionamos una variable artificial al lado izquierdo:
 
                      X1 +  X2  +2X3      =     7 queda:
                      X1 +  X2  +2X3    + A2  =     7

Recordemos: las variables de holgura quedan con coeficiente 0 en la función objetivo y las variables artificiales con coeficiente M. Positiva si es minimizando o negativa si es maximizando.
 
En resumen el modelo queda de la siguiente manera:
 
Min Z  =  2X1 +     X2     +  3X   + 0S1 + 0S2 + MA1 + 0S3 + MA2
Sujeto a:
                    3X1  + X  + 2X3 +   S1                              =  10
                       X1 - 2X2 + 3X        - S2   + A              =    6
                     2X1+ 3XX                        + S3         =    9                   
                       X1+ X2   + 2X3                               + A2    =  7          
C.N.N (Condición de No Negatividad)

Inicio del Método de las Dos Fases:


Min Z  =  A1 + A2
Sujeto a:
                    3X1 +X2 + 2X3 + S1                     =    10
                      X1 -2X2+ 3X3    - S2   + A1         =     6
                     2X1+3X2- X3             + S3           =     9                   
                       X1+ X2+ 2X3                  + A2    =     7          
C.N.N (Condición de No Negatividad)

 

 

FASE 1

 

 

 

En la siguiente figura encontramos la tabla simplex clásica. En la primera fila los nombres de las variables de decisión, y justo abajo de ellas, los coeficientes de estas variables en la función objetivo. Cómo en la primera fase minimizamos la suma de las variables artificiales, por eso sólo encontramos un valor de 1 abajo de A1 (variable artificial 1) y de A2 (variable artificial 2). En la segunda columna encontramos las variables que estan en la base al inicio. Como es costumbre, para escogerlas preferimos si sólo hay variables de decisión y de holgura, escogemos la de holgura para estar en la base (aqui las llamamos S) y si hay  de decision, de holgura y artificiales, preferimos la artificial. Por eso, las variables que se escogen para la base son:  S1, A1, S3, A2.    A la izquierda de esta columna, como es usual, se coloca los coeficientes en la función objetivo, de las variables que estan en la base.  

 

Luego vienen los coeficientes de las restricciones, y debajo del título RHS (Right Hand Side), o "lado derecho" de la restricción, colocamos las disponibilidades o requerimientos.  En otros libros de texto a esta columna tambien la llaman Bi, lo importante es que usted entienda que todos los diferentes formatos de tablas, realmente son lo mismo, lo único que cambia es el orden, la forma de llamar a las columnas, etc.

 

Bueno, sin dar tantas vueltas: En la primera iteración se  calcula Z y C - Z, y por lo tanto la variable que entra, como estamos minimizando, entra la más negativa: X3 y entra la que mas restringe: A1. Eso hace que la celda pivote este en el valor 3, que lo coloqué con verde en todas las figuras.  Y se aplica eliminación gaussiana: Se divide toda esa fila por tres, y luego con la fila convertida, elimino por encima y por debajo de la celda pivote multiplicando por el valor opuesto al que quiero eliminar la fila pivote y sumandosela componente a componente a la fila que deseo eliminar. Bueno, en estos momentos del partido, creo que usted ya debe saber bien como hacer la eliminación gaussiana (Y si no, coloquelo en los comentarios abajo, para ampliar la explicación!) .

 

 

 

 

El valor de la función objetivo, en cada itereación la he colocado en azul claro, para que vaya viendo el progreso: 13 -> 3  ->  0. 

 

Al terminar en cero, el semaforo nos da luz verde para seguir con  la siguiente fase.  

 

 FASE 2

 

En la FASE 2, fijese que cambiamos la fila de la función objetivo y dejamos la del programa original, pero como en la fase 1 nos aseguramos de eliminar las variables artificiales, en la fase 2, nos podemos dar el lujo y el gusto de eliminarlas. También, como es lógico, las borramos de las restricciones. Ahora , sin estorbos, sin constantes M, o variables artificiales que nos retracen el paso, por que vamos de prisa, realizamos la iteración,. y para el colmo de nuestra suerte, en sólo una iteración acabamos. 

 

Encontramos el valor de Z.  He escogido el mismo programa para resolverlo por la Gran M que por el método de las dos fases. Compárelo  a ver cuál le gusta más... a mi me gustaba más el método de la Gran M, pero ahora me esta gustando más el método de las Dos Fases... aunque la verdad, en la práctica, en la vida real, nunca he resuelto a mano un programa lineal, si no que siempre he usado un software... mi jefe no me paga más, por más iteraciones que calculé, si no por que le entregue una respuesta rápida y exacta de lo que se necesita: Si. Lo sé. A veces, la vida es triste  :)  

 

 

 

 

Contenido :

Social