Este trabalho trata do problema da inversão de Automata Celulares em reticulados n x n, com relação de transição Neumann, no corpo de Galois de ordem 2. Sabe-se, da literatura, que sob estas condições o problema é de difícil resolução matemática. O problema foi resolvido em parte, pois conseguiu-se estabelecer a condição necessária para o mesmo, utilizando, como ferramenta de análise, técnicas da Álgebra Linear; e sob este aspecto, o trabalho pode ser considerado como uma extensão ao trabalho de Sutner e ao de Barua e Ramakrishnan. O resultado mais interessante e, s.m.j. inédito, estabelece que o carpete de Sierpinski pode ser gerado a partir de coeficientes dos polinômios de Chebyshev.

Sistemas de dutos correspondem atualmente ao modo mais eficaz para o transporte de grandes quantidades de fluidos líquidos e gasosos por longas distâncias. Dutos são utilizados pela Indústria Petrolífera para o transporte de petróleo e de seus produtos derivados. O presente trabalho aborda o scheduling de distribuição dutoviária de um sistema que opera com um duto que transporta produtos de uma refinaria para depósitos com localizações geográficas distintas através de modelos de programação matemática. O sistema é composto pela Refinaria do Planalto (REPLAN) da Petrobras localizada em Paulínia (SP). A ela é conectado um duto (OSBRA) que se estende por cerca de 1000 quilômetros. O maior detalhamento do modelo matemático para operações dutoviárias desenvolvido por Rejowski Jr. (Dissertação de Mestrado, EPUSP, São Paulo, 2001) se torna primordial nessa complexa operação logística. Um fator de extrema importância é a contaminação dos produtos dentro da linha dutoviária. Desta forma, são desenvolvidas restrições especiais que impõem paradas aos segmentos do duto somente quando os mesmos não possuem interfaces. Estas restrições fazem com que a formulação proposta encontre a solução ótima do problema proposto. O aprimoramento destas formulações se torna fundamental, pois os modelos gerados possuem um número elevado de decisões a serem otimizadas. Relações lógicas envolvendo o estoque inicial nos depósitos e na linha dutoviária e a demanda de cada um dos produtos são propostas. Estas relações melhoram o desempenho computacional para os modelos propostos em cenários de demandas altas. Posteriormente, as restrições especiais de contaminação dos produtos e as relativas ao atendimento das demandas nas bases de distribuição são relaxadas e transformadas em penalidades na função objetivo. Estas penalidades aumentam o esforço de resolução dos modelos e ao mesmo tempo possuem grande influência nos resultados operacionais do sistema. Outro fator de extrema importância para o scheduling de operações dutoviárias é a sua representação em tempo contínuo. Adicionalmente, esta representação faz com que a incorporação de restrições hidráulicas de maneira simplificada seja possibilitada. Desta forma, uma estratégia simplificada e eficaz para se determinar a vazão do duto, envolve incluir a curva de rendimento das estações de bombeamento. Esta formulação, que é modelada como um MINLP (Mixed Integer Non Linear Programming), é comparada com uma formulação MILP (Mixed Integer Linear Programming) em tempo discreto com vazões e rendimentos fixos proposta por Rejowski Jr. e Pinto (Computers and Chemical Engineering, 2004, v.28/8 p.1511-1528). Foi mostrado que a presente formulação forneceu soluções de melhor qualidade. A formulação MILP em tempo discreto é caracterizada como um caso particular da presente formulação proposta. A formulação MINLP sofre forte influência do número de intervalos de tempo que a compõem e este fator deve sempre ser considerado para que a melhor solução possa ser encontrada em tempo computacional factível. Esta formulação ainda é aplicada com sucesso a um caso sob diversas configurações de bombeamento com diferentes custos unitários e curvas de rendimento. Duas formulações que consideram a programação de operações de dutos com a incorporação dos aspectos hidráulicos calculados de maneira rigorosa são apresentadas. A primeira delas resulta em um modelo MINLP e considera variações na duração dos intervalos de tempo e na vazão operacional do sistema. Uma segunda formulação apresentada como um modelo MILP é desenvolvida. Resultados computacionais para ambos os modelos são apresentados, assim como as suas soluções geradas são discutidas. O impacto de variações no relevo do sistema dutoviário é analisado. Foram detectadas alterações na vazão de operação do sistema dutoviário, na escolha dos intervalos de tempo em que o sistema é ativado, no rendimento das estações de bombeamento e no tempo total de operação do sistema. Posteriormente, em um outro exemplo, é mostrado que variações no relevo também podem alterar a seqüência dos produtos alimentados pela refinaria ao duto. Finalmente, as formulações têm os seus resultados comparados aos de modelos com considerações hidráulicas simplificadas, cujos resultados podem levar a soluções subótimas e até mesmo inviáveis. / Pipeline systems correspond nowadays to the most efficient mode for the transportation of large amounts of liquid and vapor products for long distances. Pipelines are utilized by the Petroleum Industry to transport petroleum and its product derivatives. The present work addresses the scheduling of pipeline distribution of a system that operates with a pipeline that transports products from a refinery to depots at different geographical locations by mathematical programming models. The system is composed by the Planalto Refinery (REPLAN) from Petrobras. A pipeline (OSBRA) is connected to the refinery that extends for approximately 1000 kilometers. A higher level of detail in the mathematical model for pipeline operations developed by Rejowski Jr. (MS Dissertation, EPUSP São Paulo, 2001) becomes essential in this complex logistic operation. A factor of extreme importance is product contamination inside the pipeline. Therefore, special constraints are developed that impose the segments of the pipeline to operate continuously when they do not contain interfaces. These constraints help the proposed formulation to find the optimal solution of the problem. The improvement of logical formulations becomes paramount because the generated models encompass a large number of decisions to be optimized. Logical relations involving the initial inventory at the depots and at the pipeline, as well as the demands for each product are proposed. These relations improve the computational performance of the proposed models in scenarios of high-demand. Then, the special constraints and the demand satisfaction at the depots at the end of the operational horizon are relaxed and added as penalties in the objective function. These penalties increase the solution effort of the proposed models and at the same time have great influence on the operational results of the system. Another factor of extreme importance for the pipeline operation scheduling is its continuous time representation. Additionally, this representation enables the models to incorporate simplified hydraulic constraints. Therefore, a simplified and efficient strategy to determine the pipeline flow rate is to include the yield curves of the pumping stations. This formulation, that is modeled as an MINLP (Mixed Integer Non Linear Programming), is compared to an MILP (Mixed Integer Linear Programming) with discrete time and fixed flow and yield rates proposed by Rejowski Jr. and Pinto (Computers and Chemical Engineering, 2004, v.28/8 p.1511-1528). It is shown that the present formulation provides better quality results. The MILP formulation with discrete time is characterized as a particular case of the proposed formulation. The MINLP is greatly influenced by the number of time intervals that compose it and this factor has always to be considered so that the best solution can be found with feasible computational effort. This formulation is also applied to a case with several pumping station configurations with different unit costs and yield curves. Two formulations that consider the scheduling of pipeline operations with the incorporation of the hydraulic aspects calculated rigorously are presented. The first one results in an MINLP model and considers variations on the time interval durations and in the pipeline flow rate. A second MILP formulation is developed. Computational results for both models are shown as well as the generated solutions discussed. The impact of variations on the topographical profile of the pipeline system is analyzed in the obtained results by the models. Changes in the flow rate of the pipeline, in the decision of the time intervals that the system is activated, in the pumping station yields and in the time interval durations were detected. Then, in another example it is shown that the changes in the topographical profile can alter the sequence of products sent by the refinery to the pipeline. Finally, both formulations have their results compared to models with simplified hydraulic considerations, whose results can lead to suboptimal and even to infeasible solutions.

