Programación Lineal Entera: Resolución con Branch and Bound, Cortes de Gomory y Algoritmos, Exámenes de Matemáticas

¡Descarga Programación Lineal Entera: Resolución con Branch and Bound, Cortes de Gomory y Algoritmos y más Exámenes en PDF de Matemáticas solo en Docsity! PROGRAMACIÓN LINEAL ENTERA 6-9-2007 1. Considerar el problema entero siguiente: max 81.6x1 + 112.2x2 + 71.2x3 + 60.88x4 s.a.: 5x1 + 7x2 + 4x3 + 3x4 ≤ 14 x1, x2 ∈ {0, 1, 2}, x3 ∈ {0, 1, 2, 3}, x4 ∈ {0, 1, 2, 3, 4} Resolverlo utilizando el método de Branch and Bound, con las siguientes reglas: • Elegir, como variable de ramificación, la más cercana a 0.5 y, en caso de empate, aquella con un coeficiente mayor en la función objetivo. • Usar DFS como estrategia para elegir el nudo a explorar y, en caso de empate, explorar primero la rama más arriba y a la izquierda del árbol. Explicar los pasos seguidos y dibujar el árbol resultante. 2. Considerar el problema entero siguiente: max 5 x1 + 6 x2 + 7 x3 s.a.: -2x1 + x2 + x3 ≤ 6 x1 + 2x2 + x3 ≤ 4 -2x1 + 2x2 + 4x3 ≤ 12 x1, x2, x3 ≥ 0 y enteras. La tabla óptima de la relajación lineal es: Base x1 x2 x3 h1 h2 h3 LD z 0 6 0 0 17 3 1 3 80 3 h1 0 2 0 1 1 −12 4 x1 1 1 0 0 2 3 −1 6 2 3 x3 0 1 1 0 1 3 1 6 10 3 Resolver el problema utilizando cortes de Gomory. En cada iteración, encontrar todos los posibles cortes y añadir sólo el que tenga el menor término independiente. 3. Considerar el problema 0-1: max 10x1 + 4x2 + 12x3 + 8x4 + 9x5 s.a.: 3x1 + x2 + 4x3 + x5 ≤ 4 x1 + x2 = 1 x3 + x4 = 1 x1, x2, x3, x4, x5 ∈ {0, 1}. Construir la relajación lagrangiana de este problema cuando se dualiza la restricción mochila. Utilizar esta relajación para resolver el problema entero original mediante el método del subgradiente. Tomar como multiplicador inicial λ0 = 0 y usar µk = 0.5 k para calcular la longitud del paso.