Made available in DSpace on 2014-06-12T18:31:25Z (GMT). No. of bitstreams: 2 arquivo8701_1.pdf: 1516305 bytes, checksum: c60dee928595b5ce00f6d3e80c35ad52 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2007 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho, estudamos o problema restrito dos três corpos onde os primários movem-se numa órbita elíptica de colisão, isto é, o momento angular dos primários é identicamente zero e a energia é negativa. Este problema apresenta três subproblemas, a saber: o caso estritamente espacial (isto é, a partícula infinitesimal move-se no espaço); o caso planar (isto é, a partícula infinitesimal move-se num plano que contém os primários) e o caso isósceles (isto é, a partícula infinitesimal move-se em um plano ¡ perpendicular a reta que contém os primários e passando através do centro de massa dos primários). É relevante observar que a dinâmica dos primários é periódica e contém um número infinito de colisões. Assim, os primários representam um termo de for»ca periódica no sistema, fazendo com que esse sistema seja não conservativo. Esta é uma das grandes dificuldades em se obter uma descrição completa da dinâmica deste problema. Esses três subproblemas foram escritos como uma perturbação do problema de Kepler, desta maneira obtivemos uma grande quantidade de órbitas periódicas. A técnica usada para conseguirmos tais órbitas foi o método da Continuação Analítica de Poincaré. No entanto, não foi possível usar o Teorema da Função Implícita na sua forma padrão, uma vez que não temos a diferenciabilidade suficiente do campo devido ao parâmetro perturbador introduzido. Para contornar este problema, usamos o Teorema de Arenstorf, o qual exige um pouco menos do campo. No caso isósceles, o qual chamamos por problema restrito dos três corpos isósceles elíptico com colisão, obtemos mais informações sobre a dinâmica da partícula. Além de provarmos a existência de uma grande quantidade de órbitas periódicas, conseguimos mergulhar o shift de Bernoulli em uma seção conveniente do fluxo, mostrando que este problema possue uma dinâmica caótica. Além disso, construímos esta dinâmica simbólica

Magíster en Gestión de Operaciones / Dada una colección de ciudades y el costo de viajar entre cualquier par de ella, el problema del vendedor viajero, que denotaremos como TSP (traveling salesman problem en inglés), consiste en encontrar el tour menos costoso que visita todas las ciudades al menos una vez retornando al punto inicial. En su forma métrica este problema es NP-duro, y por lo tanto no existe un algoritmo en tiempo polinomial que lo resuelva, salvo que P=NP. Para el caso métrico, Christofides diseñó en el año 1976 un 3/2-algoritmo de aproximación, el cual despertó una gran curiosidad con respecto a la aproximabilidad del problema. Sin embargo, y pese a los grandes esfuerzos efectuados en investigación, el algoritmo de Christofides es el de mejor garantía hasta el día de hoy. Recientemente han habido varios mejoras importantes con respecto a la aproximabilidad en casos especiales de TSP métrico. En el año 2011 Oveis Gharan et al. diseñaron un (3/2-ε)-algoritmo de aproximación para el caso graph-TSP, donde la distancia métrica entre cada par de ciudades está dada por el menor número de arcos necesarios para conectarlas por un camino dentro de un grafo sin pesos. En el mismo año Mömke y Svensson mejoran el resultado a 1.461, mientras Mucha en el 2012 mejora la garantía del algoritmo a 13/9. En el caso de que el grafo es cúbico de n vértices y 2-conexo, el algoritmo de Mömke y Svensson entrega un tour de largo menor a (4/3)n, resultado obtenido también por Boyd et al. en el año 2011. En este trabajo estudiamos el problema graph-TSP en distintas variantes de grafos cúbicos. Primero estudiamos el caso en que el grafo es planar, cúbico, bipartito y 3-conexo, el cual es un caso interesante desde el punto de vista de teoría de grafos ya que, según la conjetura de Barnette de hace más de 40 años estos grafos serían Hamiltonianos. En esta clase de grafos, conocidos como grafos de Barnette, mostramos que en un grafo de n vértices existe un tour de largo a lo más (4/3-1/18)n. Luego relajamos las condiciones sobre el grafo, quitando la hipótesis de planaridad e imponiendo que sea cúbico, bipartito y 2-conexo, caso en el cual mostramos que existe un tour de largo a lo más (4/3-1/108)n. Finalmente, estudiamos el caso en que el grafo es solamente cúbico y 2-conexo. En este caso nos basamos en las técnicas de Boyd et al. para mostrar que existe un tour de largo a lo más (4/3-1/61236)n. En cada caso mostramos que el tour se puede encontrar en tiempo polinomial, y como n es naturalmente una cota inferior del valor de graph-TSP, cada uno de los resultados obtenidos se traduce en un algoritmo de aproximación. Además, como n es una cota inferior de la relajación de Held & Karp, que es una conocida formulación para TSP como programa lineal, obtenemos como consecuencia que el gap de integralidad de TSP con respecto a esta relajación es acotado superiormente por (4/3-1/18) para el caso de Barnette, (4/3-1/108) para el caso cúbico, bipartito y 2-conexo, y (4/3-1/61236) para el caso cúbico y 2-conexo.

