Como podemos resolver um problema de inventário utilizando programação dinâmica?

Question

Esse problema foi retirado do livro Dynamic Programming: A Computational Tool, escrito por Art Lew and Holger Mauch.

Em um problema de inventário, temos um produto que pode ser adquirido, a um custo específico por unidade e que é consumido sob demanda em períodos específicos. Há também um custo de estocagem para armazenamento de produtos não consumidos, além de uma penalização caso a demanda não consiga ser satisfeita.

O problema é formulado como um processo de decisão sequencial com \(N\) estágios, onde a cada estágio \(k\) é realizada a decisão de comprar \(x\) unidades do produto a um custo de aquisição \(C(k, x)\), que pode depender tanto do estágio \(k\) quanto do número de unidades \(x\). O estado é \((k,s)\), onde \(k\) é o número do estágio e \(s\) é o tamanho do estoque, ou seja, a quantidade de produtos disponível no início do período.

A demanda \(D(k)\) depende do período. Se a decisão em \((k, s)\) é de comprar \(x\) unidades, então o próximo estado \((k', s')\) é \((k+1, s+x-D(k))\). O custo associado com a transição de estados é o custo de aquisição \(C(k,x)\) mais o custo de estocagem \(I(k,s,x)\) para \(s\gt0\). \(C(k,x)\) pode incluir custos iniciais para \(x \gt0\), além do custo por unidade. \(I(k,s,x)\) para \(s\lt0\) representa uma multa por não cumprir uma demanda de tamanho \(s\). Podem ser impostos restrições de capacidade \(CAP\) (número máximo de unidades compradas por período) e também de inventário \(LIM\) (capacidade máxima de estoque a cada período).

A demanda pode ser definida de maneira aleatória, mas nesse caso ela será dada por um vetor fixo \((D_0,...,D_{N-1})\) conhecido previamente. O problema então pode ser representado na forma

\[f(k,s)= \min_{x} \ \{C(k,x)+I(k,s,x)+f(k+1,s+x-D(k))\},\] com \(f(k,s)=0\) quando \(k=N\).

Queremos então resolver o problema do inventário, isto é, encontrar as decisões ótimas \(x_k\) a cada período e \(f(0,s_0)\), para as seguintes condições: \(N=4\)

\(C(k,x)=3+x,\) para \(x\gt0\)
\(C(k,0)=0\)
\(CAP=5\)
\(I(k,s,x)= \frac{s+x-D(k)}{2}\), para \(s\gt0\)
\(LIM=4\)
\(D(0)=1\)
\(D(1)=3\)
\(D(2)=2\)
\(D(3)=4\)
\(s_0=0\).

Answer 1

Utilizei uma implementação recursiva para a resolução do problema, mostrada abaixo:

Definimos os parâmetros do problema:

N = 4
CAP = 5
LIM = 4
x = [i for i in range(CAP + 1)]
s0 = 0
Dk = [1, 3, 2, 4]

Criamos as funções que irão calcular o custo tanto do estoque quanto da compra das unidades:

def custo_est(s, x, k):
    return (s+x-Dk[k])/2

def custo_uni(x):
    if x > 0:
        return 3 + x
    else:
        return 0

Definimos então, a função recursiva que resolverá o problema em questão:

def inv(k,s):
    lista = []
    resultado = 0
    for i in (x):
        if k >= N:
            resultado = 0
        elif i + s - Dk[k] < 0:
            resultado = 999
        else:
            resultado = custo_uni(i) + custo_est(s, i, k) + inv(k+1, s + i - Dk[k])[0]

        lista.append(resultado)


    return [min(lista), lista.index(min(lista))]

Por último, para recuperar a política ótima, utilizei uma função de apoio:

def GetPolicy(k, s):
    f_x = inv(k,s)[0]
    x1 = inv(k,s)[1]
    s_1 = x1 - Dk[0]
    policy = [x1]
    i = 1

    while i < N:
        xi = inv(i, s_1)[1]
        policy.append(xi)
        s_1 = s_1 + xi - Dk[i]
        i += 1

    return [f_x, policy]

Ao rodar a função com os parâmetros dados, encontrei:

GetPolicy(0,0)
[20.0,[1,5,0,4]]

Que é o resultado correto, dado no livro.

Comments

Boa noite, Athos!
Achei seu código limpo e vi que resolveu o problema de forma bem objetiva. Fiquei com dúvida apenas onde está sendo considera a parte "I(k,s,x)  para s<0 representa uma multa por não cumprir uma demanda de tamanho s.". Mas  pretendo rever o código com mais calma.