Tese de mestrado integrado. Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2011

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção / Made available in DSpace on 2012-10-22T21:47:28Z (GMT). No. of bitstreams: 1 230881.pdf: 1308202 bytes, checksum: 8d33831777ae7675475a2e176aa19acf (MD5) / Esta tese tem como objetivo geral conceber um método consistente para resolução do PPOC - Problema de Programação de Ordens de Corte, de forma a considerar todos os custos e restrições envolvidos neste processo decisório. O PPOC é um problema inerente às indústrias têxteis do segmento de confecção e consiste na definição do número de peças - para cada tamanho e cor associados a uma dada referência - que deverão ser cortadas visando atender a uma demanda prevista. Para alcançar o objetivo supracitado, formulou-se o PPOC como um problema de programação não-linear inteira, que foi resolvido através da teoria de grafos. Conceberam-se 17 diferentes algoritmos que envolvem procedimentos clássicos de busca, além de heurísticas inovadoras que visam reduzir o tempo de processamento para obtenção de resultados. Para avaliação da performance de cada um desses algoritmos, foram realizados testes com dados reais acerca de quatro referências de uma indústria do segmento de confecção, além de testes com 30 cenários de demanda criados para esta finalidade. Os resultados obtidos demonstraram que os métodos BVLC/BA - Busca Vertical com Limitação de Custo/ Busca Ávida e BLNALC/BA - Busca com Lista de Nós Abertos e Limitação de Custo/ Busca Ávida possibilitaram a obtenção de melhores resultados para o PPOC, comparativamente aos resultados que podiam ser obtidos anteriormente por aquela indústria. A obtenção de bons resultados para este problema pode propiciar redução nos custos de manutenção de estoques e armazenagem de peças, bem como redução na quantidade de peças que têm de ser vendidas a preços promocionais por excederem a demanda da indústria de confecção.

