Programação Inteira: Conceitos e Métodos

Prévia do material em texto

1
Programação Inteira
Prof.: Eduardo Uchoa
http://www.logis.uff.br/~uchoa/POI
2
Programação Inteira
Tipo de modelo matemático que difere da 
programação linear simplesmente porque algumas (ou 
todas as) variáveis podem ser definidas como inteiras.
Esse recurso adicional (a primeira vista banal) permite 
modelar um número muito maior de situações.
3
Exemplo: Problema da Mochila
Um viajante precisa decidir entre n possíveis objetos 
para colocar na sua mochila com capacidade de peso 
P. Cada objeto i oferece um ganho gi mas possui um 
peso pi. O problema é escolher um subconjunto dos 
objetos com peso ≤ P que maximize o ganho total.
4
Exemplo: Problema da Mochila
P=10 p1=1 p2=2 p3=4 p4=4 p5=5 p6=6 
. g1 =3 g2=3 g3=5 g4=5 g5= 6 g6=9 
1
2
3 4
5 6
5
Modelo de Programação Inteira
inteiros,,,,,
1,,,,,0
1065442.a.S
965533Max
654321
654321
654321
654321
xxxxxx
xxxxxx
xxxxxx
xxxxxx
≤≤
≤+++++
+++++
6
Modelo de Programação Inteira
inteiros,,,,,
1,,,,,0
1065442.a.S
965533Max
654321
654321
654321
654321
xxxxxx
xxxxxx
xxxxxx
xxxxxx
≤≤
≤+++++
+++++
Solução ótima: x1, x2 e x6 =1, ganho total 15
7
Solução Ótima
P=10 p1=1 p2=2 p3=4 p4=4 p5=5 p6=6 
. g1 =3 g2=3 g3=5 g4=5 g5= 6 g6=9 
1
2
3 4
5 6
1
2
6
Graduação em Engenharia de Produção – Universidade Federal Fluminense
8
Métodos para Programação Inteira
� Planos de Corte (Gomory, 1958).
� Pouco eficiente na prática.
� Branch-and-bound (Land e Doig, 1964).
� Branch-and-cut (muitos autores, a partir dos 
anos 80).
Todos esses métodos podem ser lentos em 
alguns casos
9
max z=2x1+x2
s.a x1 + x2 ≤4
2x1 ≤ 5
x1 ,x2 ≥ 0
x1,x2 inteiros
Algoritmo de Branch-and-Bound
10
P0: x1=2.5 x2=1.5
Z=6.5
P1: x1=2 x2=2
Z=6.0
P2: x1=2.5 x2=1
Z=6.0
Parada por
integralidade
Algoritmo de Branch-and-Bound
x2 ≥ 2 x2 ≤ 1
Parada por
Limite (bound)
3 PLs para resolver esse PI
11
Como o algoritmo de Branch-and-
Bound pode ser muito ineficiente
max z = 17x1+12x2
s.a 10x1 + 7x2 ≤ 40 
x1 + x2 ≤ 5
x1 ,x2 ≥ 0 
x1,x2 inteiros
1 2 3 4
1
2
3
4
5
5
121 2 3 4
1
2
3
4
5
5
P0: x1=1.67 x2=3.33
Z=68.33
P0
131 2 3 4
1
2
3
4
5
5
P0: x1=1.67 x2=3.33
Z=68.33
P1: x1=1 x2=4
Z=65
P2: x1=2 x2=2.86
Z=68.29
x1 ≤ 1 x1 ≥ 2
P1 P2
141 2 3 4
1
2
3
4
5
5
P3
P0: x1=1.67 x2=3.33
Z=68.33
P1: x1=1 x2=4
Z=65
P2: x1=2 x2=2.86
Z=68.29
P3: x1=2.6 x2=2
Z=68.2
x1 ≤ 1 x1 ≥ 2
x2 ≤ 2 x2 ≥ 3
151 2 3 4
1
2
3
4
5
5
P4
P0: x1=1.67 x2=3.33
Z=68.33
P1: x1=1 x2=4
Z=65
P2: x1=2 x2=2.86
Z=68.29
P3: x1=2.6 x2=2
Z=68.2
x1 ≤ 1 x1 ≥ 2
x2 ≤ 2 x2 ≥ 3
P4: x1=2 x2=2
Z=58
P5: x1=3 x2=1.43
Z=68.14
x1 ≤ 2 x1 ≥ 3
P5
161 2 3 4
1
2
3
4
5
5
P0: x1=1.67 x2=3.33
Z=68.33
P1: x1=1 x2=4
Z=65
P2: x1=2 x2=2.86
Z=68.29
P3: x1=2.6 x2=2
Z=68.2
x1 ≤ 1 x1 ≥ 2
x2 ≤ 2 x2 ≥ 3
P4: x1=2 x2=2
Z=58
P5: x1=3 x2=1.43
Z=68.14
x1 ≤ 2 x1 ≥ 3
P6: x1=3.3 x2=1
Z=68.1
x2 ≤ 1 x2 ≥ 2
P6
171 2 3 4
1
2
3
4
5
5
P0: x1=1.67 x2=3.33
Z=68.33
P1: x1=1 x2=4
Z=65
P2: x1=2 x2=2.86
Z=68.29
P3: x1=2.6 x2=2
Z=68.2
x1 ≤ 1 x1 ≥ 2
x2 ≤ 2 x2 ≥ 3
P4: x1=2 x2=2
Z=58
P5: x1=3 x2=1.43
Z=68.14
x1 ≤ 2 x1 ≥ 3
P7
P6: x1=3.3 x2=1
Z=68.1
x2 ≤ 1 x2 ≥ 2
P7: x1=3 x2=1
Z=63
P8: x1=4 x2=0
Z=68
x1 ≤ 3
x1 ≥ 4
P8
18
P0: x1=1.67 x2=3.33
Z=68.33
P1: x1=1 x2=4
Z=65
P2: x1=2 x2=2.86
Z=68.29
P3: x1=2.6 x2=2
Z=68.2
P4: x1=2 x2=2
Z=58
P5: x1=3 x2=1.43
Z=68.14
P6: x1=3.3 x2=1
Z=68.1
P7: x1=3 x2=1
Z=63
P8: x1=4 x2=0
Z=68
P9: infactível
P10: infactível
x1 ≤ 1 x1 ≥ 2
x2 ≤ 2 x2 ≥ 3
x1 ≤ 2 x1 ≥ 3
x2 ≤ 1 x2 ≥ 2
x1 ≤ 3 x1 ≥ 4
19
OBSERVAÇÃO
Este material refere-se às notas de aula do curso 
TEP117 (Pesquisa Operacional I) da Universidade 
Federal Fluminense (UFF) e não pode ser 
reproduzido sem autorização prévia do autor. 
Quando autorizado, seu uso é exclusivo para 
atividades de ensino e pesquisa em instituições 
sem fins lucrativos.