Este trabalho trata do problema de configuração de redes logísticas, em que são consideradas como principais decisões a quantidade e a localização de instalações logísticas e a definição da alocação de clientes às instalações. Mais especificamente, o trabalho considera um processo típico de configuração de redes logísticas que se vale de modelos discretos de otimização e a tomada de decisão com base nos resultados. O objetivo da tese é propor modelos e métodos capazes de dar suporte às etapas fundamentais deste tipo de estudo. Inicialmente são propostos métodos para a seleção de locais candidatos considerados nos modelos de localização. Os métodos se valem de informações sobre a distribuição dos pontos de demanda ao longo da rede para a obtenção dos candidatos a instalação e são avaliados por meio de sua aplicação a dois conjuntos de instâncias da literatura científica e comparação de tempos de resolução e de valores da função objetivo. Os resultados mostram que o tempo de resolução foi reduzido, na média, em 57% e os gaps das funções objetivo resultantes vale menos que 0,16% em comparação com os modelos que consideram todos os pontos de demanda como candidatos. Adicionalmente, também foram propostos métodos capazes de obter soluções alternativas de qualidade para problemas de localização que podem ser comparadas a fim de fornecer mais subsídio para a tomada de decisão. Os métodos são capazes de obter as K melhores soluções de problemas de localização e são avaliados por meio de sua aplicação a 215 instâncias da literatura científica. Além disso, a abordagem proposta permitiu a análise de resultados nunca antes obtidos para um problema muito estudado: as K melhores soluções do problema de localização de instalações capacitadas com custo fixo. Duas características principais foram identificadas: a quantidade de instalações é estável - em 99% das instâncias testadas o desvio padrão da quantidade de instalações nas 20 melhores soluções de cada instância é menor que um - e grande parte das instalações que fazem parte da solução ótima de cada instância também faz parte da maior parte das 20 melhores soluções. A partir de tais conclusões, o trabalho investiga algumas propriedades gerais de problemas de localização e apresenta uma análise topológica das 215 instâncias utilizadas, com base em indicadores propostos. Por fim, três tipos de modelos de redes neurais capazes de identificar relações entre os valores dos indicadores das instâncias e os valores das variáveis resposta associadas às melhores soluções são aplicados e avaliados. A abordagem consiste em comparar o tempo de resolução e o valor da função objetivo de modelos cujos espaços de soluções viáveis são reduzidos com base nos resultados obtidos pelas redes neurais. Os resultados mostram que é possível utilizar tal abordagem para melhorar o processo de configuração de redes logísticas, seja na etapa de construção dos modelos seja proporcionando mais subsídios para a tomada de decisão. / This thesis deals with the supply chain network design problem (SCND) that aims to find the optimal location of facilities and the allocation of customers to each facility. The work considers a typical process of SCND in which discrete optimization models are run and its results are used in the decision making. The goal of the thesis is to propose models and methods to support the stages of this type of planning process. Initially, methods for the selection of candidates considered in the localization models are proposed. The methods consider the distribution of the demand points throughout the network to obtain the candidates and are evaluated by their application to two sets of scientific literature instances and comparison of computational times and objective function values. The results show that the average computational time has been reduced by 57% and the resulting objective function gaps are less than 0,16% compared to the solutions obtained by the models that consider all the demand points as candidates. In addition, the thesis present methods capable of obtaining high-quality alternative solutions to location problems that can be compared in order to provide better support for decision making. The methods obtain the K-best solutions of location problems and are evaluated by their application to 215 instances of the scientific literature. In addition, the proposed approach allowed the analysis of results never before obtained for a well-studied problem: the best solutions of the capacitated fixed cost facility location problem. Two main insights were identified: the number of facilities is stable - in 99% of the tested instances the standard deviation of the number of facilities in the 20 best solutions of each instance is less than one - and most of the selected facilities in the optimal solution of each instance is selected in most of the 20 best solutions as well. Based on these conclusions, the work investigates some general properties of localization problems and presents a topological analysis of the 215 instances, based on proposed indicators. Finally, three types of neural network models capable of identifying relations between the instances indicators and the values of the variables of the best solutions are applied and evaluated. The approach consists in comparing the computational time and the objective function value of models whose feasible solution spaces are reduced based on the results obtained by the neural networks. The results show that it is possible to use such approach to improve the SCND process, either at the construction stage of the models or by providing more information for the decision making.

