Introdução a Otimização

Prévia do material em texto

OTIMIZAÇÃO
Modelagem de Sistemas 
Ambientais
Prof. Ariel O. Gomes
Otimização
Desejo de maximizar ou minimizar alguma função a qual 
denomina-se função objetivo
Encontrar o projeto que melhor represente a melhor 
solução para ao problema
Simulação e Otimização
Simulação é o processo de representar matematicamente um
sistema, e realizar experimentações para prever seu
comportamento quando sujeito a determinadas condições.
Ex: Modelos chuva-vazão, modelo de reservatórios, modelos 
de redes hidráulicas, modelos de redes de fluxo...
Otimização é a determinação das condições que resultam no
melhor desempenho do sistema. Normalmente envolve a
execução de diversas simulações.
Exemplos de algoritmos: programação linear, não-linear, 
dinâmica, técnicas de inteligência artificial...
CONSTRUÇÃO DE MODELOS 
MATEMÁTICOS
4
Sistema Real
Definição e 
Descrição do Problema
Modelo Matemático
Solução do Modelo
Implementação da Solução
Simplificação
Decisão 
Teórica x 
Política
Revisão
ELEMENTOS DE UM MODELO 
MATEMÁTICO DE OTIMIZAÇÃO
DECISÕES
Identificar quais decisões efetivamente resolvem o 
problema.
O que não conhecemos no problema?
RESTRIÇÕES
Identificar quais as restrições que limitam as 
decisões a tomar
OBJETIVOS
Definir objetivos capazes de indicar que uma 
decisão é preferível a outras
5
Encontrar o valor 
dos parâmetros de 
um modelo 
matemático que 
resultem em uma 
boa concordância 
entre dados 
observados e 
calculados. 
Gupta et al.
ELEMENTOS DE UM MODELO 
MATEMÁTICO DE OTIMIZAÇÃO
▪ Função Objetivo: Constitui-se da função a ser maximizada ou
minimizada . Pode ser chamada de função multiobjetivo
quando leva em consideração vários critérios a serem
otimizados
▪ Restrições: representam as condições que devem ser
satisfeitas, podendo ser de igualdade ou desigualdade.
▪ Problema irrestrito: não tem restrições
Ponto ótimo: caracterizado pelo valar da
variáveis de projeto que otimizam a função
objetivo e satisfazem as restrições;
Determine as dimensões de um canal retangular
para transportar um vazão Q, com declividade I e
comprimento L conhecidos. Deseja-se determinar a
altura H e a largura B conforme ilustra a figura, tal
que o custo total da obra seja mínimo. Admite-se que
o custo total do canal seja composto de : custo de
instalação ( R$/m3 escavado) e custo de
revestimento ( R$/m2 de superfície)
H
B
Dados:
Q
L
I
C1: custo de escavação ( R$/m3)
C2: custo de revestimento (R$/m2)
T1: volume de escavação
T2: área de revestimento
H
B
Dados:
Q
L
I
B e H: variáveis de decisão
Custo Total da Obra: função objetivo a minimizar!
Minimizar: C1.T1 + C2.T2
Sujeito a:
B>0
H>0
Q: equação de Maning
C1: custo de escavação ( R$/m3)
C2: custo de revestimento (R$/m2)
T1: volume de escavação
T2: área de revestimento
Minimizar: C1.T1 + C2.T2
Sujeito a:
B>0
H>0
Q: equação de Maning
Se B e H são variáveis de decisão. Então Colocar a função
objetivo em função de B e H
T1= B.H.L
T2=(B+2H).L
Q = (1/n)(B.H). {[(B.H)/(B+2H)]^2/3}. I^(1/2)
Então fica:
Minimizar: C1.BHL+ C2.(B+2H).L
Sujeito a:
Q - (1/n)(B.H).{[(B.H)/(B+2H)]^2/3}.
I^(1/2)=0
B>0
H>0
▪ Maximizar benefícios líquidos
▪ Minimizar custos de projetos
▪ Minimizar tempo de atendimento de demanda
▪ Minimizar o consumo de água
▪ Maximizar a qualidade Ambiental
▪ Minimizar Perdas
▪ Minimizar Impactos Ambientais
▪ Encontrar o mínimo ou o máximo de uma função
0
20
40
60
80
100
120
140
160
0 10 20 30
▪ Encontrar pontos da função em que a derivada é zero.
▪ Vantagens: pode ser rápido, é mais elegante) 
▪ Desvantagens: problemas de recursos hídricos apresentam funções 
de picos múltiplos, funções descontínuas, ausência da forma 
analítica da função, por exemplo
0
20
40
60
80
100
120
140
160
0 10 20 30
2x.cx.ba)x(F ++=
0
dx
dF
=
▪ Superfícies de resposta complexas
▪ Pontos extremos mal definidos
▪ Regiões planas
▪ Muitos ótimos locais
▪ Ótimo global apenas pouco melhor do que os ótimos locais
▪ Cálculo analítico,
▪ Método de Lagrange
▪ Método Gráfico
▪ Técnicas numéricas
▪ Busca aleatória
▪ Busca direta
▪ Mistos
▪ Vantagens: funções 
descontínuas; picos 
múltiplos
▪ Desvantagens: 
demorado; não existe 
garantia de atingir o 
ponto ótimo global
0
20
40
60
80
100
120
140
160
0 10 20 30
“Ótimo”
▪ Estratégia de caminhar “morro acima” 
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Máximo global
Máximo local
Função objetivo: F(x1,x2) 
x1
x2
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Início: ponto coordenadas (parâmetros) aleatórias
X1=valor aleatório entre a e b
X2=valor 
aleatório entre 
c e d
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Determina direção de busca: exemplo x2=x2+0,3; x1=x1
Função objetivo melhorou? Não, então tenta no outro sentido. 
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Não, então volta para o ponto anterior...
F.O melhorou? Sim, então continua no mesmo sentido
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
...e muda a direção de busca.
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
E assim segue até encontrar um ponto em que não existe
direção de busca que melhore o valor da FO
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Rosenbrock: Método um pouco mais eficiente
Direção de busca é a que potencialmente dará maior incremento da FO
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Limitação da busca direta: Ótimos locais
Região que 
atrai solução
para o ótimo
local
Tentativa de contornar problema: Busca 
direta com inicialização múltipla
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Várias 
tentativas; 
espera se que 
o ótimo global 
seja a melhor
solução 
testada.
Problema: Ineficiente e ineficaz quando a FO tem muitos ótimos locais
▪ Programação linear (Simplex)
▪ Programação não-linear
▪ Programação dinâmica
▪ Algoritmos genéticos
▪ Caminhos de formiga
▪ …
▪ Definição da faixa de validade dos parâmetros
▪ geração aleatória de pontos (conjuntos de parâmetros)
▪ avaliação das funções objetivo para cada ponto
▪ reprodução, evolução
▪ conjuntos com melhores F.O. têm maior chance de contribuir na 
reprodução 
Inspiração na natureza
•Conceitos de população, reprodução e gerações
•Filhos são semelhantes aos pais
•Os pais mais “adaptados” tem maior 
probabilidade de gerar filhos
•Os filhos não são completamente iguais aos 
pais
Algumas regras gerais dos 
algoritmos genéticos
▪ Na natureza:indivíduos mais adaptados têm maior probabilidade 
de sobreviver até chegar à fase reprodutiva e de participar do 
processo de reprodução.
▪ No algoritmo: pontos com maior FO têm maior probabilidade de 
serem escolhidos para participar dos complexos. 
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 1
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 2
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 3
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 4
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 5
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 6
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 7
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 8
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 9
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 10
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Passo 20
▪ Considerar mais de uma FO.
▪ Calibração de modelos hidrológicos distribuídos
▪ Otimização de sistemas de reservatórios de usos múltiplos 
(controle de cheias x regularização de vazão)
▪ Vazão e evapotranspiração
Problemas e formulação da função objetivo, declaração das 
variáveis e restrições.
Um sistema biológico de tratamento de águas residuárias
necessita de nutrientes para a fase de crescimento de
bactérias.
As necessidades nutricionais
das bactérias estão na tabela ao lado:
Component
e
quantidade 
(mg)
N 80
P 70
K 100
glicose 60
Você deve pegar 4 soluções
para compor a solução a ser
injetada no reator, que contém
as seguintes quantidades de
cada componente por litro de
solução (ver tabela ao lado).
Ou seja, 1 litro de solução A
contém 10 mg de N, 8 mg de P,
15 mg de K e 20 mg de glicose.
Componen
te 
Solução(mg)
A B C D
N 10 5 9 10
P 8 7 6 6
K 15 3 4 7
glicose 20 2 3 9
Solução Custo($/L)
A 100
B 800
C 1200
D 3500
Os custos unitários das soluções são os seguintes:
Deseja-se saber as quantidade de A, B, C e D na composição a ser
injetada no reator, de maneira a atender as necessidades
nutricionais das bactérias à custo mínimo
O Governo Federal colocou 20 ha (hectare) de terras
desmatadas à disposição de produtores locais. Estimula-se
que tal área seja utilizada para o plantio de soja e algodão.
Calcula-se que há 1200 homens-horas disponíveis durante o
período de semeadura; e que são necessários 20 homens-
horas por hectare de soja e 120 homens-horas por hectare de
algodão. Oferece-se ainda uma linha máxima de crédito de $
6.000 (seis mil dólares), dividida da seguinte forma: $ 600,00
(seiscentos dólares) por hectare de soja e $ 200,00 (duzentos
dólares) por hectare de algodão. Como organizar essa área de
plantio se é sabido que as margens de lucro esperadas são $
50,00 (cinqüenta dólares) por hectare de soja e $ 25,00 (vinte
e cinco dólares) por hectare de algodão?
Objetivo: Maximização do lucro
Alternativas: produção de soja (x1)
produção de algodão (x2)
Restrições: área; disponibilidade de mão-de-obra; crédito
Estrutura matemática:
sujeito a 
A solução ótima é :
Exemplo 3: Produção de Aço vs. 
Ambiente
Uma empresa de aço emite para a atmosfera três 
tipos de contaminantes:
◼partículas
◼óxido sulfúrico
◼hidrocarbonetos
A produção de aço inclui duas fontes principais de 
contaminação: 
◼ os altos- fornos para produzir o ferro-gusa (ferro de primeira fundição 
ainda não purificado)
◼os fornos abertos para converter o ferro em aço
De acordo com decisões governamentais a fábrica tem de
reduzir anualmente a emissão dos contaminantes como a
seguir se indica:
Exemplo 3: Produção de Aço vs. Ambiente(2)
Contaminante Redução requerida no nível 
anual de emissão
(em milhares de toneladas)
A:Partículas 60
B: Óxido sulfúrico 150
C: Hidrocarbonetos 125
Exemplo 3: Produção de Aço vs. Ambiente(3)
Para reduzir a emissão os engenheiros propõem as seguintes medidas: 
◼ Aumentar a altura das chaminés
◼ A utilização de filtros nas chaminés
◼ Incluir certos aditivos nos combustíveis
Cada medida tem associado os seguintes custos anuais na sua
implementação em milhares de Euros:
Método de redução Altos fornos Fornos abertos
Chaminés mais altas 8 10
Filtros 7 6
Melhores 
combustíveis
11 9
Exemplo 3: Produção de Aço vs. Ambiente(4)
Com as medidas propostas vai ser possível eliminar as quantidades anuais 
dos contaminantes A, B e C nas seguintes quantidades (em milhares de 
toneladas):
Chaminés mais 
altas
Filtros Melhores 
combustíveis
Contaminante Altos 
fornos
Fornos 
Abertos
Altos 
fornos
Fornos 
Abertos
Altos 
fornos
Fornos 
Abertos
Partículas 12 9 25 20 17 13
Óxido sulfúrico 35 42 18 31 56 49
Hidrocarbonetos 37 53 28 34 29 20
Estas medidas podem ser implementadas na sua totalidade ou 
parcialmente.