View
120
Download
1
Category
Preview:
Citation preview
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 1/22
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 2/22
El Algoritmo de Radicación yAcotamiento ( o de branch and bound)
comienza con unarelajación del problema (no considerar restricciones de integralidad) y construyeun árbol
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 3/22
con soluciones enteras particionando elconjunto de soluciones factibles de
modo de descartar solucionesfraccionarias. Sin embargo, este solohecho de descomponer nos puedellevar a un problema inmanejable por lo
que debemos podar el arbol demanera inteligente.
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 4/22
En este momento será más convenienteexplicar los fundamentos del algoritmo
de ramificar y acotar (R y A), por mediode un ejemplo numérico
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 5/22
Consideremos el siguiente problema deProgramación lineal Entera:
Max z = 5×1 + 4×2Sujeto a
x1 + x2 <=5
10×1 + 6×2 <=45 x1, x2 >= 0 y entero
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 6/22
El procedimiento de Ramificar y Acotar se basa en tratar solo con el problemaprogramación lineal. Como la soluciónóptima (x1 = 3,75, x2 = 1,25 y z = 23,75)pero no satisface la necesidad devalores enteros, el algoritmo de R y Aexige “modificar” el espacio desoluciones lineales de forma tal que nospermita identificar, finalmente, paraconseguir la solución óptima entera
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 7/22
Primero seleccionaremos una de las variablescuyo valor corriente en la solución óptima nocumple el requisito de valor entero.Seleccionando x1=3,75 arbitrariamente,observamos que la región ( 3 < x1 < 4 ) delespacio de soluciones lineales, no puedeincluir ninguna espacio solución factibleentera. Entonces podemos modificar elespacio de soluciones lineales eliminando estaregión no prometedora, lo que, en realidad, esequivalente a reemplazar el espacio originalpor dos espacios los PL1 y PL2, definidos de lamanera siguiente:
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 8/22
1. Espacio PL1 = espacio PLO + (x1 <= 3)2 . Espacio PL2 = espacio PLO + (x1 >= 4)
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 9/22
los espacios PL1 y PL2 en forma grafica. Seve que los dos espacios contienen losmismos puntos enteros factibles del modelo
PLE. Esto significa que, desde el punto devista del problema original de PLE, tratar con PL1 y PL2 es igual que tratar con eloriginal PLO. La diferencia principal es quela selección de las nuevas restricciones e
acotamiento ( x1 >= 3 y x1 <= 4 ) mejoraranla oportunidad de forzar a los puntosextremos óptimos de PL1 y PL2 hacia lasatisfacción del requisito de valor entero
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 10/22
Además el hecho que las restriccionesde acotamiento están en la “vecindad
inmediata” del optimo continuo del PLO,incrementara las posibilidades deproducir “buenas” soluciones enteras.
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 11/22
Las nuevas restricciones x1 >= 3 y x1 <= 4son mutuamente excluyentes, PL1 y PL2
deben tratarse como dos programaslineales separados. Esta dicotomía dalugar al concepto de ramificación en elalgoritmo de R y A. En efecto, ramificar
significa subdividir un espacio desoluciones corrientes en subespaciosmutuamente excluyentes
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 12/22
Aquí vemos las ramas PL1 y PL2 y x1 llamadavariable de ramificación
Sabemos que la solución óptima entera debe
encontrarse en PL1 o PL2. Sin embargo, enausencia del espacio grafico de soluciones, notenemos manera de determinar donde puedeencontrarse la solución óptima, por lo quenuestra única opción es investigar ambos
problemas. Hacemos esto trabajando con unproblema a la vez (PL1 o PL2). Supongamosque escogemos a PL1 asociado con x1 <= 3.En efecto, debemos resolver el siguienteproblema:
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 13/22
Max z = 5×1 + 4×2
Sujeto a
x1 + x2 <=510×1 + 6×2 <=45
x1 <=3
x1, x2 >= 0
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 14/22
Como se indico antes PL1 es el mismoque el PLO con la restricción adicional
de acotamiento superior, x1 <= 3. así podemos aplicar el algoritmo primal deacotamiento superior para resolver elproblema.
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 15/22
Esto da la nueva solución óptima
X1 = 3, x2 = 2 y z = 23
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 16/22
Como esta solución satisface el requisitode valor entero, se dice que el PL1 esta
agotado, vació, lo que significa que elPL1 no puede producir ninguna soluciónmejor y no necesita investigarse mas afondo.
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 17/22
Determinar una solución factible entera enuna etapa temprana de los cálculos escrucial para incrementar la eficiencia del
algoritmo R y A. Tal solución fija una cotainferior al valor objetivo optimo, que a suvez se puede usar para descartar automáticamente cualquier subproblemano explorado (como el PL2) que no dan
mejor solución entera. En este ejemplo elPL1 produce la cota inferior z = 23. Estosignifica que cualquier solución enteramejorada debe tener el valor de z mayor 23.
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 18/22
Sin embargo, como la solución óptimadel problema PLO tiene z = 23,75 y como
todos los coeficientes de la funciónobjetivo son enteros, se infiere queningún subproblema que proceda delPLO puede producir un valor de z mejor
que 23. En consecuencia, podemosdescartar al PL2 porque no puede dar una mejor solución entera.
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 19/22
Del análisis anterior vemos que unsubproblema esta agotado si no
satisface una de las siguientescondiciones:
1. El subproblema da una solución factibleentera
2. El subproblema no puede dar una mejor solución que la mejor cota inferior disponible (valor z) del problema (Uncaso especial de esta condición es queel subproblema no tendrá ningunasolución factible en absoluto)
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 20/22
Pero si en nuestro ejemplo decidimosinvestigar PL2 primero la solución resultanteserá: x1 = 4, x2 = 0,8333, z = 23,3333. Como
x2 no es entero el PL2 debe investigarsemas a fondo creándose el PL3 y PL4 yusando las respectivas ramas x2 >=0 y x2>=1. Esto significa que
Espacio PL3 = espacio PLO + (x1 >= 4) + (x2<=0)
Espacio PL4 = espacio PLO + (x1 >= 4) + (x2>=1)
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 21/22
En este momento para escoger tressubproblemas, el PL1, PL3 y PL4. (Observenuevamente que estos tres subproblemasincluyen todas las soluciones enteras factiblesdel problema original PLE.) Si seleccionamosarbitrariamente el PL4, descubrimos que notiene solución factible y por ello esta agotado.A continuación seleccionamos el PL3 parainvestigarlo. Su solución la da x1 = 4,5, x2 = 0 y z= 22,5. Como x1 = 4,5 no es entero, creamosdos subproblemas, el PL5 y PL6 del PL4, usandolas restricciones x1 <= 4 y x1 >= 5respectivamente.
5/11/2018 Algoritmo de Ramificar y Acotar - slidepdf.com
http://slidepdf.com/reader/full/algoritmo-de-ramificar-y-acotar 22/22
Obtenemos entonces:
Espacio PL5 = espacio PLO + (x1 >= 4) + (x2
<=0) + (x1 <= 4)Espacio PL6 = espacio PLO + (x1 >= 4) + (x2
<=0) + (x1 >= 5)
Escogemos ahora el PL6, para investigarlo.Como el PL6 no tiene solución factible,esta agotado
Recommended