Made available in DSpace on 2015-03-05T13:59:42Z (GMT). No. of bitstreams: 0 Previous issue date: 2 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o Problema de Roteamento de Veículos em que apenas a restrição da capacidade do veículo é considerada. O objetivo deste problema é atender a uma rede de clientes, através da criação de rotas de custo mínimo que respeitem a capacidade do veículo. Para gerar soluções para este problema uma aplicação será desenvolvida utilizando a metaheurística Busca Tabu. A Busca Tabu permite que estratégias de intensificação e diversificação sejam utilizadas para guiar a procura de boas soluções. Para esta aplicação dois tipos de movimentos geradores de vizinhança serão utilizados: a realocação de vértices e a troca de vértices entre rotas. Os resultados obtidos nesta aplicação serão comparados com resultados de heurísticas clássicas e com resultados publicados por outros autores que utilizam a Busca Tabu na abordagem do Problema de Roteamento de Veículos

Made available in DSpace on 2016-04-27T17:27:09Z (GMT). No. of bitstreams: 1 Claudiomiro Bispo.pdf: 267777 bytes, checksum: a69d97f8dafde914121b0221393d239f (MD5) Previous issue date: 2014-10-23 / This dissertation aims to study obstacles to happy life as presented in the dialogue On the Happy Life (De Beata Vita) by the philosopher Augustine of Hippo (13 November 354 28 August 430). First, Augustine s fundamental elements of life and formation are presented, especially his conception of human being created by God, whom departs from him, but for his fulfillment must return to God. However, this return, metaphorically presented by Augustine as navigation, has challenges to be faced, obstacles to be overcome because of the evil in human life. The Happy Life stands out to improper nutrition for the soul, inadequate wishes, live subject to fears, skepticism (represented by academics), the soul s impurities, the soul apart from God and pride / Esta dissertação tem por objetivo tratar dos obstáculos à vida feliz conforme apresentado no diálogo A vida feliz (De Beata Vita) do filósofo Agostinho de Hipona. (13 de novembro de 354 28 de Agosto de 430). Primeiramente são apresentados elementos fundamentais da vida e da formação de Agostinho, especialmente sua concepção do homem enquanto ser criado por Deus, que se afasta dele, mas que, para sua realização, deve voltar a ele. Entretanto, essa volta, apresentada metaforicamente por Agostinho como uma navegação, possui desafios a ser enfrentados, obstáculos a serem transpostos por causa do mal na vida humana. Em A Vida Feliz destacam-se a alimentação inadequada para a alma, desejar de modo impróprio, viver sujeitos a receios, ceticismo (representado pelos acadêmicos), as impurezas da alma, a distância da alma de Deus e o orgulho

Apresentamos o problema do transporte ótimo de Monge-Kantorovich com duas medidas de probabilidade conhecidas e que possuem suporte em um conjunto de cardinalidade finita. O objetivo é determinar condições que permitam construir um acoplamento destas medidas que minimiza o valor esperado de uma função de custo conhecida e que assume valor nulo apenas nos elementos da diagonal. Apresentamos também um resultado relacionado com a solução do problema de Monge-Kantorovich em espaços produto finitos quando conhecemos soluções para o problema nos espaços marginais. / We present the Monge-Kantorovich optimal problem with two known probability measures on a finite set. The objective is to obtain conditions that allow us to build a coupling of these measures that minimizes the expected value of a cost function that is known and is zero only on the diagonal elements. We also present a result that is related with the solution of the Monge-Kantorovich problem in finite product spaces in the case that solutions to the problem in the marginal spaces are known.

