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

x1
+
x2

Restrições

C1
x1
+
x2
C2
x1
+
x2
Otimização Discreta e Programação Inteira Mista

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)

Passo 1: Relaxação Linear Contínua

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.

Passo 2: Verificação de Integralidade e Ramificaçã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⌉).

Passo 3: Avaliação de Subproblemas e Limitação

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).

Passo 4: Poda Sistemática de Ramos

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.

Maximizar Z = 5x₁ + 8x₂
Restrição 1: x₁ + x₂ ≤ 6
Restrição 2: 5x₁ + 9x₂ ≤ 45
Não-negatividade: x₁ ≥ 0, x₂ ≥ 0
Restrição inteira: x₁, x₂ ∈ ℤ (ambas as variáveis devem ser inteiras)

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 NodeBranch ConstraintLP Relaxation PointObjective ZBranch & Bound Action
Nó 1 (Raiz)Relaxação linear contínua (sem restrições inteiras)x₁ = 2,25; x₂ = 3,75Z = 41,25Variável x₁ = 2,25 fracionária. Ramifica-se em x₁ ≤ 2 (Nó 2) e x₁ ≥ 3 (Nó 3).
Nó 2Adiciona-se restrição: x₁ ≤ 2 (do Nó Raiz)x₁ = 2,00; x₂ = 35/9 ≈ 3,89Z = 370/9 ≈ 41,11Variável x₂ ≈ 3,89 fracionária. Ramifica-se em x₂ ≤ 3 (Nó 4) e x₂ ≥ 4 (Nó 5).
Nó 4Nó 2 + restrição: x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3)x₁ = 2; x₂ = 3Z = 34,00Solução inteira! Incumbente inicial: Z* = 34 em (2, 3).
Nó 5Nó 2 + restrição: x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4)x₁ = 1,80; x₂ = 4,00Z = 41,00Variável x₁ = 1,80 fracionária (Z = 41 > 34). Ramifica-se em x₁ ≤ 1 (Nó 6) e x₁ ≥ 2 (Nó 7).
Nó 6Nó 5 + restrição: x₁ ≤ 1 (x₁ ≤ 1, x₂ ≥ 4)x₁ = 1,00; x₂ = 40/9 ≈ 4,44Z = 365/9 ≈ 40,56Variável x₂ ≈ 4,44 fracionária (Z ≈ 40,56 > 34). Ramifica-se em x₂ ≤ 4 (Nó 8) e x₂ ≥ 5 (Nó 9).
Nó 8Nó 6 + restrição: x₂ ≤ 4 (x₁ ≤ 1, x₂ = 4)x₁ = 1; x₂ = 4Z = 37,00Solução inteira! Como 37 > 34, atualiza incumbente: Z* = 37 em (1, 4).
Nó 9Nó 6 + restrição: x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0)x₁ = 0; x₂ = 5Z = 40,00Solução inteira! Como 40 > 37, atualiza incumbente: Z* = 40 em (0, 5) (ÓTIMO GLOBAL).
Nó 7Nó 5 + restrição: x₁ ≥ 2 (x₁ ≥ 2, x₂ ≥ 4)Inviável (5(2)+9(4) = 46 > 45)InviávelPodado por Inviabilidade.
Nó 3Adiciona-se restrição: x₁ ≥ 3 (do Nó Raiz)x₁ = 3; x₂ = 3Z = 39,00Soluçã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.