Orientador: Rodney C. Bassanezi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-15T13:28:51Z (GMT). No. of bitstreams: 1 Toledo_LuciaHelenaMezzacappaMoraesde_M.pdf: 1576897 bytes, checksum: ed49be81a6a9b5db30650005131994d1 (MD5) Previous issue date: 1979 / Resumo: Não informado. / Abstract: Not informed. / Mestrado / Mestre em Matemática

Orientador : Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-15T13:14:58Z (GMT). No. of bitstreams: 1 Oliveira_AntonioCostade_M.pdf: 2077929 bytes, checksum: c7812ef3301b21c76d3b46f3491fe42f (MD5) Previous issue date: 1987 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Matemática Aplicada

Orientador: Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-20T00:13:37Z (GMT). No. of bitstreams: 1 Rangel_MariadoSocorroNogueira_M.pdf: 1539388 bytes, checksum: 1b7cb5400a240ba143c6750c03f7c7ac (MD5) Previous issue date: 1990 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Matemática Aplicada

Orientador: Silvio Alexandre de Araujo / Coorientador: Diego Jacinto Fiorotto / Banca: Mariá Cristina Vasconcelos Nascimento Rosset / Banca: Desiree Maldonado Carvalho / Resumo: O problema de dimensionamento de lotes com plantas flexíveis e custo de transporte consiste em definir quais plantas deverão ser flexíveis para produzir determinados itens e em determinar a quantidade de itens que deve ser produzida em cada planta e para quais clientes estes itens deverão ser entregues de forma a suprir as demandas predeterminadas, em um horizonte de tempo finito e dividido em períodos, levando em conta custos de produção, preparo, estoque, hora extra, flexibilidade e transporte. Neste trabalho é proposto um modelo matemático para este problema, além de uma análise computacional a fim de verificar se, com um orçamento de flexibilidade predefinido, pode-se oferecer as mesmas vantagens comparado ao orçamento de flexibilidade total. São analisados os casos de flexibilidade com plantas dedicada, plantas com flexibilidade total e algumas reduções deste nível de flexibilidade, como de 20%, 50% e 80% deste orçamento para investir em possíveis flexibilidades das plantas. Os resultados computacionais, para instâncias de tamanho pequeno indicam que é possível obter bons resultados com flexibilidade reduzida e que investir em flexibilidade é importante. Para instâncias de tamanho médio, a dificuldade em se resolver o modelo matemático não permitiu uma análise precisa sobre flexibilidade / Abstract: The lot sizing problem with flexible plants and transport costs consists in defining which plants should be flexible to produce certain items and to determine the quantity of items that should be produced in each plant and to which customers these items should be delivered in order to meet predetermined demands, in a finite time horizon divided into time periods, taking into account production, setup, inventory, overtime, flexibility and transportation costs. In this work, we propose a mathematical model for this problem, in addition to a computational analysis, in order to determine if, with a lower flexibility budget, the same benefits can be achieved compared to the total flexibility budget. We analyze the cases of flexibility with dedicated plants, plants with total flexibility and some reductions of flexibility, such as 20%, 50% and 80% of this budget to invest in possible plant flexibility. The computational results for small instances indicate that it is possible to obtain good results with reduced flexibility and that investing in flexibility is important. For medium instances, the difficulty in solving the mathematical model has not allowed an accurate analysis of flexibility / Mestre

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2008-02-27Bitstream added on 2014-06-13T19:47:35Z : No. of bitstreams: 1 santos_smpg_me_sjrp.pdf: 975189 bytes, checksum: 365d7872dbad44341fdaa7290f787b15 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho estudamos o processo produtivo de uma fábrica de móveis característica do Pólo Moveleiro de Votuporanga/SP e propomos um modelo de otimização inteira mista para o processo de produção desta fábrica acoplando o Problema de Dimensionamento de Lotes (PDL) com o Problema de Corte de Estoque (PCE) Bidimensional. O modelo considera vários itens (produtos finais), horizonte rolante de planejamento, sendo que somente o período inicial é programado detalhadamente em relação às restrições de atendimento à demanda por peças e de capacidade das máquinas. Dois conjuntos de padrões de corte são utilizados, aqueles preferidos pela empresa e um conjunto de padrões tabuleiros compostos, e visa a utilização da capacidade total de corte da máquina seccionadora. Testes computacionais fazendo várias comparações foram realizados e mostram a eficiência da abordagem quando o problema é resolvido de forma integrada e quando o conjunto de padrões de corte tabuleiros compostos é utilizado. / In this work we studied the production process of a furniture company located in Votuporanga/SP and we propose a mixed-integer optimization model for the furniture industry production process, integrating the Lot Sizing Problem with the Cutting Stock Problem. The mathematical model considers multi items (final products) in a rolling horizon basis, where only the initial period is detailed with respect to the pieces demanded and capacity machines constraints. Two cutting pattern sets are used, the industry preferred cutting patterns and a set of composed checkerboard patterns, and aims at using the total capacity of the saw machine use. Computational tests with multiple comparisons show the approach effectiveness when the problem is solved in an integrated form and when the composed checkerboard patterns set is used.

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T19:31:46Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T19:32:02Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T19:32:17Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5) / Made available in DSpace on 2017-02-01T19:32:17Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5) Previous issue date: 2016-08-04 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this work, lectures on Optimization Problems Applied Geometry. It presents initially a little history of some classic optimization problems in Euclidean Geometry Plana, as the Isoperimétrico Problem, the Heron Problem an the Steiner Problem. From there, he used that knowledge to build definitions, theorems and propositions regarding the Optimization of Geometry which provided grandiose tools for problem solving that can be applied in high school or in Mathematics Olympics. / Neste trabalho, disserta-se sobre Problemas de Otimização Aplicados à Geometria. Apresentase inicialmente um pouco da história de alguns problemas clássicos de otimização em Geometria Euclidiana Plana, como, o Problema Isoperimétrico, o Problema de Heron e o Problema de Steiner. A partir daí, usou-se esse conhecimento para construir definições, teoremas e proposições a respeito da Otimização em Geometria o que proporcionou grandiosas ferramentas para a resolução de problemas que podem ser aplicados no Ensino Médio ou em Olimpíadas de Matemática.

