Esta tese de mestrado se propõe a resolver alguns problemas interessantes na área de Computação e Matemática, utilizando técnicas de Análise Combinatória, Teoria dos Grafos, Funções Geratrizes, Programação Dinâmica e Álgebra Linear. No decorrer da tese são abordados 3 problemas cujas soluções apresentam enfoque original, sob o ponto de vista da Teoria da Computação. O primeiro problema é o problema de Ulam (no capítulo referente a este problema, um novo algoritmo heurístico que interpreta o papel de um dos jogadores é apresentado). O segundo problema trata da contagem do número de matrizes de sinais alternantes e o último problema trata da contagem do número recobrimentos por dominós de uma dada figura plana (ou pareamentos perfeitos em grafos bipartidos).

Esta tese melhora o upper bound de tempo e de espaço da resolução paralela do Subset-Sum Problem (SSP) - que é uma variante do Problema da Mochila - numa máquina PRAM SIMD CREW (Parallel Random Access Machine; Single Instruction/Multiple Data; Concurrent Read/Exclusive Write) nos dois paradigmas mais consagrados na literatura científica, isto é, tanto na abordagem através das listas como por programação dinâmica. Com relação ao primeiro paradigma, é apresentada uma paralelização ótima e adaptativa do conhecido algoritmo das duas listas de Horowitz e Sahni (JACM, 1974) numa PRAM SIMD CREW de p processadores: ela resolve o SSP de n objetos em tempo O(2n/2/p) e espaço O(2n/2), onde 1 p < 2n/2/n2. Como esse algoritmo seqüencial tem até hoje a melhor complexidade de tempo para a resolução do Problema da Mochila, então nosso algoritmo paralelo pode ser considerado, a partir de agora, como o melhor resultado teórico de toda a literatura. Além disso, são apresentados três algoritmos paralelos adaptativos baseados no paradigma da programação dinâmica, que são os primeiros a resolverem o SSP de n objetos e capacidade c em tempo o(nc/p) e espaço O(n+c) numa PRAM SIMD CREW de p processadores. Eles melhoram as complexidades de tempo e de espaço do algoritmo de Lin e Storer, (JPDC, 1991), que vinha sendo o mais eficiente até o momento.

