Blog

UNIVESIDADE ESTÁCIO DE SÁ / CAMPUS: VIRTUAL: EAD ALUNO: EDMUNDO CERQUEIRA – MATRÍCULA: 201101165952 CURSO: LOGISTICA – EAD DISCIPLINA: OTIM ZAÇÃO DE SISTEMA DE TRANSPORTE professor: Luis Otavio de Marins Ribeiro Data: 31 de Outubro de 2011. ATIVIDADE ES RUTURADA APRESETAÇAO Neste este trabalho v profissional no ramo satisfação como Inici vivemos em um mun tudo muda rapidame to next*ge pouco da atividade m da nossa , uma vez que de tensões, no qual erdade o que nos reserva o futuro. Neste contexto, poss vel confiar, nos outros? É possível confiar no amanhã, no mercado globalizado, nos rojetos, nos governantes?

A maioria das pessoas acha que não mais existe neste instigante horizonte especialista no assunto que sustentam que sim, é possível – é necessário. Portanto confiança a minha concepção é a chave para o sucesso pessoal e empresarial. Vale acrescentar que o sucesso não cai do céu é preciso nos abraçar uns ao outros, pois somos todos anjos com apenas uma asa. só podemos voar quando abraçados uns aos outros. Pois surgimos em um lugar quente e aconchegante, onde nossas necessidades são atendidas automaticamente e uma presença constante nos envolve com seus movimentos e voz.

Gozamos de um estado de unidade e sincronicidade com o universo que nos supre, sem distinguir onde nós terminamos e eles começam. e quaisquer esforços utilizados para a realização do bem e para o bem vale apena. RESUMO O presente trabalho apresenta um estudo de caso sobre a otimização de roteiros na distribuição de ferro, de uma empresa localizada em Passo Fundo para 26 lojas filiais, localizadas em cidades da região, com a finalidade de se determinar o roteiro ótimo a ser realizado, que corresponda ao caminho de menor distância entre as cidades a serem visitadas, em cada distribuição.

Realizou-se um estudo sobre o problema real, o qual foi representado através de um modelo matemático de otimização linear inteira, para o qual buscou-se encontrar uma solução ótima, através de técnicas de otimização. Como geralmente existe uma grande quantidade de variáveis em aplicações reais, também foram utilizados programas computacionais para a resolução do problema em questão. Devido às características do problema analisado, optou-se por realizar a otimização através do Solver do Excel.

Assim, apresenta-se o problema real, a modelagem matemática utilizada, para sua resolução, e os resultados obtidos través da otimização das quatro principais ratas, realizadas pelo funcionário que transporta o ferro para a empresa. Como resultado, obteve-se uma redução média de 11,52% na distância total a ser percorrida, pelo funcionário, na distribuição do ferro realizada pela empresa. 1. INTRODUÇAO Devido às rápidas transformações que ocorrem na atualidade, buscam-se sempre novas ferramentas, para que se possa acompanhar essas transformações.

Com isso, acabam surgindo alguns problemas complexos, que necessitam do auxílio de ferramentas da matemática, a PAGF 39 acabam surgindo alguns problemas complexos, que necessitam o auxilio de ferramentas da matemática, para que possam ser resolvidos e analisados. Existem várias técnicas de resoluções utilizadas em aplicações reals. Neste trabalho, devido às características do problema a ser resolvido, foram utilizadas a Modelagem Matemática e a Otimização. O problema real trata da otimização da distribuição de ferro de uma empresa localizada em Passo Fundo/RS, que o transporta para 26 cidades da região.

A distribuição é realizada por um funcionário, que trabalha na própria empresa, o qual Informou a existência de quatro principais rotas diferentes. Os roteiros oram representados através de modelos matemáticos e foram otimizados, a finalidade de se determinar quais deveriam ser os caminhos ótimos, ou seja, que correspondam aos roteiros de menor distância, visando economia de custos e de tempo, de modo que as entregas pudessem ser feitas de forma mais rápida e econômica.

Para tanto, foi realizada uma revisão bibliográfica sobre os assuntos relacionados ao problema, visando identificar modelos e métodos matemáticos adequados para sua resolução e, também, foi feita uma pesquisa de campo com funcionários da empresa, para se obter os dados reais necessários para a odelagem matemática do problema. Desta maneira, foi possível construir modelos matemáticos, para representar os problemas reals.

Assim, apresenta-se os resultados obtidos em relação ao processo de otimização de um problema real da distribuição de ferro realizada por uma empresa de Passo Fundo, para região, o qual foi transformado em modelos matemáticos de otimização, os quais Fundo, para região, o qual foi transformado em modelos matemáticos de otimização, os quais foram otimizados, com objetivo de se obter as soluções ótimas para o problema, através de técnicas de otimização

Diversos problemas reais podem ser modelados, como problemas de Programação Linear, através de modelos de fluxo em redes, tais como o problema de transmissão de mensagens em redes de computadores, o problema do transporte de mercadorias das fábricas até o mercado consumidor, e também, o problema de determinação do caminho mínimo para se entregar mercadorias em várias cidades distintas, que trata-se do problema real abordado neste trabalho.

Nos problemas de fluxo em rede realiza-se o processo de otimização da distribuição de produtos, originados em pontos de oferta e consumidos em postos de demanda, dentro de ma rede de interligações possíveis. Os problemas de fluxo em rede podem ocorrer dentro de plantas industriais, sistema de comunicação e de transporte, de distribuição de água e outros, mas servem para outros modelos de situações diversas que se assemelham, por abstração. Geralmente a oferta e a demanda de cada produto possuem um valor conhecido.

A distribuição dos produtos não precisa ser somente de um ponto de produção a um ponto de demanda, mas também podem ser utilizados pontos intermediários. As interligações podem possuir restrições de capacidade de tráfego e custos variados. Um dos problemas clássicos de fluxo em redes é o Problema de Fluxo de Custo Mínimo, que consiste em determinar qual o melhor caminho a ser percorrido pelo fluxo, de produtos, em uma rede, que corresponda ao roteiro de menor custo poss 2 percorrido pelo fluxo, de produtos, em uma rede, que corresponda ao roteiro de menor custo possível.

Dentre os problemas de fluxo com custo mínimo em redes, destaca-se o problema do caixeiro viajante (PCV), o qual será utilizado na resolução do problema proposto. 2. PROBLEMAS DO CAIXEIRO VIAJANTE Conforme Golbarg e Luna (2000), o Problema do Caixeiro Viajante é um dos mais conhecidos problemas de programação matemática. Os problemas de roteamento lidam em sua maior parte com passeios ou tours sobre pontos de demanda ou oferta. Esses pontos podem ser representados por cidades, postos de trabalho ou atendimento, depósitos, etc.

Um dos mais importantes tipos de passeios, o denominado hamiltoniano, tem esse nome, pois em 1857, Willian Rowan Hamilton propôs um jogo que chamou de “‘Around the World”. Esse jogo era realizado sobre um dodecaedro sendo que cada vértice estava associado a uma cidade. O objetivo do jogo era encontrar um caminho, través dos vértices do dodecaedro, que iniciasse e terminasse em uma mesma cidade sem nunca repetir uma visita. Uma solução do jogo de Hamilton chamou-se ciclo hamiltoniano. Apesar de Hamilton não ter sido o primeiro a propor esse problema, o seu jogo o divulgou.

Hassler Whitney foi quem divulgou primeiramente esse problema em 1934. O problema do caixeiro viajante é um problema de otimização que está associado à determinação dos caminhos hamiltonianos em um grafo qualquer. O objetivo deste problema é encontrar em um grafo o caminho hamiltoniano de menor custo. O Problema do Caixeiro Viajante é importante devido a pelo enos três características: grande aplicação prática, uma enorme PAGF s 9 importante devido a pelo menos três características: grande aplicação prática, uma enorme relação com outros modelos, grande dificuldade de solução exata.

O problema do caixeiro é um clássico exemplo de problema de otimização combinatória (CAIXEIRO, 2009). O que se poderia fazer no primeiro momento para se resolver esse tipo de problema é reluzi-lo a um problema de enumeração: acham-se todas as rotas possíveis, depois se calcula o comprimento de cada uma delas, para então ver qual a menor. Quando se acha todas as rotas e estas são contadas, pode-se dizer que se está reduzindo o problema de otimização a um problema de enumeração.

Se fizermos raciocínio combinatorio simples, encontra-se o numero de rotas para o caso de n cidades. por exemplo, no caso de n CIC]5 cidades, a primeira e última posição são fixas; na segunda posição podemos colocar qualquer uma das quatro cidades restantes; na terceira posição podemos colocar qualquer uma das três cidades restantes e na quarta posição podemos colocar as duas cidades restantes, teremos apenas uma cidade para colocar na quinta osição. Conseqüentemente, o número de rotas seria: 4 x 3 x 2 x 1 = 24.

Da mesma forma, se tivermos n cidades, como a primeira é fixa, fica fácil de perceber que o número total de escolhas que se pode fazer é cn ou seja, an 01 0! caminhos possíveis. Quando o problema é simétrico a quantidade de caminhos possíveis reduz para (n C] 1)! /2. Desta forma podemos gerar cada rota, calcular o comprimento total das viagens de cada rota e verqual delas tem o menor comprimento total. Analisando superficialmente, parece ser uma tarefa fácil, mas não é mesmo PAGF 6 39 menor comprimento total. ? mesmo usando computadores muito bons.

Pode-se perceber a complexidade de resolução de um PCV, através dos dados da Tabela 1, que apresenta o tempo necessário para resolução de problemas de acordo com o número de nós ( n ) envolvidos , na rede considerada, através da análise de todos os caminhos possíveis. A presença de um fatorial na medida do esforço computacional do método da redução torna inviável o uso do computador para problemas muito grandes. Por esse motivo pode-se dizer que o problema do caixeiro viajante é um problema NP-difícil, ou seja, possui ordem de resolução de complexidade ão polinomial.

O método reducionista torna-se prático para o caso de n ser bem pequeno, caso contrário não. Ainda não foi encontrado um método prático para resolver o problema do caixeiro viajante que envolva esforço polinomial e começa- se a pensar que este não existe. O fato de existir ou não um método que envolva esforço polinomial para resolver o problema do caixeiro viajante é um dos grandes problemas em aberto da Matemática. Se fosse descoberta uma forma de resolver o problema do caixeiro em tempo polinomial, poderia ser resolvida, também em tempo polinomial, uma grande quantidade de outros roblemas matemáticos importantes.

Mas se ficasse provado que é impossivel resolver o problema do caixeiro em tempo polinomial, também fica entendido que uma grande quantidade de problemas importantes não teria solução em tempo polinomial. Tabela 1 : Tempo necessário para resolução de um PCV com n nós n rotas por segundo On 01 0! cálculo total 5 250 mi PAGF 7 9 necessário para resolução de um PCV com n nós n rotas por segundo Dn 21a! cálculo total 5 250 milhoes 24 Insignificante 10 110 milhoes 362 880 0. 003 seg1S 71 milhoes 87 bilhoes 20 min 20 53 milhoes 1 x 1017 73 anos 25 42 mllhoes 6. 1023 470 milhoes de anos Fonte: (CAIXEIRO, 2009) Existem várias formulações para o PCV, devidas sua importância. Além disso, foi dito que o PCV possui uma quantidade de restrições da ordem de n 2 . No exemplo acadêmico apresentado para uma rede com 5 nós foram necessárias 35 restrições, como já era esperado (ordem de 2 CIC]32 n Dessa forma, buscou-se investigar outros aplicativos que resolvessem problemas maiores e que facilitassem, também, a inserção dos dados do problema. Entre eles escolheu-se o software Excel que é apresentado a seguir 3. RESOLUÇÃO DO pcv ATRAVÉS DO SOLVER DO EXCEL

