This thesis is motivated by practical problems encountered in handling live products in the poultry processing industry, where live birds are manually transferred by human labors. As the task of handling live products is often unpleasant and hazardous, it is an ideal candidate for automation. To reduce the number of configurations and live birds to be tested, this thesis focuses on developing analytical models based on the Lagrange method to predict the effect of mechanical inversion on the shackled bird. Unlike prior research which focused on the effect of different inversion paths on the joint force/torque of a free-falling shackled bird, this thesis research examines the effect of kinematic constraints (designed to support the bird body) on the shackled bird. Unlike free-falling, the imposed kinematic constraints enable the shackled bird to rotate about its center of mass, and thus minimize wing flapping. In this thesis, birds are geometrically approximated as ellipsoids while the lower extremity is modeled as a pair of multi-joint serial manipulators. With the constraint equations formulated into a set of differential algebraic equations, the equations of motion as well as Lagrange multipliers characterizing kinematical constraints are numerically solved for the bird motion, specifically the position, velocity, and orientation and hence the forces and torques of the joints. The dynamic models are verified by comparing simulation results against those obtained using a finite element method. The outcomes of this thesis will provide some intuitive insights essential to design optimization of a live-bird transfer system.

The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved in polynomial time; with them, the CSPP is NP-hard and thus far no polynomial-time algorithms exist for solving it optimally. The problem arises in a number of practical situations. In the case of vehicle path planning, the vehicle may be an aircraft flying through a region with obstacles such as mountains or radar detectors, with an upper bound on the fuel consumption, the travel time or the risk of attack. The vehicle may be a submarine travelling through a region with sonar detectors, with a time or risk budget. These problems all involve a network which is a discrete model of the physical domain. Another example would be the routing of voice and data information in a communications network such as a mobile phone network, where the constraints may include maximum call delays or relay node capacities. This is a problem of current economic importance, and one for which time-sensitive solutions are not always available, especially if the networks are large. We consider the simplest form of the problem, large grid networks with a single side constraint, which have been studied in the literature. This thesis explores the application of Constraint Programming combined with Lagrange Relaxation to achieve optimal or near-optimal solutions of the CSPP. The following is a brief outline of the contribution of this thesis. Lagrange Relaxation may or may not achieve optimal or near-optimal results on its own. Often, large duality gaps are present. We make a simple modification to Dijkstra’s algorithm that does not involve any additional computational work in order to generate an estimate of path time at every node. / We then use this information to constrain the network along a bisecting meridian. The combination of Lagrange Relaxation (LR) and a heuristic for filtering along the meridian provide an aggressive method for finding near-optimal solutions in a short time. Two network problems are studied in this work. The first is a Submarine Transit Path problem in which the transit field contains four sonar detectors at known locations, each with the same detection profile. The side constraint is the total transit time, with the submarine capable of 2 speeds. For the single-speed case, the initial LR duality gap may be as high as 30%. The first hybrid method uses a single centre meridian to constrain the network based on the unused time resource, and is able to produce solutions that are generally within 1% of optimal and always below 3%. Using the computation time for the initial Lagrange Relaxation as a baseline, the average computation time for the first hybrid method is about 30% to 50% higher, and the worst case CPU times are 2 to 4 times higher. The second problem is a random valued network from the literature. Edge costs, times, and lengths are uniform, randomly generated integers in a given range. Since the values given in the literature problems do not yield problems with a high duality gap, the values are varied and from a population of approximately 100,000 problems only the worst 200 from each set are chosen for study. These problems have an initial LR duality gap as high as 40%. A second hybrid method is developed, using values for the unused time resource and the lower bound values computed by Dijkstra’s algorithm as part of the LR method. The computed values are then used to position multiple constraining meridians in order to allow LR to find better solutions. / This second hybrid method is able to produce solutions that are generally within 0.1% of optimal, with computation times that are on average 2 times the initial Lagrange Relaxation time, and in the worst case only about 5 times higher. The best method for solving the Constrained Shortest Path Problem reported in the literature thus far is the LRE-A method of Carlyle et al. (2007), which uses Lagrange Relaxation for preprocessing followed by a bounded search using aggregate constraints. We replace Lagrange Relaxation with the second hybrid method and show that optimal solutions are produced for both network problems with computation times that are between one and two orders of magnitude faster than LRE-A. In addition, these hybrid methods combined with the bounded search are up to 2 orders of magnitude faster than the commercial CPlex package using a straightforward MILP formulation of the problem. Finally, the second hybrid method is used as a preprocessing step on both network problems, prior to running CPlex. This preprocessing reduces the network size sufficiently to allow CPlex to solve all cases to optimality up to 3 orders of magnitude faster than without this preprocessing, and up to an order of magnitude faster than using Lagrange Relaxation for preprocessing. Chapter 1 provides a review of the thesis and some terminology used. Chapter 2 reviews previous approaches to the CSPP, in particular the two current best methods. Chapter 3 applies Lagrange Relaxation to the Submarine Transit Path problem with 2 speeds, to provide a baseline for comparison. The problem is reduced to a single speed, which demonstrates the large duality gap problem possible with Lagrange Relaxation, and the first hybrid method is introduced. / Chapter 4 examines a grid network problem using randomly generated edge costs and weights, and introduces the second hybrid method. Chapter 5 then applies the second hybrid method to both network problems as a preprocessing step, using both CPlex and a bounded search method from the literature to solve to optimality. The conclusion of this thesis and directions for future work are discussed in Chapter 6.