O principal objetivo desta dissertação é estudar um contraexemplo para o Décimo Quarto Problema de Hilbert no caso de dimensão n = 5, que foi apresentado por Arno van den Essen ([6]) em 2006 e que é baseado em um contraexemplo de D. Daigle e G. Freudenburg ([4]). Para isso, serão estudados os conceitos fundamentais da teoria de derivações e os princípios básicos das derivações localmente nilpotentes, bem como seus respectivos corolários. Dentre esses princípios encontra-se o Princípio 13, que garante que, se B é uma k- álgebra polinomial, digamos B = k[x1; ..., xn], (onde k é um corpo de característica zero) e D é uma derivação localmente nilpotente sobre B, então seu núcleo A = ker D satisfaz A = B &cap: Frac(A). Assim encontramos o contraexemplo esperado, ao mostrar que A não é finitamente gerado sobre k. Além disso, no apêndice deste trabalho, é dada uma prova para o caso de dimensão 1 do Décimo Quarto Problema de Hilbert. / The main objective of this thesis is to study a counterexample to the Hilberts Fourteenth Problem in dimension n = 5, which was presented by Arno van den Essen ([6]) in 2006 and that is based on a counterexample of D. Daigle and G. Freudenburg ([4]). For these purpose, we study the fundamental concepts of the theory of derivations and the basic principles of locally nilpotent derivations and their corollaries. Among these principles, Principle 13 ensures that if B is a k-algebra polynomial, say B = k[x1; ..., xn], (where k is a field of characteristic zero) and D is a locally nilpotent derivation on B, then its kernel A = ker D satisfies A = B ∩ Frac(A). Once we have proved that A is not finitely generated over k, we find the expected counterexample. In addition, in the appendix of this work is given a proof for the Hilberts Fourteenth Problemin dimension n = 1.

O estudo dos pontos singulares em campos vetoriais analíticos é um problema quase completamente resolvido. O único caso que ainda permanece insolúvel é o caso monodrômico, em que as órbitas circundam a singularidade. Em sistemas diferenciais analíticos, se p é singularidade monodrômica, então p ou é um centro, ou é um foco. O problema do centro-foco consiste em determinar condições que diferenciem os casos em que p é um foco, daqueles em que p é um centro. O tema central desta dissertação é a investigação do problema do centro-foco em sistemas diferenciais analíticos com singularidade nilpotente. Este problema é bastante estudado, uma vez que ainda não existe um algoritmo eficiente para este caso, tal como ocorre em sistemas com singularidades não degeneradas. Estudamos duas técnicas bastante distintas. A primeira faz uso da teoria das formas normais e aborda o problema da maneira clássica, dividindo-o na investigação da monodromia e no estudo da estabilidade. O outro método investiga os sistemas diferenciais com singularidades nilpotentes como limite de sistemas com singularidades não degeneradas. A fim de avaliarmos sua eficiência e compreendermos as possíveis obstruções envolvidas, aplicamos os métodos a famílias concretas de sistemas diferenciais / The study of singular points in planar analytic vector fields is a problem almost completely solved. The only case that remains open is the monodromic one, in which the orbits turn around the singularity. In analytic differential systems, if p is a monodromic singular point, then p is either a center or a focus. The center-focus problem consists in determining conditions for distinguishing between a center and a focus. The main purpose of this work is the investigation of the center-focus problem in analytic differential systems with nilpotent singular points. This problem is still widely studied, since there is no algorithm for such case, comparable to the Lyapunov method for the case of non-degenerate singularities. We studied two different methods. The first makes use of the normal form theory and deals with the problem in the classic way, splitting it up in two parts: the investigation of the monodromy and the study of the stability. The latter investigates the differential analytic systems with nilpotent singular points as limit of differential systems with nondegenerate singularities. In order to evaluate the efficiency and understand possible obstructions, we applied the two techniques to concrete families of differential systems

Neste mestrado estudamos o problema integrado de produção e distribuição (PIPD). Ao resolver o PIPD, tenta-se obter de maneira integrada as decisões de produção, controle de estoque, distribuição e roteamento de veículos. Neste tipo de problema, em cada período, um único ou múltiplos itens são produzidos e distribuídos para os clientes com o objetivo de atender uma determinada demanda a um custo total mínimo. Ou seja, no PIPD deve-se decidir quando e quanto produzir de cada item e as rotas e distribuições de cada veículo tal que o custo final, que inclui custos de produção, estoque e distribuição, seja mínimo. Estudamos o problema e modelo matemático considerado em Armentano et al. (2011). Para tratar o PIPD propomos heurísticas baseadas em programação matemática e geramos instâncias com múltiplos itens para testar o desempenho destas heurísticas. Comparamos os resultados obtidos pelas heurísticas com o solver comercial Cplex. Os resultados mostram que algumas das abordagens propostas obtiveram soluções de boa qualidade considerando as instâncias geradas. / In this work, the integrated production and vehicle routing problem (IPVRP) was studied. IPRP is solved by deciding on a integrated way the production, inventory control, distribution and vehicle routing decisions. In this type of problem, in each period, a single or multiple items are produced and distributed to costumers in order to meet a certain demand while minimizing the total cost, i.e., decide when and how much to produce of each item and the routes and distribution for each vehicle such that the final cost, which includes production, inventory and distribution costs is minimal. We considered the problem and mathematical model studied in Armentano et al. (2011). In order to deal with IPRP, heuristics based on mathematical programming were proposed together with multiple items instances to test the performance of those heuristics. We compare their results with the comercial solver Cplex. Results showed that some proposed heuristics obtained good quality solutions considering the generated instances.

