[pt] Além do seu importante papel metalúrgico, o coque representa mais da metade do custo de produção do ferro gusa e cerca de 20% do custo de fabricação do aço. Por isso, as siderúrgicas integradas buscam misturas de custo mínimo para produção de coque que atendam aos requisitos de qualidade. Para garantir essa qualidade, elas impõem aos seus fornecedores de carvão cláusulas contratuais relativas à umidade, cinzas, enxofre, fósforo, matéria volátil, fluidez, refletância e dilatação e, eventualmente, outras. Como nem sempre essas exigências são atendidas pelos fornecedores, penalidades contratuais são especificadas com o propósito de evitar que as siderúrgicas arquem com os custos causados por desvios de especificações. Entretanto, tais penalidades nem sempre refletem os custos realmente causados, pois estes decorrem não só da redução do material aproveitável, mas, também, dos reajustes necessários na mistura para que o coque se mantenha dentro da qualidade exigida. Essa dissertação propõe um sistema para determinação do ônus efetivamente causado por desvios nas especificações de um carvão contratado. Uma apresentação detalhada do problema, sua formulação como modelo de programação linear e um procedimento para a análise são propostos. Um sistema protótipo funcional foi desenvolvido e ilustrações numéricas das análises são discutidas. / [en] In addition to its important metallurgical role, the coke accounts for more than half of the total production cost of the pig iron and around 20% of the total cost of steel production. For this reason, the integrated steelmaking mills seek minimum cost coal blends for producing coke within the quality requirements. To guarantee this quality the steelmaking mills impose to their coal vendors some contractual clauses regarding humidity, ashes, sulfur, phosphor, volatile matter, fluidity, reflectance and dilatation, and sometimes, still others. Since these requirements are not always met by the vendors, contractual penalties are specified with the purpose of avoiding that the steelmakers end up with the burden of the costs caused by such specs deviations. Nonetheless, such penalties do not always reflect the actual costs they cause, because the latter derive not only from the reduction of the usable material, but also from the blend adjustments necessary to keep the coke within the required quality. This thesis proposes a system for determining the burden effectively caused by specs deviations. A detailed presentation of the problem, its formulation as a linear programming model and a procedure for analysis are proposed. A functional prototype system was developed and numerical illustrations of the analyses are discussed.

[pt] A indústria das comunicações tem passado nos últimos anos, mundialmente, por profundas transformações. A Internet é a responsável pela maior destas transformações. Com o advento da Internet, existe a necessidade de uma banda de transmissão maior para o tráfego de dados. Para resolver esse problema, surgiu o conceito de redes ópticas e a multiplexação no domínio do comprimento de onda. Entretanto, isso criou um outro problema: o roteamento dos pacotes. A maior parte das redes de comunicação hoje em dia, ainda possui muitos sinais eletrônicos, o que significa que os sinais ópticos precisam ser convertidos em elétricos para serem ampliados, regenerados ou roteados e, depois, reconvertidos para ópticos. Isso acaba gerando atrasos na transmissão dos sinais e um gargalo nas redes ópticas. Para minimizar este problema, vários algoritmos foram criados. Apegando-se a tais fatos, este estudo explora o tema para implementar um algoritmo de enumeração recursiva, que tem como objetivo alocação de comprimentos em redes ópticas, visando minimizar o custo total de transmissão. Esse algoritmo foi testado e comparado com o algoritmo de programação linear, que fornece a solução ótima. / [en] The communication industry was passing in lastest years by great transformations in world. Internet is the mainly responsable for that, because there is the necessity of a large band to data transmission. The optical networks concept and wavelength division multiplexing technology were arised in order to solve this problem. However, this created another problem: the packet routing. The major part of communications networks still has electronics signals. This means that the optical signals have to be converted into electrical signals to be amplified, regenerated and routed and later recovered into optical. This implies in a delay on the data transmission and creates a bottleneck in the optical networks. Some algorithms have been created to minimize this problem. This dissertation has tried to develop an algorithm to solve RWA (routing and wavelength assignment) problems, aiming at the minimum total cost to transmitt datas. This algorithm was tested and compared with the linear program algorithm that gives the optimal solution to RWA problem.