Diss. Stockholm : Handelshögskolan, 2002.

Neste trabalho são estudadas três metodologias de otimização não-linear: o Método da Função Lagrangeana, o Método da Função Penalidade e o Método da Função Lagrangeana Aumentada. Com o estudo da Função Lagrangeana e do Método da Função Penalidade, foi possível alcançar a formulação da Função Lagrangeana Aumentada com o objetivo de resolver problemas de programação não-linear não-convexos. Testes numéricos são apresentados para o problema não-convexo de programação não-linear conhecido como Fluxo de Potência Ótimo. / In this dissertation, three nonlinear optimization methodologies are studied: the Lagrangian Function Method, the Penalty Function Method and Augmented Lagrangian Function Method. Through the studies ofthe Lagrangian Function and the Penalty function Method, it was possible to reach the formulation of the Augmented Lagrangian Function aiming to solve nonlinear nonconvex programming problems. Numerical tests are presented for the nonconvex nonlinear programming problem known as optimal power flow.

Este trabalho apresenta uma metodologia para a alocação de fontes de reativos em sistemas de energia elétrica. A metodologia é baseada no multiplicador de Lagrange, o qual indica a sensibilidade entre a função objetivo perdas de potência ativa na transmissão, e as restrições injeções de potência reativa. Os multiplicadores de Lagrange são obtidos impondo-se as condições de estacionaridade à função Lagrangeana Aumentada, a qual é associada ao problema de Fluxo de Carga Ótimo. A metodologia é comparada com o método Simplex e com o sistema original. Testes foram realizados com os sistemas AEP14 e AEP30 que mostraram a eficiência da metodologia. / This work presents a methodology for the allocation of reactive sources in electrical power systems. The methodology is based on Lagrange\'s multiplier that points out the sensibility between the objective function - transmission active power loss and the constraints reactive power injections. The Lagrange\'s multipliers are obtained by imposing the conditions of stationarity at Augmented Lagrangeana function, that is connected to the Optimal Load Flow problem. The methodology is compared with the Simplex method and the original system. Tests were canied out with AEP14 and AEP30 systems, that showed the efficiency of the methodology.

Este trabalho apresenta a modelagem de um problema representado por um pêndulo elástico com excitação paramétrica vertical do suporte e a análise de estabilidade do sistema pendular que se obtém desconsiderando a elasticidade do pêndulo. A modelagem dos pêndulos e a obtenção das equações do movimento são feitas a partir da equação de Lagrange, utilizando as leis de Newton e para a análise de estabilidade do sistema pendular são apresentados os diagramas de bifurcações, multiplicadores de Floquet, mapas e seções de Poincaré e expoentes de Lyapunov. O comportamento do sistema pendular com excitação paramétrica vertical do suporte é investigado através de simulação computacional e apresentam-se resultados para diferentes faixas de valores da amplitude de excitação externa. / This work presents the modeling of an elastic pendulum with parametric excitation of the support and the analysis of the stability of the pendulum that one obtains disregarding the elasticity of the pendulum. The modeling of the pendulum and the equation of motions are obtained from the Lagrange\'s equations, using Newton\'s law. The concepts of bifurcation, Floquet\'s multipliers, Poincaré maps and sections and Lyapunov exponent are presented for the analysis of stability. The behavior of the pendulum with parametric excitation of the suport is investigated through computational simulation and results for different intervals of values of the external excitation amplitude are presented.

