viernes, 18 de abril de 2008

EL MÉTODO DE LA GRAN “M” (PENALIZACIÓN)

EL MÉTODO DE LA GRAN “M” (PENALIZACIÓN)

El método de la gran M consiste en modificar el problema original para dar lugar a un nuevo problema agregando una variable W llamada artificial y que se penalizara mediante un costo “M” de valores grandes y positivos, y esto permite que la función objetivo tome valores muy grandes.

Cuando W salga de la base en ese momento W=0 y esto indica haber regresado al problema original, pero si se llega a W>0, entonces el problema no tendrá solución.

MinZ= Cx + Mw

Sujeta a las restricciones y penalizando a Zw1 - Cw

  • Condición de introducción de las variables

Restricción > resta

Restricción < suma

Debido a que M es un valor positivo suficientemente grande, la variable R1 se penaliza en la función objetivo utilizando —MR, en el caso de la maximización, y +RM, en la minimización. Debido a esta penalidad El proceso de optimización lógicamente tratara de impulsar R1, al nivel cero

Minimice Z= 4X1 + X2

La forma estándar se obtiene restando un superávit X3 en la segunda restricción y añadiendo una holgura X en la tercera restricción. Por tanto obtenemos

Minimice Z= 4X1 +X2

La primera y segunda ecuación no tiene variables que desempeñen el papel de holguras. Por consiguiente, utilizamos las variables R1 y R2 en estas dos ecuaciones y las penalizamos en la función objetivo con MR1 + MR2. La PL resultante se da como

Minimice Z=4X1 +X2 + MR1 + MR2

En el modelo modificado, ahora podemos utilizar R1, R2 y X4 como la solución básica factible inicial como lo demuestra la siguiente tabla simplex

Antes de proceder con los cálculos del método simplex, necesitamos hacer que el renglón -Z sea consistente con el resto de la tabla simplex. De manera específica, el valor de z asociado con la solución básica inicial R1 = 5, R2 6, y X4 = 4 debe ser 3M + 6M + O = 9M en vez de O, como se muestra en el lado derecho del renglón -Z. Esta inconsistencia se debe al hecho de que R, y R2 tienen coeficientes no cero (-M, -M) en e! renglón -Z Estas inconsistencias se eliminan sustituyendo R1 y R2 en el renglón -Z, utilizando las ecuaciones apropiadas de restricción.

En particular, observe los elementos “1” realzados en el renglón -R1 y en el renglón -R2. Multiplicando cada uno de los renglones –R1 y de los renglones -R2 por M y añadiendo la suma al renglón -Z, efectivamente se sustituirá a R1 y R2 en el renglón objetivo. Podemos resumir este paso como

Nuevo renglón Z= Antiguo renglón Z + M x (Renglón R1) + M x (Renglón R2)

Esto se aplica como



4 comentarios:

nmilenah dijo...

Hola, fijate que tengo un problema con un ejercicio del Metodo de la gran M; z= 20x1+30x2-5x3+14x4+12x5 -20x6+12x7+15x8, sujeta a: x1=1000; x2=1500; x3=800; x4=1200; x5=900; x6=1100; x7=700; x8=1300. ¿Que solución le podría dar? Si me puedes ayudar te lo agradeceria mucho.

Dasrol dijo...

creo que tiene un error de iteracion en la segunda fila donde la VB es R2 y la columna es x2 deberia ser 5/3 no -1/3

Azael Suarez Loaiza dijo...

hola, me agrado la explicación pero tiene un error el error que ya noto Dasrol

Azael Suarez Loaiza dijo...

=)grax por la explicacion