Problema de otimização - Optimization problem

Em matemática , ciência da computação e economia , um problema de otimização é o problema de encontrar a melhor solução de todas as soluções viáveis .

Os problemas de otimização podem ser divididos em duas categorias, dependendo se as variáveis são contínuas ou discretas :

Um problema de otimização com variáveis discretas é conhecido como otimização discreta , em que um objeto como um inteiro , permutação ou gráfico deve ser encontrado a partir de um conjunto contável .
Um problema com variáveis contínuas é conhecido como otimização contínua , na qual um valor ótimo de uma função contínua deve ser encontrado. Eles podem incluir problemas restritos e problemas multimodais.

Problema de otimização contínua

A forma padrão de um problema de otimização contínua é

{\ displaystyle {\ begin {alinhado} & {\ underset {x} {\ operatorname {minimize}}} && f (x) \\ & \ operatorname {subject \; to} && g_ {i} (x) \ leq 0, \ quad i = 1, \ dots, m \\ &&& h_ {j} (x) = 0, \ quad j = 1, \ dots, p \ end {alinhado}}}

Onde

$f : ℝ n \to ℝ$ é a função objetivo a ser minimizada sobre o vetor $n-$ variável $x$ ,
$g i (x) \leq 0$ são chamados de restrições de desigualdade
$h j (x) = 0$ são chamados de restrições de igualdade , e
$m \geq 0$ e $p \geq 0$ .

Se $m = p = 0$ , o problema é um problema de otimização irrestrita. Por convenção, o formulário padrão define um problema de minimização . Um problema de maximização pode ser tratado negando a função objetivo.

Problema de otimização combinatória

Formalmente, um problema de otimização combinatória $A$ é quádruplo $(I, f, m, g)$ , onde

$I$ é um conjunto de instâncias;
dada uma instância $x \in I$ , $f (x)$ é o conjunto de soluções viáveis;
dada uma instância $x$ e uma solução viável $y$ de $x$ , $m (x, y)$ denota a medida de $y$ , que geralmente é um real positivo .
$g$ é a função objetivo e é $mínimo$ ou $máximo$ .

O objetivo é então encontrar para alguma instância $x$ uma solução ótima , ou seja, uma solução viável $y$ com

{\ displaystyle m (x, y) = g {\ bigl \ {} m (x, y ') \ mid y' \ in f (x) {\ bigr \}}.}

Para cada problema de otimização combinatória, existe um problema de decisão correspondente que pergunta se existe uma solução viável para alguma medida particular $m 0$ . Por exemplo, se houver um gráfico $G$ que contém vértices $u$ e $v$ , um problema de otimização pode ser "encontrar um caminho de $u$ para $v$ que usa as bordas menor número". Esse problema pode ter uma resposta de, digamos, 4. Um problema de decisão correspondente seria "há um caminho de $u$ para $v$ que usa 10 ou menos arestas?" Este problema pode ser respondido com um simples 'sim' ou 'não'.

No campo dos algoritmos de aproximação , os algoritmos são projetados para encontrar soluções quase ótimas para problemas difíceis. A versão de decisão usual é, então, uma definição inadequada do problema, uma vez que especifica apenas soluções aceitáveis. Embora pudéssemos introduzir problemas de decisão adequados, o problema é mais naturalmente caracterizado como um problema de otimização.

Veja também

Problema de contagem (complexidade)
Otimização de Design
Problema de função
Problema de luva
Pesquisa operacional
Satisficing : o ótimo não precisa ser encontrado, apenas uma solução "boa o suficiente".
Problema de pesquisa
Programação semi-infinita

Referências

links externos

"Como o Traffic Shaping otimiza a largura de banda da rede" . IPC . 12 de julho de 2016 . Página visitada em 13 de fevereiro de 2017 .

Languages

In other projects