Acin112 s8 Resuelta

ACIN112
Guía de Ejercicios: Ejemplos de Programación Entera

Solucionario
EJEMPLO 1
Considere el siguiente problema que busca maximizar los beneficios en lafabricación de 2 productos.
Max 4x1 + 6x2
s.a. 8x1 + 6x2 ≤ 24

2x1 + 82 ≤ 24
+
x1 , x2 ∈ Ζ
Determine el valor y solución óptima del problema original Branch & Bound (B&B), indicar gráfico en cada
subproblema, empezar a ramificar por x2 de ser posible, en caso de no seguir ramificando por algún nodo
explicar por qué.
Desarrollo:
Se relaja el problema (cambiando las variables a continuas) y se resuelve el problema con el método gráfico.
El punto óptimo de este problema se encuentra en el vértice 𝑥𝑥1 = 0,92 y 𝑥𝑥2 = 2,77 con una función
objetivo de 20,3.
Dado que la solución tiene variables fraccionales, se debe ramificar el problema por la variable fraccionaria que más
impacta en la función objetivo.
Maximizar 4X1 + 6X2
4X1= 4*0.92 =3.68

6X2= 6*2.77 =16.62 Se debe ramificar por X2
Desarrollo:
El punto óptimo de este problema se encuentra en el vértice 𝑥𝑥1 = 0,92 y 𝑥𝑥2 = 2,77 con una función
objetivo de 20,3.
Dado que la solución tiene variables fraccionales, se debe ramificar el problema por la variable fraccionaria que más
impacta en la función objetivo.
Maximizar 4X1 + 6X2
4X1= 4*0.92 =3.68

6X2= 6*2.77 =16.62 Se debe ramificar por X2
Al ramificar por x2 se tienen dos nuevos problemas:
Problema 2: con la nueva

restricción de x2 ≤ 2
Problema 3: con la nueva

restricción de x2 ≥ 3
El árbol de exploración es el siguiente:

Problema 2 ( x2 ≤ 2 ):
Se resuelve el problema con el método gráfico.
El punto óptimo de este problema se encuentra en el vértice 𝑥𝑥1 = 1,5 y 𝑥𝑥2 = 2 con una función objetivo
de 18.
Problema 3 ( x2 ≥ 3 ):
Se resuelve el problema con el método gráfico.

El punto óptimo de este problema se encuentra en el vértice 𝑥𝑥1 = 0𝑥𝑥 y =
2 3 con una función objetivo de 18.
Dado que la solución del problema 3 tiene variables enteras y es la misma del problema 2, no es necesario
seguir ramificando el problema 2, ya que al seguir ramificando se encontrará la misma o peor solución.
Por lo que la solución óptima del problema es de 18 con 𝑥𝑥1 = 0 y 𝑥𝑥2 = 3

EJEMPLO 2
Determine la solución óptima entera y de la relajación lineal del siguiente problemaen forma gráfica. Reporte
tanto el valor óptimo como las coordenadas óptimas de las variables de decisión.
Max. 5x1 + 8x2

s.a. x1 + x2 ≤ 6
5x1 + 9x2 ≤ 45
+
x1 , x2 ∈ Ζ
Desarrollo:
Problema 1:
El punto óptimo de este problema se encuentra en el vértice
𝑥𝑥1 = 2,25 y 𝑥𝑥2 = 3,75 con una función objetivo de 41,25, como las variables no son enteras se debe
dividir.
Problema 2 ( x1 ≤ 2 ):
𝑥𝑥1 = 2 y 𝑥𝑥2 = 3,89 con una función objetivo de 41,12.
Problema 3 ( x1 ≥ 3 ):
𝑥𝑥1 = 3 y 𝑥𝑥2 = 3 con una función objetivo de 39.
Dado que en P2 la solución obtenida es mayor a la de P3 se debe seguir ramificando.

Problema 4 ( x1 ≤ 2 , x2 ≤ 3 ):
Problema 5 ( x1 ≤ 2 , x2 ≥ 4 ):
𝑥𝑥1 = 1,8 y 𝑥𝑥2 = 4 con una función objetivo de 41.
Dado que la solución obtenida en P5 es la mejor y se tienen variables fraccionales se debe continuar dividiendo
el problema.
Problema 6 ( x1 ≤ 2 , x2 ≥ 4 , x1 ≤ 1 ):
𝑥𝑥1 = 1 y 𝑥𝑥2 = 4,44 con una función objetivo de 40,52.
Problema 7 ( x1 ≤ 2 , x2 ≥ 4 ,x1 ≥ 2 )
Infactible.
Problema 8 ( x1 ≤ 2 , x2 ≥ 4 , x1 ≤ 1 ,):
𝑥𝑥1 = 1 y 𝑥𝑥2 = 4 con una función objetivo de 39

Problema 9 ( x1 ≤ 2 , x2 ≥ 4 , x1 ≤ 1 ,):
Dado que el problema 9 tiene la función objetivo más alta con variables enteras es la solución óptima.

El óptimo entero es de 40 con x1 = 0 y x2 = 5
El óptimo relejado (primera solución) es de 41,25 con x1 = 2,25 y x2 = 3,75

