Matéria P2

Prévia do material em texto

UNIVERSIDADE FEDERAL FLUMINENSE 
ESCOLA DE ENGENHARIA 
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO 
 
 
 
 
 
 
APOSTILA 
PESQUISA OPERACIONAL II 
(Matéria P2) 
 
 
 
 
 
 
 
PROFESSOR: LUIS TORRES 
MONITOR: ANDREW DE JESUS 
 
 
 
 
 
 
 
 
NITERÓI - RJ 
PERÍODO 2013.2
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
1 
 
 
Sumário 
 
1. Projeto Redes: PERT – CPM ................................................................................ 2 
1.1 Definição: ................................................................................................... 2 
1.2 Montar uma Rede: ..................................................................................... 3 
1.3 Calcular a Duração da Rede: ..................................................................... 4 
1.4 Construção da Tabela Caminho Crítico: .................................................... 6 
2. CPM .................................................................................................................... 10 
2.1 Definição: ................................................................................................. 10 
2.2 Acelerar o Projeto: ................................................................................... 12 
3. Programação Não Linear: ................................................................................... 14 
3.1 Definição: ................................................................................................. 14 
3.2 Método de Resolução: ............................................................................. 14 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
2 
 
 
 
 
 
1. Projeto Redes: PERT – CPM 
1.1 Definição: 
 
Um projeto tem como ser entendido como um grupo de operações 
regidas numa certa sequência para se chegar a um objetivo. As operações que 
ocorrem num projeto, gastando tempo e recursos, são denominadas de atividades. 
Para representar estas atividades e o posicionamento em que são realizadas, é usado 
o esquema de redes. 
Nas redes, para cada atividade existe um início e um fim. As atividades são 
representadas por setas e os eventos, que são o respectivo início e fim de cada 
atividade, são ilustrados por círculos, que também são chamados de nós. A seta 
estará saindo da atividade que é início e chegando a uma que é o fim, desta forma, 
faz-se a analogia de uma progressão no tempo. As atividades são representadas 
letras e os círculos são numerados, em ordem crescente, da esquerda para a direita. 
Um exemplo prático do uso de redes pode ser a na tarefa de realizar almoço: 
ATIVIDADE IDENTIFICAÇÃO 
ATIVIDADE 
ANTERIOR 
Resolver fazer o Almoço A - 
Comprar ingredientes para o prato do dia B A 
Elaborar lista de convidados C A 
Preparar o almoço D B 
Ligar para convidados E C 
Arrumar mesa F D 
Receber convidados G E,F 
Servir o almoço H G 
 
Segue abaixo um possível modelo de rede para essa: 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
3 
 
 
Numa rede, é chamado de caminho a qualquer conjunto de atividades, 
que leve do nó inicial até o nó final. Nesse exemplo, temos os possíveis 
caminhos: 
Caminho M: (1, 2), (2, 3), (3, 5), (5,6), (6,7) e (7,8) e outro caminho, 
 Caminho N: (1,2), (2,4), (4,6), (6,7) e (7,8) 
A duração de um caminho é a soma das durações de cada uma das 
atividades que compõem esse caminho. Na rede, o caminho com o tempo de 
duração maior é conhecido como caminho crítico e domina o tempo de término 
do projeto, pois o tempo de duração de um projeto é igual ao tempo que seu 
caminho crítico tem. Qualquer atraso que ocorrer no caminho crítico, 
automaticamente determinará um atraso no tempo global do projeto. Cada 
atividade do caminho crítico é denominada de atividade crítica. De forma 
alguma essas atividades podem atrasar, porque se ocorrer um atraso na 
mesma, o projeto por consequência vai atrasar. Em pesquisa operacional, as 
atividades críticas, tem a característica de não possuírem folga, isto é, sua 
folga é zero. Nos caminhos que não são críticos, suas atividades podem sofrer 
algum atraso sem que isso implique, em primeira instância, no atraso do 
projeto. Mas se a mesma atrasar demasiadamente pode sim alterar o tempo 
total do projeto. 
1.2 Montar uma Rede: 
 
Antes de calcularmos o tempo global da rede e de sabermos qual é o caminho 
crítico, é necessário, primeiramente montá-la. 
O procedimento é respeitar a sequência de cada atividade e lembrando que as 
linhas que ligam as atividades (caminhos) podem ser em qualquer direção. 
Segue um exemplo de rede com suas respectivas atividades, de forma que se 
organizem respeitando a ordem em que ocorrem. 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
4 
 