O planejamento da expansão da capacidade de sistemas elétricos visa garantir o fornecimento futuro de energia elétrica. A busca por esse objetivo deve ser feita tendo em vista critérios como custos, tecnologias disponíveis, confiabilidade e impactos ambientais. No presente trabalho, o foco são os objetivos de mínimos custos e mínimas emissões de gases de efeito estufa, da geração elétrica. No contexto global atual, esse planejamento representa um grande desafio. Sendo uma atividade de grande importância para o desenvolvimento dos países, envolve, além das incertezas próprias da atividade, também as incertezas das políticas energéticas, as quais dependem de outras agendas políticas da administração em turno. Além disso, uma vez que a geração de energia é baseada em muitos casos em recursos naturais sensíveis às condições climáticas, o processo de planejamento também deve lidar com a incerteza da mudança climática. Dessa forma, são necessários planos flexíveis capazes de antecipar possíveis mudanças (resultado das incertezas mencionadas) e evitar o desvio dos objetivos iniciais, que levariam em diferentes resultados. O primeiro passo é conhecer o impacto que possíveis mudanças podem gerar nas metas iniciais. Algumas metodologias e ferramentas exploradas nesta área, normalmente consideram apenas os efeitos da mudança climática, enquanto que outras mais gerais consideram as políticas de energia ou climáticas, mas não a possibilidade de mudança nessas políticas nem a sua combinação. Ou seja, são consideradas estáticas para o período de planejamento. O presente trabalho traz como contribuição original para a área a inclusão da incerteza inerente às políticas energéticas, combinada à incerteza climática, e a avaliação o desempenho dos caminhos possíveis, identificando os mais robustos. O objetivo deste trabalho é determinar o impacto e a influência das incertezas das políticas energéticas e das mudanças climática, de forma combinada, sobre os resultados finais no planejamento da expansão da capacidade de sistemas elétricos, em termos de custos e emissões de CO2. Outros objetivos secundários incluem a identificação de políticas robustas com boa performance para qualquer cenário climático e desenvolvimento de uma abordagem de análises das mudanças climáticas e políticas. São aplicadas técnicas de otimização de expansão de capacidade para elaborar uma metodologia híbrida que combina programação dinâmica com programação linear multiobjectivo para a geração dos diferentes cenários de mudança da política energética, bem como os trade-offs. A metodologia é aplicada em uma região estudo de caso envolvendo a expansão de capacidade do subsistema elétrico sul do brasil. Resultados mostram que: (i) é possível determinar os impactos das mudanças de políticas energéticas para diferentes cenários de mudança climática a través dos trade-off de custos e emissões de CO2; (ii) é possível identificar políticas energéticas robustas; (iii) é possível identificar a influência da mudança climática no desempenho (em termos de custos e emissões de CO2) das políticas energéticas. Os resultados e métodos aqui produzidos são úteis para países em desenvolvimento e emergentes, como o Brasil, ao oferecer um marco metodológico capaz de auxiliar na programação de seus investimentos em expansão da geração de energia em ambientes com grandes incertezas, além de fornecer de uma ferramenta para o desenho de políticas energéticas e climáticas. / The planning of Power systems capacity expansion aims to guarantee the future supply of electrical energy. The pursuit of this objective should be made considering criteria such as costs, available technologies, reliability and environmental impacts. In the present work, the focus is the objectives of minimum costs and minimum emissions of greenhouse gases in the power generation. In the current global context, such planning is a major challenge. As an activity of great importance for the development of countries, it involves, in addition to the inherent uncertainties of the activity, energy policies uncertainties, which depend on other political agendas of the administration in turn. Also, since energy generation relies in many cases on climate-sensitive natural resources, the planning process must also deal with the climate change uncertainty. Hence, flexible plans are necessary to anticipate possible changes (that come up of the mentioned uncertainties) and avoid the deviation from the initial objectives, which would lead to different results. The first step is knowing the impact that possible changes can generate on the initial goals. Some methodologies and tools explored in this area consider only the effects of climate change, while others more general consider energy or climate policies, but not the possibility of change in these policies or their combination. That is, they are considered static for the planning period. The present work has as an original contribution to the area by the inclusion of the inherent uncertainty of energy policies, combined with the climatic uncertainty, and the evaluation of the possible paths, identifying the most robust ones. The objective of this work is to determine the impact and influence of energy policy and climate change uncertainties, combined, on the final results in the planning of the power systems capacity expansion regarding costs and CO2 emissions. Other secondary objectives include identifying robust policies with good performance for any climate scenario and developing a climate change and policy analysis approach. Capacity-optimization techniques are applied to develop a hybrid methodology that combines dynamic programming with multi-objective linear programming to generate different scenarios for energy policy change, as well as trade-offs. The methodology is applied in a region case study involving the capacity expansion of the Brazilian southern power subsystem. Results show that: (i) it is possible to determine the impacts of energy policy changes for different scenarios of climate change through the trade-off of costs and CO2 emissions; (ii) robust energy policies can be identified; (iii) it is possible to identify the influence of climate change on the performance (regarding costs and CO2 emissions) of energy policies. The results and methods produced here are useful for developing and emerging countries, such as Brazil, by offering a methodological framework capable of assisting in scheduling their investments in expanding energy generation in environments with significant uncertainties, as well as providing a tool for the design of energy and climate policies.

