ALGORITMO DE RAMIFICACIÓN Y ACOTAMIENTO

Este método se aplica para obtener soluciones enteras.

x≤ ⟦a ⟧ x≥ ⟦a ⟧+1

⟦−3,5 ⟧=−4

⟦−3,8 ⟧=−4

⟦−3,2 ⟧=−4

⟦2,5 ⟧=2

⟦2,8 ⟧=2

⟦2,1 ⟧=2

La parte entera es el número que no excede al número dado.

En esta técnica al maximizar encontramos el menor valor, y

Al minimizar encontramos el mayor valor.

ALGORITMO DE BRANCH AND BOUND (RAMIFICACIÓN Y ACOTAMIENTO)

Es un algoritmo diseñado para la resolución de modelos de programación entera, sin embargo, es muy frecuente que la naturaleza del problema nos indique que las variables son enteras o binarias. Su operatoria consiste en resolver este como si fuese un modelo de programación lineal y luego generar cotas en caso que al menos una variable de decisión adopte un valor fraccionario. El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que favorecen la obtención de valores enteros para las variables de decisión.

En este contexto resolver el modelo lineal asociado a un modelo de programación entera se conoce frecuentemente como resolver la relajación continua del modelo entero.

EJERCICIO 1

MAXIMIZAR

Z=3 X1+4 X2

2 X1+X2≤62 X1+3 X2≤9X i≥0 ;enteros

- 0 +- 0 +- 0 +- 0 +- 0 +- 0 +

DESARROLLO

2 X1+X2≤6X y

0 63 0

2 X1+3 X2≤9

x y

0 39/2 0

C= (3, 3/2)

Resolver las ecuaciones por eliminación:

(-1) 2 X1+X2=6 2 X1+3 X2=9

- 2 X1−X2=−6 2 X1+3 X2=9

2 X2=3

X2=32X2=1,5 Z=3 X1+4 X2 Z=12,75

Solución óptima o problema relajado

SOLUCIÓN ENTERA Z=12; X1=0 X2=3

Z=12,75X1=2,25X2=3,2

Z=9X1=3X2=0

Z=12,8X1=2X2=1,7

Z=12,5X1=1,5X2=2

Z=10X1=2X2=1

InfactibleZ=12,2X1=1X2=2,3

Z=10X1=1X2=2

Z=12X1=0X2=3

X1≤2 X1≥3

X2≤1 X2≥2

X1≤1 X1≥2

X2≤2 X2≥3

Cotas

EJERCICIO 2

MINIMIZAR

2 X1+X2≤6 X1≤2,52 X1+3 X2≤9 X1≤3

X1≤2

X2≤1

X2=1X1=2

2 X1+X2≤6 X1≤22 X1+3 X2≤9 X1≤1,5

X1≤2

X2≥2

X2=2X1=1,5

2 X1+X2≤6 X2≤42 X1+3 X2≤9 X2≤2,3

X1≤2

X2≥2

X1≤1

X1=1X2=2,3

2 X1+X2≤6 X2≤22 X1+3 X2≤9 X2≤1,7

X1≤2X1=2X2=1,7

2 X1+X2≤6 X2≤0X2=02 X1+3 X2≤9 X2≤1

X1≥3

X1=3

INFACTIBLE

2 X1+X2≤6 X2≤22 X1+3 X2≤9 X2≤1,7

X1≤2

X2≥2

X1≥2

X1=2X2=1

2 X1+X2≤6 X1≤22 X1+3 X2≤9 X1≤1,5

X1≤2

X2≥2

X1≤1

X2≤2

X2=2

2 X1+X2≤6 X1≤1,52 X1+3 X2≤9 X1≤0

X1≤2

X2≥2

X1≤1

X2≤3

X2=3

Z=−5 X1−8 X2

X1+X2≤65 X1+9 X2≤45X i≥0 ;enteros

X1+X2≤6X1=6X2=6

5 X1+9 X2≤45

X Y0 59 0

−5 X1−5 X2≤−30 5 X1+9 X2≤45

4 X2≤15

X2≤3,75

X1+3,75≤6X1≤2,25

Z=−41,25

SOLUCIÓN Z=−40 X1=0 X2=5

Z=−39X1=3X2=3

Z=−41X1=1,8X2=4

Z=41,25X1=2,25X2=3,75

Z=−40,2X1=1X2=4,4

No factible

Z=−37X1=1X2=4

Z=−40X1=0X2=5

X1+X2≤6 X1≤35 X1+9 X2≤45X1≤3,6

X2≤3X1≤3

X1+X2≤6 X1≤25 X1+9 X2≤45X1≤1,8

X2≥4X1≥1,8

X1+X2≤6 X2≤55 X1+9 X2≤45X2≤4,4

X2≥4X1≤1X1=1X2≤4,4

X1+X2≤6 X2≤45 X1+9 X2≤45X2≤3,89

X2≥4X1≥2X1=1X2=4

No Factible

X2≤3 X2≥4

X1≥2X1≤1

X2≤4 X2≥5

X1+X2≤6 X2≤25 X1+9 X2≤45X2≤1,8

X1≤1X2≤4X2=4X1≤1

X1+X2≤6 X2≤15 X1+9 X2≤45X2≤0

X1≤1X2≥5X2=5X1=0