“A” -> é a atividade inicial do projeto; 
“B”, “C”, “D” -> começam depois que a atividade “A” terminar; 
“E” -> Começa depois que as atividades “B” e “C”terminarem; 
“F” -> Começa depois de “C” terminar; 
“G” -> Começa depois que “D” e “F” terminarem; 
“H” -> Começa depois que “E” e “G” terminarem. Sendo “H” a atividade final. 
 
Basta colocar os eventos (círculos numerados) ligados pelas atividades, seguindo 
a ordem em que são planejadas. 
Segue a ilustração da rede descrita acima: 
 
 
 
De cada nó deve sair apenas um caminho, quando ocorre de saírem 2 (duas) 
atividades de um evento, um deles deverá ser “fantasma”, isto é, não atrasa o 
processo, é uma atividade que não consome custo ou tempo. 
Observação: Nunca devemos colocar uma atividade dentro do nó, apenas 
números ficam no nó. 
1.3 Calcular a Duração da Rede: 
 
Após montar a rede, é necessário calcular a duração de seu caminho crítico, o qual 
determinará o tempo global do projeto. Segue a rede construída acima com os tempos 
de suas respectivas atividades. 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
5 
 
Agora teremos que calcular o valor de cada nós, o método usado é o mesmo que 
empregamos para achar o valor do nó na realização do “CAMINHO MAIS CURTO”, só 
que ao invés de escolhermos a menor soma dentre as atividades que chegam em 
cada nó, vamos escolher no caso de redes, a soma de atividades que der o maior 
valor. 
O valor máximo será representado por En, onde “n” é o número do respectivo nó 
de onde sai a atividade. Segue abaixo a rede com o respectivo valor máximo de cada 
nó: 
 
Temos aqui o valor máximo de cada nó. Com isso, o valor do último nó, em nosso 
exemplo, o nó 7 (sete), é o tempo total do projeto, que é 41 unidades de tempo. 
Observação: Temos do nó 3 (três) para o nó 4 (quatro), o mesmo valor, pois como foi 
mencionado anteriormente, a atividade fantasma não possui tempo, ou seja, sua 
duração é 0 (zero). 
Agora faremos o processo inverso. Iremos do fim até o início. Pegando o valor do 
último nó e diminuindo da sua atividade antecessora e colocando esse valor no nó 
anterior. Será realizado até o primeiro nó. A esse valor representamos por Ln, onde “n” 
é o número do respectivo nó de onde contamos o valor da atividade. Segue abaixo a 
execução dessa etapa. 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
6 
 
O caminho crítico será aquele em que o En e o Ln tiverem o mesmo valor. Para 
essa rede o caminho crítico é o representado pela linha em vermelho abaixo.Isso mostra que o caminho crítico não pode atrasar senão atrasa o tempo global 
do projeto. Entretanto, as atividades “B”, “D” e “E” possuem folga, pois não fazem 
parte do caminho crítico. 
1.4 Construção da Tabela Caminho Crítico: 
 
Existe outra forma de encontrar o caminho crítico sem ser pelo método mostrado 
acima. É através da construção da tabela caminho crítico. Logo abaixo, existem alguns 
termos que é importante conhecer para a elaboração da tabela. 
ES:Tempo de início mais cedo da atividade; 
EF: Tempo de término mais cedo da atividade; 
LS: Tempo de início mais tarde da atividade; 
LF: Tempo de término mais tarde; 
TF: Folga total (não atrapalha o tempo global do projeto); 
FF: Folga livre (não atrapalha a atividade seguinte); 
Exemplo: 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
7 
 
 
Na primeira coluna iremos colocar as respectivas atividades, sempre colocando em 
ordem o número das atividades de acordo com a ordem crescente das letras dos nós. 
 
 
 
Na segunda coluna, colocamos o tempo de cada atividade de acordo com a rede. 
 
Para preencher a coluna ES, olhamos na rede qual é o tempo máximo que o 
primeiro número (nó) do par ordenado pode receber do nó anterior, por exemplo, o par 
ordenado (1,2) o máximo que o nó 1 (um) pode receber do nó anterior é zero, pois ele 
é o nó inicial, não há outro nó antes dele. Nos pares ordenados iniciados com o 2 
(dois), os nós (2,4), (2,3) e (2,5), o maior valor de chegada para o nós 2 (dois) é 
quatro. E fazemos assim sucessivamente. 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
8 
 
 
Encontramos o EF somando o Tempo com o ES, ou seja, EF = Tempo + ES. 
 
