O objetivo principal desta tese foi a implantação de uma nova estratégia para a integração da otimização em tempo real (RTO), com o controle preditivo multivariável em uma unidade de processo industrial. A solução proposta pode ser considerada como uma estratégia de uma camada, na qual os problemas de controle e otimização econômica são resolvidos simultaneamente, na mesma camada da estrutura de controle. Supondo que o objetivo econômico a ser maximizado (minimizado) seja uma função côncava (convexa) das entradas e saídas de processo, o controlador MPC com otimização econômica (OMPC) foi obtido através da inclusão do gradiente reduzido do objetivo econômico, na função objetivo do controlador preditivo. Esta abordagem foi testada inicialmente através da simulação do conjunto reator regenerador de uma Unidade de Craqueamento Catalítico Fluido (UFCC). O controlador otimizador foi implementado com sucesso em uma coluna de destilação de tolueno, na Unidade de Recuperação de Aromáticos da refinaria de Cubatão da Petrobras. Este controlador está em funcionamento contínuo por cerca de um ano, sem qualquer problema relatado. Para a determinação das condições ótimas, um modelo rigoroso de coluna de destilação multicomponentes no estado estacionário é incluído no controlador preditivo para permitir o cálculo online do objetivo econômico. A trajetória prevista para o sistema de destilação até o ponto ótimo é calculada utilizando-se um modelo linear dinâmico, o qual foi obtido através de testes em degrau na planta real. O ponto ótimo obtido através da estratégia proposta leva em consideração as restrições nas entradas manipuladas e a faixa de controle para as saídas. O problema de otimização resultante para cálculo das ações de controle é uma QP, que pode ser facilmente resolvida com os solvers disponíveis. O MPC com otimização econômica foi implementado como um módulo do pacote SICON (Sistema de Controle da Petrobras). / This thesis was mainly aimed at the implementation of a new strategy for the integration of real time optimization (RTO) with multivariable predictive control in an industrial process system. The proposed strategy can be considered as a one-layer strategy where the control and economic optimization problems are solved simultaneously in the same layer of the control structure. Assuming that the economic objective to be maximized (minimized) is a concave (convex) function of the process inputs and outputs, the optimizing model predictive control (OMPC) was obtained through the inclusion of the reduced gradient of the economic objective in the control objective of the predictive controller. The approach was initially tested through the simulation of the reactorregenerator of a Fluid Catalytic Cracking Unit (FCCU). The optimizing controller has been successfully implemented in a toluene distillation column at the Aromatic Recovery Unit of the Cubatão refinery of Petrobras. This controller has been in continuous operation for about one year without any reported problem. For determining the optimum operating conditions, a steady-state rigorous multicomponent distillation model is included in the predictive controller to allow the on-line computation of the economic objective. The predicted trajectory of the distillation system towards the optimum point is computed with a linear dynamic model that was obtained through step tests in the real plant. The optimum point that is achieved with the proposed strategy takes into account the constraints in the manipulated inputs and the zone control of the outputs. The resulting optimization problem that produces the control actions is a QP that can be easily solved with available solvers. The optimizing MPC was implemented as a module of the SICON (Petrobras Control System) package.

