Calculadora de Programação Inteira (Branch and Bound)
Resolva problemas de programação linear inteira utilizando a árvore de Branch and Bound, analisando relaxações contínuas e podas de nós.
Tamanho do Problema
Objetivo
Função Objetivo — Maximizar Z
Restrições
Programação Linear Inteira e Branch and Bound: Guia Acadêmico
Entenda como o algoritmo de Ramificação e Avaliação (Branch & Bound) explora árvores de relaxação, poda ramos dominados e garante o ótimo inteiro exato sem arredondamentos heurísticos.
1. Qual problema a Programação Inteira resolve?
A Programação Linear padrão assume variáveis com valores reais contínuos. Contudo, em problemas logísticos e operacionais práticos, muitas variáveis representam unidades indivisíveis: máquinas, funcionários, lotes ou decisões booleanas (0-1). A Programação Linear Inteira (PLI) impõe a restrição xⱼ ∈ ℤ. Como o espaço viável inteiro é uma grade descontínua de pontos, métodos tradicionais de gradiente falham, exigindo buscas em árvore como o Branch and Bound.
2. O Algoritmo Branch and Bound (Dakin / Land-Doig)
Remove-se temporariamente a restrição de integralidade (admitindo xⱼ ∈ ℝ) e resolve-se o problema pelo método Simplex. O valor contínuo Z_LP funciona como limitante superior absoluto para maximização.
Se a solução contínua for inteira, o ótimo foi alcançado. Se uma variável xₖ for fracionária com valor v, criam-se dois subproblemas: Ramo Esquerdo (xₖ ≤ ⌊v⌋) e Ramo Direito (xₖ ≥ ⌈v⌉).
Resolve-se a relaxação contínua de cada novo nó. Mantém-se o registro da 'solução incumbente' (o melhor valor inteiro Z* obtido até o momento).
Poda-se um nó se: (1) For inviável, (2) Seu limitante Z_nó ≤ Z* (dominado pela incumbente), ou (3) For encontrada uma solução inteira (atualiza-se Z* se Z_nó > Z*).
3. Exemplo Acadêmico Resolvido: Programação Inteira com 2 Variáveis
Veja por que arredondar a solução contínua falha e como a árvore completa de 9 nós atinge Z* = 40.
Por que o Arredondamento Ingênuo Falha Drasticamente
A relaxação contínua resulta no ponto ótimo (x₁ = 2,25; x₂ = 3,75) com Z = 41,25. Se arredondarmos para o inteiro mais próximo (2, 4), a Restrição 2 resulta em 5(2) + 9(4) = 46 > 45 (Inviável!). Se arredondarmos para baixo (2, 3), temos Z = 34, ficando 6 unidades abaixo do ótimo real. O Branch and Bound elimina esse erro.
Evolução Completa da Árvore de Branch and Bound (Busca em Profundidade DFS)
| Tree Node | Branch Constraint | LP Relaxation Point | Objective Z | Branch & Bound Action |
|---|---|---|---|---|
| Nó 1 (Raiz) | Relaxação linear contínua (sem restrições inteiras) | x₁ = 2,25; x₂ = 3,75 | Z = 41,25 | Variável x₁ = 2,25 fracionária. Ramifica-se em x₁ ≤ 2 (Nó 2) e x₁ ≥ 3 (Nó 3). |
| Nó 2 | Adiciona-se restrição: x₁ ≤ 2 (do Nó Raiz) | x₁ = 2,00; x₂ = 35/9 ≈ 3,89 | Z = 370/9 ≈ 41,11 | Variável x₂ ≈ 3,89 fracionária. Ramifica-se em x₂ ≤ 3 (Nó 4) e x₂ ≥ 4 (Nó 5). |
| Nó 4 | Nó 2 + restrição: x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3) | x₁ = 2; x₂ = 3 | Z = 34,00 | Solução inteira! Incumbente inicial: Z* = 34 em (2, 3). |
| Nó 5 | Nó 2 + restrição: x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4) | x₁ = 1,80; x₂ = 4,00 | Z = 41,00 | Variável x₁ = 1,80 fracionária (Z = 41 > 34). Ramifica-se em x₁ ≤ 1 (Nó 6) e x₁ ≥ 2 (Nó 7). |
| Nó 6 | Nó 5 + restrição: x₁ ≤ 1 (x₁ ≤ 1, x₂ ≥ 4) | x₁ = 1,00; x₂ = 40/9 ≈ 4,44 | Z = 365/9 ≈ 40,56 | Variável x₂ ≈ 4,44 fracionária (Z ≈ 40,56 > 34). Ramifica-se em x₂ ≤ 4 (Nó 8) e x₂ ≥ 5 (Nó 9). |
| Nó 8 | Nó 6 + restrição: x₂ ≤ 4 (x₁ ≤ 1, x₂ = 4) | x₁ = 1; x₂ = 4 | Z = 37,00 | Solução inteira! Como 37 > 34, atualiza incumbente: Z* = 37 em (1, 4). |
| Nó 9 | Nó 6 + restrição: x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0) | x₁ = 0; x₂ = 5 | Z = 40,00 | Solução inteira! Como 40 > 37, atualiza incumbente: Z* = 40 em (0, 5) (ÓTIMO GLOBAL). |
| Nó 7 | Nó 5 + restrição: x₁ ≥ 2 (x₁ ≥ 2, x₂ ≥ 4) | Inviável (5(2)+9(4) = 46 > 45) | Inviável | Podado por Inviabilidade. |
| Nó 3 | Adiciona-se restrição: x₁ ≥ 3 (do Nó Raiz) | x₁ = 3; x₂ = 3 | Z = 39,00 | Solução inteira, mas Z = 39 ≤ Z* (40). Podado por Limitação Dominada. |
Solução Óptima Inteira Demonstrada
Todos os 9 nós do grafo foram devidamente explorados ou podados. Solução Ótima Inteira Global: x₁* = 0, x₂* = 5 com Máximo Z* = 40. (Resultado idêntico ao motor de cálculo).
4. Erros Comuns em Avaliações Acadêmicas
Supor que o Ótimo Inteiro é Vizinho do Ótimo Contínuo
O ponto inteiro ótimo pode situar-se distante do vértice da relaxação contínua. Sempre desenvolva a árvore em vez de testar vizinhos aleatórios.
Não Podar Nós Dominados pela Incumbente
Continuar a ramificar nós cujo limitante superior seja inferior ou igual ao melhor valor inteiro conhecido (Z ≤ Z*) causa esforço inútil.
Definição Incorreta dos Intervalos de Ramificação
Os ramos devem delimitar exatamente o intervalo inteiro: xₖ ≤ ⌊v⌋ e xₖ ≥ ⌈v⌉. O uso de desigualdades estritas exclui soluções candidatas.