Metodo De La Gran "M"

Investigación De Operaciones - Método de la Gran M

Descripción clara del Método de la Gran M para resolver problemas de Programación Lineal usando el Simplex con restricciones de >= e =
Mientras que los Programas  Lineales que solo tienen restricciones de <= se pueden resolver sólo usando variables de holgura, para aquellos programas lineales que involucren restricciones de tipo >= e= es necesario como ya lo habíamos comentado, usar variables artificiales.  Dijimos también que las variables de holgura tenían un significado físico real que correspondía a las disponibilidades o requerimientos no usados en las restricciones, pero que las  variables  artificiales no tenían ninguna representación física y que sólo eran usadas como un comodín matemático para ayudar en la solucióndel problema. Pues bien, cuando tenemos que usar variables artificiales al tener restricciones de >= e = debemos usar uno de las siguientes variantes del simplex:
 
* El Método de la Gran M
* El Método de las dos fases
 
Aquí detallaremos el Método de la Gran M.
 
Definimos la letra M como un número muy grande pero finito para usarlo como coeficiente de las variables artificialesen  la función objetivo y con sentido contrario a la misma para penalizar de manera muy grande la existencia de las mismas en la solución.  Si el objetivo es minimizar las variables artirficiales entraran con M positivo y si es maximizar las variables artificiales se usaran como -M. 
 
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 supremamente fácil. Simplementese 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 maslo 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érminosgenerales:
 
                    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 esta 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 unavariable 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 estarminimizando 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:
 
           ...