Metodologia De Bifurcacion

Metodología de Bifurcación y Acotación

El método de bifurcación y acotación resuelve el PPLEM mediante una secuencia de PPL que se obtiene relajando las condiciones de integralidad e incluyendo restricciones adicionales.

El número de restricciones adicionales aumenta a medida que el método progresa. Estas restricciones separan la región factible en subregiones factibles complementarias.

Inicialmente se fijan cotas inferiores y superiores de la solución óptima. La estrategia de bifurcación disminuye la cota superior y aumenta la inferior. La diferencia de ambas es una medida de la proximidad de la solución actual a la óptima, si ésta existe.

Cuando se minimiza, se puede encontrar una cota inferior relajando las restricciones de integralidad del problema original y resolviendo el PPL resultante. De la misma forma, el valor de la función objetivo para cualquier solución del problema inicial es una cota superior del valor óptimo.

Este método puede parar debido a tres razones:

1. El problema actual no es factible.

2. La solución actual satisface las condiciones de integralidad.

3. La cota inferior obtenida es mayor que la superior actual.

Una bifurcación se aborta por infactibilidad, integralidad o acotación

Para resolver un PPLEM se tienen las siguientes etapas:

 Etapa 1: Iniciación. Fijar una cota superior (∞) y una inferior (-∞) a la solución óptima. Resolver el PPLEM relajando las condiciones de integralidad. Si este problema es infactible, el original también lo es y no hay solución. Si la solución es entera, es óptima. En otro caso, la cota inferior se actualiza con el valor de la solución óptima obtenida.

 Etapa 2: Bifurcación. Usando una variable candidata a entera xk que no es entera, se generan dos problemas, por bifurcación, a partir del original, tal como sigue. Si el valor de la variable xk es a.b, donde a y b son sus partes entera y fraccional, respectivamente, el primer problema bifurcado es el original relajado con la restricción xk ≤ a, y el segundo, el original relajado con la restricción complementaria xk ≥ a + 1. Estos problemas se sitúan en una lista de procesado y se consideran secuencialmente o en paralelo para su resolución.

 Etapa 3: Solución. Resolver el problema siguiente en la lista de procesado

 Etapa 4: Actualización de cotas. Si la solución del problema actual es entera y el correspondiente valor de su función objetivo es menor que la cota superior en curso, se actualiza ésta a éste y se almacena el problema como candidato a óptimo. En otro caso, si el valor de la función objetivo está entre ambas cotas, se actualiza la cota inferior con dicho valor, y se procede a bifurcar añadiendo los dos problemas a la lista de procesado.

 Etapa 5: Corte. Si la solución suministrada por el problema en curso es entera, no es posible la bifurcación, por lo que se aborta la bifurcación debido a la integralidad de la solución. Si la solución no es entera y el valor de la función objetivo es mayor que la cota superior actual, no se puede mejorar la solución por esa rama, por lo que se aborta el proceso por esa rama, debido a acotación. Si el problema en curso no es factible, no es posible continuar por esa rama, por lo que se aborta el proceso, debido a infactibilidad.

 Etapa 6: Optimalidad. Si la lista de procesado está no vacía se continúa con la Etapa 3. En otro caso, el proceso concluye. Si hay un candidato a óptimo, éste da la solución. En otro caso, el problema es infactible. Este algoritmo revuelve la solución óptima o informa sobre su no existencia en la Etapa 1 ó la 6.

Cualquier variable que no sea entera puede ser candidata para la bifurcación. La elección de cuál elegir es un problema que debe resolverse basándose en el conocimiento sobre el problema de que se trate. Los problemas de la lista de procesado pueden procesarse mediante las estrategias de “anchura primero” o “altura primero” o una mezcla de ambas. La figura 2 muestra ambas alternativas.

Figura 2. Estrategias de (a) “búsqueda en anchura”, y (b) “búsqueda en profundidad”.

Una estrategia de “altura primero” genera rápidamente problemas restringidos que generalmente suministran buenas cotas superior e inferior. Además suministra rápidamente problemas infactibles y, por tanto, el abortado de las ramas. Una estrategia de “anchura primero” procesa problemas muy parecidos, lo cual puede explotarse convenientemente. Las técnicas de computación paralela pueden explotarse con ambas estrategias.

Ejemplos

Minimizar

sujeto a

La región factible es la que se muestra en la figura 3.

Figura

...