Flashcard FC241309
Quais são os passos essenciais do método Branch-and-Bound para resolver um problema de programação inteira binária?
Programação Linear
CESGRANRIO · 2010
Quais são os passos essenciais do método Branch-and-Bound para resolver um problema de programação inteira binária?
Mostrar resposta e comentário
Resposta
Relaxação LP; resolver; se solução fracionária, fatiar (branch) sobre uma variável fracionária criando subproblemas com x_j=0 e x_j=1; usar os bounds obtidos para podar nós cujo bound não supera a melhor solução inteira encontrada.Explicação e exemplo:
Passos:
- Fazer a relaxação LP (permitir 0≤x≤1) e resolver para obter um bound.
- Se a solução for inteira, é ótima.
- Se for fracionária, escolher uma variável fracionária e criar dois ramos com x_j=0 e x_j=1 (branching).
- Resolver os nós (ou relaxações) para obter bounds; podar qualquer nó cujo bound não possa superar a melhor solução inteira conhecida (pruning).
Exemplo:
Considere o problema
\(\max\;10x_1+8x_2+6x_3\)
sujeito a
\(\;3x_1+2x_2+2x_3\le 4,\quad x_i\in\{0,1\}.\)
Relaxação LP (0≤x_i≤1) → solução: \(x_1=1,\;x_2=0.5,\;x_3=0\) com bound \(10+8\cdot0.5=14\).
Como \(x_2\) é fracionário, faz‑se branching:
- Nodo A: \(x_2=0\). Relaxação dá solução fracionária \(x_1=1,\;x_3=0.5\) → bound = \(10+6\cdot0.5=13\) (≤14) → pode ser podado.
- Nodo B: \(x_2=1\). Combinando com \(x_3=1\) cabe na capacidade → solução inteira \(x_2=1,x_3=1\) com valor \(8+6=14\).
Como encontramos solução inteira com valor igual ao melhor bound, ela é ótima e os nós restantes podem ser podados.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/236125
Conteúdo do catálogo FC Concursos · Atualizado em