Programación entera: Bifurcación y planos de corte

Tema 6: Programación entera: Bifurcación y planos de corte.

Objetivos del tema:

 Introducir las principales técnicas de programación entera

 Introducir el método de bifurcación y acotación (Brach and Bound, B&B) para problemas de Programación Entera

 Analizar las diferentes estrategias que pueden utilizarse en cada una de las etapas del algoritmo B&B

 Utilizar el algoritmo B&B para resolver algunos problemas de Programación Lineal Entera Puros, Mixtos y Binarios

 Presentar algunas de las técnicas de preprocesamiento para problemas de Programación Lineal Entera Binaria

 Presentar un procedimiento para la generación de planos de corte en problemas de Programación Lineal Entera Binarios

 Introducir el método de los planos de corte de Gomoroy para Programación Lineal Entera

1

A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL

Problemas de Programación Lineal Entera

Tal y como se vio en el Tema 2 en muchos problemas de programación lineal sólo tienen sentido aquellas soluciones de la región factible en las que todas o algunas de las variables de decisión toman valores enteros. Este tipo de problemas se denominan en general Problemas de Programación Lineal Entera (PPLE). En concreto:

• Si todas las variables del problema son enteras se habla de PPLE Pura.

• Si sólo algunas son enteras y las restantes son continuas se habla de PPLE Mixta.

• Si todas las variables enteras son binarias (0/1) el problema se denomina PPLE Binaria.

En ingeniería los problemas más frecuentes son los PPLE Mixta. Estos problemas proporcionan un marco de modelado flexible y eficiente para formular y resolver muchos problemas de ingeniería. Un PPLE Mixta general se formula en forma estándar como:

n

Minimizar z   c j x j

j 1

sujeto a

n

 aij x j  bi

j 1

; i  1, 2,..., m

x j  0 ;

j  1, 2, ..., n

x j  

; j  1, 2, ..., I

; I  n

Este tema se proporciona una introducción a los principales algoritmos para obtener la solución a este tipo de problemas. En concreto, se

estudian los métodos siguientes:

• Método de bifurcación y acotación: La solución al PPLE original se obtiene resolviendo una secuencia ordenada de PPLs que se obtienen relajando las restricciones de integralidad y añadiendo restricciones adicionales.

• Método de los planos de corte: En esta técnica, se resuelve el problema original relajado en el que se incluyen restricciones adicionales, denominadas cortes de Gomoroy, que reducen la región factible sin excluir soluciones que cumplen las condiciones de integralidad.

2

A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL

Método de bifurcación y acotación para un PPLE Mixta.

El método de bifurcación y acotación (B&B, de Branch and Bound) resuelve un PPLE resolviendo una secuencia ordenada de PPLs que se obtienen relajando las restricciones de integralidad y añadiendo restricciones adicionales. El número de restricciones adicionales crece a medida que el método B&B progresa. Estas restricciones permiten separar la región factible en subregiones complementarias.

El método B&B establece inicialmente cotas inferior y superior del valor óptimo de la función objetivo. El mecanismo de bifurcación aumenta progresivamente el valor de la cota inferior y disminuye también progresivamente el valor de la cota superior. La diferencia entre estas cotas es una medida de la proximidad de la solución actual a la óptima, si ésta existe.

Al minimizar, se obtiene una cota inferior de la solución óptima relajando las restricciones de integralidad del PPLE inicial y resolviendo el PPL resultante. Además, el valor de la función objetivo para cualquier solución del PPLE original es una cota superior de la solución óptima. De manera análoga, al maximizar, la solución del PPL relajado es una cota superior para el óptimo y cualquier solución del PPLE original es una cota inferior de la solución óptima.

A continuación se enumeran los pasos del algoritmo B&B para un PPLE Mixta:

Paso 1: Iniciación

1.1 Se establece una cota superior () y una cota inferior (−) de la solución óptima.

1.2 Se resuelve el PPLE Mixta inicial relajando las restricciones de integralidad.

1.2.a Si el problema relajado es infactible, el original también lo es y no hay solución.

1.2.b Si la solución obtenida satisface las condiciones de integralidad, es óptima.

1.2.c En cualquier otro caso, se actualiza el valor de la cota correspondiente con el valor de la función objetivo resultante.

Paso 2: Bifurcación

2.1 Empleando la variable xk que ha de ser entera y no lo es, se generan mediante bifurcación dos problemas. Si el valor de la variable que ha de ser entera xk es a.b, donde a y b son sus partes entera y fraccional respectivamente, los problemas fruto de la bifurcación son los siguientes.

2.1.a El primer problema es el PPLE relajado al que se la añade la restricción xk≤a

2.1.b El segundo es el PPLE relajado al que se le añade la restricción xk≥a+1

2.2

Estos problemas se colocan ordenadamente en una lista de problemas a procesar que son resueltos secuencialmente o en

paralelo. Obsérvese que la técnica de bifurcación propuesta cubre completamente el espacio de soluciones.

3

A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL

Paso 3: Solución

3.1 Se resuelve el siguiente problema en la lista de problemas a procesar.

Paso 4: Acotación

4.1 Si

...