pesquisa operacional caso dos equipamentos

Prévia do material em texto

Universidade Federal da Paraíba 
Centro de Tecnologia 
Departamento de Engenharia de Produção 
Disciplina: Pesquisa Operacional II / Pesq. Oper. Aplic. à Eng. de Produção II 
Professor: Hugo Kramer 
 
Equipe: Amanda Cibele – 11328421 
 Karina Rocha – 11517896 
 Sheylla Monteiro – 11221768 
 Vinicius Urquiza - 11111344 
 
Problema: Reposição de equipamentos 
 
1. Introdução 
 A programaçaõ dinâmica é uma técnica matemática útil para tomar uma sequência de 
decisões inter-relacionadas. Ela fornece um procedimento sistemático para determinar a 
combinaçaõ de decisões ótimas. O problema pode ser dividido em estágios, também chamados 
de etapas, com a necessidade de estabelecer uma decisaõ política a cada estágio. A decisaõ 
tomada em um estágio particular relaciona-se com os estágios pos- teriores. Freqüentemente 
(embora nem sempre) tem-se que tomar decisões em intervalos regulares de tempo, que seraõ 
considerados estágios do problema de PD. 
 Cada estágio (ou etapa) tem um conjunto de estados associados a ele. Em geral, os 
estados representam várias condições possíveis dentro das quais o sistema poderia estar naquele 
estágio do problema. Esse conjunto de estados pode ser finito ou infinito. O efeito da decisaõ 
política é transformar o estado do estágio atual em um estado do próximo estágio. Quando o 
estado do próximo estágio é univocamente determinado pela decisaõ política sobre o estado 
atual, estaremos tratando de um problema de PD determinística. Pode ocorrer ainda que o estado 
destino dependa, além dos fatores já citados, de alguma distribuiçaõ probabilística. Neste último 
caso, estaremos diante de um problema de PD probabilística. 
 Em contraste com a PL, naõ existe uma formulaçaõ matemática padraõ para resolver toda 
a categoria de problemas de PD. Ao contrário, a PD é um tipo geral de abordagem para a soluçaõ 
de problemas, onde as equações particulares têm que ser desenvolvidas para se ajustar a cada 
situaçaõ em particular. Naõ obstante, algumas características gerais aparecem em todos os 
modelos que seraõ apresentados. 
 
2. Descrição do problema 
 Para que uma máquina ou equipamento continue em funcionamento é necessário arcar 
com um alto custo operacional. Com o decorrer do tempo, a produtividade tende a diminuir e os 
custos operacionais tendem a aumentar. Ou seja, as receitas serão menores a cada ano, isto 
implica que, depois de um certo tempo, a queda de produtividade e o aumento dos custos 
operacionais sejam tais que a decisão mais econômica seja substituir o equipamento. Então, o 
Problema da Substituição de Equipamentos consiste em decidir, dentro de um horizonte de 
tempo, qual o momento mais apropriado para a substituição de um determinado equipamento. 
 No início de cada ano, uma máquina ficará em serviço por mais um ano ou pode ser 
substituída por uma nova. Seja r(t), c(t) e s(t) a renda anual, o custo de operação e o valor 
residual, respectivamente, de uma máquina de t anos. O custo de adquirir uma nova máquina em 
qualquer ano é I. 
 
Os elementos do modelo PD são os seguintes: 
 1. O estágio i é representado pelo ano i, i = 1, 2, ..., n. 
 2. As alternativas no estágio (ano) i são para manter (K) ou substituir (R) a máquina no 
início do ano i. 
 3. O estado no estágio i é a idade da máquina no início do ano i. 
 