EJEMPLO 3
Dado el siguiente árbol del algoritmo de B&B para un problema de mochila con función objetivo
max 8x1 +11x2 + 6x3 + 4x4
a) ¿Está completo el árbol o falta explorar algún subproblema? Justifique.
b) Suponga que solo se han generado los nodos 1, 2, 3, 4 y 5. Indique cuál sería el error que se cometería
al utilizar la solución entera del nodo 4 en lugar de seguir explorando el árbol y llegar al óptimo.
Desarrollo:
Primero se evalúan los valores de cada problema en la función objetivo:

a) Debe ramificarse el problema P9, ya que tiene una mejor solución (función objetivo) que la actual entera
(P6).
b) Si solo se tienen los problemas 1, 2, 3, 4 y 5 se tendría una cota de 18 ≤ FO ≤ 21,8 y se cometería un error
de 3,8, ya que como la solución de P5 es mejor al seguir ramificando en P5 se podría obtener una solución
entera con función objetivo igual
a 21,8 (o un valor menor).
EJEMPLO 4
Al resolver parcialmente el siguiente problema de programación lineal entera mixta.
Max -5x1 − 8x2
s.a. x1 + x2 ≤ 6
5x1 + 9x2 ≤ 45
X1, x2, ∈ Ζ
+
Se ha obtenido el siguiente árbol de ramificación y acotamiento (Branch & Bound).
a) ¿Entré qué valores se encuentra el valor óptimo del problema entero?
b) ¿Qué correspondería hacer a continuación?

Desarrollo:
a) Dado que es un problema de minimización, las soluciones factibles (variables enteras) entregan el
valor de la cota superior, y los nodos por ramificar dan las cotas inferiores.
En este ejercicio, el problema P1 tiene una solución con variables enteras por lo que entregará la cota
superior, y ahora se debe buscar el problema que tenga la mejor solución, pero con variables fraccionables,
el cual es P3.
por lo que en el problema anterior en P1 se obtuvo una solución factible con variables enteras, por lo que
será la cota superior y en P3 como es un nodo para ramificar nos entregará la cota inferior.
−40, 55 ≤ F.O. ≤ −39
b) El nodo P3 tiene una solución mejor a la incumbente (-39) por lo que se debe
ramificar generando dos nuevos subproblemas, P5 con la x2 ≤ 4 y P6 con las restricciones x2 ≥ 5
Bibliografía
1. Taha, H., Martínez del Campo Varela, G., & González Pozo, V. (2004). Investigación de operaciones
(Séptima edición). México: Pearson Educación.
2. Beneventti, D. (2019). Apunte Docente. Universidad Andrés Bello. Santiago.
3. Hillier, F. S. y Lieberman G J. (1994). Introducción a la Investigación de Operaciones, Mc Graw Hill.

Acin112 s8 Resuelta

Cargado por

Copyright:

Formatos disponibles

Acin112 s8 Resuelta

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Acin112 s8 Resuelta

Cargado por

Copyright:

Formatos disponibles

ACIN112

Guía de Ejercicios: Ejemplos de Programación Entera

Max 4x1 + 6x2

s.a. 8x1 + 6x2 ≤ 24

Maximizar 4X1 + 6X2

4X1= 4*0.92 =3.68

Maximizar 4X1 + 6X2

4X1= 4*0.92 =3.68

Problema 2: con la nueva

Problema 3: con la nueva

El árbol de exploración es el siguiente:

Se resuelve el problema con el método gráfico.

Se resuelve el problema con el método gráfico.

Por lo que la solución óptima del problema es de 18 con 𝑥𝑥1 = 0 y 𝑥𝑥2 = 3

El árbol de exploración es el siguiente:

Max. 5x1 + 8x2

El punto óptimo de este problema se encuentra en el vértice

El punto óptimo de este problema se encuentra en el vértice

𝑥𝑥1 = 2 y 𝑥𝑥2 = 3,89 con una función objetivo de 41,12.

𝑥𝑥1 = 3 y 𝑥𝑥2 = 3 con una función objetivo de 39.

Dado que en P2 la solución obtenida es mayor a la de P3 se debe seguir ramificando.

El punto óptimo de este problema se encuentra en el vértice

𝑥𝑥1 = 2 y 𝑥𝑥2 = 3 con una función objetivo de 34.

𝑥𝑥1 = 1,8 y 𝑥𝑥2 = 4 con una función objetivo de 41.

El punto óptimo de este problema se encuentra en el vértice

𝑥𝑥1 = 1 y 𝑥𝑥2 = 4,44 con una función objetivo de 40,52.

El punto óptimo de este problema se encuentra en el vértice

𝑥𝑥1 = 1 y 𝑥𝑥2 = 4 con una función objetivo de 39

El punto óptimo de este problema se encuentra en el vértice

𝑥𝑥1 = 0 y 𝑥𝑥2 = 5 con una función objetivo de 40.

El árbol de exploración es el siguiente:

El óptimo relejado (primera solución) es de 41,25 con x1 = 2,25 y x2 = 3,75

a) ¿Está completo el árbol o falta explorar algún subproblema? Justifique.

Primero se evalúan los valores de cada problema en la función objetivo:

Se ha obtenido el siguiente árbol de ramificación y acotamiento (Branch & Bound).

a) ¿Entré qué valores se encuentra el valor óptimo del problema entero?

b) ¿Qué correspondería hacer a continuación?

−40, 55 ≤ F.O. ≤ −39

2. Beneventti, D. (2019). Apunte Docente. Universidad Andrés Bello. Santiago.

3. Hillier, F. S. y Lieberman G J. (1994). Introducción a la Investigación de Operaciones, Mc Graw Hill.

También podría gustarte