Essa pesquisa propõe abordar o problema da alocação de medidores em sistemas de distribuição, de forma a reduzir os custos, garantindo o monitoramento dos distúrbios que afetam a qualidade da energia elétrica, mas também de obter alocações de medidores que facilitem a localização do curto-circuito. O problema de otimização é formulado por meio da programação linear inteira e resolvido por meio de algoritmos adequados para implementar cada modelagem matemática. São considerados sistemas testes com diferentes características, com destaque para a presença de linhas monofásicas e/ou bifásicas, linhas heterogêneas e geradores distribuídos acoplados na rede de distribuição principal. O problema de otimização clássico (reduzir custos garantindo o monitoramento) é retomado e é proposta uma modelagem mais geral, aplicável também a sistemas de distribuição com a presença de ramais monofásicos e/ou bifásicos. A parte da modelagem voltada para o problema da localização de faltas visa à redução das situações de múltipla estimação do local da falta, caracterizadas pela existência de múltiplos pontos no sistema com a mesma distância elétrica até a subestação. Esses dois modelos foram resolvidos separadamente, como dois problemas de otimização mono-objetivo, e em conjunto, sendo portanto, um problema multi-objetivo. As instâncias testadas incluem conjuntos de faltas de todos os tipos, simuladas ao longo das linhas do sistema, considerando a variação da impedância de falta. Os resultados apresentaram soluções de monitoramento para os dois sistemas testes considerados contendo entre 2 e 7 medidores. As soluções alcançadas são atrativas para a concessionária, pois requerem baixo custo de investimento e manutenção dos equipamentos e da infraestrutura de comunicação. A metodologia proposta apresentou alocações dispostas estrategicamente que garantem o monitoramento da qualidade da energia elétrica e minimizam o problema da múltipla estimação da falta, possibilitando o seu uso como suporte a um sistema localizador de faltas. / This research proposes to address the monitors allocation problem in distribution systems, aiming to reduce costs, ensuring the monitoring of disturbances affecting the power quality, but also to obtain monitoring systems that facilitate the process of fault location. The optimization problem is formulated through integer linear programming and solved by suitable algorithms for each mathematical modeling. Test systems with different characteristics, emphasis on the presence of single-phase and/or biphasic lines, heterogeneous lines and distributed generators were considered. The classic optimization problem (reduce costs by ensuring disturbance monitoring) is covered and a more general modeling is proposed, also applicable to distribution systems with the presence of single-phase and/or biphasic branches. The process of fault location is supported through the reduction of the multiple estimation of fault location, characterized by the existence of multiple points in the system with the same electrical distance to the substation. These two models were solved separately, as two mono-objective optimization problems, and together, in a multi-objective perspective. The tested instances include sets of faults of all types, simulated along the lines of the system, considering the fault impedance variation. The results presented monitoring solutions for the two test systems considered containing between 2 and 7 meters. The solutions achieved are attractive to the utility, as they require low investment and maintenance costs for equipment and communication infrastructure. The proposed methodology presented allocations strategically placed that guarantee the power quality monitoring and minimize the multiple estimation problem, allowing its use as support to a faults locator system.

O objetivo principal desta tese foi a implantação de uma nova estratégia para a integração da otimização em tempo real (RTO), com o controle preditivo multivariável em uma unidade de processo industrial. A solução proposta pode ser considerada como uma estratégia de uma camada, na qual os problemas de controle e otimização econômica são resolvidos simultaneamente, na mesma camada da estrutura de controle. Supondo que o objetivo econômico a ser maximizado (minimizado) seja uma função côncava (convexa) das entradas e saídas de processo, o controlador MPC com otimização econômica (OMPC) foi obtido através da inclusão do gradiente reduzido do objetivo econômico, na função objetivo do controlador preditivo. Esta abordagem foi testada inicialmente através da simulação do conjunto reator regenerador de uma Unidade de Craqueamento Catalítico Fluido (UFCC). O controlador otimizador foi implementado com sucesso em uma coluna de destilação de tolueno, na Unidade de Recuperação de Aromáticos da refinaria de Cubatão da Petrobras. Este controlador está em funcionamento contínuo por cerca de um ano, sem qualquer problema relatado. Para a determinação das condições ótimas, um modelo rigoroso de coluna de destilação multicomponentes no estado estacionário é incluído no controlador preditivo para permitir o cálculo online do objetivo econômico. A trajetória prevista para o sistema de destilação até o ponto ótimo é calculada utilizando-se um modelo linear dinâmico, o qual foi obtido através de testes em degrau na planta real. O ponto ótimo obtido através da estratégia proposta leva em consideração as restrições nas entradas manipuladas e a faixa de controle para as saídas. O problema de otimização resultante para cálculo das ações de controle é uma QP, que pode ser facilmente resolvida com os solvers disponíveis. O MPC com otimização econômica foi implementado como um módulo do pacote SICON (Sistema de Controle da Petrobras). / This thesis was mainly aimed at the implementation of a new strategy for the integration of real time optimization (RTO) with multivariable predictive control in an industrial process system. The proposed strategy can be considered as a one-layer strategy where the control and economic optimization problems are solved simultaneously in the same layer of the control structure. Assuming that the economic objective to be maximized (minimized) is a concave (convex) function of the process inputs and outputs, the optimizing model predictive control (OMPC) was obtained through the inclusion of the reduced gradient of the economic objective in the control objective of the predictive controller. The approach was initially tested through the simulation of the reactorregenerator of a Fluid Catalytic Cracking Unit (FCCU). The optimizing controller has been successfully implemented in a toluene distillation column at the Aromatic Recovery Unit of the Cubatão refinery of Petrobras. This controller has been in continuous operation for about one year without any reported problem. For determining the optimum operating conditions, a steady-state rigorous multicomponent distillation model is included in the predictive controller to allow the on-line computation of the economic objective. The predicted trajectory of the distillation system towards the optimum point is computed with a linear dynamic model that was obtained through step tests in the real plant. The optimum point that is achieved with the proposed strategy takes into account the constraints in the manipulated inputs and the zone control of the outputs. The resulting optimization problem that produces the control actions is a QP that can be easily solved with available solvers. The optimizing MPC was implemented as a module of the SICON (Petrobras Control System) package.

