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 minimizaçã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. Em alguns casos, chegamos a valores cuja alteração discreta não conduz a resultados melhores, mas que não são também o Ótimo Global - a essas soluções chamamos de Ótimo Local.

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. Outras levarão à necessidade de métodos não-exatos (heurísticas), uma vez que sua formulação e/ou resolução exatas levariam a uma complexidade (poderia ser criado artigo sobre isso) intratável.

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)

3) Quanto à natureza da função objetivo:

A) Função Convexa - Ótimo Local é Global (mais simples)

B) Função Côncava - Ótimo Local não necessariamente Gloal (mais complicado de resolver)

--Thiago Serra 18:42, 7 Jan 2005 (UTC)