Otimização combinatória: diferenças entre revisões
Optimização combinatória |
|||
| Linha 1: | Linha 1: | ||
A '''Optimização Combinatória''' é um ramo da ciência da computação que estuda problemas de otimização em conjuntos. |
A '''Optimização Combinatória''' é um ramo da ciência da computação que estuda problemas de otimização em conjuntos. |
||
Em um problema de optimizaçã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 Óptimo 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 Óptimo Global - a essas soluções chamamos de |
Em um problema de optimizaçã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 Óptimo 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 Óptimo Global - a essas soluções chamamos de Óptimo Local. |
||
Existem muitas classificações possível para o problema de |
Existem muitas classificações possível para o problema de optimização, e algumas delas apresentarão métodos exactos e eficientes de resolução. Outras levarão à necessidade de métodos não-exactos ([[heurística]]), uma vez que sua formulação e/ou resolução exatas levariam a uma complexidade (poderia ser criado artigo sobre isso) intratável. |
||
Revisão das 18h40min de 19 de setembro de 2005
A Optimização Combinatória é um ramo da ciência da computação que estuda problemas de otimização em conjuntos.
Em um problema de optimizaçã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 Óptimo 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 Óptimo Global - a essas soluções chamamos de Óptimo Local.
Existem muitas classificações possível para o problema de optimização, e algumas delas apresentarão métodos exactos e eficientes de resolução. Outras levarão à necessidade de métodos não-exactos (heurística), uma vez que sua formulação e/ou resolução exatas levariam a uma complexidade (poderia ser criado artigo sobre isso) intratável.
Como técnicas de soluções exatas - em especial com algoritmo polinomial para alguns problemas - temos, por exemplo:
Algoritmos de grafos (ver Teoria dos grafos)
Para mais informações, ver Lista de algoritmos.
Algumas das técnicas de obtenção de soluções aproximadas:
Algoritmos genéticos (Genetic Algorithms, em inglês)
Busca tabú (Taboo Search, em inglês)
Colônia de formigas (Ant Colony, em inglês)
Greedy Randomized Adaptive Search Procedures (GRASP, sigla)
Redes neurais (Neural Networks, em inglês)
Simulated annealing (Anelagem Simulada, em português)
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 - Óptimo Local é Global (mais simples)
B) Função Côncava - Óptimo Local não necessariamente Global (mais complicado de resolver)