PESQUISA OPERACIONAL
- OTIMIZAÇÃO COMBINATÓRIA
PROBLEMAS
DE
OTIMIZAÇÃO
Prof. Angelo Augusto Frozza, M.Sc.
EM
REDES
ROTEIRO

Esta aula tem por base o Capítulo 6 do livro de
Taha (2008):

Otimização em Redes

CPM e PERT
OTIMIZAÇÃO EM REDES

Definições

Rede

Conjunto de nós conectados por arcos (ramos).

Uma rede é descrita pela notação (N, A), sendo N o conjunto
de nós e A o conjunto de arcos.

P.ex.:
N = {1, 2, 3, 4, 5}
A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5)}
OTIMIZAÇÃO EM REDES

Definições
OTIMIZAÇÃO EM REDES

Definições

Rede

Associado com cada rede está um fluxo
 P.ex.: fluxo de produtos de petróleo em uma tubulação ou
fluxo de automóveis em rodovias;

O fluxo em uma rede é limitado pela capacidade de seus
arcos, que pode ser finita ou infinita.
OTIMIZAÇÃO EM REDES

Definições

Rede

Um arco é orientado (ou dirigido) se ele permitir fluxo
positivo em uma direção e fluxo zero na direção oposta;

Uma rede orientada é aquela na qual todos os arcos são
orientados;

Um caminho é uma sequência de arcos distintos que ligam
dois nós passando por outros nós, independente da direção
de fluxo em cada arco;

Um caminho forma um ciclo (ou loop) se conectar um nó a si
mesmo, passando por outros nós;
OTIMIZAÇÃO EM REDES

Definições

Rede

Uma rede conectada é uma rede tal que todos os pares de
nós estão ligados por no mínimo um caminho;

Uma árvore é uma rede conectada sem ciclos, formada por
um subconjunto de todos os nós;

Uma árvore geradora é uma árvore que liga todos os nós da
rede;
OTIMIZAÇÃO EM REDES

Exemplos

Projetos de rede de tubulação em geral (petróleo, água
fluídos industriais etc.);

Determinação do caminho mais curto (trajetos);

Determinação da capacidade máxima de tubulações;

Determinação de cronograma de um projeto;

E muitos outros....
OTIMIZAÇÃO EM REDES

Algoritmos de otimização em redes

Árvore geradora mínima

Algoritmo do caminho mas curto

Algoritmo do fluxo máximo

Algoritmo de caminho crítico (COM – Critical Path
Method)

Algoritmo capacitado de rede de custo mínimo
CPM E PERT

CPM – Critical Path Method ou Método do caminho
crítico

PERT – Program Evaluation and Review Technique
ou Técnica de Revisão e Avaliação de Programa
São métodos baseados em rede, desenvolvidos para
auxiliar no planejamento, na programação e no controle
de projetos.
CPM E PERT

Um projeto é definido como um conjunto de atividades
inter-relacionadas, sendo que cada atividade consome
tempo e recursos;

O objetivo do CPM e do PERT é fornecer meios
analíticos para programar as atividades;
CPM E PERT

Em primeiro lugar, se definem as atividades do projeto, suas
relações de precedência e seus requisitos de tempo;

Em seguida, as relações de precedência entre as atividades
deverão ser representadas por uma rede;

A terceira etapa envolve cálculos específicos para desenvolver uma
programação temporal para o projeto;

Durante a execução do projeto, pode ser que as coisas não ocorram
conforme o planejado, assim como algumas atividades podem ser
adiantadas ou atrasadas;
 Quando isso ocorre, a programação deve ser revisada para
refletir a realidade.
CPM E PERT

PERT e CPM são técnicas independentes;

CPM


Considera durações determinísticas para as atividades;
PERT

Considera durações probabilísticas;
CPM E PERT

Representação em rede

Cada atividade do projeto é representada por um arco que
aponta na direção do desenvolvimento de um projeto;

Os nós da rede estabelecem as relações de precedência entre
as diferentes atividades;
CPM E PERT

Representação em rede

As três regras para construir a rede:

Regra 1: Cada atividade é representada por um, e somente um, arco;

Regra 2: Cada atividade deve ser identificada por dois nós finais
distintos;

Regra 3: Para manter as relações corretas de precedência, é preciso
responder às seguintes perguntas quando cada atividade for
adicionada à rede:
a)
Quais atividades devem preceder imediatamente a atividade
atual?
b)
Quais atividades devem vir após a atividade atual?
c)
Quais atividades devem ocorrer concorrentemente com a
atividade atual?
CPM E PERT

Representação em rede

Regra 2: Cada atividade deve ser identificada por dois nós finais
distintos;
Uma atividade fictícia pode ser usada para representar duas
atividades concorrentes, A e B;
 Por definição, uma atividade fictícia é representada por um arco
tracejado e não consome nem tempo nem recursos;
 São usadas para fornecer nós finais exclusivos para as atividades e
satisfazer a regra 2;

CPM E PERT

Representação em rede

Regra 2: Cada atividade deve ser identificada por dois nós finais
distintos;
Uma atividade fictícia pode ser usada para representar duas
atividades concorrentes, A e B;
 Por definição, uma atividade fictícia é representada por um arco
tracejado e não consome nem tempo nem recursos;
 São usadas para fornecer nós finais exclusivos para as atividades e
satisfazer a regra 2;

CPM E PERT

Representação em rede

As três regras para construir a rede:

Regra 3: Para manter as relações corretas de precedência, é preciso
responder às seguintes perguntas quando cada atividade for
adicionada à rede:
a)
Quais atividades devem preceder imediatamente a atividade
atual?
b)
Quais atividades devem vir após a atividade atual?
c)
Quais atividades devem ocorrer concorrentemente com a
atividade atual?
CPM E PERT

