O trabalho apresentado nesta dissertação é referente ao estudo da evacuação de pessoas, mais especificamente, a evacuação predial faseada. O objetivo é determinar, para instâncias de até 25 andares, os instantes de liberação de cada grupo de pessoas, a fim de minimizar o tempo total de evacuação do edifício. No entanto, a determinação destes instantes deve considerar o risco ao qual os diferentes grupos estão submetidos, priorizando a evacuação do andar afetado. Além disso, os conflitos de diferentes grupos por espaço nas rotas de evacuação também devem ser evitados, já que, são nessas situações que acontecem grande parte dos acidentes. Para atingir tal objetivo, foi elaborado um modelo matemático de programação linear inteira. Devido à alta complexidade do modelo, fez-se necessária a aplicação de métodos heurísticos para a obtenção de soluções. Dessa maneira, foram desenvolvidas uma heurística de busca baseada em GRASP e uma heurística lagrangeana. Apesar da heurística lagrangeana atestar a qualidade da solução (a partir da comparação do resultado obtido com o limitante inferior), a heurística de busca mostrou-se mais adequada para o problema, pois forneceu resultados de qualidade com pouco esforço computacional. / This dissertation studies the evacuation of people, more specifically, building phased evacuation. The objective of this study is to determine, for buildings of up to 25 floors, in which instants each group of people has to be released, in order to minimize the total evacuation time. Furthermore, the determination of these instants has to consider the risk to which each group of people is submitted, thus the affected floor has to be the first group to be released. In addition, conflicts for space between groups should be avoided, since such situations increase the occurrences of accidents. To achieve this goal, an integer linear programming model was designed. Due to the high complexity of the model, it was necessary to apply heuristics to obtain solutions for some instances. Therefore, a search heuristic based on GRASP and a lagrangian heuristic were developed. Despite the fact that the lagrangian heuristic attests to the quality of the solution (when it is compared to the lower bound), the search heuristic was considered more suitable for this problem because it provided quality results with lower computational efforts.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2010 / Made available in DSpace on 2012-10-25T09:16:45Z (GMT). No. of bitstreams: 1 286903.pdf: 3179531 bytes, checksum: 147f57bbf31752db925e7f566b471e5b (MD5) / O problema da programação diária da operação de sistemas hi-drotérmicos tem como objetivo definir quais unidades devem estar operando, os respectivos níveis de geração, em cada hora do dia seguinte, com o propósito de atender à demanda ao longo do dia, às restrições operativas das usinas e dos reservatórios e às restrições elétricas do sistema ao menor custo operativo. Uma característica desafiante do problema da programação consiste em obter uma solução de boa qualidade com um custo computa-cional moderado. A obtenção de uma solução dessa natureza requer uma modelagem detalhada de todos os elementos de ge-ração e transmissão do sistema hidrotérmico. Em consequência, o problema de otimização resultante possui um elevado grau de complexidade, o qual pode ser decomposto em subproblemas menores, com características distintas e mais fáceis de serem so-lucionados. Neste trabalho, a estratégia de solução proposta para o problema da programação diária está baseada nas metodologi-as da Relaxação Lagrangeana e do Lagrageano Aumentado. Essa estratégia de solução proposta para o problema da programação diária é analisada em uma configuração hidrotérmica, extraída do sistema elétrico brasileiro. / The daily operation programming problem of hydrothermal systems aims to define which units should be in operation, the respective generation levels at each hour of the day, with the purpose of matching the demand, and meeting the operating plants constraints, the reservoir constraints and the electrical system constraints at the minimum operative cost. A challenging feature of this programming problem consists of obtaining a solution with good quality and moderate computational burden. In order to obtain a good solution, a detailed modeling of the generation and the transmission system is required. Consequently, the resulting optimization problem has a high degree of complexity, which can be decomposed into smaller subproblems, with distinctive characteristics and easier to solve. In this work, the proposed strategy of solution to the daily programming problem is based on the Lagrangian Relaxation and Augmented Lagrangian methods. This proposed strategy to the daily programming problem is analyzed in a hydrothermal setting, extracted from the Brazilian electrical system.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Elétrica / Made available in DSpace on 2012-10-22T21:13:18Z (GMT). No. of bitstreams: 1 232413.pdf: 1398027 bytes, checksum: f7a1d4cc5f0d9ff727a8c81e2ad2dd1e (MD5) / O problema da programação diária da operação de sistemas hidrotérmicos tem como objetivo definir quais unidades devem estar operando, os respectivos níveis de gera-ção, com o propósito de atender à demanda ao menor custo operativo. Uma caracte-rística desafiante do problema da programação consiste em obter uma solução de boa qualidade com um custo computacional moderado. A obtenção de uma solução de boa qualidade requer uma modelagem detalhada da função de produção das unida-des hidrelétricas e termelétricas, bem como das respectivas restrições de operação dessas unidades. Particularmente, neste trabalho tem-se como foco a modelagem das usinas hidrelétricas, dada a importância dessas instalações para o Sistema Elétrico Brasileiro. Assim, para essas unidades, as não-linearidades associadas à cota de jusan-te, as perdas hidráulicas, o rendimentos da unidade e as zonas proibidas de geração são modeladas detalhadamente. Em conseqüência, o problema de otimização resul-tante pode ser caracterizado como não-linear e de grande porte o qual pode ser trata-do satisfatoriamente por meio da aplicação da técnica de Relaxação Lagrangena. De forma geral, essa técnica decompõe o problema em subproblemas menores, com ca-racterísticas distintas e mais fáceis de serem solucionados. Para obter um tempo com-putacional compatível com o horizonte de estudo, especial atenção deve ser dada ao subproblema de alocação das unidades hidrelétricas, o qual é natureza combinatória. Nesse sentido, este trabalho propõe duas formas distintas de decomposição do pro-blema, baseadas na Relaxação Lagrangeana, possibilitando o estabelecimento de uma análise comparativa das soluções apresentadas e dos tempos computacionais, que por sua vez possibilita definir, para problemas reais, a estratégia de decomposição mais apropriada. Os estudos foram realizados utilizando-se uma configuração reduzida extraída do Sistema Elétrico Brasileiro, constituída de cinco reservatórios, 22 unidades hidrelétricas e duas unidades termelétricas.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2011 / Made available in DSpace on 2012-10-26T07:42:30Z (GMT). No. of bitstreams: 1 295134.pdf: 3300794 bytes, checksum: 2e4906157b9f1035162468e9714c55a6 (MD5) / Este trabalho propõe um modelo para o problema de alocação de unidades hidrelétricas, cujo objetivo consiste em determinar quais unidades devem operar, e os respectivos níveis de geração de usinas hidrelétricas em cascata, a cada hora, em um horizonte de um dia. Como uma contribuição apresenta-se uma nova modelagem para a função de produção das unidades geradoras, com destaque para as perdas mecânicas e elétricas presentes nos conjuntos turbina gerador. Para levar em consideração as complexidades inerentes deste problema de maneira condizente com as necessidades do caso brasileiro, o modelo da alocação é representado matematicamente como um problema de programação não linear binário-misto. Com o objetivo de resolver este problema eficientemente este trabalho faz uso de uma estratégia de decomposição baseada nos métodos da Relaxação Lagrangeana e do Lagrangeano Aumentado. Diferentes análises em torno da modelagem e da estratégia de solução propostas neste trabalho são realizadas mediante o uso de um sistema composto por quatro usinas hidrelétricas em cascata, cuja capacidade de potência instalada é de 4.170 MW.

