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\).