Prueba 2 2014 2

Prueba Parcial #2 MDIO Semestre Primavera 2014
´
Profesor: Eduardo Alvarez
M. Ayudantes: Al´exis Ar´evalos, Felipe Ulloa.
Nombre:

Nota:

Duraci´
on: 90 min

Observaciones: La prueba debe resolverseen forma individual, no est´a permitido el uso de apuntes ni de
cualquier dispositivo electr´
onico (tel´efono m´ovil, reproductor de m´
usica, etc) salvo una calculadora b´
asica.
Ejercicio #1:Algoritmo de Planos de Cortes de Gomory I (1.00 pts)
Se tiene el siguiente problema de programaci´on entera:
min z = − 5x1 − 4x2
s.t. x1 + x2 ≤ 5
10x1 + 6x2 ≤ 45
x1 , x2 enteros.
El tableau ´
optimo de larelajaci´
on lineal de este problema es el siguiente (con s1 y s2 siendo las variables de
holgura de la primera y segunda restricci´on respectivamente):
T.0
0
1
2

xB
−z
x2
x1

z
1
0
0

x1
0
0
1

x20
1
0

s1
5/2
5/2
-3/2

s2
1/4
-1/4
1/4

rhs
95/4
5/4
15/4

Resuelva el problema utilizando el algoritmo de planos de corte de Gomory e indique cu´al es la soluci´
on y
el valor ´
optimo. Nota: en cadaiteraci´
on, genere el plano de corte utilizando aquella variable con el menor
sub-´ındice y que debiese ser entera.
Ejercicio #2: Algoritmo de Planos de Cortes de Gomory II (1.00 pts)
Se tiene elsiguiente problema de programaci´on entera:
min z = − 14x1 − 18x2
s.t.

− x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x1 , x2 enteros.

El tableau ´
optimo de la relajaci´
on lineal de este problema es el siguiente (cons1 y s2 siendo las variables
de holgura de la primera y segunda restricci´on respectivamente):

T.0
0
1
2

xB
−z
x2
x1

z
1
0
0

x1
0
0
1

x2
0
1
0

1

s1
56/11
7/22
-1/22

s2
30/11
1/22
3/22

rhs126
7/2
9/2

Resuelva el problema utilizando el algoritmo de planos de corte de Gomory e indique cu´al es la soluci´
on y
el valor ´
optimo. Nota: en cada iteraci´
on, genere el plano de corteutilizando aquella variable con el menor
sub-´ındice y que debiese ser entera.
Ejercicio #3: Algoritmo de Branch-and-Bound (2.0 pts)
Considere un problema de minimizaci´
on donde todas las variables de...