La Gran M

RESTRICCIONES EN FORMA DE IGUALDAD O LA GRAN “M”.

Sea el problema real:

Maximizar: Z=3x_1+5x_2

Sujeto a:

x_1 ≤4

2x_2≤12

3x_1+2x_2 =18

El correspondiente problema artificial:

Definimos: A_1=18-3x_1-2x_2

Maximizar: Z=3x_1+5x_2-MA_1

Sujeto a:

x_1 ≤4

2x_2≤12

De modo que: 3x_1+2x_2+A_1=18

Pero incluyendo todas las variables involucradas tenemos:

Maximizar: Z=3x_1+5x_2-0S_1-0S_2-MA_1

Sujeto a:

1x_1+ 0x_2+ 1S_1+0S_2 +0A_1 =4

0x_1 + 2x_2+0S_1 +1S_2 +0A_1 =12

3x_1+ 2x_2 +0S_1 +0S_2 + 1〖 A〗_1=18

Transformando el renglón cero, tenemos:

Z-3x_1-5x_2+0S_1+0S_2+MA_1=0

La tabla correspondiente es:

Iteración Previa

Renglón Variable x_1 x_2 S_1 S_2 A_1 b_i

[0] Z -3 -5 0 0 0 0

[1] S_1 1 0 1 0 0 4

[2] S_2 0 2 0 1 0 12

[3] A_1 3 2 0 0 1 18

Después multiplicamos el renglón tres [3] por menos eme (– M) y lo sumamos con los valores del renglón cero [0] como sigue:

(-M)× ( 3 2 0 0 1 18)

(-3M -2M 0 0 -M -18M)

(-3 -5 0 0 +M 0)

================================================

(-3-3M -5-2M 0 0 0 -18M)

Y con esta transformación estamos listos para escribir la iteración cero:

Iteración cero

Renglón Variable x_1 x_2 S_1 S_2 A_1 b_i

[0] Z -3-3M -5-2M 0 0 0 -18M

[1] S_1 1 0 1 0 0 4

[2] S_2 0 2 0 1 0 12

[3] A_1 3 2 0 0 1 18

La mayor de las columnas es la correspondiente a -3-3M y el renglón a seleccionar es entre el renglón [1] con valor de 4/1=4y el renglón [3] con valor de 18/3=6, así que seleccionamos el renglón [1] por tener el valor cuatro (4) que es menor que el renglón [3] cuyo valor de seis (6).

Iteración cero

Renglón Variable x_1 x_2 S_1 S_2 A_1 b_i

[0] Z -3-3M -5-2M 0 0 0 -18M

[1] S_1 1 0 1 0 0 4

[2] S_2 0 2 0 1 0 12

[3] A_1 3 2 0 0 1 18

Lo primero que vemos que no hay necesidad de transforma el renglón [1] puesto que tiene un uno (1) en el cruce de la selección y procedemos a transforma el renglón cero [0] al multiplicar el renglón uno [1] por -3-3M como sigue:

(3+3M)× ( 1 0 1 0 0 4)

(3+3M 0 3+3M 0 0 12+12M)

(-3-3M -5-2M 0 0 0 -18M)

===================================================

( 0 -5-2M 3+3M 0 0 12-6M)

Ahora este es nuestro nuevo reglón [0]. Y vemos que el segundo renglón [2] no requiere transformación dado que tiene un cero (0) en la columna. Pero sí el tercer renglón [3] que tiene un tres (3) si lo requiere como sigue:

(-3)× ( 1 0 1 0 0 4)

(-3 0 -3 0 0 -12)

( 3 2 0 0 1 18)

===================================================

( 0 2 -3 0 1 -6)

Estamos listos para escribir la iteración 1 como sigue:

Iteración Uno

Renglón Variable x_1 x_2 S_1 S_2 A_1 b_i

[0] Z 0 -5-2M 3+3M 0 0 12+6M

[1] x_1 1 0 1 0 0 4

[2] S_2 0 2 0 1 0 12

[3] A_1 0 2 -3 0 1 6

Nos damos cuenta que aún no hemos terminado puesto que hay un negativo que es -5-2M de la columna de x_2, columna que seleccionamos y debemos decidir cual renglón seleccionamos y solo pueden participar el renglón [2] con una cociente de 12/2=6 y el renglón [3] con una división de 6/2=3, de estos valores en menor corresponde con el tercer renglón [3] con valor de (3) así que seleccionamos este renglón:

Iteración Uno

Renglón Variable x_1 x_2 S_1 S_2 A_1 b_i

[0] Z 0 -5-2M 3+3M 0 0 12+6M

...