Programación Entera y Ejemplo del Algoritmo de Branch and Bound

Un modelo de Programación Entera (PE) permite abordar aplicaciones donde la solución tiene sentido si una parte o todas las decisiones toman valores restringidos a números enteros. Por ejemplo, consideremos que tenemos el siguiente problema de Programación Lineal:

problema-max-branch-and-bou

Si todas las variables restringen sus valores a números enteros, entonces estamos frente a un modelo de Programación Entera (puro). Por el contrario, si al menos algún conjunto de variables no esta acotada a adoptar valores o números enteros, se trata de un modelo de Programación Entera (Mixta).

Luego, si consideramos que estamos a un modelo de Programación Entera (puro o mixto) y resolvemos el modelo de Programación Lineal asociado (esto es, admitiendo valores continuos para las variables), estaremos obteniendo la solución de la Relajación Continua del modelo entero. Para un modelo de maximización, la relajación continua nos proporciona una cota superior del valor óptimo del modelo de Programación Entera asociado.

En el caso particular que la Relajación Continua nos proporcione una solución entera, entonces ésta será también la solución del modelo de Programación Entera asociado. En caso contrario deberemos utilizar alguna estrategia o algoritmo para obtener la solución del modelo de PE.

Una herramienta eficiente para abordar estos casos es el algoritmo de Branch & Bound. Utilizaremos un ejemplo para explicar este método:

Resuelva el siguiente modelo de Programación Entera utilizando el Algoritmo de Branch & Bound:

ple-maximizacion

grafico-problema-branch-and

El dominio de puntos factibles para el modelo de Programación Lineal asociado es el área demarcada con verde. Dicho modelo tiene valor óptimo igual a 39, con X1=1,9 y X2=0. Esto corresponde a la relajación continua del PLE y nos proporciona una cota superior del valor óptimo de dicho problema.

Además, claramente la solución de la relación continua no satisface la condición de integralidad del modelo de PLE. Finalmente, en el gráfico anterior se han marcado todas aquellas combinaciones que satisfacen las restricciones del modelo de PLE (A, D, E, B, G, F y C). Claramente esto corresponde a un subdominio del problema lineal asociado lo que justifica que la relajación continua nos entrega una cota superior del valor óptimo del PLE.

Al aplicar el algoritmo de Branch & Bound, el nodo inicial corresponde a la relajación continua y se van agregando las ramas o nodos necesarios hasta alcanzar la(s) soluciones que satisfacen las condiciones de integralidad.

ejercicio-branch-and-bound

  • P0: Corresponde a la relajación continua del PLE.
  • P1: Po + x1<=1. (solución inicial X1=1,9 aproximada al entero inferior)
  • P2: Po + x1>=2 (solución inicial X1=1,9 aproximada al entero superior). Infactible.
  • P11: P1 + x2<=1 (solución óptima X1=1 y X2=1. Valor Óptimo Z=33. Debido a que la solución satisface las restricciones de integralidad, se termina este nodo).
  • P12: P1 + x2>=2 (solución X1=5/7 y X2=2. No es solución óptima de PLE debido a que X1 es aún fraccionario. Se continua el método debido a que el Valor Óptimo Z=37 es mayor que el Valor Óptimo de P11, en caso contrario se detiene el método y P11 sería la solución óptima de PLE).
  • P121: P12 + x1<=0 (X1=0 y X2=13/4. Z=35,75. Se continua siguiendo el mismo razonamiento anterior)
  • P122: P12 + X1>=1 Infactible.
  • P1211: P121 + X2<=3 (X1=0 y X2=3. Z=33 es el valor en la función objetivo más alto obtenido para los nodos con soluciones enteras). Se agota este nodo.
  • P1212: P121 + x2>=4 Infactible.
  • Luego la Solución Óptima del PLE) es X1=0 y X2=3 con Valor Óptimo Z=33.
MaloRegularBuenoMuy BuenoExcelente (3 Votos, Promedio: 4,67 de un máximo de 5)
Cargando…

, , , ,

Sin Comentarios aun.

Comparte tus Comentarios!