Les Réseaux de Chaleur (RdC) connaissent un nouvel essor en France qui s’explique par leur capacité à valoriser, à un prix raisonnable, des énergies bas carbone dans les domaines du chauffage et de l’eau chaude sanitaire aujourd’hui fortement émetteurs de CO2. L’amélioration du contrôle de ces systèmes complexes est un enjeu clé pour accroître leur compétitivité et favoriser leur développement. Cette thèse s’intéresse à la gestion par commande optimale des RdC. Pour cette application, nous avons développé et évalué un algorithme qui, à partir d’une prévision de la demande, optimise l’utilisation des différents moyens de production ainsi que la température de départ et la pression différentielle. Par rapport aux systèmes existants, les originalités de notre solution sont de tirer pleinement partie des capacités de stockage thermique dans le réseau et de déterminer le meilleur compromis entre coûts liés au pompage et pertes thermiques. Cette thèse débute par un travail de modélisation dynamique réalisé à l’échelle composant. En nous appuyant sur une démarche de validation expérimentale, nous avons systématiquement recherché le meilleur compromis entre précision et efficacité numérique (Chapitre 1). Le cas d’étude, décrit dans le Chapitre 2, est un RdC virtuel à l’échelle d’un quartier, représentatif du cas Grenoble. Pour le développement du système de gestion avancée, nous présentons ensuite une version linéarisée du modèle de réseau de distribution que nous intégrons à un optimiseur en suivant le formalisme de la programmation linéaire mixte. L’algorithme de gestion proposé est ensuite décrit (Chapitre 3). Il associe un modèle dynamique non-linéaire et l’optimiseur précité. L’objet du quatrième chapitre est l’évaluation des performances de notre algorithme par la simulation et la comparaison à des méthodes de contrôle existantes. Enfin, un dernier chapitre étudie la robustesse de l’algorithme en condition de commande réelle, c’est-à-dire en tenant compte de différentes sources d’incertitude. / District Heating (DH) are currently fast-growing in France. This situation is explained by their ability to exploit and disseminate massively, at a reasonable price, energy sources with low CO2 contents in the sectors of space heating and domestic hot water production, nowadays strongly emitters of greenhouse gases. Improving the control of these complex energy systems is a key issue for increasing their competitiveness and promote their development.This thesis focuses on the optimal control of DH systems. For this application, we have developed and tested an algorithm that optimizes, given a load prediction, the use of the production means, the supply temperature and the differential pressure. Compared to existing methods, the original features of the developed solution are to fully exploit the thermal storage capacity of the network and to determine the best compromise between costs for pumping and heat losses.This thesis begins with a work on dynamic modeling carried out at the component scale. Based on an experimental validation approach, we systematically sought the best compromise between accuracy and computational efficiency (Chapter 1). The case study, described in Chapter 2, is a virtual DH at the district scale, representing the Grenoble case. For the development of the advanced control system, we then present a linearized version of the distribution network model that we integrate into an optimizer relying on Mixed Linear Programming. The proposed control algorithm is described in Chapter 3. It combines a nonlinear dynamic model and the aforementioned optimizer. The topic of the fourth chapter is the evaluation of the performance of our algorithm by simulation and comparison with existing methods of control. A final chapter examines the robustness of the algorithm in real control conditions considering various sources of uncertainty.

