Investigacion de operaciones

METODO DE LAS DOS FASES
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álido.  Habría más bien que comparar la eficiencia de los algoritmos anivel 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 = 0entonces 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 +  3X2 -  X3   <=  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 supremamentefá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 equivalea 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 o6+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 coeficientemuy 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...