[pt] Esta tese apresenta uma nova proposta para modelagem das funções de custo futuro, utilizadas na Programação Dinâmica Estocástica (PDE). A técnica proposta é aplicada ao planejamento da operação de médio prazo de sistemas elétricos de potência. Através da discretização do espaço de estados, o algoritmo de fechos convexos (convex hull) é utilizado na obtenção de uma série de hiperplanos que compõe um conjunto convexo. Estes planos representam uma aproximação linear por partes da função de custo futuro. O custo operacional médio utilizando a metodologia proposta considerando-se um único cenário de afluências foi comparado com o custo obtido da programação dinâmica dual determinística para o mesmo cenário de afluências. Esta análise mostra a convergência das duas metodologias e é utilizada para determinar o nível mínimo de discretização necessário para modelagem das funções de custo futuro. A partir deste resultado é feita a extensão da análise para diversos cenários de afluências utilizando-se a metodologia proposta, sendo a função de custo futuro obtida através da média do custo de operação para os diversos cenários, em cada discretização. A aplicabilidade do método é mostrada utilizando um caso exemplo de duas usinas hidrelétricas reais em cascata. Adicionalmente, um estudo de caso analisa as vantagens da paralelização do código de programação, onde métricas tais como fator de aceleração e eficiência são analisadas. Por fim, é apresentada uma simulação contendo todo o sistema elétrico brasileiro, representado por reservatórios equivalentes. / [en] This thesis presents a new approach for the expected-cost-to-go functions modeling used in the stochastic dynamic programming (SDP) algorithm. The proposed technique is applied to the long-term operation planning of electrical power systems. Using state space discretization, the convex hull algorithm is used for constructing a series of hyperplanes that composes a convex set. These planes represent a piecewise linear approximation for the expected-cost-to-go functions. The mean operation costs obtained by the proposed methodology for a single water inflow scenario were compared with those from the deterministic dual dynamic programming for the same inflow scenario.This sensitivity analysis shows the convergence of both methods and is used to determine the minimum discretization level necessary to model the expected-cost-to-go functions. From the obtained result the proposed methodology is extended to the analysis of a set of water inflow scenarios, where the expected-cost-to-go function is obtained by the mean operation cost to all the considered scenario in each discretization level. The applicability of the proposed methodology for two hydro plants in a cascade is demonstrated. Additionally, a case study using code parallelization is presented aiming at gaining computational performance, where the parallelization performance, as speedup and efficiency are measured. To finish with a simulation with the whole Brazilian electrical system considering aggregated reservoir is presented.

[pt] Muitas aplicações são tornadas programáveis para usuários finais avançados adicionando recursos como scripting e macros. Outras aplicações dão a uma linguagem de programação um papel central na sua interface com o usuário. Esse é o caso, por exemplo, da linguagem de fórmulas de planilhas de cálculo. Enquanto a área de scripting se beneficiou dos avanços das pesquisas em linguagens de programação, produzindo linguagens maduras e reusáveis, o estado das linguagens em nível de interface não teve o mesmo grau de desenvolvimento. Argumentamos que um melhor entendimento desta classe de linguagens se faz necessário. Neste trabalho, modelamos semânticas de linguagens de usuário final existentes, em três diferentes domínios: multimídia, planilhas e engenharia. Nosso foco é em linguagens de dataflow, um paradigma representativo em aplicações programáveis por usuários finais. Com base nessa análise, temos como objetivo prover um melhor entendimento do design de linguagens de dataflow no contexto de programação de usuários finais e propor linhas-guia para o projeto de linguagens de nível de interface baseadas neste paradigma para aplicações programáveis. / [en] Many applications are made programmable for advanced end-users by adding facilities such as scripting and macros. Other applications take a programming language to the center stage of its UI. That is the case, for example, of the spreadsheet formula language. While scripting has benefited from the advances of programming language research, producing mature and reusable languages, the state of UI-level languages lags behind. We claim that a better understanding of such languages is necessary. In this work, we model the semantics of existing end-user programming languages in three different domains: multimedia, spreadsheets and engineering. Our focus is on dataflow languages, a representative paradigm for end-user programmable applications. Based on this analysis, we aim to provide a better understanding of dataflow semantics as used in the context of end-user programming and propose guidelines for the design of UI-level languages for end-user programmable applications.

