Metodo gran M

2.5.- METODO DE LA GRAN M
Éste método consisten en modificar el problema original y transformarlo a la forma canónica, lo cual se logra agregando un nuevo vector, conocido como variable artificial W, a las restricciones que generan el problema de negatividad en las variables de holgura (por lo general, ocurren las restricciones de igualdad y mayor-igual). Estas variables penalizan a la funciónobjetivo con un costo de MW, donde M es un valor positivo arbitrario muy elevado. Como el método simplex siempre trata de mejorar la función objetivo, por ello es que éste tratará de sacar a W de la base cuanto antes posible. Cuando W sale de la base, esto se traduce en que se ha retornado al problema original y cuya solución óptima estará garantizada por el método simplex. Si durante la operaciónse llegará a una solución óptima en que W tiene un valor positivo, entonces implica que el problema original no tiene solución (o la solución es infactible).

Nota: hay que tener presente que cuando la función objetivo es una maximización, la variable artificial la penalizará con un valor negativo (-MW), en cambio, para una función objetivo de minimización, la variable artificial la penalizaracon un valor positivo (+MW).

Ejemplo:


La forma estándar del modelo simplex queda:


Pero la restricción 1 y 2 no tienen variables que desempeñen la función de variable holgura, es decir, en la primera no existe variable y en la segunda hay una variable superflua, por lo cual, para solucionar dicho problema, se le adicionan dos variables artificiales w1 y w2:


Entonces, el PPLqueda:


Tenemos tres ecuaciones y seis incógnitas, por ello, la base inicial debe incluir 6-3=3 variables básicas con valor distinto a cero e igual número de no básicas con valor igual a cero. Para ello, la función objetivo debe contener el mismo número de variables que no están en la base, pero la función objetivo esta constituida por cuatro variables, por lo cual, será necesario sustituir lostérminos de w1 y w2 para obtener la forma canónica adecuada; lo anterior, se efectúa reemplazando dichos términos partir de las restricciones que poseen dichas variables w1 y w2. Para nuestro caso, corresponde a la restricción 1 y 2:


Por lo tanto, la función objetivo queda como:



Finalmente, el PPL queda de la siguiente manera:


El tableau inicial queda:
Z X1 X2 X3 W1 W2 X41 -(4+7M)  -(1+4M) M 0 0 0 -9M
W1 0 3
1 0 1 0 0 3 
W2 0 4 3 -1 0 1 0 6
X4 0 1 2 0 0 0 1 4

Z X1 X2 X3 W1 W2 X4
1 0 (1-5M)/3  M (4+7M)/3 0 0 4-2M
X1 0 1 1/3 0 1/3 0 0 1
W2 0 0 5/3
-1 -4/3 1 0 2 
X4 0 0 5/3 0 -1/3 0 1 3

Z X1 X2 X3 W1 W2 X4
1 0 0 1/5 (8+5M)/5 -(1-5M)/5 0 18/5
X1 0 1 0 1/5 3/5 -1/5 0 3/5
X2 0 0 1 -3/5 -4/5 3/5 0 6/5
X4 0 0 0 1 1 -1 1 1
Lasolución óptima es:


2.6.- METODO DE DOBLE FASE
Al igual que el método de la gran M, este método cumple con los mismos objetivos que el anterior, pero de la siguiente manera. Sea el siguiente problema original (en este caso usaremos la minimización para la función objetivo, aunque el método es independiente si es maximización, sólo hay que interpretar bien el sentido de las reglas autilizar):


Introducimos las variables artificiales al problema original:


FASE I:
Se resuelve el siguiente problema.


La solución óptima en esta fase debe ser W = 0. Si se tiene que W > 0, el problema no tiene solución.

Si la primera fase es efectivamente óptima, se pasa a la siguiente fase.

FASE II:
Se toma toda la tabla óptima anterior, ignorando únicamente las columnasasociadas a los Wi y el renglón de costos reducidos , sustituyendo este renglón por la función objetivo inicial:



Ejemplo:

Fase I:


Al igual que el método de la gran M, la solución debe estar constituida de tres variables, entonces:

El problema estándar queda:


La tabla inicial queda:
W X1 X2 X3 W1 W2 X4
1 7  4 -1 0 0 0 9
W1 0 3
1 0 1 0 0 3 
W2 0 4 3 -1 0 1 0 6
X4 0...