Loading AI tools
Da Wikipédia, a enciclopédia livre
A Otimização Combinatória é um ramo da ciência da computação e da matemática aplicada que estuda problemas de otimização em conjuntos finitos.
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. Os valores possíveis às variáveis de decisão são delimitados pelas restrições impostas sobre essas variáveis, formando um conjunto discreto (finito ou não) de soluções factíveis a um problema. O problema pode ser de minimização ou de maximização da função objetivo. A resposta para o problema de otimização, 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 óptimo global - a essas soluções chamamos de ótimo local.
Há muitas classificações possíveis 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 intratável.
Como técnicas de soluções exatas - em especial com algoritmo polinomial para alguns problemas - temos, por exemplo:
Algumas das técnicas de obtenção de soluções aproximadas:
Entre as classificações possíveis, encontram-se:
1) Quanto à relação entre as variáveis de decisão na função objetivo e nas restrições:
2) Quanto ao valor que podem assumir as variáveis:
3) Quanto à natureza da função objetivo:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.