In this thesis some problems in mathematical programming have been studied. Chapter 1 contains a brief review of the problems studied and the motivation for choosing these problems for further investigation. The development of two algorithms for finding all the vertices of a convex polyhedron and their applications are reported in Chapter 2. The linear complementary problem is studied in Chapter 3 and an algorithm to solve this problem is outlined. Chapter 4 contains a description of the plant location problem (uncapacited). This problem has been studied in some depth and an algorithm to solve this problem is presented. By using the Chinese representation of integers a new algorithm has been developed for transforming a nonsingular integer matrix into its Smith Normal Form; this work is discussed in Chapter 5. A hybrid algorithm involving the gradient method and the simplex method has also been developed to solve the linear programming problem. Chapter 6 contains a description of this method. The computer programs written in FORTRAN IV for these algorithms are set out in Appendices Rl to R5. A report on study of the group theory and its application in mathematical programming is presented as supplementary material. The algorithms in Chapter 2 are new. Part one of Chapter 3 is a collection of published material on the solution of the linear complementary problem; however the algorithm in Part two of this Chapter is original. The formulation of the plant location problem (uncapacited) together with some simplifications are claimed to be original. The use of Chinese representation of integers to transform an integer matrix into its Smith Normal Form is a new technique. The algorithm in Chapter 6 illustrates a new approach to solve the linear programming problem by a mixture of gradient and simplex method.

Um dos problemas mais relevantes em organizações de grande porte é a escolha de locais para instalação de plantas industriais, centros de distribuição ou mesmo pontos comerciais. Esse problema logístico é uma decisão estratégica que pode causar um impacto significativo no custo total do produto comercializado. Existem na literatura diversos trabalhos que abordam esse problema. Assim, o objetivo desse trabalho é analisar o problema da localização de instalações proposto por diferentes autores e definir um modelo que seja o mais adequado possível ao mercado de distribuição de combustíveis no Brasil. Para isso, foi realizada uma análise do fluxo de refino e distribuição praticado neste segmento e da formação do respectivo custo de transporte. Foram consideradas restrições como capacidade de estoque, gama de produtos ofertados e níveis da hierarquia de distribuição. A partir dessa análise, foi definido um modelo matemático aplicado à redução dos custos de frete considerando-se a carga tributária. O modelo matemático foi implementado, em linguagem C, e permite simular o problema. Foram aplicadas técnicas de computação paralela visando reduzir o tempo de execução do algoritmo. Os resultados obtidos com o modelo Single Uncapacited Facility Location Problem (SUFLP) simulado nas duas versões do programa, sequencial e paralela, demonstram ganhos de até 5% em economia de custos e redução do tempo de execução em mais de 50%. / One of the most relevant problems at large organizations is the choice of locations for estabilishing facilities, distribution centers or retail stores. This logistics issue is an strategic decision which may cause signicant impact at the eective cost of the product. There are several papers tackling this issue. The objective of this dissertation is to analyze the Facility Location Problem previously developed by other authors and to dene the most applicable model to the fuel distribution industry in Brazil. It started from the analyzis of the upstream and downstream ow in practice at this segment and from the respective transportation cost formation. Some constraints were considered like stock capacity, multicommodity oer and distribution hierarchy levels so it could be possible to dene a mathematical model applied to freight economy considering the incident taxes. The dissertation also has the objective of creating a program using the C language which could simulate the problem. It were applied parallel computing techniques to reduce runtime of the algorithm. The results obtained from the Single Uncapacited Facility Location Problem (SUFLP) executed in both program versions, sequential and parallel, demonstrate up to 5% of eective costs gain and reduction of more than 50% in execution time.

Um dos problemas mais relevantes em organizações de grande porte é a escolha de locais para instalação de plantas industriais, centros de distribuição ou mesmo pontos comerciais. Esse problema logístico é uma decisão estratégica que pode causar um impacto significativo no custo total do produto comercializado. Existem na literatura diversos trabalhos que abordam esse problema. Assim, o objetivo desse trabalho é analisar o problema da localização de instalações proposto por diferentes autores e definir um modelo que seja o mais adequado possível ao mercado de distribuição de combustíveis no Brasil. Para isso, foi realizada uma análise do fluxo de refino e distribuição praticado neste segmento e da formação do respectivo custo de transporte. Foram consideradas restrições como capacidade de estoque, gama de produtos ofertados e níveis da hierarquia de distribuição. A partir dessa análise, foi definido um modelo matemático aplicado à redução dos custos de frete considerando-se a carga tributária. O modelo matemático foi implementado, em linguagem C, e permite simular o problema. Foram aplicadas técnicas de computação paralela visando reduzir o tempo de execução do algoritmo. Os resultados obtidos com o modelo Single Uncapacited Facility Location Problem (SUFLP) simulado nas duas versões do programa, sequencial e paralela, demonstram ganhos de até 5% em economia de custos e redução do tempo de execução em mais de 50%. / One of the most relevant problems at large organizations is the choice of locations for estabilishing facilities, distribution centers or retail stores. This logistics issue is an strategic decision which may cause signicant impact at the eective cost of the product. There are several papers tackling this issue. The objective of this dissertation is to analyze the Facility Location Problem previously developed by other authors and to dene the most applicable model to the fuel distribution industry in Brazil. It started from the analyzis of the upstream and downstream ow in practice at this segment and from the respective transportation cost formation. Some constraints were considered like stock capacity, multicommodity oer and distribution hierarchy levels so it could be possible to dene a mathematical model applied to freight economy considering the incident taxes. The dissertation also has the objective of creating a program using the C language which could simulate the problem. It were applied parallel computing techniques to reduce runtime of the algorithm. The results obtained from the Single Uncapacited Facility Location Problem (SUFLP) executed in both program versions, sequential and parallel, demonstrate up to 5% of eective costs gain and reduction of more than 50% in execution time.