Método de la M Grande (o Gran M) en Programación Lineal

En el contexto de la aplicación del Método Simplex no siempre es inmediata la obtención de una solución básica factible inicial, en las variables originales del modelo. Para conseguir esto existen varios procedimientos como son el Método Simplex de 2 Fases y el Método de la M Grande (o Gran M) el cual abordaremos en este artículo. Para ello consideremos el siguiente modelo de Programación Lineal en 2 variables:

modelo-m-grande

A continuación agregamos las variables no negativas x_{3} (holgura restricción 1), r_{1} (auxiliar restricción 2), x_{4} (exceso restricción 3) y r_{2} (auxiliar restricción 3). El modelo ahora es:

formato-m-grande

Donde el parámetro M es una constante positiva suficientemente grande para representar una penalización adecuada en la función objetivo. La tabla inicial del método esta dada por:

tabla-inicial-m-grande

Antes de continuar con las iteraciones se debe procurar que el costo reducido de las variables r_{1}r_{2} sean ceros. Para ello multiplicamos por -M la fila 2 y la fila 3 y luego sumamos a la fila 4, obteniendo lo siguiente:

iteracion-1-m-grande

Ahora debemos seleccionar que variable no básica ingresa a la base. El menor costo reducido corresponde a la variable x_{1} en consecuencia dicha variable ingresa a la base. Luego calculamos el mínimo cuociente en dicha columna: Min \begin{Bmatrix}{\frac{27/10}{3/10}, \frac{6}{1/2}, \frac{6}{3/5}}\end{Bmatrix}=9, el cual se alcanza en la fila 1, por tanto la variable x_{3} deja la base. Se actualiza la tabla:

segunda-iteracion-m-grande

Siguiendo con las iteraciones ahora la variable x_{2} entra a la base. El criterio de factibilidad indica que: Min \begin{Bmatrix}{\frac{9}{1/3}, \frac{3/2}{1/3}, \frac{3/5}{1/5}}\end{Bmatrix}=3 la variable r_{2} abandona la base (el pivote se encuentra en la fila 3). Actualizamos la tabla:

tercera-iteracion-gran-m

Una nueva iteración indica que x_{3} ingresa a la base. El mínimo cuociente en la respectiva columna es: Min \begin{Bmatrix}{\frac{8}{20/3}, \frac{1/2}{5/3}}\end{Bmatrix}=3/10 (recordar que se omiten denominadores menores a cero). Ahora el pivote se encuentra en la fila 2 y en consecuencia x_{4} deja la base. Se actualiza la tabla:

tabla-optima-m-grande

Se ha alcanzado la solución óptima con x_{1}=15/2x_{2}=9/2. Notar que las variables auxiliares (r1 y r2) son no básicas en el óptimo. El valor óptimo es 21/4 (notar que el signo esta cambiado).

Para una mejor comprensión de los resultados alcanzados a continuación se presenta la resolución gráfica del problema haciendo uso del software Geogebra. El dominio de soluciones factibles corresponde a la recta que une los vértices A y B. Adicionalmente se muestra la curva de nivel que pasa por la solución óptima (vértice B).

solucion-grafica-m-grande

Teóricamente se espera que en la aplicación del Método de la M Grande las variables auxiliares sean no básicas en el óptimo. Si el modelo de Programación Lineal es infactible (es decir, si las restricciones no son consistentes), la iteración del Método Simplex final incluirá al menos una variable artificial como básica.

Adicionalmente la aplicación de la técnica de la M Grande implica teóricamente que M tiende a infinito. Sin embargo al usar la computadora M debe ser finito, pero suficientemente grande. En específico M debe ser lo bastante grande como para funcionar como penalización, al mismo tiempo no debe ser tan grande como para perjudicar la exactitud de los cálculos del Método Simplex, al manipular una mezcla de números muy grandes y muy pequeños.

Rating: 3.2. From 6 votes.
Please wait...

, , , , , , ,

Sin Comentarios aun. Se el primero en comentar!

Deja un comentario