[pt] Problemas de geração de grades horárias visam agendar eventos a fim de satisfazer demandas, ao mesmo tempo que satisfazem restrições adicionais. Uma solução é boa se todas as grades horárias resultantes são aceitáveis para todas as pessoas e recursos envolvidos. Para a geração de grades horárias escolares, um número conhecido de aulas, envolvendo estudantes, professores e salas de aula, deve ser agendado ao longo da semana, enquanto limitações operacionais, institucionais, pedagógicas e pessoais devem ser satisfeitas. A alta dificuldade do problema tem levado muitos pesquisadores a trabalhar em abordagens de resolução para o mesmo desde o início dos anos 60. Encontrar uma solução aplicável em um cenário do mundo real implica em satisfazer vários requisitos de qualidade e em não ignorar questões políticas, o que torna o problema clássico muito mais intrincado. Este trabalho descreve uma abordagem baseada em programação inteira mista (MIP) desenvolvida para resolver um problema real de geração de grades horárias escolares e discute ideias e desafios encarados durante a fase de implantação da solução em algumas escolas brasileiras. Em contraste com outros trabalhos na área, o compartilhamento de professores entre diferentes unidades de uma escola é considerado. Experimentos computacionais foram realizados para cenários cujo número de unidades varia de 2 a 15, o número de professores de 35 a 471, e o número de turmas de 16 a 295. Diferentes estratégias foram combinadas, visando a convergência da procura por boas soluções. Por fim, os resultados são avaliados e as melhores abordagens são destacadas. / [en] Timetabling problems look to schedule meetings in order to satisfy a set of demands, while respecting additional constraints. In a good solution the resulting timetables are acceptable to all people and resources involved. In school timetabling, a given number of lectures, involving students, teachers and classrooms, need to be scheduled over the week, while having to satisfy operational, institutional, pedagogical and personal restrictions. The difficulty of the problem has driven many researchers to work on solving approaches for it since the early 1960 s. Finding an actual solution to a real world scenario implies satisfying many quality requirements and not ignoring the political issues, which turns the classical problem much more intricate. This work describes an approach based on mixed integer programming (MIP) developed for solving a real-world school timetabling problem and discusses ideas and issues faced during solution deployment phase for some Brazilian schools. In contrast to other works on school timetabling, teaching staff sharing between distinct school units are considered. Computational experiments were performed for scenarios whose number of school units varies from 2 to 15, number of teachers varies from 35 to 471 and number of classes varies from 16 to 295. Different strategies were combined aiming at converging to good solutions. Finally, results are evaluated and the best approaches are highlighted.

Nous étudions les bornes sur les distances des racines des polynômes entiers et les applications de ces résultats. La séparation des racines complexes pour les polynômes réductibles normalisés de quatrième degré à coefficients entiers est examinée plus à fond. Différents lemmes sur les racines des polynômes en nombres p-adiques sont prouvés. Sont fournies les familles explicites de polynômes de degré général, ainsi que les familles dans certaines classes de polynômes quadratiques et cubiques avec une très bon separation des racins dans le cadre p-adique. Le reste de la thèse est dédié aux résultats liés aux versions p-adiques des fonctions de Mahler et de Koksma wn et w*n , ainsi qu'aux classifications correspondantes des nombres transcendants dans Cp. Le résultat principal est une construction des nombres pour lesquelles les deux fonctions wn et w*n sont différentes pour tous les n et puis l'intervalle de valeurs possibles pour wn-w*n est élargi. Les inégalités reliant les valeurs des fonctions de Koksma en nombres algébriquement dépendants sont prouvées. / We study bounds on the distances of roots of integer polynomials and applications of such results. The separation of complex roots for reducible monic integer polynomials of fourth degree is thoroughly explained. Lemmas on roots of polynomials in the p-adic setting are proved. Explicit families of polynomials of general degree as well as families in some classes of quadratic and cubic polynomials with very good separation of roots in the same setting are exhibited. The second part of the thesis is concerned with results on p-adic versions of Mahler's and Koksma's functions wn and w*n and the related classifications of transcendental numbers in Cp. The main result is a construction of numbers such that the two functions wn and w*n differ on them for every n and later on expanding the interval of possible values for wn-w*n. The inequalities linking values of Koksma's functions for algebraically dependent numbers are proved.

