Slides_BranchandBound
51 pág.

Slides_BranchandBound


DisciplinaPesquisa Operacional I7.085 materiais45.044 seguidores
Pré-visualização4 páginas
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 ;
Observac¸o\u2dces
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Observac¸o\u2dces
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Observac¸o\u2dces
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Observac¸o\u2dces
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Observac¸o\u2dces
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Observac¸o\u2dces
performace de um algoritmo branch-and-bound
1. branch: uma maneira eficiente de selecionar o ve´rtice para
dividir o seu subconjunto
2. bound: uma maneira de se obter uma bom limite inferior
maneiras principais para selecionar um ve´ritice
1. pelo menor limite inferior
2. pela largura da a´rvore
3. pela profundidade da a´rvore
Problema de minimizac¸a\u2dco
modelo
minimizar z =
n\u2211
j=1
cjxj
sujeito a`
n\u2211
j=1
aijxj \u2265 bi \u2200i = 1, . . . ,m
xj \u2208 {0, 1} \u2200j = 1, . . . , n.
caracter´\u131sticas
I ordenac¸a\u2dco no vetor c
c1 \u2264 c2 \u2264 . . . \u2264 cn
I vetor c todo possitivo
se cj , fazer xj = (1\u2212 x \u2032j ), onde x \u2032j \u2208 {0, 1}
Linear Inteira =\u21d2 Programac¸a\u2dco Linear Bina´ria
Todo problema de Programac¸a\u2dco Linear Inteira pode ser
transformado em Programac¸a\u2dco Linear Bina´ria. Por exemplo, se
0 \u2264 x \u2264 u, onde 2n\u22121 < u < 2n
enta\u2dco cada valor via´vel de x pode ser expresso como:
x =
n\u2211
i=0
2iyi , com yi \u2208 {0, 1}
Assim a varia´vel x pode ser substituida em todo o problema por
esta soma envolvendo (n + 1) varia´veis bina´rias.
Algoritmo Branch-and-bound para PLIB - Balas [1]
Notac¸a\u2dco
I soluc¸a\u2dco parcial: subconjunto de soluc¸o\u2dces onde se conhece o
valor de k primeiras varia´veis do conjunto total das n varia´veis
do problema (x1, . . . , xk\u22121, xk , xk+1, . . . , xn);
I soluc¸a\u2dco completa: soluc¸a\u2dco onde se conhece o valor de todas
as n varia´veis do problema;
I conclusa\u2dco de uma soluc¸a\u2dco parcial: e´ uma soluc¸a\u2dco completa
partindo de uma soluc¸a\u2dco parcial
(x1, . . . , xk\u22121, xk , xk+1, . . . , xn);
I z\u2217k : valor o´timo da func¸a\u2dco objetivo quando a soluc¸a\u2dco onde a s
k primeiras varia´veis foram fixadas e as n \u2212 k varia´veis
restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for
soluc¸a\u2dco via´vel do problema.
Algoritmo Branch-and-bound para PLIB - Balas [1]
Notac¸a\u2dco
I soluc¸a\u2dco parcial: subconjunto de soluc¸o\u2dces onde se conhece o
valor de k primeiras varia´veis do conjunto total das n varia´veis
do problema (x1, . . . , xk\u22121, xk , xk+1, . . . , xn);
I soluc¸a\u2dco completa: soluc¸a\u2dco onde se conhece o valor de todas
as n varia´veis do problema;
I conclusa\u2dco de uma soluc¸a\u2dco parcial: e´ uma soluc¸a\u2dco completa
partindo de uma soluc¸a\u2dco parcial
(x1, . . . , xk\u22121, xk , xk+1, . . . , xn);
I z\u2217k : valor o´timo da func¸a\u2dco objetivo quando a soluc¸a\u2dco onde a s
k primeiras varia´veis foram fixadas e as n \u2212 k varia´veis
restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for
soluc¸a\u2dco via´vel do problema.
Algoritmo Branch-and-bound para PLIB - Balas [1]
Notac¸a\u2dco
I soluc¸a\u2dco parcial: subconjunto de soluc¸o\u2dces onde se conhece o
valor de k primeiras varia´veis do conjunto total das n varia´veis
do problema (x1, . . . , xk\u22121, xk , xk+1, . . . , xn);
I soluc¸a\u2dco completa: soluc¸a\u2dco onde se conhece o valor de todas
as n varia´veis do problema;
I conclusa\u2dco de uma soluc¸a\u2dco parcial: e´ uma soluc¸a\u2dco completa
partindo de uma soluc¸a\u2dco parcial
(x1, . . . , xk\u22121, xk , xk+1, . . . , xn);
I z\u2217k : valor o´timo da func¸a\u2dco objetivo quando a soluc¸a\u2dco onde a s
k primeiras varia´veis foram fixadas e as n \u2212 k varia´veis
restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for
soluc¸a\u2dco via´vel do problema.
Algoritmo Branch-and-bound para PLIB - Balas [1]
Notac¸a\u2dco
I soluc¸a\u2dco parcial: subconjunto de soluc¸o\u2dces onde se conhece o
valor de k primeiras varia´veis do conjunto total das n varia´veis
do problema (x1, . . . , xk\u22121, xk , xk+1, . . . , xn);
I soluc¸a\u2dco completa: soluc¸a\u2dco onde se conhece o valor de todas
as n varia´veis do problema;
I conclusa\u2dco de uma soluc¸a\u2dco parcial: e´ uma soluc¸a\u2dco completa
partindo de uma soluc¸a\u2dco parcial
(x1, . . . , xk\u22121, xk , xk+1, . . . , xn);
I z\u2217k : valor o´timo da func¸a\u2dco objetivo quando a soluc¸a\u2dco onde a s
k primeiras varia´veis foram fixadas e as n \u2212 k varia´veis
restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for
soluc¸a\u2dco via´vel do problema.
Construc¸a\u2dco da a´rvore de pesquisa
Caracter´\u131sticas da a´rvore de pesquisa
1. ve´rtice k: representa uma soluc¸a\u2dco parcial onde as k primeiras
varia´veis foram fixadas
2. branch: criar dois novos ve´rtices onde xk+1 = 0 e xk+1 = 1
3. limite iferior de cada ve´rtice e´ calculado:
LIk =
\uf8f1\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f2\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f3
k\u2211
j=1
cjxj se xk = 1 (ou se k = 0 ou k = n);
k\u22121\u2211
j=1
cjxj + ck+1 se xk = 0.
Construc¸a\u2dco da a´rvore de pesquisa
Caracter´\u131sticas da a´rvore de pesquisa
1. ve´rtice k: representa uma soluc¸a\u2dco parcial onde as k primeiras
varia´veis foram fixadas
2. branch: criar dois novos ve´rtices onde xk+1 = 0 e xk+1 = 1
3. limite iferior de cada ve´rtice e´ calculado:
LIk =
\uf8f1\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f2\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f3
k\u2211
j=1
cjxj se xk = 1 (ou se k = 0 ou k = n);
k\u22121\u2211
j=1
cjxj + ck+1 se xk = 0.
Construc¸a\u2dco da a´rvore de pesquisa
Caracter´\u131sticas da a´rvore de pesquisa
1. ve´rtice k: representa uma soluc¸a\u2dco parcial onde as k primeiras
varia´veis foram fixadas
2. branch: criar dois novos ve´rtices onde xk+1 = 0 e xk+1 = 1
3. limite iferior de cada ve´rtice e´ calculado:
LIk =
\uf8f1\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f2\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f3
k\u2211
j=1
cjxj se xk = 1 (ou se k = 0 ou k = n);
k\u22121\u2211
j=1
cjxj + ck+1 se xk = 0.
Construc¸a\u2dco da a´rvore de pesquisa
outras caracter´\u131sticas
1. soluc¸a\u2dco via´vel no ve´rtice k: verificar se cada restric¸a\u2dco do
problema pode ser satisfeita. O ve´rtice k da a´rvore na\u2dco tem
soluc¸a\u2dco via´vel se
k\u2211
j=1
aij +
n\u2211
j=k+1
max{aij , 0} < bi
Exemplo
minimizar z = 3x1 + 5x2 + 6x3 + 9x4 + 10x5 + 10x6
sujeito a` \u22122x1 + 6x2 \u2212 3x3 + 4x4 + x5 \u2212 2x6 \u2265 2
\u22125x1 \u2212 3x2 + x3 + 3x4 \u2212 2x5 + x6 \u2265 \u22122
5x1 \u2212 x2 + 4x3 \u2212 2x4 + 2x5 \u2212 x6 \u2265 3
xj \u2208 {0, 1} \u2200j = 1, . . . , 6.
Definic¸a\u2dco
Modelo
minimizar z =
n\u2211
j=1
cjxj
sujeito a`
n\u2211
j=1
aijxj \u2265 bi \u2200i = 1, . . . , n
xj \u2208 IN \u2200j = 1, . . . , k(k < n),
xj \u2265 0 \u2200j = k + 1, . . . , n.
Quando i = n, este problema e´ uma problema de Programac¸a\u2dco
Linear Inteira.
Algoritmo branch-and-bound para PLIM
Origem
Proposto por Dakin [2]