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