Submitted by Edileide Reis (leyde-landy@hotmail.com) on 2013-04-10T17:55:55Z No. of bitstreams: 1 Luiz.pdf: 5892404 bytes, checksum: 4fdceae3cd45c4ee27c8b376fbaacefb (MD5) / Approved for entry into archive by Rodrigo Meirelles(rodrigomei@ufba.br) on 2013-04-22T19:26:19Z (GMT) No. of bitstreams: 1 Luiz.pdf: 5892404 bytes, checksum: 4fdceae3cd45c4ee27c8b376fbaacefb (MD5) / Made available in DSpace on 2013-04-22T19:26:19Z (GMT). No. of bitstreams: 1 Luiz.pdf: 5892404 bytes, checksum: 4fdceae3cd45c4ee27c8b376fbaacefb (MD5) Previous issue date: 2009 / Esse trabalho foi realizado tendo como base a pesquisa sobre as condições de abastecimento na Bacia Hidrográfica do Rio Itapicuru, Bahia, em cinqüenta e quatro municípios, dez deles localizados no trecho médio do rio, e oito dos quais banhados pelo mesmo e que apresentam grande deficiência no abastecimento d’água. Analisando o potencial produtivo de recursos hídricos subterrâneos e de superfície dessa região, foi definida uma macro região deficiente para estudo. Essa região, apesar de possuir mananciais produtivos com boas condições em quantidade e qualidade, tem o abastecimento extremamente deficiente, por não dispor de infraestrutura de adução de água para o fornecimento às populações. A região de estudo abrange o município de Quijingue e a parte norte do município de Tucano. Foram definidos aglomerados de povoados, cada qual constituindo uma Unidade de Distribuição a ser abastecida, a partir dos Pontos de Produção selecionados. A região-piloto definida para estudo, foi organizada com seis Unidades de Distribuição e oito Pontos de Produção, permitindo o exame de quarenta e oito possibilidades de adução de água, e a seleção das melhores opções para atender satisfatoriamente o abastecimento à maioria expressiva dos povoados. A decisão sobre um sistema ótimo, com tantas alternativas e variáveis envolvidas, resulta num problema complexo. Visando tratar o problema sistemicamente e, definir as melhores condições para as aduções sob um ponto de vista técnico e econômico, foi empregada a técnica de otimização. Optou-se pelo modelo de Programação Inteira Linear, considerando-se vazões máximas de produção dos pontos principais disponíveis; a demanda hídrica dos povoados; as distâncias entre os Pontos de Produção e as Unidades de Distribuição (UDs); as perdas de energia para condução das vazões; e, os custos dos sistemas de adução de água, por gravidade e por recalque, conforme as condições topográficas.Assumindo-se algumas simplificações no problema, a exemplo do traçado linear das adutoras. As curvas de custos tiveram que ser linearizadas, com isso tendo-se que introduzir variáveis inteiras binárias. O resultado do modelo de otimização apontou apenas seis adutoras, como opções ótimas,com base no objetivo de menor custo e atendendo integralmente as restrições. Concluindo-se ser promissor o emprego dessa metodologia no planejamento dos sistemas hidráulicos, visando apoiar estudos para o desenvolvimento da infraestrutura hídrica.Trata-se de abordagem sistêmica pouco usual no meio técnico, mas que pode vir a ser incorporada e, com isso, possibilitando avançar com relação às análises benefício-custos tradicionais e predominantes. / Salvador