[pt] Problemas de Programação de Horários (PPHs) tem sido amplamente estudados, dada a sua importância prática e teórica. A maioria das variações do problema pertence µa classe NP-Difícil. Em geral, trata-se da alocação de recursos materiais e humanos no espaço e no tempo, visando a otimização de um conjunto de objetivos definidos. Na Programação de Horários de Cursos Universitários, por exemplo, o objetivo pode ser a satisfação do corpo docente e o desempenho acadêmico dos alunos. Nos últimos anos, as formulações de PPHs propostas pela International Timetabling Competition (ITC) tem sido bastante utilizadas, sendo notável a predominância de métodos baseados em busca local e metaeurísticas entre as abordagens propostas recentemente. Este trabalho tem como objetivo propor algoritmos para o Problema de Programação de Horários Pós-Matrícula da ITC, focando principalmente em métodos heurísticos baseados em Programação Matemática. Entre os modelos de Programação Linear Inteira Mista que propomos para este problema, destaca-se o modelo baseado na Formulação de Representantes Assimétricos para o Problema de Coloração de Grafos. Abordamos a aplicação da heurística de Local Branching e propomos um esquema de resolução por Geração de Colunas, como forma de viabilizar o tratamento dos modelos propostos, uma vez que a complexidade de tais modelos representa um desafio para os resolvedores de Programação Linear Inteira Mista atualmente disponíveis. / [en] Timetabling Problems have been widely studied, given its practical and theorical relevance. Most of its variations belong to the NP-Hard class of problems. In general, it is about allocation of material and human resources in time and space, aiming to optimize some set of defined objetives. In University Course Timetabling, for example, the objective might be the satisfaction of professors and the academic performance of students. In the last years, the formulations for timetabling problems proposed by the In- ternational Timetabling Competition (ITC) have been widely adopted. The predominance of meta-heuristics and local search-based methods is remark- able among the recently proposed approaches. The objetive of this thesis is to propose algorithms for the Post Enrolment-based Course Timetabling Problem of the ITC, focusing on Mathematical Programming-based heuris- tic methods. Among the Mixed Integer Linear Programming models that we propose for this problem, we highlight the one based on the Asymetric Representatives Formulation for the Graph Coloring Problem. We explore the application of the Local Branching heuristic and we propose a Column Generation solution procedure, as an attempt to handle the proposed models, given that the complexity of such models poses a challenge for currently available Mixed Integer Linear Programming solvers.

