Algoritmo de Wagner-Whitin

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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):

  1. Uma encomenda só chega quando o nível de stocks atinge o zero.
  2. 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[editar | editar código-fonte]

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:

            C_{t,N+1} = min \left \{ E_{t,k} + C_{k,N+1} \right \}    t = N, …, 2, 1;  t < k \le N+1

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):

                       D(t) H \ge A  \Leftrightarrow  D(t) \ge A/H

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[editar | editar código-fonte]

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

      Z_{ce} = C + hP\sum_{i=c}^{e} Q_{ce} - Q_{ci}   1 \le c \le e \le N

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_Npor esta ordem. O valor de f_e é calculado usando a fórmula:

      f_e= min \left ( Z_{ce} + f_{c-1} \right )           c = 1, 2, …, e

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.
      f_N = Z_{wN} + f_{w-1}
  • A penúltima encomenda ocorre no período v e é suficiente para satisfazer a procura nos períodos v a w.
      f_{w-1} = Z_{vw-1} + f_{v-1}
  • A primeira encomenda ocorre no período 1 e é suficiente para satisfazer a procura nos períodos 1 até {u-1}.
      f_{u-1} = Z_{1u-1} + f_0

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

Matriz dos custos variáveis totais

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

Alternativas dos custos variáveis totais

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):

Wagner-Whitin4.jpg

Referências[editar | editar código-fonte]

  • GONÇALVES, José Fernando – Gestão de aprovisionamentos. Ed. rev. Porto: Publindústria, 2000. ISBN 978-972-95794-9-3
  • TERSINE, Richard J. – Principles of inventory and materials management. 3ª ed. New York: Elsevier Science Publishing, 1988. ISBN 978-0-444-01162-6

Ver também[editar | editar código-fonte]

Bibliografia[editar | editar código-fonte]

  • BRAMEL, Julien; SIMCHI-LEVI, David – The Logic of Logistics. New York: Springer-Verlag, 1997. ISBN 978-0-387-94921-5

Ligações externas[editar | editar código-fonte]