[pt] Métodos de otimização topológica estrutural visam obter a melhor distribuição de material dentro de um dado domínio, sujeito a carga, condições de contorno e restrições de projeto, de forma a minimizar alguma medida especificada. A otimização topológica estrutural pode ser dividida em dois tipos: contínua e discreta, sendo a forma discreta o foco da pesquisa desta dissertação. O objetivo deste trabalho é a criação de um sistema para realizar todos os passos dessa otimização, visando a resolução de problemas com grandes dimensões. Para realizar esse tipo de otimização, é necessária a criação de uma malha densa de barras, esta definida como conjunto de nós cobrindo todo o domínio, conectados através de barras, além da especificação dos apoios e das forças aplicadas. Este trabalho propõe um novo método para geração da malha densa de barras, utilizando como entrada somente o contorno do domínio que se deseja otimizar, contrapondo com métodos que necessitam de um domínio já discretizado, como uma malha de poliedros. Com a malha gerada, este trabalho implementou a otimização topológica, sendo necessário resolver um problema de programação linear. Toda a parte de otimização foi realizada dentro do framework TopSim, tendo implementado o método dos pontos interiores para a resolução da programação linear. Os resultados apresentados possuem boa qualidade, tanto na geração quanto na otimização, para casos 2D e 3D, tratando casos com mais de 68 milhões de barras. / [en] Structural topology optimization methods are used to find the optimal material distribution within a given domain, subject to loading, boundary conditions and design constraints, in order to minimize some specified measure. Structural topology optimization can be divided into two types: continuum and discrete, with the discrete type being the research focus of this dissertation. The goal of this work is the creation of a system to achieve all the steps of this optimization process, aiming problems with large dimensions. In order to perform the optimization, it is necessary create a ground structure, defined as a set of nodes covering the entire domain, connected by bars, with the supports and the applied loads. This work proposes a new method for the ground structure generation, using as input only the domain boundary, in contrast with methods that require a domain already discretized, such as a polyhedron mesh. With the generated mesh, this work has implemented the topological optimization, needing to solve a linear programming problem. All the optimization part was performed within the TopSim framework, implementing the interior point method for the linear programming resolution. The results presented have good quality, both in generation and optimization, for 2D and 3D cases, considering cases with more than 68 million bars.

[pt] O objetivo deste trabalho é o de apresentar uma proposta de metodologia para a análise de estruturas pelo Método dos Elementos Finitos, utilizando-se na sua implementação as técnicas de programação orientada a objetos e computação distribuída. A utilização das técnicas de programação orientada a objetos permite a implementação de um código compacto, portável e de fácil adaptação. Para a implementação do código optou-se pela utilização da linguagem C++, que possui os recursos mais importantes da programação orientada a objetos, destacando-se a herança, o polimorfismo e a sobrecarga de operadores, e da biblioteca MPI de computação paralela. Inicialmente serão apresentados os procedimentos necessários à implementação orientada a objetos da análise de estruturas pelo método dos elementos finitos, sendo posteriormente apresentadas às alterações necessárias à inclusão das técnicas de processamento paralelo, empregando-se duas técnicas de paralelização. A grande quantidade de operações matriciais envolvidas na análise de estruturas pelo método dos elementos finitos motivou ainda o desenvolvimento de uma biblioteca de classes para a representação destas operações. Os exemplos apresentados têm a finalidade de verificar a exatidão dos resultados obtidos com o código implementado, e as vantagens de se empregar a programação orientada a objetos e a computação distribuída / [en] This work focuses on a methodology for the analysis of structures based on the Finite Element Method (FEM) using on its implementation object-oriented programming techniques, together with parallel programming. The usage of object-oriented programming techniques allows the implementation of a compact, portable and of easily adaptable source code. The implementation was carried out using C++ language, which has the main features of the object-oriented programming, such as inheritance, polymorphism and operator overloading, and the MPI library for parallel computing. The procedures taken into account on object-oriented implementations for analysis of structures using the Finite Element Method are presented, followed by the modifications needed for including parallel computing, using two strategies. Also, the large amount of matrix operations involved on the structures analysis using Finite Element Method motivated the development of a class library which represents such operations. The examples presented have the purpose of verify the accuracy of the results obtained with the code, and the advantages of the use of object-oriented programming and parallel computing.