In industrial applications, the thermal energy is obtained in specific equipment, such as boilers or heaters, and distributed to local usage through some transport fluid, mostly water vapor. Most industries uses multiple boilers to supply its steam demand, having tied operational costs. In this dissertation, was developed a mathematical optimization model in a language of algebraic modeling using GAMS® software. The aim is develop a computational systemic tool to support operational decisions of the steam generation. Generally, manufacturers do not operate simultaneously all of its steam generators. The choice of equipment to be used is a function of industrial process demand of steam. Regarding the use of such equipment, is not considered structured aid tools. The decisions were embased in the experience of those who were involved in operational activities. The model allows to identify specific situations to startup and shutdown, as well as the load on each boiler. In addition, the model provides estimates of steam production costs. Adjustments and evaluation of the applicability of the model occurred through a study case in a factory of the polyvinyl chloride production company, called Braskem S/A. The actual data provided by the company were compared to the results generated by the model, being evaluated their effectiveness. The results proved the model successful applicability, providing a direction, considering the generation of steam in the one year horizon. The application efficiency of the tool as a basis for the operation of steam generation was proved for long planning horizons and can be applied to shorter periods, such as weeks or months. / Em aplicações industriais, a energia térmica é obtida em equipamentos específicos, tais como caldeiras ou aquecedores, e distribuída aos locais de utilização através de um fluido de transporte, em sua maioria o vapor de água. A maior parte das indústrias utiliza várias caldeiras para suprir a demanda de vapor, havendo custos operacionais atrelados. Neste trabalho foi desenvolvido um modelo matemático de otimização em uma linguagem de modelagem algébrica, utilizando o software GAMS®. O intuito foi desenvolver uma ferramenta computacional sistêmica para apoiar as decisões operacionais de geração de vapor. De um modo geral, as indústrias não operam todos os geradores de vapor simultaneamente. A escolha do equipamento a ser utilizado, dentre os existentes na planta, é função da demanda de vapor dos processos industriais. No que diz respeito à utilização desses equipamentos, não se considera ferramentas de auxílio estruturadas, ficando as decisões embasadas na experiência dos envolvidos nas atividades operacionais. O modelo permitirá identificar situações específicas para acionamento e desligamento, bem como a carga em cada uma das caldeiras. Além disso, o modelo fornece estimativas dos custos de produção de vapor. Os ajustes e a avaliação da aplicabilidade do modelo ocorreram por meio de um estudo de caso realizado na unidade de produção de Policloreto de Viníla da empresa BRASKEM S/A. Os dados reais fornecidos pela empresa foram comparados aos resultados gerados pelo modelo, sendo avaliada sua eficácia. Os resultados obtidos comprovaram o sucesso na aplicabilidade do modelo, sendo obtido um direcionamento, considerando a geração de vapor no horizonte de um ano. A eficiência de aplicação da ferramenta como embasamento para a operação de geração de vapor foi comprovada para horizontes de planejamento longos, podendo ser aplicado a períodos mais curtos, como meses ou semanas.