Neste trabalho apresentamos dois modelos de otimização e um método heurístico de solução para tratar um problema de comprovação fiscal em exportações de commodities no Brasil. Dos modelos de otimização, um foi desenvolvido baseado no Problema de Dimensionamento de Lotes e outro no Problema da Mochila. O governo brasileiro estimula as exportações no país através de alguns benefícios fiscais, alguns desses, sendo possíveis através da comprovação fiscal das exportações de mercadorias acompanhadas de notas fiscais de tipo de operação de fim específico para a exportação. Os benefícios deixam de ser concedidos a partir da perda do prazo da comprovação fiscal da nota fiscal, que é realizado utilizando a Declaração Única de Exportação (DU-E). Cada nota fiscal possui uma data de emissão, dias de isenção fiscal, o percentual da alíquota de ICMS cobrado dependendo do estado emissor, os itens e suas quantidades. As decisões visam estabelecer as combinações de quais notas fiscais devem ser comprovadas em cada embarque de produtos para o mercado exterior, obedecendo às suas datas de isenção de modo a minimizar os impostos pagos devido aos vencimentos dos prazos de despachos das notas. Os resultados obtidos por meio do modelo matemático mostram que a política otimizada de embarque dos produtos das notas fiscais apresenta uma redução dos custos em aproximadamente 39% em determinadas situações. / In this paper we present two optimization models and a heuristic method to deal with a problem of export tax on Brazilian commodities. Regarding the optimization models, one was developed based on the lot-sizing problem and an other on the knapsack problem. The Brazilian government encourages local exportation through tax benefits, some of them being possible by the taxation of exported goods being accompanied by invoices of an operation type that is specific for the purpose of the export. These benefits cease to be granted as a result of exceeding the tax invoice verification period, which is granted using the Single Export Declaration (DU-E). Each invoice has a date issue, days of tax exemption, the percentage of the ICMS tax rate charged depending on the issuing state, the items and their quantities. The decisions aim to establish the combinations of which invoices must be presented for each shipment of products to the foreign market, obeying their exemption dates in order to minimize the taxes paid due the maturity of the delivery times on the documents. The results obtained using the mathematical model show that the optimized shipping policy for invoiced products presents a 39% reduction in costs in certain situations.

