Este trabalho aborda a otimização do planejamento produtivo a curto-prazo de um estaleiro náutico. A atual competitividade deste setor motiva a necessidade do uso otimizado dos recursos fabris. Uma ação nessa direção é implantar sistemas computacionais para auxilio do processo de tomada de decisões operacionais buscando atender pedidos dentro de prazos desejados com uso racional dos recursos produtivos. A matéria prima utilizada é a fibra de vidro, envolvendo assim seus processos de fabricação, na confecção de modelos de produtos que concorrem pela utilização de um número limitado de recursos (e.g. postos de trabalho e moldes de laminação). O objetivo principal é minimizar a ociosidade do posto de trabalho gargalo na fabricação de peças entre um modelo e outro de embarcação. Foi elaborada uma abordagem computacional baseada em Programação Linear Inteira Mista (PLIM), onde o problema original é decomposto em problemas menores, que são facilmente resolvidos. Estes problemas menores consistem em um agrupamento menor de produtos, que foram chamados de campanhas. Após a geração das possíveis campanhas, um modelo matemático permite definir as campanhas que devem ser produzidas para atender à demanda de produtos. Na literatura consultada, evidenciaram-se poucos trabalhos com características similares à realidade da empresa estudada. Os resultados obtidos para as campanhas de produção determinadas e para mix de produção variados indicam que a abordagem proposta é capaz de tratar com sucesso o problema real proposto. / This work addresses the optimization of short term production planning in a nautical shipyard. The current competitiveness of this sector motivates the need for optimized use of manufacturing resources. An action in this direction is to employ computing systems that can improve the decision making of scheduling activities. It aims to meet the delivery due dates of products with rational use of productive resources. The used raw material is fiberglass, thus involving their manufacturing processes. And the models of products compete for the use of a limited number of resources (eg, workstations and lamination molds). The main objective is to minimize the idleness of the bottleneck workstation in the manufacturing of parts. A computational approach was developed based on Mixed Integer Linear Programming (MILP), where the original problem is decomposed into smaller problems that are easily solved. These smaller problems consist of a smaller cluster of products, which were named as campaigns. After the generation of possible campaigns, a mathematical model allows to define which campaigns should be produced to meet the demand of products. In literature, there are few researches driven to this sector. The results obtained for all the campaigns and for a varied production mix indicate that the proposed approach is able to successfully address this real problem.

Neste trabalho discutimos a inserção de tópicos básicos de Programação Linear em duas variáveis no ensino médio e apresentamos os resultados da aplicação de uma sequência didática abordando este tema. A aplicação da sequência foi realizada ao longo de oito encontros semanais no Centro de Ensino Médio Pastor Dohms – Unidade Camaquã – na modalidade de oficinas no turno inverso às aulas. Nossa sequência didática priorizou atividades que objetivaram levar os alunos a interpretar resultados e estabelecer conjecturas em detrimento à resolução mecanizada de exercícios. Elaboramos, para a aplicação da sequência, cinco problemas e através deles, desenvolvemos toda a teoria necessária para o entendimento e resolução das atividades. Usamos o software GeoGebra como meio facilitador para que os alunos conjecturassem sobre o teorema básico da Programação Linear. A elaboração e as análises dos resultados da aplicação da sequência didática basearam-se na Teoria de Registros de Representação Semióticas, de Raymond Duval, que trata dos aspectos cognitivos relacionados às representações semióticas e à aquisição de conhecimentos matemáticos. A coleta de dados foi feita através de anotações, filmagens dos encontros e do material produzido pelos alunos durante as aulas. Ao final, da pesquisa concluímos que a abordagem do conteúdo Programação Linear na educação básica pode dar significado a conteúdos que, para os estudantes parecem desconexos, além de aumentar o espectro de problemas passíveis de resolução pelos alunos do ensino médio. / In this paper we discuss the integration of basic topics of Linear Programming in two variables in to high school and we present the results of applying a sequence of didactic addressing this theme. The Mathematics application of the sequence was accomplished with eight weekly meetings at the Pastor Dohms High School in Camaquã, in workshops dummy the opposite shift. Our didactic sequence prioritized activities that were designed to take the student to interpret results, and not merely through mechanic exercises. To apply the sequence, we developed five exercises and through them develop all necessary theory for solving the problems. We used the GeoGebra software to facilitate the learning of the basic linear programming theorem. This program was based on the theory of representation registers due to Raymond Duval the addresses he cognitive aspects of knowledge acquisition. The data was collected from notes, filmed meetings and work produced by students in class. At the end of the study conclude that the linear programming approach of content in basic education can give meaning to the contents that seem unconnected to students in addition to increasing the range of problems solvable by students.

