Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2017-01-10T10:46:25Z No. of bitstreams: 1 texto completo.pdf: 410638 bytes, checksum: ed5d9e4a6b492aa4480a1c0d392e8903 (MD5) / Made available in DSpace on 2017-01-10T10:46:25Z (GMT). No. of bitstreams: 1 texto completo.pdf: 410638 bytes, checksum: ed5d9e4a6b492aa4480a1c0d392e8903 (MD5) Previous issue date: 2003-07-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho teve como objetivo apresentar dois estudos: um relacionado com a transformação de um veículo transportador de madeira e o outro com a substituição de equipamentos e máquinas. No primeiro foi utilizado um modelo matemático constituído por equações diferenciais para a determinação do momento ótimo de transformação de um veículo transportador florestal que pas- saria por duas transformações durante sua vida útil. A importância deste estudo deve-se a uma situação que vem sendo verificada no setor de transporte rodo- viário, em que veículos estão sendo transformados e continuam trabalhando em outro ramo de atividade, porém a decisão quanto ao momento ótimo de se fazer tais transformação tem sido tomada de forma arbitrária, sem preocupação com a viabilidade econômica. Para tanto desenvolveu-se um modelo utilizando equa- ções diferenciais que possibilitou a definição dos momentos ótimos das transfor- mações de uma carreta (cavalo mecânico + semi-reboque de três eixos), em caminhão truck (6x4) e posteriormente em caminhão toco (4x2), que seria retirado do processo. Os resultados obtidos foram satisfatórios, visto que, ao se comparar o método do ciclo terminal com o método proposto, observou-se um valor anual equivalente de R$4.084,06 para uma carreta que seria utilizada por nove anos e seria substituída e um valor anual equivalente de R$10.555,04 para o sistema de transformação com duração de 31 anos. A metodologia proposta se mostrou eficiente para dar suporte à tomada de decisão no que se refere aos veículos de transporte pesado, que representam um importante ativo nas empre- sas do ramo florestal. É possível maximizar o lucro do conjunto de versões utilizadas: carreta, truck e toco. No segundo estudo utilizou-se um modelo de programação dinâmica para avaliar a substituição de equipamentos. O problema foi avaliado através de um estudo de caso, com um horizonte de planejamento de dez anos. Foram considerados dois modelos utilizando programação dinâmica: em um deles a função objetivo foi de minimização dos custos e, no outro, de maximização dos lucros, no qual foi inserida a receita gerada pelo equipamento. Desse modo, foi possível definir o momento ótimo de substituição do equipa- mento e a decisão mais lucrativa dentro do horizonte de planejamento, o que foi observado por meio de uma “árvore de decisão” confeccionada a partir dos resultados obtidos na resolução. O modelo com receita utilizado no segundo trabalho é mais indicado para situações em que o equipamento gera receitas diretas, como no caso de aluguel ou frete do equipamento; outrossim, aquele que inclui apenas os custos é mais indicado para situações em que o equipamento é utilizado sem se preocupar com a geração de receitas anuais. Por meio de uma análise de sensibilidade, notou-se que, na situação em que não se inclui a receita, a decisão é mais afetada pela variação da taxa de juros utilizada. Portanto, cha- ma-se a atenção nesses modelos para a escolha da taxa de juros, que deve ser criteriosa, pois ela afeta a rentabilidade do investimento, e também para o fato de processo de substituição apresente coerência com a realidade do problema. / The objective of this work was to present two studies: one related to the transformation of a wood transport vehicle and the other related to the replacement of equipment and machines. In the first study a mathematic model composed by differential equations was used to determine the optimal time of transportation of a forest transport vehicle which would go through two transformations during its useful lifetime. The importance of this study is based on the circumstances observed in the road transport sector, in which vehicles are transformed into other uses but the decision of the optimal time to make the transformation has been done under arbitrary conditions, with no concern as to the economic feasibility. To overcome this a model using differential equations was developed to enable the definition of optimal times for the transformations of a cart (mechanic horse + semitrailer with three axes), into a truck (6x4), and later into a two-wheeled cart without springs (4x2) which would be removed of the process. The results obtained were satisfactory because by comparing the terminal cycle method, with the proposed method an annual value equivalent to R$4,084.06 was observed for a cart used during mine years and then replaced and an annual value equivalent to R$10,555.04 for the transformation system for a 31 year duration. The proposed methodology showed to be efficient to support the decision making related to heavy transport vehicles, which are important assets in forest enterprises. It is possible to maximize the profit of the set of versions if they are cart, truck and two-wheeled cart without springs. In the second study a dynamic programming model was used to evaluate the equipment replacement. The problem was evaluated through a case study for a tem years plan. Two models using dynamic programming were evaluated and in one of the models the objective was to minimize costs and in the other one the objective was to maximize profits, in which the incomes generated by the equipment were used. Through these models it was possible to define the optimal time for the equipment replacement and the most profitable decision within the tem years plan. This was observed through a “decision tree” based on the results obtained from the decision. The model with incomes used in the second work is best recommended for situations where the equipment generates direct incomes, as is the case of equipment rent or freight. The other one which includes only the costs is but recommended where the equipment is used without concern of generating annual income. Through a sensibility analysis, it was observed that in the situation where the income is not included, the decision is most affected by the variation of the interest rates used. Therefore, in this models attention must be paid to a very careful interest rate choice, because it affects investment rentability and also so that the replacement process shows coherence with reality of the problem.

