# Algoritmo de Wagner-Whitin

O algoritmo de Wagner-Whitin, criado por Harvey M. Wagner e Thomson M. Whitin em 1958, é uma técnica matemática complexa para o dimensionamento de lotes e que faz uma avaliação das várias formas possíveis de se efectuar uma encomenda de maneira a satisfazer as exigências em cada período do horizonte de planeamento (Dicionário, 2008).
Este algoritmo apenas se aplica a produtos com procura determinística discreta, utilizando a programação dinâmica para minimização dos custos associados à gestão dos stocks e para se obter as quantidades óptimas de encomenda (Gestão, 2008).
Existem duas propriedades que a solução óptima deste algoritmo tem de satisfazer (Gonçalves, 2000, p. 32):
* Uma encomenda só chega quando o nível de stocks atinge o zero.
* Existe um limite superior para o número de períodos para os quais uma encomenda durará.
O algoritmo de Wagner-Whitin, normalmente é utilizado como benchmark para avaliação de modelos alternativos, pois conduz a soluções óptimas. No entanto, é frequente que se adoptem modelos mais simples para a resolução deste tipo de problemas devido à sua complexidade (Gestão, 2008).

## Formulação de Gonçalves

Para este algoritmo utilizam-se as seguintes variáveis:
* $C_{t,N+1}$ = custo do conjunto de encomendas desde o início do período $t$ até ao início do período $N+1$. $C_{i,i}=0$ e o início de um período corresponde ao fim do período anterior.
* $E_{t,k}$ = custo de uma encomenda que chega no período $t$ e que satisfaz a procura até ao início do período $k$.
Equação:
O custo da solução óptima é dado por $C_{1,N+1}$. Este algoritmo tem início no último período N e repete-se até ao período 1 (Gonçalves, 2000, p. 33).
Para a segunda propriedade, que se justifica pelo facto de um aumento do número de períodos aumentar os custos de posse de tal maneira que é melhor fazer uma nova encomenda, utiliza-se a seguinte expressão (Gonçalves, 2000, p. 33, 38):
Esta propriedade diz que, quando o custo de posse da quantidade $D(t)$ é maior que o custo de encomenda, $A$, então a solução óptima deverá ter uma encomenda que chegue no período $t$ (Gonçalves, 2000, p. 38).

## Formulação de Tersine

