Pular para o conteúdo principal

Programação Inteira

A Programação Inteira é uma extensão da Programação Linear onde as variáveis de decisão são restritas a serem inteiros. A formulação matemática básica para um problema de Programação Inteira é:

Aqui, indica que as variáveis de decisão são inteiras.

Arredondamento em LP e Falhas​

A abordagem de arredondamento pode falhar de várias maneiras. Uma delas é que o arredondamento da solução ótima de um LP pode resultar em uma solução inviável para o PI original. Além disso, mesmo que seja viável, não há garantia de que a solução arredondada seja ótima.

Suponha que a solução ótima para o LP relaxado seja e após o arredondamento obtenhamos . A seguinte desigualdade pode ocorrer:

onde é o valor ótimo do problema de PI.

Formulação Ideal e ​

Para qualquer problema de Programação Inteira, o conjunto é o conjunto de todas as soluções inteiras viáveis. O fechamento convexo deste conjunto, , é a menor região convexa que contém todas as soluções inteiras. Em termos matemáticos:

A formulação ideal para um problema de PI é aquela cujo conjunto viável é exatamente .

O poliedro integral é essencialmente o poliedro e é útil porque quaisquer pontos extremos desse poliedro são soluções inteiras. O objetivo ao resolver problemas de PI muitas vezes é encontrar uma representação deste poliedro integral ou aproximar-se dele de forma eficaz.

Relação com LP​

Métodos como o branch-and-bound ou o branch-and-cut são técnicas comuns para resolver problemas de PI, e esses métodos frequentemente usam soluções de problemas de LP como subproblemas. Esses métodos tentam aproximar de forma eficiente para encontrar uma solução ótima do problema de PI.

Programação Inteira-Mista (MIP)​

A PM permite uma combinação de variáveis contínuas e inteiras, possibilitando maior flexibilidade na modelagem de problemas complexos.

O uso de métodos híbridos, combinando aspectos do Simplex com técnicas de PI, permite resolver problemas de PM.

Branch-and-Bound​

Inicialização:

  • Relaxação Linear: Comece resolvendo a relaxação linear do problema original, ou seja, o problema sem as restrições de integralidade. Isso fornece uma solução contínua que serve como um limite superior inicial (para problemas de minimização) ou limite inferior (para problemas de maximização).
  • Seleção do Nó Raiz: O problema relaxado é o nó raiz da árvore de pesquisa.

Ramificação (Branching):

  • Seleção de Variável: Escolha uma variável que tenha um valor fracionário na solução ótima da relaxação linear.

  • Divisão: Crie dois subproblemas (nós filhos), um com a restrição de que a variável selecionada seja arredondada para baixo e outro com a restrição de que seja arredondada para cima.

  • Construção da Árvore de Pesquisa: Esses subproblemas tornam-se nós em uma árvore de pesquisa, onde o nó raiz é o problema original e os nós folha são problemas com todas as variáveis inteiras.

Avaliação de Limites (Bounding):

  • Cálculo de Limites: Resolva a relaxação linear de cada subproblema para obter limites para a solução ótima.
  • Corte (Pruning): Se o limite de um subproblema for pior que a melhor solução inteira encontrada até agora, esse subproblema pode ser descartado.

Seleção de Nós:

  • Estratégia de Seleção: Escolha o próximo nó a ser explorado com base em uma estratégia, como "melhor limite primeiro" ou "profundidade primeiro".
  • Exploração: Explore a árvore de pesquisa seguindo a estratégia de seleção, repetindo as etapas de ramificação e corte.

Terminação:

  • Condição de Parada: Continue o processo até que não haja mais nós a serem explorados ou até que outros critérios de parada sejam atendidos.
  • Solução Ótima: A melhor solução inteira encontrada durante o processo é a solução ótima.

Exemplo​

Vamos considerar um pequeno problema de programação inteira mista:

Aqui, é uma variável contínua e é uma variável inteira.

Inicialização Primeiro, resolvemos a relaxação linear do problema:

A solução ótima da relaxação é com . Como é fracionário, precisamos continuar.

Ramificação (Branching)

Selecionamos para ramificação.

  1. No primeiro subproblema, é arredondado para baixo, i.e., .
  2. No segundo subproblema, é arredondado para cima, i.e., .

Avaliação de Limites (Bounding)

  1. No primeiro subproblema (com ), a solução ótima é com .
  2. No segundo subproblema (com ), a solução ótima é com .

Como é a solução inteira com maior valor para nosso problema de maximização, ela é a solução ótima do problema PI.

Conclusão

Pelo método de branch-and-bound, determinamos que a solução ótima do problema de PI é com .

Vantagens e Desvantagens​

Vantagens:

  • Garante a obtenção da solução ótima global.
  • Pode ser mais eficiente que a enumeração exaustiva.

Desvantagens:

  • Pode ser computacionalmente caro para problemas grandes.
  • A eficiência depende da estratégia de seleção e da qualidade dos limites.

A Programação Linear, Inteira e Mista abarca uma gama rica e diversificada de técnicas de otimização. Os algoritmos e métodos associados a essas técnicas oferecem soluções práticas e eficazes para uma variedade de problemas complexos encontrados em campos como engenharia, economia e ciências sociais.