Diversos

Programação Linear
Inteira
Capítulo 3

Programação Linear Inteira ou Programação Inteira
 Pode ser entendida como um caso específico da programação linear.
 Quando as variáveis, ou parte delas, são valores inteiros.

 Tipos de PLI
 Programação inteira pura: todas as variáveis de decisão são inteiras.
 Programação inteira mista: algumas variáveis de decisão são inteiras.
 Programação inteira booleana (ou binária): variáveis de decisão só podem assumir valores 0 ou 1.

2

Exemplo

3

Arredondamento
 Por que não resolver seus problemas correspondentes “relaxados” e arredondar as variáveis de decisão para o maior ou menor inteiro mais próximo?

 Dois problemas podem resultar:
 Valores arredondados podem resultar inviáveis no PI.
 Soluções resultantes são altamente sub-ótimas.

4

Arredondamento
Exemplo

Solução Relaxada

Maximizar z  x1  x2

 Solução ótima do Simplex:

sujeito a :
 2 x1  2 x2  3 x1  1,5

 x1 = 1,5 e x2 = 3 com z* = 4,5.

 Experimentemos arredondar x1 para 1 ou 2.

x1  0, x2  0 e x1 , x2 

5

Arredondamento
 Arredondamento resulta em soluções não admissíveis.

 Só 5 pontos satisfazem as restrições.  Novas restrições poderiam ser incluídas no problema para conduzir ao ponto ótimo.
6

Métodos de Solução de PLI
 A redução do espaço de soluções admissíveis através de novas restrições nunca poderá resultar em melhores resultados.

 Isso implica que a solução ótima não inteira impõe um “teto” para a solução inteira.

 No exemplo anterior, a solução com x1 = 2 resultou em z = 5 (maior que o ótimo z = 4,5) e poderia ser eliminada sem testar sua admissibilidade.
7

Visão Geral do Métodos de Solução de PLI
 Técnicas de Enumeração
 Técnicas de Cortes

 Técnicas Híbridas

 Na maioria dos casos, as técnicas de solução são especializadas para os tipos de problemas de PLI.
 Entretanto, certas técnicas são bastante recorrentes.

8

Enumeração