METODO DE LA GRAN M
Método de la gran M
Corresponde a una variación del algoritmo simplex para penalizar la presencia de variables artificiales mediante la introducción de una constante M definida como un valor muy grande pero finito
Ejemplo:oMin Z= 4
Sujeto a:
0
oPaso 1
convertir la desigualdad de cada restricción en igualdad
oPaso 2
o Paso 3
Z= 4++
o Paso 4Determinar nuestras variables básicas como solución factible inicial para las restricciones
o Paso 5
Expresaremos la función objetivo en términos de variables básicasZ= 4++
Por otro lado se tiene que:
-
se sustituye en la función objetivo:
Z= 4+M()+M(-)
o Luego se obtendrá:
Z- (4)
o Paso 6
Planteamos la tabla básica inicial en ella colocamos los coeficientes de la función objetivo:
o Paso 7
Se selecciona la variable de entrada correspondiente a la función optima
o Paso 8
Se selecciona la variable de salida según su factibilidadPara esto primero dividiremos la solución en nuestra que es la variable de entrada
En este caso fue el numero mas pequeño y por lo tanto nuestra fila pivote
o Tenemos listo nuestra fila y columna pivote y se procede a hacer cálculos como en el método simplex
o Paso 9
Se calcula la fila pivote dividiendo para hacer 1 nuestro pivote.
o Paso 10
Calcular los valores de Z para construir nuestra tabla en este caso será -(4)* EP los nuevos valores de Z serán:
Para y se hace lo mismo para hacer 0 en valor que esta debajo de nuestra ecuación pivote. (se multiplica su valor en en signo negativo por la ecuación pivote) y la primera iteración queda de la siguiente manera:
Como vimos en nuestra tabla anterior que no hay solución nos regresamos al paso 7Siendo el y al dividir la solución nuestra variable de salida es
Haciendo nuestros cálculos empezando con nuestra ecuación pivote haciendo 1 siguiendo como en el método simplex nuestra siguiente iteración quedaría de la siguiente manera:
Observando la tabla hemos encontrado la solución a este ejercicioSustituyendo en la funcio objetivo se comprueba que las soluciones encontradas cumple con la siguiente igualdad