Slides_BranchandBound
51 pág.

Slides_BranchandBound


DisciplinaPesquisa Operacional I7.024 materiais44.968 seguidores
Pré-visualização4 páginas
as varia´veis sa\u2dco inteiras (\u2208 IN).
Dificuldades no arredondamento - 1
a viabilidade na\u2dco e´ mantida
maximizar z = x1 + 2x2
sujeito a` \u2212x1 + x2 \u2264 2, 5
x1 + x2 \u2264 3, 5
x1 \u2208 IN x2 \u2208 IN
I o´timo cont´\u131nuo:
x1 = 0, 5; x2 = 3 e z = 6, 5
I o´timo inteiro:
x1 = 1; x2 = 2 e z = 5
Dificuldades no arredondamento - 1
a viabilidade na\u2dco e´ mantida
maximizar z = x1 + 2x2
sujeito a` \u2212x1 + x2 \u2264 2, 5
x1 + x2 \u2264 3, 5
x1 \u2208 IN x2 \u2208 IN
I o´timo cont´\u131nuo:
x1 = 0, 5; x2 = 3 e z = 6, 5
I o´timo inteiro:
x1 = 1; x2 = 2 e z = 5
Dificuldades no arredondamento - 2
o´timo inteiro longe do o´timo arredondado
maximizar z = x1 + 5x2
sujeito a` x1 + 10x2 \u2264 20
x1 \u2264 2
x1 \u2208 IN x2 \u2208 IN
I o´timo cont´\u131nuo:
x1 = 2; x2 = 9/5 e z = 11
I o´timo inteiro:
x1 = 0; x2 = 2 e z = 10
Dificuldades no arredondamento - 2
o´timo inteiro longe do o´timo arredondado
maximizar z = x1 + 5x2
sujeito a` x1 + 10x2 \u2264 20
x1 \u2264 2
x1 \u2208 IN x2 \u2208 IN
I o´timo cont´\u131nuo:
x1 = 2; x2 = 9/5 e z = 11
I o´timo inteiro:
x1 = 0; x2 = 2 e z = 10
Construc¸a\u2dco de uma a´rvore de pesquisa
Caracter´\u131sticas dos ve´rtices da a´rvore
I ve´rtice aberto
I ve´rtice fechado
I limite superior (LSk)
I limite inferior (LIk)
I Subconjunto de soluc¸o\u2dces (Sk)
Construc¸a\u2dco do algoritmo
I LA: lista de ve´rtices aberto
I LF : lista de ve´rtices fechado
I LS : limite superior do problema
I LI : limite inferior do problema
Construc¸a\u2dco de uma a´rvore de pesquisa
Caracter´\u131sticas dos ve´rtices da a´rvore
I ve´rtice aberto
I ve´rtice fechado
I limite superior (LSk)
I limite inferior (LIk)
I Subconjunto de soluc¸o\u2dces (Sk)
Construc¸a\u2dco do algoritmo
I LA: lista de ve´rtices aberto
I LF : lista de ve´rtices fechado
I LS : limite superior do problema
I LI : limite inferior do problema
Inicializac¸a\u2dco
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = \u2205: lista fechado e´ vazia;
3. LS = LS0 =\u221e; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´\u131sticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o\u2dces na\u2dco via´veis do problema;
6. s = \u2205 melhor soluc¸a\u2dco encontrada;
Inicializac¸a\u2dco
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = \u2205: lista fechado e´ vazia;
3. LS = LS0 =\u221e; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´\u131sticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o\u2dces na\u2dco via´veis do problema;
6. s = \u2205 melhor soluc¸a\u2dco encontrada;
Inicializac¸a\u2dco
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = \u2205: lista fechado e´ vazia;
3. LS = LS0 =\u221e; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´\u131sticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o\u2dces na\u2dco via´veis do problema;
6. s = \u2205 melhor soluc¸a\u2dco encontrada;
Inicializac¸a\u2dco
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = \u2205: lista fechado e´ vazia;
3. LS = LS0 =\u221e; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´\u131sticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o\u2dces na\u2dco via´veis do problema;
6. s = \u2205 melhor soluc¸a\u2dco encontrada;
Inicializac¸a\u2dco
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = \u2205: lista fechado e´ vazia;
3. LS = LS0 =\u221e; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´\u131sticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o\u2dces na\u2dco via´veis do problema;
6. s = \u2205 melhor soluc¸a\u2dco encontrada;
Inicializac¸a\u2dco
Fac¸a:
1. LA = {0}: colocar o ve´rice 0 na lista aberto;
2. LF = \u2205: lista fechado e´ vazia;
3. LS = LS0 =\u221e; LI0 = 0;
4. LI = 0 ou calculado pelas caracter´\u131sticas do problema;
5. S0 = conjunto de todo o universo de valores para as varia´veis.
Isto inclui as soluc¸o\u2dces na\u2dco via´veis do problema;
6. s = \u2205 melhor soluc¸a\u2dco encontrada;
Regra de parada
teste
I se LI \u2265 LS ou LA = \u2205: PARE
I se s = \u2205: o problema na\u2dco tem soluc¸a\u2dco;
I sena\u2dco: s e´ a soluc¸a\u2dco o´tima;
I sena\u2dco: va´ para iterac¸a\u2dco;
Regra de parada
teste
I se LI \u2265 LS ou LA = \u2205: PARE
I se s = \u2205: o problema na\u2dco tem soluc¸a\u2dco;
I sena\u2dco: s e´ a soluc¸a\u2dco o´tima;
I sena\u2dco: va´ para iterac¸a\u2dco;
Iterac¸a\u2dco - primeira parte
branch
Na lista aberto LA, selecione um ve´rtice k (por exemplo, o ve´ritice
de menor limite inferior LIk , neste caso, fac¸a LI = max{LI , LIk});
1. retire o ve´rtice k de LA e coloque-o em LF ;
2. utilizando uma regra apropriada, subdivida o subconjunto Sk
de soluc¸o\u2dces representadas pelo ve´rtice k em novos
subconjuntos Sk \u2032 gerando assim os novos ve´rtices k
\u2032 para a
a´rvore de pesquisa;
Iterac¸a\u2dco - primeira parte
branch
Na lista aberto LA, selecione um ve´rtice k (por exemplo, o ve´ritice
de menor limite inferior LIk , neste caso, fac¸a LI = max{LI , LIk});
1. retire o ve´rtice k de LA e coloque-o em LF ;
2. utilizando uma regra apropriada, subdivida o subconjunto Sk
de soluc¸o\u2dces representadas pelo ve´rtice k em novos
subconjuntos Sk \u2032 gerando assim os novos ve´rtices k
\u2032 para a
a´rvore de pesquisa;
Iterac¸a\u2dco - segunda parte
bound
Para cada novo ve´ritice k \u2032 gerado, verifique se existe a
possibilidade de soluc¸o\u2dces via´veis no ve´rtice;
I se sim:
1. calcule o limite inferior LIk\u2032 do ve´rtice;
2. verifique se LIk\u2032 < LS
I se sim: verifique se uma soluc¸a\u2dco via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a\u2dco encontrada;
(ii) LS = LIk\u2032 ;
(iii) transferir todos os ve´rtices k \u2032\u2032 de LA cujo LIk\u2032\u2032 \u2265 LS para
LF ;
- sena\u2dco: colocar o ve´rtice na LA;
I sena\u2dco: colocar o ve´rtice k \u2032 na LF ;
I sena\u2dco: colocar o ve´rtice k \u2032 na lista fechado LF ;
Iterac¸a\u2dco - segunda parte
bound
Para cada novo ve´ritice k \u2032 gerado, verifique se existe a
possibilidade de soluc¸o\u2dces via´veis no ve´rtice;
I se sim:
1. calcule o limite inferior LIk\u2032 do ve´rtice;
2. verifique se LIk\u2032 < LS
I se sim: verifique se uma soluc¸a\u2dco via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a\u2dco encontrada;
(ii) LS = LIk\u2032 ;
(iii) transferir todos os ve´rtices k \u2032\u2032 de LA cujo LIk\u2032\u2032 \u2265 LS para
LF ;
- sena\u2dco: colocar o ve´rtice na LA;
I sena\u2dco: colocar o ve´rtice k \u2032 na LF ;
I sena\u2dco: colocar o ve´rtice k \u2032 na lista fechado LF ;
Iterac¸a\u2dco - segunda parte
bound
Para cada novo ve´ritice k \u2032 gerado, verifique se existe a
possibilidade de soluc¸o\u2dces via´veis no ve´rtice;
I se sim:
1. calcule o limite inferior LIk\u2032 do ve´rtice;
2. verifique se LIk\u2032 < LS
I se sim: verifique se uma soluc¸a\u2dco via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a\u2dco encontrada;
(ii) LS = LIk\u2032 ;
(iii) transferir todos os ve´rtices k \u2032\u2032 de LA cujo LIk\u2032\u2032 \u2265 LS para
LF ;
- sena\u2dco: colocar o ve´rtice na LA;
I sena\u2dco: colocar o ve´rtice k \u2032 na LF ;
I sena\u2dco: colocar o ve´rtice k \u2032 na lista fechado LF ;
Iterac¸a\u2dco - segunda parte
bound
Para cada novo ve´ritice k \u2032 gerado, verifique se existe a
possibilidade de soluc¸o\u2dces via´veis no ve´rtice;
I se sim:
1. calcule o limite inferior LIk\u2032 do ve´rtice;
2. verifique se LIk\u2032 < LS
I se sim: verifique se uma soluc¸a\u2dco via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a\u2dco encontrada;
(ii) LS = LIk\u2032 ;
(iii) transferir todos os ve´rtices k \u2032\u2032 de LA cujo LIk\u2032\u2032 \u2265 LS para
LF ;
- sena\u2dco: colocar o ve´rtice na LA;
I sena\u2dco: colocar o ve´rtice k \u2032 na LF ;
I sena\u2dco: colocar o ve´rtice k \u2032 na lista fechado LF ;
Iterac¸a\u2dco - segunda parte
bound
Para cada novo ve´ritice k \u2032 gerado, verifique se existe a
possibilidade de soluc¸o\u2dces via´veis no ve´rtice;
I se sim:
1. calcule o limite inferior LIk\u2032 do ve´rtice;
2. verifique se LIk\u2032 < LS
I se sim: verifique se uma soluc¸a\u2dco via´vel foi encontrada;
- se sim:
(i) s = nova soluc¸a\u2dco encontrada;
(ii) LS = LIk\u2032 ;
(iii) transferir todos os ve´rtices k \u2032\u2032 de LA cujo LIk\u2032\u2032 \u2265 LS para
LF ;
- sena\u2dco: colocar o ve´rtice na LA;
I sena\u2dco: colocar o ve´rtice k \u2032 na LF ;
I sena\u2dco: colocar o ve´rtice k \u2032 na lista fechado LF ;
Iterac¸a\u2dco - segunda parte
bound
Para cada novo ve´ritice k \u2032 gerado, verifique se existe a
possibilidade de soluc¸o\u2dces via´veis no ve´rtice;