Orientador : Secundino Soares Filho / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-31T21:27:59Z (GMT). No. of bitstreams: 1 Martinez_Luciana_D.pdf: 1513051 bytes, checksum: 6538c666995e04822ac7486dc8bb2c21 (MD5) Previous issue date: 2001 / Doutorado

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-07-28T12:04:17Z No. of bitstreams: 1 rafaelbrunodasilvabrandi.pdf: 13228407 bytes, checksum: 1e92e8c2fa686ddcaea1c9ed0d33b278 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-07-28T12:16:14Z (GMT) No. of bitstreams: 1 rafaelbrunodasilvabrandi.pdf: 13228407 bytes, checksum: 1e92e8c2fa686ddcaea1c9ed0d33b278 (MD5) / Made available in DSpace on 2016-07-28T12:16:14Z (GMT). No. of bitstreams: 1 rafaelbrunodasilvabrandi.pdf: 13228407 bytes, checksum: 1e92e8c2fa686ddcaea1c9ed0d33b278 (MD5) Previous issue date: 2016-02-29 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / O Sistema Elétrico Brasileiro (SEB) apresenta características peculiares devido às grandes dimensões do país e pelo fato da geração elétrica ser proveniente predominantemente de usinas hidráulicas. Como as afluências a estas usinas possuem comportamento estocástico e grandes reservatórios proporcionam ao sistema a capacidade de uma regularização plurianual, a utilização dos recursos hidráulicos deve ser planejada de forma minuciosa em um horizonte de tamanho considerável. Assim, o planejamento da operação de médio prazo compreende um período de 5 a 10 anos com discretização mensal e é realizado por uma cadeia de modelos computacionais tal que o principal modelo desta cadeia é baseado na técnica da Programação Dinâmica Dual Estocástica (PDDE). O objetivo deste trabalho é obter avanços nas metodologias de programação dinâmica atualmente utilizadas. Partindo-se da utilização da inserção iterativa de cortes, implementa-se um modelo computacional para o planejamento da operação de médio prazo baseado na metodologia de Programação Dinâmica Estocástica (PDE) utilizando uma discretização mais eficiente do espaço de estados (PDEE). Além disso, a metodologia proposta de PDE possui um critério de convergência bem definido para o problema, de forma que a inclusão da medida de risco CVaR não altera o processo de avaliação da convergência de forma significante. Dado que a inclusão desta medida de risco à PDDE convencional dificulta a avaliação da convergência do processo pela dificuldade da estimação de um limite superior válido, o critério de convergência proposto na PDEE é, então, base para um novo critério de convergência para a PDDE tal que pode ser aplicado mesmo na consideração do CVaR e não aumenta o custo computacional envolvido. Adicionalmente, obtém-se um critério de convergência mais detalhado em que as séries utilizadas para amostras de afluência podem ser avaliadas individualmente tais que aquelas que, em certo momento, não contribuam de forma determinante para a convergência podem ser descartadas do processo, diminuindo o tempo computacional, ou ainda serem substituídas por novas séries dentro de uma reamostragem mais seletiva dos cenários utilizados na PDDE. As metodologias propostas foram aplicadas para o cálculo do planejamento de médio prazo do SIN baseando-se em subsistemas equivalentes de energia. Observa-se uma melhoria no algoritmo base utilizado para a PDE e que o critério proposto para convergência da PDDE possui validade mesmo quando CVaR é considerado na modelagem. / The Brazilian National Grid (BNG) presents peculiar characteristics due to its huge territory dimensions and hydro-generation predominancy. As the water inflows to these plants are stochastic and a pluriannual regularization for system storage capacity is provided, the use of hydro-generation must be planned in an accurate manner such that it considersalongplanningperiod. So, thelong-termoperationplanning(LTOP)problemis generallysolvedbyachainofcomputationalmodelsthatconsideraperiodof5to10years ahead such that the primary model of this chain is based on Stochastic Dual Dynamic Programming (SDDP) technique. The main contribution of this thesis is to propose some improvements in Stochastic Dynamic Programming techniques usually settled on solving LTOP problems. In the fashion of an iterative cut selection, it is firstly proposed a LTOP problem solution model that uses an ecient state space discretization for Stochastic Dynamic Programming (SDP), called ESDP. The proposed model of SDP has a welldefined convergence criterion such that including CVaR does not hinder convergence analysis. Due to the lack of good upper bound estimators in SDDP when including CVaR, additional issues are encountered on defining a convergence criterion. So, based on ESDP convergence analysis, a new criterion for SDDP convergence is proposed such that it can be used regardless of CVaR representation with no extra computational burden. Moreover, the proposed convergence criterion for SDDP has a more detailed description such that forward paths can be individually assessed and then be accordingly discarded for computational time reduction, or even define paths to be replaced in a more particular resampling scheme in SDDP. Based on aggregate reservoir representation, the proposed methodsofconvergenceofSDDPandtheESDPwereappliedonLTOPproblemsrelatedto BNG. Results show improvements in SDDP based technique and eectiveness of proposed convergence criterion for SDDP when CVaR is used.

