View
145
Download
1
Category
Preview:
Citation preview
Matemática computacional: métodosnuméricos, programação linear, otimização
Ricardo Terra
rterrabh [at] gmail.com
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 1 / 46
CV
Nome: Ricardo Terra
Email: rterrabh [at] gmail.com
www: ricardoterra.com.br
Twitter: rterrabh
Lattes: lattes.cnpq.br/ 0162081093970868
Ph.D. (UFMG/UWaterloo),Post-Ph.D. (INRIA/Université Lille 1)
BackgroundAcadêmico : UFLA (desde 2014), UFSJ (1 ano ), FUMEC (3 anos ), UNIPAC (1 ano ), FAMINAS (3 anos )
Profissional : DBA Eng. (1 ano ), Synos (2 anos ), Stefanini (1 ano )
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 2 / 46
Introdução à Matemática Computacional
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 3 / 46
Introdução à Matemática Computacional
Matemática ComputacionalMatemática ∩ Computação
Trata problemas complexos
qualquer área (qual não tem?)
Por meio da busca matemática de soluções
Isto é, explora o que o computador faz de melhor
É então programar algoritmos O(n!), O(nn)?
não necessariamente
vai um pouco além... vamos ver!
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 4 / 46
Introdução à Matemática Computacional
Matemática ComputacionalMatemática ∩ Computação
Trata problemas complexos
qualquer área (qual não tem?)
Por meio da busca matemática de soluções
Isto é, explora o que o computador faz de melhor
É então programar algoritmos O(n!), O(nn)?
não necessariamente
vai um pouco além... vamos ver!
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 4 / 46
Introdução à Matemática Computacional
Solução em 4 etapas1 Definição do Problema
2 Modelagem Matemática
3 Solução Numérica
4 Análise dos Resultados
Se eu lhe dizer que...o algoritmo talvez seja a parte mais fácil
não acredita?
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 5 / 46
Introdução à Matemática Computacional
Solução em 4 etapas1 Definição do Problema
2 Modelagem Matemática
3 Solução Numérica (algoritmos!!!)
4 Análise dos Resultados
Se eu lhe dizer que...o algoritmo talvez seja a parte mais fácil
não acredita?
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 5 / 46
Introdução à Matemática Computacional
Solução em 4 etapas1 Definição do Problema
2 Modelagem Matemática
3 Solução Numérica (algoritmos!!!)
4 Análise dos Resultados
Se eu lhe dizer que...o algoritmo talvez seja a parte mais fácil
não acredita?
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 5 / 46
Introdução à Matemática Computacional
Nada como exemplos!Determinante
Seja uma matriz quadrada A = (aij)ni,j=1
Solução: det(A) =∑±a1i1 · · ·anin
Fácil de programar para qualquer n
Super eficiente para:−2 2 3−1 1 32 0 1
Por que?
n = 3→ segundos n = 25→ 400.000 anos
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 6 / 46
Introdução à Matemática Computacional
Nada como exemplos!Determinante
Seja uma matriz quadrada A = (aij)ni,j=1
Solução: det(A) =∑±a1i1 · · ·anin
Fácil de programar para qualquer n
Super eficiente para:−2 2 3−1 1 32 0 1
Por que? A soma em todas as n! permutações
n = 3→ segundos n = 25→ 400.000 anos
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 6 / 46
Introdução à Matemática Computacional
Nada como (mais?) exemplos!Postponed
A partir de agora: on-the-fly
Nesta aula, visão geral das principais áreas:1 Métodos Numéricos
2 Programação Linear
3 Otimização
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 7 / 46
Métodos Numéricos
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 8 / 46
Métodos Numéricos
O que são métodos numéricos?
Algoritmos que usam aproximação numéricaheurísticas?
resultados exatos?
Convergem, convergem, convergem até um ops
ideia de ponto fixo (contudo, raramente o alcançam)
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 9 / 46
Métodos Numéricos
Achando um número aleatório!
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 10 / 46
Métodos Numéricos
Achando um número aleatório!
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 10 / 46
Métodos Numéricos
Por exemplo:
1 public class Terra
3 public static void main (String args[])System.out.println( Math.sqrt(2) );
5
7
Qual o resultado?
Essa pergunta está errada nesta aula
Assim, por que 1.4142135623730951?
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 11 / 46
Métodos Numéricos
Por exemplo:
1 public class Terra
3 public static void main (String args[])System.out.println( Math.sqrt(2) );
5
7
Qual o resultado? Essa pergunta está errada nesta aula
Assim, por que 1.4142135623730951?
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 11 / 46
Métodos Numéricos
Por exemplo:
1 public class Terra
3 public static void main (String args[])System.out.println( Math.sqrt(2) );
5
7
Qual o resultado? Essa pergunta está errada nesta aula
Assim, por que 1.4142135623730951?
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 11 / 46
Métodos Numéricos
Passo #1: Definição do Problema
Calcular√
a, a > 0 usando operações básicas (+ − /∗)
Fácil!
Passo #2: Modelagem Matemática
Problema real→ Problema original (lembra redução NP-Completo)
x =√
a =⇒ x2 = a =⇒ f (x) = x2 − a = 0
De fato: determinar a raiz de uma equação algébrica
Atenção: problema original pode ter mais soluções que real+√
a e −√
a
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 12 / 46
Métodos Numéricos
Passo #1: Definição do Problema
Calcular√
a, a > 0 usando operações básicas (+ − /∗)
Fácil!
Passo #2: Modelagem Matemática
Problema real→ Problema original (lembra redução NP-Completo)
x =√
a =⇒ x2 = a =⇒ f (x) = x2 − a = 0
De fato: determinar a raiz de uma equação algébrica
Atenção: problema original pode ter mais soluções que real+√
a e −√
a
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 12 / 46
Métodos Numéricos
Passo #3: Solução Numérica
Qual o método mais apropriado para f (x) = x2 − a = 0?
Possível solução: método de Newton
xk+1 = xk − f (xk )f ′(xk )
Substituindo f (x) e f ′(x), tem-se que:
xk+1 = xk −x2
k − a2xk
= xk −xk
2+
a2xk
= (xk +axk
) ∗ 0.5
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 13 / 46
Métodos Numéricos
Passo #3: Solução Numérica
Resultado: um processo iterativoque calcula
√a
a partir de x0
usando apenas operações aritméticas
i xi xi − 30 1.00001 5.0000 2.00002 3.4000 0.40003 3.0235 0.02354 3.0001 0.00015 3.0000 0.0000
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 14 / 46
Métodos Numéricos
1 Algoritmo Newtonparâmetros de entrada: x0, Toler, IterMax
3 parâmetros de saída: Raiz, Iter, CondErroCondErro = 0 se a raiz for encontrada, 1 caso contrário
5
Fx <- f(x0); DFx <- f’(x0); x <- x0; Iter <- 0;7 escreva Iter, x, DFx, Fxrepita
9 DeltaX <- -Fx/DFx; x <- x + DeltaXFx <- f(x); DFx <- f’(x);
11 Iter <- Iter + 1escreva Iter, x, DFx, Fx, DeltaX
13 se ( abs(DeltaX) <= Toler e abs(Fx) <= Toler ) ou DFx = 0ou Iter >= IterMax
15 então interrompafimse
17 Raiz <- xteste de convergência
19 se abs(DeltaX) <= Toler e abs(Fx) <= Toler entãoCondErro <- 0
21 senãoCondErro <- 1
23 fimsefimalgoritmo
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 15 / 46
Métodos Numéricos
Passo #4: Análise dos ResultadosA solução é adequada ao problema?
sim, ótimo!
não, nova formulação matemática
Por exemplo, se x0 < 0:
i xi xi − 30 −1.00001 −5.0000 −2.00002 −3.4000 −0.40003 −3.0235 −0.02354 −3.0001 −0.00015 −3.0000 0.0000
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 16 / 46
Métodos Numéricos
Aplicações Reais de Métodos Numéricos√
a → apenas um exemplo
e só mostramos a solução com o método de Newton
Ao longo da disciplina:
seno, coseno...
interpolação polinomial
equações lineares
EDO
etc.
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 17 / 46
Programação Linear / Otimização
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 18 / 46
Programação Linear / Otimização
Programação Linear
Envolve problemas de otimização em que:
função objetivo é linear
restrições são lineares
Mas...
o que é função objetivo e restrições?
isso tem aplicação prática?
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 19 / 46
Programação Linear / Otimização
Otimização
Busca da melhor solução dentre um conjunto de soluções
Função objetivo
um critério de avaliação das soluções alternativas
permite dizer que uma é melhor que a outra
É a função objetivo que buscamos otimizar
alguns casos maximizar
outros casos minimizar
E quanto às restrições?
o que deve ser respeitado pela função objetivo
À procura de uma definição mais formal?
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 20 / 46
Programação Linear / Otimização
Otimização (do ponto de vista matemático)
Uma função fora denominada função objetivo
Um conjunto Ω
contendo todas as possíveis soluções
Um problema de otimização matemático é definido por:
min f (x) , x ∈ Ω
ou
max f (x) , x ∈ Ω
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 21 / 46
Programação Linear / Otimização
Que tal exemplos práticos?O problema da mistura (minimizar custos)
Ração
Barragem de concreto (só modelagem do problema)
O problema da produção (maximizar faturamento)
Geladeira
Pão e Pizza (só citar)
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 22 / 46
Problema da mistura – Ração
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 23 / 46
Problema da mistura – Ração
Queremos saber quais as quantidades ideais de cadaingrediente para fazer uma quantidade de ração, com asnecessidades nutricionais atendidas e o custo total dosingredientes seja o menor possível
Temos os ingredientes e seus custos:
Milho (A1) – R$ 65,00 /Kg
Farinha de ossos (A2) – R$ 30,00 /Kg
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 24 / 46
Problema da mistura – Ração
Para fazer uma certa quantidade de ração para aves porexemplo, é necessário uma certa quantidade nutrientes,digamos, vitamina A (Va), vitamina B (Vb) e proteína (Vc)
Mais importante, segue sua quantidade nos ingredientes:
Milho (A1) → 2 un. Va 3 un. Vb 1 un. Vc
Farinha de ossos (A2)→ 3 un. Va 2 un. Vb
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 25 / 46
Problema da mistura – Ração
Ademais, a ração deve ter no mínimo:7 un. Va 9 un. Vb 1 un. Vc
Objetivo: determinar a quantidade dos alimentos parasatisfazer as restrições da ração e ter o menor custo
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 26 / 46
Problema da mistura – Ração
Modelagem
Variáveis de decisão
x1 = quantidade de ingrediente do tipo 1 presente na mistura
x2 = quantidade de ingrediente do tipo 2 presente na mistura
Função custo (restrições evitam ser nulo)
f (x1, x2) = 65x1 + 30x2
Nosso objetivo: determinar x1 e x2 tal que
f (x1, x2) = min f (x) , x ∈ Ω
e logicamente considerando as restrições
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 27 / 46
Problema da mistura – Ração
Modelo Matemático
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 28 / 46
Para lembrar:
Problema da mistura – Ração
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 29 / 46
Problema da mistura – Ração
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 29 / 46
Problema da mistura – Ração
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 29 / 46
Problema da mistura – Ração
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 29 / 46
Problema da mistura – Ração
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 29 / 46
Problema da mistura – Ração
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 29 / 46
Problema da mistura – Ração
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 29 / 46
Problema da mistura – Ração
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 29 / 46
Problema da mistura – Ração
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 29 / 46
Problema da mistura – Barragem de concreto
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 30 / 46
Problema da mistura – Barragem de concreto
Na implantação de uma barragem com grande consumode concreto, usar-se-á como fontes de agregados graúdos:Britas graníticas, seixos rolados e pedra britada comercial
A tabela no próximo slide apresenta os custos e ascomposições granulométricas de cada agregado e acomposição granulométrica ideal
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 31 / 46
Problema da mistura – Barragem de concreto
Dados do problema da barragem de concreto
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 32 / 46
Problema da mistura – Barragem de concreto
Modelo Matemático
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 33 / 46
Para lembrar:
Problema da produção – Geladeira
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 34 / 46
Problema da produção – Geladeira
Empresa precisa decidir quais modelos de geladeira instalarem sua nova planta
luxo ou básico
No máximo, 1500 un. luxo e 6000 un. básico por mês
Empresa contratou 25.000 homens-hora por mês
Luxo requer 10 homens-hora, básico requer 8 homens-hora
A capacidade da linha de montagem é de 4.500geladeiras por mês (os modelos dividem a mesma linha)
O lucro unitário do modelo luxo é R$100 por mês, básicolucra R$50 por mês
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 35 / 46
Problema da produção – Geladeira
Objetivo: determinar quanto produzir de cada modelo, demodo a satisfazer todas as restrições e maximizar o lucro daempresa
Variáveis de decisão
x1 = quantidade de geladeiras do modelo luxo a serproduzida por mês
x2 = quantidade de geladeiras do modelo básico a serproduzida por mês
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 36 / 46
Problema da produção – Geladeira
Modelo Matemático
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 37 / 46
Problema da produção – Geladeira
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 38 / 46
Problema da produção – Geladeira
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 38 / 46
Problema da produção – Geladeira
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 38 / 46
Problema da produção – Geladeira
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 38 / 46
Problema da produção – Geladeira
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 38 / 46
Problema da produção – Geladeira
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 38 / 46
Problema da produção – Pão e Pizza
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 39 / 46
Problema da produção – Pão e Pizza
Uma padaria produz: pão (P1) e massa de pizza (P2)
Usa-se: farinha (M1), fermento (M2), ovos (M3) e manteiga(M4), em que tem-se em estoque, respectivamente, 60, 38,18 e 55 unidades
1 kg de pão requer 1 un. de farinha, 2 un. de fermento e 3un. de manteiga
1 kg de massa de pizza requer 3 un. de farinha, 1 un. de ovoe 1 un. de manteiga
O pão e massa de pizza são vendidos a R$ 22/Kg e R$20/Kg
Objetivo: determinar a quantidade de cada produto a serfabricada que maximize as vendas e respeite o estoque
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 40 / 46
Programação Linear / Otimização
Algoritmo
Entendi os exemplos. Mas existe algoritmo para isso?
A resposta é simplex
SimplexAlgoritmo mais utilizado em Programação Linear
Não é tão simples como o nome (mas também não é assim complicado)
por isso só uma visão geral nesta aula
Em suma, a partir do modelo matemático do problema
passa para formal normal matricial
executa o algoritmo
são sete passos muito bem definidos
resultado: solução ótima (se existir)
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 41 / 46
Programação Linear / Otimização
Algoritmo
Entendi os exemplos. Mas existe algoritmo para isso?
A resposta é simplex
SimplexAlgoritmo mais utilizado em Programação Linear
Não é tão simples como o nome (mas também não é assim complicado)
por isso só uma visão geral nesta aula
Em suma, a partir do modelo matemático do problema
passa para formal normal matricial
executa o algoritmo
são sete passos muito bem definidos
resultado: solução ótima (se existir)
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 41 / 46
Programação Linear / Otimização
Então, consegue complicar?
O melhor é que consegue fácil e ainda conseguimos solucionar!
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 42 / 46
Programação Linear / Otimização
Então, consegue complicar?
O melhor é que consegue fácil e ainda conseguimos solucionar!
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 42 / 46
Programação Linear / Otimização
Então, consegue complicar?
O melhor é que consegue fácil e ainda conseguimos solucionar!
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 42 / 46
Programação Linear / Otimização
Então, consegue complicar?
O melhor é que consegue fácil e ainda conseguimos solucionar!
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 42 / 46
Considerações Finais
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 43 / 46
Considerações Finais
Para concluir, viu-se nesta aula:Matemática Computacional
Processo (as quatro etapas)
Motivação (det(A))
Métodos numéricos
Alguns problemas (√
a) e métodos numéricos (Newton)
Programação Linear/Otimização:
Função objetivo e restrições
Exemplos práticos de otimização
Simplex
Ao longo da disciplinas
Aprofundar... (não é afundar)
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 44 / 46
Referências
Frederico Campos et al. Algoritmos Numéricos. 2 ed., 2007.
Maristela Santos. Otimização Linear. Notas de aula, 2012.
Ricardo Terra (rterrabh [at] gmail.com) Matemática computacional Fevereiro, 2013 45 / 46
Recommended