Agora para determinarmos as outras colunas, iremos para a última linha e o valor 
do último EF, será o mesmo valor do último LF. E o respectivo LS será obtido 
subtraindo o Tempo do LF, isto é, último LS = último LF – Tempo. 
 
Então preencheremos tanto a coluna do LF quanto do LS, analisando a tabela do 
fim para o início. Olharemos agora para o segundo número do par ordenado, por 
exemplo nos casos (4,6) e (5,6), o segundo número é o 6 (seis). Veremos, nesse 
número qual é o LS mínimo do par ordenado onde esse número é o primeiro número 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
9 
 
no par ordenado abaixo. No caso do (4,6) e (5,6) teremos que ver, nas outras 
atividades onde o 6 (seis) é o primeiro número no par ordenado. Temos somente um 
par ordenado onde o 6 (seis) é primeiro que é o par (6,7). O seu LS é 33 (trinta e 
três). Esse valor do LS será o respectivo LF das atividades (4,6) e (5,6). O LS deles 
será obtido com a subtração do LF pelo Tempo da respectiva atividade. 
 
Repetimos o processo para as linhas de cima, sempre indo do fim para o início. 
 
Para encontrar o TF é simples, ele será igual ao subtração do LF pelo EF ou pela 
subtração do LS pelo ES, isto é, TF = LF – EF ou TF = LS – ES. 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
10 
 
Os valores onde o TF é igual a 0 (zero), termos o caminho crítico. Perceba que 
é o mesmo caminho crítico encontrado para o valor anterior. 
 
Para calcular o FF começaremos do início para o fim. Pegamos a atividade (n,m) e as 
próximas atividades que começam com “m”, ou seja, (m,k), pegamos o ES da 
atividade (m,k), diminuímos pelo ES da atividade (n,m) e diminuímos pelo tempo da 
atividade (n,m). Esse resultado dará o valor de FF da atividade (n,m). 
 
2. CPM 
2.1 Definição: 
 
É quando queremos analisar não só a duração de uma atividade, mas também o 
seu custo. Nessa etapa o objetivo principal é ver a viabilidade de reduzir o tempo de 
um projeto por meio de um aumento de custos. Cada atividade possui um tempo pré-
determinado para ser realizada, no entanto, em muitos casos, por meio de um 
investimento em determinada atividade, é possível reduzir esse tempo. Como feito em 
outros casos, irá ser colocado abaixo um exemplo para facilitar o entendimento desse 
conceito. 
Seja a rede abaixo com seus respectivos tempos de execução de cada atividade. 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
11 
 
 
Em CPM estaremos preocupados no caminho mais longo, isto é, onde a soma das 
atividades é maior. Nessa rede o caminho mais longo é dado por (1,2) e (2,5), cuja 
soma é dezoito. Esse caminho mais longo é representado por seguimentos com 
tracejados mais fortes. Aqui usaremos vermelho para ficar mais claro o entendimento. 
 
Agora veremos, para esse projeto, uma tabela que revela o tempo e o custo do 
projeto se for realizado no tempo previsto, como também o seu tempo e custo caso 
desejarmos acelerar algumas ou todas as atividades. Segue a tabela para esse projeto 
e suas respectivas atividades. 
 
 A primeira coluna “Atividade” representa cada atividade da rede; 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
12 
 
 A segunda e terceira colunas se referem, respectivamente, à duração e ao 
custo da atividade se a mesma for realizada normalmente, ou seja, se for 
executada com o mesmo tempo do planejamento inicial. 
 A quarta e a quinta colunas dizem a respeito de quanto tempo conseguimos 
reduzir a duração de cada atividade, assim como o custo envolvendo essa 
aceleração. 
 A última coluna menciona sobre quanto custa para se acelerar a duração de 1 
