8/20/2019 Algoritmoderamificacinyacotamiento 150722042553 Lva1 App6892

1/8

 0 +

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, sinembargo, es muy recuente que la naturaleza del problema nos indique que las variablesson enteras o binarias. !u operatoria consiste en resolver este como si uese un modelode programación lineal y luego generar cotas en caso que al menos una variable dedecisión adopte un valor raccionario. El algoritmo genera en orma recursiva cotas "orestricciones adicionales# que avorecen la obtención de valores enteros para las variablesde decisión.

En este contexto resolver el modelo lineal asociado a un modelo de programación entera

se conoce recuentemente como resolver la rela$ación continua del modelo entero.EJERCICIO 1

MAXIMIZAR

  Z =3 X 1+4 X 2

8/20/2019 Algoritmoderamificacinyacotamiento 150722042553 Lva1 App6892

2/8

2 X 1+ X 

2≤6

2 X 1+3 X 

2≤ 9

 X i≥ 0; enteros

DESARROLLO

2 X 1+ X 

2≤6

X y0 %3 &

 

2 X 1+3 X 

2≤ 9

8/20/2019 Algoritmoderamificacinyacotamiento 150722042553 Lva1 App6892

3/8

x y0 '9!

&

() "', '*+#

esolver las ecuaciones por eliminación-

"/# 2 X 1+ X 2=6

  2 X 1+3 X 2=9

  2  X 1− X 2=−6

  2 X 1+3 X 2=9

2 X 2=3

 X 2=3

2 X 

2=1,5   Z =3 X 1+4 X 2   Z =12,75

!olución óptima o problema rela$ado

X1X1

X2 X2

X1 X1

X2 X2

8/20/2019 Algoritmoderamificacinyacotamiento 150722042553 Lva1 App6892

4/8

 

INFACTIBLE

!0L1(234 E45EA 6)/+7 8/)& 8+)'

C"#$%

2 X 1+ X 

2≤6  

 X 1

≤2

2 X 1+3 X 

2≤ 9

 X 1

≤1,5

2 X 1+ X 

2≤6  

 X 1

≤2

2 X 1+3 X 

2≤ 9

 X 1

≤1,5

 X 1

≤2

2 X 1+ X 

2≤6  

 X 1

≤1,5

2 X 1+3 X 

2≤ 9

 X 1

≤0

 X 1

≤2

2 X 1+ X 

2≤6  

 X 2

≤ 4

2 X 1+3 X 

2≤ 9

 X 2

≤2,3

2 X 1+ X 

2≤6  

 X 1

≤2,5

2  X 1+3  X 

2≤9

 X 1≤3

2 X 1+ X 

2≤6  

 X 2

≤0   X 2=0

2 X 1+3 X 

2≤ 9

 X ≤1

2 X 1+ X 

2≤6  

 X 2

≤2

2 X 1+3 X 

2≤ 9

 X ≤1 7

8/20/2019 Algoritmoderamificacinyacotamiento 150722042553 Lva1 App6892

5/8

EJERCICIO !

MINIMIZAR

Z =−5 X 1−8 X 

2

 X 1+ X 

2≤ 6

5 X 1+9 X 

2≤ 45

 X i≥ 0; enteros

 X 1+ X 2 ≤ 6

 X 1=6

 X 2=6

5 X 1+9 X 

2≤ 45

8/20/2019 Algoritmoderamificacinyacotamiento 150722042553 Lva1 App6892

6/8

X Y0 99 &

−5 X 1−5 X 

2≤−30

 5 X 

1+9 X 

2≤ 45

 4 X 

2≤ 15

 X 2

≤3,75

 X 1+3,75 ≤6

 X 1

≤2,25

Z =−41,25

8/20/2019 Algoritmoderamificacinyacotamiento 150722042553 Lva1 App6892

7/8

SOLUCIÓN  Z =−40 X 1=0 X 2=5

Z =41,25

=

Z =−41

 X   =1,8

Z =−39

=

X2≥X2≤

Z =−40

 X   =0

Z =−37

=

Z =−40,2

=

 No facti

X1≥X1≤

X2≤ X2≥

 X 1+ X 

2≤6

  X 

1≤3

5 X 1+9 X 

2≤ 45

 X 1+ X 

2≤6

  X 

1≤2

5 X 1+9 X 

2≤ 45

No

 X 1+ X 

2≤ 6  

 X 2

≤ 4

5 X 1+9 X 

2≤ 45

 X 2

≤3,89

 X 1+ X 

2≤ 6  

 X 2

≤5

5 X 1+9 X 

2≤ 45

 X 2

≤ 4,4

 X 1+ X 

2≤ 6  

 X 2

≤1

5 X 1+9 X 

2≤ 45   X 

2≤0

 X 1+ X 

2≤ 6  

 X 2

≤2

5 X 1+9 X 

2≤ 45

 X 2

≤1,8

8/20/2019 Algoritmoderamificacinyacotamiento 150722042553 Lva1 App6892

8/8