Otimização combinatória

A Otimização Combinatória é um ramo da ciência da computação que estuda problemas de otimização em conjuntos.

Em um problema de otimização temos uma função objetivo e um conjunto de restrições, ambos relacionados às variáveis de decisão. O problema pode ser de minimazação ou de maximização da função objetivo. A resposta para o problema, ou seja, o Ótimo Global, será o menor (ou maior) valor possível para a função objetivo para o qual o valor atribuído às variáveis não viole nenhuma restrição.

Existem muitas classificações possível para o problema de otimização, e algumas delas apresentarão métodos exatos e eficientes de resolução.

Dentre as classificações possíveis, seguem abaixo algumas:

1) Quanto à relação entre as variáveis de decisão na função objetivo e nas restrições: A) Programação Linear B) Programação Não-Linear

2) Quanto ao valor que podem assumir as variáveis: A) Programação Real (nome não-utilizado, apenas posto aqui para diferenciação) B) Programação Inteira C) Programação 0-1 (variáveis inteiras, com apenas dois valores possíveis) D) Programação Mista (algumas variáveis reais e outras inteiras)