DIAS, Fábio Carlos Sousa. Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica. 2008. 89 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2008. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T15:12:03Z No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-15T15:32:35Z (GMT) No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Made available in DSpace on 2016-07-15T15:32:35Z (GMT). No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) Previous issue date: 2008 / In this work, we study the Simple Plant Location Problem (SPLP). Using its classical mathematical programming formulation and another recently proposed formulation, we develop several algorithms to …nd lower and upper bounds for the problem as well as branch-and-bound algorithms. With the classical formulation, such bounds are obtained via the data correction method and dominance criteria between …xed and transportation costs. We propose a projection of this formulation that has shown to be computationally atractive. Using the new formulation, we propose and prove the correctness of several iterative procedures that attempt to …nd an optimal solution to the problem by solving a sequence of parametric sub-problems, each one obtained by removing some variables and constraints of the original formulation. At each iteration of this process, we can obtain lower and upper bounds. We also apply Lagrangean relaxation to this new formulation in order to get other bounds. We consider several possibilities of relaxing the constraints. In addition, we develop branch-and-bound algorithms based on both formulations and the obtained bounds. We evaluate the computational e¢ ciency of all proposed algorithms with hard test instances from the literature. Computational results are reported and comparisons with other algorithms from the literature are carried out. / Neste trabalho, estudamos o problema de localização simples (SPLP - Simple Plant Location Problem). Usando a formulação matemática clássica e uma outra formulação proposta recentemente, desenvolvemos vários algoritmos para encontrar limites inferiores e superiores, bem como algoritmos tipo branch-and-bound. Com a formulação clássica, tais limites são obtidos utilizando o método de correção de dados e critérios de dominância entre os custos …xos e de transporte. Propomos uma projeção dessa formulação, que se mostrou computacionalmente atrativa. Usando a nova formulação propomos e mostramos a corretude de vários procedimentos iterativos que procuram encontrar uma solução para o problema, resolvendo uma seqüência de subproblemas paramétricos obtidos com a remoção de variáveis e restrições da formulação original. Em cada iteração desse processo, podemos gerar limites inferiores e superiores. Aplicamos ainda relaxação lagrangeana a essa nova formulação para obter outros limites. Analisamos várias possibilidades de relaxação das restrições. Desenvolmento também algoritmos branch-and-bound baseados em ambas as formulações e nos limites obtidos. Avaliamos a e…ciência computacional de todos os algoritmos com instâncias de teste difíceis, disponíveis na literatura. Resultados computacionais e comparações com outros algoritmos da literatura são reportados.

