RESUMO DE PROGRAMAÇÃO LINEAR INTEIRA

Resumo - Programação Linear Inteira - PLI.

Problemas de Programação Linear onde todas ou algumas variáveis devem ter valores inteiros.

Quanto a Classificação:

1. PLI puro (só variáveis inteiras) ou PLI misto (variáveis inteiras e variáveis xi >= 0).
2. Com variáveis inteiras binárias (0 ou 1) ou com variáveis inteirasem geral (0, 1, 2, 3, 4,...). 2

Métodos:

1. Arredondamento ou truncagem dos valores não inteiros: podem produzir soluções distantes da ótima, ou mesmo que não sejam viáveis (ver exemplo adiante).

Arredondamento gerando solução inviável.

Seja o modelo de PLI:

Resolução gráfica: PL Relaxado =
PLI sem integralidade das soluções

2. Métodos de otimização da PLI: têm o inconveniente de o tempo de resolução crescer drasticamente com o aumento do número de variáveis inteiras do modelo.

3. Branch and Bound (Partição e Avaliação)

O método Branch-and-Bound (em português, particionar e limitar “as partições”) é um algoritmo que apresenta essa qualidade. Como os problemas de PLI são “relativamente grandes”, para resolvê-los diretamente deve-sedividi-lo em sub-problemas cada vez menores, até que estes possam ser solucionados.

Três Fases do Branch and Bound

1. Partição (branching) - Dividir um problema num conjunto de subproblemas (mais pequenos que o problema original)
A divisão é feita criando uma partição do conjunto de soluções Fazíveis
Existem métodos sofisticados para a selecção da variável de partição (branching variable)

2. Bounding (avaliação) - Para cada um dos subproblemas é necessário obter uma avaliação de qual é o melhor valor que o óptimo pode ter (um majorante nos problemas de maximização e um minorante nos problemas de minimização - em qualquer dos casos é um limite - (bound)).

A forma de o fazer é resolver uma forma relaxada do problema e que seja de fácil resolução. Embora se possa considerar outras formas de relaxamento o mais usual é considerar o relaxamento linear (i.e. relaxar as