[pt] No cenário atual da economia mundial, é essencial aumentar a integração entre os diferentes atores da cadeia de suprimentos das empresas, reduzindo custos operacionais e melhorando a eficiência. O roteamento de navios é parte imprescindível dessa integração no comércio marítimo global, sendo objeto de estudo de muitos autores. Neste trabalho, apresentamos diferentes metodologias para resolver variantes do Problema de Roteamento Marítimo com Estoques. Esse problema envolve um grande número de variáveis e é computacionalmente complexo de ser resolvido. Nossa principal motivação é resolver um caso real de roteamento de navios de uma grande empresa do setor de Óleo e Gás, obtendo soluções de alta qualidade em tempos computacionais plausíveis e melhorando os resultados atuais da empresa. Todas as metodologias desenvolvidas são baseadas em uma combinação de uma meta-heurística com um modelo matemático de programação linear. Uma das principais diferenças entre as metodologias está no modelo matemático para resolver o problema de estoque, onde testamos abordagens de tempo discreto e tempo contínuo. As outras diferenças dizem respeito ao número de produtos avaliados (único ou múltiplos produtos) e à meta-heurística usada (heurística de busca local com um fator de probabilidade de Simulated Annealing ou Hybrid Variable Neighborhood Search). Para a metodologia que utiliza um modelo de tempo discreto, os resultados são satisfatórios, com violações baixas e pontuais do estoque em um tempo computacional aceitável. Para a metodologia que utiliza um modelo de tempo contínuo, os resultados são ainda melhores, uma vez que, em reduzido tempo computacional, as violações de estoque permanecem baixas ou inexistentes, dependendo do cenário avaliado e da meta-heurística utilizada. Os resultados obtidos neste trabalho são notáveis e permitem sua aplicação prática em casos reais. / [en] In the current scenario of the world economy, it is essential to increase the integration between the different players in the companies supply chain, reducing operational costs, and improving efficiency. Ship routing is a substantial part of this integration regarding global maritime commerce, being the object of study by many authors. In this work, we present different methodologies to solve variants of the Maritime Inventory Routing Problem. This problem involves a large number of variables and is a computationally complex problem to solve. Our primary motivation is to solve a ship routing real case of a large company in the Oil and Gas sector, achieving high-quality solutions in plausible processing times and improving companies current results. All developed methodologies are based on a metaheuristic combination with a linear mathematical model. One of the main differences between the methodologies lies in the mathematical model to solve the inventory problem, where we tested discrete-time and continuous-time approaches. Other differences concern the number of evaluated products (single or multi-product) and the metaheuristic used (local search heuristics with a Simulated Annealing probability factor or Hybrid Variable Neighborhood Search). For the methodology using the discretetime model, the results are satisfactory, with low and punctual inventory violations in an acceptable computational time. For the methodology using the continuous-time model, the results are better once, in reduced computational time, inventory violations remain low or non-existent, depending on the scenario evaluated and the metaheuristic used. The results obtained in this work are remarkable and allow its practical application for real cases.

[pt] O presente trabalho tem por objetivo desenvolver uma formulação e um sistema que seja uma ferramenta auxiliar para o engenheiro de projeto na definição de modelos de bielas e tirantes de estruturas bi-dimensionais. No sistema desenvolvido o usuário pode partir de um modelo complexo, com um número grande de barras nas mais variadas direções. Essa solução inicial pode se basear nos resultados em tensão de uma análise linear elástica por elementos finitos e na experiência do projetista. Todavia, como o usuário terá muitas dúvidas quanto ao melhor modelo as ser usado, ele pode superpor no modelo inicial todas as soluções que achar possíveis. A função do sistema é escolher entre todas as soluções admissíveis (aquelas que respeitam equilíbrio e resistência) a que for mais econômica. Define-se como solução mais econômica aquela que corresponder ao menor consumo de armadura. A formulação do problema conduz a um problema de Programação Linear (PL) e o programa LINDO [2] é utilizado para resolvê-lo. A visualização do modelo é também parte do sistema desenvolvido e é feito a partir dos resultados gerados pelo programa LINDO. O trabalho se divide basicamente em três partes. Na primeira parte é feita uma revisão sobre modelos de bielas e tirantes e sobre fundamentos de programação linear. A segunda parte consta da formulação do problema e por ultimo os resultados do programa são comparados com aqueles fornecidos pela literatura. A ferramenta desenvolvida neste trabalho pode ser de grande utilidade para a definição de modelos de bielas e tirantes mas ela nem de longe tem a pretensão de substituir a experiência, a intuição e o bom senso do engenheiro de projeto que deve sempre prevalecer, inclusive na análise crítica dos resultados do programa. / [en] The present work has the aim of developing a formulation and a computational system, which should be used by the structural engineers an auxiliary tool in the definition of strut and tie models of bidimensional structures. In the developed system the user can define initially a very complex system with a great number of bars and many different directions. This initial solution can be based on both the stress results of a linear elastic finite element analysis and the experience of the engineer. As the user may be in doubt about the best model to be used he may superimpose in the initial model all the allowable solutions he may find. The aim of the system is to choose among all the allowable solution (these ones wich satisfy equilibrium and strenght) the more economical one. As more economical solution is considered the one which correspond to the least consumption of reinforcement. The problem formulation leads to a linear programming problem (LP) and the LINDO program [2] is used for solving it. The visualization of the model and results is also part of the system. It is based on the data generated by the LINDO program. The work is basicaly divided in three parts. In the first one a revision about strut and tie models as well as the basic knowledge in linear programming is presented. In the second part the problem formulation is shown and the last the results of the program are compared with those old the technical literature. The computational tool presented here may be of great utility in the definition of strut and tie models, but it has not by far the intention and the feeling of the engineers which shall ever prevail, inclusive in the critic analysis of the program results. / [es] El presente trabajo tiene como objetivo desarrollar un sistema que sirva como herramienta auxiliar para el ingeniero de proyecto en la definición de modelos de bielas y tirantes de extructuras bidimensionales. En el sistema desarrollado, el usuario puede partir de un modelo complejo, con un número grande de barras en varias direcciones. Esa solución inicial puede basearse en los resultados en tensión de un análisis lineal elástica por elementos finitos y en la experiencia del proyectista. Como el usuario tendrá muchas dudas respecto al mejor modelo as ser usado, él puede superponer en el modelo inicial todas las soluciones que juzgue posibles. La función del sistema es elegir entre todas las soluciones admisibles (aquellas que respetan equilibrio y resistencia) la que sea más económica. Se define como solución más económica aquella que correspdonda al menor consumo de armadura. La formulación del problema conduce a un problema de Programación Lineal (PL) que es resuelto con ayuda del programa LINDO [2]. La visualización del modelo también es parte del sistema desarrollado y parte de los resultados generados por el programa LINDO. El trabajo se divide básicamente en tres partes. En la primeira parte se realiza una revisión de los modelos de bielas y tirantes y de los fundamentos de programación lineal. La segunda parte contiene la formulación del problema y la presentación de los resultados del programa se comparan con los reportados en la literatura. La herramienta desarrollada en este trabajo puede ser de gran utilidad para la definición de modelos de bielas y tirantes pero no tiene la pretensión de substituir la experiencia, la intuición y el buen senso del ingeniero de proyecto que debe siempre prevalecer, incluso en el análisis crítico de los resultados del programa.