Dissertação (mestrado) - Pontifícia Universidade Católica do Paraná, Curitiba, 2008 / Bibliografia: f. 76-79 / O Planejamento Mestre da Produção (MPS - Master Production Scheduling) transforma a previsão de vendas em um plano de produção possível de ser executado, o que permite a verificação dos recursos críticos existentes para cumprir o programa proposto por uma / Master Production Scheduling (MPS) transforms the forecasting of sales into a plan of possible production to be executed, so it opens the possibility to find the critical facilities necessary to accomplish the production program. This work presents a comp

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnologico / Made available in DSpace on 2016-01-08T19:45:13Z (GMT). No. of bitstreams: 0 Previous issue date: 1995 / A abordagem DEA (Data Envelopment Analysis) foi originalmente desenvolvida por Charnes, Cooper e Rhodes (1978), objetivando medir a eficiência relativa de unidades de decisão que desempenham tarefas de transformar múltiplos inputs em múltiplos outputs. O modelo original CCR, junto com o modelo BCC e o modelo multiplicativo formam o núcleo das estruturas analíticas que constituem a DEA. Cada um desses modelos classifica a unidade de produção observada como eficiente ou ineficiente e usa um conjunto referência, fixado por objetivos de comparações. A característica que distingue cada modelo é o conjunto referência envolvido. As unidades de produção são então medidas contra o consumo e o nível de produção encontrados no conjunto referência. Neste trabalho, utiliza-se DEA para avaliar a eficiência relativa e a performance gerencial de escolas da rede municipal da cidade do Rio Grande/RS. Considerando-se somente aqueles fatores-escola, ou seja, fatores de controle gerencial, foram aplicados os modelos CCR e BCC. Adicionalmente, com os fatores sócio-econômicos e a taxa de eficiência obtida pelo DEA, procedeu-se uma análise de regressão. Os resultados mostram que, considerando-se somente os fatores-escola, o nível de output indica consideráveis ineficiências para algumas unidades escolares. Porém, incluindo-se os fatores sócio-econômicos na análise, através de um ajustamento feito por meio de regressão linear, observa-se que unidades ineficientes poderiam ser consideradas eficientes, o que indica que os fatores gerenciais não seriam responsáveis pela ineficiência mas sim os fatores sócio-econômicos.