Este trabalho apresenta um modelo linearizado para ser utilizado em problemas de planejamento da expansão de sistemas de distribuição de energia elétrica (SDEE) com geração distribuída (GD), em um horizonte de curto prazo. O ponto de operação em regime permanente é calculado através de um modelo linearizado da rede, sendo as cargas e geradores representados por injeções constantes de corrente, o que torna possível calcular as correntes nos ramos e as tensões nas barras através de expressões lineares. As alternativas de expansão consideradas são: (i) alocação de bancos de capacitores; (ii) alocação de reguladores de tensão; e (iii) recondutoramento. Ainda, o modelo considera a possibilidade de seleção do tap dos transformadores de distribuição como alternativa para a redução das violações de tensão. A flexibilidade do modelo permite obter soluções considerando a contribuição das GDs no controle de tensão e potência reativa sem a necessidade de especificar uma tensão para a barra da subestação. O modelo de otimização proposto para a solução destes problemas utiliza uma função objetivo linear, além de restrições lineares e variáveis contínuas e binárias. Dessa forma, o modelo de otimização pode ser representado como um problema de programação linear inteira mista (PLIM) A função objetivo considera a minimização dos custos de investimento (aquisição, instalação e remoção de equipamentos e aquisição de condutores) e dos custos de operação, que correspondem aos custos anuais de manutenção somados aos custos das perdas de energia e das violações dos limites de tensão. A variação da carga é representada através de curvas de duração, sendo que os custos das perdas e das violações são ponderados pela duração de cada nível de carregamento. Utilizando uma abordagem de PLIM, sabe-se que existem condições suficientes que garantem a otimalidade de uma dada solução factível, além de permitir que a solução seja obtida através de métodos de otimização clássica. O modelo proposto foi implementado na linguagem de programação OPL e resolvido utilizando o solver comercial CPLEX. O modelo foi validado através da comparação dos resultados obtidos para cinco sistemas de distribuição com os resultados obtidos utilizando um fluxo de carga convencional. Os casos analisados e os resultados obtidos demonstram a precisão do modelo proposto e seu potencial de aplicação. / This work presents a linearized model to be used in short-term expansion planning problems of power distribution systems (PDS) with distributed generation (DG). The steady state operation point is calculated through a linearized model of the network, being the loads and generators modeled as constant current injections, which makes it possible to calculate the branch currents and bus voltages through linear expressions. The alternatives considered for expansion are: (i) capacitor banks placement; (ii) voltage regulators placement; and (iii) reconductoring. Furthermore, the model considers the possibility of adjusting the taps of the distribution transformers as an alternative to reduce voltage violations. The flexibility of the model enables solutions that includes the contribution of DGs in the control of voltage and reactive power without the need to specify the substation voltage. The optimization model proposed to solve these problems uses a linear objective function, along with linear constraints, binary and continuous variables. Thus, the optimization model can be represented as a mixed integer linear programming problem (MILP) The objective function considers the minimization of the investment costs (acquisition, installation and removal of equipment and acquisition of conductors) and the operation costs, which corresponds to the annual maintenance cost plus the costs related to energy losses and violation of voltage limits. The load variation is represented by discrete load duration curves and the costs of losses and voltage violations are weighted by the duration of each load level. Using a MILP approach, it is known that there are sufficient conditions that guarantee the optimality of a given feasible solution, besides allowing the solution to be obtained by classical optimization methods. The proposed model was written in the programming language OPL and solved by the commercial solver CPLEX. The model was validated through the comparison of the results obtained for five distribution systems with the results obtained through conventional load flow. The analyzed cases and the obtained results show the accuracy of the proposed model and its potential for application.

