Pesquisa Operacional - PEOP
AULA 10: PERT/CPM
Academia da Força Aérea
Objetivos
Verifique ao final desta aula se você é capaz de:
1-analisar contextos envolvendo PERT/CPM;
Roteiro da Aula
- Exercícios de Revisão
Rede 1 - Ajustes
Observe com base na rede abaixo sobre a atividade C que: \(FI=C_j-T_i-d=4-3-1=0\) e \(FL=C_j-C_i-d=4-3-1=0\), são ambas nulas, o que não corresponde à realidade.
flowchart LR
1(("1
(0,0)")) -->|"A ,3"| 2(("2
(3,3)"))
linkStyle 0 stroke:red
2 -->|"B,2"| 4(("4
(5,5)"))
linkStyle 1 stroke:red
2 -->|C,1| 3(("3
(4,5)"))
3 -.->|"0"| 4
4 -->|"D ,10"| 5(("5
(15,15)"))
linkStyle 4 stroke:red
flowchart LR
1(("1
(0,0)")) -->|"A ,3"| 2(("2
(3,3)"))
linkStyle 0 stroke:red
2 -->|"B,2"| 4(("4
(5,5)"))
linkStyle 1 stroke:red
2 -->|C,1| 3(("3
(5,5)"))
style 3 fill:#f9f,stroke:#333,stroke-width:4px
style 4 fill:#f9f,stroke:#333,stroke-width:4px
3 -.->|"0"| 4
4 -->|"D ,10"| 5(("5
(15,15)"))
linkStyle 4 stroke:red
Observe que a atividade fantasma (3,4) é de codificação e que na verdade os eventos 3 e 4 são os mesmos, portanto o início e o fim devem ter os mesmos valores. Usando esse raciocínio, ajustamos os cedos e tardes de ambos os eventos como sendo os mesmos valores. Consequentemente, haverá um ajuste no cálculo da FI e FL da atividade C, cujos valores serão respectivamente 1 e 1, o que reflete melhor a realidade do projeto.
| Atividade | Precedentes | tn | Ci | Ti | Cj | Tj | FT | FD | FI | FL |
|---|---|---|---|---|---|---|---|---|---|---|
| A | - | 3 | 0 | 0 | 3 | 3 | 0 | 0 | 0 | 0 |
| B | A | 2 | 3 | 3 | 5 | 5 | 0 | 0 | 0 | 0 |
| C | A | 1 | 3 | 3 | 5 | 5 | 1 | 1 | 1 | 1 |
| D | B,D | 10 | 5 | 5 | 15 | 15 | 0 | 0 | 0 | 0 |
Rede 1 - Representações Possíveis
Mais de uma forma de representar a rede. Observe que a segunda e quarta rede representam adequadamente a realidade do projeto pois as folgas da atividade C são adequadamente obtidas com base nestas duas redes. Note que o cronograma do projeto será o mesmo para qualquer das redes abaixo.
flowchart LR
1(("1
(0,0)")) -->|"A ,3"| 2(("2
(3,3)"))
linkStyle 0 stroke:red
2 -->|"B,2"| 4(("4
(5,5)"))
linkStyle 1 stroke:red
2 -->|C,1| 3(("3
(4,5)"))
style 3 fill:#bbf,stroke:#f66,stroke-width:2px,color:#fff,stroke-dasharray: 5 5
3 -.->|"0"| 4
4 -->|"D ,10"| 5(("5
(15,15)"))
linkStyle 4 stroke:red
flowchart LR
1(("1
(0,0)")) -->|"A ,3"| 2(("2
(3,3)"))
linkStyle 0 stroke:red
2 -->|"B,2"| 4(("4
(5,5)"))
linkStyle 1 stroke:red
2 -->|C,1| 3(("3
(5,5)"))
style 3 fill:#f9f,stroke:#333,stroke-width:4px
style 4 fill:#f9f,stroke:#333,stroke-width:4px
3 -.->|"0"| 4
4 -->|"D ,10"| 5(("5
(15,15)"))
linkStyle 4 stroke:red
flowchart LR
1(("1
(0,0)")) -->|"A ,3"| 2(("2
(3,3)"))
linkStyle 0 stroke:red
2 -->|"B,2"| 4(("4
(5,5)"))
linkStyle 1 stroke:red
3 -->|C,1| 4
2 -.->|"0"| 3(("3
(3,4)"))
style 3 fill:#bbf,stroke:#f66,stroke-width:2px,color:#fff,stroke-dasharray: 5 5
4 -->|"D ,10"| 5(("5
(15,15)"))
linkStyle 4 stroke:red
flowchart LR
1(("1
(0,0)")) -->|"A ,3"| 2(("2
(3,3)"))
linkStyle 0 stroke:red
2 -->|"B,2"| 4(("4
(5,5)"))
linkStyle 1 stroke:red
3 -->|C,1| 4
2 -.->|"0"| 3(("3
(3,3)"))
4 -->|"D ,10"| 5(("5
(15,15)"))
linkStyle 4 stroke:red
style 3 fill:#f9f,stroke:#333,stroke-width:4px
style 4 fill:#f9f,stroke:#333,stroke-width:4px
Rede 2
Observe a rede abaixo e proponha ajustes para melhor representar a realidade do projeto.
flowchart LR
O(("1
(0,0)")) -->|A,1| A(("2
(1,1)"))
linkStyle 0 stroke:red
A -->|"B ,2"| B(("3
(3,3)"))
linkStyle 1 stroke:red
B -->|"C ,4"| C(("4
(7,8)"))
A -->|"D ,3"| D(("5
(4,6)"))
B -->|"E ,5"| F(("6
(8,8)"))
linkStyle 4 stroke:red
D -->|"F ,2"| F(("6
(8,8)"))
F -->|"G ,4"| G(("7
(12,12)"))
G -->|"H ,1"| H(("8
(13,13)"))
linkStyle 6 stroke:red
linkStyle 7 stroke:red
C -.-> F
Rede 2 - resposta
Há uma atividade fantasma de codificação entre os eventos 4 e 6, que são os mesmos na prática. Assim o ajuste seria:
flowchart LR
O(("1
(0,0)")) -->|A,1| A(("2
(1,1)"))
linkStyle 0 stroke:red
A -->|"B ,2"| B(("3
(3,3)"))
linkStyle 1 stroke:red
B -->|"C ,4"| C(("4
(8,8)"))
style C fill:#ff0000,stroke:#333,stroke-width:4px
A -->|"D ,3"| D(("5
(4,6)"))
B -->|"E ,5"| F(("6
(8,8)"))
linkStyle 4 stroke:red
D -->|"F ,2"| F(("6
(8,8)"))
F -->|"G ,4"| G(("7
(12,12)"))
G -->|"H ,1"| H(("8
(13,13)"))
linkStyle 6 stroke:red
linkStyle 7 stroke:red
C -.-> F
style F fill:#ff0000,stroke:#333,stroke-width:4px
Note que este ajuste impactará nas folgas independente e livre somente da atividade C: considerando a rede sem ajustes \(FI_C=7-3-4=0\) e \(FL_C=7-3-4=0\). Após os ajustes \(FI_C=8-3-4=1\) e \(FL_C=8-3-4=1\)
Rede 3
Observe a rede abaixo e proponha ajustes para melhor representar a realidade do projeto.
flowchart LR
1(("1
(0,0)")) -->|A,2| 2(("2
(2,2)"))
linkStyle 0 stroke:red
2 -->|"B ,4"| 3(("3
(6,6)"))
linkStyle 1 stroke:red
3 -->|"C ,10"| 4(("4
(16,16)"))
linkStyle 2 stroke:red
4 -->|"D ,6"| 5(("5
(22,26)"))
4 -->|"E ,4"| 6(("6
(20,20)"))
linkStyle 4 stroke:red
6 -->|"F ,5"| 7(("7
(25,25)"))
linkStyle 5 stroke:red
5 -->|"G ,7"| 8(("8
(29,33)"))
6 -.->|"0"| 8(("8
(29,33)"))
8 -->|"H ,9"| 9(("9
(38,42)"))
4 -->|"I ,7"| 10(("10
(23,25)"))
10 -.->|"0"| 7(("7
(25,25)"))
7 -->|"J ,8"| 11(("11
(33,33)"))
linkStyle 11 stroke:red
9 -->|"M ,2"| 14(("14
"))
11 -->|"K ,4"| 12(("12
(37,38)"))
11 -->|"L ,5"| 13(("13
"))
linkStyle 14 stroke:red
12 -.->|"0"| 13(("13
(38,38)"))
13 -->|"N ,6"| 14(("14
(44,44)"))
linkStyle 16 stroke:red
Rede 3 - resposta
flowchart LR
1(("1
(0,0)")) -->|A,2| 2(("2
(2,2)"))
linkStyle 0 stroke:red
2 -->|"B ,4"| 3(("3
(6,6)"))
linkStyle 1 stroke:red
3 -->|"C ,10"| 4(("4
(16,16)"))
linkStyle 2 stroke:red
4 -->|"D ,6"| 5(("5
(22,26)"))
4 -->|"E ,4"| 6(("6
(20,20)"))
linkStyle 4 stroke:red
6 -->|"F ,5"| 7(("7
(25,25)"))
linkStyle 5 stroke:red
5 -->|"G ,7"| 8(("8
(29,33)"))
6 -.->|"0"| 8(("8
(29,33)"))
8 -->|"H ,9"| 9(("9
(38,42)"))
4 -->|"I ,7"| 10(("10
(23,25)"))
10 -.->|"0"| 7(("7
(25,25)"))
7 -->|"J ,8"| 11(("11
(33,33)"))
linkStyle 11 stroke:red
9 -->|"M ,2"| 14(("14
"))
11 -->|"K ,4"| 12(("12
(37,38)"))
11 -->|"L ,5"| 13(("13
"))
linkStyle 14 stroke:red
12 -.->|"0"| 13(("13
(38,38)"))
13 -->|"N ,6"| 14(("14
(44,44)"))
linkStyle 16 stroke:red
A atividade fantasma (6,8) é de interdependência e nenhum ajuste se aplica. A atividade fantasma (10,7) é desnecessária e poderia ser eliminada e a atividade fantasma (12,13) é de codificação então os eventos 12 e 13 são os mesmos na prática. A rede ajustada envolve eliminar a atividade fantasma (10,7) fazendo com que a atividade I seja (4,7), renumerar os eventos de 11 a 14 e alterar o cedo e tarde do nó 12 que se tornará 11 na rede ajustada. Veja o resultado:
flowchart LR
1(("1
(0,0)")) -->|A,2| 2(("2
(2,2)"))
linkStyle 0 stroke:red
2 -->|"B ,4"| 3(("3
(6,6)"))
linkStyle 1 stroke:red
3 -->|"C ,10"| 4(("4
(16,16)"))
linkStyle 2 stroke:red
4 -->|"D ,6"| 5(("5
(22,26)"))
4 -->|"E ,4"| 6(("6
(20,20)"))
linkStyle 4 stroke:red
6 -->|"F ,5"| 7(("7
(25,25)"))
linkStyle 5 stroke:red
5 -->|"G ,7"| 8(("8
(29,33)"))
6 -.->|"0"| 8(("8
(29,33)"))
8 -->|"H ,9"| 9(("9
(38,42)"))
4 -->|"I ,7"| 7
7 -->|"J ,8"| 10(("10
(33,33)"))
linkStyle 10 stroke:red
9 -->|"M ,2"| 13(("13
"))
10 -->|"K ,4"| 11(("11
(38,38)"))
style 11 fill:#ff0000,stroke:#333,stroke-width:4px
style 12 fill:#ff0000,stroke:#333,stroke-width:4px
10 -->|"L ,5"| 12(("12
"))
linkStyle 13 stroke:red
11 -.->|"0"| 12(("12
(38,38)"))
12 -->|"N ,6"| 13(("13
(44,44)"))
linkStyle 15 stroke:red
Rede 4
Observe a rede abaixo e proponha ajustes para melhor representar a realidade do projeto.
flowchart LR
1 -->|"A ,10"| 2(("2
(10,10)"))
linkStyle 0 stroke:red
1(("1
(0,0)")) -->|"B ,12"| 3(("3
(12,13)"))
4 -->|"F ,6"| 8(("8
(22,22)"))
linkStyle 2 stroke:red
4-.->6(("6
(27,28)"))
5-.->6
5 -->|"G ,8"| 10(("10
(28,32)"))
6 --->|"K,10"| 11(("11"))
2 -->|"C ,6"| 4(("4
(16,16)"))
linkStyle 7 stroke:red
2 -.-> 7(("7
(12,13)"))
3 -.-> 7
3 -->|"D ,8"| 5(("5
(20,24)"))
8 -.-> 9(("9
(22,30)"))
8 ---->|"H,16"| 11(("11"))
linkStyle 12 stroke:red
10 -->|"J,6"| 11(("11"))
7 --->|"E ,15"| 6
9 -->|"I,8"| 11(("11
(38,38)"))
Rede 4 - resposta
flowchart LR
1 -->|"A ,10"| 2(("2
(10,10)"))
linkStyle 0 stroke:red
1(("1
(0,0)")) -->|"B ,12"| 3(("3
(12,13)"))
4 -->|"F ,6"| 8(("8
(22,22)"))
linkStyle 2 stroke:red
4-.->6(("6
(27,28)"))
5-.->6
5 -->|"G ,8"| 10(("10
(28,32)"))
6 --->|"K,10"| 11(("11"))
2 -->|"C ,6"| 4(("4
(16,16)"))
linkStyle 7 stroke:red
2 -.-> 7(("7
(12,13)"))
3 -.-> 7
3 -->|"D ,8"| 5(("5
(20,24)"))
8 -.-> 9(("9
(22,30)"))
8 ---->|"H,16"| 11(("11"))
linkStyle 12 stroke:red
10 -->|"J,6"| 11(("11"))
7 --->|"E ,15"| 6
9 -->|"I,8"| 11(("11
(38,38)"))
Observamos que a única atividade fantasma de codificação é (8,9) pois os eventos 8 e 9 são os mesmos. Assim cabe um ajuste no cedo e tarde do evento 9 para representar adequadamente a realidade do projeto.
flowchart LR
1 -->|"A ,10"| 2(("2
(10,10)"))
linkStyle 0 stroke:red
1(("1
(0,0)")) -->|"B ,12"| 3(("3
(12,13)"))
4 -->|"F ,6"| 8(("8
(22,22)"))
linkStyle 2 stroke:red
4-.->6(("6
(27,28)"))
5-.->6
5 -->|"G ,8"| 10(("10
(28,32)"))
6 --->|"K,10"| 11(("11"))
2 -->|"C ,6"| 4(("4
(16,16)"))
linkStyle 7 stroke:red
2 -.-> 7(("7
(12,13)"))
3 -.-> 7
3 -->|"D ,8"| 5(("5
(20,24)"))
style 8 fill:#ff0000,stroke:#333,stroke-width:4px
8 -.-> 9(("9
(22,22)"))
style 9 fill:#ff0000,stroke:#333,stroke-width:4px
8 ---->|"H,16"| 11(("11"))
linkStyle 12 stroke:red
10 -->|"J,6"| 11(("11"))
7 --->|"E ,15"| 6
9 -->|"I,8"| 11(("11
(38,38)"))
Rede 5
Observe a rede abaixo e responda:
1- O que acontece com o prazo do projeto se a atividade I iniciar no tempo 30.
2- Quanto é possível atrasar a atividade E sem comprometer o início mais cedo de suas atividades sucessoras?
3- Considerando o início da atividade A com atraso de 5 u.t., qual o impacto no cronograma do projeto?
4- Considerando que todas as atividades deste projeto possuem o mesmo custo marginal e que só podem ser aceleradas em 1 u.t., quais atividades devem ser aceleradas para que o projeto seja executado em 35 u.t.?
flowchart LR
1 -->|"A ,10"| 2(("2
(10,10)"))
linkStyle 0 stroke:red
1(("1
(0,0)")) -->|"B ,12"| 3(("3
(12,13)"))
4 -->|"F ,6"| 8(("8
(22,22)"))
linkStyle 2 stroke:red
4-.->6(("6
(26,27)"))
5-.->6
5 -->|"G ,8"| 10(("10
(28,29)"))
6 --->|"K,9"| 11(("11"))
2 -->|"C ,6"| 4(("4
(16,16)"))
linkStyle 7 stroke:red
2 -.-> 7(("7
(12,13)"))
3 -.-> 7
3 -->|"D ,8"| 5(("5
(20,21)"))
style 8 fill:#ff0000,stroke:#333,stroke-width:4px
8 -.-> 9(("9
(22,22)"))
style 9 fill:#ff0000,stroke:#333,stroke-width:4px
8 ---->|"H,16"| 11(("11"))
linkStyle 12 stroke:red
10 -->|"J,7"| 11(("11"))
7 --->|"E ,14"| 6
9 -->|"I,8"| 11(("11
(38,38)"))
Rede 5 - resposta
1- O que acontece com o prazo do projeto se a atividade I iniciar no tempo 30.
Não causará nenhuma alteração no prazo pois UDI = 30.
2- Quanto é possível atrasar a atividade E sem comprometer o início mais cedo de suas atividades sucessoras?
Devemos analisar FI e FL pois estas são as folgas que impactam diretamente no início mais cedo das atividades sucessoras. \(FI_E=27-13-15=-1\), ou seja NÃO há folga para que a atividade inicie no tempo 13 sem impactar o início mais cedo das sucessoras. \(FL_E=27-12-15=0\), ou seja, NÃO é possível atrasar a atividade E sem comprometer o ínicio previsto das sucessoras.
3- Considerando o início da atividade A com atraso de 5 u.t., qual o impacto no cronograma do projeto?
Se uma atividade crítica for atrasada em 5 unidades de tempo, o impacto no cronograma afetará todas as atividades sucessoras: C, E, F, H, I e K. No caso em questão afetará diretamente as sucessoras do caminho crítico, aumentando o prazo do projeto em 5.u.t.
Resposta continuação
4- Considerando que todas as atividades deste projeto possuem o mesmo custo marginal e que só podem ser aceleradas em 1 u.t., quais atividades devem ser aceleradas para que o projeto seja executado em 35 u.t.?
A solução não é única, uma resposta possível é:
Aplicando o algoritmo de otimização tempo/custo, no passo 1 poderá selecionar qualquer uma das atividades críticas pois todas possuem mesmo CM.
Escolhendo reduzir 1 u.t. de A, reduz o projeto para 37 semanas. As atividades críticas serão A(9)-C(6)-F(6)-H(16). Volta para o passo 1.
Escolhendo reduzir 1 u.t. de C, reduz o tempo do projeto para 36 semanas. As atividades críticas serão A(9)-C(5)-F(6)-H(16).Volta para o passo 1.
Escolhendo reduzir 1 u.t. de F, reduz o tempo do projeto para 35 semanas como desejado. As atividades críticas serão A(9)-C(5)-F(5)-H(16); B(12)-E(14)-K(9) e B(12)-D(8)-G(8)-J(7). Todas as atividades que foram aceleradas (A, C e F) estão no caminho crítico, logo não é possível desacelerá-las.
Assim resulta que para realizar o projeto em 35 semanas devemos acelerar A, C e F em 1 u.t. com aumento de 3 u.m. ao custo normal do projeto previsto originalmente para 38 u.t.
Outras soluções possíveis seria acelerar A, C e H ou A, F e H ou ainda C, F e H!
flowchart LR
1 -->|"A ,9"| 2(("2
(9,9)"))
linkStyle 0 stroke:red
1(("1
(0,0)")) -->|"B ,12"| 3(("3
(12,12)"))
linkStyle 1 stroke:red
4 -->|"F ,5"| 8(("8
(19,19)"))
linkStyle 2 stroke:red
4-.->6(("6
(26,26)"))
5-.->6
5 -->|"G ,8"| 10(("10
(28,28)"))
linkStyle 5 stroke:red
6 --->|"K,9"| 11(("11"))
linkStyle 6 stroke:red
2 -->|"C ,5"| 4(("4
(14,14)"))
linkStyle 7 stroke:red
2 -.-> 7(("7
(12,12)"))
3 -.-> 7
linkStyle 9 stroke:red
3 -->|"D ,8"| 5(("5
(20,20)"))
linkStyle 10 stroke:red
style 8 fill:#ff0000,stroke:#333,stroke-width:4px
8 -.-> 9(("9
(19,19)"))
style 9 fill:#ff0000,stroke:#333,stroke-width:4px
8 ---->|"H,16"| 11(("11"))
linkStyle 12 stroke:red
10 -->|"J,7"| 11(("11"))
linkStyle 13 stroke:red
7 --->|"E ,14"| 6
linkStyle 14 stroke:red
9 -->|"I,8"| 11(("11
(35,35)"))
Cronograma com mais de um caminho crítico
flowchart LR
1 -->|"A ,9"| 2(("2
(9,9)"))
linkStyle 0 stroke:red
1(("1
(0,0)")) -->|"B ,12"| 3(("3
(12,12)"))
linkStyle 1 stroke:red
4 -->|"F ,5"| 8(("8
(19,19)"))
linkStyle 2 stroke:red
4-.->6(("6
(26,26)"))
5-.->6
5 -->|"G ,8"| 10(("10
(28,28)"))
linkStyle 5 stroke:red
6 --->|"K,9"| 11(("11"))
linkStyle 6 stroke:red
2 -->|"C ,5"| 4(("4
(14,14)"))
linkStyle 7 stroke:red
2 -.-> 7(("7
(12,12)"))
3 -.-> 7
linkStyle 9 stroke:red
3 -->|"D ,8"| 5(("5
(20,20)"))
linkStyle 10 stroke:red
style 8 fill:#ff0000,stroke:#333,stroke-width:4px
8 -.-> 9(("9
(19,19)"))
style 9 fill:#ff0000,stroke:#333,stroke-width:4px
8 ---->|"H,16"| 11(("11"))
linkStyle 12 stroke:red
10 -->|"J,7"| 11(("11"))
linkStyle 13 stroke:red
7 --->|"E ,14"| 6
linkStyle 14 stroke:red
9 -->|"I,8"| 11(("11
(35,35)"))
| Atv | PDI | PDT | UDI | UDT | Tipo | Caminho |
|---|---|---|---|---|---|---|
| A | 0 | 9 | 0 | 9 | Crítica | 1 |
| B | 0 | 12 | 0 | 12 | Crítica | 2 |
| C | 9 | 14 | 9 | 14 | Crítica | 1 |
| D | 12 | 20 | 12 | 20 | Crítica | 3 |
| E | 12 | 26 | 12 | 26 | Crítica | 2 |
| F | 14 | 19 | 14 | 19 | Crítica | 1 |
| G | 20 | 28 | 20 | 28 | Crítica | 3 |
| H | 19 | 35 | 19 | 35 | Crítica | 1 |
| I | 19 | 27 | 27 | 35 | 0 | |
| J | 28 | 35 | 28 | 35 | Crítica | 3 |
| K | 26 | 35 | 26 | 35 | Crítica | 2 |
Continuação
