Ejercicio de método Branch and Bound (Ramificación y Acotación)

Investigación de Operaciones I

Diego Nicolás Ramos Zamudio-20181020167

Ejercicio de método Branch and Bound

(Ramificación y Acotación)

Modelo

Maximizar Z = 4x1 + 6x2 +2x3

S.a

4x1 – 4x2 <= 5

-x1 + 6x2 <= 5

-x1 + x2 +x3 <= 5

X1, X2, X3 >= 0 y entera

Solución

Sacamos la Forma Estandarizada

Max Z= -4x1 -6x2 – 2x3

S.a

4x1 – 4x2 + S1 = 5

-x1 + 6x2 + S2 = 5

-x1 + x2 + x3 + S3 = 5

X1, X2, X3 >= 0, E

Aplicamos Simplex

Matriz Inicial

Cj 4 6 2 0 0 0

VB X1 X2 X3 S1 S2 S3 Bj

S1 0 4 -4 0 1 0 0 5

S2 0 -1 6 0 0 1 0 5

S3 0 -1 1 1 0 0 1 5

Zj -4 -6 -2 0 0 0 0

Cj-Zj 8 12 0 0 0 0

Observamos el Zj más alejado del 0 por los negativos para determinar la columna pivote y dividimos los valores con Bj con los valores de la columna de X2 y tomamos el valor más bajo de ellos, siendo el pivote 6.

Ingresa la variable X2 y sale S2.

Iteración 1

Cj 4 6 2 0 0 0

VB X1 X2 X3 S1 S2 S3 Bj

S1 0 10/3 0 0 1 2/3 0 25/3 4*X2+S1

X2 6 -1/6 1 0 0 1/6 0 5/6 X2*1/6

S3 0 -5/6 0 1 0 -1/6 1 25/6 -1*X2+S3

Zj -5 0 -2 0 2 0 5

Cj-Zj 9 6 4 0 0 0

Observamos el Zj más alejado del 0 por los números negativos nuevamente y vemos que es la columna X1, dividimos los valores de Bj con los valores de la columna pivote y tomamos el valor más bajo, siendo el pivote 10/3

Ingresa la variable X1 y sale S1

Iteración 2

Cj 4 6 2 0 0 0

VB X1 X2 X3 S1 S2 S3 Bj

X1 4 1 0 0 3/10 1/5 0 5/2 3/10*S1

X2 6 0 1 0 1/20 1/5 0 5/4 1/6*X1+X2

S3 0 0 0 1 ¼ 0 1 25/4 -1*X2+X2

Zj 0 0 -2 3/2 2 0 35/2

Cj-Zj 4 6 4 0 0 0

Observamos el Zj más alejado del 0 por los números negativos nuevamente y vemos que es la columna X3, y como los demás son 0 el pivote es 1

Ingresa la variable X3 y sale S3.

Iteración 3

Cj 4 6 2 0 0 0

VB X1 X2 X3 S1 S2 S3 Bj

X1 4 1 0 0 3/10 1/5 0 5/2

X2 6 0 1 0 1/20 1/5 0 5/4

X3 2 0 0 1 ¼ 0 1 25/4

Zj 0 0 0 2 2 2 30

Cj-Zj 4 6 2 0 0 0

Ya con el ultimo tablero de simplex y observado las respuestas de los valores de las variables aplicamos el método de branch and bound.

Siendo

X1 = 5/2

X2 = 5/4

X3 = 25/4

Z = 30

Implementando el método de Ramificación y acotación

Obtenemos P0

Tomamos el valor entero de X1 para ramificar P0 por lo tanto siendo 5/2 = 2+1/2, tomamos el valor de 2 para reemplazar X1.

De esta manera creamos nuevamente el modelo pero agregando la nueva restricción de X1 <= 1, y pasamos a resolver el modelo de una manera muy sencilla, reemplazando X1 = 1 en las restricciones y despejando X2 y X3 respectivamente en el susodicho caso en que una variable tenga dos posibles respuestas tomamos el valor mayor de estos o el valor entero.

Obteniendo P1

También podemos resolver el modelo con la nueva restricción por simplex para obtener a P1 pero sería un proceso más largo y tedioso.

Quedando de la siguiente

...