Programação inteira

Um Problema de Programação Inteira é um modelo de programação linear no qual algumas ou todas as variáveis do problema pertencem ao conjunto dos números inteiros. Quando todas as variáveis são inteira o modelo é denominado programação inteira pura; caso contrário, é denominado programação inteira mista^[1].

A solução de um Problema Linear Inteiro (PLI) aparenta ser fácil, no entanto produzir soluções para programas inteiros é um problema NP-difícil.

O modelo de PLI é o seguinte^[1]:

Max (ou Min) ${\displaystyle \sum _{j=1}^{n}c_{j}x_{j}}$
sujeito a	${\displaystyle \sum _{j=1}^{n}a_{i},_{j}x_{j}\leqslant b_{i}}$	para i = 1, 2, ..., m
	${\displaystyle x_{j}\epsilon Z}$	para j = 1, 2, ..., p (≤n)
	${\displaystyle x_{j}\geq 0}$	para j = p+1, ..., n

A maneira simplista para resolver um PLI é simplesmente remover a restrição de que x é inteiro, resolver o PL correspondente (relaxamento do PPI), e depois arredondar os valores da solução relaxada obtida. Essa abordagem pode ser uma solução inviável ou muito distante do ideal.

O método Branch-and-Bound baseia-se na idéia de desenvolver uma enumeração inteligente das soluções candidatas à solução ótima inteira de um problema. 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 melhor solução utiliza-se de limites calculados ao longo da enumeração.

O método de planos de corte é um método exato que busca iterativamente refinar um conjunto viável ou função objetivo por meio de inequações lineares, chamadas cortes. Tais procedimentos são utilizados para encontrar soluções inteiras para PLI, bem como para resolver problemas gerais de otimização convexa. O uso de planos de corte para resolver PLI foi introduzido por Ralph Gomory.

Há duas razões principais para usar variáveis inteiras na modelagem de problemas como um programa linear:

1. As variáveis inteiras representam quantidades que só podem ser inteiras.
2. As variáveis inteiras representam decisões e por isso só devem assumir os valores 0 ou 1.

Estas considerações ocorrem frequentemente na prática e a PLI pode ser usada em muitos domínios de aplicação, alguns dos quais são brevemente descritos a seguir.

A programação inteira mista tem muitas aplicações na produção industrial. Um exemplo importante ocorre no planejamento de produção agrícola envolve determinar o rendimento de produção de várias culturas que podem compartilhar recursos (por exemplo, terra, trabalho, capital, sementes, fertilizantes, etc.).

Uma possível objetivo é maximizar a produção total, sem exceder os recursos disponíveis. Em alguns casos, isto pode ser expresso em termos de um programa linear, mas variáveis devem ser inteiras.

• Programação linear

Referências

• M.S. Bazaraa, J.J. Jarvis e H.D. Sherali. Linear Programming and Network Flows. Wiley, 1990.

• Um Tutorial em Programação Inteira (em inglês)
• Programação Linear Inteira (em castelhano)
• Programação Linear Inteira (em inglês)
• Programação Linear. Programação Inteira (em castelhano)