[pt] O aumento da produção de petróleo brasileiro e o consequente aumento na demanda por transporte marítimo levaram a PETROBRAS a buscar ferramentas para aumentar a eficiência de seu transporte marítimo. Neste sentido, a atividade de programação de navios busca alocar os navios a um conjunto de cargas definido a priori, respeitando as restrições comerciais e operacionais, a fim de transportá-las com o menor custo possível. Com o intuito de auxiliar o programador nesta atividade, esta dissertação propõe um sistema de suporte à decisão (SSD) baseado em otimização para a programação de navios. O SSD proposto foi desenhado especificamente para a atividade de longo curso de navios de petróleo da PETROBRAS, sendo este gerado a partir da adaptação de modelos disponíveis na literatura acadêmica. Os testes comparativos realizados com o protótipo do SSD na atividade de longo curso de navios de petróleo mostraram que a ferramenta tem um significativo potencial de redução de custo. O SSD proposto se apresentou como uma opção viável para auxiliar a programação de navios da companhia na busca pela redução de custos de transporte marítimo. / [en] The increasing production of Brazilian oil and the consequent increase in the demand for shipping, led PETROBRAS to seek tools to increase the efficiency of its shipping. In this sense, the activity of ship scheduling seeks to assign vessels to a set of cargos, respecting business and operational restrictions in order to transport them with the lowest possible cost. To assist the ship scheduling planner in this activity, this dissertation proposes an optimization based decision support system (DSS) for ship scheduling. The proposed DSS was designed specifically for the long-term tanker scheduling activity at PETROBRAS and it was implemented based on models available in the academic literature. The comparative tests using the DSS prototype proposed in this dissertation showed that it has a potential for significant cost reduction. The proposed DSS was considered a viable tool to assist the ship scheduling planners in reducing shipping costs.