.Wireless Sensor Networks importance is rapidly increasing and becoming a vital element in the process of gathering information in almost every scientific and practical aspect, but since the sensor node is usually a small device and has a battery with very limited life, power consumption is turning out to be the main drawback of this significant technology thus a lot of work and researches is going on to find new ways to reduce the power needed to operate those sensors. One of the main power consuming functionality of this technology is the wireless transmission of the data that the sensors collect across the fields [5][6]. In order to overcome this restriction, many proposals have been made to create an optimal algorithm that can guide the way each sensor node transmit it's data in order to reduce the power needed for the transmission process. This research focuses on creating a simplified scheduling algorithm that can break up the transmission waves into chains of nodes, so that each node transmits the data that has been collected to the best available node around, and so on till the information is propagated to the main server that collects all the information and analyze them.This newly proposed algorithm takes many attributes into considerations, but the main ones are the geographical information and the load that each senor node carries. A simulation model has been created to verify the effectiveness of the algorithm and to compare how close the results to the ideal network configuration are.

Orientador: Ariane Luzia dos Santos / Banca: Renata Zotin Gomes de Oliveira / Banca: Érica Regina Filletti Nascimento / Resumo: Neste trabalho são apresentados os fundamentos da Programação Linear, em especial, da Programação Linear Geométrica, instrumento importante de otimização para problemas de Economia, gestão de empresas, problemas de transportes, obtenção de misturas ótimas, entre outros. Além disso, é apresentada uma proposta didática para os professores de educação básica da escola pública, utilizando o software GeoGebra como instrumento motivador para o estudo de uma situação de aprendizagem proposta no material de apoio idealizado pela Secretaria da Educação do Estado de São Paulo, abordada no caderno do aluno do 3º ano do Ensino Médio / In this work presents the fundamentals of linear programming in particular, of geometric linear programming, important instrument of optimization for economic problems, business management, transport problems, obtaining optimal mixtures, among others. In addition, presents a didactic proposal for teachers of the basic education of public school, using the GeoGebra software as a motivating tool for the study of a learning situation proposed in the support material designed by the Education secretary of the State of São Paulo is presented, adressed in the student notebook of 3rd year of high school / Mestre

A era do petróleo parece estar chegando ao fim e novas fontes de energia, renováveis e mais amigas do meio ambiente, já estão disponíveis para a sociedade. Dentre essas fontes, o biodiesel vem chamando a atenção das autoridades pela sua compatibilidade com o diesel e pelo potencial de geração de riqueza no campo. A Lei 11.097/2005 autorizou a introdução do biodiesel no Brasil, obrigando a adição de 2% ao diesel de petróleo, a partir do ano de 2008. O biodiesel é um produto obtido da transesterificação de óleos e gorduras de origem vegetal, animal ou residual que possui características muito semelhantes ao diesel do petróleo. Sendo assim, não é preciso “reinventar o carro” nem modificar a distribuição para o consumidor final, visto que os motores a diesel podem rodar, facilmente, com porções de biodiesel ao diesel o qual pode ser comercializado nos atuais postos de combustíveis. Assim, é necessário estruturar a cadeia produtiva do biodiesel, para que se possa atender a uma demanda capaz de substituir 2% do diesel comercializado, a partir do ano de 2008. Diante disso, este trabalho visa a elaborar um modelo matemático, utilizando as técnicas da programação linear para auxiliar na decisão sobre a localização das futuras usinas de biodiesel e a sua estrutura de distribuição. Como cada Estado do Brasil poderá utilizar diferentes fontes de óleo vegetal, com base em suas características (geoclimáticas) para a produção de biodiesel, cada Estado poderá ter diferentes configurações da cadeia produtiva. Este trabalho testou o modelo no Estado do Rio Grande do Sul onde a tendência é produzir biodiesel a partir do óleo de soja. O modelo demonstrou, dentre as alternativas escolhidas e com base nas premissas assumidas ao longo deste trabalho, que uma usina de escala grande (120.000 toneladas/ano), localizada em Canoas, seria a alternativa que minimizaria os custos totais de transporte e de instalação. Entretanto, o modelo proposto é flexível para diferentes contextos e distintos parâmetros, adaptando-se às necessidades de cada região. / The age of oil seems to be near the end and new sources of energy, renewable and more environmentally friendly, are already available for society. Amongst these sources, biodiesel has been standing out for its compatibility with diesel and for its potential of wealth generation in this field. The Brazilian law 11,097/2005 authorizes the introduction of biodiesel in Brazil, compelling a 2% addition into diesel oil from the year 2008. Biodiesel is results from the transesterification of oils and fats of vegetal, animal or residual origins, and has very similar characteristics to diesel oil. Thus, one does not need to “reinvent the car” or modify distribution for the final consumer, once diesel-run engines can easily work with portions of biodiesel mixed within diesel oil that is commercialized in current service stations. Thus, it is necessary to structure the productive chain of biodiesel so that it can take care of a demand replacing 2% of the diesel commercialized from the year 2008. Therefore, this work aims to elaborate a mathematical model, using linear programming techniques to help decide where to locate the future biodiesel plants as well as their distribution structure. As each state of Brazil will make use of different vegetal oil sources, due to geographic characteristics, when producing biodiesel, each state might have different configurations of productive chain. This work tests the model in the State of Rio Grande do Sul, where producing biodiesel from the soy oil is the trend. It demonstrates, amongst the alternatives chosen and based on the assumptions throughout this work, that a plant of large scale (120,000 tons per year) located in the city of Canoas would most probably be the alternative to minimize the total costs of transport and installation. However, the model proposed is flexible for different contexts and parameters, able to adapt to the necessities of each region.