Orientador: Silvio Alexandre de Araujo / Banca: Maria do Socorro Nogueira Rangel / Banca: Pedro Munari / Banca: Mauricio Cardoso de Souza / Banca: Edson Luiz França Senne / Resumo: O problema de dimensionamento de lotes é um problema de otimização da produção e consiste em determinar a quantidade de produtos a serem produzidos em cada período ao longo de um horizonte de tempo nito, de modo a atender uma demanda e otimizar uma função objetivo, por exemplo, minimizar os custos. Esta tese aborda duas extensões diferentes do problema de dimensionamento de lotes padrão. Na primeira parte, considerase o problema de dimensionamento de lotes com vários itens, tempos de preparação e máquinas paralelas distintas, e na segunda parte, o problema de dimensionamento de lotes com vários itens e preparação crossover. Para a primeira parte desta tese, em que estuda-se o problema de dimensionamento de lotes com máquina paralelas, o objetivo é aplicar diferentes métodos de solução que utilizam relaxação Lagrangiana e decomposição de Dantzig-Wolfe para obter limitantes inferiores de alta qualidade e desenvolver heurísticas Lagrangianas para obter boas soluções factíveis (limitantes superiores). Baseado em uma reformulação forte do problema como um problema de caminho mínimo e diferente da abordagem tradicional em que as restrições de ligação são as restrições de capacidade, utiliza-se as restrições de uxo, isto é as restrições de demanda, como as restrições de ligação. O objetivo desta abordagem é obter limitantes inferiores de alta qualidade e para tanto, utiliza-se três métodos de solução diferentes. No primeiro a relaxação Lagrangiana é aplicada as restrições de uxo. Para os outros dois resolve-se o problema mestre aplicando métodos de solução diferentes que combinam relaxação Lagrangiana e decomposição de Dantzig-Wolfe de forma hibrida. Duas heurísticas primais, baseadas em transferências de produção, são utilizadas para gerar soluções factíveis. Experimentos computacionais utilizando conjuntos de dados da literatura são apresentados e mostram que os métodos de... / Abstract: The lot sizing problem is a production optimization problem and consists of determining the quantity of products to be produced in each period of a nite time horizon, in order to meet the demand and optimize an objective function, for example, to minimize costs. In this thesis we address two di erent extensions of the standard lot sizing problem. In the rst part we consider the capacitated lot-sizing problem with multiple items, setup time and unrelated parallel machines and, in the second one, the capacitated lot sizing problem with multiple items and setup crossover. For the rst part of this thesis where we study the lot sizing problem with unrelated parallel machines, the aim is to apply di erent solution methods that use Lagrangian relaxation and Dantzig-Wolfe decomposition to obtain high quality lower bounds and develop Lagrangian heuristics to obtain good feasible solutions (upper bounds). Based on a strong reformulation of the problem as a shortest path problem and unlike in the traditional approach in which the linking constraints are the capacity constraints, we use the ow constraints, i.e. the demand constraints, as linking constraints. The aim of this approach is to obtain high quality lower bounds and for this we have used three di erent solution methods. In the rst one the Lagrangian relaxation is applied to the ow constraints. For the other two we solve the master problem applying solution methods that combine Lagrangian relaxation and Dantzig-Wolfe decomposition in a hybrid form. Two primal heuristics, based on transfers of production quantities, are used to generate feasible solutions. Computational experiments using data sets from the literature are presented and show that the solution methods produce lower bounds of excellent quality and competitive upper bounds, when compared with the bounds produced by other methods from the literature and by a high-performance MIP software... / Doutor

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-02-26Bitstream added on 2014-06-13T20:48:31Z : No. of bitstreams: 1 melega_gm_me_sjrp.pdf: 491033 bytes, checksum: 2ae4cff430e065db1faa96fe0c6d7304 (MD5) / Os problemas de dimensionamento de lotes consistem em determinar, em um horizonte de tempo finito, a quantidade de itens a serem produzidos para os quais há uma demanda a ser atendida e utiliza-se custos de produção, estoque e preparo. Este trabalho aborda o problema de dimensionamento de lotes em um ambiente constitíudo de várias plantas. Cada item pode ser produzido em qualquer planta é possível atender a demanda de uma determinada planta com produção proveniente de uma (ou várias outras) planta(s); para tanto, incorre-se um custo de transferência. Neste trabalho são propostas reformulações para o problema de dimensionamento de lotes com várias plantas, baseadas no problema do caminho mínimo (Shortest Path- SP) e no problema de localização de facilidades (Facility Location- FL). Alguns resultados computacionais são apresentados comparando a formulação original às reformulações apresentadas. Além disso, propôs-se, para uma das reformulações, um método de busca de limitantes inferiores, no qual a relaxação Lagrangiana é aplicada às restrições de demanda e o método do subgradiente é utilizado para atualizar os multiplicadores. A fim de verificar a qualidade dos limitantes obtidos, são apresentados experimentos computacionais com dados da literatura e estes são comparados aos obtidos com o pacote comercial CPLEX / The lot sizing problem consists of determining, in a finite time horizon, the quantity of items to be produced for which there are demands to be met and involve costs of produc-tion, inventory and setup. This work deals with the multi-plant lot sizing problem. Each item can be produced in any plant and the demand of a particular plant can be met using the production from another (or several other) plant(s); to do so, there is a transfer cost. We present reformulations for the classical problem, based on the shortest path problem (SP) and the facility location problem (FL). Some computational results are shown com-paring all formulations presented. Moreover, we propose, for one of the reformulations, a solution method to find lower bounds, where, the Lagrangian relaxation is applied to the demand constraints and the subgradient method is used to update the multipliers. Aiming to verify the quality of the lower bounds, we present computational experiments with data from literature and compare them to those obtained with commercial package CPLEX