O principal objetivo dos veículos híbridos é diminuir o consumo de combustível em relação a veículos convencionais. Para isso, existe a necessidade de realizar a integração dos diferentes sistemas do trem-de-força e coordenar o seu funcionamento através de estratégias de controle. Tais estratégias são desenvolvidas e simuladas em conjunto com um modelo computacional da planta do veículo antes de serem aplicadas em uma unidade de controle eletrônica. O presente estudo tem como objetivo analisar o gerenciamento de energia em um veículo híbrido elétrico não-plugin do tipo série-paralelo visando à diminuição de consumo de combustível. O método de otimização global é utilizado para encontrar as variáveis de controle que resultam no mínimo consumo de combustível em um determinado ciclo de condução. Na primeira etapa, um modelo computacional da planta do veículo e da estratégia de controle não-ótima são criados. Os resultados obtidos da simulação são então comparados com dados experimentais do veículo operando em dinamômetro de chassis. A seguir, o método de otimização global é aplicado ao modelo computacional utilizando programação dinâmica e tendo como objetivo a minimização do consumo de combustível total ao final do ciclo. Os resultados mostram considerável redução do consumo de combustível utilizando otimização global e tendo como variável de controle não só a razão de distribuição de torque mas também os pontos de operação do motor de combustão. Os modelos computacionais criados nesse trabalho são disponibilizados e podem ser usados para o estudo de diferentes estratégias de controle para veículos híbridos. / The main goal of hybrid electric vehicles is to decrease engine emission and fuel consumption levels. In order to realize this, one must perform the powertrain system integration and coordinate its operation through supervisory control strategies. These control strategies are developed in a simulation environment containing the plant model of the powertrain before they can be implemented in a real-time control unit. The goal of this work is to analyze the energy management strategy which minimizes the fuel consumption in a series-parallel non-plugin hybrid electric vehicle. Global optimization is used for finding the control variables that result in the minimum fuel consumption for a specific driving cycle. In a first stage, a computational model of vehicle plant and non-optimal control strategy are created. The results from the simulation are compared against experimental data from chassis dynamometer tests. Next, a global optimization strategy is applied using dynamic programming in order to minimize total fuel consumption at the end of the driving cycle. The results from the optimization show a considerable fuel consumption reduction having as control variables not only the torque-split strategy but also the engine operating points. As contribution from this work, the computational models are made available and can be used for analyzing different control strategies for hybrid vehicles.

