Otimização

Author

Adriano

Métodos Exatos de Otimização

Os métodos exatos de otimização são frequentemente chamados de métodos determinísticos. Eles são caracterizados pela previsibilidade de seus passos, dado um ponto de partida conhecido. Ou seja, um método determinístico sempre levará à mesma resposta se iniciar do mesmo ponto. Estes métodos opõem-se aos métodos estocásticos ou aleatórios, que incorporam elementos de aleatoriedade em seus processos.

Métodos Heurísticos de Otimização

Os métodos heurísticos são regras práticas derivadas da experiência, sem uma prova conclusiva de validade. Eles são projetados para encontrar soluções boas, mas não necessariamente ótimas, para problemas de otimização. Estes métodos podem ser tanto determinísticos quanto estocásticos. Eles ganharam destaque nos anos 80 como ferramentas adicionais para superar as limitações das heurísticas convencionais.

Diferenças Fundamentais e Aplicações

  • Fundamento: Os métodos exatos seguem uma abordagem algorítmica rigorosa baseada em princípios matemáticos estabelecidos, enquanto os métodos heurísticos dependem de regras práticas e muitas vezes de experimentação.

  • Fundamento: Os métodos exatos seguem uma abordagem algorítmica rigorosa baseada em princípios matemáticos estabelecidos, enquanto os métodos heurísticos dependem de regras práticas e muitas vezes de experimentação, também são mais relativamente mais rápidos.

Exemplos

  • Métodos Exatos: Algoritmos de programação linear, métodos de pontos interiores, métodos de ramificação e corte.

  • Métodos Heurísticos: Algoritmos genéticos, otimização por enxame de partículas, busca tabu, e recocimento simulado.

Curiosidades

  • Métodos Exatos: Frequentemente são a base para o estudo teórico em otimização e têm suas raízes nos primeiros desenvolvimentos da matemática e da computação.

  • Métodos Heurísticos: Muitas vezes inspirados em fenômenos naturais, como a evolução (algoritmos genéticos) ou o comportamento de animais (otimização por colônia de formigas).

Cada método tem seu próprio conjunto de forças, limitações e contextos ideais de aplicação, tornando a escolha entre eles dependente das necessidades específicas e características do problema a ser resolvido.

Diferenças na Matemática e Abordagem

  1. Definição e Rigor:

    • Métodos Exatos: Baseiam-se em uma definição matemática rigorosa do problema e em um algoritmo preciso para encontrar a solução ótima.

    • Métodos Heurísticos: Dependem de regras práticas, que podem não garantir uma solução ótima, mas são eficientes para encontrar soluções boas em problemas complexos.

  2. Processo de Solução:

    • Métodos Exatos: Seguem um processo sistemático e previsível, com passos bem definidos.

    • Métodos Heurísticos: Empregam uma abordagem mais experimental e adaptativa, muitas vezes inspirada em processos naturais ou fenômenos biológicos.

  3. Aplicabilidade:

    • Métodos Exatos: São mais adequados para problemas bem definidos e de menor escala, onde uma solução precisa é necessária.

    • Métodos Heurísticos: São úteis em problemas de grande escala ou com complexidade elevada, onde uma solução exata pode ser impraticável de calcular.

Exemplos para Métodos Heurísticos

  1. Problema do Caixeiro Viajante (TSP): Dada uma lista de cidades e as distâncias entre elas, encontrar o caminho mais curto que visita todas as cidades uma vez e retorna à cidade de origem. Devido à complexidade computacional exponencial para problemas maiores, métodos heurísticos como algoritmos genéticos ou otimização por colônia de formigas são frequentemente usados.

  2. Otimização de Horários de Trabalho: Criar horários de trabalho para uma grande equipe, considerando várias restrições e preferências. A natureza variada e complexa dessas restrições torna os métodos heurísticos, como algoritmos genéticos ou busca tabu, mais viáveis.

  3. Otimização de Redes de Distribuição: Projetar a rede de distribuição ótima para produtos de um armazém para vários destinos, considerando custos, tempo e capacidade. Métodos heurísticos são úteis aqui devido à complexidade e ao tamanho do problema.

Exemplos para Métodos Exatos

  1. Problemas de Programação Linear: Por exemplo, maximização de lucro ou minimização de custos em operações de negócios com restrições lineares. Aqui, o método simplex ou a programação linear inteira são eficazes.

  2. Problemas de Fluxo de Rede: Como encontrar o caminho mais curto ou o fluxo máximo em uma rede. Algoritmos como o de Dijkstra (para o caminho mais curto) ou o algoritmo Ford-Fulkerson (para fluxo máximo) são métodos exatos aplicáveis.

  3. Otimização de Portfólio de Investimentos: Determinar a alocação ótima de recursos em diferentes ativos para maximizar o retorno esperado, sujeito a um certo nível de risco. Este é um problema bem definido onde métodos exatos como a programação quadrática são adequados.

Exemplo com Método Exato: Programação Linear usando lpSolve

Problema:

Maximizar \(3x + 4y\)

Sujeito a:

  • \(x + 2y \leq 14\)
  • \(3x - y \geq 0\)
  • \(x, y \geq 0\)

Código R:

library(lpSolve)

# Definir os coeficientes da função objetivo
f.obj <- c(3, 4)

# Definir as matrizes de restrição
f.con <- matrix(c(1, 2, 3, -1), nrow = 2, byrow = TRUE)
f.dir <- c("<=", ">=")
f.rhs <- c(14, 0)

# Resolver o problema de programação linear
solucao <- lp("max", f.obj, f.con, f.dir, f.rhs)

# Exibir a solução
solucao #valor função
Success: the objective function is 42 
solucao$solution #valos de x e y que maximizam
[1] 14  0

Exemplo com Método Heurístico: Otimização por Algoritmo Genético usando GA

Problema:

Maximizar \(f(x)=x*sen(10*π*x)+1\)

Código R:

library(GA)

# Definir a função objetivo
f.obj <- function(x) x * sin(10 * pi * x) + 1.0
lbound <- -1; ubound <- 2
curve(f.obj, from = lbound, to = ubound, n = 1000)

# Configurar e rodar o algoritmo genético
ga <- ga(type = "real-valued", fitness = function(x) f.obj(x), 
         lower = -1, upper = 2, popSize = 50, maxiter = 100)
# Exibir a solução
summary(ga)
── Genetic Algorithm ─────────────────── 

GA settings: 
Type                  =  real-valued 
Population size       =  50 
Number of generations =  100 
Elitism               =  2 
Crossover probability =  0.8 
Mutation probability  =  0.1 
Search domain = 
      x1
lower -1
upper  2

GA results: 
Iterations             = 100 
Fitness function value = 2.850274 
Solution = 
           x1
[1,] 1.850549
plot(ga)

curve(f.obj, from = lbound, to = ubound, n = 1000)
points(ga@solution, ga@fitnessValue, col = 2, pch = 19)

  • O pacote GA é usado para realizar otimização utilizando algoritmos genéticos.

  • A função objetivo é definida e, neste caso, estamos maximizando-a

  • O algoritmo genético é configurado com limites para a variável, tamanho da população e número máximo de iterações.

  • A solução fornece o valor ótimo de \(x\) e o valor máximo da função.