Made available in DSpace on 2014-06-12T17:37:57Z (GMT). No. of bitstreams: 2 arquivo3958_1.pdf: 1858605 bytes, checksum: 010b7efbaa0ac4aef2becd712d518c7a (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esta dissertação tem por objetivo principal propor um procedimento para resolução de problemas de controle ótimo com a utilização do Princípio do Máximo de Pontryagin e algoritmos probabilísticos, principalmente o Talus, visando melhoria da acurácia e aumento de eficiência deste processo. Para tanto, apresenta-se o desenvolvimento histórico da teoria do controle ótimo e resumem-se as principais características dos algoritmos utilizados. Além disso, uma vez definido o método, resolveram-se alguns exemplos com a finalidade de comparação de desempenho com a programação dinâmica interativa e a parametrização de controle, formas mais usuais de solução. Para completar a abordagem, sugeriram-se algumas possibilidades para utilizar o Talus na resolução de equações diferenciais. A partir disso, foi possível garantir a efetividade do objetivo inicial e propor temas para estudos futuros

Esta tese é dedicada ao estudo de modelos de otimização de carteiras de investimento multi-período. Daremos ênfase a um modelo com restrições intermediárias formulado como um problema de controle ótimo e resolvido utilizando técnicas de programação dinâmica. Serão tratados aspectos teóricos e práticos desta classe de problemas. Primeiramente faremos uma revisão das principais hipóteses dos modelos de otimização de carteiras e o caso uni-período. Analisaremos a seguir as generalizações para o caso multi-período, onde os modelos utilizam apenas restrições para o valor esperado e/ou para a variância da carteira no instante final do período analisado. Apresentaremos então o principal resultado proposto neste trabalho onde consideramos o problema de seleção ótima de ativos multi-período no qual podemos incorporar ao modelo restrições intermediárias para o valor esperado e variância da carteira durante o período de análise. A grande vantagem desta técnica é permitir o controle do valor esperado e/ou da variância da carteira ao longo de todo o horizonte de análise. Faremos uma comparação o entre as formulações apresentadas e realizaremos experimentos numéricos com o modelo proposta nesta tese. Os principais resultados originais desta tese encontram-se no Capítulo 5. No Capítulo 6 apresentamos as simulações numéricas realizadas com o modelo proposto. / The subject of this thesis is the study of multi-period portfolio optimization problems. We focus on a model with intermediate constraints formulated as an optimal control problem and solved by using dynamic programming techniques. Both theoretical and practical issues are addressed. Firstly we will analyze the main hypothesis of portfolio optimization models and the single period case. Then we will present the generalization for the multi-period case, where the models use only constraints for the expected value and variance at the final period. The main result proposed in this work considers the multi-period portfolio selection problem with intermediate constraints on the expected value and variance of the portfolio taken into account in the optimization problem. The main advantage of this technique is that it is possible to control the intermediate expected value or variance of the portfolio during the time horizon considered. Comparison between the presented formulations and numerical experiments of the proposed model will be exposed. The main original results of this thesis can be found in Chapter 5. In Chapter 6 we present numerical simulations with the proposed model.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia de Produção, Florianópolis, 2010 / Made available in DSpace on 2012-10-25T04:16:28Z (GMT). No. of bitstreams: 1 284254.pdf: 811377 bytes, checksum: 8bcc424ed5fdd32a50e501be02fe295e (MD5) / Neste trabalho é proposto um modelo de otimização para o problema de localização de instalações, alocação de demanda e operação de estoque em redes dinâmicas onde parte dos arcos desta rede está sujeita a interrupções que podem ocorrer segundo probabilidades conhecidas, respeitando um processo Markoviano. O modelo é concebido com o objetivo de integrar, numa mesma abordagem, decisões estratégicas (onde localizar) e decisões operacionais (como operar) visando proporcionar a minimização dos custos do sistema, ao mesmo tempo em que se estabelece nível de serviço para atendimento à demanda. Para resolver este modelo é desenvolvida uma estratégia que utiliza programação dinâmica estocástica, simulação, o modelo clássico de lote econômico de compra e uma adaptação do algoritmo heurístico de Teitz & Bart. Tal estratégia é implementada em um programa de computador e testes computacionais são realizados com sucesso em um estudo de caso elaborado a partir de dados hipotéticos. Os resultados obtidos e as análises realizadas demonstram a factibilidade do modelo e a aplicabilidade da estratégia de solução.

A melhora da confiabilidade em redes de distribuição de energia elétrica é um tema importante para as indústrias de fornecimento de eletricidade, devido aos regulamentos estritos em muitos países. Depois de uma falha na rede, algumas chaves são usadas para isolar a falha, enquanto outras restauram a energia a alguns consumidores. A ótima seleção das chaves que serão abertas ou fechadas para restaurar a energia é conhecido como o problema de restauração de serviço. A instalação de chaves em posições estratégicas pode reduzir o tempo de parada, e assim melhorar a confiabilidade da rede. A seleção ótima de posições para instalar chaves é conhecido como o problema de alocação de chaves. Estes dois problemas estão relacionados estreitamente. Esta dissertação estuda o problema de alocação de chaves, considerando o problema de restauração de serviço como um subproblema. Dois métodos são propostos para estimar a confiabilidade de uma rede de distribuição com um conjunto dado de chaves instaladas. O foco principal está nas heurísticas para resolver o problema composto. Propõe-se aqui métodos como busca tabu, procedimento de busca gulosa adaptativa aleatória (sigla em inglês: GRASP), e procedimento iterativo de construção por amostras com reconexão de caminhos. Também estuda-se o benefício dos métodos de construção gulosa, semigulosa, aleatória e por amostras, e estuda-se o desempenho das estratégias de busca local por amostras, primeira melhoria e melhor melhoria. Os diferentes métodos são comparados e analisados. Os resultados mostram que os métodos por amostras são baratos e levam a soluções de boa qualidade. O procedimento iterativo de construção por amostras com reconexão de caminhos é o melhor método proposto para resolver o problema composto que é proposto nesta dissertação. / The improvement of reliability in electrical power distribution networks is an important issue for electricity supply industries, due to strict regulations in many countries. After a failure in the network, some switches are used to isolate the failure, while others restore the energy to some consumers. The optimal selection of the switches to open or close to restore energy is called the service restoration problem. The installation of switches in strategic places may reduce the outage time in case of blackouts, and thus improve the reliability of the network. The optimal selection of places to install switches is called the switch allocation problem. These two problems are closely related. This dissertation studies the switch allocation problem, considering the service restoration problem as a sub-problem. Two methods are proposed to estimate the reliability of a distribution network with a given set of installed switches. The main focus is in heuristics to solve the joint problem. It proposes methods like tabu search, greedy randomized adaptive search procedure, and iterated sample construction with path relinking. It also studies the benefit of greedy, semigreedy, random, and sample construction methods, and studies the performance of sample, first improvement and best improvement local search strategies. The different methods are compared and analyzed. The results show that sample approaches are inexpensive and lead to solutions of good quality. Iterated sample construction with path relinking is the best method to solve the joint problem that is proposed in this dissertation.

O planejamento da expansão da capacidade de sistemas elétricos visa garantir o fornecimento futuro de energia elétrica. A busca por esse objetivo deve ser feita tendo em vista critérios como custos, tecnologias disponíveis, confiabilidade e impactos ambientais. No presente trabalho, o foco são os objetivos de mínimos custos e mínimas emissões de gases de efeito estufa, da geração elétrica. No contexto global atual, esse planejamento representa um grande desafio. Sendo uma atividade de grande importância para o desenvolvimento dos países, envolve, além das incertezas próprias da atividade, também as incertezas das políticas energéticas, as quais dependem de outras agendas políticas da administração em turno. Além disso, uma vez que a geração de energia é baseada em muitos casos em recursos naturais sensíveis às condições climáticas, o processo de planejamento também deve lidar com a incerteza da mudança climática. Dessa forma, são necessários planos flexíveis capazes de antecipar possíveis mudanças (resultado das incertezas mencionadas) e evitar o desvio dos objetivos iniciais, que levariam em diferentes resultados. O primeiro passo é conhecer o impacto que possíveis mudanças podem gerar nas metas iniciais. Algumas metodologias e ferramentas exploradas nesta área, normalmente consideram apenas os efeitos da mudança climática, enquanto que outras mais gerais consideram as políticas de energia ou climáticas, mas não a possibilidade de mudança nessas políticas nem a sua combinação. Ou seja, são consideradas estáticas para o período de planejamento. O presente trabalho traz como contribuição original para a área a inclusão da incerteza inerente às políticas energéticas, combinada à incerteza climática, e a avaliação o desempenho dos caminhos possíveis, identificando os mais robustos. O objetivo deste trabalho é determinar o impacto e a influência das incertezas das políticas energéticas e das mudanças climática, de forma combinada, sobre os resultados finais no planejamento da expansão da capacidade de sistemas elétricos, em termos de custos e emissões de CO2. Outros objetivos secundários incluem a identificação de políticas robustas com boa performance para qualquer cenário climático e desenvolvimento de uma abordagem de análises das mudanças climáticas e políticas. São aplicadas técnicas de otimização de expansão de capacidade para elaborar uma metodologia híbrida que combina programação dinâmica com programação linear multiobjectivo para a geração dos diferentes cenários de mudança da política energética, bem como os trade-offs. A metodologia é aplicada em uma região estudo de caso envolvendo a expansão de capacidade do subsistema elétrico sul do brasil. Resultados mostram que: (i) é possível determinar os impactos das mudanças de políticas energéticas para diferentes cenários de mudança climática a través dos trade-off de custos e emissões de CO2; (ii) é possível identificar políticas energéticas robustas; (iii) é possível identificar a influência da mudança climática no desempenho (em termos de custos e emissões de CO2) das políticas energéticas. Os resultados e métodos aqui produzidos são úteis para países em desenvolvimento e emergentes, como o Brasil, ao oferecer um marco metodológico capaz de auxiliar na programação de seus investimentos em expansão da geração de energia em ambientes com grandes incertezas, além de fornecer de uma ferramenta para o desenho de políticas energéticas e climáticas. / The planning of Power systems capacity expansion aims to guarantee the future supply of electrical energy. The pursuit of this objective should be made considering criteria such as costs, available technologies, reliability and environmental impacts. In the present work, the focus is the objectives of minimum costs and minimum emissions of greenhouse gases in the power generation. In the current global context, such planning is a major challenge. As an activity of great importance for the development of countries, it involves, in addition to the inherent uncertainties of the activity, energy policies uncertainties, which depend on other political agendas of the administration in turn. Also, since energy generation relies in many cases on climate-sensitive natural resources, the planning process must also deal with the climate change uncertainty. Hence, flexible plans are necessary to anticipate possible changes (that come up of the mentioned uncertainties) and avoid the deviation from the initial objectives, which would lead to different results. The first step is knowing the impact that possible changes can generate on the initial goals. Some methodologies and tools explored in this area consider only the effects of climate change, while others more general consider energy or climate policies, but not the possibility of change in these policies or their combination. That is, they are considered static for the planning period. The present work has as an original contribution to the area by the inclusion of the inherent uncertainty of energy policies, combined with the climatic uncertainty, and the evaluation of the possible paths, identifying the most robust ones. The objective of this work is to determine the impact and influence of energy policy and climate change uncertainties, combined, on the final results in the planning of the power systems capacity expansion regarding costs and CO2 emissions. Other secondary objectives include identifying robust policies with good performance for any climate scenario and developing a climate change and policy analysis approach. Capacity-optimization techniques are applied to develop a hybrid methodology that combines dynamic programming with multi-objective linear programming to generate different scenarios for energy policy change, as well as trade-offs. The methodology is applied in a region case study involving the capacity expansion of the Brazilian southern power subsystem. Results show that: (i) it is possible to determine the impacts of energy policy changes for different scenarios of climate change through the trade-off of costs and CO2 emissions; (ii) robust energy policies can be identified; (iii) it is possible to identify the influence of climate change on the performance (regarding costs and CO2 emissions) of energy policies. The results and methods produced here are useful for developing and emerging countries, such as Brazil, by offering a methodological framework capable of assisting in scheduling their investments in expanding energy generation in environments with significant uncertainties, as well as providing a tool for the design of energy and climate policies.

A melhora da confiabilidade em redes de distribuição de energia elétrica é um tema importante para as indústrias de fornecimento de eletricidade, devido aos regulamentos estritos em muitos países. Depois de uma falha na rede, algumas chaves são usadas para isolar a falha, enquanto outras restauram a energia a alguns consumidores. A ótima seleção das chaves que serão abertas ou fechadas para restaurar a energia é conhecido como o problema de restauração de serviço. A instalação de chaves em posições estratégicas pode reduzir o tempo de parada, e assim melhorar a confiabilidade da rede. A seleção ótima de posições para instalar chaves é conhecido como o problema de alocação de chaves. Estes dois problemas estão relacionados estreitamente. Esta dissertação estuda o problema de alocação de chaves, considerando o problema de restauração de serviço como um subproblema. Dois métodos são propostos para estimar a confiabilidade de uma rede de distribuição com um conjunto dado de chaves instaladas. O foco principal está nas heurísticas para resolver o problema composto. Propõe-se aqui métodos como busca tabu, procedimento de busca gulosa adaptativa aleatória (sigla em inglês: GRASP), e procedimento iterativo de construção por amostras com reconexão de caminhos. Também estuda-se o benefício dos métodos de construção gulosa, semigulosa, aleatória e por amostras, e estuda-se o desempenho das estratégias de busca local por amostras, primeira melhoria e melhor melhoria. Os diferentes métodos são comparados e analisados. Os resultados mostram que os métodos por amostras são baratos e levam a soluções de boa qualidade. O procedimento iterativo de construção por amostras com reconexão de caminhos é o melhor método proposto para resolver o problema composto que é proposto nesta dissertação. / The improvement of reliability in electrical power distribution networks is an important issue for electricity supply industries, due to strict regulations in many countries. After a failure in the network, some switches are used to isolate the failure, while others restore the energy to some consumers. The optimal selection of the switches to open or close to restore energy is called the service restoration problem. The installation of switches in strategic places may reduce the outage time in case of blackouts, and thus improve the reliability of the network. The optimal selection of places to install switches is called the switch allocation problem. These two problems are closely related. This dissertation studies the switch allocation problem, considering the service restoration problem as a sub-problem. Two methods are proposed to estimate the reliability of a distribution network with a given set of installed switches. The main focus is in heuristics to solve the joint problem. It proposes methods like tabu search, greedy randomized adaptive search procedure, and iterated sample construction with path relinking. It also studies the benefit of greedy, semigreedy, random, and sample construction methods, and studies the performance of sample, first improvement and best improvement local search strategies. The different methods are compared and analyzed. The results show that sample approaches are inexpensive and lead to solutions of good quality. Iterated sample construction with path relinking is the best method to solve the joint problem that is proposed in this dissertation.

O estudo da substituição de bens de capital proporciona a empresa uma visão sobre a vida útil dos seus bens e oportuniza o planejamento para efetuar, dentro de um tempo ótimo, a troca do bem atual por um substituto que possa oferecer vantagens no que diz respeito a custos de operação e manutenção, sendo possível obter com isso a maximização das receitas. Esta dissertação propõe um modelo para a avaliação da vida útil econômica de máquinas e equipamentos fazendo uso da programação dinâmica (PD) com a geração de números aleatórios por meio do método de Monte Carlo (MMC). O modelo contempla a definição das variáveis que serão utilizadas, a aplicação do método de Monte Carlo às variáveis, o cálculo dos valores presentes, os cálculos da programação dinâmica com o objetivo de definir a máxima receita, o desenvolvimento da programação com o uso do software MatLab e a validação do modelo. As simulações foram realizadas utilizando as taxas de desconto baseadas no IPCA, CDI, IGP-M, Selic e meta Selic. A utilização do método de Monte Carlo possibilitou a geração de uma série de políticas para cada simulação, sendo estas analisadas estatisticamente como forma de verificar aquela que melhor representaria a política de substituição e consequentemente definisse a vida útil econômica do bem. O modelo foi aplicado a um centro de usinagem vertical e demonstrou flexibilidade na informação dos dados de entrada ao se utilizar a programação no software MatLab. Observou-se que além de gerar uma gama de possibilidades o modelo PD+MMC pode auxiliar o tomador de decisão quanto a estratégia a ser utilizada na substituição da máquina. Os cálculos efetuados por meio do modelo PD+MMC, para um horizonte de planejamento de 15 anos, utilizando as cinco taxas de desconto, forneceram políticas de substituição com estimativas de vida útil econômica de 3 anos para as taxas CDI, Selic e meta Selic e vida útil superior a 15 anos para as taxas IPCA e IGP-M. Por meio das análises estatísticas foi possível definir que a política de substituição que apresentou maior confiabilidade foi a que utilizou o IPCA/IBGE, a qual gerou a maior receita e a maior vida útil da máquina, superior a 16 anos, apresentando significância de 77,56% para a frequência de políticas. / Submitted by Ana Guimarães Pereira (agpereir@ucs.br) on 2017-08-28T11:15:02Z No. of bitstreams: 1 Dissertacao Ricardo Plizzari.pdf: 2804449 bytes, checksum: 020b648827a0a91276c93b1a078bd672 (MD5) / Made available in DSpace on 2017-08-28T11:15:02Z (GMT). No. of bitstreams: 1 Dissertacao Ricardo Plizzari.pdf: 2804449 bytes, checksum: 020b648827a0a91276c93b1a078bd672 (MD5) Previous issue date: 2017-08-24 / The replacement study of capital goods provides to the company an overview about the useful life of its assets and provides planning for effecting, within an optimal time, the exchange of the present good by a substitute that may offer advantages with respect to Costs of operation and maintenance, being possible to obtain the maximization of revenues. This dissertation proposes a model for evaluation of economic useful life of machines and equipment making use of dynamic programming (PD) with the generation of random numbers by the Monte Carlo method (MMC). The model includes variables definition that will be used, the application of the Monte Carlo method to the variables, calculation of the present values, dynamic programming calculations with the objective of defining the maximum revenues, the programming development using MatLab software and validation of model. The simulations were performed using the discount rates based on the IPCA, CDI, IGP-M, Selic and Selic targets. The use of Monte Carlo method allowed the generation of a series of policies for each simulation, being analysed statistically as a way to verify the one that would best represent the replacement policy and consequently defined the economic useful life of the good. The model was applied to a vertical milling centre and showed flexibility in the information of the input data when using the programming in the software MatLab. It was observed that in addition to generating a range of possibilities the PD+MMC model can assist the decision maker regarding the strategy to be used in the replacement of machine. The PD + MMC calculations, for a 15-year planning horizon, using the five discount rates, provided replacement policies with economic life estimated 3-year economic life for the CDI, Selic and Selic and Useful life over 15 years for the IPCA and IGP-M rates. The PD+MMC calculations for a planning horizon of 15 years, using the five discount rates, provided replacement policies with three years useful life estimate for CDI, Selic and target Selic rates and for the IPCA and plus than fifteen years useful life for IPCA and IGP-M rates. By means of the statistical analyzes it was possible to define that the substitution policy that presented the highest reliability was the one that used the IPCA / IBGE, which generated the highest revenue and the longest useful life of the machine, over 16 years, presenting a significance of 77, 56% for policy frequency.