[pt] Esta dissertação apresenta um modelo de programação linear para mercados virtuais, que tem como objetivo principal incentivar vendedores a oferecerem preços mais baixos e compradores a pagarem mais pelos produtos. Esse incentivo é feito através de compensações aos participantes do mercado que agirem desta forma. O modelo funciona basicamente como um leilão bi-lateral, onde tanto vendedores quanto compradores podem dar seus lances. Para este modelo básico foram modeladas extensães como: existência de custo de transporte entre vendedores e compradores; economia de escala no preço do comprador; possibilidade de múltiplos produtos em um mesmo leilão. Para o modelo básico e cada uma das extensões propostas foi elaborado o sistema de compensações baseados em princípios da Teoria dos Jogos. Em cada caso, foi verificada a existência de soluções de núcleo e como essas soluções determinam as características do mercado. / [en] This work presents a linear programming model for virtual markets. The main objective is to encourage sellers to offer lower prices and buyers to pay more for products. This is done through a system where the agents are awarded for acting this way. The basic version of the model works as an auction where buyers and sellers can make their bids. Some extensions were developed for this basic model, to allow situations like: transportation cost between buyers and sellers; scale economy for the buyer's price; multiples products in the same auction. For the basic model and each of its extensions, the system of awards has been developed based on Game Theory principles. In each case, the model was reinterpreted as a game and its core solutions were found. It was also verified how these solutions determine market's behavior.

[pt] As despesas anuais em saúde para a maioria dos países são crescentes. Segundo a Organização Mundial de Saúde (OMS), em 2011 o Brasil gastou aproximadamente 10 porcento do produto interno bruto em saúde. Consequentemente, incrementar a eficiência na prestação de serviços médicos está se tornando cada vez mais importante. Em um hospital as salas de cirurgia representam um dos principais centros de custos e de rendimentos. As salas de cirurgia são um aspecto difícil de gerenciar devido à prioridade das partes envolvidas no processo, nomeadamente, pacientes, cirurgiões, staff, pessoal administrativo, e a escassez de recursos como leitos, salas de cirurgia, equipamentos especiais, etc. A presente dissertação aborda um problema real de programação de salas de cirurgia para pacientes eletivos de um hospital em Lisboa, onde é proposta uma reformulação do modelo de PLI proposto por Marques et al. (2012). Esta reformulação é baseada no problema da mochila, com o objetivo de encontrar soluções mais eficientes em termos computacionais. De acordo com os testes realizados, uma modificação no modelo que quebre sua simetria além de fornecer uma solução mais eficiente computacionalmente, melhora a solução original pois diminui o gap inicial de 782,59 porcento para 2,25 porcento. Também foi proposto um modelo de simulação no que foram criados vários cenários para avaliar a incerteza envolvida, nos quais a duração média das cirurgias foi submetida a valores majorados. Esta simulação pode servir como ferramenta de apoio na tomada de decisões, pois de acordo com o grau de conservadorismo de quem toma as decisões, podem ser estabelecidas políticas de programação das Salas de Cirurgia. / [en] For most countries annual health expenditures are increasing. According to the World Health Organization (WHO), in 2011, Brazil expends about 10 percent of its gross domestic product on health. Hence, improving health care efficiency is becoming increasingly important. Within a hospital, the Operating Rooms represent a major cost and incomes center. Operating Rooms are a difficult aspect to manage because many stakeholders involved in the process, namely, patients, surgeons, staff, hospital manager, and the scarcity of resources like beds, operating rooms, especial equipment, etc. This dissertation deals with a real problem of operating rooms programming for elective patients in a Lisbon hospital. For this problem, we propose a reformulation of the integer programming model proposed by Marques et al. (2012). This reformulation is based on the knapsack problem, in order to find a more efficient solution in terms of time. According to tests carried out, a reformulation in the model that breaks symmetry, computationally provides a more efficient solution and enhance the original solution because it reduces the initial gap from 782.59 percent to 2.25 percent. In addition, a simulation model was proposed to create various scenarios to assess the involved uncertainty, mainly due to surgery duration variation. This simulation can serve as a support tool in decision-making, according to the degree of conservatism of the decision maker, Operating Rooms scheduling policies can be established.

[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] 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