[pt] Esta tese propõe uma metodologia para obter uma solução para problemas de programação linear fuzzy. A metodologia aqui descrita apresenta um conjunto de soluções em que tanto os valores das variáveis quanto o valor ótimo para a função de custo, ou função objetivo, possuem uma faixa de valores possíveis. Assim, é possível fornecer um conjunto de soluções factíveis que atendam a diferentes cenários, além de fornecer ao tomador de decisões uma ferramenta de análise mais útil, permitindo que sejam analisadas outras soluções possíveis antes de se escolher uma solução em particular. O problema é resolvido de forma iterativa, tornando mais simples e de fácil aplicação a metodologia desenvolvida. / [en] This work proposes an approach to obtain a solution to linear fuzzy programming problems. The approach described here presents a solution set in where both the variables values and the cost function optimun value to have an associated membership function. Thus, it is possible to provided not only a feasible solution set applicable to different scenarios but also to supply the decision maker with a more powerful tool for the analysis of other possible solutions. The problem is solved in an interactive way, so that the developed is approach easily applicable and simple to handle

[pt] O objetivo deste trabalho é apresentar as formulações variações para o problema de análise limite e o desenvolvimento do processo de resolução, que envolve o método dos elementos finitos e as técnicas de programação matemática. As formulações variacionais são apresentadas em três versões: estática, cinemática e mista. Estas formulações são derivadas a partir da proposição das relações constitutivas na forma de pseudo-potenciais conjugados. Esses princípios são discretizados através do método dos elementos finitos. São propostos dois algoritmos iterativos de programação matemática para a solução do problema. Os algoritmos podem ser aplicados tanto para o comportamento plástico descrito por funções de escoamento lineares como não lineares. Nas aplicações numéricas são analisados corpos em estado plano de tensão, deformação e com simetria de revolução. / [en] The aim of this work is to present variational formulations for the limit analysis problem and solution procedures using the finite element method and mathematical programming techniques. The variational formulations are presented in three versions: static, kinematical and mixed. These formulations are derived from the proposition of the constitutive relationship in the form of conjugate pseudopotencials. Finite element discretizations are proposed for each of the three continuous problems. Two iterative mathematical programming algorithms are prosed to solve the problem. These algorithms can be applied to the plastic behavior described by a set of linear or non-linear yield functions. Limit analysis in plane strain, plane stress and axissymetric solids are considered in the numerical examples.

