Lista 2 - Solução de Problemas de Programação Inteira pelo Método BB (EaD)

Prévia do material em texto

LISTA 2 
 
Centro Federal de Educação Tecnológica Celso Suckow da Fonseca 
Departamento de Engenharia de Produção 
Disciplina: Pesquisa Operacional II 
Tema: Solução de PPIs pelo método Branch-and-Bound 
Professor: Ormeu Coelho da Silva Júnior 
 
1 – Resolva o PPI abaixo pelo método de BB, selecionando a variável “mais fracionária” para 
ramificação em cada iteração, e as seguintes estratégias de busca para seleção dos nodos: 
1 2
1 2
1 2
1 2
max
s.a.:
2 2 3
7 3 22
,
z x x
x x
x x
x x 
 
  
 
¢
 (P1) 
(a) de busca em profundidade. 
(b) de busca em largura. 
(c) Ilustre a região de viável antes e após a inserção de todas as disjunções. 
(d) Calcule o gap (relativo) de Programação Linear. 
(e) Calcule o gap dual (relativo) em cada iteração, considerando a solução do item (a). 
(f) Calcule o gap dual (relativo) em cada iteração, considerando a solução do item (b). 
 
2 – Resolva o PPI abaixo pelo método de BB, selecionando a variável “mais fracionária” para 
ramificação em cada iteração, e as seguintes estratégias de busca para seleção dos nodos: 
1 2
1 2
1 2
1 2
max 2 3
s.a.:
5 7 35
4 9 36
,
z x x
x x
x x
x x 
 
 
 
¢
 (P2) 
(a) de busca em profundidade com backtracking; 
(b) de busca em largura. 
(c) Ilustre a região de viável antes e após a inserção de todas as disjunções. 
(d) Calcule o gap (relativo) de Programação Linear. 
(e) Calcule o gap dual (relativo) em cada iteração, considerando a solução do item (a). 
(f) Calcule o gap dual (relativo) em cada iteração, considerando a solução do item (b). 
 
3 – Resolva o PPI abaixo pelo método de BB, utilizando a variável “mais fracionária” para 
selecionar a variável a ser ramificada e as seguintes estratégias de busca: 
1 2
1 2
1 2
1 2
min 5 4
s.a.:
3 2 5
2 3 7
,
z x x
x x
x x
x x 
 
 
 
¢
 (P3) 
(a) de busca em profundidade com backtracking. 
(b) de busca em largura. 
(c) Ilustre a região de viável antes e após a inserção de todas as disjunções. 
(d) Calcule o gap (relativo) de Programação Linear. 
(e) Calcule o gap dual (relativo) em cada iteração, considerando a solução do item (a). 
(f) Calcule o gap dual (relativo) em cada iteração, considerando a solução do item (b).