Uma das maneiras de resolver o problema com o Excel é utilizando uma matriz de variáveis e custos. A seguir serão apresentados os passos que devem ser seguidos para se obter a otimização de um problema de programação linear ou de programaçao linear inteira (LACHTERMACHER, 2007). Primeiramente os dados serão inseridos em duas matrizes, uma para as distâncias (custos) e outras para as variáveis. Considerando um PVC com 5 nós. Na Figura 2 estão apresentadas as duas matrizes, sendo a primeira das distâncias (ou custos nos arcos) e a segunda das variáveis. Neste exemplo a matriz das istâncias e simetrica.

A segunda etapa é inserir equações referentes as restrições de fluxo de entrada no nó, cujo somatório deverá ser 1, e de fluxo de salda do nó, cujo somatóno também deverá ser 1, ou seja, o soma deverá ser 1, e de fluxo de saída do nó, cujo somatório também deverá ser 1, ou seja, o somatório dos fluxo de entrada e saída deverão ser iguais a 1. As células H13 a H17 contêm os somatórios das linhas referentes às colunas C à G e as células C 18, DIB, E 18, F18 e G18 contêm os somatórios das colunas referentes às linhas 13 à 17 (ver Figura 3).

O valor da função objetivo foi inserido na célula B2. Para chegarmos ao resultado correto da função objetivo ara i 1„5, ou seja, que todo fluxo fosse do nó para ele mesmo. Esta solução apesar de ser possível não é a solução do problema, pois não apresenta um caminho único que inicie e termine no mesmo nó, visitando todos os nós da rede, com custo mínimo. Nesse caso, a solução indica que existem subciclos que sevem ser evitados.

Assim, conforme o software indica os subciclos hamiltonianos, são inseridas restrições de modo que os subciclos obtidos nas otimizações sejam evitados. Após as inserções das restrições, para evitar os subciclos encontrados, novamente é solicitado ao software que faça a otimização do PCV. Figura 3: Inserção de restrições de conservação de fluxo nos nós Figura 4: Inserção da função objetivo para que fosse encontrada a solução ótima do problema, foi necessário inserir apenas quatro restrições para que os CICIOS hamiltonianos fossem evitados, entre dois e três nós apenas. . PROBLEMA DE DISTRIBUIÇÃO DA EMPRESA MACONORTE Na empresa Maconorte Comércio de Materiais de Construção, que é uma rede de material de construção, e transportado, cinco ezes por semana, ferro para as filiais localizadas em 26 cidades da região de Passo Fundo. Como, o caminhão, q semana, ferro para as filiais localizadas em 26 cidades da região de Passo Fundo.

Como, o caminhão, que transporta o ferro, faz muitas rotas diferentes, surgiu a curiosidade de saber qual seria o melhor camlnho a ser feito pelo funcionário que leva o ferro, obtendo- se, assim, o percurso de distância mínima para distribuição do produto. Assim, o objetivo, deste trabalho é elaborar modelos matemáticos que representem as principais rotas feitas pelo aminhão, analisar os modelos e resolvê-los pelo método mais adequado para o problema, obtendo assim os caminhos ótimos a serem percorridos, de modo que o gasto com o transporte seja minimo.

Através de uma funcionária da empresa, com a autorização do gerente da mesma, obteve-se a lista das cidades pelas quais é transportado o ferro. Após, foi elaborado um questionário, o qual foi aplicado ao funcionário que transporta o ferro, para saber quais são as rotas mais utilizadas por ele, e por que ele faz aquele caminho. Com essas informações é possível desenvolver o modelo para chegarmos ao objetivo do trabalho.

Segundo o funcionário que transporta o ferro, as rotas feitas por ele semanalmente, são as seguintes: passo Fundo à Marcelino Ramos, Passo Fundo à Nova Prata, Passo Fundo à São José do Ouro, passo Fundo à Jacutinga e passo Fundo à Selbach. Para realizar a primeira rota ele sai de Passo Fundo, passa em Sertão, Estação, Getúlio Vargas, Erechim, Viadutos, Marcelino Ramos e volta para Passo Fundo. Para realizar a segunda rota ele sai de Passo Fundo, vai para Casca, Paraí, Nova Araça, Guaporé, Nova Prata e volta para Passo Fundo. Ao realizar a terceira rota ele sai de Pa