O problema de controle de estoques com demanda não estacionária e lead-time positivo tem se tornado cada vez mais relevante em virtude da crescente tendência de redução do ciclo de vida dos produtos e internacionalização das cadeias de suprimentos. Embora haja uma solução exata para a minimização do custo esperado da política de estoques para este cenário, baseado no método de programação dinâmica, o custo computacional deste método ainda é considerado elevado. Este trabalho detalha e avalia através de simulação o método exato e duas aproximações para a minimização do custo esperado da política de estoques, em termos do desempenho em custo e eficiência computacional. Os resultados experimentais permitem a análise dos métodos disponíveis. Enquanto a abordagem heurística de Bollapragada e Morton, que utiliza o nivelamento da demanda não estacionária, perde desempenho de custo com o aumento do lead-time, a nova heurística proposta, que aproxima os parâmetros da política ótima por valores limitantes, produz resultados sucessivamente melhores com o aumento do lead-time. / The inventory control problem with nonstationary demand and positive lead-time has become increasingly important due to the growing trend of reduction in product life cycle and internationalization of the supply chain. Although there is an exact solution to the minimization of the expected cost of inventory policy on this environment, through the method of dynamic programming, the computational cost of this method is still considered high. This work details and evaluates through simulation the exact method and two heuristic solutions for the minimization of expected cost of inventory policy, in terms of cost performance and computational efficiency. The experimental results allow the analysis of the available methods. While the Bollapragada and Morton heuristic approach, which levels the non-stationary demand, decreases the cost performance when lead-time is increased, the new heuristic proposed, that approximates the optimal policy parameters by limiting values, successively produces better results with increasing lead-times.

O planejamento da operação energética em sistemas hidrotérmicos de potência com um único reservatório tem como objetivo determinar a participação de usinas hidrelétricas e térmicas de forma a garantir o suprimento de energia demandada ao menor custo operacional possível, dentro de restrições físicas e técnicas do modelo. Alguns fatores tornam a solução deste problema bastante complexa destacando a não linearidade e a não separabilidade temporal aditiva. O objetivo deste trabalho é apresentar uma nova abordagem com tratamento agregado das afluências, descrevendo uma nova caracterização das distribuições de probabilidades e um novo modelo para a programação dinâmica estocástica markoviana. Nesse novo modelo da programação dinâmica estocástica markoviana, agregações plurimensais de vazões são utilizadas como entrada em um modelo de programação dinâmica estocástica markoviana modificado para discretizações temporais plurimensais. A nova abordagem proposta foi simulada em diferentes usinas hidrelétricas brasileiras localizadas em diferentes regiões geográficas e sob diferentes regimes hidrológicos. Os resultados das simulações feitas com a utilização deste novo modelo são apresentados e comparados ao modelo de programação dinâmica estocástica markoviana mensal, atualmente utilizado no setor elétrico brasileiro, com economia de custos relativas superiores a 10% em alguns casos. / The energetic operation planning on hydrothermal power systems with a single reservoir aims to determine the participation of hydroelectric power plants and thermal power plants to guaranty supply of energy demanded with the smallest possible cost, under physical and technical model boundaries. Some points became the solution of this problem complex, highlighting the non linearity and the additive non time separability. The objective of this paper is show the new approach with aggregated inflows, describing a new probability distributions featuring and a new model for the markovian stochastic dynamic programming. On this new model of markovian stochastic dynamic programming, multi monthly inflow aggregations are used as input in a model of markovian stochastic dynamic programming modified for multi months discretizations. The new approach proposed was simulated on differents Brazilian hydroelectric power plants located on different regions and under different hydrologic regime. The results of simulations using this new model are presented and compared to the model of monthly markovian dynamic programming, nowadays used on the Brazilian electrical sector, with relatives economic savings up to 10% in some cases.

