Cuadro Comparativo De Ramifificacion Y Acotamiento
Enviado por karina280 • 11 de Junio de 2014 • 386 Palabras (2 Páginas) • 511 Visitas
Ramificación y acotamientos
Ramificación Acotamientos
Resuelven problemas de programación entera Resuelven problemas de programación entera
encuentran la solución óptima para un
problema de programación entera mediante la enumeración eficiente de los puntos
en la región factible encuentran la solución óptima para un
problema de programación entera mediante la enumeración eficiente de los puntos
en la región factible
Subdivide un espacio de soluciones en subespecies mutuamente excluyentes. las restricciones
de acotamiento estén en la ''vecindad inmediata'' del óptimo continuo del SP0
incrementará las posibilidades de producir "buenas" soluciones enteras
Las ramas
asociadas se definen por las restricciones x1 3 y x1 4, donde x1 se denomina
variable de ramificación. el SP1 es el mismo que el SP0 con la restricción
adicional de acotamiento superior,. Así, podemos aplicar el método simplex
de acotamiento superior para resolver el problema
La solución óptima de la programación lineal entera
debe encontrarse en el SP1 o en el SP2.
Las nuevas restricciones x1 3 y x1 4 son mutuamente excluyentes, SP1 y
SP2 deben tratarse como dos problemas de programación lineal separados Las nuevas restricciones x1 3 y x1 4 son mutuamente excluyentes, SP1 y
SP2 deben tratarse como dos problemas de programación lineal separados
Determinan una solución factible entera en una etapa temprana de los cálculos
es crucial para incrementar la eficiencia del algoritmo Determinar una solución factible entera en una etapa temprana de los cálculos
es crucial para incrementar la eficiencia del algoritmo
asume que es un modelo de Programación Lineal.
X, es la variable de ramificación
Ejemplos de y acotamientos
max –z 21x1+11x2
7x1+4x2<=13
El
...