| CEOC Seminars 2004 |
December 17, 2004
The Department of Control and Automation of Technical University of Georgia and our research interests
Abstract:
My talk will have a general character. In order to motivate a future cooperation between our universities, to prepare a possible research project between the Control Theory Group on the Centre for Research in Optimization and Control, and mobility of Students and Professors under the European TEMPUS program between the University of Aveiro and the Technical University of Georgia, I will say a few words about Georgia, about the structure of our university, my Faculty, the educational process in Georgia, and about the scientific directions of our Department as well as my own research interests.
|
December 3, 2004
Plane embedded trees
Abstract:
From the graph theoretic point of view a way of embedding tree (or graph) on a plane is irrelevant. But from the point of view of applications (for example, data structures, epidemic spread models, social networks, etc) it is necessary to consider such trees as different ones. Two families of plane embedded trees are introduced (one in the labelled case and other for the unlabelled trees) as well as some typical properties of them are presented. Special Attention is given to these properties which differ embedded trees from the "normal" ones.
|
November 19, 2004
Formal chronological calculus and noncomutative symmetric functions
Abstract:
We will present a formal version of the cronological calculus developped by A. Agrachev et al.'78. This new tool (E.Rocha'04) gives a mechanism to extend results from Nonlinear Control Theory to other areas of mathematics.
As an application, we will apply it to obtain Lie-relations between some noncommutative symmetric functions, I.Gel'fand et al'95.
|
November 12, 2004
Geometric graphs: some problems and applications
Abstract:
Geometric graphs are interesting structures both from the combinatorial and the geometric point of view. Geometric graphs are being studying widely because their many applications. In this talk two different kind of problemas related with plane geometric graphs will be presented. One of them deals with the realization of plane geometric graphs on small grids and how small the grid can be if we want to transform one graph into another by means of basic transformations in the graph (constant size transformations). The second one is related with applications of geometric graph theory to mechanical gear systems. Some interesting problems on geometric graphs come from these kind of systems. We will give an overview about it.
|
November 5, 2004
A disjunctive programming approach for Odd-Diameter-Constrained Minimum Spanning Trees
Abstract:
The Diameter-Constrained Minimum Spanning Tree (DMST) Problem seeks at least cos spanning tree subject to a (diameter) bound imposed on the number of edges in the tree between any node pair. The problem is easy to solve when D = 2 or 3 and is NP-Hard when D ³ 4. In a previous research concerning network flow-based formulations for diameter-constrained tree problems, Gouveia and Magnanti (2003) have found problems to be more difficult to solve when the tree diameter D is odd.
We provide an alternate modelling approach for those situations. In the approach we use disjunctive programming techniques to present a model to a core subproblem related with the selection of the central edge for the situations when D is odd. The model to the core subproblem gives an extended description of the convex hull of the associated integer solutions. By combining this model for the subproblem with the basic model for the whole problem we obtain a new model for the DMST when D is odd with much stronger linear programming relaxation.
The linear programming gaps for the new model are very small, typically less than 0.5%, and are usually smaller than the gaps of the best previous model described in Gouveia and Magnanti (2003). Moreover, we can solve several large Euclidean problem instances that were not solved with the models described in the previous work.
|
October 22, 2004
Minimização do Número de Vigilantes em Galerias de Arte por Aproximações Sucessivas
Resumo:
Será abordado o problema da colocação de guardas em vértices de um polígono simples de forma a que o vigiem totalmente e o seu número seja mínimo. A solução proposta baseia-se no cálculo do valor óptimo por aproximações sucessivas. Nesta abordagem cada aproximação é obtida por resolução de um problema de cobertura mínima de conjuntos, associada a uma partição do polígono. Essa resolução é efectuada usando um sistema de Programação por Restrições. Será explicado o tratamento de alguns problemas geométricos e exemplificada a avaliação experimental do método para polígonos simples ortogonais.
|
October 15, 2004
Newton's aerodynamical problem in media of positive temperature
Abstract:
Consider the problem of minimazation of resistance of a body moving through a rarefied medium. Usually it is supposed (classical Newton's problem) that the particles are immovable, i.e. the mean velocity of the body. Here we consider the (more general) case where these values are comparable. The problem is solved, and classification of solutions is made, in three and in two dimensions.
|
May 28, 2004
Método dos Conjuntos Atingíveis Generalizado e as suas Aplicações
Resumo:
Considera-se um método elaborado para analisar os modelos matemáticos com controlo. A ideia principal é construir ou aproximar, na forma explícita, o conjunto de todas as combinações possíveis dos critérios que caracterizam o funcionamento do modelo. Numa segunda fase, este conjunto é analisado graficamente, usando um software especial. Serão dados exemplos de aplicação do método proposto e dos sistemas de apoio de decisão na área de economia, ecologia e engenharia.
|
May 21, 2004
Necessary Conditions of Optimality for Impulsive Control Problems
Abstract:
First-order and second-order necessary conditions of optimality for an impulsive control problem that remain informative for abnormal control processes are discussed. One of the main features of these conditions is that no a priori normality assumptions required. This feature follows from the fact that these conditions rely on an extremal principle which is proved for an abstract minimization problem with equality and inequality constraints and constraints given by an inclusion in a convex cone. Two simple examples illustrate the power of the main result.
|
May 7, 2004
Questões Matemáticas no Traçado de Reservas para a Protecção da Biodiversidade
Resumo:
No traçado de redes de áreas protegidas há que assegurar certos requisitos de natureza conservacionista de forma a favorecer a diversidade e sustentabilidade das espécies. Estes requisitos dizem respeito, fundamentalmente, aos níveis de abundância e variedade das espécies, e às configurações espaciais das reservas. Frequentemente, tais pretensões colidem com outras formas de utilização do solo, recurso normalmente escasso e muito disputado. Consequentemente, o terreno destinado à reserva é limitado, sendo indispensável conceber o seu traçado eficientemente, i.e., incorporando aqueles requisitos numa área mínima. Nesta comunicação, abordam-se este tipo de questões segundo um ponto de vista matemático.
|
April 23, 2004
Um modelo combinatório para codificação de imagens
Resumo:
Neste trabalho introduz-se um modelo combinatório para codificação de imagens, formulado no contexto da teoria dos grafos, cuja descodificação obriga à determinação de um subgrafo que constitui uma biclique. Adicionalmente, apresentam-se duas técnicas de descodificação baseadas em programação inteira e em optimização combinatória e fazem-se estudos comparativos sobre a eficiência computacional destas abordagens relativamente a implementações anteriores.
|
April 16, 2004
Sistemas de Dedução - Provadores Automáticos de Teoremas
Resumo:
Apresentam-se os conceitos de sistema de dedução e de sistema de demonstração automática. Introduzem-se alguns dos sistemas de demonstração automática de teoremas actuais, assim como um sistema actualmente em desenvolvimento. Mostram-se alguns exemplos de aplicação.
|
April 2, 2004
Uma Abordagem Heurística de um Problema de Optimização de Rotas e Veículos
Resumo:
Os problemas de optimização de rotas e veículos (Vehicle Routing Problems) são problemas muito estudados em Investigação Operacional. Este facto deve-se à enorme importância tanto no contexto logístico como na sua complexidade matemática. A maioria destes problemas é NP-difícil o que torna impossível a obtenção de soluções óptimas para os problemas encontrados no mundo real, desafiando assim a procura de novas heurísticas mais eficientes. Nesta apresentação propomos a modelação matemática dum problema prático de optimização dos transportes de uma empresa que distribui os seus produtos entre vários clientes, utilizando transportes heterogéneos, de acordo com algumas exigências dos seus clientes (horas de entrega, volumes de embalagens, ...) na forma do Vehicle Routing Problem withTime Windows (VRPTW) e o desenvolvimento do algoritmo para a resolução deste problema. A estratégia que está na base deste algoritmo, utiliza uma heurística de agrupamento dos clientes (pela sua proximidade e pelos valores das suas encomendas.), que permite subdividir o problema geral em um número finito de problemas de VRPTW. Para resolver o problema de VRPTW em cada agrupamento utiliza-se o método de relaxação Lagrangeana com o melhoramento posterior baseado na heurística das economias combinadas modificadas.
|
Marc 26, 2004
Do Modelo à Aplicação Final
Resumo:
As aplicações do Projecto Matemática Ensino (PmatE), encerram um conjunto de ferramentas que apresentam uma perspectiva inovadora sobre as tradicionais aplicações de eLearning, sendo de destacar a componente lúdica capaz de atrair os estudantes para o seu trabalho.
O sistema baseia-se numa filosofia de aprendizagem pela avaliação e funciona como um complemento ao manual de estudo e à sala de aula. Nunca substituindo ou diminuindo o papel que o professor desempenha no ensino tradicional.
Os alunos são motivados a estudar através de ferramentas com o perfil de jogo, mas sem nunca pender para o lado exclusivamente lúdico.
Estas aplicações têm um carácter competitivo que provou, ao longo do tempo, ser um aliado eficaz para sensibilizar os alunos para a necessidade de criar métodos de trabalho e estudo.
Todo o sistema se baseia no conceito de modelos geradores de questões (modelos). Os modelos quando são inseridos no sistema são catalogados de acordo com uma estrutura rígida que oferece a estas aplicações outra das suas características mais importantes: a avaliação qualitativa.
O orador vai descrever sucintamente todo o processo, desde a idealização dos conteúdos até à sua representação final na WEB.
|
March 19, 2004
Transformações Infinitesimais e Espaço Tangente (II)
Resumo:
Constroem-se Espaços Quase-Tangentes a partir dos quais se obtém o Espaço Tangente utilizando a função parte standard.
|
March 5, 2004
Singularities of optimal averaged profit in Arnold's model
Abstract:
We study the time averaged profit for one parametric families of control systems and profit densities on the circle. When all admissible velocities of motion are positive the classification of generic singularities of the best averaged profit like the function of the parameter is presented, and the stability of these singularities is proved.
|
February 27, 2004
Extremos Anormais em Problemas de Optimização: Rigidez e Condiçoes de Optimalidade da 2ª ordem
Resumo:
Em Programação Não Linear (PNL) os extremos anormais aparecem quando as restrições do problema não são regulares (os gradientes correspondentes são linearmente dependentes). Neste caso o multiplicador de Lagrange que corresponde à função objectivo em condições de optimalidade é igual a zero em alguns pontos extremais (extremos anormais).
Tradicionalmente em Optimização a função objectivo e as funções de restrições foram tratados nas maneiras diferentes e o facto que a função objectivo não aparece em condições optimais era considerado como alguma "patologia". A opinião geral era que nos casos de extremos anormais é impossível de resolver o problema aplicando as condições de optimalidade conhecidas de 1ª e 2ª ordem e as actividades nessa área foram dirigidas para o estudo das condições que garantam a normalidade do problema.
Nós apresentamos as condições de optimalidade de 2ª ordem que implicam o isolamento do óptimo local no nível crítico para problema geral de PNL e discutimos as condições necessárias de optimalidade na presença dos extremos anormais.
|
February 20, 2004
Well-posedness for the minimazation problem for a functional of the gradient: various approaches
Abstract:
The objective of this seminar is to present various results on minimizers of a nonconvex integral functional of the gradient with the affine boundary data obtained during the last ten years. We study the existence of a continuous selection from the family of minimizers considered as a multivalued mapping with nonconvex values in the space of continuous functions. Recently, the complete resolution of this problem was obtained. Particularly, we have proved the possibility to approximate uniformly each solution of the relaxed problem continuously depending on boundary condition by corresponding solutions of original one.
|
February 13, 2004
Variedades diferenciáveis: Transformações Infinitesimais e Espaço Tangente
Resumo:
Aproximação de campos vectoriais por meio de certos difeomorfismos internos.
|
February 6, 2004
Aspectos Combinatórios e Geométricos dos Matroides Lagrangianos
Resumo:
Os matroides de Coxeter, estão associados aos grupos de Coxeter e incluem os matroides quando o grupo de Coxeter considerado é $S_n$. Focaremos aspectos combinatórios e geométricos dos matroides de Coxeter associados ao grupo $C_n$, em particular, dos de rank maximal (Lagrangianos), que estão relacionadas com mapas em superfícies de um modo análogo ao dos matroides com grafos.
|
|
|
|
|
|