segunda-feira, maio 29, 2006

 

Algoritmo de Wagner-Whitin


O algoritmo de Wagner-Whitin obtém uma solução óptima, recorrendo a um modelo de programação dinâmica, para as quantidades a encomendar, num horizonte finito, dinâmico e determinístico, em que a procura de todos os períodos é satisfeita. Os períodos de tempo no horizonte de planeamento têm que ter uma dada duração fixa e as encomendas são feitas para assegurar a chegada dos materiais no início do período de tempo. O trabalho computacional deste algoritmo é reduzido pelo facto da solução óptima ter de satisfazer as seguintes duas propriedades:
O algoritmo determina a política de menor custo controlável e envolve o seguinte procedimento de três passos:

1. Calcular a matriz dos custos variáveis totais para todas as alternativas possíveis de encomendas para um horizonte de tempo de N períodos. O custo variável total inclui os custos de encomenda e de posse. Definir Zc e 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.

Zc e = C + h Pi = c, ..., e (Qc e - Qc i), para 1 ≤ ceN

onde:

C = custo de encomenda

h = custo de posse por período, em fracção do custo unitário

P = custo unitário

Qc e = ∑k = c, ..., e Rk

Rk = procura no período k

2. Definir fe como o mínimo custo possível nos períodos 1 a e, dado que o nível do stock no final do período e é zero. O algoritmo começa com f0 = 0 e calcula f1, f2, ..., fN por esta ordem. O valor de fe é calculado por ordem crescente usando a fórmula:

fe = min (Zc e + fc - 1), para c = 1, 2, ..., e

Por outras palavras, para cada período, são comparadas todas as combinações de alternativas de encomenda e estratégias suplementares fe. A melhor combinação (de mais baixo custo) é registada como sendo a estratégia fe que satisfaz as necessidades dos períodos 1 a e. O valor de fN é o custo do programa óptimo de encomendas.

3. Para traduzir a solução óptima (fN), obtida pelo algoritmo, em quantidades a encomendar, aplicar o seguinte:

fN = Zw N + fw – 1A encomenda final ocorre no período w e é suficiente
para satisfazer a procura nos períodos w a N.
fw – 1 = Zv w – 1 + fv – 1A penúltima encomenda ocorre no período v e é suficiente
para satisfazer a procura nos períodos v a w – 1.
fu – 1 = Z1 u – 1 + f0A primeira encomenda ocorre no período 1 e é suficiente
para satisfazer a procura nos períodos 1 até u – 1.


Um artigo tem um custo unitário de 50 UM, custo de encomenda de 100 UM e um custo de posse por período, em fracção do custo unitário, de 0,02. Suponha-se que o nível das existências, no inicio do período 1, é zero e as procuras são as seguintes:


Período123456
Procura750033280010


A matriz dos custos variáveis totais apresentada na Tabela 1 é calculada como se segue:

Zc e = C + h Pi = c, ..., e (Qc e - Qc i)

Z1 1 = 100 + 1 (75 – 75) = 100

Z1 2 = 100 + 1 [(75 – 75) + (75 – 75)] = 100

Z1 3 = 100 + 1 [(108 – 75) + (108 – 75) + (108 – 108)] = 166

Z1 4 = 100 + 1 [(136 – 75) + (136 – 75) + (136 – 108) + (136 – 136)] = 250

Z1 5 = 100 + 1 [(136 – 75) + (136 – 75) + (136 – 108) + (136 – 136) + (136 – 136)] = 250

Z1 6 = 100 + 1 [(146 – 75) + (146 – 75) + (146 – 108) + (146 – 136) + (146 – 136) + (146 – 146)] = 300

Z2 2 = 100 + 1 (0 – 0) = 100

Z2 3 = 100 + 1 [(33 – 0) + (33 – 33)] = 133

Z2 4 = 100 + 1 [(61 – 0) + (61 – 33) + (61 – 61)] = 189

