Pesquisa Operacional - PEOP

AULA 5: PERT/CPM

Profa. Luciane Alcoforado / Profa. Renata

Academia da Força Aérea

Objetivos

Verifique ao final desta aula se você é capaz de:

1- elaborar a rede de um projeto (Ap); 2- realizar a programação do projeto (Ap); 3- elaborar o cronograma do projeto (Ap);4- calcular a incerteza na programação do projeto (Ap); 5- analisar a incerteza na programação do projeto (An)

Roteiro da Aula

  • Gabarito dos exercícios
  • Programação/cronograma do projeto
  • Incertezas na Programação de um projeto
  • Discussões
  • Exercícios Propostos

Gabarito para conferência

Exercício 1

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"| 11(("10
    (33,33)"))
    linkStyle 10 stroke:red
    9 -->|"M ,2"| 14(("13
    "))
    11 -->|"K ,4"| 12(("11
    (38,38)"))
    11 -->|"L ,5"| 13(("12
    "))
    linkStyle 13 stroke:red
    12 -.->|"0"| 13(("12
    (38,38)"))
    13 -->|"N ,6"| 14(("13
    (44,44)"))
    linkStyle 15 stroke:red

Fórmulas: \(td_{ij}=T_j-C_i\)

\(FT_{ij}=td_{ij}-d_{ij}\);

\(FD_{ij}=T_j-T_i-d_{ij}\);

\(FI_{ij}=C_j-T_i-d_{ij}\);

\(FL_{ij}=C_j-C_i-d_{ij}\)

Tabela de Folgas - exercício 1

Atividade Tipo Duracao Ci Ti Cj Tj FT FD FI FL
A Critica 2 0 0 2 2 0 0 0 0
B Critica 4 2 2 6 6 0 0 0 0
C Critica 10 6 6 16 16 0 0 0 0
D NaoCritica 6 16 16 22 26 4 4 0 0
E Critica 4 16 16 20 20 0 0 0 0
F Critica 5 20 20 25 25 0 0 0 0
G NaoCritica 7 22 26 29 33 4 0 -4 0
H NaoCritica 9 29 33 38 42 4 0 -4 0
I NaoCritica 7 16 16 25 25 2 2 2 2
J Critica 8 25 25 33 33 0 0 0 0

continua…

Tabela de Folgas - exercício 1 cont.

Atividade Tipo Duracao Ci Ti Cj Tj FT FD FI FL
11 K NaoCritica 4 33 33 38 38 1 1 1 1
12 L Critica 5 33 33 38 38 0 0 0 0
13 M NaoCritica 2 38 42 44 44 4 0 0 4
14 N Critica 6 38 38 44 44 0 0 0 0

Analisando as folgas das atividades não críticas, recomenda-se priorizar nesta ordem as atividades K, I, G, H, M e D, observando que G e H possuem FI < 0 e devem ser aceleradas para evitar possível atraso no tempo de início mais cedo das atividades sucessoras.

Gabarito para conferência

Exercício 2

flowchart LR
1 -->|"C ,2"| 4(("4
    "))
     4 -->|"H,3"| 5(("5
    "))
     1(("1
    (0,0)")) -->|A,3| 2(("2
    (3,3)"))
    linkStyle 2 stroke:red
    2 -->|"D ,4"| 3(("3
    (7,7)"))
    linkStyle 3 stroke:red
    2 -->|"E ,2"| 4(("4
    (5,8)"))
    2 -->|"F ,7"| 5(("5
    (11,11)"))  
    1 -->|"B ,6"| 3(("3
    (7,7)"))
    3 -->|"G,4"| 5(("5
    (11,11)"))
    linkStyle 7 stroke:red

Fórmulas:

\(FT_{ij}=T_j-C_i-d_{ij}\); \(FD_{ij}=T_j-T_i-d_{ij}\); \(FI_{ij}=C_j-T_i-d_{ij}\); \(FL_{ij}=C_j-C_i-d_{ij}\)

\(PDI_{ij}=C_i\); \(PDT_{ij}=C_i+d_{ij}\); \(UDI_{ij}=T_j - d_{ij}\); - \(UDT_{ij}=T_j\)

Tabela das Folgas exercício 2

Atividade Duracao Ci Ti Cj Tj FT FD FI FL PDI PDT UDI UDT
A 3 0 0 3 3 0 0 0 0 0 3 0 3
B 6 0 0 7 7 1 1 1 1 0 6 1 7
C 2 0 0 5 8 6 6 3 3 0 2 6 8
D 4 3 3 7 7 0 0 0 0 3 7 3 7
E 2 3 3 5 8 3 3 0 0 3 5 6 8
F 7 3 3 11 11 1 1 1 1 3 10 4 11
G 4 7 7 11 11 0 0 0 0 7 11 7 11
H 3 5 8 11 11 3 0 0 3 5 8 8 11

Analisando as folgas das atividades não críticas, recomenda-se priorizar nesta ordem as atividades B,F, H, E e C.

Gabarito para conferência

Exercício 3

Fórmulas:

\(FT_{ij}=T_j-C_i-d_{ij}\); \(FD_{ij}=T_j-T_i-d_{ij}\); \(FI_{ij}=C_j-T_i-d_{ij}\); \(FL_{ij}=C_j-C_i-d_{ij}\)

\(PDI_{ij}=C_i\); \(PDT_{ij}=C_i+d_{ij}\); \(UDI_{ij}=T_j - d_{ij}\); \(UDT_{ij}=T_j\)

flowchart LR
 1(("1
    (0,0)")) -->|A,3| 2(("2
    (3,3)"))
     linkStyle 0 stroke:red
    2 -->|"B ,2"| 3(("3
    (6,6)"))
 2 -->|"C ,3"| 4(("4
    (6,6)"))
     linkStyle 2 stroke:red
    4 -.->|"0"| 3(("3
    (6,6)"))
     linkStyle 3 stroke:red
     4 -->|"E,3"| 5(("5
    "))
     4 -->|"H,2"| 6(("6
    "))
     3 -->|"F,5"| 6(("6
    "))
     3 -->|"D,7"| 5(("5
    (13,13)"))
     linkStyle 7 stroke:red
     5 -->|"G,6"| 6(("6
    (19,19)"))
     linkStyle 8 stroke:red

Tabela das Folgas exercício 3

Atividade Tipo Duracao Ci Ti Cj Tj FT FD FI FL
A Critica 3 0 0 3 3 0 0 0 0
B NaoCritica 2 3 3 6 6 1 1 1 1
C Critica 3 3 3 6 6 0 0 0 0
D Critica 7 6 6 13 13 0 0 0 0
E NaoCritica 4 6 6 13 13 3 3 3 3
F NaoCritica 5 6 6 19 19 8 8 8 8
G Critica 6 13 13 19 19 0 0 0 0
H NaoCritica 2 6 6 19 19 11 11 11 11

Recomenda-se priorizar nesta ordem as atividades B, E, F e H.

Recorde: Marcos do Projeto

\(PDI_{ij}=C_i\) é a Primeira Data de Início da atividade \((ij)\), definida como a primeira oportunidade de iniciar uma atividade \((ij)\).

\(PDT_{ij}=C_i+d_{ij}\) é a Primeira Data de Término da atividade \((ij)\), é a primeira oportunidade de concluir uma atividade.

\(UDI_{ij}=T_j - d_{ij}\) é a Última Data de Início da atividade \((ij)\), definida como a última oportunidade de iniciar uma atividade a fim de que não ocorram atrasos nas atividades subsequentes.

\(UDT_{ij}=T_j\) é a Última Data de Término da atividade \((ij)\), definida como a última oportunidade de terminar uma atividade a fim de que não haja atrasos nas atividades subsequentes.

Recorde exemplo anterior

A seguir recorde o exercício 3 da aula 4.

Exercício 3

Com base na rede de projeto, calcule seus marcos, ou seja, PDI, PDT, UDI, UDT de cada atividade.

  • \(PDI_{ij}=C_i\);
  • \(PDT_{ij}=C_i+d_{ij}\);
  • \(UDI_{ij}=T_j - d_{ij}\);
  • \(UDT_{ij}=T_j\)

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"| 11(("10
    (33,33)"))
    linkStyle 10 stroke:red
    9 -->|"M ,2"| 14(("13
    "))
    11 -->|"K ,4"| 12(("11
    (38,38)"))
    11 -->|"L ,5"| 13(("12
    "))
    linkStyle 13 stroke:red
    12 -.->|"0"| 13(("12
    (38,38)"))
    13 -->|"N ,6"| 14(("13
    (44,44)"))
    linkStyle 15 stroke:red

Resposta

Atividade Tipo Duracao PDI PDT UDI UDT
A Critica 2 0 2 0 2
B Critica 4 2 6 2 6
C Critica 10 6 16 6 16
D NaoCritica 6 16 22 20 26
E Critica 4 16 20 16 20
F Critica 5 20 25 20 25
G NaoCritica 7 22 29 26 33

continua…

Resposta cont.

Atividade Tipo Duracao PDI PDT UDI UDT
8 H NaoCritica 9 29 38 33 42
9 I NaoCritica 7 16 23 18 25
10 J Critica 8 25 33 25 33
11 K NaoCritica 4 33 37 34 38
12 L Critica 5 33 38 33 38
13 M NaoCritica 6 38 40 42 44
14 N Critica 2 38 44 38 44

Cronograma

Para montar o cronograma do projeto da rede com duração de 44 semanas, iniciamos desenhando a linha do tempo anotando os marcos do projeto. A primeira linha (em vermelho) representará a sequência de atividades críticas: A (0 a 2)-B (2 a 6)-C (6 a 16)-E (16 a 20)-F (20 a 25) -J (25 a 33)-L (33 a 38) -N (38 a 44).

Cronograma (continuação)

As atividades não críticas são representadas no cronograma através de três linhas azuis, sendo uma linha pontilhada representando o tempo disponível para a atividade e duas linhas contínuas representando a duração da atividade, uma com início na PDI e outra com início na UDI.

Observe que a linha pontilhada azul da atividade G inicia em 22 e termina em 33, esse é o tempo disponível para realizar a tarefa G. A linha contínua de 22 (PDI) a 29 (PDT) indica o mais cedo que a atividade pode iniciar e terminar, e a a linha de 26 (UDI) a 33 (UDT) indica o mais tarde que a atividade pode iniciar e terminar. Note que o tamanho das linhas contínuas representam a duração da atividade, que neste caso é de 7 semanas.

Cronograma (continuação)

Incluir as atividades não-críticas no cronograma, indicando as primeiras datas de início (PDI) e última data de término (UDT) unidas por linhas tracejadas horizontais, indicando que estas atividades poderão ter sua execução programada dentro deste intervalo, sem que haja prejuízo nas relações de precedência. Inclui-se ainda mais 2 linhas contínuas de comprimento proporcional à duração da atividade, iniciando cada uma na PDI e UDI.

Cronograma Final

Resumo

Os marcos do projeto são pontos importantes do cronograma para controle dos prazos de cada atividade.

São eles:

\(PDI_{ij}=C_i\) é a Primeira Data de Início da atividade \((ij)\).

\(PDT_{ij}=C_i+d_{ij}\) é a Primeira Data de Término da atividade \((ij)\).

\(UDI_{ij}=T_j - d_{ij}\) é a Última Data de Início da atividade \((ij)\).

\(UDT_{ij}=T_j\) é a Última Data de Término da atividade \((ij)\).

Nas atividades críticas \(PDI=UDI\) e \(PDT=UDT\).

Incertezas na Programação de um Projeto

A duração de cada atividade, na prática, pode ser diferente daquela prevista na elaboração do projeto.

Muitos fatores praticamente impossíveis de serem previstos podem adiantar ou atrasar a duração de uma atividade. Exemplo, escassez ou abundância de recursos, intempéries climáticas, entre tantos outros.

A metodologia PERT supõe a independência entre a duração das atividades e utiliza 3 diferentes tipos de estimativas para seu valor para determinar os parâmetros da distribuição de probabilidade: Otimista, Mais Provável e Pessimista.

Parâmetros a serem calculados

Para cada atividade (i,j) podemos calcular a duração média \(\mu_{ij}\) e a variância \(\sigma_{ij}^2\) da seguinte forma:

\(\mu_{ij} = \frac{O_{ij}+4M_{ij}+P_{ij}}{6}\)

\(\sigma_{ij}^2 = (\frac{P_{ij}-O_{ij}}{6})^2\)

Sendo,

\(O_{ij}\) a duração estimada da atividade no cenário otimista;

\(M_{ij}\) a duração estimada da atividade no cenário mais provável;

\(P_{ij}\) a duração estimada da atividade no cenário pessimista.

Duração estimada do projeto

A duração de um projeto é determinada pela soma das durações das atividades críticas e as “n” atividades pertencentes ao caminho crítico são consideradas independentes,

O valor esperado para o tempo de duração do projeto \(\mu_{P}\) bem como a sua variância \(\sigma_{P}^2\) são:

\(\mu_P=\sum_{i=1}^{n}\mu_i\) (duração estimada)

\(\sigma_P^2=\sum_{i=1}^{n}\sigma_i^2\) (variância estimada)

\(\sigma_P = \sqrt{\sigma^2}\) (desvio-padrão estimado)

Probabilidade de duração do projeto

Para o cálculo da probabilidade de duração do projeto, lança-se mão do Teorema do Limite Central e assim a distribuição normal é empregada para obter por exemplo a probabilidade da duração total do projeto ser menor do que um certo prazo:

\[P(duração \le prazo) = P(Z\le z)\] em que \(Z = \frac{prazo - \mu_P}{\sigma_P}\)

Exemplo

Considere um projeto contendo 8 atividades cujas estimativas de duração são dadas na tabela.

flowchart LR
1(("1
    ")) -->|"A1"| 2(("2
    "))
     2 -->|"A3"| 4(("4
    "))
     1 -->|A2| 3(("4
    "))
    3 -.-> 5(("5
    "))
    4-->|"A5"|6(("6
    "))
    6-->|"A8"|7
    3-->|"A6"|7
    5-->|"A7"|7(("7
    "))
    1-->|"A4"|7

Atividade Precedente O MP P
A1 - 1 1 1
A2 - 2 4 6
A3 A1 1 1 1
A4 - 3 6 9
A5 A3 1 2 3
A6 A4 3 5 7
A7 A2 1 2 3
A8 A5 4 6 8

continua…

Exemplo

1- Obtenha a estimativa de duração de cada atividade, bem como sua variância.

Use \(\mu_{ij} = \frac{O_{ij}+4M_{ij}+P_{ij}}{6}\) e \(\sigma_{ij}^2 = (\frac{P_{ij}-O_{ij}}{6})^2\)

continua…

Exemplo

1- Resposta

Atividade Precedente O MP P duracao variancia
A1 - 1 1 1 1 0.000
A2 - 2 4 6 4 0.444
A3 A1 1 1 1 1 0.000
A4 - 3 6 9 6 1.000
A5 A3 1 2 3 2 0.111
A6 A4 3 5 7 5 0.444
A7 A2 1 2 3 2 0.111
A8 A5 4 6 8 6 0.444

Exemplo

Rede

flowchart LR
1(("1
   (0,0) ")) -->|"A1, 1"| 2(("2
    (1,1)"))
     2 -->|"A3, 1"| 4(("4
     (2,2)"))
     1 -->|A2, 4| 3(("4
    (4,5)"))
    3 -.-> 5(("5
    (4,8)"))
    4-->|"A5, 2"|6(("6
    (4,4)"))
    6-->|"A8, 6"|7
    3-->|"A6, 5"|7
    5-->|"A7, 2"|7(("7
    (10,10)"))
    1-->|"A4, 6"|7
    linkStyle 0 stroke:red
    linkStyle 1 stroke:red
    linkStyle 4 stroke:red
    linkStyle 5 stroke:red

2- Sabendo que o caminho crítico é formado pelas atividades A1, A3, A5 e A8, calcule a probabilidade da duração do projeto ser menor ou igual a 8 dias.

continua…

Exemplo

2- Resposta

Deseja-se \(P(Duração \le 8)\).

A estimativa da duração de cada atividade crítica é: \(\mu_{A1}=1; \mu_{A3}=1; \mu_{A5}=2; \mu_{A8}=6\)

A estimativa da variância destas atividades é: \(\sigma_{A1}^2=0; \sigma_{A3}^2=0; \sigma_{A5}^2=0.111; \sigma_{A8}^2=0.444\)

\(\mu_P=\sum_{i=1}^{n}\mu_i= 1+1+2+6=10\)

\(\sigma_P^2=\sum_{i=1}^{n}\sigma_i^2=0+0+0.111+0.444=0.555 \rightarrow \sigma_P=0.745\)

\[P(\mu_P \le 8) = P(Z\le z)\] em que \(z = \frac{8 - 10}{0.745}=-2.69\)

Graficamente a probabilidade desejada é a área em destaque

Tabela Normal

Consulte o valor 2.69 na tabela e anote a probabilidade correspondente, ou seja, 0.49643.

\(P(Z\le z)=P(Z\le -2.69)=0.5-0.49643=0.00357\)

Resposta

A probabilidade do projeto durar 8 semanas é de aproximadamente 0.00357 ou 0.0357%, ou seja, muito pouco provável que esse prazo máximo de 8 dias seja cumprido.

Discussões

Compartilhe suas dúvidas ou insights.

Prepare-se para a próxima aula: Revisar o conteúdo das aulas anteriores e realizar os exercícios propostos

Exercícios Propostos

Realize os exercícios a seguir.

1

O projeto apresentado na tabela a seguir, possui a seguinte rede (já construída em exercício anterior). Considerando as estimativas para o desvio-padrão, calcule a probabilidade do projeto ser completado em menos de 10 dias.

Atividades Precedente Duração (Semanas) Desvio Padrão
A - 3 0.1
B - 6 0.2
C - 2 0.8
D A 4 0.4
E A 2 0.6
F A 7 1
G B,D 4 1
H C,E 3 1

continua…

1 continuação

flowchart LR
1 -->|"C ,2"| 4(("4
    "))
     4 -->|"H,3"| 5(("5
    "))
     1(("1
    (0,0)")) -->|A,3| 2(("2
    (3,3)"))
    linkStyle 2 stroke:red
    2 -->|"D ,4"| 3(("3
    (7,7)"))
    linkStyle 3 stroke:red
    2 -->|"E ,2"| 4(("4
    (5,8)"))
    2 -->|"F ,7"| 5(("5
    (11,11)"))  
    1 -->|"B ,6"| 3(("3
    (7,7)"))
    3 -->|"G,4"| 5(("5
    (11,11)"))
    linkStyle 7 stroke:red

2

2-Calcule a probabilidade do projeto ser completado em menos de 18 dias, agora observando as estimativas da variância.

Atividades Precedente Duração (Semanas) Variância
A - 3 1
B A 2 0.6
C A 3 0.4
D B,C 7 0.1
E C 3 0.1
F B,C 5 0
G D,E 6 0
H C 2 1

continua…

2 continuação

flowchart LR
 1(("1
    (0,0)")) -->|A,3| 2(("2
    (3,3)"))
     linkStyle 0 stroke:red
    2 -->|"B ,2"| 3(("3
    (6,6)"))
 2 -->|"C ,3"| 4(("4
    (6,6)"))
     linkStyle 2 stroke:red
    4 -.->|"0"| 3(("3
    (6,6)"))
     linkStyle 3 stroke:red
     4 -->|"E,3"| 5(("5
    "))
     4 -->|"H,2"| 6(("6
    "))
     3 -->|"F,5"| 6(("6
    "))
     3 -->|"D,7"| 5(("5
    (13,13)"))
     linkStyle 7 stroke:red
     5 -->|"G,6"| 6(("6
    (19,19)"))
     linkStyle 8 stroke:red