Uma das principais metas das empresas concessionárias é fornecer energia a seus clientes de forma continua, confiável e com baixo custo. A qualidade do serviço de distribuição de energia é fiscalizada por órgãos reguladores do setor elétrico, sendo quantificada por métricas como o indicador de confiabilidade SAIDI (System Average Interruption Duration Index). A melhoria da confiabilidade dos sistemas de distribuição de energia elétrica é um assunto em destaque atualmente, tendo em vista a necessidade de um suprimento de energia cada vez mais confiável, para evitar as perdas econômicas que ocorrem com as interrupções. Neste contexto, este trabalho apresenta uma contribuição para a solução do problema de restabelecimento de sistemas de distribuição. A abordagem consiste no desenvolvimento de um modelo analítico de otimização, cujo objetivo principal é determinar a localização das chaves de manobras na rede que possibilite o restabelecimento efetivo da carga no período pós-falta. A viabilidade do restabelecimento é considerada através de restrições que garantem níveis adequados das tensões nas cargas, bem como a limitação da sobrecarga das linhas e as capacidades de reserva dos alimentadores adjacentes. A modelagem destas restrições é efetuada através de uma versão linear do fluxo de potência em termos das injeções nodais de correntes. As equações que descrevem o fluxo de potência são formuladas como funções das localizações das chaves de manobras no alimentador. A confiabilidade é caracterizada em termos da duração média das interrupções sustentadas, mensurada pelo indicador SAIDI. Visando à maior precisão na representação do efeito das faltas sobre a confiabilidade do alimentador, a metodologia agrega um modelo existente na literatura para alocação dos dispositivos de proteção de forma simultânea às chaves de manobras. A alocação dos dispositivos de proteção e manobras é sujeita a restrições técnicas e econômicas. Para resolver o modelo de otimização não-linear inteira mista, é usada uma técnica de otimização de uso geral, baseada no algoritmo Branch-and-Bound. Assim, metodologia permite a otimização determinística da confiabilidade do alimentador, garantindo o nível ótimo de confiabilidade e a racionalização dos investimentos por parte das concessionárias. Um estudo de caso é apresentado para avaliar a efetividade da metodologia na otimização da confiabilidade de um alimentador de distribuição real. / One of the main goals of utility companies is to provide energy to its customers continuously, reliably and cost effectively. The quality of power distribution service is supervised by regulators of the electricity sector, being quantified by metrics such as the reliability index SAIDI (System Average Interruption Duration Index). Improving the reliability of electricity distribution systems is a key issue nowadays, in view of the need for an increasingly reliable power supply in order to avoid the economic losses due to interruptions. In this context, this work presents a contribution to solve the distribution systems restoration problem. An analytical model is developed to determine locations of the sectionalizing switches in order to restore the system loads in the post-fault period. Restoration feasibility is considered by constraints that ensure adequate voltage levels on the system loads, emergency capacity of support feeders as well as line overloads. Constraints modeling is performed by a linear power flow based on current injection approach. Power flow equations are formulated as functions of switches locations. Reliability is considered in terms of average interruption durations measured by the SAIDI index. Aiming to a greater precision in representing the reliability impact of faults, the methodology aggregates a model from the literature for simultaneous allocation of protective devices and switches. Protective devices and switches allocation is subject to technical and economical constraints. The proposed model is solved by a general-use optimization technique, based on the branch-and-bound method. The proposed methodology makes possible the deterministic optimization of distribution reliability, as well as to rationalize investments of electric utilities. A case study is presented to evaluate the effectiveness of reliability optimization of a real distribution feeder.

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.

Le travail de thèse présenté dans ce mémoire porte sur des méthodes d'optimisation pour la conception conjointe des nomenclatures d'une famille de produits et de sa chaîne logistique. Dans les milieux industriels comme dans les services, le contexte commercial très concurrentiel oblige les entreprises à diversifier leurs offres pour mieux répondre aux demandes de leurs clients. La gestion de cette diversité est alors une problématique centrale : comment proposer une large variété de produits pour satisfaire les besoins des clients tout en maîtrisant les coûts de production, d'inventaire et de logistique ? Les réponses à ce problème relèvent des disciplines habituellement séparées : la conception des produits, la production et la logistique. Si une majorité des approches existantes traitent ces problématiques de façon séquentielle, l'interdisciplinarité apparaît cependant comme un élément essentiel dans la gestion de la diversité. L'objectif de cette thèse est de chercher comment améliorer les interactions entre la conception de familles de produits et l'optimisation des réseaux logistiques en proposant une étape de conception intermédiaire et en développant des outils mathématiques, avec un intérêt particulier porté aux problématiques de développement durable. / This PhD thesis addresses the problem of joint bills-of-materials and supply chain design for a product family. In industry as well as in services, the highly competitive business environment obliges companies to diversify their offers to meet the demands of their customers. Then, managing diversity is a central issue: how to offer a wide variety of products to meet customer needs while controlling costs of production, inventory and logistics? Answers to theses problems are usually in separate disciplines: product design, production and logistics. If most of existing approaches tackle these problems sequentially, interdisciplinarity, however, appears as a key aspect of diversity management. The objective of this thesis is to investigate how to improve the interaction between product families design and supply chain optimization and to develop mathematical tools, with a focus on sustainable development.