Z2 5 = 100 + 1 [(61 – 0) + (61 – 33) + (61 – 61) + (61 – 61)] = 189

Z2 6 = 100 + 1 [(71 – 0) + (71 – 33) + (71 – 61) + (71 – 61) + (71 – 71)] = 229

Z3 3 = 100 + 1 (33 – 33) = 100

Z3 4 = 100 + 1 [(61 – 33) + (61 – 61)] = 128

Z3 5 = 100 + 1 [(61 – 33) + (61 – 61) + (61 – 61)] = 128

Z3 6 = 100 + 1 [(71 – 33) + (71 – 61) + (71 – 61) + (71 – 71)] = 158

Z4 4 = 100 + 1 (28 – 28) = 100

Z4 5 = 100 + 1 [(28 – 28) + (28 – 28)] = 100

Z4 6 = 100 + 1 [(38 – 28) + (38 – 28) + (38 – 38)] = 120

Z5 5 = 100 + 1 (0 – 0) = 100

Z5 6 = 100 + 1 [(10 – 0) + (10 – 10)] = 110

Z6 6 = 100 + 1 (10 – 10) = 100


Tabela 1. Matriz dos custos variáveis totais Zc e

e123456
c

1100100166250250300
2100133189189229
3100128128158
4100100120
5100110
6100



O mínimo custo possível nos períodos 1 a e (fe), mostrado na Tabela 2, é determinado como se segue:

fe = min (Zc e + fc - 1)

f0 = 0

f1 = min (Z1 1 + f0) = 100 + 0 =

= 100, para Z1 1 + f0

f2 = min (Z1 2 + f0, Z2 2 + f1) = min (100 + 0, 100 + 100) =

= 100, para Z1 2 + f0

f3 = min (Z1 3 + f0, Z2 3 + f1, Z3 3 + f2) = min (100 + 0, 133 + 100, 100 + 100) =

= 166, para Z1 3 + f0

f4 = min (Z1 4 + f0, Z2 4 + f1, Z3 4 + f2, Z4 4 + f3) = min (250 + 0, 189 + 100, 128 + 100, 100 + 166) =

= 288, para Z3 4 + f2

f5 = min (Z1 5 + f0, Z2 5 + f1, Z3 5 + f2, Z4 5 + f3, Z5 5 + f4) =

= min (250 + 0, 189 + 100, 128 + 100, 100 + 166, 100 + 228) =

= 288, para Z2 5 + f1

f6 = min (Z1 6 + f0, Z2 6 + f1, Z3 6 + f2, Z4 6 + f3, Z5 6 + f4, Z6 6 + f5) =

= min (300 + 0, 229 + 100, 158 + 100, 120 + 166, 110 + 228, 100 + 228) =

= 258, para Z3 6 + f2


Tabela 2. Alternativas dos custos variáveis totais e fe

e123456
c

1100100166250250300

2200233289289329
3200228228258

4266266286
5328338
6328

fe100100166228228258



Neste caso, f6 = fN é a combinação de Z3 6 e f2, de modo que a última encomenda é feita no período 3 e vai satisfazer as necessidades dos períodos 3 a 6, ou 33 + 28 + 0 + 10 = 71 unidades; f2 é a combinação de Z1 2 e f0, de modo que a encomenda é feita no período 1 e vai satisfazer as necessidades dos períodos 1 a 2, ou seja 75 + 0 = 75 unidades. A programação óptima das encomendas e os custos variáveis cumulativos são os seguintes:


Período123456
Procura7503328010
Quantidade encomendada75071000
Custos variáveis cumulativos100100238248258258


TERSINE, Richard J. – Principles of Inventory and Materials Management, 3.ª ed., Nova Iorque, North-Holland, 1988.

Comments: Enviar um comentário

Links to this post:

Criar uma hiperligação



<< Home

This page is powered by Blogger. Isn't yours?