Limited range coverage problems

Tal como o título indica, esta tese estuda problemas de cobertura com alcance limitado. Dado um conjunto de antenas (ou qualquer outro dispositivo sem fios capaz de receber ou transmitir sinais), o objectivo deste trabalho é calcular o alcance mínimo das antenas de modo a que estas cubram completamente um caminho entre dois pontos numa região. Um caminho que apresente estas características é um itinerário seguro. A definição de cobertura é variável e depende da aplicação a que se destina. No caso de situações críticas como o controlo de fogos ou cenários militares, a definição de cobertura recorre à utilização de mais do que uma antena para aumentar a eficácia deste tipo de vigilância. No entanto, o alcance das antenas deverá ser minimizado de modo a manter a vigilância activa o maior tempo possível. Consequentemente, esta tese está centrada na resolução deste problema de optimização e na obtenção de uma solução particular para cada caso. Embora este problema de optimização tenha sido investigado como um problema de cobertura, é possível estabelecer um paralelismo entre problemas de cobertura e problemas de iluminação e vigilância, que são habitualmente designados como problemas da Galeria de Arte. Para converter um problema de cobertura num de iluminação basta considerar um conjunto de luzes em vez de um conjunto de antenas e submetê-lo a restrições idênticas. O principal tema do conjunto de problemas da Galeria de Arte abordado nesta tese é a 1-boa iluminação. Diz-se que um objecto está 1-bem iluminado por um conjunto de luzes se o invólucro convexo destas contém o objecto, tornando assim este conceito num tipo de iluminação de qualidade. O objectivo desta parte do trabalho é então minimizar o alcance das luzes de modo a manter uma iluminação de qualidade. São também apresentadas duas variantes da 1-boa iluminação: a iluminação ortogonal e a boa !-iluminação. Esta última tem aplicações em problemas de profundidade e visualização de dados, temas que são frequentemente abordados em estatística. A resolução destes problemas usando o diagrama de Voronoi Envolvente (uma variante do diagrama de Voronoi adaptada a problemas de boa iluminação) é também proposta nesta tese.

Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.

Implicit optimality criterion for convex SIP problem with box constrained index set

We consider a convex problem of Semi-Infinite Programming (SIP) with multidimensional index set. In study of this problem we apply the approach suggested in [20] for convex SIP problems with one-dimensional index sets and based on the notions of immobile indices and their immobility orders. For the problem under consideration we formulate optimality conditions that are explicit and have the form of criterion. We compare this criterion with other known optimality conditions for SIP and show its efficiency in the convex case.

Optimization models for a short sea fuel oil distribution problem

O transporte marítimo e o principal meio de transporte de mercadorias em todo o mundo. Combustíveis e produtos petrolíferos representam grande parte das mercadorias transportadas por via marítima. Sendo Cabo Verde um arquipelago o transporte por mar desempenha um papel de grande relevância na economia do país. Consideramos o problema da distribuicao de combustíveis em Cabo Verde, onde uma companhia e responsavel por coordenar a distribuicao de produtos petrolíferos com a gestão dos respetivos níveis armazenados em cada porto, de modo a satisfazer a procura dos varios produtos. O objetivo consiste em determinar políticas de distribuicão de combustíveis que minimizam o custo total de distribuiçao (transporte e operacões) enquanto os n íveis de armazenamento sao mantidos nos n íveis desejados. Por conveniencia, de acordo com o planeamento temporal, o prob¬lema e divido em dois sub-problemas interligados. Um de curto prazo e outro de medio prazo. Para o problema de curto prazo sao discutidos modelos matemáticos de programacao inteira mista, que consideram simultaneamente uma medicao temporal cont ínua e uma discreta de modo a modelar multiplas janelas temporais e taxas de consumo que variam diariamente. Os modelos sao fortalecidos com a inclusão de desigualdades validas. O problema e então resolvido usando um "software" comercial. Para o problema de medio prazo sao inicialmente discutidos e comparados varios modelos de programacao inteira mista para um horizonte temporal curto assumindo agora uma taxa de consumo constante, e sao introduzidas novas desigualdades validas. Com base no modelo escolhido sao compara¬das estrategias heurísticas que combinam três heur ísticas bem conhecidas: "Rolling Horizon", "Feasibility Pump" e "Local Branching", de modo a gerar boas soluçoes admissíveis para planeamentos com horizontes temporais de varios meses. Finalmente, de modo a lidar com situaçoes imprevistas, mas impor¬tantes no transporte marítimo, como as mas condicões meteorológicas e congestionamento dos portos, apresentamos um modelo estocastico para um problema de curto prazo, onde os tempos de viagens e os tempos de espera nos portos sao aleatórios. O problema e formulado como um modelo em duas etapas, onde na primeira etapa sao tomadas as decisões relativas as rotas do navio e quantidades a carregar e descarregar e na segunda etapa (designada por sub-problema) sao consideradas as decisoes (com recurso) relativas ao escalonamento das operacões. O problema e resolvido por um metodo de decomposto que usa um algoritmo eficiente para separar as desigualdades violadas no sub-problema.

