Branch and Bound

Branch and BoundUnidad 1 Dr. Cristian Oliva San Martín [email protected] Departamento de Ingeniería Civil Industrial Investigación de Operaciones II Temario Dividir para Conquistar Temario Dividir para Conquistar Enumeración Implícita . .. . Entonces z = maxk =1. . .. K .Dividir para Conquistar Considere el problema z = max {cx : x ∈ S }. ∪ SK una descomposición de S en conjuntos más pequeños. ◮ Cómo podemos dividir el problema en una serie de problemas más pequeños. .. más fáciles de resolver y que uniendo la información podamos resolver el problema original? Proposición: Sea S = S1 ∪ S2 ∪ . . Sea z k = max {cx : x ∈ Sk } para k = 1.K {z k }. .. Además se ilustran las cotas superiores e inferiores de los problemas correspondientes. 27 S 13 25 S 20 20 S1 20 25 S2 15 S1 25 S2 15 . ∪ SK una descomposición de S en conjunto más pequeños. Entonces z k y z = maxk {z } es una cota inferior para z . . . .Enumeración Implícita ◮ Cómo podemos usar las cotas sobre los valores de {z k } inteligentemente? Proposición: Sea S = S1 ∪ S2 ∪ . . Ejemplo: En la figura 1 se muestra una descomposición de S en dos conjuntos S1 y S2 . Sean z k = max {cx : x ∈ Sk } para ¯k una cota superior de z k y z k una cota k = 1. .. Sea z ¯ = maxk {z ¯k } es una cota superior para z inferior de z k . K . . S se descompone en dos conjuntos S1 y S2 e ilustra las cotas inferiores y superiores de los problemas correspondientes. 27 S S 13 21 20 S1 18 26 26 S2 S1 21 21 S2 26 Figura: Podado por Cota 2 .Ejemplo 2 En la figura 2. Ejemplo 3 En la figura 3. S se descompone en dos conjuntos S1 y S2 e ilustra las cotas inferiores y superiores de los problemas correspondientes. 40 S S 13 24 S1 13 13 37 24 S2 S1 S2 37 37 Figura: Imposible podar 3 . .Tres razones que nos permiten podar el árbol ◮ Podar por optimalidad: z t = {max cx : x ∈ St } ha sido resuelto. Podar por cota: z ◮ . ¯t ≤ z .Tres razones que nos permiten podar el árbol ◮ Podar por optimalidad: z t = {max cx : x ∈ St } ha sido resuelto. ¯t ≤ z . ◮ ◮ .Tres razones que nos permiten podar el árbol ◮ Podar por optimalidad: z t = {max cx : x ∈ St } ha sido resuelto. Podar por cota: z Podar por infactibilidad: St = ∅. Branch and Bound: Un ejemplo z = max 4x1 − x2 x2 2 x ∈ Z+ ∪0 s .a 7x1 − 2x2 ≤ 14 ≤3 2x1 − 2x2 ≤ 3 . La representación óptima resultante es: ¯ = max z 59 7 1 −4 7 x3 − 7 x4 1 +7 x3 + 2 7 x4 x1 x2 + x4 −2 7 x3 + 10 7 x4 + x5 20 7 =3 23 = 7 = x1 . x4 . en la cual las restricciones de integralidad son eliminadas.Obtención de cotas Para obtener una primera cota superior. x5 ≥ 0 ¯ = 59 Se obtiene una cota superior z 7 y una solución no-entera 20 ¯ ¯ (x . x5 y se resuelve la relajación de programación lineal. 0) con valor objetivo z = 0. x4 . x3 . Existe alguna forma directa de encontrar una 1 2 7 cota inferior? Aparentemente podemos suponer que la mejor solución encontrada es (0. 3 ) . se agregan las variables de holgura x3 . x2 . . x ) = ( . Branch and Bound hasta aquí 59 7 S 0 . se necesita ramificar o dividir. dado que x ¯ 1 = S1 = S ∩ {x : x1 ≤ 20 7 . podemos dividir el problema de la siguiente forma: S1 = S ∩ {x : xj ≤ ⌊x ¯j ⌋} S2 = S ∩ {x : xj ≥ ⌈x ¯j ⌉} Siguiendo nuestro ejemplo. Cómo deberíamos Dado que z < z dividir la región factible? Una idea es seleccionar una variable que requiere ser entera pero que en la solución de programación lineal es fraccionaria. Luego. tomamos: 20 } 7 20 S2 = S ∩ {x : x1 ≥ } 7 59 7 S 0 x1 ≤ 2 S1 x1 ≥ 3 S2 .Ramificando ¯. Arbitrariamente seleccionamos S1 . .Seleccionando un problema (nodo) La lista de problemas activos (nodos) que tienen que ser examinados contiene ahora S1 y S2 . x6 ≥ 0 se tiene: ¯ z 1 = max 15 2 1 −2 x5 − 3x6 x1 x2 x3 −1 2 x5 + x6 + x6 − x5 − 5x6 x4 + 1 2 x5 + 6x6 x1 . x 2 ) = (2.Reoptimizando ◮ ◮ ◮ Cómo deberíamos resolver los programas lineales modificados sin tener que resolverlos nuevamente desde el inicio? Dado que sólo hemos añadido una restricción al programa lineal. x4 . 1 ¯ ¯ y (x 1. x2 . 2 ). x6 ≥ 0 =2 1 = 2 =1 5 = 2 ¯ con z 1 = 15 2 . x3 . x5 . y es por esta razón que se reoptimiza desde esta base utilizando el algoritmo simplex dual. Aplicando esta idea a la relajación de programación lineal de S1 y reescribiendo x1 ≤ 2 como x1 + x6 = 2. . la base óptima actual sigue siendo factible dual. Branch and Bound hasta aquí 59 7 S 0 x1 ≤ 2 15 2 S1 0 x1 ≥ 3 S2 . tomamos: 1 } 2 1 S2 = S ∩ {x : x2 ≥ } 2 S1 = S ∩ {x : x2 ≤ 59 7 S 0 x1 ≤ 2 15 2 S1 0 x1 ≥ 3 S2 x2 = 0 S3 x2 ≥ 1 S4 .Ramificando S1 no puede ser podado. Dado que x 2 = 2 . así usando la misma regla de ramificación 1 ¯ anterior creamos dos nodos S3 y S4 . .S3 y S4 . Arbitrariamente seleccionamos S2 .Seleccionando un problema (nodo) La lista de problemas activos (nodos) que tienen que ser examinados contiene ahora S2 . x7 ≥ 0 es infactible y por ello S2 se poda por infactibilidad. x4 . . x2 . x5 . x3 . x7 ≥ 0 se tiene: ¯ = max z 59 7 1 −4 7 x3 − 7 x4 2 +1 7 x3 + 7 x4 x1 x2 + x4 −2 7 x3 + 1 7 x3 10 7 x4 + x5 2 +7 x4 + x7 20 7 =3 23 = 7 1 =− 7 = x1 .Reoptimizando ◮ Aplicando el algoritmo simplex dual a la relajación de programación lineal de S2 y reescribiendo x1 ≥ 3 como x1 − x7 = 3. Branch and Bound hasta aquí 59 7 S 0 x1 ≤ 2 15 2 S1 0 x1 ≥ 3 S2 x2 = 0 S3 x2 ≥ 1 S4 . . Arbitrariamente seleccionamos S4 .Seleccionando un problema (nodo) La lista de problemas activos (nodos) que tienen que ser examinados contiene ahora S3 y S4 . z 4 = z4 = z4 = 7. 59 7 S 0 x1 ≤ 2 15 2 S1 0 x1 ≥ 3 S2 x2 = 0 S3 x2 ≥ 1 7 S4 . x2 ≥ 1 la solución ¯ ¯ óptima es: (x 1.Reoptimizando ◮ Aplicando el algoritmo simplex dual a la relajación de programación lineal de S4 = S ∩ {x : x1 ≤ 2. Como esta solución es ¯ entera. x 2 ) = (2. El nodo se poda por optimalidad. 1) con valor 7. Actualización del Branch and Bound Como la solución es entera.1). 7}.59 7 S 7 x1 ≤ 2 15 2 S1 7 x1 ≥ 3 S2 x2 = 0 S3 x2 ≥ 1 7 S4 7 . almacenar la solución correspondiente (2. actualizamos el valor de la mejor solución factible encontrada hasta aquí: z ← max {0. Seleccionando un problema (nodo) La lista de problemas activos (nodos) que tienen que ser examinados contiene ahora sólo S3 . Seleccionamos S3 . . Reoptimizando ◮ Aplicando el algoritmo simplex dual a la relajación de programación lineal de S3 = S ∩ {x : x1 ≤ 2. x2 = 0 la solución 3 ¯ ¯ óptima es: (x 1. x 2 ) = ( 2 . 59 7 S 7 x1 ≤ 2 15 2 S1 7 x1 ≥ 3 S2 x2 = 0 6 S3 x2 ≥ 1 7 S4 7 . 0) con valor 6. Actualización del Branch and Bound ¯ Como z = 7 > z 3 = 6. 59 7 S 7 x1 ≤ 2 15 2 S1 7 x1 ≥ 3 S2 x2 = 0 6 S3 x2 ≥ 1 7 S4 7 . S3 se poda (muere) por cota. no hubiera sido necesario explorar el nodo S3 . ◮ . 1) con z = 7. X2 ) = (2. Por ello.Seleccionando un problema (nodo) y Conclusiones ◮ La lista de problemas activos (nodos) que tienen que ser examinados esta vacía. Con ello. la solución óptima es (x1 . Observe que también se hubiera podido utilizar un preprocesamiento de la cota superior observando que el valor de la función objetivo debe ser entero dado que los coeficientes son enteros y las variables enteras. actualice cota primal z = z ¯i ∗ i Actualice x = x (PL) pode por optimalidad no i i generar dos subproblemas S1 y S2 i i con formulaciones P1 y P2  . Inicialización Problema inicial S con Formulación P en la lista z = −∞ Lista vacía? no ? Seleccione Problema Si con formulación P i Resuelva relajación PL de P i Cota dual z ¯ i = valor PL x i (PL)=solución PL SI -PARE. pode por cota no Si x (PL) entero. OPTIMO x ∗ ? ? si  si  si  Si P i vacío. pode por infactibilidad no ? ? ? Si z ¯ i ≤ z .Branch and Bound basado en programación lineal En la figura se presenta un flujograma de un algoritmo simple del tipo branch and bound. Documents Similar To Branch and BoundSkip carouselcarousel previouscarousel nextCoordinacion de Reles de Sobrecorrienteuploaded by HEQUISOptimizaciondeoperaciones.docuploaded by DannyMárquez230827512-Caso-4-1-Telas-y-Modas-de-Otono.docxuploaded by marcelo aguilar ochoa02 Metodos 27 Mayo 2014uploaded by Max MorenoOptimizaciondeoperaciones.docuploaded by DannyMárquezinvest. operac. 1 expo recuperacion-1.pptxuploaded by NooDLeKc KKInvestigación Operativa Iuploaded by Nilton JchMet Simplexuploaded by Alexandra Molano Rodríguez20131ILN250V2_Pauta_Certamen_N°1uploaded by José Abarca BarreraProgramacion Lineal Clase 2uploaded by Antho Durand CiriacoMétodo de la M Grande.docxuploaded by Fernanda RodriguezPpt-dual en Programacion Lineal uploaded by Rom Joaquin R2010_Matematicas_17_13uploaded by kudasai_sugoiDualidad en Programación Linealuploaded by KATYUSKA20122ILN250V3_Pauta_Certamen_1uploaded by sebastian_pfeiffer_2PROGRAMACIÓN LINAL.docxuploaded by janeth quiñonesCUESTIONARIO uploaded by Xulianna Rocano MejiaIO+1+Modulo+2uploaded by Cristian Javier Ortiz OlmosFase2 uploaded by nicoEjercicios de Programacion Lineal Resueltos Mediante El Metodo Simplexuploaded by LucyRosseCaceresQuispe07 - Programacao Linearuploaded by Antonio Adrian Martinez GavilanDIOP_U3_A1_OMBMuploaded by Don Omar Hunter ShadesProblema de rutas de vehículosuploaded by Tomas BurgosMetodo Simplexuploaded by RIGITOProgramacion Lineal usando solveruploaded by JuanGutierrezBenitez0387is1.pdfuploaded by Doufeellucky14 Sensibilidaduploaded by Deivis Rpztrabajouploaded by MercenaritoxDPL_Guíauploaded by cintriagozambranoIntro Opit iuploaded by Sebastián Cáceres GMore From Evelyn Nicole HerreraSkip carouselcarousel previouscarousel nextDiscurso 1uploaded by Evelyn Nicole HerreraDiagrama PQ ANG1uploaded by Evelyn Nicole HerreraTema 5 CC Ambientalesuploaded by Evelyn Nicole HerreraDsi Derecho Al Trabajouploaded by Evelyn Nicole HerreraEncuesta hombres.xlsxuploaded by Evelyn Nicole Herrera37313114 Calculo Del Capital de Trabajouploaded by Evelyn Nicole HerreraDiagnostico Sat Tsunami - Pacifico Suruploaded by Evelyn Nicole HerreraER Simulaciones (1)uploaded by Evelyn Nicole HerreraPsicomotricidad_infantil_factores.pptxuploaded by Evelyn Nicole HerreraAcceder Comunitario Reduploaded by Evelyn Nicole HerreraProyecciones_Hogares (1)uploaded by Evelyn Nicole HerreraProceso Fab Vidrio Ppt [Autoguardado]uploaded by Evelyn Nicole Herrera02020093uploaded by Evelyn Nicole HerreraGuia de Evaluacionuploaded by Evelyn Nicole HerreraDiscurso 2uploaded by Evelyn Nicole Herreramortalidad caninos.pdfuploaded by Evelyn Nicole Herreraproyecciones_poblacion_2014.pdfuploaded by Evelyn Nicole Herrera01 SI Informacion Clasificacionuploaded by Evelyn Nicole HerreraReported Speechuploaded by Evelyn Nicole Herrera05tecnicas de proyeccion de mercado.pdfuploaded by Evelyn Nicole HerreraManual MIDEPLAN, Preparación y presentación de proyectos de inversión.pdfuploaded by Evelyn Nicole HerreraPedagogia_Educacionuploaded by Evelyn Nicole HerreraBases Curriculares Parvularia (1).pdfuploaded by Evelyn Nicole HerreraProyecciones_Hogares.pdfuploaded by Evelyn Nicole HerreraModal Verbsuploaded by Evelyn Nicole Herrera05_TIPOS_DE_SIuploaded by Evelyn Nicole Herreratempladouploaded by Evelyn Nicole Herreraestadistica_descriptiva.pdfuploaded by Evelyn Nicole HerreraEJERCICIOS_1_EXCEL (1).xlsxuploaded by Evelyn Nicole HerreraInvestigacion de Operaciones Hillieruploaded by Evelyn Nicole HerreraMenú del pie de páginaVolver arribaAcerca deAcerca de ScribdPrensaNuestro blog¡Únase a nuestro equipo!ContáctenosRegístrese hoyInvitar amigosObsequiosAsistenciaAyuda / Preguntas frecuentesAccesibilidadAyuda de compraAdChoicesEditoresLegalTérminosPrivacidadCopyrightRedes socialesCopyright © 2018 Scribd Inc. .Buscar libros.Directorio del sitio.Idioma del sitio: English中文EspañolالعربيةPortuguês日本語DeutschFrançaisTurkceРусский языкTiếng việtJęzyk polskiBahasa indonesiaUsted está leyendo una previsualización gratuita.DescargarCerrar diálogo¿Está seguro?This action might not be possible to undo. Are you sure you want to continue?CANCELARAceptar