MÉTODO DE LA GRAN M

MÉTODO DE LA GRAN M
El método de la gran M consiste en modificar el problema original para dar lugar a un nuevo problema agregando una variable llamada artificial y que se penalizaran mediante un costo “M” de valores grandes y positivos, y esto permite que la función objetivo tome valores muy grandes.
PASOS A SEGUIR
1. Pasar a la forma estándar el modelo matemático.
2. Agregar variablesartificiales en las ecuaciones que no tienen variables de holgura.
3. Se deben penalizar a las variables artificiales en la función objetivo asignándolas coeficientes positivos muy grandes. Sea M un número muy grande (en los modelos de minimización la penalización para cada variable se suma en los modelos de maximización se restan).
4. Con la solución inicial artificial se aplica el método Simplex de laforma acostumbrada generando las tablas necesarias para llegar a una solución.
EJEMPLO
Una compañía fabrica y vende cinco productos.
En la siguiente tabla se dan los costos por unidad y precio de venta


PRODUCTO




A
B
C
D
E
COSTO POR UNIDAD
50
80
300
25
10
PRECIO DE VENTA
70
90
350
50
12

Productos A,B,C,D,E
Si el objetivo es maximizar las unidades totales, formule un modelo de programaciónlineal dotado de las siguientes restricciones:
Hay que producir un mínimo de 20 unidades del producto A y 10 unidades del producto B; no se dispone de suficie4ntes materias primas para una producción total mayor que 75 unidades; el número de unidades fabricadas de los productos C y E han de ser iguales.
FORMULACION DEL PROBLEMA:
Variables de decisión
Xi cantidad de productos i que deben producir lacompañía i (A,B,C,D,E)


FUNCION OBJETIVO:
Max Z= (70-50) Xi + (90-80) X2 + (350-300) X3 + (52-25) X4 + (12-10) X2
Max Z= (20) X1 + (10) X2 + (50) X3 + (25) X4 + (2) X5:

Sujeto a: Condición de no negatividad
x1 >=20 (x1+ x2 + x3 + x4 + x5) >=0
x2 >=10
x1+x2+x3+x4+x5 <=75
x3 + x5 =0


SOLUCION DEL PROBLEMAEstandarización del problema
Z = 20x1 + 10x2 + 50x3 + 25x4 + 2x5 – Mx7 – Mx9 – Mx11
Z = 20x1 + 10x2 + 50x3 + 25x4 + 2x5 + Mx7 + Mx9 + Mx11=0

x1 -x6+x7 =20
x2 - x8 + x9 =10
x1+x2+x3+x4+x5 + x10 =75
x3 + x5+ x11 =0


RECORDEMOS
Las variables de holgura quedan con coeficiente 0 en la función objetivo y las variables artificiales con coeficiente M.
Positiva si es minimizando o negativa si es maximizando.

En la primera iteración la regla para escoger las variables que estarán en la base es la siguiente:
1. Si hay variables de decisión y de holgura, se toma la de holgura.2. Si hay variables de decisión, de holgura y artificiales se toma la variable artificial.
3. Si hay variables de decisión y artificiales se toma la variable artificial.
PARA DEFINIR EL PIVOT
Definir la variable que entra: Cuál es el valor más negativo de Cj-Zj? Recordemos que M representa un número finito, muy grande. Por lo tanto ésta variable debe entrar a remplazar a otra variable en la base.Definir la variable que sale: Para establecer que variable debe salir de la base, hacemos un cociente entre la disponibilidad y la columna de la variable que entra.
ITERACIÓN GAUSS-JORDAN
Después de que se haya encontrado que variable sale de la base, y cual entra y que por lo tanto ya tenemos una celda pivote, es necesario realizar la eliminación gaussiana. Lo podemos resumir como:
Convertir lacelda pivote en 1, dividiendo toda la fila por ella misma.
Convertir todas las celdas por encima y por debajo de la celda pivote en 0.
Esta nueva fila que hemos calculado va a servir para convertir las demás celdas por la columna del pivote en cero, como es el requisito del método.
Para ello hacemos operaciones entre filas y columnas de la siguiente manera:
Multiplicamos la fila que contenía el...