Pular para conteúdo

Lista 06 · Otimização

Acompanha o capítulo 6. Mínimo e máximo são raízes da derivada: varredura para o chute, Newton para a precisão, e o sinal de \(f''\) para conferir. Economia, arquitetura, aviação.

Abrir no Colab

Baixar o caderno

Como esta lista funciona

Abra o caderno no Colab, escreva a sua solução no lugar do # TODO e rode a célula de teste logo abaixo. Ela mesma diz o que passou e o que falhou — você não precisa esperar correção de ninguém.

O código de cada exercício também está aqui embaixo, caso você prefira colar num editor local. Os testes comparam números com tolerância.

Exercícios marcados com ✏️ são à mão, no papel, com 4 casas decimais — como na parte em papel das avaliações.

Exercício 01

✏️ À mão. Seja \(f(x) = x^2 - 6x + 10\).

a) Calcule \(f\) na grade \(x = 0, 1, 2, \ldots, 6\). Onde fica o menor valor da grade?

b) Faça um passo de Newton para otimização, \(x_1 = x_0 - f'(x_0)/f''(x_0)\), a partir de \(x_0 = 0\), com as derivadas exatas.

c) O passo acertou o mínimo exatamente. Por quê? (Pense no que é a aproximação de Newton para uma parábola.)

d) Use o sinal de \(f''\) para confirmar que é um mínimo.

Exercício 02

Escreva minimo_na_grade(f, a, b, n), que calcula f numa grade de n pontos igualmente espaçados de a a b e devolve o x da grade em que f é menor. Use np.linspace e np.argmin.

def g(x):
    return (x - 2.3)**2

minimo_na_grade(g, 0, 5, 51)    # -> 2.3

import numpy as np


def minimo_na_grade(f, a, b, n):
    """O x da grade np.linspace(a, b, n) em que f é menor."""
    # TODO: a grade, a posição do menor e o x nessa posição
    pass


# --- testes (não altere) ---
def g_ex02(x):
    return (x - 2.3)**2


def h_ex02(x):
    return x**4 - 3 * x**2 + x


assert abs(minimo_na_grade(g_ex02, 0, 5, 51) - 2.3) < 1e-9
assert abs(minimo_na_grade(h_ex02, -2, 2, 41) - (-1.3)) < 1e-9, "o vale mais fundo, na grade"
print("Exercício 02: todos os testes passaram!")

Exercício 03

Escreva otimo_newton(f, x0, n_iter), que faz n_iter passos de Newton para otimização a partir de x0, com

