Cuadro Comparativo De Ramifificacion Y Acotamiento

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 dominio de puntos factibles para el modelo de Programación Lineal asociado es el área demarcada converde. Dicho modelo tiene valor óptimo igual a

39

, con

X1=1,9

y

X2=0

. Esto corresponde ala relajación contínua del PLE y nos proporciona una cota superior del valor óptimo de dicho problema.Además, claramente la solución de la relación contínua no satisface la condición de integralidad delmodelo de PLE. Finalmente, en el gráfico anterior se han marcado con

azul

todas aquellascombinaciones que satisfacen las restricciones del modelo de PLE. Claramente esto corresponde a unsubdominio del problema lineal asociado lo que justifica que la relajación continua nos entrega una cotasuperior del valor

...