(uma) atividade. Por exemplo a atividade (1,2) tem duração inicial de 8 (oito) 
unidades de tempo e custo de 100 (cem) unidades monetárias. É possível 
reduzir para 6 (seis) unidades do tempo e reduzindo essas duas atividades ele 
custará 200 unidades monetárias. Isto significa que para reduzir 2 (dois) dias 
custou 100 unidades monetárias a mais, portanto, reduzir em 1 (um) a duração 
custará 50 unidades monetárias. Em termos matemáticos, pegue o tempo 
normal e subtraia pelo tempo acelerado e divida esse resultado pela diferença 
do custo acelerado pelo custo normal, assim encontrará a declividade de todas 
as atividades. 
Por meio desta tabela conseguimos saber em quanto tempo conseguimos reduzir 
a duração do projeto, como também quanto teremos que desembolsar em unidades 
monetárias para obter esse objetivo. 
Por exemplo, o custo desse projeto sem haver acelerações é 580 (quinhentos e 
oitenta) unidades monetárias. Mas podemos ir acelerando atividade por atividade e 
assim reduzir o tempo global do projeto e vendo quanto irá nos custar. 
2.2 Acelerar o Projeto: 
 
Para acelerar o projeto existem algumas regras. Não adianta ir acelerando 
qualquer atividade, pois dependendo da atividade que for escolhida, esta pode não 
reduzir o tempo total do projeto. 
Tempos que reduzir as atividades que fazerem parte do caminho mais longo, 
reduzindo estas, estaremos garantindo que o tempo geral do projeto irá se reduzir. 
OBS: É claro que estaremos pressupondo que não haverá atrasos nas atividades, 
todas serão executadas no prazo planejado. 
Dentre as atividades que formam o caminho mais longo devemos reduzir aquelas 
com menor declividade, isto é, as que custam mais “barato” por dia de redução, pois 
como engenheiros de produção queremos sempre reduzir o tempo e custo o máximo 
possível. Então entre reduzir em 1 (uma) a duração, vamos ver qual custa menos. 
Cuidado, pois quando reduzirmos as atividades o caminho mais longo pode ser 
alterado, logo, esteja atendo para não reduzir uma atividade que não implicará em 
redução no tempo global. 
 
ApostilaPesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
13 
 
Para esse estudo, vamos utilizar o exemplo utilizado no item anterior e iremos 
colocar na própria rede seus tempos normal e acelerado,como também os custos 
normal e acelerado. 
 
Para reduzir a duração iremos escolher sempre o caminho mais longo (caminho 
crítico) e vamos escolher, dentre as atividades do caminho crítico qual tem a menor 
declividade. Após isto, iremos “recalcular” o caminho mais longo e seu novo custo. 
Depois verificamos se temos condições financeiras de reduzir mais ainda o tempo, 
se tivermos, repetiremos o processo novamente até chegar a uma duração 
interessante que estabeleça uma relação custo benefício para a empresa. 
Temos ciência que o projeto acima possui duração de 18 (dezoito) unidades de 
tempo e custo de 580 (quinhentos e oitenta) unidades monetárias. Segue abaixo uma 
tabela com algumas reduções efetuadas: 
 
OBS: Na última linha da tabela tivemos que reduzir duas atividades, pois ambas, 
eram o caminho crítico, as duas demoravam 12 (doze) unidades de tempo, então só 
era possível reduzir o tempo total do projeto se reduzíssemos ambas. Por 
conseguinte, o custo é a soma da declividade das duas atividades. 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
14 
 
3. Programação Não Linear: 
3.1 Definição: 
 
É quando queremos maximizar ou minimar equações e respectivas restrições que 
são não lineares. Por exemplo: 
A equação: 3 + 4 é uma equação linear, entretanto, a equação x² não é linear. 
3.2 Método de Resolução: 
 
Resolver um problema de programação não linear, pode ser uma tarefa bem 
árdua, porém, em nosso curso nos atentaremos apenas a um método mais prático. 
Esse método consistem em derivar a equação dada e iguala-la a 0 (zero). 
Por exemplo, resolva o seguinte problema de programação não linear: 
Min 
 + 
 + 3 + 
S.A.: 3 + = 1 
 
Iremos resolver derivando parcialmente em função objetivo em função de cada 
variável. E para cada restrição iremos igualá-la a 0 (zero) e “criar” uma variável para 
ela. 
 
Colocando as restrições na função objetivo teremos: 
Min 
 + 
 + 3 + 3 + – 1) 
Agora basta derivar parcialmente cada variável da função objetivo. 
 
 
 = 2 + 3 + = 0 
 
 
 = 4 + 1 + = 0 
 
 
 = + – 1 = 0 
Agora temos um sistema de três incógnitas e três variáveis, basta resolver o 
sistema e pronto temos a solução.