Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Programação dinâmica: O problema do investimento ótimo.

0 votos
32 visitas
perguntada Jun 23 em Ciência da Computação por MarcioGama (86 pontos)  

Este problema foi tirado do livro Dynammic programming: A computational tool de Art Lew e Holger Mauch (2007). É o problema 2.18, Optimal Investment Problem (INVEST).

No problema o investidor deve decidir quanto dos seus recursos disponíveis ele irá investir dado as probabilidades do investimento ser um sucesso ou fracasso.

A função desse problema é:
\[f(k,s) = max_{i} \{p_{i}f(k+1, s +i) + (1-p_{i})f(k+1, s - i + 1)\} \]

Onde:
\(i\) é a quantidade escolhida para investir
\(p_{i}\) é a chance do investimento ser um sucesso dada a quantidade investida \(i\)
\(k\) é período
\(s\) é a quantidade disponível para investir
\(s + i\) e \(s - i + 1\) são os retornos caso o investimento dê certo ou não.

O problema então quer maximizar o valor esperado do investimento dado a escolha inicial de investir e analisar os períodos subsequentes a essa decisão.

O livro dá como exemplo o seguinte caso:
4 períodos, \(s_{0}\) = 2 e \(p_{i}\) = \([1, 0.2, 0.4]\) as chances de sucesso para cada decisão possível de investimento inicial \([0,1,2]\). O objetivo então é achar o i que maximiza \(f(1,2)\) e a condição de parada é que se chegue no último período, ou seja, quando \(k = 4\). O resultado esperado é \(f(1,2) = 2.6\) com decisão inicial igual a \(i = 1\).

Compartilhe

1 Resposta

0 votos
respondida Jun 23 por MarcioGama (86 pontos)  

Segue a solução.

import numpy as np
prob = [1, 0.2, 0.4]
d = [0,1,2]

n = 4
def invest(k,s):
    lista = []
    for i in range(len(d)):
        if k==n:
            resultado = s
        else:
            resultado = prob[i]*max(invest(k + 1,s + d[i])) + (1 - prob[i])*max(invest(k+1, s - d[i] + 1))
        lista.append(resultado)
    return lista

print(invest(1,2))

resultado:

[2.4000000000000004, 2.6000000000000005, 2.6000000000000005]

Porque eu usei o max na recursão de f? Para conseguir retornar uma lista no final e analisar o resultado de cada decisão.

comentou Jul 4 por Julia Regina Scotti (31 pontos)  
Achei muito legal a sua implementação, em especial o max :-)

Para enteder melhor o que estava acontecendo fiz:

n=4
def invest_julia(k,s):
    lista = []
    for i in range(len(d)):
        if k==n:
            resultado = s
        else:
            res_0 = prob[0]*invest_julia(k+1, s+d[0]) + (1-prob[0])*invest_julia(k+1, s-d[0]+1)
            res_1 = prob[1]*invest_julia(k+1, s+d[1]) + (1-prob[1])*invest_julia(k+1, s-d[1]+1)
            res_2 = prob[2]*invest_julia(k+1, s+d[2]) + (1-prob[2])*invest_julia(k+1, s-d[2]+1)
            resultado = max(res_0, res_1, res_2)
      #  lista.append(resultado)
    return resultado
            
e daí eu ia variando o n para encontrar o resultado [2.2, 2.4, 2.6, 2,8, 3, ...]

Mas o que acho  deixou o problema mais confuso é que investir 1 ou 2 sempre dá na mesma (é indiferente investir 1 ou 2);

Note que, se investir 1, vamos ter 0.2(s+1)+0.8s
que é igual a se investir 2: 0.4(s+2)+0.6(s-1)
...