Otimização Discreta

Introdução à Ciência da Computação
– Otimização Discreta –

Aluna: Livia Maria de Freitas
Curso: Ciência da Computação – 1º Período

Otimização Discreta
Também chamada de programação linear inteira.
Problemas de programação linear inteira: variáveis de decisão só assumem valores inteiros;
Problemas de programação linear inteira mista: as variáveis de decisão assumem valores inteiros ou reais;
Problemas de programação binária ou programação 0-1: variáveis de decisão assumem valores 0 ou 1;
Problemas de otimização combinatória: encontrar, dentre todos os possíveis subconjuntos, aquele cujo custo seja o menor possível.

Métodos de otimização discreta

Enumeração
Relaxação
Busca

Enumeração

Enumeração total: resolve problemas de otimização discreta verificando os fatos e comparando todos os valores possíveis das variáveis de decisão (combinações dos valores discretos das variáveis de decisão).

Problemas com a enumeração total
Explosão combinatória; k variáveis de decisão (binárias) → 2^k soluções.

Relaxação de modelos discretos

Modelo P é uma relaxação (de restrições) do modelo P se toda solução factível de P também é uma solução factível de P e ambos modelos possuem a mesma função objetivo;

Relaxações devem ser significativamente mais tratáveis que modelos originais.

Soluções de relaxação

Se a solução ótima do problema relaxado é factível para o problema original, então ela é também a solução ótima do problema original;

Se o modelo relaxado é infactível, o modelo original também é.

Relaxação forte

Se relaxação é uma boa aproximação do modelo original, então:
Detecta infactibilidade rapidamente;
Obtêm limitantes mais precisos;
Tem maior chance de fornecer a solução ótima;
Arredondamento mais fácil.

Relaxação é forte se
Valor ótimo é mais próximo do valor ótimo do modelo original;
Solução ótima é mais próxima da solução ótima do modelo original.

Relaxação Lagrangeana