Nesta tese, apresentamos uma metodologia concreta para calcular os controles -ótimos para sistemas estocásticos não-Markovianos. A análise trajetória a trajetória e o uso da estrutura de discretização proposta por Leão e Ohashi [36] conjuntamente com argumentos de seleção mensuráveis, nos forneceu uma estrutura para transformar um problema infinito dimensional para um finito dimensional. Desta forma, garantimos uma descrição concreta para uma classe bastante geral de problemas. / In this thesis, we present a concrete methodology to calculate the -optimal controls for non-Markovian stochastic systems. A pathwise analysis and the use of the discretization structure proposed by Leão and Ohashi [36] jointly with measurable selection arguments, allows us a structure to transform an infinite dimensional problem into a finite dimensional. In this way, we guarantee a concrete description for a rather general class of stochastic problems.

This study considers a vehicle routing problem with time windows, accessibility restrictions on customers and a fleet that is heterogeneous with regard to capacity, average speed and cost. A vehicle can perform multiple routes per day, all starting and ending at a single depot, and it is assigned to a single driver, whose total work hours are limited. The available fleet is divided into an owned fleet, for which a variable cost is incurred, and a chartered fleet, for which only a fixed cost is incurred for each vehicle used. A column generation algorithm embedded in a branch-and-bound framework is proposed. The column generation pricing subproblem required a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performing multiple routes per day and to address the need to determine the workdays start time within the planning horizon. To make the algorithm efficient, a constructive heuristic and a learning metaheuristic algorithm based on tabu search were also developed. Both were used on branch-and-bound tree nodes to generate a good initial solution to the linear restricted master problem; particularly, to find a good initial primal bound to the branch-and-bound tree. / Este estudo aborda um problema de roteirização de veículos com janelas de tempo, restrições de acessibilidade nos clientes e uma frota que é heterogênea em relação à capacidade de carga, velocidade média de deslocamento e custo. Um veículo pode percorrer múltiplas rotas por dia, todas começando e terminando em um mesmo depósito, e está designado a um único motorista, cujo total de horas trabalhadas no dia está limitado a um valor máximo. A frota disponível é dividida em uma frota própria, para a qual um custo variável é incorrido, e uma frota de freteiros, para a qual apenas um custo fixo é incorrido para cada veículo utilizado. Um algoritmo baseado em geração de colunas, integrado a um procedimento de branch-and-bound, é proposto neste estudo. O subproblema de precificação da geração de colunas requereu um algoritmo específico para o problema do caminho mínimo elementar com restrições sobre recursos capaz de lidar com a possibilidade de cada veículo percorrer múltiplas rotas por dia e capaz de lidar com a necessidade de determinar o instante de início do dia de trabalho do motorista dentro do horizonte de planejamento. Para tornar o algoritmo eficiente, uma heurística construtiva e uma heurística de melhoria baseada em busca tabu também foram desenvolvidos. Ambos são utilizados nos nós da árvore de branch-and-bound para gerar boas soluções iniciais para o problema mestre restrito da geração de colunas; particularmente, para encontrar um bom limitante primal inicial para a árvore de branch-and-bound.