A virtualização de redes tem se tornado cada vez mais proeminente nos últimos anos. Tal técnica permite a criação de infraestruturas de rede que se adaptam a necessidades específicas de aplicações de rede distintas, além de dar suporte à instanciação de ambientes favoráveis para o desenvolvimento e avaliação de novas arquiteturas e protocolos. Apesar de esforços recentes (motivados principalmente pela busca de mecanismos para avaliar propostas relacionadas à Internet do Futuro) terem contribuído substancialmente para a materialização desse conceito, nenhum preocupou-se em conciliar alocação eficiente de recursos e satisfação de requisitos de segurança (e.g., confidencialidade). É importante ressaltar que, no contexto de redes virtuais, a proteção de infraestruturas de rede compartilhadas constitui condição fundamental para seu uso em larga escala. É de grande importância que o impacto negativo causado pelo aprovisionamento de segurança seja considerado no processo de mapeamento de redes virtuais, de forma a permitir o uso integral dos recursos físicos sem subestimar requisitos de capacidade. Portanto, nesta dissertação, são propostos um modelo ótimo e um al- goritmo heurístico para realizar o mapeamento de redes virtuais em substratos físicos que têm por objetivo otimizar a utilização de recursos físicos garantindo a satisfação de requisitos de segurança. Ambas as abordagens possuem uma modelagem precisa de custos adicionais associados a mecanismos de segurança usados para proteger re- des virtuais, e são capazes de atender requisições de redes virtuais de forma online. Além disso, são apresentados os resultados de um extensivo processo de avaliação realizado, incluindo uma comparação detalhada entre o modelo ótimo e o algoritmo heurístico. Os experimentos revelam que o modelo baseado em Programação Linear Inteira é capaz de alocar redes virtuais de forma ótima em substratos físicos com até cem roteadores, enquanto que o algoritmo heurístico é capaz de adaptar-se a infraestruturas maiores, provendo mapeamentos sub-ótimos em um curto espaço de tempo. / Network virtualization has become increasingly prominent in recent years. It enables the creation of network infrastructures that are specifically tailored to the needs of distinct network applications and supports the instantiation of favorable en- vironments for the development and evaluation of new architectures and protocols. Although recent efforts (motivated mainly by the search for mechanisms to eval- uate Future Internet proposals) have contributed substantially to materialize this concept, none of them has attempted to combine efficient resource mapping with ful- fillment of security requirements (e.g., confidentiality). It is important to note that, in the context of virtual networks, the protection of shared network infrastructures constitutes a fundamental condition to enable its use in large scale. Considering the negative impact of security provisions in the virtual network embedding process is of paramount importance in order to fully utilize physical re- sources without underestimating capacity requirements. Therefore, in this thesis we propose both an optimal model and a heuristic algorithm for embedding virtual networks on physical substrates that aim to optimize physical resource usage while meeting security requirements. Both approaches feature precise modeling of over- head costs of security mechanisms used to protect virtual networks, and are able to handle virtual network requests in an online manner. In addition, we present the results of an extensive evaluation we carried out, including a detailed comparison of both the optimal model and the heuristic algorithm. Our experiments show that the Integer Linear Programming (ILP) model is capable of optimally embedding virtual networks on physical infrastructures with up to a hundred routers, while the heuristic algorithm is capable of scaling to larger infrastructures, providing timely, sub-optimal mappings.

