Branch And Bound

Universidad Católica de la Santísima Concepción.
Facultad de Ingeniería
Investigación de Operaciones II

Tarea N°1:
“Técnicas de Branch and Bound y Preprocesamiento”

Nombre: Michelle Bizama
Profesor: Dr. Cristian Oliva San Martín.

Índice.
Introducción……………………………………………………………………………………………………………………………….. 3
Desarrollo
* Ejercicio 1 ………………………………………………………………………………………………………………………. 5
* Ejercicio 2……………………………………………………………………………………………………………………….. 9
* Ejercicio 3………….………………………………………………………………………………………………………….. 13
* Ejercicio 4……………………………………………………………………………………………………………………. 15

Introducción.
A través de la presente tarea se desarrollarán una serie de ejercicios relacionados con las técnicas de Branch and Bound y preprocesamiento.
La técnica deBranch and Bound se aplica mayoritariamente para resolver problemas de optimización. Esta técnica, conocida también como técnica de “Ramificación y poda”, se interpreta como un árbol de soluciones, donde cada rama lleva a una posible solución posterior a la actual. La característica de esta técnica, es que el algoritmo se encarga de detectar en qué ramificación las soluciones dadas ya no estánsiendo óptimas, para “podar” esa rama del árbol y no continuar malgastando recursos y procesos en casos que se alejan de la solución óptima.
La idea básica de este método es responder a la pregunta ¿Se puede dividir el problema en problemas más pequeños para obtener la solución”?. Esta técnica se utiliza para resolver problemas tipo enteros, por lo que la solución es del mismo tipo. Se sabe que esmuy difícil resolver esta situación, por lo que el problema se relaja, es decir, el problema entero se convierte en uno del tipo continuo (Xi ≥0, ∀i) y las soluciones dejan de ser puntos y se transforman en una “región factible”. Así, con este método se pretende ir reduciendo este espacio de soluciones factibles, agregando nuevas restricciones y obteniendo problemas más pequeños y más fáciles deresolver. Encontramos la solución óptima cuando la solución óptima de los problemas relajados cumple con las restricciones del problema original. De forma más formal se puede escribir: Considere el problema z = max{cx : x ∈ S}.Proposición: Sea S = S1 ∪ S2 ∪ . . . ∪ SK una descomposición de S, en conjuntos más pequeños. Sea zk = max{cx : x ∈ Sk} para k = 1, . . . ,K. Entonces z = maxk=1,..., K{zk}.Además se debe tener en cuenta el tema de las cotas. La siguiente proposición lo explica: Sea S = S1 ∪ S2 ∪ . . . ∪ SK una descomposición de S en conjunto más pequeños. Sean zk = max{cx : x ∈ Sk} para k = 1, . . . ,K.. Sea Ẑk una cota superior de zk y Ẕk una cota inferior de zk .Entonces:
Ẑ = maxk{ Ẑk } es una cota superior para z
Ẕ = maxk{ Ẕk } es una cota inferior para z.
En otras palabras,si la solución del problema relajado es solución entera, entonces las soluciones son iguales.
Finalmente, existen 3 situaciones en las que el árbol se puede podar:
* Optimalidad: Cuando la CS = CI.
* Cota: La mejor CI para el problema original es mayor o igual que la CS de un problema específico.
* Infactible: El conjunto es vacío.


Imagen de un árbol de Branch and Bound.En P1 se muestra la restricción X1≤1, la cual sirve para reducir el espacio de solución factible, además de las restricciones no negatividad.
Además se muestran los valores que toman X1 y X2 en cada ramificación y los valores de z de cada subproblema.

El otro tema abordado en esta tarea es la técnica de preprocesamiento que se utiliza simplemente para reducir el tamaño del problema, eliminandorestricciones y variables que son redundantes y mejorando las cotas.

Ejercicio 1.

Sea el siguiente problema de programación lineal entera. Resuelva utilizando el algoritmo Branch and Bound. Usted puede utilizar cualquier programa computacional para obtener la solución de la relajación de programación lineal.

Max 2x1 + 3x2...