\[ f'(x) \approx \frac{f(x+h) - f(x-h)}{2h}, \qquad f''(x) \approx \frac{f(x+h) - 2f(x) + f(x-h)}{h^2}, \]

e \(h = 10^{-4}\).

def otimo_newton(f, x0, n_iter):
    """Ponto de f'(x) = 0 por Newton, com f' e f'' pelas diferenças centrais."""
    h = 1e-4
    x = x0
    # TODO: n_iter passos: d1, d2 e x = x - d1 / d2
    return x


# --- testes (não altere) ---
import numpy as np



def lata_ex03(r):
    return 2 * np.pi * r**2 + 700 / r


def h_ex03(x):
    return x**4 - 3 * x**2 + x


assert abs(otimo_newton(lata_ex03, 3.8, 10) - (350 / (2 * np.pi))**(1 / 3)) < 1e-6
assert abs(otimo_newton(h_ex03, 2.0, 30) - 1.1309011) < 1e-5, "a partir de 2, o vale da direita"
print("Exercício 03: todos os testes passaram!")

Exercício 04

Escreva tipo_de_ponto(f, x), que devolve o texto "minimo" se a segunda derivada central (com \(h = 10^{-4}\)) for positiva em x, e "maximo" caso contrário.

def tipo_de_ponto(f, x):
    """'minimo' se f'' > 0 em x, 'maximo' se f'' < 0."""
    h = 1e-4
    # TODO: d2 pela central e um if
    pass


# --- testes (não altere) ---
def h_ex04(x):
    return x**4 - 3 * x**2 + x


assert tipo_de_ponto(h_ex04, -1.3008) == "minimo"
assert tipo_de_ponto(h_ex04, 0.1699) == "maximo"
assert tipo_de_ponto(h_ex04, 1.1309) == "minimo"
print("Exercício 04: todos os testes passaram!")

Exercício 05

Economia — o preço certo. Um produto custa R$ 20 para fabricar. Quanto mais caro, menos se vende: a demanda é \(1000\,e^{-0{,}05p}\) unidades a um preço \(p\). A função lucro(p) (já escrita) é a margem vezes a demanda.

Escreva preco_otimo(), que acha o preço de maior lucro: uma varredura de R$ 20 a R$ 100 (81 pontos) para o chute e 10 passos de Newton em \(-\text{lucro}\).

Depois de passar: qual o lucro máximo? E o lucro vendendo a R$ 30 ou a R$ 60?

import numpy as np


def lucro(p):
    """Lucro (R$) vendendo a p reais: margem vezes demanda. JÁ ESCRITA."""
    demanda = 1000 * np.exp(-0.05 * p)
    return (p - 20) * demanda


def preco_otimo():
    """Preço que maximiza o lucro: varredura de 20 a 100 e Newton em -lucro."""
    # TODO: defina menos_lucro(p); varredura com np.linspace e np.argmin;
    # depois 10 passos de Newton com as diferenças centrais
    pass


# --- testes (não altere) ---
assert abs(preco_otimo() - 40) < 1e-6, "o preço ótimo é R$ 40 (custo + 1/0.05)"
print("Exercício 05: todos os testes passaram!")

Exercício 06

Arquitetura — a janela que deixa entrar mais luz. Uma janela é um retângulo com um semicírculo em cima (a "janela normanda"). O caixilho tem perímetro fixo \(P\). A função area_janela(r, P) (já escrita) dá a área de vidro para um raio \(r\) do semicírculo.

Escreva raio_janela(P), que acha o raio de maior área por Newton em \(-\text{área}\) (20 passos, \(h = 10^{-4}\)), a partir de \(r = P/8\).

A resposta exata é \(r = P/(4 + \pi)\). Quanto vale a altura do retângulo nesse caso?

import numpy as np


def area_janela(r, P):
    """Área (m²) de uma janela retângulo + semicírculo de raio r e perímetro P. JÁ ESCRITA."""
    altura = (P - 2 * r - np.pi * r) / 2
    return 2 * r * altura + np.pi * r**2 / 2


def raio_janela(P):
    """Raio que dá a maior área para o perímetro P."""
    # TODO: defina menos_area(r) e faça 20 passos de Newton a partir de r = P / 8
    pass


# --- testes (não altere) ---
import numpy as np


assert abs(raio_janela(6) - 6 / (4 + np.pi)) < 1e-6
assert abs(raio_janela(10) - 10 / (4 + np.pi)) < 1e-6
print("Exercício 06: todos os testes passaram!")

Exercício 07

Aviação — a velocidade que gasta menos combustível. O arrasto de um avião tem duas partes: o atrito com o ar, que cresce com \(v^2\), e o arrasto "induzido" pela sustentação, que diminui com \(v^2\). O combustível gasto por quilômetro é proporcional a \(D(v) = a\,v^2 + b/v^2\).

Escreva velocidade_economica(a, b), que faz uma varredura de 50 a 400 m/s (de 10 em 10, com um laço e o padrão "extremo", sem numpy) para achar o chute e depois 20 passos de Newton (\(h = 10^{-3}\)).

velocidade_economica(0.0003, 2e6)    # -> ≈ 285.74 m/s

Confira com a resposta exata, \(v = (b/a)^{1/4}\).

def velocidade_economica(a, b):
    """Velocidade que minimiza o arrasto a*v**2 + b/v**2 (varredura + Newton)."""

    def arrasto(v):
        return a * v**2 + b / v**2

    # TODO: varredura de 50 a 400 de 10 em 10 guardando o melhor v;
    # depois 20 passos de Newton a partir dele
    pass


# --- testes (não altere) ---
assert abs(velocidade_economica(0.0003, 2e6) - (2e6 / 0.0003)**0.25) < 1e-4
assert abs(velocidade_economica(0.0005, 5e5) - (5e5 / 0.0005)**0.25) < 1e-4
print("Exercício 07: todos os testes passaram!")

Exercício 08

Juntando as peças. As funções minimo_na_grade e otimo_newton já estão escritas. Escreva minimo_global(f, a, b), que usa a primeira (com 201 pontos) para achar o chute e a segunda (20 passos) para refinar.

Teste em \(x^4 - 3x^2 + x\) no intervalo \([-2, 2]\): a resposta tem de ser o vale mais fundo (\(x \approx -1{,}3008\)), e não o da direita — que é o que Newton sozinho acha a partir de \(x = 2\).

import numpy as np


def minimo_na_grade(f, a, b, n):
    """JÁ ESCRITA."""
    xs = np.linspace(a, b, n)
    return xs[np.argmin(f(xs))]


def otimo_newton(f, x0, n_iter):
    """JÁ ESCRITA."""
    h = 1e-4
    x = x0
    for it in range(n_iter):
        d1 = (f(x + h) - f(x - h)) / (2 * h)
        d2 = (f(x + h) - 2 * f(x) + f(x - h)) / h**2
        x = x - d1 / d2
    return x


def minimo_global(f, a, b):
    """O mínimo de f em [a, b]: varredura de 201 pontos e 20 passos de Newton."""
    # TODO: duas linhas, uma chamada de cada função pronta
    pass


# --- testes (não altere) ---
def h_ex08(x):
    return x**4 - 3 * x**2 + x


def g_ex08(x):
    return (x - 0.7)**2 + 1


assert abs(minimo_global(h_ex08, -2, 2) - (-1.3008396)) < 1e-6, "o vale mais fundo"
assert abs(minimo_global(g_ex08, -5, 5) - 0.7) < 1e-6
print("Exercício 08: todos os testes passaram!")