Representação em rede

As respostas para as perguntas da Regra 3 podem exigir a
utilização de atividades fictícias para garantir as precedências
corretas entre as atividades.

Por exemplo:

Considere o seguinte segmento de um projeto:
1.
A atividade C começa imediatamente após a conclusão de A e B;
2.
A atividade E só começa após a conclusão de B.
CPM E PERT

Representação em rede

Faça os exercícios sobre representação de redes.
Conjunto 6.5A do livro
 Problema número 1
 Problema número 6
 Problema número 8

CPM E PERT

Cálculos do caminho crítico

O resultado final do COM é a construção da programação
temporal para o projeto;
CPM E PERT

Cálculos do caminho crítico

Para atingir esse objetivo de modo conveniente, executamos
cálculos especiais para produzir as seguintes informações:
1.
Duração total necessária para concluir o projeto;
2.
Classificação das atividades do projeto como críticas e não críticas;

Uma atividade é crítica se não houver nenhum “espaço de
manobra”, ou folga, na determinação de seus tempos de início e
conclusão;

Uma atividade não crítica permite certa folga na programação, de
modo que o tempo de início da atividade pode ser adiantado ou
atrasado dentro de limites sem que afete a conclusão do projeto
como um todo.
CPM E PERT

Cálculos do caminho crítico

Para fazer todos os cálculos necessários, define-se um evento
como o ponto no tempo em que as atividades são concluídas e
outras iniciadas;

Em termos de rede, um evento corresponde a um nó;

Defina-se:
= tempo mais cedo da ocorrência do evento j
 j = tempo mais tarde da ocorrência do evento j
 Dij = duração da atividade (i, j)

j
CPM E PERT

Cálculos do caminho crítico

As definições do tempo mais cedo e do tempo mais tarde da
ocorrência do evento j são especificadas em relação às datas
de início e conclusão do projeto inteiro;

Os cálculos do caminho crítico envolvem dois passos:
Primeiro: o cálculo no sentido nó inicial - nó final do projeto,
denominado forward pass, que determina os tempos mais cedo de
ocorrência dos eventos
 Segundo: o cálculo no sentido nó final – nó inicial, denominado
backward pass, que determina os tempos mais tarde de ocorrência
dos eventos;

CPM E PERT

Cálculos do caminho crítico

Forward pass (tempos mais cedo de ocorrência, )

Os cálculos começam no nó 1 e continuam recursivamente até o nó
final n;

Etapa inicial: determine
tempo 0;

Etapa geral: dado que os nós p, q, ...., e v são ligados diretamente ao
no j por atividades de entrada (p, j), (q, j), ..., e (v, j), e que os tempos
de ocorrência mais cedo dos eventos (nós) p, q, ..., e v já foram
calculados, a ocorrência mais cedo do evento j é calculada como:
, = max {
1
p
= 0 para indicar que o projeto começa no
+ Dpj,
q
+ Dqj, ...,
v
+ Dvj}
O forward pass vai estar concluído quando n no nó n tiver sido
calculado.
 j representa o caminho (duração) mais longo até o nó j.

CPM E PERT

Cálculos do caminho crítico

Backard pass (tempos mais tarde de ocorrência, )



Após a conclusão do forward pass, os cálculos do backward pass
começam no nó n e terminam no nó 1;
Etapa inicial: determine n = n para indicar que os tempos mais cedo
e mais tarde da ocorrência do último nó do projeto serão os mesmos;
Etapa geral: dado que os nós p, q, ...., e v são ligados diretamente ao
no j por atividades de entrada (j, p), (j, q), ..., e (j, v), e que os tempos
mais tarde de ocorrência dos nós p, q, ..., e v já foram calculados, a
ocorrência mais tarde do nó j é calculada como:
, = min {p - Djp, q - Djq, ..., v - Djv}
O backard pass vai estar concluído quando 1 no nó 1 for calculado.
 1 = 1 (= 0)

CPM E PERT

Cálculos do caminho crítico

Com base nos cálculos precedentes, uma atividade (i, j) será
crítica se satisfazer três condições:
1.
2.
3.
i = i
j = j
j - i =
j
-
i
= Dij
As três condições declaram que os tempos mais cedo e mais
tarde da ocorrência dos nós finais i e j são iguais, e que a
duração Dij se ajusta “rigidamente” ao espaço de tempo
especificado.
 Portanto, uma atividade que não satisfaça as três condições é
não crítica.
 Por definição, as atividades críticas de uma rede devem
constituir um caminho ininterrupto que abranja toda a rede, do
início ao fim.

CPM E PERT

Exercício
CPM E PERT

Exercícios

Faça os exercícios sobre representação de redes.
Conjunto 6.5B do livro
 Problema número 1
 Problema número 2
 Problema número 3

CPM E PERT

O que você pode aprofundar no estudo de CPM:

Para saber mais sobre resolver problemas de COM, procure
estudar também:
Regras para construção da programação temporal
 Formulação do problema de CPM em Programação Linear


Estes dois tópicos são cobertos pelo livro de TAHA (2008).
CPM E PERT

O que mais você pode aprofundar

A diferença entre CPM e PERT é que no PERT, a duração de
uma atividade se baseia em três estimativas:
Tempo otimista, a, que ocorre quando a execução vai muitíssimo
bem;
 Tempo mais provável, m, que ocorre quando a execução transcorre
sob condições normais;
 Tempo pessimista, b, que ocorre quando a execução vai muitíssimo
mal.


Dê uma olhada no livro de TAHA (2008) sobre como resolver
problemas de PERT.
REFERÊNCIAS BIBLIOGRÁFICAS

TAHA, H. A. Pesquisa Operacional. 8. ed. São
Paulo: Pearson, 2008.