Question

O método Branch-and-Bound (B&B) baseia-se na idéia de desenvolver uma enumeração inteligente das soluções candidatas à solução ótima inteira de um problema. Neste algoritmo apenas uma fração das soluções factíveis é realmente examinada. O termo branch refere-se ao fato de que o método efetua partições no espaço das soluções e o termo bound ressalta que a prova da otimalidade da solução utiliza-se de limites calculados ao longo da enumeração.

Fonte:Disponível em:Acesso.14.Set.2018

Neste contexto, descreva de forma sucinta os cinco passo do algoritmo Branch-and-Bound, não sendo necessária a utilização de pseudo código

Answer 1

Resposta:

l problema maximização

II - O termo branch refere-se ao fato de que o método efetua partições no espaço das soluções

III - O termo bound ressalta que a prova da otimalidade da solução utiliza-se de limites calculados ao longo da enumeração.

llll problema minimização.

Answer 2

Resposta:

O algoritmo de Branch and Bound é composto por 5 etapas,

conforme descrito abaixo

1. Resolver o problema como se fosse um problema de PL com as

variáveis relaxadas (ignorando a condição de integralidade). Conferir

a solução ótima calculada e observar se as variáveis que deveriam

ser inteiras são, de fato, inteiras. Caso as variáveis sejam inteiras, o

problema foi resolvido. Caso contrário, passar à próxima etapa.

2. Se na etapa anterior houver uma variável não inteira entre dois

números inteiros consecutivos e não negativos (i x i 1 2 < <j ), dois

novos modelos de programação inteira se formam, acrescido ao

problema original uma restrição do tipo x i j £ 1 , ou do tipo x i j ³ 2 .

3. Se alguma das primeiras aproximações ainda apresentar uma

solução não inteira, o problema de PI resultante por essa primeira

aproximação torna-se candidato a uma ramificação adicional.

4. Se o problema for de maximização, a ramificação continua até

ser obtida uma primeira aproximação inteira (que é uma candidata

à solução ótima do problema original, e o valor da função objetivo

relativa às variáveis encontradas torna-se o limite inferior para o

problema, o que significa que modelos cujas primeiras aproximações

apresentem valores da função objetivo menores que o limite inferior

devem ser descartados.

5. Se o problema for de minimização, o procedimento é o

mesmo. A diferença é que os limites a serem utilizados devem ser

superiores, e não inferiores. Logo, o valor da função objetivo a partir

da primeira solução inteira torna-se o limite superior do problema,

e devem ser descartados os modelos com valor de função objetivo

maiores ao limite

Explicação: