Pesquisa Operacional - PEOP
AULA 8-9: PERT/CPM
Academia da Força Aérea
Objetivos
Verifique ao final desta aula se você é capaz de:
1-selecionar alternativas de acordo com a relação tempo/custo do projeto (An);
Roteiro da Aula
- Gabarito dos exercícios
- Exercícios de Revisão
- Exercícios Propostos
Gabarito para conferência
Montagem de Redes
Rede 1
| Atividade | Precedentes | d |
|---|---|---|
| A | - | 3 |
| B | A | 5 |
| C | A | 2 |
| D | C | 4 |
| E | B,D | 10 |
flowchart LR
1(("1
(0,0)")) -->|"A ,3"| 2(("2
(3,3)"))
linkStyle 0 stroke:red
2 -->|"B,5"| 4(("4
"))
2 -->|C,2| 3(("3
(5,5)"))
linkStyle 2 stroke:red
3 -->|"D ,4"| 4(("4
(9,9)"))
linkStyle 3 stroke:red
4 -->|"E ,10"| 5(("5
(19,19)"))
linkStyle 4 stroke:red
Rede 2
| Atividade | Precedentes | d |
|---|---|---|
| A | - | 2 |
| B | - | 8 |
| C | A,B | 3 |
| D | A,B | 5 |
| E | C,D | 4 |
| F | A | 8 |
| G | B | 2 |
| H | C,G | 4 |
| I | H | 10 |
| J | E,F,H | 5 |
continua…
Rede 2
flowchart LR
1 -->|B,8| 2
1 -->|A,2| 3
2 -.-> 4
3 -.-> 4
2 -->|G,2| 5
4 -->|C,3| 6
6 -.-> 5
6 -.-> 7
4 -->|D,5| 7
5 -->|H,4| 8
8 -.-> 9
7 -->|E,4| 9
3 -->|F,8| 9
8 --> |I,10|10
9 -->|J,5| 10
1(("1
(0,0)"))
2(("2
(8,8)"))
3(("3
(2,8)"))
4(("4
(8,8)"))
5(("5
(11,11)"))
6(("6
(11,11)"))
7(("7
(13,16)"))
8(("8
(15,15)"))
9(("9
(17,20)"))
10(("10
(25,25)"))
linkStyle 6 stroke:red
linkStyle 0 stroke:red
linkStyle 2 stroke:red
linkStyle 5 stroke:red
linkStyle 9 stroke:red
linkStyle 13 stroke:red
Rede 3
| Atividade | Precedentes | d |
|---|---|---|
| A | - | 6 |
| B | - | 8 |
| C | - | 4 |
| D | - | 18 |
| E | A,B | 8 |
| F | B | 4 |
| G | B | 5 |
| Atividade | Precedentes | d | |
|---|---|---|---|
| 8 | H | C | 10 |
| 9 | I | D | 8 |
| 10 | J | D,E,F | 12 |
| 11 | K | D,G,H | 8 |
| 12 | L | K,I,J | 16 |
| 13 | M | I | 4 |
Rede 3 - continuação
flowchart LR
1 -->|A,6| 2
1 -->|B,8| 3
1 -->|C,4| 4
1 -->|D,18| 5
2 -->|E,8| 6
3 -.-> 2
3 -->|F,4| 6
3 -->|G,5| 7
4 -->|H,10| 7
5 -.-> 6
5 -.-> 7
7 -->|K,8| 9
5 --> |I,8|8
6 -->|J,12| 9
8 -.-> 9
8 -->|M,4| 10
9 -->|L,16| 10
1(("1
(0,0)"))
2(("2
(8,10)"))
3(("3
(8,10)"))
4(("4
(4,12)"))
5(("5
(18,18)"))
6(("6
(18,18)"))
7(("7
(18,22)"))
8(("8
(26,30)"))
9(("9
(30,30)"))
10(("10
(46,46)"))
linkStyle 3 stroke:red
linkStyle 9 stroke:red
linkStyle 13 stroke:red
linkStyle 16 stroke:red
Rede 4
| Atividade | Precedentes | d |
|---|---|---|
| A | - | 10 |
| B | - | 12 |
| C | A | 6 |
| D | B | 8 |
| E | A,B | 15 |
| F | C | 6 |
| G | D | 8 |
| H | E,F | 16 |
| I | E | 8 |
| J | G | 6 |
| K | C,D | 10 |
Rede 4 - continuação
flowchart LR
1 -->|"A ,10"| 2(("2
(10,12)"))
1(("1
(0,0)")) -->|"B ,12"| 3(("3
(12,12)"))
linkStyle 1 stroke:red
4 -->|"F ,6"| 9(("9
(27,27)"))
4-.->6(("6
(20,33)"))
5-.->6
5 -->|"G ,8"| 10(("10
(28,37)"))
6 ------>|"K,10"| 11(("11"))
2 -->|"C ,6"| 4(("4
(16,21)"))
2 -.-> 7(("7
(12,12)"))
3 -.-> 7
linkStyle 9 stroke:red
3 -->|"D ,8"| 5(("5
(20,29)"))
8 -.-> 9
linkStyle 11 stroke:red
9 -->|"H,16"| 11(("11"))
linkStyle 12 stroke:red
10 -->|"J,6"| 11(("11"))
7 --->|"E ,15"| 8(("8
(27,27)"))
linkStyle 14 stroke:red
8 -->|"I,8"| 11(("11
(43,43)"))
Exercícios de revisão geral
Para resolver os exercícios consulte este formulário e a tabela da distribuição normal disponível no moodle ou ainda neste link https://edisciplinas.usp.br/mod/resource/view.php?id=3018073
\(td_{(i,j)} = T_j - C_i\) ; \(CM = \frac{C_a-C_n}{t_n-t_a}\)
\(FT_{(i,j)} = td_{(i,j)} - d_{(i,j)}\) ; \(FL_{(i,j)} = C_j - C_i - d_{(i,j)}\); \(FD_{(i,j)} = T_j - T_i - d_{(i,j)}\); \(FI_{(i,j)} = C_j - T_i - d_{(i,j)}\)
\(PDI_{(i,j)} = C_i\) ; \(PDT_{(i,j)} = PDI_{(i,j)} + d_{(i,j)}\) ; \(UDI_{(i,j)} = UDT_{(i,j)} - d_{(i,j)}\) ; \(UDT_{(i,j)} = T_j\)
\(\mu_P=\sum_{i=1}^{n}\mu_i\) ; \(\sigma_P^2=\sum_{i=1}^{n}\sigma_i^2\)
\(\mu_i= \frac{P+4\cdot M+O}{6}\) ; \(\sigma_i^2= (\frac{P-O}{6})^2\) ; \(z= (\frac{x-\mu_P}{\sigma_P})\)
Exercício extra 1
Observe a rede e monte o cronograma 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)"))
Solução
Para montar o cronograma do projeto, devemos calcular os seus marcos:
| Atv | d | Ci | Ti | Cj | Tj | PDI | PDT | UDI | UDT | FT | Tipo |
|---|---|---|---|---|---|---|---|---|---|---|---|
| A | 10 | 0 | 0 | 10 | 10 | 0 | 10 | 0 | 10 | 0 | Crítica |
| B | 12 | 0 | 0 | 12 | 13 | 0 | 12 | 1 | 13 | 1 | |
| C | 6 | 10 | 10 | 16 | 16 | 10 | 16 | 10 | 16 | 0 | Crítica |
| D | 8 | 12 | 13 | 20 | 24 | 12 | 20 | 16 | 24 | 4 | |
| E | 15 | 12 | 13 | 27 | 28 | 12 | 27 | 13 | 28 | 1 | |
| F | 6 | 16 | 16 | 22 | 22 | 16 | 22 | 16 | 22 | 0 | Crítica |
| G | 8 | 20 | 24 | 28 | 32 | 20 | 28 | 24 | 32 | 4 | |
| H | 16 | 22 | 22 | 38 | 38 | 22 | 38 | 22 | 38 | 0 | Crítica |
| I | 8 | 22 | 30 | 38 | 38 | 22 | 30 | 30 | 38 | 8 | |
| J | 6 | 28 | 32 | 38 | 38 | 28 | 34 | 32 | 38 | 4 | |
| K | 10 | 27 | 28 | 38 | 38 | 27 | 37 | 28 | 38 | 1 |
Cronograma
Exercício extra 2 (Análise)
Com base no cronograma construído, analise as consequências no prazo do projeto, considerando em separado cada uma das situações a seguir:
1- a possibilidade da atividade B iniciar no ponto 2 da linha do tempo.
2- a possibilidade da atividade G iniciar no ponto 22 da linha do tempo.
3- a possibilidade da atividade F iniciar no ponto 18 da linha do tempo.
Resposta Esperada
1- Considerando que UDI = 1, iniciar B no ponto 2 significa atrasar em 1 u.t. a UDI de B. Assim, analisando o cronograma, a atividade E terá seu cronograma atrasado em 1 u.t. e consequentemente a atividade K idem. Desse modo o cronograma estará atrasado em 1 u.t., terminando em 39.
2- Como o ponto 22 está entre \(PDI_G=20\) e \(UDI_G=24\), não haverá nenhum impacto no prazo do projeto se iniciarmos a atividade G em 22.
3- Sendo F uma atividade crítica, qualquer atraso em \(PDI=UDI=16\) impactará em atraso no prazo do projeto. No caso em questão, se iniciar em 18, sofrerá um atraso de 2 u.t., ou seja, será concluída em 24 e atrasará o início da atividade H que só poderá finalizar em 40. Desse modo o atraso no projeto será também de 2 u.t.
Exercício extra 3 (Análise)
Com base na rede do exercício extra 1, avalie a probabilidade do projeto ser completado em menos de 35 semanas, sabendo que:
| Atv | \(\mu\) | \(\sigma\) | Tipo |
|---|---|---|---|
| A | 10 | 1.0 | Crítica |
| B | 12 | 1.0 | |
| C | 6 | 1.0 | Crítica |
| D | 8 | 0.3 | |
| E | 15 | 0.3 | |
| F | 6 | 0.3 | Crítica |
| Atv | \(\mu\) | \(\sigma\) | Tipo | |
|---|---|---|---|---|
| 7 | G | 8 | 1.2 | |
| 8 | H | 16 | 0.5 | Crítica |
| 9 | I | 8 | 0.3 | |
| 10 | J | 6 | 1.0 | |
| 11 | K | 10 | 1.0 |
Resposta Esperada
Dos dados do problema deduz-se que \(\mu_P=38\) (estimativa da duração do projeto)
\(\sigma_P^2=1^2+1^2+0.3^2+0.5^2=2.34\), assim \(\sigma_P=\sqrt{2.34}=1.53\)
\(P(Duração \le 35)\) = \(P(Z \le \frac{35-38}{1.53})=P(Z \le -1.96)= 0.5 - 0.475=\) 0.025
Exercício extra 4 (Análise)
Você tem a missão de reduzir a duração do projeto para 17 dias. Diante disso, de acordo com a otimização tempo/custo, a forma correta de realizar a sua missão bem como o aumento de custo do projeto é:
flowchart LR
1(("1
")) -->|"A ,5"| 3(("3
"))
1 -->|"B ,6"| 2(("2
"))
2 --> |"D,2"| 3
2 --> |"F,2"| 5(("5
"))
2 --> |"E,1"| 4
4 --> |"H,7"| 5
3 --> |"G,6"| 5
5 --> |"I,5"| 6(("6
"))
1 --> |"C,8"| 4(("4
"))
| Atv | tn | ta | Cn | Ca |
|---|---|---|---|---|
| A | 5 | 3 | 2.0 | 2.5 |
| B | 6 | 2 | 3.0 | 4.0 |
| C | 8 | 7 | 10.0 | 11.0 |
| D | 2 | 1 | 7.0 | 9.0 |
| E | 1 | 1 | 1.0 | 1.0 |
| F | 2 | 2 | 1.5 | 1.5 |
| G | 6 | 5 | 4.0 | 5.6 |
| H | 7 | 5 | 3.5 | 4.5 |
| I | 5 | 3 | 5.0 | 5.5 |
Resposta Esperada
| Atv | tn | ta | Cn | Ca | CM |
|---|---|---|---|---|---|
| A | 5 | 3 | 2.0 | 2.5 | 0.25 |
| B | 6 | 2 | 3.0 | 4.0 | 0.25 |
| C | 8 | 7 | 10.0 | 11.0 | 1 |
| D | 2 | 1 | 7.0 | 9.0 | 2 |
| E | 1 | 1 | 1.0 | 1.0 | - |
| F | 2 | 2 | 1.5 | 1.5 | - |
| G | 6 | 5 | 4.0 | 5.6 | 1.6 |
| H | 7 | 5 | 3.5 | 4.5 | 0.5 |
| I | 5 | 3 | 5.0 | 5.5 | 0.25 |
Rede Normal: prazo de 20 dias com custo normal de R$ 37,00.
flowchart LR
1(("1
(0,0)")) -->|"A ,5"| 3(("3
(8,9)"))
1 -->|"B ,6"| 2(("2
(6,7)"))
2 --> |"D,2"| 3
2 --> |"F,2"| 5(("5
(15,15)"))
2 --> |"E,1"| 4
4 --> |"H,7"| 5
3 --> |"G,6"| 5
5 --> |"I,5"| 6(("6
(20,20)"))
1 --> |"C,8"| 4(("4
(8,8)"))
linkStyle 8 stroke:red
linkStyle 5 stroke:red
linkStyle 7 stroke:red
continua…
Resposta Esperada cont.
Rede Normal: prazo de 20 dias com custo normal de R$ 37,00.
flowchart LR
1(("1
(0,0)")) -->|"A ,5"| 3(("3
(8,9)"))
1 -->|"B ,6"| 2(("2
(6,7)"))
2 --> |"D,2"| 3
2 --> |"F,2"| 5(("5
(15,15)"))
2 --> |"E,1"| 4
4 --> |"H,7"| 5
3 --> |"G,6"| 5
5 --> |"I,5"| 6(("6
(20,20)"))
1 --> |"C,8"| 4(("4
(8,8)"))
linkStyle 8 stroke:red
linkStyle 5 stroke:red
linkStyle 7 stroke:red
Rede Acelerada: prazo de 17 dias acelerando a atividade H em 1 dia (custo adicional de R$0,50) e a atividade I em 2 dias (custo adicional de R$0,50) com custo total de R$ 38,00.
flowchart LR
1(("1
(0,0)")) -->|"A ,5"| 3(("3
(8,8)"))
1 -->|"B ,6"| 2(("2
(6,6)"))
2 --> |"D,2"| 3
2 --> |"F,2"| 5(("5
(14,14)"))
2 --> |"E,1"| 4
4 --> |"H,6"| 5
3 --> |"G,6"| 5
5 --> |"I,3"| 6(("6
(17,17)"))
1 --> |"C,8"| 4(("4
(8,8)"))
linkStyle 8 stroke:red
linkStyle 5 stroke:red
linkStyle 7 stroke:red
linkStyle 1 stroke:red
linkStyle 2 stroke:red
linkStyle 6 stroke:red
Exercício extra 5 (Análise)
Analise a Folga Independente e Livre da Atividade C.
Atenção à atividade C, note que o evento de início mais cedo é \(C_2\) e o de fim mais cedo é \(C_4\) e não \(C_3\) pois há uma atividade fantasma de codificação entre os eventos 3 e 4, ou seja, B e C são atividades paralelas e portanto iniciam e terminam nos mesmos eventos.
Seria um erro obter
\(FI_C=C_3-T_2-d=4-3-1=0\) e \(FL_C=C_3-C_2-d=4-3-1=0\), pois C pode atrasar seu início em 1 dia, sem atrasar o início de D.
As folgas corretas são portanto:
\(FI_C=C_4-T_2-d=5-3-1=1\) e \(FL_C=C_4-C_2-d=5-3-1=1\)
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:#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
Cronograma com mais de um caminho crítico
Observe a rede com 3 caminhos críticos e monte o cronograma. Obtenha a Folga Independente da atividade I.
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:#f9f,stroke:#333,stroke-width:4px
8 -.-> 9(("9
(19,27)"))
style 9 fill:#f9f,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)"))
Solução
Obtenha os marcos do projeto:
| 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
Continuação
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:#f9f,stroke:#333,stroke-width:4px
8 -.-> 9(("9
(19,27)"))
style 9 fill:#f9f,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)"))
Atenção para a Folga Independente da atividade I, observe que a mesma possue uma atividade fantasma de codificação entre os eventos 8 e 9, portanto I é uma atividade paralela à H, logo os eventos de início e fim são respectivamente 8 e 11. Assim:
\(FI_I=C_{11}-T_8-8 = 35-19-8=8\)
Prepare-se para a avaliação parcial
1- Revise os conteúdos de todas as aulas anteriores.
2- Faça seu resumo com os conceitos desenvolvidos nas aulas para melhor fixação.
3- Verifique se realizou todas as atividades e exercícios propostos.
4- Refaça os exercícios que encontrou maior dificuldade.
