Programação dinâmica: O problema da produção

Question

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

Neste problema, o produtor deve escolher quanto produzir de um certo bem e existe uma demanda por esse bem. No problema também podem existir custos para armazenar bens e uma taxa de penalidade caso a demanda não seja atendida.

O problema é um processo de decisão sequencial com N estágios, onde em cada estágio \(k\) existe um custo de produção \(C(k,i)\) que depende do estágio e da quantidade produzida \(i\). A quantidade em estoque no início do estágio é determinada por \(s\), a demanda é \(D(k)\) e o custo de armazenagem é \(I(k,s)\). O custo de armazenagem também pode ser usado para representar uma penalidade caso a demanda não seja atendida.

A função custo é:

\[f(k,s) = min_{i}\{C(k,i) + I(k,i) + f(k+1, s + i - D(k))\}\]

A condição que encerra o processo é \(f(k,s) = I(k,s)\) quando \(k = n\).

O livro sugere a seguinte situação:

A demanda \(D(k) = 1\) com chance \(p = 0.6 \) e \(D(k) = 2\) com chance \((1 - p)\).

A função \(I(k,s) = 1.1i ; i >=0\) e \(I(k,s) = -1.5i ; i <0\)</p>

Logo, o problema fica:

\[f(k,s) = min_{i}\{C(k,i) + I(k,i) +p f(k+1, s + i - 1) + (1-p)f(k+1, s + i - 2)\}\]

O livro dá como exemplo os casos \(f(1,0) = 42.244\) produzindo 2 unidades inicialmente e \(f(2,1) = 19.9\) e \(f(2,0) = 28.26\)

É interessante também olhar o seguinte exercício:
Exercício complementar

Answer 1

Implementação:

p = 0.6;
n = 4;
q = [0 , 1, 2];
custo = [0, 10, 19];

def penalidade(s):
    if s > 0:
        return 1.1*s;
    else:
        return -1.5*s;


def custo(q):
    custo = [0, 10, 19];
    if q < 0:
        return 30000;
    else:
        return custo[q];

def prod(k,s):
    lista = []
    resultado = 0;
    for i in (q):
        if k > n:
            resultado = 0;
        else:
            resultado = custo(max(0-s,i)) + penalidade(s) + p*(min(prod(k + 1,s + max(0-s,i) - 1))) + (1-p)*(min(prod(k+1, s + max(0-s,i) - 2)))

        lista.append(resultado);
    return lista;

testes

print(prod(1,0))

[44.436, 42.676, 42.244]

print(prod(2,1))

[19.9, 20.36, 24.096000000000004]

print(prod(2,0))

[30.14, 28.799999999999997, 28.26]

Comments

Achei novamente sua implementaação muito legal!!!

Só acrescentaria que acho que na descrição do problema, onde diz

"A função I(k,s)=1.1i;i>=0 e I(k,s)=−1.5i;i<0"

o certo seria  I(k,s)=1.1s;s>=0 e I(k,s)=−1.5s;s<0e

que é como foi implementado. Também porque o custo de investário depende de qual o estoque e não quanto foi produzido nesse periodo.

Achei legal você o re-interpretar como uma penalidade, já que é estranho falar em estoque negativo (s<0)