Dado que a máquina tem t anos ao início do ano i, definido como: 
f(t) = máxima receita líquida para os anos i, i+1, ..., n 
A equação recursiva é: 
𝑓𝑖 (𝑡) = 𝑚á𝑥 {
𝑟(𝑡) − 𝑐(𝑡) + 𝑓𝑖+1(𝑡 + 1)
𝑟(0) + 𝑠(𝑡) − 𝐼 − 𝑐(0) + 𝑓𝑖+1(1)
 
𝑓𝑛(𝑡) = 𝑚á𝑥 {
𝑟(𝑡) − 𝑐(𝑡) + 𝑠(𝑡 + 1)
𝑟(0) + 𝑠(𝑡) + 𝑠(1) − 𝐼 − 𝑐(0)
 
 
 
 
 
 
 
 
Se MANTÉM 
Se REPÕE 
 
Se MANTÉM 
Se REPÕE 
 
2.1. Definição de uma instância do problema 
 Uma empresa precisa determinar a política de reposição de equipamentos para os 
próximos 4 anos. Atualmente a empresa possui uma máquina que tem três anos. A empresa exige 
que quando uma máquina atingir 6 anos seja substituída. O custo de uma nova máquina é de 
R$100.000. A tabela a seguir apresenta os dados do problema. 
idade, t 
(anos)
receita, 
r(t) (R$)
custo 
operacional, 
c(t) (R$)
Valor de sucata, 
s(t) (R$)
0 20.000,00 200,00 
1 19.000,00 600,00 80.000,00 
2 18.500,00 1.200,00 60.000,00 
3 17.200,00 1.500,00 50.000,00 
4 15.500,00 1.700,00 30.000,00 
5 14.000,00 1.800,00 10.000,00 
6 12.200,00 2.200,00 5.000,00 
 
Tabela 1 – instância do problema 
 
 A determinação de valores viáveis para a idade da máquina em cada estágio é um pouco 
complexa. A Figura abaixo resume a rede que representa o problema. 
 
Figura 1: diagrama de representação da idade da máquina em função do ano de decisão 
 
 
 
2.2. Exemplo de solução viável para o problema 
As soluções viáveis é qualquer solução que siga os caminho do diagrama da figura 1 a cada 
ano. No primeiro ano uma solução viável seria repor o equipamento, no ano 2 pode-se repor o 
equipamento, no ano 3 podemos repor o equipamento, no ano seguinte manter o equipamento e 
no ano 5 todos os equipamentos devem ser vendidos. 
Com isso chegamos à seguinte solução viável: manter, repor, repor, manter e vender. O 
cálculo da receita é mostrado a seguir: 
 Ano 4: manter 
𝑓4(1) = 𝑟(1) − 𝑐(1) + 𝑠(1 + 1) = 19.000 – 600 + 60.000 = 78.400 
 Ano 3: repor 
𝑓3(1) = 𝑟(0) + 𝑠(1) − 𝐼 − 𝑐(0) + 𝑓3+1(1) = 20.000 + 80.000 – 100.000 – 200 + 
78.400 = 78.600 
 Ano 2: repor 
𝑓2(1) = 𝑟(0) + 𝑠(1) − 𝐼 − 𝑐(0) + 𝑓2+1(1) = 20.000 + 80.000 – 100.000 – 200 + 
78.600 = 78.800 
 Ano 1: repor 
𝑓1(3) = 𝑟(0) + 𝑠(3) − 𝐼 − 𝑐(0) + 𝑓1+1(1) = 20.000 + 50.000 – 100.000 – 200 + 
78.800 = 48.600 
 
A receita é de R$48.600,00 
A figura abaixo representa o diagrama com as decisões. 
 
 
 
Figura 2 – diagrama de decisões 
 
 
3. Programação dinâmica 
 A Programação Dinâmica desse problema corresponde a acharmos a solução ótima do 
problema através das receitas analisadas a cada estágio, ou seja, subproblemas. A Solução ótima 
seria então acharmos a maior receita a cada ano que se passa, portanto a cada estágio. A Maior 
receita correspondente a cada ano seria então a melhor solução. 
 
3.1. Definição dos subproblemas 
No início do ano 1, temos uma máquina de 3 anos de idade. Podemos substituí-la (R) por 
uma nova ou mantê-la (K) por mais um ano. Se ocorrer uma substituição, no início do ano 2 a 
nova máquina terá um 1 ano de idade. A mesma lógica é aplicada ao início dos anos 2 a 4, se 
uma máquina for substituída no início dos anos 2,3 ou 4, sua reposição terá 1 ano de idade no 
período seguinte. Além disso, se no início do ano 4 houver uma máquina de 6 anos a idade, ela 
deverá ser substituída. 
A rede mostra que, no início do ano 2, as possíveis idades da máquina são de 1 e 4 anos. 
No início do ano 3, as possíveis idades são 1,2 e 5 anos, e no início do ano 4 as idades possíveis 
são 1,2,3 e 6 anos. A rede também assume que a máquina será descartada no início do ano 5 de 
forma independente da idade. 
A solução de rede mostrada equivale a encontrar a rota mais longa (receita máxima) 
desde o início do ano 1 até o final do ano 4. Usaremos a forma tabular para resolver o problema. 
Todos os valores estão em milhares de dólares. Observe que, se uma máquina for substituída no 
ano 4 (ou seja, no final do horizonte de planejamento), sua receita líquida incluirá o valor de 
sucata, s(t), da máquina substituídae o valor de sucata, s(1), da máquina de substituição. 
 
3.2. Definição da recursão 
Dado que a máquina tem t anos ao início do ano i, definido como: 
f(t) = máxima receita líquida para os anos i, i+1, ..., n 
A equação recursiva é: 
 
𝑓𝑖 (𝑡) = 𝑚á𝑥 {
𝑟(𝑡) − 𝑐(𝑡) + 𝑓𝑖+1(𝑡 + 1)
𝑟(0) + 𝑠(𝑡) − 𝐼 − 𝑐(0) + 𝑓𝑖+1(1)
 
 
𝑓𝑛(𝑡) = 𝑚á𝑥 {
𝑟(𝑡) − 𝑐(𝑡) + 𝑠(𝑡 + 1)
𝑟(0) + 𝑠(𝑡) + 𝑠(1) − 𝐼 − 𝑐(0)
 
 
Se MANTÉM 
Se REPÕE 
 
Se MANTÉM 
Se REPÕE 
 
 Onde: 
 r(t) é a receita que cada máquina fornece dependendo da idade (t). Por exemplo, uma 
máquina nova (0 anos) gera uma receita de R$20.000,00 
 c(t) é o custo operacional em função da idade (em t) da máquina. 
 s(t) é o valor de sucata que depende de quantos anos a máquina possui no momento 
da venda. 
 I é o investimento de adquirir uma nova máquina e tem um valor fixo de 
R$100.000,00. 
 𝑓𝑖+1(𝑡 + 1) no caso de manter o equipamento, é a solução ótima (receita) do estágio 
posterior (i+1) em relação ao equipamento que terá uma idade t+1 
 𝑓𝑖+1(𝑡) no caso de manter o equipamento, é a solução ótima (receita) do estágio 
posterior (i+1) em relação ao equipamento novo. 
 
 
3.3. Exemplo de solução por programação dinâmica 
 Sabendo que no final do ano 5 todos os equipamentos virarão sucata, iniciaremos o 
problema a partir do ano 4 (ou estágio 4). A seguinte fórmula é utilizada para achar obter o 
resultado: 𝑓𝑛(𝑡) = 𝑚á𝑥 {
𝑟(𝑡) − 𝑐(𝑡) + 𝑠(𝑡 + 1)
𝑟(0) + 𝑠(𝑡) + 𝑠(1) − 𝐼 − 𝑐(0)
 em que n = 4. 
 
No ano 4 podemos observar no diagrama (figura 1) que tem-se 4 opções possíveis: 
 Manter ou repor o equipamento de 1 ano (t = 1) 
 Manter ou repor o equipamento de 2 anos (t = 2) 
 Manter ou repor o equipamento de 3 anos (t = 3) 
 Substituir o equipamento de 6 anos 
Utilizando a fórmula para resolver a primeira opção temos o seguinte cálculo: 
1º caso: se manter 
 f4(1) = r(1) – c(1) + s(2) = 19.000 – 600 + 60.000 = 78.400 
2º caso: se repor 
 f4(1) = r(0) + s(1) + s(1) – I – c(o) = 20.000 + 80.000 + 80.000 - 100.000 - 200 = 79.800 
 Como o problema é de maximização, com esses cálculos chegamos a conclusão que para 
o primeiro item do ano 4 a melhor escolha é de repor a máquina pois o valor obtido foi o maior. 
Se MANTÉM 
Se REPÕE 
 
Os resultados para os itens 2, 3 e 4 são mostrados na tabela 2. 
K R
t r(t) + s(t+1) - c(t) r(0) + s(t) +s(1) - c(t) - I f4(t) decisão
1 19 + 60 - 0,6 = 78,4 20 + 80 + 80 - 0,2 - 100 = 79,8 79,8 R
2 18,5 + 50 - 1,2 = 67,3 200 + 60 + 80 - 0,2 - 100 = 59,8 67,3 K
3 17,2 + 30 - 1,5 = 45,7 20 + 50 + 80 - 0,2 - 100 = 49,8 49,8 R
6 (deve-se substituir) 10 + 5 + 80 - 0,2 - 100 = 4,8 4,8 R
decisão do estágio 4 (em mil R$)
solução ótima
 
Tabela 2 – decisões do estágio 4 
 
 Após analisar os valores da tabela, é observado que a melhor decisão para o ano 4 é de 
repor o equipamento que possuía 1 ano. 
 
 A partir deste ponto iremos utilizar a seguinte equação reccursiva, onde já temos um 
valor para a fi+1(t+1) e fi+1(1): 
 𝑓𝑖 (𝑡) = 𝑚á𝑥 {
𝑟(𝑡) − 𝑐(𝑡) + 𝑓𝑖+1(𝑡 + 1)
𝑟(0) + 𝑠(𝑡) − 𝐼 − 𝑐(0) + 𝑓𝑖+1(1)
` 
 
No ano 3 podemos observar no diagrama que temos 3 opções possíveis: 
 Manter ou repor o equipamento novo (t = 1) 
 Manter ou repor o equipamento de 2 anos (t = 2) 
 Manter ou repor o equipamento de 5 anos (t = 5) 
Utilizando a fórmula para resolver a primeira opção temos o seguinte cálculo: 
1º caso: se manter 
 f3(1) = r(1) – c(1) + f4(2) = 19.000 – 600 + 67.300 = 85.700 
2º caso: se repor 
 F3(1) = r(0) + s(1) – I – c(o) + f4(1) = 20.000 + 80.000 - 100.000 - 200 + 79.800 = 79.600 
Como o problema é de maximização, com esses cálculos chegamos a conclusão que para 
o primeiro item do ano 3 a melhor escolha é continuar com a máquina pois o valor obtido foi o 
maior, ou seja quanto maior o valor, melhor a receita. 
 Os resultados para os itens 2 e 3 são mostrados na tabela 3, na tabela podemos ver que a 
melhor opção é manter o equipamento. 
Se MANTÉM 
Se REPÕE 
 
K R
t r(t) + c(t) + f4(t+1) r(0) + s(t) - c(0) - I + f4(1) f3(t) decisão
1 19 - 0,6 + 67,3 = 85,7 20 + 80 - 0,2 - 100 + 79,8 = 79,6 85,7 K
2 18,5 - 1,2 + 49,8 = 67,1 20 + 60 - 0,2 - 100 + 79,8 = 59,6 67,1 K
3 14 - 1,8 + 4,8 = 17 20 + 10 - 0,2 - 100 + 79,8 = 9,6 17 K
decisão do estágio 3 (em mil R$)
solução ótima
 
Tabela 3 – decisões do estágio 3 
 
No ano 2 podemos observar no diagrama acima que tem-se 2 opções possíveis: 
 Manter ou repor o equipamento 1 (t = 1) 
 Manter ou repor o equipamento de 4 anos (t = 4) 
Utilizando a fórmula para resolver a primeira opção temos o seguinte cálculo: 
1º caso: se manter 
 f2(1) = r(1) – c(1) + f3(2) = 19.000 – 600 + 67.100 = 85.500 
2º caso: se repor 
 f2(1) = r(0) + s(1) – I – c(o) + f3(1) = 20.000 + 80.000 - 100.000 - 200 + 85.700 = 85.500 
Com esses cálculos chegamos a conclusão de que manter ou repor o equipamento traz o 
mesmo custo à empresa. 
 Os resultados para o item 2 são mostrados na tabela 4 onde podemos ver que a melhor 
decisão é manter ou repor o equipamento 1. 
K R
t r(t) + c(t) + f3(t+1) r(0) + s(t) - c(0) - I + f3(1) f2(t) decisão
1 19 - 0,6 + 67,1 = 85,5 20 + 80 - 0,2 - 100 + 85,7 = 85,5 85,5 K ou R
4 15,5 - 1,7 + 19,6 = 33,4 20 + 60 - 0,2 - 100 + 85,7 = 35,5 35,5 R
decisão do estágio 2 (em mil R$)
solução ótima
 
Tabela 4 – decisões do estágio 2 
 
No ano 1 podemos observar no diagrama acima que tem apenas uma opção possível: 
 Manter ou repor o equipamento de 3 anos (t = 3) 
Utilizando a fórmula para resolver temos o seguinte cálculo: 
 
1º caso: se manter 
 f1(3) = r(3) – c(3) + f3(4) = 17.200 – 1.500 + 35.500 = 51.200 
2º caso: se repor 
 f1(3) = r(0) + s(3) – I – c(o) + f2(1) = 20.000 + 50.000 - 100.000 - 200 + 85.500 = 55.300 
A melhor opção é repor o equipamento, pois sua receita foi a maior. 
K R
t r(t) + c(t) + f2(t+1) r(0) + s(t) - c(0) - I + f2(1) f1(t) decisão
3 17,2 - 1,5 + 35,5 = 51,2 20 + 50 - 0,2 - 100 + 85,5 = 55,3 55,3 R
solução ótima
decisão do estágio 1 (em mil R$)
 
Tabela 5 – decisões do estágio 1 
 O diagrama abaixo mostra a solução ideal para o problema. No início do ano 1, dado o t = 
3, a melhor escolha é substituir a máquina. Portanto, a nova máquina terá, no ano seguinte, um 
ano de idade. No início do ano 2 em que t = 1 a máquina pode ser mantida ou substituída. Se for 
substituído, a máquina terá um ano no início do ano 3; caso contrário, a máquina terá dois anos 
no ano seguinte. O processo continua assim até o ano 4 ser alcançado. Em resumo as alternativas 
ótimas são (R, K, K, R) e (R, R, K, K). A receita total é de US $ 55.300. 
 
 
Figura 3 – diagrama com as soluções ótimas