Esta tesis aborda el problema de distribución en planta, el cual, en líneas generales, pretende asignar o distribuir instalaciones en un sistema de producción. Existen muchos planteamientos diferentes dependiendo de la naturaleza de los talleres de trabajo consideradas de la planta industrial, por ejemplo el tipo de producto que se fabrica, la flexibilidad requerida en las rutas de procesamiento, la forma de las instalaciones, el número de niveles, etcétera. Uno de los planteamientos más abordados ha sido el problema de distribución en planta con instalaciones de áreas iguales, generalizándose como un problema de asignación cuadrática. Para solucionar este tipo de problemas, el presente trabajo desarrolla un algoritmo greedy para la distribución de las instalaciones en la planta con los siguientes tipos de naturaleza: sistema productivo por procesos, con rutas de procesamiento, presencia de equipos para el manejo de materiales en fila múltiple, distribución en un solo nivel y horizonte de planeamiento estático. El método propuesto AlgoDist minimiza el costo total del manejo de materiales considerando la métrica de distancia Manhattan y logra obtener un equilibrio adecuado entre los algoritmos tipo constructor que generan la distribución ocupando paulatinamente las posiciones del dominio de ubicación, y los algoritmos tipo mejoría que promueven la mejor solución a partir de una distribución inicial de planta. El algoritmo heurístico es bastante eficaz para la resolución de problemas de optimización combinatoria de múltiples filas, con uso de tiempo computacional mínimo. Finalmente, el rendimiento del algoritmo ha sido probado en varios casos de estudio y sus resultados fueron comparados con los obtenidos en otros trabajos citados en la bibliografía, mostrando un grado de eficiencia del 96%, pero con un bajo costo computacional.

El problema de corte y empaquetado en dos dimensiones, es un problema NP- difícil perteneciente a la familia de problemas de la optimización combinatoria. El problema combinatorio estriba en la gran cantidad de patrones de corte que puede construirse a partir de un número determinado de requerimientos y un conjunto de objetos los cuales deben ser cortados para satisfacer estos. Este problema es muy importante debido a la gran cantidad de aplicaciones que tiene en la industria. En este trabajo presentamos un estudio de los diferentes métodos que resuelven el problema, clasificándolos por métodos exactos, heurísticas y meta heurísticas. También presentamos conceptos, modelos del problema y las relaciones con otros problemas combinatorios. / -- Two dimensional cutting and packing problems is NP-hard, it belong to the family of problems of the optimization combinatory. This problem is based in the great amount of cut patterns that can be constructed from a determined number of requirements and a set of objects which must be cut to satisfy these. This problem is very important because it presents enormous applicability in the industry. In this work we presented a study of the different methods that solve the problem, classifying them by exact methods, heuristic and meta heuristic. Also we presented concepts, models and the relations with other combinatory problems.