Orientador: Prof. Dr. Jerônimo Cordoni Pellegrini / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2016. / O objetivo deste trabalho é apresentar alguns métodos para a resolução de problemas de programação linear. Iremos definir este tipo de problema e mostrar alguns casos onde pode-se obter uma solução ótima com a ajuda de gráficos. Outra preocupação é mostrar que existem várias aplicações para otimização linear, por esse motivo alguns problemas clássicos serão discutidos e modelados. Para uma melhor compreensão sobre restrições lineares e soluções viáveis, iremos definir conjunto convexo, poliedro e politopo. Algumas situações especiais que podem surgir em otimização serão discutidas, especificamente os casos de problemas inviáveis, ilimitados e degenerados. O Método Simplex, que percorre os vértices do poliedro determinado pelas restrições lineares, será apresentado juntamente com o método das duas fases e alguns exemplos. Para resolver problemas de programação linear inteira, que são aqueles onde restringimos as variáveis de decisão a valores inteiros, o método Branch-and-Bound e Planos de Corte serão apresentados. O caso de matriz totalmente unimodular também será discutido. Finalizando, uma sequência de problemas de programação linear será sugerida, onde professor e aluno do ensino médio terão a oportunidade de discutir, modelar e encontrar a solução ótima destes problemas contando com auxílio de recursos computacionais se necessário. / The aim of this work is to present some methods for solving linear programming problems. We will define this kind of problem and show some cases where you can obtain an optimal solution with the help of graphics. Another concern is to show that there are several applications for linear optimization, therefore some classic problems will be discussed and modeled. For a better understanding about linear constraints and feasible solutions, we will define convex set, polyhedron and polytope. Some special situations that may arise in optimization will be discussed, specifically the cases of unfeasible, unlimited and degenerate problems. The Simplex method, which runs through the vertices of the polyhedron determined by linear constraints, will be presented along with the method of the two phases and some examples. To solve integer programming problems, which are those that restrict the decision variables to integer values, the Branch-and-Bound and Cutting-Plane method will be presented. The case of totally unimodular matrix will also be discussed. Finally, a sequence of linear programming problems is suggested, where teacher and high school student will have the opportunity to discuss, model and find the optimal solution of these problems with help of computer resources if necessary.

Made available in DSpace on 2016-06-02T19:51:21Z (GMT). No. of bitstreams: 1 DissRARJ.pdf: 1930702 bytes, checksum: a1b0d68f6f193815099874af8118a5e1 (MD5) Previous issue date: 2006-05-23 / The production of corn seeds involves a complex agro-industrial production chain whose main agents must offer products of high quality and low price to stay competitive. Efficient tools to coordinate this chain are thus essential to fulfill these conditions. This work proposes a linear programming model for the strategic planning of production, storing and transportation, designed to minimize production, transportation and tax costs. The model is a function of crop planning, capacity and client demand restrictions. Although relevant to the product s final cost, taxes are not traditionally considered by the planning methods currently used by the seed industry. The raw material is generally sent to the industrial unit closest to the farm; proximity to the end consumer is of secondary importance. The main productive processes and features of the seed industry described here are based on literature and visits to plants that produce corn seeds. The mathematical model detailed in this work is implemented using the GAMS programming language and the resulting system of equations solved with CPLEX. The model was validated by using different scenarios with real-world data collected during the visits to the plants; the results were consistent with those expected. Next, the results given by the model of a case study with data for an entire season were compared against those obtained by one of the companies employing the traditional method of shortest distance between farm and industrial unit. The proposed model showed a substantial decrease in total cost when compared to the traditional method. This study also confirmed the importance of integrating taxes with production and transportation planning at the logistics level. / A produção de sementes de milho envolve uma cadeia de produção agroindustrial complexa cujos agentes devem primar por oferecer produtos de alta qualidade a um baixo custo para se manterem competitivos no mercado. Instrumentos eficientes para a coordenação dessa cadeia são fundamentais para atender a esta exigência, orientando seus agentes para o cumprimento dos objetivos comuns. Neste trabalho um modelo de programação linear é proposto para realizar o planejamento tático da produção, estocagem e de transportes de forma a minimizar custos de produção, transportes e fiscais, atendendo ao mesmo tempo às restrições de programação da colheita, de capacidade e de demanda. Tradicionalmente, não são considerados nos métodos de planejamento do setor custos fiscais, como o de ICMS, que se mostram relevantes no custo unitário do produto final. A matéria-prima, em geral, é enviada para a unidade mais próxima ao campo de produção agrícola, deixandose para um segundo plano a proximidade da demanda. As principais características do processo produtivo e do setor são descritas de acordo com a literatura e visitas a empresas produtoras de sementes. Utilizou-se a linguagem GAMS e o solver CPLEX para resolver o modelo matemático. O modelo foi implementado e testado com dados realistas das empresas visitadas em diferentes cenários, verificando-se coerência nas respostas obtidas. Realizou-se um estudo de caso em uma das empresas estudadas utilizando-se os dados completos de uma safra e os resultados obtidos com o modelo proposto foram comparados com o método empregado na empresa, que considerava apenas a menor distância entre a região agrícola e a unidade industrial. Os resultados dessa comparação foram bastante satisfatórios, proporcionando uma redução significativa dos custos considerados. Além disso, foi confirmada, também para este caso, a importância de incorporar os custos fiscais na disciplina de logística integrando planejamento tributário com o de produção e dos transportes.

