Programação inteira

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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.

Modelagem[editar | editar código-fonte]

O modelo de PLI é o seguinte[1]:

Max (ou Min)
sujeito a para i = 1, 2, ..., m
para j = 1, 2, ..., p (≤n)
para j = p+1, ..., n

Métodos de solução[editar | editar código-fonte]

A maneira ingênua 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 geral solução inviável ou muito distante da otimalidade.

Branch-and-bound[editar | editar código-fonte]

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 otimalidade da solução utiliza-se de limites calculados ao longo da enumeração.

Método de planos de corte[editar | editar código-fonte]

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.

Aplicações[editar | editar código-fonte]

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.

Planejamento de produção[editar | editar código-fonte]

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.

Ver também[editar | editar código-fonte]

Referências

  1. a b Hillier, Frederick S.. Introdução à Pesquisa Operacional. Porto Alegre: McGraw-Hill, 2013.

Bibliografia[editar | editar código-fonte]

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

Ligações externas[editar | editar código-fonte]