[pt] Uma gestão eficaz da cadeia de negócio do gás natural com logística de transporte por gasodutos, considerando os principais agentes, como Carregador, Produtor, Transportador e Distribuidor, requer a utilização de tecnologia de informação e sistemas de suporte à decisão. Este trabalho apresenta um Sistema de Gestão de Logística de Transporte de Gás Natural por Gasodutos - SGLT, composto de módulos ou subsistemas integrados que propiciam maximizar a comercialização do gás natural e mitigar a ocorrência de perdas de receitas e multas contratuais devido a contingências que podem gerar falha de entrega do gás natural ao Distribuidor. Permite também avaliar o nível ótimo econômico de confiabilidade que deve ser mantido pelo Transportador, através da implantação de redundâncias, para mitigar sua exposição aos riscos de perdas de receitas e multas contratuais por parte dos agentes envolvidos na cadeia do negócio de gás natural. O sistema proposto é fundamentado na simulação Monte Carlo de falhas de equipamentos da malha de gasodutos de transporte e de restrições de oferta e demanda de gás natural, bem como os fechamentos acidentais de válvulas de bloqueio de gasodutos e de falhas nos pontos de entrega de gás natural de modo a quantificar seus impactos na Cadeia do Negócio do Gás Natural. O sistema proposto é constituído de (i) um Sistema de Informação Geográfico - SIG, (ii) um modelo de dados de gasodutos (Arc Pipeline Data Model - APDM), (iii) um simulador termo-hidráulico de escoamento de gás por dutos em regime permanente e transiente - Pipeline Studio 3.0, (iv) uma base de dados dos resultados das simulações termohidráulicas, (v) um modelo de simulação Monte Carlo para avaliação da confiabilidade do sistema de transporte utilizando o software @Risk 4.5, (vi) um modelo econômico com simulação Monte Carlo utilizando o software @Risk 4.5 e (vii) um otimizador, baseado em programação linear, para maximização da comercialização de gás e para minimização de perdas de receitas e multas contratuais devido a cortes de fornecimento de gás decorrentes de situações contingenciais. Este trabalho permitiu identificar, quantificar e justificar economicamente a implantação de unidades compressoras reservas nas estações de compressão do Gasoduto Bolívia-Brasil, e aumentar a disponibilidade do sistema de compressão, reduzindo acentuadamente a exposição do Transportador a perdas de receita e penalidades contratuais por redução de capacidade de transporte decorrentes da entrada em manutenção de unidades compressoras e de falhas não-programadas de tais equipamentos. Foram também identificadas e quantificadas as falhas de válvulas de bloqueio de gasoduto e das estações de entrega de gás, não cabendo, nestes casos, a implantação de redundância. / [en] An efficient management of the natural gas business chain, based on pipeline transmission network and taking into consideration the interaction between the main players such as Shippers, Suppliers, Transmission Companies and Local Distribution Companies, requires the use of information technology and decision-making support systems. This work presents a Natural Gas Logistic Transportation Management System, composed of integrated modules or subsystems that allow maximizing natural gas commercialization and allow mitigating revenue losses and contractual penalties due to contingencies that may cause failures in gas delivery to Local Distribution Companies. The proposed system also allow evaluating the optimum economic level of availability to be maintained by the Transmission Company by using stand-by equipment to mitigate its risk exposures to revenue losses and contractual penalties from the agents of the natural gas chain. The proposed system is based on Monte Carlo simulation of equipment failures of the gas transmission network, on the supply/delivery unexpected shortfalls, unexpected block valves closing and failures on the city-gates in order to quantify their impact on the natural gas business chain. The proposed system is made of (i) a geographic information system - GIS, (ii) a pipeline data model (Arc Pipeline Data Model - APDM), (iii) a gas pipeline thermo-hydraulic simulation for steady and transient states - Pipeline Studio 3.0, (iv) a data base of thermohydraulic simulation results and (v) a Monte Carlo simulation model to evaluate the reliability of the transmission system by using @Risk 4.5 and (vi) an economic model with Monte Carlo simulation using @Risk 4.5 and (vii) an optimizer, based on linear programming, for gas commercialization maximization and minimization of revenue losses and contractual penalties for not delivering the gas volumes at the contracted level. This work has identified, quantified and proved feasible the installation of stand-by compressor units at the Bolivia-Brail Gas Pipeline compressor stations and therefore improved the transmission system availability. As a direct benefit has reduced the Transmission Company risk exposure to revenue losses and contractual penalties due to reduction of pipeline transmission capacity as consequence of compressor units scheduled and nonscheduled outages. Failures of pipeline block valves and city-gates have also been identified and quantified but redundancy improvements were not required.