Made available in DSpace on 2016-08-17T14:52:47Z (GMT). No. of bitstreams: 1 Anselmo Rodrigues.pdf: 589170 bytes, checksum: 7eda1a9d5bbe5a0ef8355bc4c4d26ca8 (MD5) Previous issue date: 2003-08-15 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The restructuring of the electricity industry has caused an increase in the number of commercial transactions carried out in energy markets. These transactions are defined by market forces without considering the operational constraints of the transmission system. As a consequence, there are transactions that cause congestion in the transmission network, that means, violations of operational limits in one or more circuits of the transmission system. In this way, the congestion in the transmission system must be eliminated by using corrective actions, such as redispatch of generation/transactions and operation of control flow devices, to avoid cascading outages with uncontrolled loss of load. Currently, the majority of methodologies used in congestion management are based on deterministic models. It has been justified because of the complexity associated with the application of probabilistic models in generation/transmission systems. Nevertheless, some models have been developed to carry out probabilistic analysis of the congestion management. Usually, they are based on the Monte Carlo Method with nonsequential simulation and they only include bilateral transactions. However, multilateral transactions are also essential for the existence of the energy markets. The multilateral transactions reduce the financial risks associated with commercial transactions and allow the customers to have access to the energy providers. Additionally by ignoring multilateral transactions, the existing probabilistic models for the congestion management include only not-free-cost corrective actions, such as generation redispatch and transaction curtailments. On the other hand, free-cost corrective actions, such as phase shifting transformers and FACTS devices, can provide low cost solutions to eliminate congestion in interconnections of the transmission system. This condition is caused by the delay in carrying out reinforcements in the transmission systems due to financial and environmental constraints. Finally, it must be noted that only probabilistic indices based in expected values are evaluated by the probabilistic models of congestion management. However, system operators have difficulty in interpreting probabilistic indices based only in expected values. Therefore, it is necessary to develop new indices to carry out probabilistic analysis of congestion management. These new indices must consider traditionally accepted operational criteria and they must be easily interpreted by the system operators. This research has as its objective the development of models and techniques to carry out the probabilistic analysis of congestion management. The proposed models and techniques consider the following aspects associated with congestion management: the modeling of multilateral transactions, phase shifting transformers and the definition of Well-Being Indices to assess the reliability of the commercial transactions. These indices, allow the establishment of a link between the operational criteria traditionally used and the stochastic model of the electrical network. The models and indices, proposed in this research, have been based on the Monte Carlo Method with non-sequential simulation and in the linearized optimal power flow. The optimal power flow problems associated with the congestion management have been solved using the Primal-Dual Interior-Point Method. The practical application and the validation of the models and indices proposed in this research have been carried out in two systems: the IEEE System, proposed in 1996, for Reliability Studies. The main conclusions obtained with the application of the proposed models and techniques in the IEEE system are: multilateral congestion management can improve the reliability of commercial transactions, load profiles have significant effects on the Well-Being indices of the transactions, the base case condition has great impact in the Well-Being indices associated with a set of transactions and the operation of phase-shifting transformers and can decrease significantly the curtailments in the commercial transactions. / A reestruturação da indústria de eletricidade causou um aumento no número de transações comerciais efetuadas em mercados de energia. Estas transações são definidas por forças de mercado sem considerar restrições operacionais do sistema de transmissão. Consequentemente existem transações comerciais que causam congestão no sistema de transmissão, ou seja, resultam em violações de limites operacionais em um ou mais circuitos do sistema de transmissão. Desta forma, a congestão no sistema de transmissão deve ser eliminada usando-se ações corretivas, tais como redespacho de geração/transações e operação de dispositivos de controle de fluxo, para evitar contingências em cascata com perda de carga descontrolada. Atualmente, a maioria das metodologias usadas no gerenciamento da congestão se baseia em métodos determinísticos. Isto tem sido justificado devido a complexidade associada com a aplicação de modelos probabilísiticos em sistemas de geração/transmissão. Apesar disto, alguns modelos foram desenvolvidos para realizar uma análise probabilística do gerenciamento da congestão. Estes modelos geralmente se baseiam no método de Monte Carlo com Simulação Não-Sequencial e somente incluem transações bilaterais. Entretanto, transações multilaterais são também de grande importância para a existência dos mercados de energia. Os contratos multilaterais reduzem os riscos financeiros associados com transações comerciais e permitem que os consumidores tenham acesso aos fornecedores de energia. Além de não considerarem transações multilaterais, os modelos probabilísticos existentes para o gerenciamento da congestão somente incluem ações corretivas não-livres de custo, tais como redespacho da geração e cortes nas transações. Por outro lado, ações corretivas livres de custo, tais como transformadores defasadores e dispositivos FACTS, podem fornecer soluções de baixo custo para eliminar a congestão nas interligações do sistema de transmissão. Esta condição é causada pelo atraso na realização de reforços no sistema de transmissão devido a restrições financeiras e ambientais. Finalmente, observa-se que apenas índices probabilísticos que se baseiam em valores esperados são calculados pelos modelos probabilísticos de gerenciamento da congestão. Entretanto, operadores do sistema tem dificuldade em interpretar índices probabilísticos que se baseiam em valores esperados. Devido a isto, é necessário desenvolver novos índices para realizar uma análise probabilística do gerenciamento da congestão. Estes novos índices devem considerar critérios de avaliação tradicionalmente aceitos e serem facilmente interpretados pelos operadores do sistema. Este trabalho de pesquisa tem como objetivo desenvolver modelos e técnicas para realizar a análise probabilística do gerenciamento da congestão. Os modelos e técnicas propostos neste trabalho consideraram os seguintes aspectos associados com o gerenciamento da congestão: modelagem de transações multilaterais e transformadores defasadores no gerenciamento da congestão e a definição de índices de robustez para analisar a confiabilidade das transações comerciais. Estes índices permitem estabelecer um elo entre critérios de operação tradicionalmente usados e a modelagem probabilística da rede elétrica. Os modelos e índices propostos neste trabalho de pesquisa se baseiam no Método de Monte Carlo com simulação não-sequencial e no fluxo de potência ótimo linearizado. Os problemas de fluxo de potência ótimo associados com o gerenciamento da congestão foram resolvidos usando-se o Método de Pontos-Interiores Primal-Dual. A aplicação prática e validação dos modelos e índices propostos nesta pesquisa foi realizada através de diversos testes no sistema IEEE, proposto em 1996, para estudos de confiabilidade. As principais conclusões obtidas com a aplicação dos modelos e técnicas propostos no sistema IEEE são: o gerenciamento da congestão multilateral pode aumentar a confiabilidade das transações comerciais, perfis de carga tem efeitos significativos nos índices de robustez das transações comerciais, a condição do caso base tem grande impacto nos índices de robustez associados com um conjunto de transações e a operação de transfotmadores defasadores pode diminuir significativamente as interrupções nas transações comerciais.

Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature / Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eciente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que é mais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem ser exploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura