Mostrar código-fonte de 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 [[lote]]s 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 [[planejamento|planeamento]] <span id=refbDicionario2008>[[#refDicionario2008|(Dicionário, 2008)]]</span>.

Este [[algoritmo]] apenas se aplica a produtos com [[demanda|procura]] determinística discreta, utilizando a programação dinâmica para minimização dos [[custo]]s associados à gestão dos [[Estoque|''stocks'']] e para se obter as [[quantidade]]s óptimas de encomenda [[#refGestao2008|(Gestão, 2008)]].

Existem duas propriedades que a solução óptima deste algoritmo tem de satisfazer [[#refGoncalves2000|(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]] [[#refGestao2008|(Gestão, 2008)]].

== Formulação de Gonçalves ==

Para este algoritmo utilizam-se as seguintes [[variável|variáveis]]:

* <big><big><math>C_{t,N+1}</math></big></big> = custo do [[conjunto]] de encomendas desde o início do período <big><big><math>t</math></big></big> até ao início do período <big><big><math>N+1</math></big></big>. <big><big><math>C_{i,i}= 0</math></big></big>  e o início de um período corresponde ao fim do período anterior.

* <big><big><math>E_{t,k}</math></big></big> = custo de uma encomenda que chega no período <big><big><math>t</math></big></big> e que satisfaz a procura até ao início do período <big><big><math>k</math></big></big>.

[[Equação]]:

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

O custo da solução óptima é dado por <big><big><math>C_{1,N+1}</math></big></big>. Este algoritmo tem início no último período N e repete-se até ao período 1 [[#refGoncalves2000|(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 matemática|expressão]] [[#refGoncalves2000|(Gonçalves, 2000, p. 33, 38)]]:

                        <big><big><math>D(t) H \ge A  \Leftrightarrow  D(t) \ge A/H</math></big></big>

Esta propriedade diz que, quando o custo de posse da quantidade <big><big><math>D(t)</math></big></big> é maior que o custo de encomenda, <big><big><math>A</math></big></big>, então a solução óptima deverá ter uma encomenda que chegue no período <big><big><math>t</math></big></big> [[#refGoncalves2000|(Gonçalves, 2000, p. 38)]].

== Formulação de Tersine ==

Tersine utiliza uma nomenclatura diferente da de Gonçalves [[#refTersine1988|(Tersine, 1988, p. 165)]]:

* <big><big><math>C</math></big></big> = custo de uma encomenda

* <big><big><math>h</math></big></big> = fracção do custo de posse por período

* <big><big><math>P</math></big></big> = custo unitário

* <big><big><math>Q_{ce}</math></big></big> = <math>\sum_{k=c}^{e} R_k</math>

* <big><big><math>R_k</math></big></big> = procura no período <big><big><math>k</math></big></big>

Segundo Tersine [[#refTersine1988|(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 <big><big><math>N</math></big></big> períodos, calcular a matriz dos custos variáveis totais. Definir <big><big><math>Z_{ce}</math></big></big> como o custo variável total nos períodos <big><big><math>c</math></big></big> a <big><big><math>e</math></big></big>, de fazer uma encomenda no período <big><big><math>c</math></big></big>  que satisfaz as necessidades dos períodos <big><big><math>c</math></big></big>  a <big><big><math>e</math></big></big>
 
       <big><big><math>Z_{ce} = C + hP\sum_{i=c}^{e} Q_{ce} - Q_{ci}</math>   <math>1 \le c \le e \le N</math></big></big>

2. Definir <big><big><math>f_e</math></big></big> como o mínimo custo possível nos períodos 1 a <big><big><math>e</math></big></big>. O algoritmo começa com <big><big><math> f_0 = 0</math></big></big> e calcula <big><big><math>f_1, f_2,</math>…, <math>f_N</math></big></big>por esta ordem. O valor de <big><big><math>f_e</math></big></big> é calculado usando a fórmula:

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

3. De maneira a traduzir a solução óptima <big><big><math>f_N</math></big></big>, obtida pelo algoritmo, em quantidades a encomendar, aplicar o seguinte:

* A encomenda final ocorre no período <big><big><math>w</math></big></big> e é suficiente para satisfazer a procura nos períodos <big><big><math>w</math></big></big> a <big><big><math>N</math></big></big>.

       <big><big><math>f_N = Z_{wN} + f_{w-1}</math></big></big>

* A penúltima encomenda ocorre no período <big><big><math>v</math></big></big> e é suficiente para satisfazer a procura nos períodos <big><big><math>v</math></big></big> a <big><big><math>w</math></big></big>.

       <big><big><math>f_{w-1} = Z_{vw-1} + f_{v-1}</math></big></big>

* A primeira encomenda ocorre no período 1 e é suficiente para satisfazer a procura nos períodos 1 até <big><big><math>{u-1}</math></big></big>.

       <big><big><math>f_{u-1} = Z_{1u-1} + f_0</math></big></big>

Exemplo da aplicação deste algoritmo [[#refTersine1988|(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:

{| border="1" cellpadding="2"
!width="55"|Período
!width="25"|1
!width="25"|2
!width="25"|3
!width="25"|4
!width="25"|5
!width="25"|6
|-
|'''Procura''' ||75 ||0 ||33 ||28 ||0 ||10
|}

A matriz dos custos variáveis totais é calculada da seguinte maneira:

<big><big><math>Z_{11}</math> = 100 + 1(75 – 75) = 100</big></big>

<big><big><math>Z_{12}</math> = 100 + 1[(75 – 75) + (75 – 75)] = 100</big></big>

<big><big><math>Z_{13}</math> = 100 + 1[(108 – 75) + (108 – 75) + (108 – 108)] = 166</big></big>

<big><big><math>Z_{14}</math> = 100 + 1[(136 – 75) + (136 – 75) + (136 – 108) + (136 – 136)] = 250</big></big>

<big><big><math>Z_{15}</math> = 100 + 1[(136 – 75) + (136 – 75) + (136 – 108) + (136 – 136) + (136 – 136)] = 250</big></big>

<big><big><math>Z_{16}</math> = 100 + 1[(146 – 75) + (146 – 75) + (146 – 108) + (146 – 136) + (146 – 136) + (146 – 146)] = 300</big></big>

<big><big><math>Z_{22}</math> = 100 + 1(0 – 0) = 100</big></big>

<big><big><math>Z_{23}</math> = 100 + 1[(33 – 0) + (33 – 33)] = 133</big></big>

<big><big><math>Z_{24}</math> = 100 + 1[(61 – 0) + (61 – 33) + (61 – 61)] = 189</big></big>

<big><big><math>Z_{25}</math> = 100 + 1[(61 – 0) + (61 – 33) + (61 – 61) + (61 – 61)] = 189</big></big>

<big><big><math>Z_{26}</math> = 100 + 1[(71 – 0) + (71 – 33) + (71 – 61) + (71 – 61) + (71 – 71)] = 229</big></big>

<big><big><math>Z_{33}</math> = 100 + 1(33 – 33) = 100</big></big>

<big><big><math>Z_{34}</math> = 100 + 1[(61 – 33) + (61 – 61)] = 128</big></big>

<big><big><math>Z_{35}</math> = 100 + 1[(61 – 33) + (61 – 61) + (61 – 61)] = 128</big></big>

<big><big><math>Z_{36}</math> = 100 + 1[(71 – 33) + (71 – 61) + (71 – 61) + (71 – 71)] = 158</big></big>

<big><big><math>Z_{44}</math> = 100 + 1(28 – 28) = 100</big></big>

<big><big><math>Z_{45}</math> = 100 + 1[(28 – 28) + (28 – 28)] = 100</big></big>

<big><big><math>Z_{46}</math> = 100 + 1[(38 – 28) + (38 – 628) + (38 – 38)] = 120</big></big>

<big><big><math>Z_{55}</math> = 100 + 1(0 – 0) = 100</big></big>

<big><big><math>Z_{56}</math> = 100 + 1[(10 – 0) + (10 – 10)] = 110</big></big>

<big><big><math>Z_{66}</math> = 100 + 1(10 – 10) = 100</big></big>

[[Imagem:Wagner-Whitin2.jpg|thumb|center|600px|Matriz dos custos variáveis totais]]

O mínimo custo possível nos períodos 1 a <big><big><math>e</math></big></big> é determinado da seguinte maneira [[#refTersine1988|(Tersine, 1988, p. 167)]]:

<big><big><math>f_0 = 0</math></big></big>

<big><big><math>f_1= min \left ( Z_{11} + f_0 \right )</math> = (100 + 0) =           100</big></big>

<big><big><math>f_2= min \left ( Z_{12} + f_0, Z_{22} + f_1 \right ) = min \left ( 100 + 0, 100 + 100 \right )</math> = 100</big></big>

<big><big><math>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 )</math> = 166</big></big>

<big><big><math>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 )</math> = 228</big></big>

<big><big><math>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 )</math> = 228</big></big>

<big><big><math>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 )</math> = 258</big></big>

[[Imagem:Wagner-Whitin3.jpg|thumb|center|600px|Alternativas dos custos variáveis totais]]

Neste exemplo, <big><big><math>f_6 = f_N</math></big></big> é a combinação de <big><big><math>Z_{36}</math></big></big> e <big><big><math>f_2</math></big></big>, deste modo a última encomenda é efectuada no período 3 e vai satisfazer as necessidades dos períodos 3 a 6; <big><big><math>f_2</math></big></big> é a combinação de <big><big><math>Z_{12}</math></big></big> e <big><big><math>f_0</math></big></big>, 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 [[#refTersine1988|(Tersine, 1988, p. 168)]]:

[[Imagem:Wagner-Whitin4.jpg|thumb|center|600px]]

== Referências ==

* <div id=refDicionario2008>[[#refbDicionario2008|''Dicionário de logística GS1 Brasil'']] [Em linha]. [S.l.]: GS1 Brasil, 2008 [Consult. 14 Maio 2008]. Disponível em WWW: <URL:http://www.gs1brasil.org.br/lumis/portal/file/fileDownload.jsp?fileId=480F89A81371A66C01137233CA831C57{{Ligação inativa|1=data=maio de 2019 }}>

* <div id=refGestao2008>''Gestão de aprovisionamentos'' [Em linha]. [S.l.: s.n.], 2008. [Consult. 5 Maio 2008]. Algoritmo de Wagner-Whitin. Disponível em WWW:<URL:https://web.archive.org/web/20071229111849/http://gestor.no.sapo.pt/5sem/ga/gestao_de_aprovisionamento_teoria.htm>

* <div id=refGoncalves2000>GONÇALVES, José Fernando – ''Gestão de aprovisionamentos''. Ed. rev. Porto: Publindústria, 2000. ISBN 978-972-95794-9-3

* <div id=refTersine1988>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 ==

* [[Administração de estoques]]
* [[Algoritmo]]
* [[EOQ]]
* [[Gestão de stocks]]
* [[Heurística de Silver-Meal]]
* [[Modelo lote-a-lote]]

== Bibliografia ==

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

* GREEN, James H. - ''Production & Inventory Control Handbook'' [Em linha]. 3ª ed. USA: McGraw-Hill, 1997. [Consult. 3 Jun. 2008]. Disponível em WWW:<URL: http://www.google.pt/books?id=YVW02D29n_8C&printsec=frontcover&hl=en&source=gbs_summary_r&cad=0 ISBN 978-0-07-024428-3

* ORLICKY, Joseph; PLOSSL George W. - ''Orlicky's Material Requirements Planning'' [Em linha]. 2ª ed. New York: McGraw-Hill, 1994. [Consult. 6 Jun. 2008]. Disponível em WWW:<URL: http://books.google.com/books?id=AUZ-cbdNegkC&printsec=frontcover&hl=pt-BR&source=gbs_summary_r&cad=0 ISBN 978-0-07-050459-2

== Ligações externas ==
* [https://web.archive.org/web/20090930042415/http://www.pageflakes.com/vam/8919028 ''Page flakes'']

[[Categoria:Logística]]
[[Categoria:Algoritmos]]