We have proposed a method by which the topology of a network might be discovered through an algorithm like the distributed Bellman-Ford algorithm. We have explored the inner workings of two methods to automate power distribution network reconfiguration, the ILP Solver and the Heuristic Solver. We have seen how networks of different shapes can be translated into a flattened topology, which is necessary preprocessing to find a power assignment solution for a network. We have also seen some experimental results comparing the performance of the ILP Solver and the Heuristic Solver. The Heuristic Solver is a very fast, efficient algorithm to reconfigure power distribution, which is important in the case of an emergency. It performs consistently with near perfect results at a speed that is orders of magnitude quicker than the ILP Solver in almost all cases. In an application where a network is small and time is not an important constraint, the ILP Solver could possibly be preferable, but in any context where time is sensitive and near-perfect results are as acceptable as perfect results, the Heuristic Solver is much preferable. There is always room for improvement. Future tests should perhaps allow for non-integer capacity units, or loads that require other values than unit capacity. Optimizing each algorithm by rewriting them in C could give more optimized tests, though this may not be necessary to make judgments about implementing one or the other. There may be some ways to improve the Heuristic Solver, such as arranging the ordered_links in some way that could be more optimal. The algorithm could also be improved by taking advantage of the fact that once there are no more sources with capacity to provide any loads, the process of trying to assign loads to them for power supply can cease. Perhaps this method could be combined with other methods that do not presently account for load priorities or place as much value on fast execution.

Neste trabalho discutimos a inserção de tópicos básicos de Programação Linear em duas variáveis no ensino médio e apresentamos os resultados da aplicação de uma sequência didática abordando este tema. A aplicação da sequência foi realizada ao longo de oito encontros semanais no Centro de Ensino Médio Pastor Dohms – Unidade Camaquã – na modalidade de oficinas no turno inverso às aulas. Nossa sequência didática priorizou atividades que objetivaram levar os alunos a interpretar resultados e estabelecer conjecturas em detrimento à resolução mecanizada de exercícios. Elaboramos, para a aplicação da sequência, cinco problemas e através deles, desenvolvemos toda a teoria necessária para o entendimento e resolução das atividades. Usamos o software GeoGebra como meio facilitador para que os alunos conjecturassem sobre o teorema básico da Programação Linear. A elaboração e as análises dos resultados da aplicação da sequência didática basearam-se na Teoria de Registros de Representação Semióticas, de Raymond Duval, que trata dos aspectos cognitivos relacionados às representações semióticas e à aquisição de conhecimentos matemáticos. A coleta de dados foi feita através de anotações, filmagens dos encontros e do material produzido pelos alunos durante as aulas. Ao final, da pesquisa concluímos que a abordagem do conteúdo Programação Linear na educação básica pode dar significado a conteúdos que, para os estudantes parecem desconexos, além de aumentar o espectro de problemas passíveis de resolução pelos alunos do ensino médio. / In this paper we discuss the integration of basic topics of Linear Programming in two variables in to high school and we present the results of applying a sequence of didactic addressing this theme. The Mathematics application of the sequence was accomplished with eight weekly meetings at the Pastor Dohms High School in Camaquã, in workshops dummy the opposite shift. Our didactic sequence prioritized activities that were designed to take the student to interpret results, and not merely through mechanic exercises. To apply the sequence, we developed five exercises and through them develop all necessary theory for solving the problems. We used the GeoGebra software to facilitate the learning of the basic linear programming theorem. This program was based on the theory of representation registers due to Raymond Duval the addresses he cognitive aspects of knowledge acquisition. The data was collected from notes, filmed meetings and work produced by students in class. At the end of the study conclude that the linear programming approach of content in basic education can give meaning to the contents that seem unconnected to students in addition to increasing the range of problems solvable by students.

