ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

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


Enviado por   •  8 de Septiembre de 2013  •  6.736 Palabras (27 Páginas)  •  845 Visitas

Página 1 de 27

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

...

Descargar como (para miembros actualizados)  txt (40.9 Kb)  
Leer 26 páginas más »
Disponible sólo en Clubensayos.com