DOMÍNIO DAS VARIÁVEIS
Quais valores cada variável pode assumir?
x₁, x₂ ∈ [0, 10]FUNDAMENTOS DE OTIMIZAÇÃO · SUBTÓPICO 03
Nem toda solução possível é uma solução permitida.
O espaço de busca contém as alternativas que o algoritmo pode representar. As restrições recortam esse espaço e determinam quais candidatos são realmente viáveis.
ESPAÇO DE BUSCAx ∈ S
soluções permitidasfronteiras das restrições
01 · DO TODO AO PERMITIDO
Domínio, espaço de busca e região viável não são a mesma coisa.
Cada camada acrescenta informação até separar os candidatos que podem ser aceitos pelo problema.
ESPAÇO DE BUSCA · S
Todas as combinações representáveis.
S = [0,10] × [0,10]REGIÃO VIÁVEL · F
Combinações que respeitam todas as restrições.
F = {x ∈ S | gᵢ(x) ≤ 0}F ⊆ S
A região viável está contida no espaço de busca. Todo ponto viável pode ser representado, mas nem todo ponto representável é permitido.
02 · TIPOS DE RESTRIÇÃO
Limites reais assumem diferentes formas matemáticas.
Faixa de uma variável
Define o menor e o maior valor permitido para uma escolha.
010
0 ≤ x₁ ≤ 10
Capacidade ou orçamento
Permite valores de um lado da fronteira e rejeita os demais.
viávelinviável
2x₁ + x₂ ≤ 14
Balanço exato
Exige que uma relação seja atendida exatamente ou dentro de uma tolerância.
4,95,05,1
h(x) = 0
Dependência entre decisões
Uma escolha pode exigir, impedir ou limitar outra escolha.
AexigeB
x₁ = 1 ⇒ x₂ = 1
03 · LEITURA GEOMÉTRICA
Cada desigualdade elimina uma parte do espaço.
Com duas variáveis, podemos enxergar as restrições como retas e a região viável como a interseção dos lados permitidos.
Primeira fronteira
x₁ + x₂ ≤ 10Mantemos o lado abaixo da reta.
Segunda fronteira
2x₁ + x₂ ≤ 14Mantemos novamente o lado permitido.
Interseção
F = g₁ ∩ g₂A sobreposição forma a região viável.
candidato x[x₁, x₂]
→testar g₁≤ 0?
→testar g₂≤ 0?
→resultadoviável ou inviável
04 · LABORATÓRIO INTERATIVO
Maximize o resultado sem sair da região viável.
Mova o candidato pelo plano. O melhor valor só é válido quando todas as restrições são respeitadas.
Espaço de busca e região viável
Arraste o ponto. A área verde satisfaz simultaneamente as duas restrições.
região viávelx₁ + x₂ = 102x₁ + x₂ = 14candidato
8,0 + 7,0 = 15,0 ≤ 10violada por 5,02(8,0) + 7,0 = 23,0 ≤ 14violada por 9,005 · COMO O ALGORITMO LIDA COM VIOLAÇÕES
Rejeitar, reparar ou penalizar.
Metaheurísticas usam diferentes estratégias para impedir que soluções inviáveis dominem a busca.
Rejeição
Descarta o candidato e gera outro até encontrar uma solução viável.
inviável→descartar
Simples, mas pode desperdiçar muitas tentativas quando F é pequena.Reparo
Modifica o candidato para trazê-lo de volta à região permitida.
inviável→corrigir
Exige uma regra de reparo adequada à estrutura do problema.Penalização
Reduz a qualidade conforme a intensidade da violação.
f(x)→f(x) − P(x)
Permite explorar fora de F, mas o peso da penalidade precisa ser calibrado.Representação viável
Constrói a codificação para que ela produza apenas soluções permitidas.
gerar→sempre viável
Pode ser muito eficiente, embora nem sempre seja fácil de projetar.maximização com penalidadefitness(x) = f(x) − λ · violação(x)
Quanto maior a violação, maior o desconto aplicado à qualidade do candidato.
06 · ARMADILHAS COMUNS
Uma região viável mal definida compromete toda a busca.
Sinal invertido
≤ em vez de ≥Pode eliminar exatamente o lado que deveria permanecer permitido.
Unidades diferentes
horas + minutosAs grandezas precisam ser convertidas antes de participar da mesma expressão.
Região vazia
F = ∅Restrições incompatíveis tornam impossível encontrar qualquer solução.
Limite esquecido
x < 0?Sem limites básicos, o algoritmo pode descobrir valores sem significado real.
07 · NO CÓDIGO
Viabilidade é uma pergunta com resposta booleana.
function avaliarRestricoes([x1, x2]) {
const restricao1 = x1 + x2 <= 10;
const restricao2 = 2 * x1 + x2 <= 14;
const limites = x1 >= 0 && x2 >= 0;
return {
restricao1,
restricao2,
viavel: restricao1 && restricao2 && limites
};
}
avaliarRestricoes([4, 6]); // viável
avaliarRestricoes([8, 7]); // inviávelAvaliar separadamente
Cada regra gera seu próprio resultado verdadeiro ou falso.
Combinar com E
O operador lógico exige que todas as condições sejam verdadeiras.
Medir violações
Além do booleano, podemos calcular quanto o limite foi excedido.
Escolher a estratégia
O algoritmo decide rejeitar, reparar ou penalizar o candidato.
PRÓXIMO SUBTÓPICO
Máximos e mínimos.
Com objetivo e região viável definidos, podemos estudar onde os melhores valores aparecem na paisagem.
Continuar estudo →