[pt] Problemas de transporte de cargas fracionadas são grandes candidatos para a aplicação de técnicas de otimização como forma de obter um melhor aproveitamento de recursos. Nesta dissertação, são apresentados modelos de programação inteira e os algoritmos desenvolvidos para a resolução adequada dos problemas estudados neste contexto. O foco é o planejamento da movimentação dos veículos para o atendimento das demandas ao longo de um período pré-definido. Diferentes formas de contratação dos veículos são consideradas, demandas possuem janelas de tempo para serem atendidas e podem compartilhar um mesmo veículo em um ou mais trechos do seu caminho até o destino. Conexões são permitidas, ou seja, uma demanda pode utilizar mais de um veículo para o seu atendimento, respeitando as capacidades operacionais dos centros de distribuição e coleta. Os objetivos abrangem o dimensionamento da frota, que possui um custo fixo, e o planejamento da operação ao longo do período. Este deve determinar quais demandas são transportadas por quais veículos em que instantes e em que trechos. O método de resolução proposto utiliza algoritmos para a construção e pré-processamento de grafos que representam o problema e permitem que a formulação como programa inteiro tenha uma resolução mais efciente. Além disso, o algoritmo correspondente resolve uma sequência de programas inteiros para obter soluções viáveis de qualidade para as diferentes versões do problema aqui considerado. Melhorias nos limites inferiores obtidos também são propostas. O código resultante foi testado em um conjunto de instâncias baseadas na operação de uma transportadora brasileira de grande porte. Resultados foram obtidos tanto para condições de utilização reais, isto é, com o tempo de execução limitado, como para testar os limites do método proposto. Em ambos os casos pôde-se obter soluções de alta qualidade comprovada. / [en] Less-than-truckload transportation problems are great candidates for the application of optimization techniques as a form to obtain a better exploitation of resources. This thesis introduces integer programming models and the developed algorithms for the proper resolution of the studied problems in this context. The focal point is the vehicle's dislocation planning for the ideal attendance of the demands during a certain time period. Different forms of vehicle contract are considered. There are time windows for the attendances and demands can share a same vehicle in one or more parts of its route until his destination. Connections are allowed, that is, demands can use more than one vehicle for its attendance, respecting the operational capacities of the centers (collection and distribution stations). The goals embraces the sizing of the proper fleet which has a fixed cost, and the operation's planning during the period. This one should determine which demands are transported by which vehicles in what instants and where on routes. The resolution's method proposed uses algorithms for the graph's construction and pre-processing which represents the problem and allows that the formulation, as an integer program, to have a resolution more efficient. Furthermore, the corresponding algorithm solves a sequence of integer programs to obtain feasible quality solutions for the differents versions of the considered problem. Improvements on the lower bounds gotten are also proposed. The resulting code was tested in a set of proposed instances that were based on the operation of an important brazilian trucking company . Results were acquired such for conditions of real utilization, in other words, with a limited time of execution, as to test the limits of the proposed method. In both cases, solutions of comproved high quality were obtained.

[pt] A otimização em esportes é uma área que reúne diversas aplicações relacionadas ao planejamento e gestão de atividades esportivas. Diversas técnicas de otimização combinatória têm sido aplicadas, por exemplo, à  construção de tabelas de torneios e à  análise do desempenho de equipes em competições. Um problema que surge no contexto da organização de competições esportivas consiste na determinação de quais árbitros atuarão em cada partida de um determinado torneio. Diversas regras devem ser observadas no processo de atribuição de árbitros, que em geral envolve também a consideração de vários objetivos. Esta tese tem como objetivo principal apresentar um estudo sobre um problema de atribuição de árbitros, comum a várias ligas esportivas amadoras. Demonstra-se que a versão de decisão do problema estudado é um problema NP-completo. Considera-se inicialmente duas variantes mono-objetivo do PAA, que diferem uma da outra pela função objetivo adotada. Propõe-se modelos de programação linear inteira que permitem uma abordagem exata para a resolução de instâncias de pequeno e médio portes. Com o intuito de tratar instâncias de tamanho real, propõe-se também abordagens aproximadas de resolução baseadas na metaheurí­stica Iterated Local Search (ILS). Uma vez que o PAA tem origem em aplicações reais, ligadas a processos de tomada de decisões, é natural que envolva a consideração de diversos objetivos, muitas vezes em conflito. Tal fato motivou a investigação do uso de técnicas de otimização multi-critério que possam ser utilizadas na construção de um sistema de suporte a decisão e aplicadas a uma variante bi-objetivo do PAA, que considera simultaneamente as duas funções objetivo utilizadas nas variantes mono-objetivo estudadas. Abordagens de resolução exata e aproximada para esta variante bi-objetivo são propostas e seus resultados discutidos. / [en] Optimization in sports is a field of increasing interest. Combinatorial optimization techniques have been applied e.g. to game scheduling and playoff elimination. A problem that arises in competition management is the assignment of referees to games already scheduled. There are a number of rules and objectives that should be taken into account when referees are assigned to games. We address two mono-objective versions of a Referee Assignment Problem (RAP) common to many amateur leagues of sports such as soccer, baseball, and basketball. The problem is formulated by integer programming and its decision version is proved to be NP-complete. To tackle real-life large instances of the RAP, we propose a three-phase heuristic approach based on a constructive procedure, a repair heuristic to make solutions feasible, and a local search heuristic to improve feasible solutions, based on the metaheuristic iterated local search. Numerical results on realistic instances are presented and discussed. This work also investigates the solution of a bi-objective version of the RAP, which combines both objective functions used in the mono-objective versions. Exact and heuristic approaches are proposed to solve this bi-objective version and its computational results are discussed.

