OTIMIZAÇÃO COMBINATÓRIA

Otimização Combinatória, Notas de aula, 2009/2 c Departamento de Computação, Universidade Federal de Ouro Preto.

OTIMIZAÇÃO COMBINATÓRIA

Marcone Jamilson Freitas Souza

Departamento de Computação
Instituto de Ciências Exatas e Biológicas
Universidade Federal de Ouro Preto
Homepage: http://www.iceb.ufop.br/decom/prof/marcone
E-mail: [e-mail]

2

Otimização Combinatória

Sumário
I

Programação Inteira

4

1 Introdução
1.1 Características dos modelos lineares de programação inteira . . . . . . . . . . . . .

4
4

2 Modelagem de Programação Matemática Inteira
2.1 Alocação de recursos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Problema da Mochila 0-1 (Knapsack Problem) . . . . . . . . . . . . . . . . . . . .
2.3 Problema da Mochila Inteira . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Problema da Mochila 0-1 Múltipla . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Problema da Mochila Inteira Múltipla . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Problema de Corte de Estoque (Cutting Stock Problem) . . . . . . . . . . . . . . .
2.7 Problema de Corte de Estoque Unidimensional . . . . . . . . . . . . . . . . . . . .
2.8 Alocação de pessoal (Staff Scheduling) . . . . . . . . . . . . . . . . . . . . . . . .
2.9 Problema da Fábrica de Prateleiras . . . . . . . . . . . . . . . . . . . . . . . . . .
2.10 Fluxo Máximo em Redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.11 Caminho Mínimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.12 Programação da produção - exemplo 1 . . . . . . . . . . . . . . . . . . . . . . . .
2.13 Sequenciamento em processadores paralelos e idênticos . . . . . . . . . . . . . . .
2.14 Planejamento da Produção - Problema da Fábrica de Motores . . . . . . . . . . .
2.15 Problema de empacotamento (Bin Packing) . . . . . . . . . . . . . . . . . . . . .
2.16 Open Dimensional