Tersine utiliza uma nomenclatura diferente da de Gonçalves (Tersine, 1988, p. 165):
* $C$ = custo de uma encomenda
* $h$ = fracção do custo de posse por período
* $P$ = custo unitário
* $Q_{ce}$ = $\sum _{k=c}^{e}R_{k}$
* $R_{k}$ = procura no período $k$
Segundo Tersine (1988, p. 165) este algoritmo resolve-se em três etapas:
1. Para todas as alternativas possíveis de encomendas, para um horizonte de tempo de $N$ períodos, calcular a matriz dos custos variáveis totais. Definir $Z_{ce}$ como o custo variável total nos períodos $c$ a $e$, de fazer uma encomenda no período $c$ que satisfaz as necessidades dos períodos $c$ a $e$
2. Definir $f_{e}$ como o mínimo custo possível nos períodos 1 a $e$. O algoritmo começa com $f_{0}=0$ e calcula $f_{1},f_{2},$…, $f_{N}$por esta ordem. O valor de $f_{e}$ é calculado usando a fórmula:
3. De maneira a traduzir a solução óptima $f_{N}$, obtida pelo algoritmo, em quantidades a encomendar, aplicar o seguinte:
* A encomenda final ocorre no período $w$ e é suficiente para satisfazer a procura nos períodos $w$ a $N$.
* A penúltima encomenda ocorre no período $v$ e é suficiente para satisfazer a procura nos períodos $v$ a $w$.
* A primeira encomenda ocorre no período 1 e é suficiente para satisfazer a procura nos períodos 1 até ${u-1}$.
Exemplo da aplicação deste algoritmo (Tersine, 1988, p. 166):
Um artigo tem um custo unitário de 50 UM, custo de encomenda de 100 UM e uma fracção do custo de posse por período de 0,02. Suponha-se que o nível das existências, no início do período 1, é zero e as procuras são as seguintes:
| Período | 1 | 2 | 3 | 4 | 5 | 6 |
| Procura | 75 | 0 | 33 | 28 | 0 | 10 |
A matriz dos custos variáveis totais é calculada da seguinte maneira:
$Z_{11}$ = 100 + 1(75 – 75) = 100
$Z_{12}$ = 100 + 1[(75 – 75) + (75 – 75)] = 100
$Z_{13}$ = 100 + 1[(108 – 75) + (108 – 75) + (108 – 108)] = 166
$Z_{14}$ = 100 + 1[(136 – 75) + (136 – 75) + (136 – 108) + (136 – 136)] = 250
$Z_{15}$ = 100 + 1[(136 – 75) + (136 – 75) + (136 – 108) + (136 – 136) + (136 – 136)] = 250
$Z_{16}$ = 100 + 1[(146 – 75) + (146 – 75) + (146 – 108) + (146 – 136) + (146 – 136) + (146 – 146)] = 300
$Z_{22}$ = 100 + 1(0 – 0) = 100
$Z_{23}$ = 100 + 1[(33 – 0) + (33 – 33)] = 133
$Z_{24}$ = 100 + 1[(61 – 0) + (61 – 33) + (61 – 61)] = 189
$Z_{25}$ = 100 + 1[(61 – 0) + (61 – 33) + (61 – 61) + (61 – 61)] = 189
$Z_{26}$ = 100 + 1[(71 – 0) + (71 – 33) + (71 – 61) + (71 – 61) + (71 – 71)] = 229
$Z_{33}$ = 100 + 1(33 – 33) = 100
$Z_{34}$ = 100 + 1[(61 – 33) + (61 – 61)] = 128
$Z_{35}$ = 100 + 1[(61 – 33) + (61 – 61) + (61 – 61)] = 128
$Z_{36}$ = 100 + 1[(71 – 33) + (71 – 61) + (71 – 61) + (71 – 71)] = 158
$Z_{44}$ = 100 + 1(28 – 28) = 100
$Z_{45}$ = 100 + 1[(28 – 28) + (28 – 28)] = 100
$Z_{46}$ = 100 + 1[(38 – 28) + (38 – 628) + (38 – 38)] = 120
$Z_{55}$ = 100 + 1(0 – 0) = 100
$Z_{56}$ = 100 + 1[(10 – 0) + (10 – 10)] = 110
$Z_{66}$ = 100 + 1(10 – 10) = 100
O mínimo custo possível nos períodos 1 a $e$ é determinado da seguinte maneira (Tersine, 1988, p. 167):
$f_{0}=0$
$f_{1}=min\left(Z_{11}+f_{0}\right)$ = (100 + 0) = 100
$f_{2}=min\left(Z_{12}+f_{0},Z_{22}+f_{1}\right)=min\left(100+0,100+100\right)$ = 100
$f_{3}=min\left(Z_{13}+f_{0},Z_{23}+f_{1},Z_{33}+f_{2}\right)=min\left(166+0,133+100,100+100\right)$ = 166
$f_{4}=min\left(Z_{14}+f_{0},Z_{24}+f_{1},Z_{34}+f_{2},Z_{44}+f_{3}\right)=min\left(250+0,189+100,128+100,100+166\right)$ = 228
$f_{5}=min\left(Z_{15}+f_{0},Z_{25}+f_{1},Z_{35}+f_{2},Z_{45}+f_{3},Z_{55}+f_{4}\right)=min\left(250+0,189+100,128+100,100+166,100+228\right)$ = 228
$f_{6}=min\left(Z_{16}+f_{0},Z_{26}+f_{1},Z_{36}+f_{2},Z_{46}+f_{3},Z_{56}+f_{4},Z_{66}+f_{5}\right)=min\left(300+0,229+100,158+100,120+166,110+228,100+228\right)$ = 258
Neste exemplo, $f_{6}=f_{N}$ é a combinação de $Z_{36}$ e $f_{2}$, deste modo a última encomenda é efectuada no período 3 e vai satisfazer as necessidades dos períodos 3 a 6; $f_{2}$ é a combinação de $Z_{12}$ e $f_{0}$, deste modo a encomenda é feita no período 1 e vai satisfazer as necessidades dos períodos 1 a 2. A programação óptima das encomendas e os custos variáveis cumulativos são os seguintes (Tersine, 1988, p. 168):