[pt] Uma facilidade é qualquer centro que presta serviços a um conjunto de clientes. Pode ser, dentre outros, uma escola, uma fabrica ou um armazém. Problemas de localização de facilidades são problemas de otimização combinatória que tratam da tomada de decisão relativa ao posicionamento destes serviços, que devem otimizar algum critério pré-definido. As medidas que usualmente são utilizadas para quantificar a qualidade de uma solução para esta classe de problemas tem seus cálculos baseados em que clientes são servidos por que facilidade. Uma conseqüência imediata é a forte relação entre os problemas de localização e os problemas de classificação de dados (clusterização). Dentre os problemas de localização de facilidades amplamente estudados esta o problema das p-Medianas (PMNC), objeto de pesquisa desta dissertação. O PMNC tem como objetivo determinar quais p facilidades devem ser abertas com o intuito de minimizar a soma das distancias de cada cliente a facilidade aberta mais próxima do mesmo. O PMNC é classificado como um problema NP - Difícil e é um dos problemas centrais na classificação automática de dados (clusterização). Esta dissertação apresenta algoritmos primais, duais e exatos para tratamento do PMNC, focando no desenvolvimento de algoritmos duais e exatos. Foram implementadas cinco heurísticas construtivas e um método de busca local. Além disto, foram propostos três novos métodos duais e um método exato. Como resultado, analisamos um conjunto de técnicas para o tratamento do problema. A escolha da melhor técnica é fortemente dependente da configuração da instancia tratada. Foi obtido o ótimo para algumas instancias e para as demais a diferença entre o valor dos limites inferior e superior nos melhores casos não ultrapassam 3%. / [en] A facility is any center that offers services to a set of clients. It may be, among others, a school, a factory or a depot. Facility location problems are combinatorial optimization problems that handle decisionmaking in respect to the positioning of those services, optimizing some defined criteria. The measures often used to assess the quality of a solution for this class of problems relate to which clients are served by which facility. An immediate consequence is the strong relationship between location problems and data clustering. One of the widely studied facility location problems is the uncapacited p-median problem (UPM), the main subject of this thesis. Given a set of possible facility locations, the UPM consists in determining a subset of locations at which the facilities shall be established, minimizing the sum of distances from each client to its closest open facility. The UPM belongs to the class of NP-hard problems and is a central problem of data clustering. This thesis presents primal, dual and exact algorithms for approaching the UPM, focusing on the development of dual and exact algorithms. Five constructive heuristics and one local search method were implemented. Furthermore, three new dual methods and one exact method were proposed. The result is the analysis of a set of techniques to solve the problem. The choice of best technique is strongly dependent of the configuration of the treated instance. We obtained the optimum for some instances and for others the difference between the value of the lower and upper bounds in the best cases do not exceed 3%.