O presente trabalho aborda um problema inverso associado a difus~ao de calor em uma barra unidimensional. Esse fen^omeno e modelado por meio da equac~ao diferencial par- cial parabolica ut = uxx, conhecida como equac~ao de difus~ao do calor. O problema classico (problema direto) envolve essa equac~ao e um conjunto de restric~oes { as condic~oes inicial e de contorno {, o que permite garantir a exist^encia de uma soluc~ao unica. No problema inverso que estudamos, o valor da temperatura em um dos extremos da barra n~ao esta disponvel. Entretanto, conhecemos o valor da temperatura em um ponto x0 xo no interior da barra. Para aproximar o valor da temperatura no intervalo a direita de x0, propomos e testamos tr^es algoritmos de diferencas nitas: diferencas regressivas, leap-frog e diferencas regressivas maquiadas. / This work deals with an inverse problem for the heat diusion in a bar of size L. This one-dimensional phenomenum is modeled by the parabolic partial dierential equation ut = uxx, known as the heat diusion equation. The classic problem (Direct Problem) involves this equation coupled to a set of constraints { initial and boundary conditions { in such a way as to guarantee a unique solution for it. The inverse problem hereby considered may be described in the following way: at one bar extreme point the temperature is un- known, but it is given at a xed interior point for all time. Three nite dierence algorithms (backward dierences, leap-frog, disguised backward dierences) are proposed and tested to approximate solutions for this problem. Keywords: Diusion equation. Finite dierences. Inverse problem.

Orientador: Maximiliano Ujevic Tonino / Disseração (mestrado) - Universidade Federal do ABC. Programa de Pós-Graduação em Física, 2011.