Orientador: Marco Lucio Bittencourt / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-08-10T12:57:32Z (GMT). No. of bitstreams: 1 Vazquez_ThaisGodoy_D.pdf: 11719751 bytes, checksum: c6d385d6a6414705c9f468358b8d3bea (MD5) Previous issue date: 2008 / Resumo: Este trabalho tem por objetivo principal o desenvolvimento de funções de interpolaçao e regras de integraçao tensorizaveis para o Metodo dos Elementos Finitos (MEF) de alta ordem hp, considerando os sistemas de referencias locais dos elementos. Para isso, primeiramente, determinam-se ponderaçoes especficas para as bases de funçoes de triangulos e tetraedros, formada pelo produto tensorial de polinomios de Jacobi, de forma a se obter melhor esparsidade e condicionamento das matrizes de massa e rigidez dos elementos. Alem disso, procuram-se novas funçoes de base para tornar as matrizes de massa e rigidez mais esparsas possiveis. Em seguida, escolhe-se os pontos de integraçao que otimizam o custo do calculo dos coeficientes das matrizes de massa e rigidez usando as regras de quadratura de Gauss-Jacobi, Gauss-Radau-Jacobi e Gauss-Lobatto-Jacobi. Por fim, mostra-se a construçao de uma base unidimensional nodal que permite obter uma matriz de rigidez praticamente diagonal para problemas de Poisson unidimensionais. Discute-se ainda extensoes para elementos bi e tridimensionais / Abstract: The main purpose of this work is the development of tensor-based interpolation functions and integration rules for the hp High-order Finite Element Method (FEM), considering the local reference systems of the elements. We first determine specific weights for the shape functions of triangles and tetrahedra, constructed by the tensorial product of Jacobi polynomials, aiming to obtain better sparsity and numerical conditioning for the mass and stiffness matrices of the elements. Moreover, new shape functions are proposed to obtain more sparse mass and stiffness matrices. After that, integration points are chosen that optimize the cost for the calculation of the coefficients of the mass and stiffness matrices using the rules of quadrature of Gauss-Jacobi, Gauss-Radau-Jacobi and Gauss-Lobatto-Jacobi. Finally, we construct an one-dimensional nodal shape function that obtains an almost diagonal stiffness matrix for the 1D Poisson problem. Extensions to two and three-dimensional elements are discussed. / Doutorado / Mecanica dos Sólidos e Projeto Mecanico / Doutor em Engenharia Mecânica

Orientador: José Mario Martínez Pérez / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-20T05:08:42Z (GMT). No. of bitstreams: 1 FloresCallisaya_Hector_D.pdf: 2324904 bytes, checksum: e15e7624ccad0fdf64ce3c4d8095c20a (MD5) Previous issue date: 2012 / Resumo: Neste trabalho, serão propostos modelos matemáticos para problemas de empacotamento não reticulado de esferas em regiões limitadas por quadráticas no plano e no espaço. Uma técnica para construir representações ou parametrizações será introduzida, mediante a qual será possível encontrar um sistema de desigualdades que determinam o empacotamento de um número fixo de esferas. Desta forma, resolvemos o problema de empacotamento de esferas através de uma sequência de sistemas de desigualdades. Finalmente, para obter resultados eficientes, minimizaremos a função de sobreposição, usando o método do Lagrangiano Aumentado / Abstract: In this work, we will propose mathematical models for not latticed packing of spheres problems in regions bounded by quadratic in the plane and in the space. A technique to construct representations or parameterizations will be introduced, by which it will be possible to find a system of inequalities which determine the packing of a fixed number of spheres. Thus, we solve the problem of packing spheres through a sequence of systems of inequalities. Finally, to obtain effective results, we will minimize the overlay function using the Augmented Lagrangian Method / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientadores: José Raimundo de Oliveira, Ignacio Bravo Muñoz / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-21T12:37:43Z (GMT). No. of bitstreams: 1 Fazanaro_FilipeIeda_D.pdf: 53323687 bytes, checksum: 76694b226ed99a337ecee1769ed9c4e0 (MD5) Previous issue date: 2012 / Résumén: Esta tesis tiene como objetivo la caracterización de sistemas dinámicos no lineales y abruptos. Se propone una nueva metodología para la estimación del espectro de Lyapunov capaz de superar las dificultades relacionadas en los sistemas basados en funciones lineales por partes sobre la aplicación de los métodos clásicos de cálculo (cuando se utiliza linealización local o análisis de series de las series temporales experimentales). Este enfoque, denominado como Dinámica de los Clones, realiza la estimación del espectro de Lyapunov y también mejora el estudio de las características topológicas relacionadas con los procesos de mezcla que dan lugar al comportamiento caótico. Este estudio se lleva a cabo utilizando las Estructuras Coherentes de Lagrange que pueden obtenerse a través de la construcción de un campo de Exponentes de Lyapunov de Tiempo Finito donde se puede identificar a las crestas (o las separatrices) que dan la posibilidad de identificar las distintas regiones de convergencia y divergencia del espacio de estados. Debido al hecho que esta tesis se desarrolla fundamentalmente bajo un ordenador, los aspectos prácticos involucrados en los experimentos numéricos necesarios, emplean algunos conceptos y herramientas de computación en paralelo. Esto último permitió la optimización de los algoritmos implementados. Por lo tanto, los experimentos se realizaron para verificar la eficacia del enfoque de las Dinámicas Clonadas para la caracterización del circuito de Chua, y también para obtener las Estructuras Coherentes de Lagrange que tienen relación con los modelos dinámicos capaces de generar atractores caóticos multiscroll / Resumo: Essa tese objetiva caracterizar sistemas dinâmicos não lineares não suaves. Para tal, é proposta uma nova abordagem de estimação do espectro de Lyapunov capaz de contornar as dificuldades intrínsecas aos sistemas estruturados por funções lineares por partes quando da aplicação de metodologias clássicas (baseadas em linearizações locais ou em análises de séries temporais). Essa abordagem possibilita a estimação do espectro de Lyapunov e, além disso, auxilia no estudo das características topológicas relacionadas aos processos de mistura que dão origem ao comportamento caótico. Essa linha de estudo é realizada através das Estruturas Lagrangianas Coerentes, as quais são obtidas pela construção de um campo de Expoentes de Lyapunov de Tempo Finito, onde é possível identificar cristas (ou separatrizes) que dividem regiões de convergência e de divergência no espaço de estados. Por se tratar de um trabalho basicamente computacional, essa tese contempla os aspectos práticos envolvidos para a realização dos experimentos numéricos através da utilização de alguns conceitos e ferramentas de computação paralela, o que possibilitou a otimização dos algoritmos implementados. Nesse sentido, os experimentos foram realizados de modo a verificar a eficácia da metodologia proposta para a caracterização do circuito de Chua e, ainda, foram obtidas as Estruturas Lagrangianas Coerentes para os modelos dinâmicos capazes de gerar atratores caóticos multiscroll / Abstract: This thesis aims to characterize non-smooth nonlinear dynamical systems. To accomplish this purpose, we propose a new approach for estimating the Lyapunov spectrum which is capable to overcome the intrinsic difficulties of classical methods (based on local linearization or time series analysis) when dealing with systems based on piecewise linear functions. This approach, called Cloned Dynamics, allows the estimation of the Lyapunov spectrum and also improves the study of the topological features related to the mixing processes that give rise to the chaotic behavior. This study is performed using the Lagrangian Coherent Structures which are obtained by the construction of a Finite Time Lyapunov Exponents field where it is possible to identify the ridges (or the separatrices) which divide the convergence and divergence regions of the state space. Due to the fact that this thesis is basically developed under a computer environment, the practical features involved in the numerical experiments employing some parallel computing concepts and tools are discussed, which allowed the optimization of the algorithms implemented. In this sense, experiments were performed to verify the effectiveness of the Cloned Dynamics approach for the characterization of the Chua's circuit, and also to obtain the Lagrangian Coherent Structures related to the dynamical models capable of generating multiscroll chaotic attractors / Doutorado / Automação / Doutor em Engenharia Elétrica

In this thesis we present a slight generalisation of the Pearl complex or relative quantum homology to some non monotone Lagrangian submanifolds. First we develop the theory for the so called almost monotone Lagrangian submanifolds, We apply it to uniruling problems as well as estimates for the relative Gromov width. In the second part we develop the theory for toric fiber in toric Fano manifolds, recovering previous computaional results of Floer homology . / Doctorat en Sciences / info:eu-repo/semantics/nonPublished