Uma das tarefas mais básicas em bioinformática é a comparação de seqüências feita por algoritmos de alinhamento, que modelam as alterações evolutivas nas seqüências biológicas através de mutações como inserção, remoção e substituição de símbolos. Este trabalho trata de generalizações nos algoritmos de alinhamento que levam em consideração outras mutações conhecidas como rearranjos, mais especificamente, inversões, duplicações em tandem e duplicações por transposição. Alinhamento com inversões não tem um algoritmo polinomial conhecido e uma simplificação para o problema que considera somente inversões não sobrepostas foi proposta em 1992 por Schöniger e Waterman. Em 2003, dois trabalhos independentes propuseram algoritmos com tempo O(n^4) para alinhar duas seqüências com inversões não sobrepostas. Desenvolvemos dois algoritmos que resolvem este mesmo problema: um com tempo de execução O(n^3 logn) e outro que, sob algumas condições no sistema de pontuação, tem tempo de execução O(n^3), ambos em memória O(n^2). Em 1997, Benson propôs um modelo de alinhamento que reconhecesse as duplicações em tandem além das inserções, remoções e substituições. Ele propôs dois algoritmos exatos para alinhar duas seqüências com duplicações em tandem: um em tempo O(n^5) e memória O(n^2), e outro em tempo O(n^4) e memória O(n^3). Propomos um algoritmo para alinhar duas seqüências com duplicações em tandem em tempo O(n^3) e memória O(n^2). Propomos também um algoritmo para alinhar duas seqüências com transposons (um tipo mais geral que a duplicação em tandem), em tempo O(n^3) e memória O(n^2). / Sequence comparison done by alignment algorithms is one of the most fundamental tasks in bioinformatics. The evolutive mutations considered in these alignments are insertions, deletions and substitutions of nucleotides. This work treats of generalizations introduced in alignment algorithms in such a way that other mutations known as rearrangements are also considered, more specifically, we consider inversions, duplications in tandem and duplications by transpositions. Alignment with inversions does not have a known polynomial algorithm and a simplification to the problem that considers only non-overlapping inversions were proposed by Schöniger and Waterman in 1992. In 2003, two independent works proposed algorithms with O(n^4) time to align two sequences with non-overlapping inversions. We developed two algorithms to solve this problem: one in O(n^3 log n) time and other, considering some conditions in the scoring system, in O(n^3) time, both in O(n^2) memory. In 1997, Benson proposed a model of alignment that recognized tandem duplication, insertion, deletion and substitution. He proposed two exact algorithms to align two sequences with tandem duplication: one in O(n^5) time and O(n^2) memory, and other in O(n^4) time and O(n^3) memory. We propose one algorithm to align two sequences with tandem duplication in O(n^3) time and O(n^2) memory. We also propose one algorithm to align two sequences with transposons (a type of duplication more general than tandem duplication), in O(n^3) time and O(n^2) memory.

Esta dissertação aborda o problema de redução do consumo de combustível para veículos. Com esse objetivo, realiza-se o levantamento de um modelo estocástico e de seus parâmetros, o desenvolvimento de um controlador para o veículo, e análise dos resultados. O problema considera a interação com o trânsito de outros veículos, que limita a aplicação de resultados antes disponíveis. Para isto, propõe-se modelar a dinâmica do problema de maneira aproximada, usando sistemas com saltos markovianos, e levantar as probabilidades de transição dos estados da cadeia através de um modelo mais completo para o trânsito no percurso. / This dissertation deals with control of vehicles aiming at the fuel consumption optimization, taking into account the interference of traffic. Stochastic interferences like this and other real world phenomena prevents us from directly applying available results. We propose to employ a relatively simple system with Markov jumping parameters as a model for the vehicle subject to traffic interference, and to obtain the transition probabilities from a separate model for the traffic. This dissertation presents the model identification, the solution of the new problem using dynamic programming, and simulation of the obtained control.