Perceções sociais dos portugueses face aos riscos associados às alterações climáticas

O aquecimento do sistema climático é inequívoco e a influência humana é clara. A continuação da emissão de gases com efeito de estufa irá potenciar os impactes das alterações climáticas, representando um compromisso futuro que se perpetuará por vários séculos. As alterações climáticas não proporcionam uma experiência sensorial direta, embora as variações de temperatura e de precipitação e os extremos climáticos de vários tipos poderem ser experienciados. O cidadão comum não se apercebe do que está a acontecer, a menos que ocorram mudanças significativas, no estado normal do tempo para uma determinada época, na região do mundo onde ele vive. Mesmo para os especialistas, o problema só é cognoscível através de uma vasta rede científica, técnica e institucional. O conhecimento, é portanto, transmitido ao público em geral maioritariamente através de representações dos media sobre o discurso produzido pela comunidade científica. O principal objetivo deste trabalho é averiguar a interligação entre o discurso científico, o discurso mediático e as perceções da população portuguesa na temática das alterações climáticas. A metodologia utilizada, para a prossecução do objetivo, num trabalho que cruza o domínio científico da engenharia do ambiente com o das ciências sociais, encontra-se dividida em 3 fases principais: (1) Uma primeira fase onde se realiza uma análise ao discurso científico de produção nacional, com uma análise de conteúdo aos resumos dos artigos científicos, utilizando 884 resumos da base de dados Scopus de 1975 a 2013 com a palavra-chave ‘Climate Change’; (2) Uma segunda fase onde se analisa o conteúdo de notícias de meios de comunicação social portugueses, aplicando uma análise de conteúdo a 4340 notícias veiculadas por 4 órgãos de comunicação social (Correio da Manhã, Público, RTP e TSF) entre 2004 e 2013, utilizando os respetivos motores de busca online com a palavra-chave ‘Alterações Climáticas’; e, (3) uma terceira fase onde se compila a informação dos estudos existentes sobre a população portuguesa, utilizando os dados dos Eurobarómetros que incluem o tema das alterações climáticas de 1982 a 2014. Seguindo uma linha condutora que inclui o discurso científico, o discurso mediático e as perceções sociais, almejou-se uma abrangência do tema das alterações climáticas, investigando a existência do fenómeno e as respetivas causas, as consequências com a análise dos impactes e dos riscos associados a esses impactes e as soluções através de medidas de mitigação e de adaptação. Nos principais resultados emerge a evidência de que a intensidade de crescimento da produção científica nacional não se traduz num crescimento consistente dos índices de noticiabilidade dos órgãos de comunicação social e desde 2010 que o número de dias por ano, sem notícias sobre alterações climáticas, ultrapassa dos 50%. Em consequência, os níveis de informação da população portuguesa sobre as alterações climáticas são sistematicamente inferiores à média europeia. Em Portugal as taxas de pouco ou nulo conhecimento rondam os dois terços de inquiridos. Não obstante o seu caráter contínuo, para que as alterações climáticas se tornem alvo de interesse dos media é necessário que ocorram reuniões políticas, encontros científicos ou outros acontecimentos. A visibilidade alcançada pelos acontecimentos nacionais é muito fraca e os acontecimentos meteorológicos extremos, não são frequentemente relacionados com o fenómeno das alterações climáticas. No seio da comunidade científica portuguesa existe um claro consenso sobre a existência das alterações climáticas e das suas causas antropogénicas. No discurso mediático português não se verifica enviesamento da informação não sendo surpreendente os baixos níveis de ceticismo dos portugueses. A abordagem aos impactes das alterações climáticas, tanto no discurso científico como no discurso mediático, é robusta e em 2014, cerca de sete em dez portugueses afirma que as alterações climáticas são um problema muito sério. Contudo, Portugal apresenta a proporção mais baixa da Europa de respondentes que percepcionam as alterações climáticas como o problema mais grave que o mundo enfrenta. Para estes resultados poderá contribuir a baixa inclusão de termos relacionados com o risco, tanto no discurso científico como no mediático, não ultrapassando os 20%. Tanto o discurso científico como o discurso mediático não estão direcionados para as soluções (mencionando especificamente medidas de mitigação ou medidas de adaptação). A menção às medidas de mitigação e às medidas de adaptação não ultrapassam os 16% no discurso científico e apresentam valores ainda mais baixos no discurso mediático (13%). Em ambos os discursos existe uma clara preferência pela menção às medidas de adaptação em detrimento das medidas de mitigação. Com valores tão baixos na abordagem às soluções das alterações climáticas não surpreendem os também diminutos níveis de responsabilidade que a população portuguesa atribui a si própria no combate às alterações climáticas.