Os custos de produção de minério de ferro possuem variações de acordo com a especificidade de cada mina. Na fase mina, dois dos maiores custos de produção estão associados aos índices: distância média de transporte e a relação estéril minério. A implantação do projeto de múltiplas minas e correias transportadoras em Itabira visa diminuir os custos associados a estes dois indicadores. O método de alimentação da planta de beneficiamento oriundo de múltiplas minas foca em reduzir a relação estéril minério global do complexo e a implantação de correias transportadoras mitiga o aumento da distância média de transporte. O presente trabalho tem seu enfoque em uma proposta de lavra de múltiplas minas e de uma pilha de minério para alimentação de três diferentes usinas. Propõem-se um modelo de programação linear por metas que determinará a melhor alimentação das usinas, menor distância média de transporte e menor relação estéril minério. Este modelo de otimização foi elaborado utilizando o software LINGO com interface com EXCEL, e avalia cenários diversificados entre o transporte por caminhões fora de estrada e o transporte misto entre caminhões fora de estrada e transportadores de correia de longa distância. Os resultados apresentados mostram que o método de múltiplas minas é uma saída técnica e economicamente viável para melhor aproveitamento das jazidas do Complexo Minerador de Itabira, apresentando uma economia que varia de US$82M até US$118M dependendo do local de instalação das unidades de Britagem Semimóvel (BSMs). / Production costs of iron ore varies according to the specificity of each mine. In the mining phase, some of the largest operational costs are associated to the haulage distance and the stripping ratio. In this context, the implementation of the multiple mines project and the conveyor belts at the Itabira Complex Mines aims to optimize these two indicators. The multiple mines methodology focuses on reducing the overall stripping ratio of the complex, and the implementation of conveyor belts mitigates the increase of the haulage distance. Two mines and a stock pile are available to feed three different concentration plants. The goal is to achieve the best way to feed the plants considering the economic aspects. A linear goal programming model is proposed to determine the best iron ore mass feeding the plants from different mines, taking into account the least haulage distance and the smallest stripping ratio. This optimization model was developed using LINGO Software to interface with EXCEL and evaluate diversified scenarios. The results showed that the method of multiple mines is a technical and economically viable method for mine planning at the Itabira Complex.

Este trabalho apresenta o processo de seleção de estratégia de reconversão industrial de uma pequena refinaria de petróleo no Sul do Brasil através da aplicação de uma modelagem integrada, utilizando um método multicriterial e programação matemática. Neste estudo foram identificadas linhas de negócio potencialmente aplicáveis à realidade da companhia e definido um conjunto de critérios de análise abrangendo as três dimensões da sustentabilidade empresarial: econômica, social e ambiental. Com base na avaliação da importância relativa de cada critério, atribuída por um grupo de decisores, e no desempenho das linhas de negócio em cada um dos critérios, foi aplicado método fuzzy TOPSIS para análise e ordenação das linhas de negócio. As informações resultantes desta análise, juntamente com dados econômicos objetivos, foram utilizadas em um modelo de programação linear inteira para avaliar portfólios viáveis de linhas de negócio, identificando estratégias candidatas à implementação na refinaria. O desempenho global de cada estratégia candidata, obtido mediante agregação dos desempenhos individuais das linhas de negócio e calculado conforme método fuzzy TOPSIS, foi analisado através de ferramentas gráficas, de modo a gerar elementos para subsidiar a seleção da melhor estratégia de reconversão. Os resultados obtidos demonstraram a eficiência da abordagem proposta, no sentido de facilitar o entendimento e a exploração da situação problema e, assim, oferecer um adequado suporte à tomada de decisão. / This dissertation presents a selection process of industrial reconversion strategy in a small oil refinery in southern Brazil by applying an integrated modeling approach, using a multicriteria and a mathematical programming method. Potentially performing business lines were identified, as well a set of criteria covering the three dimensions of corporate sustainability: economic, social and environmental. Based on the relative importance evaluation of each criteria given by a group of decision-makers, and on performance of the business lines in each of the criteria, fuzzy TOPSIS method was applied for analysis and sorting of business lines. The information resulting from this analysis, along with objective economic data, were used in integer linear programming model to evaluate effective portfolios of business lines, identifying candidate strategies to implement in the refinery. Fuzzy TOPSIS is used to generate overall performance scores of each candidate strategy, aggregating the individual performance of the business lines. The sustainability assessment was analyzed through graphical tools in order to generate information to support the selection of the best strategy for the industrial reconversion. The results demonstrated the efficiency of the proposed approach to facilitate the understanding and exploitation of the problem situation and thus offer adequate support to decision making.