Upload
internet
View
104
Download
0
Embed Size (px)
Citation preview
Otimização em RedesProf. Bruno Samways dos [email protected]
Pesquisa Operacional II
Introdução
1 – Problema de Fluxo Máximo2 – Problema da Árvore de Expansão Mínima3 – Problema do Caminho Mais Curto4 – Problema de Fluxo de Custo Mínimo5 – Redes PERT/CPM
Pesquisa Operacional II
Redes para Projeto
•Os projetos são conjuntos de atividades inter-relacionadas, sendo que cada atividade consome tempo e recursos
•O objetivo do Pert - Program evaluation and review technique e do CPM – Critical Path Method é fornecer meios analíticos para programar as atividades
•De que modo isso é feito?
Pesquisa Operacional II
Redes para Projeto
1
3
2
4
5
6
1) Os nós são apenas elos de ligação
EC
A
B
4
G
D
H
2
5
3
4 F
1
2
4
2) Os ARCOS são as atividades e os seus tempos de duração
Pesquisa Operacional II
Representação com atividade fictícia
B
2
3
A
1
2
3
A
3
2
B
C
C
5
5
Arco fictício com duração ZERO
Pesquisa Operacional II
Atividades do projeto
Planejamento - Fases
Rede do projeto
Cálculo da rede
Programação Temporal (Gantt)
Pesquisa Operacional II
Atividades do Projeto – Produção de um livroATIVIDADE PREDECES
SORA(S)DURAÇÃO
(SEMANAS)
A: Revisão do manuscrito pela editora --- 3
B: Preparação de páginas de amostra --- 2
C: Projeto gráfico da capa do livro --- 4
D: Preparação da arte-final --- 3
E: Aprovação do autor para o manuscrito editado e pág. amostra
A, B 2
F: Diagramação do livro E 4
G: revisão das provas diagramadas pelo autor
F 2
H: Revisão da arte-final pelo autor D 1
I: Produção dos clichês G, H 2
J: Produção e encadernação do livro C, I 4
Pesquisa Operacional II
Rede Resultante
2
1
5
3 4
7
8 9
6
AB
D
C
E F
G
I
H
J
2
2
3
2 2
2
1
4
3
4
Pesquisa Operacional II
Pert - CPM
•A Técnica de revisão e avaliação de programa – Pert, considera as durações das atividades de modo PROBABILÍSTICO
•Já o Método do Caminho Crítico – CPM, considera as durações DETERMINÍSTICAS
Pesquisa Operacional II
CPM – Critical Path Method•É um método utilizado para se calcular o
prazo do projeto e o seu CAMINHO CRÍTICO•CAMINHO CRÍTICO é a sequência de
atividades que não podem sair do cronograma estipulado, incluindo a data de início, duração e término de cada atividade
•A atividade crítica não tem nenhuma “folga” na determinação de seus tempos de início e conclusão
Pesquisa Operacional II
Método
•Forward Pass: é o tempo mais CEDO de início de uma atividade.
•Backward Pass: é o tempo mais TARDE de início da atividade.
Pesquisa Operacional II
Passos
•Forward Pass•1) determine = 0 (zero) no nó 1
para indicar que o projeto começa no tempo zero;
•2) para os valores dos próximos nós, faça a soma entre o nós predecessores e as respectivas atividades, rotulando o nó atual com o MAIOR resultado entre as somas;
•3) repita o passo 2) até o último nó. O valor do nó final é o prazo final do projeto.
Pesquisa Operacional II
1
2
3
4
56
B
A
C
E
F
H
D
G
6
5
3
2
8
1
12
11
0
5 13
8
13
25
A duração do projeto é de 25 dias!
Pesquisa Operacional II
Passos• Backward Pass• 1) determine = 25 no nó 6 para indicar
que o projeto finaliza no dia 25;• 2) para os valores dos próximos nós, faça a
subtração entre os nós predecessores (do caminho inverso) e as respectivas atividades, rotulando o nó atual com o MENOR resultado proveniente das subtrações;
• 3) repita o passo 2) até o nó de início. O valor do nó inicial deve ser 0 (zero), indicando que suas contas estão certas.
Pesquisa Operacional II
1
2
3
4
56
B
A
C
E
F
H
D
G
6
5
3
2
8
1
12
11
0
5 13
8
13
25
25
13
13
11
5
0
Pesquisa Operacional II
Caminho crítico
•O caminho crítico vai incluir os nós que tiverem os mesmos valores calculados nos passos forward pass e backward pass
XX=
Pesquisa Operacional II
1
2
3
4
56
B
A
C
E
F
H
D
G
6
5
3
2
8
1
12
11
0
5 13
8
13
25
25
13
13
11
5
0
Pesquisa Operacional II
Exercício IMPORTANTE
1 432 6
7
119
5
8
10
A B C E
D
I 12
13
14
GH
K
F
LJ
M
N
2 4 1
6
79
5
7
3
64
58
4