Otimização em Redes-Algoritmos CPM-PERT e Caminho Crítico

1 Profª Dra Stella Jacyszyn Bachega Escopo e Definição de Problemas Alguns exemplos Minimizar custo de construção de uma rede de tubulações de gás natural Determinar o caminho mais curto entre duas cidades em uma rede de rodovias existentes Determinar a capacidade máxima de um oleoduto que liga a fonte até as empresas receptoras Determinar um cronograma para as atividades de um projeto de construção civil Determinar um esquema de fluxo de custo mínimo entre as bacias de petróleo e as refinarias por meio de uma rede de tubulações 2 Alguns algoritmos de otimização em redes 1 Algoritmo de caminho crítico CPM Critical Path Method PERT Program Project Evaluation and Review Technique 2 Árvore geradora mínima 3 Algoritmo de caminho mais curto 4 Algoritmo de fluxo máximo Escopo e Definição de Problemas N A Onde N conjunto de nós A conjunto de arcos Exemplo Definições Rede conjunto de nós conectados por arcos ou ramos Notação 3 Definições Arco orientado dirigido permite fluxo positivo em uma direção e fluxo zero na direção oposta Rede orientada todos os arcos são orientados Caminho sequência de arcos distintos que ligam dois nós passando por outros nós independentemente da direção de fluxo em cada arco Ciclo loop caminho formado que conecta um nó a si mesmo passando por outros nós Rede conectada rede na qual todos os pares de nós estão ligados por no mínimo um caminho Definições Árvore rede conectada sem ciclos formada por um subconjunto de todos os nós Árvore geradora árvore que liga todos os nós da rede 4 Algoritmo de Caminho Crítico O PERT CPM é uma ferramenta de valiosa colaboração quando da elaboração de um planejamento e de seu respectivo controle objetivando atingir uma determinada meta PERTCPM 5 O CPM Critical Path Method foi elaborado entre 1956 e 1958 pela Dupont Company que desenvolvia projetos de produtos químicos Para cumprirem os seus objetivos deveriam executar os projetos com o máximo de precisão em relação ao fator tempo Origem O PERT Program Project Evaluation and Review Technique foi elaborado por volta de 1957 por uma equipe de Projetos Especiais da Marinha dos EUA quando necessitava desenvolver um projeto muito complexo construir um foguete o qual requeria um sólido planejamento e um rígido controle considerando a grandeza do projeto O projeto contava com 200 empreiteiras 9000 subempreiteiras e deveriam ser construídas em torno de 70000 peças Com a aplicação da técnica foi possível reduzir de cinco para apenas três anos o tempo para execução do projeto do submarino atômico que conduziria o míssil Polaris Origem 6 O PERT CPM pode ser aplicado em tudo que se possa imaginar que tenha uma origem e um término previamente fixado Desde a fabricação de um alfinete até a elaboração de um projeto para colocar um satélite em órbita Campo de Aplicação O PERT trabalha com três estimativas de tempo Tempo otimista condições favoráveis Tempo mais provável tempo mais próximo da realidade Tempo pessimista condições desfavoráveis Por este motivo o PERT possui características probabilísticas e variáveis aleatórias Portanto para calcular o tempo de cada atividade é necessário usar a fórmula abaixo O CPM possui características determinísticas e variáveis reais Diferenças básicas 7 Atividade representa uma parcela do trabalho total necessário para a execução de um projeto Consome tempo e recursos humanos financeiros tecnológicos e materiais Evento é a caracterização no tempo da origem ou do término de uma atividade não consome tempo e nem recursos Alguns conceitos Atividade fantasma não consome tempo e nem recursos mas só deve ser utilizada quando for realmente necessária Casos que deve ser utilizada Evitar que entre dois eventos sucessivos exista mais do que uma atividade Demonstrar a independência de uma atividade Alguns conceitos 8 o Atividades condicionantes são aquelas que condicionam a realização das atividades que lhes sucedem o Atividades paralelas são duas ou mais atividades ocorridas entre dois eventos sucessivos o Atividades simultâneas são duas ou mais atividades que partem de um único evento e se direcionam para eventos diferentes Alguns conceitos Exemplo CPM Atividade Eventos Duração D dias Antecedente Subsequente A 1 2 10 B 1 3 6 C 2 4 7 D 3 4 5 E 3 5 9 F 4 6 5 G 5 6 4 9 1 Com base no quadro monte o Diagrama ou a Rede que é a representação gráfica do projeto Roteiro para aplicar a técnica A C F B E G D 10 7 5 4 5 9 6 1 2 4 6 3 5 2 Calcule os tempos mais cedo e os represente no lado esquerdo dos eventos Faça para todos os caminhos presentes na rede Roteiro para aplicar a técnica A C F B E G D 10 7 5 4 5 9 6 1 0 2 10 4 17 11 22 16 19 6 3 6 6 5 15 10 3 Calcule os tempos mais tarde e os represente no lado direito dos eventos Faça para todos os caminhos presentes na rede sentido inverso dos fluxos Roteiro para aplicar a técnica A C F B E G D 10 7 5 4 5 9 6 1 0 0 6 3 2 10 10 4 17 17 11 17 22 16 19 6 22 3 6 12 9 6 5 15 18 FT Folga Total é o atraso máximo que uma atividade pode ter sem alterar a data final de sua conclusão FT TD D ou FT Dtf Dci D FL Folga Livre é o atraso máximo que uma atividade pode ter sem comprometer a data mais cedo do seu evento final FL Dcf Dci D FD Folga Dependente é o período que se dispõe para realização da atividade iniciandoa no tarde do evento inicial e não ultrapassando o tarde do evento final FD Dtf Dti D FI Folga Independente é o período que se dispõe para a realização da atividade iniciandoa no tarde do evento inicial e não ultrapassando o cedo do evento final FI Dcf Dti D Cálculo das Folgas 11 Exemplo do cálculo das folgas e do tempo disponível TD 1 2 5 18 3 14 A 10 Cálculo das Folgas Cálculo das Folgas 12 Métodos para estabelecer o Caminho Crítico I Pelas diferenças constantes entre os cedos e os tardes encontrada no último evento Regras Básicas a não são críticas as atividades cuja diferença entre cedos e tardes não seja igual àquela encontrada no último evento b poderão ser críticas aquelas atividades cuja diferença no evento inicial e final entre cedos e tardes seja igual à encontrada no último evento c são realmente atividades críticas aquelas que obedecem à condição anterior e que a data mais tarde de seu evento final menos a sua própria duração é exatamente igual à data mais tarde de seu evento inicial ou seja Tarde Posterior Duração da Atividade Tarde Anterior Determinação do Caminho Crítico II Pelas Folgas das Atividades onde as folgas livre total dependente e independente devem ser iguais a 0 zero Determinação do Caminho Crítico 13 4 Selecionar os tempos mais cedo e os tempos mais tarde que serão utilizados para os cálculos das folgas Roteiro para aplicar a técnica A C F B E G D 10 7 5 4 5 9 6 1 0 0 6 3 2 10 10 4 17 17 11 17 22 16 19 6 22 3 6 12 9 6 5 15 18 Maior valor Menor valor Exemplo CPM Atividade D Cedo Tarde FT FL FD FI i f i f A 10 B 6 C 7 D 5 E 9 F 5 G 4 FT Dtf Dci D FL Dcf Dci D FD Dtf Dti D FI Dcf Dti D 5 Calcular as folgas total livre dependente e independente 14 Exemplo CPM Atividade D Cedo Tarde FT FL FD FI i f i f A 10 0 10 0 10 0 0 0 0 B 6 0 6 0 9 3 0 3 0 C 7 10 17 10 17 0 0 0 0 D 5 6 17 9 17 6 6 3 3 E 9 6 15 9 18 3 0 0 0 F 5 17 22 17 22 0 0 0 0 G 4 15 22 18 22 3 3 0 0 FT Dtf Dci D FL Dcf Dci D FD Dtf Dti D FI Dcf Dti D 5 Calcular as folgas total livre dependente e independente Exemplo CPM Atividade D Cedo Tarde FT FL FD FI i f i f A 10 0 10 0 10 0 0 0 0 B 6 0 6 0 9 3 0 3 0 C 7 10 17 10 17 0 0 0 0 D 5 6 17 9 17 6 6 3 3 E 9 6 15 9 18 3 0 0 0 F 5 17 22 17 22 0 0 0 0 G 4 15 22 18 22 3 3 0 0 3 FT Dtf Dci D FL Dcf Dci D FD Dtf Dti D FI Dcf Dti D 5 Calcular as folgas total livre dependente e independente 15 5 Identifique o tempo total do projeto e o caminho crítico Roteiro para aplicar a técnica A C F B E G D 10 7 5 4 5 9 6 1 0 0 6 3 2 10 10 4 17 17 11 17 22 16 19 6 22 3 6 12 9 6 5 15 18 Tempo total do projeto 22 dias Caminho crítico A C F Exemplo PERT Atividade Eventos Duração D dias Antecedente Subsequente a b c tm 2 A 1 2 8 10 11 B 1 3 4 6 7 C 2 4 5 7 75 D 3 4 45 5 6 E 3 5 8 9 11 F 4 6 45 5 65 G 5 6 2 4 5 16 Fórmulas para cálculo da variância e desviopadrão das atividades Variância Desviopadrão Variância do planejamento Soma das variâncias das atividades do caminho crítico Fornece o grau de incerteza associado à previsão Onde a tempo otimista c tempo pessimista Roteiro para aplicar a técnica Exemplo PERT Atividade Eventos Duração D dias Antecedente Subsequente a b c tm 2 A 1 2 8 10 11 983 025 B 1 3 4 6 7 583 025 C 2 4 5 7 75 675 017 D 3 4 45 5 6 508 006 E 3 5 8 9 11 917 025 F 4 6 45 5 65 517 011 G 5 6 2 4 5 383 025 17 1 Com base no quadro monte o Diagrama ou a Rede que é a representação gráfica do projeto Roteiro para aplicar a técnica A C F B E G D 983 675 517 383 508 917 583 1 2 4 6 3 5 2 Calcule os tempos mais cedo e os represente no lado esquerdo dos eventos Faça para todos os caminhos presentes na rede Roteiro para aplicar a técnica A C F B E G D 983 675 517 383 508 917 583 1 0 2 983 4 1658 1091 2175 1608 1883 6 3 583 5 15 583 18 Roteiro para aplicar a técnica A C F B E G D 983 675 517 383 508 917 583 1 0 2 983 4 1658 1091 2175 1608 1883 6 3 583 5 15 583 3 Calcule os tempos mais tarde e os represente no lado direito dos eventos Faça para todos os caminhos presentes na rede sentido inverso dos fluxos 0 567 292 983 1658 2175 115 875 1792 1658 875 4 Selecionar os tempos mais cedo e os tempos mais tarde que serão utilizados para os cálculos das folgas Roteiro para aplicar a técnica A C F B E G D 1 2 4 6 3 5 Maior valor Menor valor 983 675 517 383 508 917 583 0 983 1658 1091 2175 1608 1883 583 15 583 0 567 292 983 1658 2175 115 1792 1658 19 Exemplo PERT Atividade D Cedo Tarde FT FL FD FI i f i f A 983 B 583 C 675 D 508 E 917 F 517 G 383 FT Dtf Dci D FL Dcf Dci D FD Dtf Dti D FI Dcf Dti D Exemplo PERT Atividade D Cedo Tarde FT FL FD FI i f i f A 983 0 983 0 983 0 0 0 0 B 583 0 583 0 875 292 0 292 0 C 675 983 1658 983 1658 0 0 0 0 D 508 583 1658 875 1658 567 567 275 275 E 917 583 15 875 1792 292 0 0 0 F 517 1658 2175 1658 2175 0 0 0 0 G 383 15 2175 1792 2175 292 292 0 0 292 FT Dtf Dci D FL Dcf Dci D FD Dtf Dti D FI Dcf Dti D 20 875 Roteiro para aplicar a técnica A C F B E G D 1 2 4 6 3 5 983 675 517 383 508 917 583 0 983 1658 1091 2175 1608 1883 583 15 583 0 567 292 983 1658 2175 115 1792 1658 5 Identifique o tempo total do projeto e o caminho crítico Tempo total do projeto 2175 dias Caminho crítico A C F Para calcular as probabilidades de realização do planejamento nos tempos prefixados é necessário calcular a variância do planejamento e o tempo esperado total do planejamento semanal Fórmula para encontrar o fator de probabilidade Z Onde Z Fator de Probabilidade TC Tempo estabelecido para conclusão do projeto TE Tempo estimado para realização do projeto Desvio padrão das atividades que foram usadas para obter o valor TE Probabilidade Probabilidade Exemplo Qual a probabilidade de esse projeto ser concluído em 23 dias Z TC TE σ 23 2175 172 09573 9573 Áreas da distribuição Normal Padrão Áreas da distribuição Normal Padrão continuação 23 Bibliografia Básica ARENALES M ARMENTANO V MORABITO R YANASSE H H Pesquisa Operacional para cursos de engenharia Rio de Janeiro Campos 2006 HILLIER F S LIEBERMAN G J Introdução à Pesquisa Operacional São Paulo McGrawHill 2006 TAHA H A Pesquisa Operacional uma visão geral São Paulo Pearson Prentice Hall 2008 Bibliografia adicional TUBINO D F Planejamento e controle da produção teoria e prática São Paulo Atlas 2007 Bibliografia Complementar ANDRADE E L Introdução à Pesquisa Operacional Métodos e Modelos para Análise de Decisões Rio de Janeiro LTC 2004 COLIN E C Pesquisa Operacional 170 aplicações em Estratégia Finanças Logística Produção Marketing e Vendas Rio de Janeiro LTC 2007 LACHTERMACHER G Pesquisa operacional na tomada de decisões Rio de Janeiro Campus 2007 MOREIRA D A Pesquisa Operacional Curso Introdutório São Paulo Thomson Learning 2007 PRADO D Teoria das Filas e da Simulação 3ª ed Editora INDG Tecnologia e Serviços Ltda 2006