Dissertação (Mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2014 / Made available in DSpace on 2015-02-05T21:07:09Z (GMT). No. of bitstreams: 1 329082.pdf: 2114425 bytes, checksum: 7619c2267ed887db1dd635bd0fd5e7f9 (MD5) Previous issue date: 2014 / A introdução de fontes renováveis com capacidade variável, tais como usinas eólicas e fotovoltaicas, traz grandes desafios para a operação dos sistemas de energia elétrica. São necessárias ferramentas computacionais capazes de realizar a análise da condições operativas dos sistemas na presença dessas novas fontes de geração. O presente trabalho apresenta uma ferramenta computacional que otimiza os custos da operação de um sistema elétrico incorporando o comportamento aleatório da geração eólica. As equações que fornecem o ponto de operação em regime permanente de usinas eólicas são inseridas no problema de fluxo de potência ótimo (FPO), sendo a aleatoriedade do vento representada através de cenários de velocidade de vento equiprováveis. O problema FPO é formulado de maneira que a complementação da geração eólica seja feita pelas usinas hidrelétricas, enquanto que as usinas termelétricas mantêm constantes suas gerações nos diferentes cenários de vento. Utilizam-se conceitos da relaxação Lagrangenana e da programação dual para viabilizar a resolução do problema. Com o intuito de melhorar o desempenho da ferramenta computacional as restrições relaxadas são adicionadas a função objetivo através de um termo linear e um termo quadrático, resultando em um Lagrangeano Aumentado. O problema é resolvido através do Método dos Multiplicadores com Direção Alternada (MMDA). A eficácia da ferramenta computacional é avaliada através de simulações em três sistemas elétricos, sendo eles: os sistemas teste do IEEE de 14 e 30 barras e um equivalente do sistema da Região Sul com 192 barras. Os resultados obtidos mostram a aplicabilidade do modelo FPO e a eficiência do método de resolução.<br> / Abstract: The use of renewable energy sources, with variable generation capacity, brings new challenges to power system operation. Computational tools used in the analysis of the system must be updated in order to properly represent the impact of this new type of generation on system. This work describes a computational tool to minimize operational costs of hidrothermal systems considering the random behavior of wind power generation. The equations that express the steady state operation of wind farms are incorated in a estochastic optimal power flow (OPF) problem that represent the variability of wind through a set of equiprobable scenarios. The OPF problem is formulated in a way that wind power generation is complemented by hydro generation, while the thermoelectric plants maintain the same dispatch in every scenario of wind. The Lagrangian Relaxation is used solve the problem. In order to improve the performance of the solution algorithm, the relaxed constraints are introduced into the OPF objective function by linear and quadratic penalties, which results in a Aungmented Lagrangian. The problem is solved by the Alternating Direction Method of Multpliers (ADMM). The efficiency of the computacional tool is evaluated through simulations using the IEEE test systems with 14 and 30 buses and an equivalent of the Brazilian Southern Region system with 192 buses. The results demonstrate the applicability the OPF model proposed and the efficiency of the solution method.

El problema abordado en este trabajo consiste en evaluar cuál es el mejor enfoque para enfrentar la planificación minera considerando el precio como un valor incierto. Lo anterior implica determinar la extracción óptima y como el flujo de material será manejado al interior de la mina. Para ello se utilizó una modelación, basada en la mina de cobre de El Teniente, que considera un horizonte de planificación de 5 periodos. Las restricciones principales incluyen el secuenciamiento de la extracción, la construcción del túnel y el condicionamiento a un ingreso mínimo. La incertidumbre en el precio del cobre es representada a través de escenarios probabilísticos de precios, en los cuales cada uno tiene igual probabilidad de ocurrencia, y se resuelve mediante los enfoques: estocástico de maximización del valor esperado, determinístico estático de precio promedio, determinístico estático del peor caso, determinístico dinámico de precio promedio, determinístico dinámico del peor caso y el algoritmo del volumen con una heurística complementaria sencilla. Cada enfoque es evaluado mediante el valor de su función objetivo, su tiempo de resolución y su capacidad de entregar soluciones factibles. Al finalizar, se observa que el enfoque estocástico presenta el mejor desempeño a nivel de solución, pero con tiempos de resolución bastante superiores que los otros enfoques y que, por lo tanto, hacen poco atractivo el uso de éste en problemas de gran tamaño, donde la capacidad computacional se transforma en la principal limitante. Por este motivo y dado que los métodos determinísticos dinámicos presentan soluciones muy superiores a los casos estáticos y con valores muy cercanas al óptimo estocástico, se recomienda el uso de estos últimos para este tipo de problemas. Además se sugiere que las empresas analicen soluciones que acepten un cierto nivel de infactibilidad, pues se observó que la solución óptima se condicionaba fuertemente por la secuencia de extracción y, por consiguiente, al peor caso. En este sentido, un cambio marginal en dicho caso podría llevar a mejoras que pueden resultar significativas para una empresa.

O trabalho apresentado nesta dissertação é referente ao estudo da evacuação de pessoas, mais especificamente, a evacuação predial faseada. O objetivo é determinar, para instâncias de até 25 andares, os instantes de liberação de cada grupo de pessoas, a fim de minimizar o tempo total de evacuação do edifício. No entanto, a determinação destes instantes deve considerar o risco ao qual os diferentes grupos estão submetidos, priorizando a evacuação do andar afetado. Além disso, os conflitos de diferentes grupos por espaço nas rotas de evacuação também devem ser evitados, já que, são nessas situações que acontecem grande parte dos acidentes. Para atingir tal objetivo, foi elaborado um modelo matemático de programação linear inteira. Devido à alta complexidade do modelo, fez-se necessária a aplicação de métodos heurísticos para a obtenção de soluções. Dessa maneira, foram desenvolvidas uma heurística de busca baseada em GRASP e uma heurística lagrangeana. Apesar da heurística lagrangeana atestar a qualidade da solução (a partir da comparação do resultado obtido com o limitante inferior), a heurística de busca mostrou-se mais adequada para o problema, pois forneceu resultados de qualidade com pouco esforço computacional. / This dissertation studies the evacuation of people, more specifically, building phased evacuation. The objective of this study is to determine, for buildings of up to 25 floors, in which instants each group of people has to be released, in order to minimize the total evacuation time. Furthermore, the determination of these instants has to consider the risk to which each group of people is submitted, thus the affected floor has to be the first group to be released. In addition, conflicts for space between groups should be avoided, since such situations increase the occurrences of accidents. To achieve this goal, an integer linear programming model was designed. Due to the high complexity of the model, it was necessary to apply heuristics to obtain solutions for some instances. Therefore, a search heuristic based on GRASP and a lagrangian heuristic were developed. Despite the fact that the lagrangian heuristic attests to the quality of the solution (when it is compared to the lower bound), the search heuristic was considered more suitable for this problem because it provided quality results with lower computational efforts.

Made available in DSpace on 2014-06-12T18:29:31Z (GMT). No. of bitstreams: 2 arquivo642_1.pdf: 654722 bytes, checksum: c368d994dd4edb99c697edbaacfcabea (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Este trabalho visa a abordar alguns tópicos sobre geometria simplética com o intuito de estudar técnicas que serão úteis para trabalhos futuros. Apresentamos uma estrutura diferenciável para a Grassmanniana Lagrangeana de um espaço vetorial simplético, com tal estrutura definimos o índice de Maslov via grupóide fundamental para caminhos na Grassmanniana Lagrangeana e provamos algumas de suas propriedades. Antes, fazemos uso da topologia algébrica para definir e estudar algumas das propriedades do grupóide fundamental de um conjunto, neste momento apresentamos o teorema de Seifert-van Kampem. Para efeito de completude do trabalho, começamos esta dissertação exibindo os conceitos básicos da álgebra linear simplética, e em seguida dedicamos um capítulo para o estudo de algumas propriedades do índice de uma forma bilinear em um espaço vetorial, e de alguns resultados a respeito de curvas no espaço das formas bilineares simétricas de uma espaço vetorial de dimensão finita

Fornecedores necessitam atender a demanda de seus clientes da forma mais adequada possível e mantendo a qualidade de seu serviço, porém em muitos casos essa demanda é desconhecida. Esse problema pode ser modelado como um problema de roteirização e estoque com demanda estocástica o qual inclui o controle de estoque, transporte do produto e decisões de agendamento da entrega. Existem vários trabalhos na literatura para resolver esse problema, porém nenhum deles lida com janela de tempo de atendimento, capacidade máxima de estoque tanto no cliente quanto no depósito e o nível de confiança de atendimento individualizado para cada cliente. O objetivo principal deste trabalho é propor um novo algoritmo baseado em otimização matemática para lidar com esse problema mais realista. Além disso, este trabalho tem como objetivo secundário melhorar o algoritmo de estado da arte baseado em otimização matemática, visando encontrar soluções com um menor tempo computacional e custo. Foram realizados experimentos com instâncias sintéticas com 15 até 50 clientes, as quais são geradas aleatoriamente, e com uma instância real, baseada na experiência profissional no mercado empresarial e em cenários reais de distribuição na cidade de São Paulo / Providers need to supply the demand of their clients as optimally as possible and maintaining the quality of their service, however in many cases this demand is unknown. This problem can be modeled as a inventory routing problem with stochastic demand, which includes inventory control, product transportation and delivery scheduling decisions. There are several papers in the literature to solve this problem, but none of them deals with service time window, maximum stock capacity for both the customer and the depot and individualized confidence level for each costumer. The main objective of this work is to propose a new algorithm based on mathematical optimization to deal with this more realistic problem. In addition, this work has as secondary objective to improve the state of the art algorithm based on mathematical optimization, aiming to find solutions with a lower computational time and cost. Experiments were performed with synthetic instances with 15 to 50 clients, which are randomly generated, and with a real instance, based on professional experience in the business market and in real distribution scenarios in the city of São Paulo