Corte de Gomory

O método dos cortes de Gomory é uma técnica para resolver Programação Linear Inteira (PLI) — problemas onde algumas ou todas as variáveis de decisão têm de tomar valores inteiros.

O problema de PLI

Max  Z = c₁x₁ + c₂x₂ + ...
s.a. Ax ≤ b
     x ≥ 0
     x inteiro (ou parte de x inteiro, no caso misto — PLIM)

A relaxação linear (PL) ignora a restrição de inteireza e é resolvida primeiro pelo método simplex. A sua solução é geralmente fraccionária.

Ideia dos planos de corte

Um corte de Gomory é uma restrição linear gerada a partir de uma linha fraccionária da tabela simplex final que:

• Elimina a solução fraccionária atual
• Não elimina nenhuma solução inteira admissível

Adicionando iterativamente estes cortes e re-resolvendo (com dual simplex), a solução converge para o ótimo inteiro.

Geração de um corte

Para a variável básica x_i com valor b̄_i fraccionário na tabela simplex final, a linha tem a forma:

xi = b̄i − āi1x₁ − āi2x₂ − ...

Decompor cada coeficiente na sua parte inteira e fraccionária: b̄_i = ⌊b̄_i⌋ + f_i, ā_ij = ⌊ā_ij⌋ + f_ij

O corte de Gomory é: Σ f_ij x_j ≥ f_i (somando sobre as variáveis não-básicas).

Exemplo passo a passo

Suponha a seguinte PL relaxada:

Max  Z = 5x₁ + 4x₂
s.a. 6x₁ + 4x₂ ≤ 24
     x₁ + 2x₂ ≤ 6
     x₁, x₂ ≥ 0, inteiros

Passo 1 — Resolver a relaxação PL pelo simplex. Resultado: x₁ = 3, x₂ = 1,5, Z = 21.

Passo 2 — x₂ = 1,5 é fraccionário. Linha na tabela simplex:

x₂ = 1,5 − 0,25 s₁ + 0,75 s₂

f(b̄) = 0,5; f(ā_s1) = 0,25; f(ā_s2) = 0,75

Passo 3 — Corte gerado: 0,25 s₁ + 0,75 s₂ ≥ 0,5 (equivalente a s₁ + 3s₂ ≥ 2)

Passo 4 — Adicionar o corte ao problema e resolver com dual simplex. A nova solução ótima inteira é x₁ = 3, x₂ = 1, Z = 19.

Algoritmo completo

1. Resolver a relaxação PL
2. Se a solução é inteira → ótimo encontrado
3. Escolher uma variável básica fraccionária e gerar o corte de Gomory
4. Adicionar o corte como nova restrição
5. Resolver com dual simplex
6. Voltar ao passo 2

Notas práticas

Em problemas grandes, o número de cortes pode ser elevado e a convergência lenta. Os solvers modernos (CPLEX, Gurobi, GLPK) combinam cortes de Gomory com Branch and Bound — a abordagem branch-and-cut — que é hoje o método padrão para PLI.