Geometric optimization on visibility problems: metaheuristic and exact solutions

Os problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.

Solutions of Tikhonov functional equations and applications to multiplication operators on Szegö spaces

We consider a natural representation of solutions for Tikhonov functional equations. This will be done by applying the theory of reproducing kernels to the approximate solutions of general bounded linear operator equations (when defined from reproducing kernel Hilbert spaces into general Hilbert spaces), by using the Hilbert-Schmidt property and tensor product of Hilbert spaces. As a concrete case, we shall consider generalized fractional functions formed by the quotient of Bergman functions by Szegö functions considered from the multiplication operators on the Szegö spaces.

Cinética da transferência de calor em materiais com mudança de fase

É extensa a bibliografia dedicada a potenciais aplicações de materiais com mudança de fase na regulação térmica e no armazenamento de calor ou de frio. No entanto, a baixa condutividade térmica impõe limitações numa grande diversidade de aplicações com exigências críticas em termos de tempo de resposta curto ou com requisitos de elevada potência em ciclos de carga/descarga de calor latente. Foram desenvolvidos códigos numéricos no sentido de obter soluções precisas para descrever a cinética da transferência de calor com mudança de fase, com base em geometrias representativas, i.e. planar e esférica. Foram igualmente propostas soluções aproximadas, sendo identificados correspondentes critérios de validação em função das propriedades dos materiais de mudança de fase e de outros parâmetros relevantes tais como as escalas de tamanho e de tempo, etc. As referidas soluções permitiram identificar com rigor os fatores determinantes daquelas limitações, quantificar os correspondentes efeitos e estabelecer critérios de qualidade adequados para diferentes tipologias de potenciais aplicações. Os referidos critérios foram sistematizados de acordo com metodologias de seleção propostas por Ashby e co-autores, tendo em vista o melhor desempenho dos materiais em aplicações representativas, designadamente com requisitos ao nível de densidade energética, tempo de resposta, potência de carga/descarga e gama de temperaturas de operação. Nesta sistematização foram incluídos alguns dos compósitos desenvolvidos durante o presente trabalho. A avaliação das limitações acima mencionadas deu origem ao desenvolvimento de materiais compósitos para acumulação de calor ou frio, com acentuada melhoria de resposta térmica, mediante incorporação de uma fase com condutividade térmica muito superior à da matriz. Para este efeito, foram desenvolvidos modelos para otimizar a distribuição espacial da fase condutora, de modo a superar os limites de percolação previstos por modelos clássicos de condução em compósitos com distribuição aleatória, visando melhorias de desempenho térmico com reduzidas frações de fase condutora e garantindo que a densidade energética não é significativamente afetada. Os modelos elaborados correspondem a compósitos de tipo core-shell, baseados em microestruturas celulares da fase de elevada condutividade térmica, impregnadas com o material de mudança de fase propriamente dito. Além de visarem a minimização da fração de fase condutora e correspondentes custos, os modelos de compósitos propostos tiveram em conta a adequação a métodos de processamento versáteis, reprodutíveis, preferencialmente com base na emulsificação de líquidos orgânicos em suspensões aquosas ou outros processos de reduzidas complexidade e com base em materiais de baixo custo (material de mudança de fase e fase condutora). O design da distribuição microestrutural também considerou a possibilidade de orientação preferencial de fases condutoras com elevada anisotropia (p.e. grafite), mediante auto-organização. Outros estágios do projeto foram subordinados a esses objetivos de desenvolvimento de compósitos com resposta térmica otimizada, em conformidade com previsões dos modelos de compósitos de tipo core-shell, acima mencionadas. Neste enquadramento, foram preparados 3 tipos de compósitos com organização celular da fase condutora, com as seguintes características e metodologias: i) compósitos celulares parafina-grafite para acumulação de calor, preparados in-situ por emulsificação de uma suspensão de grafite em parafina fundida; ii) compósitos celulares parafina-Al2O3 para acumulação de calor, preparados por impregnação de parafina em esqueleto cerâmico celular de Al2O3; iii) compósitos celulares para acumulação de frio, obtidos mediante impregnação de matrizes celulares de grafite com solução de colagénio, após preparação prévia das matrizes de grafite celular. Os compósitos com esqueleto cerâmico (ii) requereram o desenvolvimento prévio de um método para o seu processamento, baseado na emulsificação de suspensões de Al2O3 em parafina fundida, com adequados aditivos dispersantes, tensioactivos e consolidantes do esqueleto cerâmico, tornando-o auto-suportável durante as fases posteriores de eliminação da parafina, até à queima a alta temperatura, originando cerâmicos celulares com adequada resistência mecânica. Os compósitos desenvolvidos apresentam melhorias significativos de condutividade térmica, atingindo ganhos superiores a 1 ordem de grandeza com frações de fase condutora inferior a 10 % vol. (4 W m-1 K-1), em virtude da organização core-shell e com o contributo adicional da anisotropia da grafite, mediante orientação preferencial. Foram ainda preparados compósitos de armazenamento de frio (iii), com orientação aleatória da fase condutora, obtidos mediante gelificação de suspensões de partículas de grafite em solução aquosa de colagénio. Apesar da estabilidade microestrutural e de forma, conferida por gelificação, estes compósitos confirmaram a esperada limitação dos compósitos com distribuição aleatória, em confronto com os ganhos alcançados com a organização de tipo core-shell.

O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.