Método de la Gran M

Descripción clara del Método de la Gran M para resolver problemas de Programación Lineal usando el Simplex con restricciones de >= e =

Ejemplo:

1. Convertir al Modelo Estándar:

Fig 1 

Min Z
2 1 3 0 0 M 0 M RHS

R1

3
1 2 1 0 0 0 0 10

R2

1

-2

3 0 -1 1 0 0 6

R3

2
3
-1 0 0 0 1 0 9

R4

1 1 2 0 0 0 0 1 7

Dónde X1, X2, X3 son las variables de decisión, S1, S2 y S3 son las variables de Holgura. R1, R2, R3, R4 son las restricciones y RHS son las disponibilidades o Requerimientos de las restricciones, (RHS= Right Hand Side: «el lado derecho» es decir los valores numéricos).

3. Definir la Variable que entra

Recordemos que tenemos un grupo de variables que llamamos base a las que tenemos en cuenta en cada iteración para dar la solución, las demás variables las llamamos No Básicas y se se toman con valor cero (de manera análoga a cuando resolvemos un sistema de ecuaciones que tiene más variables que ecuaciones, tenemos que hacer cierta cantidad de estas variables iguales a cero).

En la primera iteración la regla para escoger las variables que estarán en  la base es la siguiente:

-Si hay variables de decisión y de holgura, se toma la de holgura.

-Si hay variables de decisión, de holgura y artificiales se toma la variable artificial.

-Si hay variables de decisión y artificiales se toma la variable artificial.

Por esta razón para la primera restricción dónde hay variables de decisión (Xi) y la de holgura S1, tomamos la S1 para  la base, en la segunda restricción hay de holgura, de decisión y artificial, tomamos la artificial A1, en la tercera hay de decisión y de holgura, tomamos la de holgura S3 y por último en la cuarta restricción hay de decisión y artificial, por lo que tomamos la A2 para la base. Todas las demás se asumen en la primera iteración con valor cero.

Llenar la tabla inicial

Tal como se ve en la tabla de abajo. Hay muchos formatos de tablas, pero en esencia son el mismo. Esta el listado de variables que se tienen en la base (en la segunda columna rotulada como base), en la primera columna están los coeficientes de las variables básicas, luego vienen las restricciones con sus coeficientes, las disponibilidades/requerimientos de las restricciones en la columna RHS, una columna vacía llamada Theta que ya llenaremos. Las dos ultimas filas son para determinar que variable va a entrar a la base. Algunas personas omiten la fila
Z. Realmente no es necesaria, sólo para dar un poco más de claridad a la iteración.

La fila Z es el resultado de la suma del producto de la columna ‘coef’ y de cada columna en la restricción, así:

    0 * 3 + M * 1     +  0*2   +  M*1    =  2M

    0 * 1 + M * (-2) +   0*3   +  M*1    =  -M

    0 * 2 + M * 3    +   0 *-1 +  M*2    =  5M …De igual manera para las otras 5 columnas.

La fila Cj-Zj es el resultado de restar el coeficiente de la función objetivo (la segunda fila de negro) con el valor de Z que acabamos de calcular.

2-2M = 2-M (evidente!)

1-(-M) = 1+M… Etc

En este momento nos hacemos la siguiente pregunta: cuál variable al entrar a la base hace que la función objetivo disminuya más (porque estamos minimizando)? O en otras palabras, cuál es el valor más negativo de Cj-Zj? Recordemos que M representa un número finito, muy, muy grande.  Rápidamente nos damos cuenta que corresponde a 3-5M, puesto que de todas es la que tiene el valor negativo de M con mayor valor absoluto. Si no lo ve tan rápido, haga lo siguiente: reemplace M por un valor grande positivo en la fila Cj -Zj, digamos por 1000.000, notará de inmediato que el valor más negativo esta en la columna respectiva a la variable X3.
Por lo tanto ésta variable debe entrar a reemplazar a otra variable en la base… A cuál?? 

Fig 2 

 Coef Base 2 1 3 0 0 M 0 M RHS Theta  0 S1
3
1 2
1 0 0 0 0 10

5.00  M
A1
1

-2

0

-1

1 0 0 6

2.00 Sale0 S3
2 3
-1 0 0 0 1 0 9
M  M A2
1 1 2 0 0 0 0 1 7

3.50    Z
2M
-M 5M 0 -M M 0 M 13M
    

Cj- Zj

2-2M

1+M

3-5M 0 M 0 0 0              Entra                

3. Definir la Variable que Sale

5. Prueba de Optimidad:

 La prueba de optimidad se debe hacer cada vez que se evalúa si hay una variable que debe entrar a la base. Y es sencillamente lo siguiente. Se hace la pregunta: Hay alguna variable que al entrar mejora la solución? Ello lo vemos en la fila Cj-Zj. Si al calcular esta fila aún hay valores negativos y estamos minimizando, entonces es posible mejorar aún más la solución. Lo mismo para el caso de la maximización. Si hay valores positivos en la fila Cj-Zj y estamos maximizando, aún no hemos llegado al óptimo. 

En la fig 2 nos damos cuenta que habían todavía valores negativos en Cj-Zj, por lo tanto no se había terminado, ahora en la fig 3, aún quedan valores negativos, el más negativo de ellos esta en la variable X2 por lo tanto debe entrar.

Continuando el algoritmo en la fig3 evaluamos que la variable A2 debe salir, la reemplazamos en el tablero de la figura 4. Hacemos gauss-jordán, luego calculamos Z y calculamos Cj-Zj. 

Fig 3. 

 Coef Base 2 1 3 0 0 M 0 M RHS Theta  0 S1
2.33 2.33
0.00
1.00 0.67
-0.67 0 0 6
2.57  3 X3
0.33

-0.67

1.00
0.00
-0.33 0.33 0 0 2 M  0 S3
2.33 2.33 0.00 0.00
-0.33 0.33 1 0 11

4.71  M

A2

0.33 2.33 0.00 0.00 0.67
-0.67 0 1 3
1.29 Sale
  Z

1+0.33M

-2+2.33M

3 0

-1+0.66M

1-0.66M 0 M 6+3M
    

Cj- Zj

1-0.33M

3-2.33M 0 0 1-0.66M

-1+1.66M 0 0            Entra                  

Aquí en el tablero de la figura 4, evaluamos si hay algún valor negativo en la fila Cj-Zj, nos damos cuenta que no, por lo que no hay ninguna variable que al entrar mejore la solución.

Hemos llegado al óptimo: La solución es Z=9.8571 X1=0 (Por que no estaba en la base.)  X2= 1.29, X3=2.86

Fig 4 

0 S1

2.00 0.00 0.00
1.00 0.00 0.00 0.00

-1.00

3.00  3 X3
0.43 0.00
1.00 0.00
-0.14 0.14 0.00
0.29
2.86  0 S3

2.00 0.00 0.00 0.00 -1.00 1.00 1.00 -1.00
8.00  1 X2
0.14
1.00 0.00 0.00 0.29
-0.29 0.00
0.43
1.29    Z

1.43
1.00
3.00 0.00
-0.14 0.14 0.00
1.29
9.8571    Cj- Zj
0.57 0.00 0.00 0.00
0.14 M+0.62 0.00 M+2.43    

Nota

.