Tese (Doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. / Made available in DSpace on 2012-10-18T16:09:56Z (GMT). No. of bitstreams: 1 151839.pdf: 394647 bytes, checksum: cb5e1e36891637a53060371aa3669605 (MD5) / Aplicação matemática para sistematizar a agricultura em uma ou mais propriedades rurais de um determinado produtor, onde se propõe que as atividades sejam praticadas em conjunto, de forma integrada, a fim de que os resíduos e os subprodutos gerados por uma delas possam ser empregados da melhor forma possível no tratamento de outras, como fertilizantes para o solo ou como alimentos para animais. As atividades a comporem o sistema, que devem fazer parte de um conjunto maior de interesse do produtor considerado, são determinadas pela resolução de um modelo de programação matemática não-linear misto. Este modelo tem ainda a incumbência de especificar as proporções de cada uma das atividades a serem mantidas no sistema ano a ano, bem como dos elementos essenciais para o seu funcionamento, para que seja obtido o máximo lucro possível ao final de um determinado período. A resolução do modelo mencionado é feita por meio de um algoritmo genético associado ao Método Simplex.

Made available in DSpace on 2014-11-10T11:09:53Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-05-30Bitstream added on 2014-11-10T11:57:47Z : No. of bitstreams: 1 000790195.pdf: 918459 bytes, checksum: 01e8141c5483f5a04a86fdd9a1917ef1 (MD5) / O Problema do Caixeiro Viajante (PCV) é um problema clássico de Otimização Combinatória. Dado um conjunto de cidades e os custos de viagem entre cada par delas, o objetivo é encontrar um roteiro que passa em todas as cidades apenas uma vez e retorna à cidade de origem de menor custo total. O enunciado simples e resolução não trivial encantaram muitas pessoas ao longo dos anos. Na literatura são apresentadas diversas formulações matemáticas para o Problema do Caixeiro Viajante, além de comparações entre a qualidade da relaxação linear de tais formulações. A formulação clássica para o PCV é forte, porém possui um número exponencial de restrições, e é equivalente à formulação de multiproduto (multi-commodity), de ordem polinomial. O custo computacional para resolver a relaxação linear da formulação multiproduto é alto, incentivando a busca de novas formas de obter limitantes duais. Na literatura são propostos procedimentos para obtenção de limitantes duais para o PCV utilizando-se do método relax and cut, a partir do problema da designação (PD), dualizando inequações válidas que são violadas pela solução ótima do PD. Neste trabalho, propomos a aplicação do método relax and cut para a formulação do PCV com restrições de multiproduto. Os resultados obtidos no estudo computacional são encorajadores, com a implementação de um algoritmo que gera bons limitantes duais com baixo tempo computacional / The Traveling Salesman Problem (TSP) is a classical Combinatorial Optimization problem. Given a set of cities and travel costs between each pair of them, the objective is to find a tour through all the cities, visiting each city once, and returning to the city of origin with minimum total cost. The simple enunciate and non-trivial resolution enchanted many people through the years. In the literature various formulations for the Traveling Salesman Problem are presented, and the quality of the linear relaxation of such formulations is compared. The classical TSP formulation is strong, but have an exponencial number of constraints, and is equivalent to the multi-commodity formulation, of polinomial order. The computational cost to solve the linear relaxation of the multi-commodity formulation is high, stimulating the search of new ways of obtaining dual bounds. In the literature, procedures to obtain dual bounds to the TSP using the relax and cut technique are proposed, starting from the assignment problem (AP) and dualizing violated valid inequalities by the AP’s optimal solution. In this work, we propose an application of the relax and cut technique to the multi-commodity formulation for the TSP. The results obtained by the computational study are encouraging, with the implementation of an algorithm that generates good dual bounds in low running time

Orientador: Maria do Socorro Nogueira Rangel / Banca: Maristela Oliveira dos Santos / Banca: Valeriano Antunes de Oliveira / Resumo: O Problema do Caixeiro Viajante (PCV) é um problema clássico de Otimização Combinatória. Dado um conjunto de cidades e os custos de viagem entre cada par delas, o objetivo é encontrar um roteiro que passa em todas as cidades apenas uma vez e retorna à cidade de origem de menor custo total. O enunciado simples e resolução não trivial encantaram muitas pessoas ao longo dos anos. Na literatura são apresentadas diversas formulações matemáticas para o Problema do Caixeiro Viajante, além de comparações entre a qualidade da relaxação linear de tais formulações. A formulação clássica para o PCV é forte, porém possui um número exponencial de restrições, e é equivalente à formulação de multiproduto (multi-commodity), de ordem polinomial. O custo computacional para resolver a relaxação linear da formulação multiproduto é alto, incentivando a busca de novas formas de obter limitantes duais. Na literatura são propostos procedimentos para obtenção de limitantes duais para o PCV utilizando-se do método relax and cut, a partir do problema da designação (PD), dualizando inequações válidas que são violadas pela solução ótima do PD. Neste trabalho, propomos a aplicação do método relax and cut para a formulação do PCV com restrições de multiproduto. Os resultados obtidos no estudo computacional são encorajadores, com a implementação de um algoritmo que gera bons limitantes duais com baixo tempo computacional / Abstract: The Traveling Salesman Problem (TSP) is a classical Combinatorial Optimization problem. Given a set of cities and travel costs between each pair of them, the objective is to find a tour through all the cities, visiting each city once, and returning to the city of origin with minimum total cost. The simple enunciate and non-trivial resolution enchanted many people through the years. In the literature various formulations for the Traveling Salesman Problem are presented, and the quality of the linear relaxation of such formulations is compared. The classical TSP formulation is strong, but have an exponencial number of constraints, and is equivalent to the multi-commodity formulation, of polinomial order. The computational cost to solve the linear relaxation of the multi-commodity formulation is high, stimulating the search of new ways of obtaining dual bounds. In the literature, procedures to obtain dual bounds to the TSP using the relax and cut technique are proposed, starting from the assignment problem (AP) and dualizing violated valid inequalities by the AP's optimal solution. In this work, we propose an application of the relax and cut technique to the multi-commodity formulation for the TSP. The results obtained by the computational study are encouraging, with the implementation of an algorithm that generates good dual bounds in low running time / Mestre

Orientador: Geraldo Nunes Silva / Banca: Vilma Alves de Oliveira / Banca: Heloisa Helena Marino Silva / Resumo: Métodos de Runge-Kutta para problemas de controle ótimo contínuo são estudados seguindo os trabalhos de Hager [11], [15] e [17]. O problema de controle ótimo é discretizado transformando-se num problema de programação matemática. Um estudo sobre as condições necessárias de otimalidade para a solução do problema e conexões com o problema adjunto é realizado para obtenção das condições de ordem na discretização. Estuda-se também a convergência da solução do problema discretizado para a solução ótima do problema contínuo (ver Hager [17]). Nesta análise Hager obtêm uma cota para o erro entre a solução numérica e a solução contínua o qual depende do tamanho do passo. Por fim, o trabalho apresenta alguns exemplos com o intuito de ilustrar a teoria apresentada. / Abstract: Runge-Kutta methods for continuous optimal control problems are studied following the papers of Hager [11], [15] and [17]. The control problem is discretized and transformed into a mathematical programming problem. A study about necessary conditions of optimality for the solution of the problem and connections with an adjoint problem are done to provide order conditions for the method of discretization. It is also studied the convergence of the optimal solution of the discrete problem for the solution of the continuous time control problem (see Hager [17]). In this convergence analysis Hager obtains an error bound comparing the numerical and the continuous solution. The error bound is dependent of the size of the step of the method. Finally, some examples are presented aiming at illustrating the discussed theory. / Mestre