apostila_Pesquisa_Operacional

Prévia do material em texto

UNIVERSIDADE REGIONAL DE BLUMENAU 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
PESQUISA OPERACIONAL 
 
 
 
 
 
 
 
PROF. VIVIANE C. DA SILVA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 2 
UNIVERSIDADE REGIONAL DE BLUMENAU 
DISCIPLINA: PESQUISA OPERACIONAL 
PROFESSORA: VIVIANE C. DA SILVA 
 
 
 
 
 
Os métodos da Pesquisa Operacional visam auxiliar na seleção da melhor maneira de se operar um 
sistema, usualmente sob condições que exijam a utilização de recursos limitados. 
Empresas podem ser vistas como sistemas que visam obter o maior retorno possível para as suas 
atividades, com retorno podendo significar qualidade do serviço prestado no caso de uma empresa pública, 
ou lucro financeiro no caso de uma empresa privada. Planejar as atividades de uma empresa produtora de 
bens (eletrodomésticos, equipamentos eletrônicos, automóveis,...) e de serviços (telefonia, transporte, 
energia,...) significa determinar que decisões a empresa deve tomar, eventualmente ao longo do tempo e 
sob condições de incerteza, para maximizar o seu retorno. 
Problemas práticos de planejamento podem exigir a utilização de sistemas de suporte à decisão, 
softwares destinados a apoiar o processo de tomada de decisões. Sistemas deste tipo geralmente oferecem 
opções de modelagem matemática e de métodos quantitativos para tomada de decisões compatíveis com 
os modelos adotados. Os modelos matemáticos utilizados em planejamento da produção são geralmente 
modelos de otimização, no sentido de que estes modelos prescrevem obter decisões ótimas, como mínimo 
custo ou máximo lucro de produção, por exemplo. 
Dá-se o nome de Programação Matemática ao conjunto de modelos e métodos de otimização 
utilizados em planejamento da produção, podendo o termo programação ser entendido como sinônimo de 
planejamento. 
Baseado em material elaborado pelo professor Osmar Kunen e apostila da professora Janaina Poffo Possamai. 
 
Histórico: 
 
No século XII, com o início da Revolução Industrial, começaram a surgir as primeiras preocupações 
com a maximização dos lucros, minimização dos custos e desta forma começaram a surgir as primeiras 
tentativas de modelação para interpretar a realidade. 
Em 1939, Kantovich, apresenta o trabalho “Métodos Matemáticos de Organização e Planejamento de 
Produção”, formulado na forma de um problema de Programação Linear, mas para o qual não apresenta a 
resolução. 
Somente com o início da II Guerra Mundial é que surge a Pesquisa Operacional, como ramo 
científico. Seu objetivo inicial era investigar de forma sistemática e racional os processos envolvidos na 
realização de uma atividade produtiva, mesmo que no início com finalidades bélicas. 
Hoje ela possui uma grande aplicabilidade nas áreas de administração, produção, planejamento e 
organização. 
 
 
 
PESQUISA OPERACIONAL ((OOppeerraattiioonnaall RReesseeaarrcchh)) 
 3 
DDeeffiinniiççããoo 
 
Como ciência, estrutura processos, propondo um conjunto de alternativas de ação, fazendo a 
previsão e comparação de valores, de evidência e de custos. 
 
Ou seja: 
 É um método científico de tomada de decisão 
 Ferramenta estratégica de gestão de negócios 
 Construção de Modelos Matemáticos, econômicos e estatísticos para tratar de situações de 
complexidade e incerteza. 
 Analisar as relações que determinam as conseqüências futuras prováveis de ações alternativas. 
Inferência. 
 
FFAASSEESS PPRRIINNCCIIPPAAIISS 
 
 Formulação do problema 
 
É essencial em qualquer estudo de P.O. que o problema em consideração seja claramente definido. É 
quase impossível obter uma resposta “certa” a partir de um problema “errado”. 
Devemos estabelecer bem os objetivos, os cursos alternativos de ação e o efeito do sistema em 
estudo sobre os outros sistemas a ele relacionados. 
As partes interessadas devem concordar sobre um padrão de eficiência, harmonizando-se com os 
objetivos da organização total. 
 
 Construção de um modelo que represente o sistema em estudo 
 
Após a formulação do problema, o próximo passo é construir um modelo do problema ou sistema em 
estudo. 
O modelo matemático é um conjunto de equações que descreve o sistema ou o problema, 
geralmente contém dois tipos de equações: 
 A função objetivo 
 As restrições ou limitações 
 As equações referentes à função objetivo e às restrições são compostas de variáveis controláveis e 
não controláveis. 
 
** CCoonnssttrruuççããoo DDee MMooddeellooss 
 
Essência da abordagem em P.O. 
Modelo = formulação matemática dos aspectos que circundam uma tomada de decisão 
Captar os pontos cruciais do problema 
Suficientemente livre de detalhes onerosos a implementação computacional. 
 
 
 4 
 Obtenção de solução a partir do modelo 
 
 A solução do problema obtém-se através da determinação da solução ótima para o modelo e depois 
aplicando esta solução ao problema. 
 Às vezes, a complexidade matemática do modelo torna impossível a solução ótima e deve bastar 
então uma “boa” resposta. 
 As soluções dos modelos matemáticos podem ser obtidas recorrendo-se a certas técnicas ou 
ferramentas, que será o grande conteúdo de nosso programa. 
 
 Teste do modelo e da solução dele originada 
 
- Após a solução do modelo, o modelo e a solução devem ser testados. 
- O teste da solução pode ser feito de dois modos: 
 Usando-se dados passados, comparando-se o desempenho real com o desempenho indicado pelo 
modelo. 
 Fazendo o sistema operar sem mudanças e comparando seu desempenho com o do modelo`. 
- O valor do modelo e de sua solução podem ser julgados com base nestas comparações. 
 
 Colocação da solução em funcionamento: Implantação 
 
 A implantação da solução obtida é a última fase do estudo de P.O. Nesta fase o grupo de P.O. 
explica à administração responsável pelo sistema em estudo. É importante que a explicação da 
solução seja feita em termos de métodos usados no sistema real, traduzindo a solução em um 
método facilmente inteligível. 
 Depois da aplicação da solução, deve-se observar a resposta do sistema às mudanças feitas, 
evitando desvios. 
 
 IImmppllaannttaaççããoo 
 
 O grau de apoio recebido da parte da administração determinará o sucesso de um estudo de P.O. 
Uma maneira de se conseguir este apoio é tornar a administração participante de todas as fases do 
estudo de P.O. 
 Uma excelente forma de convencer a administração dos benefícios do estudo de P.O. é 
comprovação através de uma “análise de investimento” do impacto das modificações propostas pelo 
modelo. 
 
MMOODDEELLOOSS DDEE PP..OO.. 
 
 Programação Linear 
 Transportes 
 Sequenciamento de Projetos (PERT) 
 Simulação 
 5 
BIBLIOGRAFIA: 
 
ANDRADE, Eduardo Leopoldino de. Introdução a pesquisa operacional. Rio de Janeiro: LTCE, [c1990.]. 
xxvi, 377p. 
BRONSON, Richard. Pesquisa operacional. Sao Paulo: McGraw-Hill, c1985. xi, 318p. 
CORRAR, Luiz João; THEÓPHILO, Carlos Renato. Pesquisa operacional para decisão em contabilidade 
e administração: contabilometria.2. ed. São Paulo: Atlas, 2013. 490 p, il. 
HILLIER, Frederick S; LIEBERMAN, Gerald J. Introdução à Pesquisa Operacional. 9. ed. Porto Alegre: 
AMGH, 2013. xxii, 1005 p, il. 
HIRSCHEFELD, H., Planejamento com PERT-CPM e Análise do Desempenho, 9
a
 ed., São Paulo, Atlas, 
1987. 
LACHTERMACHER, Gerson. Pesquisa operacional na tomada de decisões: modelagem em Excel. Rio 
de Janeiro: Campus, 2002. [322p.], il. 
LANZER, Edgar Augusto. Programação linear : conceitos e aplicações. Rio de Janeiro : IPEA/INPES, 
1982. 258p. 
LOESCH, Cláudio; HEIN, Nelson. Pesquisa Operacional: fundamentos e modelos. São Paulo: Saraiva, 
2009. viii, 248 p, il. , 1 CD-ROM 
MAXIMIANO, A. C. A., Administração de Projetos: Transformando idéias em Resultados. São Paulo, Editora 
Atlas, 1997. 
MOREIRA, Daniel Augusto. Pesquisa Operacional: curso introdutório. São Paulo: Thomson Learning, 
2007. 
MARINS, F. Introdução à Pesquisa Operacional.Disponível em: 
http://www.feg.unesp.br/~fmarins/po/slides/1o%20s/desig.pdf 
PRADO, D., Administração de Projetos com PERT-CPM. Belo Horizonte, Ed. UFMG, 1988. 
SILVA, Ermes Medeiros da.Pesquisa Operacional: para os cursos de administração e engenharia: 
programação linear: simulação.4. ed. São Paulo: Atlas, 2010. xiv, 186 p, il 
VIEIRA, N. L., Manual de PERT-CPM, Rio de Janeiro: CNI-SESI/DN, 1980. 
 
 
 
 
 
 
 
 
 
 
 
http://www.feg.unesp.br/~fmarins/po/slides/1o%20s/desig.pdf
 6 
 
 
 
 
A Programação Linear é uma das muitas técnicas analíticas recentemente desenvolvidas que 
têm se mostrado úteis na resolução de certos tipos de problemas empresariais. Esses métodos 
quantitativos de resolução de problemas, como muito aplicados na Pesquisa Operacional, são 
baseados em conceitos matemáticos e estatísticos. 
 
Os Modelos envolvem as funções, equações e inequações do primeiro grau. 
 
ÁREAS DE APLICAÇÃO: 
 
Os métodos de programação linear podem ser aplicados principalmente à classe geral de problemas 
conhecidos como problemas de alocação. Definidos pelos economistas como aqueles envolvidos na 
alocação de recursos escassos entre fins alternativos, de acordo com algum critério. 
Os recursos escassos para uma empresa incluem capital, pessoal, equipamento e materiais. Os 
vários produtos e/ou serviços que constituem a produção da firma representam fins alternativos aos quais 
devem ser alocados recursos. O critério ou objetivo, na base de quais decisões de alocação devem ser 
tomadas, pode ser alguma forma de maximização de lucro ou outra medida qualquer apropriada de 
performance desejada. 
Encontram-se muitos tipos de problemas de alocação nas atividades empresariais, especialmente na 
produção ou função de operações. Como exemplos em que se pode aplicar a Programação Linear, 
podemos citar: 
 Determinação dos produtos a serem fabricados (composição da produção); 
 Problemas de mistura ou composição; 
 Problemas de produção e planejamento de estoque; 
 Alimentação das máquinas; 
 Problemas de transporte e distribuição física. 
 
FFoorrmmuullaaççããoo 
 
 “Traduzir” o problema de tomada de decisão em linguagem matemática 
 Não existe um procedimento padrão 
 Captar os aspectos de relevância do problema 
 Deve-se evitar aspectos insignificantes 
 
MMeettooddoollooggiiaa BBáássiiccaa ddee FFoorrmmuullaaççããoo 
 
Variável de decisão: Identificar as variáveis controláveis ou de decisão e as não controláveis 
 
Restrições: Identificar as restrições a que são submetidas as variáveis no âmbito do problema 
 Restrições de demanda 
 Restrições de produção 
 Restrições de consumo 
Função Objetivo: Identificar os objetivos, sob os quais, se definira a solução ótima 
 Maximização de Lucro 
- Representa o lucro unitário de cada produto ou serviço 
- É fundamental um sistema de custos gerencial 
- Aplicado em qualquer atividade empresarial 
 
PROGRAMAÇÃO LINEAR 
 7 
 Minimização de Custos 
- Representa o custo unitário de cada elemento 
- Aplicável principalmente nas indústrias químicas, alimentícias e farmacêuticas 
 
 MMOODDEELLOOSS MMAATTEEMMÁÁTTIICCOOSS 
 
Diferentemente do processo de decisão baseado em métodos qualitativos, geralmente centrado na 
experiência que o tomador de decisão acumulou ao longo dos anos, decisões baseadas em métodos 
quantitativos requerem uma estruturação do problema, seguida de sua representação matemática e da 
utilização de métodos de análise apropriados. A saída produzida pelo método quantitativo adotado é então 
recomendada ao tomador de decisão. 
Os métodos qualitativos e quantitativos devem ser vistos como complementares. A experiência 
acumulada pelo tomador de decisão é importante para guiar a escolha e a utilização de métodos 
quantitativos, enquanto que a análise das decisões decorrentes do emprego de métodos quantitativos ajuda 
o tomador de decisão a aumentar sua intuição e conhecimento sobre o problema, realimentando o processo 
de tomada de decisão. 
Modelos matemáticos são usados para descrever problemas de planejamento, mas, como em outras 
áreas do conhecimento, devem ser vistos como aproximações dos problemas reais que procuram retratar. 
Para que seja útil um modelo de planejamento deve capturar os aspectos essenciais do problema, o que 
exige habilidade na tarefa de modelagem. Para se chegar a resultados significativos a partir de modelos, 
uma boa capacidade de análise e também fundamental. Habilidade e capacidade de análise podem ser 
adquiridas por meio da experiência prática e do entendimento da teoria por trás dos modelos matemáticos. 
Uma etapa importante, após escrever o modelo matemático que representa uma situação real e obter 
uma solução, e a de validação do modelo. A validação do modelo é a etapa do processo envolve verificar se 
o modelo adotado e a solução obtida por meio dele, são compatíveis com a realidade do problema. Se 
todas as características relevantes do problema tiverem sido levadas em conta na modelagem, a solução 
obtida será implementável. Caso contrário, um novo ciclo de modelagem e obtenção de solução terá de ser 
desenvolvido. A implementação de uma solução validada envolve transformar a solução, obtida a partir do 
modelo, em um conjunto de instruções na linguagem operacional usada pelos administradores do sistema. 
 
Texto extraído da apostila formulada pela professora Janaina Poffo Possamai 
 
Embora não haja uma fórmula única para a modelagem, sugere-se a seguinte metodologia: 
 
 Identificar as variáveis decisórias: aquilo que se pode controlar e que se deseja saber quanto vale. 
As variáveis devem ser claramente definidas. Se a variável usa alguma unidade de medida, deve-se 
deixar bem claro qual é esta unidade de medida. Se ela é real ou só pode assumir valores inteiros. 
 Identificar o objetivo: sempre se quer ou maximizar ou minimizar um determinado objetivo, expresso 
em função das variáveis do problema. 
 Identificar os fatores restritivos: também expressas em função das variáveis do problema, as 
restrições limitam as combinações das variáveis a determinados limites. 
 
Modelo Geral de Problemas de Programação Linear 
 
Todo problema de PL pode ser descrito através de uma função objetivo e através de um conjunto de 
restrições, todos lineares. Assim, temos o seguinte modelo genérico. 
 
 8 
{ Max, Min } Z = c1x1 + c2x2 + ... + cnxn 
sujeito a 
a11x1 + a12x2 + ... + a1nxn { =,  ,  } b1 
a21x1 + a22x2 + ... + a2nxn { =,  ,  } b2 
............................................................... 
am1x1 + am2x2 + ... + amnxn { =,  ,  } bm 
x1, x2, ..., xn  0 
 
No modelo matemático acima, deve-se interpretar: 
 x1, x2, ...,xn = conjunto de variáveis estruturais do problema; 
 c1, c2, ...,cn = coeficientes da função objetivo; 
 aij e bj = coeficientes das restrições. Os coeficientes da bi da mão direita devem necessariamente ser 
não-negativos quando o algoritmo de resolução é o Simplex. 
 
O que está entre colchetes significa “usar um dos elementos separados por vírgula”. 
A função objetivo expressa a meta que se deseja atender. Esta meta ou será de maximização (Max Z 
= ...) ou de minimização (Min Z = ...). 
As restrições expressam limites a serem respeitados. A resolução procura a solução ótima no espaço 
de soluções compatíveis ao problema de PL, ou seja, no conjunto de pontos cujas coordenadas são valores 
das variáveis que satisfazem ao conjunto de restrições. Cada restrição poderá ser uma igualdade ( = ) ou 
uma desigualdade não-estrita (  ou  ). 
As últimas restrições de não negatividade das variáveis constituem condição necessária à aplicação 
do algoritmo Simplex de resolução de problemas de PL (que será trabalhado posteriormente). Embora 
normalmente isto ocorra em decorrência da natureza da variável dentro do modelo, pode haver situações 
em que varáveis são irrestritas, isto é, podem assumir qualquer valor real.É o caso, por exemplo, onde a 
variável, em um determinado problema, representa um saldo bancário, que eventualmente pode ser 
negativo. Nestes casos, existe um artifício: substituir cada variável irrestrita pela diferença de duas outras, 
onde a restrição de não negatividade se aplica. Por exemplo, seja x3 uma variável irrestrita em um problema 
de PL. Neste caso utilizamos a substituição x3 =x3’- x3”. Assim, cada ocorrência de x3 na função objetivo e 
em cada restrição é substituída por x3’- x3”. Neste caso, x3’  0 e x3”  0. Na solução ótima, tomam-se os 
valores de x3’ e x3” e com eles calcula-se x3. Se x3’ > x3” então x3 > 0. Se x3’ < x3” então x3 < 0. 
 
Observação: Os valores de todos os coeficientes são conhecidos durante a modelagem do problema. As 
variáveis são calculadas pelo algoritmo de resolução. 
Na PL, todas as variáveis devem ser quantidades reais. No caso de um problema de planejamento da 
produção em uma indústria discreta (automobilística, por exemplo), algumas das variáveis (se não todas) 
deverão representar quantidades a serem produzidas, necessariamente quantidades inteiras. Neste caso 
será necessário, dependendo da solução encontrada, fazer um ajuste na mesma. 
 
 MMÉÉTTOODDOOSS DDEE CCÁÁLLCCUULLOO 
 
 Interpretação Gráfica 
 Solução Algébrica 
 Método Simplex 
 Solução Computacional 
 
 9 
RREESSOOLLUUÇÇÃÃOO PPEELLOO MMÉÉTTOODDOO GGRRÁÁFFIICCOO 
 
Enquanto o problema estiver restrito a apenas duas variáveis, é possível representar o problema 
graficamente. Tal método possibilita melhor visão geral do problema e torna mais fácil a interpretação de 
alguns passos e resultados. 
Cada restrição define uma área que contém um número infinito de pontos representados pela área, 
que não excede a inequação de restrição. 
A combinação destas restrições define a área aceitável ou viável da resposta. 
 
Problema Exemplo 1. Uma empresa fabrica dois tipos de produtos, feitos de madeira compensada. Cada 
produto do tipo A necessita de 5 minutos para o corte e 10 minutos para a montagem; cada produto do tipo 
B precisa de 8 minutos para o corte e 8 minutos para a montagem. Dispõe-se de 3 horas e vinte minutos 
para o corte e 4 horas para a montagem. O lucro é de $ 5,00 para cada produto do tipo A e de $ 6,00 para 
cada produto do tipo B. Suponha que toda a produção é vendida. Quantas unidades de cada produto a 
empresa deverá produzir para maximizar o lucro? (É possível vender tudo o que for produzido) 
 
Problema Exemplo 2. Dois produtos, P e Q, contém os nutrientes A, B e C nas quantidades (em mg) 
indicadas no quadro abaixo. A última coluna indica a quantidade mínima necessária de cada nutriente para 
uma alimentação sadia. A última linha indica o preço de cada produto por unidade. Que quantidade de 
cada produto deve conter uma dieta para que proporcione uma alimentação sadia com o mínimo de custo? 
 
 P Q Quantidade Mínima Necessária 
A 3 1 12 
B 3 4 30 
C 2 7 28 
Custo 3 2 
 
 
 EEXXEERRCCÍÍCCIIOOSS 
 
 
Modele os seguintes problemas e resolva pelo método gráfico (se for possível). 
 
1. Um empresário tem dois produtos que dão um excelente lucro. Ele precisa então, decidir quantas 
unidades de cada produto devem ser produzidas a fim de otimizar o seu lucro total. Cada unidade do 
produto A oferece um lucro de R$ 20,00 e cada unidade do produto B, R$ 50,00. Cada unidade do produto 
A requer 3 horas de máquina e 9 unidades de matéria-prima, enquanto o produto B requer 4 horas de 
máquina e 7 unidades de matéria-prima. Os tempos máximos disponíveis de horas de máquina e de 
matéria-prima são 200 horas e 300 unidades, respectivamente. 
a) Faça a modelagem do problema acima. 
b) Resolva utilizando o método gráfico. 
c) Analise a solução apresentada. 
 
2. Um agricultor dispõe de dois tipos de adubo. O adubo A contém 3 g de fósforo, 1 g de nitrogênio e 8 g de 
potássio, e custa 5 u.m. por quilograma. O adubo tipo B contém 2 g de fósforo, 3 g de nitrogênio e 2 g de 
potássio, e custa 4 u.m. por quilograma. A terra que o agricultor vai utilizar necessita de pelo menos 3 g de 
fósforo, 1,5 g de nitrogênio e 4 g de potássio. Quanto o agricultor deve comprar de cada adubo, de modo 
que seu custo seja mínimo? 
a) Formular a modelagem de modo a determinar a quantidade de camisas a produzir para otimizar a 
solução. 
b) Resolva pelo método gráfico e analise a solução apresentada. 
 10 
3. Uma marcenaria deseja estabelecer uma programação diária de produção. Atualmente a oficina faz 
apenas dois produtos: mesa e armário, ambos de um só modelo. Para efeito de simplificação, vamos 
considerar que a marcenaria tem limitações em somente dois recursos: madeira e mão de obra, cujas 
disponibilidades diárias são mostradas na tabela abaixo: 
Recurso Disponibilidade 
Madeira 12 m
2
 
Mão de obra 8 homens-hora 
 
O processo de produção é tal que, para fazer 1 mesa, a fábrica gasta 2 m
2
 de madeira e 2 homens-hora de 
mão de obra. Para fazer um armário, a fábrica gasta 2 m
2
 de madeira e 1 homem-hora de mão de obra. 
Além disso, o fabricante sabe que cada mesa dá um lucro de 6 u.m. e cada armário dá um lucro de 2 u.m. 
O problema do fabricante é encontrar o programa de produção que maximiza o lucro total. 
 
4. Dois produtos, P e Q, contém os nutrientes A, B e C em quantidades (em mg) indicadas no quadro 
abaixo. A última coluna indica a quantidade mínima necessária de cada nutriente para uma alimentação 
sadia. A última fila indica o preço de cada produto por unidade. Que quantidade de cada produto deve 
conter uma dieta para que proporcione uma alimentação sadia com o mínimo de custo? 
 
 P Q 
A 3 1 12 
B 3 4 30 
C 2 7 28 
 3 2 
 
5. Uma fábrica manufatura dois produtos, cada um requerendo o uso de 3 máquinas. A primeira máquina 
pode ser usada no máximo 70 horas; a Segunda máquina no máximo 40 horas e a terceira máquina, no 
máximo 90 horas. O primeiro produto requer 2 horas na máquina I, 1 hora na máquina II e 1 hora na 
máquina III. O segundo produto requer 1 hora em cada uma das máquinas I e II e 3 horas na máquina III. 
Se o preço de venda é de 40 u.m. para o primeiro produto e de 60 u.m. para o segundo produto, supondo 
que todas as unidades são vendidas, quantas unidades de cada produto deveriam ser manufaturadas para 
tornar o rendimento máximo? 
 
6. A empresa Industrial Têxtil S/A realizou no mês de julho a produção e venda de dois produtos principais: 
camiseta e conjunto. Como o lucro obtido foi muito bom a empresa deseja otimizar a venda destes 
produtos, ou seja, obter o maior lucro possível com a venda dos mesmos. 
Sabe-se que os custos fixos ficam na média de R$75000,00 e que cada camiseta custa para a indústria 
R$60,00, sendo vendida a R$100,00. Já o conjunto custa, para a indústria R$150,00 e seu preço de venda 
é de R$200,00. A demanda máxima de camisetas é de 36000 unidades e dos conjuntos é de 40000 
unidades. O setor de malharia possui 50000 horas/homem disponível, sendo que cada camiseta requer 6 e 
cada conjunto, 1. O setor de beneficiamento possui 65000 horas/homem disponível, sendo que cada 
camiseta requer 1, e cada conjunto 0,8. A confecção possui 150.000 horas/homem disponível, sendo que 
cada camiseta requer 1,5 e cada conjunto 4. Quantas unidades de cada produto devem ser vendidas para 
que o lucro seja máximo? 
 
7. Uma refinaria produz gasolina e óleo combustível. Sua matéria-prima é petróleo, que pode ser adquirido 
em três diferentes países: UM, DOIS e TRÊS. A partir de um barril de petróleo do país UM, que custa U$ 
30, a refinaria obtém 20 litros de gasolina e 40 kg de óleo combustível. A partir de um barril do país DOIS, 
que custa U$ 28, a refinaria obtém 17 litros de gasolina e 43 kg de óleo combustível. A partir de um barril 
de petróleo do barril TRÊS, que custa U$ 34, a refinaria obtém 25 litros de gasolina e 35 kg de óleo 
combustível. A gerência da refinaria assinou contratos paraentregar pelo menos 200.000 litros de gasolina 
e pelo menos 380.000 kg de óleo combustível por semana, nos próximos 2 meses. Que quantidade de 
barris deve ser adquirida de cada país de modo que a refinaria possa cumprir contratos pelo menor custo de 
matéria-prima possível? 
 11 
RREESSOOLLUUÇÇÃÃOO PPEELLOO MMÉÉTTOODDOO DDOO TTAABBLLEEAAUU SSIIMMPPLLEEXX 
 
 
Problema Exemplo 1. Uma marcenaria deseja estabelecer uma programação diária de produção. 
Atualmente a oficina faz apenas dois produtos: mesa e armário, ambos de um só modelo. Para efeito de 
simplificação, vamos considerar que a marcenaria tem limitações em somente dois recursos: madeira e mão 
de obra, cujas disponibilidades diárias são mostradas na tabela abaixo: 
 
Recurso Disponibilidade 
Madeira 12 m
2
 
Mão de obra 8 homens-hora 
 
O processo de produção é tal que, para fazer 1 mesa, a fábrica gasta 2 m
2
 de madeira e 2 homens-hora de 
mão de obra. Para fazer um armário, a fábrica gasta 2 m
2
 de madeira e 1 homem-hora de mão de obra. 
Além disso, o fabricante sabe que cada mesa dá um lucro de 6 u.m. e cada armário dá um lucro de 2 u.m. 
O problema do fabricante é encontrar o programa de produção que maximiza o lucro total. 
 
Modelagem: 
 
Variáveis: x: quantidade de mesas produzidas 
 Y: quantidade de armários produzidos 
 
Função Objetivo: Máximo lucro: L = 6x + 2y 
Restrições: Matéria prima: 2x + 2y  12 
 Mão de obra: 2x + 1y  8 
 Não negatividade: x, y  0 
 
Iniciamos com a resolução gráfica do problema para comparar com a resolução via tableau simplex. 
 
Matéria Prima: )( 1222 21  xx 
x1 x2 
0 6 * 62/121220 222  xxx 
6 0 * 62/121202 111  xxx 
 
 
Mão de Obra: )( 812 21  xx 
x1 x2 
0 8 * 880 22  xx 
4 0 * 42/8802 111  xxx 
 
 12 
CÁLCULO PARA ENCONTRAR O PONTO C. 
 
Ponto C: Cruzamento das retas das restrições. 
 
Ponto C: 





82
 1222
21
21
xx
xx
 
 
Vamos eliminar a variável x1. Para isto vamos multiplicar a segunda equação por (-1). 
Ponto C: 





1)-(. 82
 1222
21
21
xx
xx
 



 41x / 
812
1222
2
21
21
xx
xx
 
 
Substituindo o valor de x2 = 4 na segunda equação para encontrar o valor de x1. 
 
2
4
 42 482842 82 111121  xxxxxx 21 x 
 
Ponto X1 X2 L = 6.x1 + 2.x2 
A 0 0 6.0 + 2.0 = 0 
B 0 6 6.0 + 2.6 = 12 
C 2 4 6.2 + 2.4 = 20 
D 4 0 6.4 + 2.0 = 24 (*) 
 
 
Análise da Solução: Deve-se fabricar 4 mesas e nenhum armário, obtendo o lucro máximo de 24 u.m. 
Desta forma utiliza-se todo tempo disponível de mão de obra. 
 
 
RESOLUÇÃO PELO TABLEAU SIMPLEX: 
 
Para que um problema de Programação Linear possa ser resolvido temos que “arrumar” a modelagem 
escrevendo-a na FORMA PADRÃO. 
 
1. Na forma padrão as restrições não podem ser escritas na forma de inequações, mas somente como 
igualdades. Para que isto seja possível temos que somar uma variável extra em cada restrição, quando a 
restrição for de “” (ou subtrair, quando a restrição for de “”) . 
 
2. Outro cuidado que temos que ter é que, todos os valores do lado direito do sinal de igualdade devem ser 
constantes, inclusive na função objetivo. Assim todos os termos, da Função Objetivo, que tiverem variáveis 
e estiverem do lado direito da igualdade deve estar do lado esquerdo. Para isto utilizamos a operação 
inversa. 
 
Resumindo, a Forma Padrão fica: 
 
 
 
 
 
 
42 x 
 13 
COMENTÁRIOS SOBRE O MÉTODO SIMPLEX: 
 
1. A Resolução do Método Simplex é baseada em tabelas onde cada tabela representa uma solução. 
 
2. Em cada solução, teremos variáveis com valores positivos, chamadas de VARIÁVEIS BÁSICAS, e 
variáveis nulas (de valor zero), denominadas de VARIÁVEIS NÃO BÁSICAS. O número de VARIÁVEIS 
BÁSICAS é equivalente ao número de restrições do problema. 
 
3. Os valores que estão à direita do sinal de igualdade são denominados MÃO DIREITA. 
 
4. Em cada tabela: 
* Na primeira linha indicamos as variáveis do problema 
* Na primeira coluna indicamos quais são as Variáveis Básicas daquela tabela (solução) 
 
Variáveis Básicas x y f1 f2 Mão Direita 
 
 
Lucro 
 
* No corpo da primeira tabela sempre inserimos os valores que temos nas restrições e na função 
objetivo da Forma Padrão do problema. 
 
Observações: 
1. A restrição de não negatividade não entra na tabela. 
2. A solução da primeira tabela sempre indica a situação da empresa antes de iniciar a produção. Desta 
forma os valores de “x” e “y”, nesta tabela, sempre serão ZERO (variáveis não básicas). Com isto, as 
Variáveis Básicas (que devem ser indicadas na primeira coluna) são as variáveis adicionais, que indicam as 
disponibilidades. 
 
 
RESOLVENDO O PROBLEMA EXEMPLO... 
 
TABELA I: 
Variáveis Básicas x y f1 f2 Mão Direita 
 
 
Lucro 
 
Para encontrarmos a solução do problema em uma tabela do Método Simplex sempre relacionamos as 
variáveis da primeira coluna com os valores apresentados na última coluna. 
Indicar a solução apresentada na primeira tabela: 
 
 
 
 
 
 14 
COMO SABER SE ESTA NÃO É A SOLUÇÃO ÓTIMA? 
 
Enquanto, no problema de maximização, houver valores negativos na última linha (linha da função 
objetivo) o problema ainda não está na sua solução ótima. 
 
Calculando a segunda tabela... 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
TABELA II: 
Variáveis Básicas x y f1 f2 Mão Direita 
 
 
Lucro 
 
Solução: 
 
 
 
 
 
 
Problema Exemplo 2. Uma fábrica manufatura dois produtos, cada um requerendo o uso de 3 máquinas. 
A primeira máquina pode ser usada no máximo 70 horas; a Segunda máquina no máximo 40 horas e a 
terceira máquina, no máximo 90 horas. O primeiro produto requer 1 hora na máquina I, 1 hora na máquina 
II e 2 horas na máquina III. O segundo produto requer 1 hora em cada uma das máquinas I e II e 4 horas 
na máquina III. Se o preço de venda é de 40 u.m. para o primeiro produto e de 60 u.m. para o segundo 
produto, supondo que todas as unidades são vendidas, quantas unidades de cada produto devem ser 
manufaturadas para tornar a receita máxima? 
 15 
EEXXEERRCCÍÍCCIIOOSS 
 
Resolva os problemas a seguir utilizando o método do Tableau Simplex. 
 
 
1. Uma empresa decide introduzir na sua linha de produção dois novos modelos de blusas: A e B. A blusa 
A requer 2 minutos para a confecção das mangas e 8 minutos para o corpo. A blusa B requer 6 minutos 
para a confecção das mangas e 4 minutos para o corpo. As máquinas utilizadas para a confecção das 
mangas estão disponíveis 60 minutos por dia. As máquinas necessárias para a confecção dos corpos das 
blusas estão à disposição 80 minutos por dia. O lucro unitário da blusa A é de 50 u.m. e da blusa B é de 40 
u.m.. Quantas blusas de cada tipo devem ser produzidas por dia para que o lucro seja máximo? (É possível 
vender tudo o que for produzido) 
 
 
2. Uma companhia produz dois tipos de camisas: manga longa e manga curta. Na companhia, o único ponto 
crítico é um tipo de máquina especial de costura disponível, da qual se dispõe de 100 horas semanais. A 
camisa de manga longa consome 30 min enquanto que a de manga curta leva 15 min na máquina referida 
acima. O mercado limita a produção semanal de camisas em 180 mangas longas e 200 mangas curtas. O 
lucro bruto por camisa de manga longa é de 5,00 u.m. e por camisa de manga curta, 3,5 u.m. Formular a 
modelagem de modo a determinar a quantidade de camisas a produzir para otimizar a solução. Analisar a 
solução apresentada. 
 
 
3. Uma empresa decide introduzir na sua linha de produção dois novos modelos de blusas: A e B. A blusa 
A requer 2 minutos para a confecção das mangas e 8 minutos para o corpo. A blusa B requer 6 minutos 
para a confecção das mangas e 4 minutos para o corpo. As máquinas utilizadas para a confecção das 
mangas estãodisponíveis 60 minutos por dia. As máquinas necessárias para a confecção dos corpos das 
blusas estão à disposição 80 minutos por dia. O lucro unitário da blusa A é de 50 u.m. e da blusa B é de 40 
u.m.. Quantas blusas de cada tipo devem ser produzidas por dia para que o lucro seja máximo? Resolva e 
analise a solução apresentada (É possível vender tudo o que for produzido) 
 
 
4. Um agricultor dispõe de dois tipos de adubo. O adubo A contém 3 g de fósforo, 1 g de nitrogênio e 8 g de 
potássio, e custa 5 u.m. por quilograma. O adubo tipo B contém 2 g de fósforo, 3 g de nitrogênio e 2 g de 
potássio, e custa 4 u.m. por quilograma. A terra que o agricultor vai utilizar necessita de pelo menos 3 g de 
fósforo, 1,5 g de nitrogênio e 4 g de potássio. Quanto o agricultor deve comprar de cada adubo, de modo 
que seu custo seja mínimo? 
* Formular a modelagem de modo a determinar a quantidade de camisas a produzir para otimizar a solução. 
Resolva e analise a solução apresentada. 
 
 
5. Em determinada empresa, a produção de cada unidade do produto A requer 3 homens-hora de mão de 
obra e 1 KWh de energia. Cada unidade do produto B requer 2 homens-hora e 3 KWh. Existe material 
disponível para a fabricação de 600 unidades do produto A e para 800 unidades do produto B. Estão 
disponíveis 2.450 homens-hora de mão de obra e 2.100 KWh de energia. O lucro por unidade é de $60 para 
o produto A e de $90 para o produto B. Quantas unidades de cada produto devem ser produzidas para que 
a empresa obtenha o máximo lucro supondo que todas as unidades produzidas sejam vendidas? 
* Formular a modelagem de modo a determinar a quantidade de camisas a produzir para otimizar a solução. 
Resolva e analise a solução apresentada. 
 
 
 
 
 16 
RREESSOOLLUUÇÇÃÃOO PPEELLOO MMÉÉTTOODDOO DDOO TTAABBLLEEAAUU SSIIMMPPLLEEXX 
VVIIAA EEXXCCEELL 
 
 
 Todos os problemas resolvidos anteriormente podem ser resolvidos novamente utilizando o excel. 
 
Resolução de problemas que possuem restrição de ≥ e que sejam de minimização: 
 
 
1. Dois produtos, P e Q, contém os nutrientes A, B e C nas quantidades (em mg) indicadas no quadro 
abaixo. A última coluna indica a quantidade mínima necessária de cada nutriente para uma alimentação 
sadia. A última linha indica o preço de cada produto por unidade. Que quantidade de cada produto deve 
conter uma dieta para que proporcione uma alimentação sadia com o mínimo de custo? 
 
 
2. Um fazendeiro produz abacaxis e melancias. Cada hectare de abacaxi consome 5 homens/hora/dia e 
cada hectare de melancia, 3. A área mínima plantada de abacaxi deve ser de 1 hectare e a de melancia, 3 
hectares. Um hectare plantado de abacaxi rende 2.000 u.m. e de melancia, 1.400 u.m.. Sabendo que se 
dispõe de 12 hectares e de 40 homens/hora/dia, quantos hectares devem ser plantados de cada um de 
forma a maximizar o rendimento do fazendeiro. Faça a modelagem do problema acima e resolva utilizando 
o método gráfico analisando a solução apresentada e verificando como ficaram as restrições. 
 
 
3. Uma refinaria produz gasolina e óleo combustível. Sua matéria-prima é petróleo, que pode ser adquirido 
em três diferentes países: UM, DOIS e TRÊS. A partir de um barril de petróleo do país UM, que custa U$ 
30, a refinaria obtém 20 litros de gasolina e 40 kg de óleo combustível. A partir de um barril do país DOIS, 
que custa U$ 28, a refinaria obtém 17 litros de gasolina e 43 kg de óleo combustível. A partir de um barril 
de petróleo do barril TRÊS, que custa U$ 34, a refinaria obtém 25 litros de gasolina e 35 kg de óleo 
combustível. A gerência da refinaria assinou contratos para entregar pelo menos 200.000 litros de gasolina 
e pelo menos 380.000 kg de óleo combustível por semana, nos próximos 2 meses. Que quantidade de 
barris deve ser adquirida de cada país de modo que a refinaria possa cumprir contratos pelo menor custo de 
matéria-prima possível? 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 17 
MMOODDEELLAAGGEEMM DDEE PPRROOBBLLEEMMAASS MMAAIIOORREESS 
 
 
Faça a modelagem dos seguintes problemas: 
 
 
1. Uma grande fábrica de móveis dispõe de um estoque semanal de 250 metros de tábuas, 600 metros de 
pranchas e 500 metros de painéis de conglomerado. A fábrica normalmente oferece uma linha de móveis 
composta por um modelo de escrivaninha, uma mesa de reunião, um armário e uma prateleira. Cada tipo de 
móvel consome certa quantidade de matéria prima, conforme a tabela abaixo. A escrivaninha é vendida por 
R$1000,00, a mesa por R$800,00, o armário por R$1200,00 e a prateleira por R$200,00 o custo da fábrica 
com mão de obra é de R$50,00 por homem hora. Cada escrivaninha necessita de 4 homens-hora; cada 
mesa precisa de 3 homens-hora, cada armário de 5 homens-hora e cada prateleira de 1 homem-hora. Há 
disponíveis 800 homens-hora. Existe uma encomenda de 15 escrivaninhas, 15 mesas, 20 armários e 7 
prateleiras que o fabricante deve entregar no final da semana. 
 
Quantidade de material em metros consumidos por unidade de 
produto 
Disponibilidade 
Do Recurso (m) 
 Escrivaninha Mesa Armário Prateleira 
Tábua 1 1 1 4 250 
Prancha 0 1 1 2 600 
Painéis 3 2 4 0 500 
 
Pede-se exibir um modelo de Programação Linear que maximize o lucro com a venda dos móveis. 
 
 
2. Uma indústria de componentes elétricos fabrica: Disjuntor simples; Disjuntor revestido; Caixa para 
disjuntor e Caixa para centrais de telefonia. 
Os preços correntes e os respectivos custos variáveis para sua produção e venda são os seguintes: 
 
Produtos Preço de Venda Custos variáveis 
Disjuntor Simples 8,00 4,00 
Disjuntor Revestido 15,00 8,00 
Caixa para Disjuntor 40,00 22,00 
Caixa para centrais 180,00 98,00 
 
A empresa fez uma pesquisa de mercado e estima de poderá vender 6.200 unidades de disjuntores 
simples. O disjuntor revestido tem um mercado de até 2.000 unidades mensais, enquanto a caixa para 
disjuntor tem mercado de grande procura, não justificando qualquer limite. A caixa para centrais só é 
vendida para estatal de telecomunicações avisou que irá comprar no máximo 130 mensais. 
O processo de fabricação é composto de quatro setores produtivos e na tabela abaixo temos os tempos de 
produção de cada produto e os potenciais mensais de produção em hora-máquina. 
 
 Horas-máquina por unidade 
Produtos Setor A Setor B Setor C Setor D 
Disjuntor Simples 0,5 1,0 0,5 0,8 
Disjuntor Revestido 1,0 0,5 0,5 0,6 
Caixa para Disjuntor 2,0 1,2 1,0 1,5 
Caixa para Centrais 8,5 5,0 4,5 2,5 
Capac. de Produção 3200 4000 3000 2500 
 
Sabe-se ainda, que os custos e despesas fixas mensais são da ordem de R$10.000,00 mensais e que 
todas as unidades fabricadas são vendidas. 
 18 
Montar a modelagem de modo que seja possível encontrar quanto deve ser fabricado de cada produto para 
que o lucro seja máximo. 
 
 
 
3. Num processo industrial podem-se produzir três tipos de produtos, cada um dos quais necessariamente 
precisa ser trabalhado numa fresa, num torno mecânico e numa retífica. Os tempos consumidos por cada 
unidade de produto em cada máquina, assim como a receita de venda de cada unidade de produto, seguem 
a tabela abaixo. 
 
Produto 
Tempo de trabalho na máquina (em minutos) Consumo (kg) Receita 
Fresa Torno Retífica matéria prima unitária (R$) 
A 15 10 5 1,5 500 
B 10 12 8 0,8 650 
C 5 4 3 0,6 200 
 
A fresadeira possui uma disponibilidade semanal máxima de 4.800 minutos, o torno 4.000 minutos e a 
retífica 3.600 minutos. A matéria prima disponível para a próxima semana é de 480 kg. 
O custo da matéria-prima é de R$ 10,0 por kg. Os custos de produção da fresa e mão-de-obra incluída é de 
R$1,00 por minuto de trabalho, do torno é de R$1,50 e da retífica é de R$2,00. 
Deseja-se assim planejar a produção da próxima semana de forma a maximizar o lucro. 
 
 
4. A Fábrica de Rádios Sinval Vulah S.A. fabrica os modelos A, B e C que tem contribuição ao lucro de $16,$30 e $50, respectivamente. As exigências de produção mínima semanais são 20 para o modelo A, 120 
para o modelo B e 60 para o modelo C. Cada tipo de rádio requer uma certa quantidade de tempo para 
fabricação das partes componentes, para a montagem e para embalagem. Especificamente, uma dúzia de 
unidades do modelo A requer três horas para fabricar, quatro horas para montar e uma para embalar. Os 
números correspondentes para uma dúzia de unidades do modelo B são 4, 5 e 2, e para uma dúzia de 
unidades do modelo C são 5, 8 e 3. Durante a próxima semana, a fábrica tem disponíveis 120 horas de 
tempo de fabricação, 160 horas de montagem e 48 horas de embalagem. Formule o problema de 
programação de produção como um modelo de programação linear que maximize o lucro. 
 
 
5. Uma determinada fábrica produz panelas de metal médias e grandes a partir de elementos circulares de 
diâmetros de 0,25 e 0,40 metros, respectivamente. A primeira operação para obter as panelas é um corte 
desses elementos circulares sobre chapas de dimensão de 1,40 x 0,50 metros. Os elementos planos 
circulares são transformados em panelas em uma segunda operação de estamparia. Para o corte existem 
quatro tipos de matrizes conforme mostra a figura abaixo. 
 
 
MATRIZ 1 MATRIZ 2
MATRIZ 3 MATRIZ 4
 
 
 
 
A fábrica deseja uma produção diária mínima de 
500 panelas médias (obtidas do elemento circular 
de diâmetro 0,25) e 350 grandes (obtidas do 
elemento circular de diâmetro de 0,40). Os custos 
em reais por chapa pelo uso das matrizes de corte 
1, 2, 3 e 4 são, respectivamente: 1, 2, 3, 2. 
Elaborar o modelo de Programação Linear que 
indique quantas chapas deverão ser cortadas em 
cada matriz de modo a minimizar o custo. 
 
 19 
RREESSOOLLUUÇÇÃÃOO DDEE PPRROOBBLLEEMMAASS DDEE PPRROOGGRRAAMMAAÇÇÃÃOO LLIINNEEAARR 
UUTTIILLIIZZAANNDDOO OO SSOOLLVVEERR 
 
 
Resolva os problemas modelados anteriormente utilizando o solver (Apêndice 1), e responda as questões 
apresentadas a seguir para os problemas 3, 4 e 5 (faça as simulações quando necessário). 
 
 
Problema 3: Resolva o problema com o auxílio do solver e responda: 
 Qual a quantidade que pode e deve ser vendida de cada produto para que o lucro seja máximo? 
 Qual o lucro máximo que se pode obter? 
 Quais restrições que limitaram esta produção? 
 Existem recursos que podem ser aplicados para melhoria da produção. Eles podem ser distribuídos 
conforme a tabela abaixo. Qual aumento obtido em cada alternativa? Qual você escolheria? 
 Horas de Fresa Horas de Torno Horas de Retífica Kg de Matéria Prima 
20 10 10 48 
0 25 10 50 
0 30 0 45 
30 0 0 30 
0 0 35 25 
0 15 25 50 
 
 
 Caso seja feito um pedido de 50 unidades do produto A. Como ficaria a nova distribuição e o lucro? 
Qual foi a perda? 
 
 
Problema 4: Resolva o problema com o auxílio do solver e responda: 
a) Escreva quantos rádios de cada modelo devem ser feitos para obter o lucro máximo. 
b) Qual é o valor do lucro? 
c) Quais restrições limitaram a produção? Caso seus limites fossem aumentados, quanto cada um 
aumentaria (ou diminuiria) o lucro? 
d) Caso o fabricante tivesse aceitado um pedido de 25 rádios do modelo A e 100 rádios do modelo B, como 
ficaria a produção? É o lucro? 
 
 
 
Problema 5: Resolva o problema com o auxílio do solver e responda: 
a) Quantas chapas devem ser cortadas em cada matriz para que o custo seja mínimo? Qual o custo 
mínimo? 
b) Quantas panelas de cada tamanho devem ser produzidas? 
c) O que acontece com o custo se os pedidos de panelas aumentarem? Em quanto cada panela a mais, de 
cada tamanho, variará o custo? 
d) Existe algum tipo de matriz que não será utilizada? Porquê? Qual a relação desta(s) matriz(es) com o 
custo? 
 
 
 
 
 
 
 
 
 20 
 
 
 
Um Problema de Transporte é um tipo especial de problema de Programação Linear, envolvendo 
um número m de origens e n de destinos. Geralmente deve-se buscar o menor custo de transporte possível, 
atendendo as necessidades dos destinos com as disponibilidades das origens. 
Outras aplicações: distribuição de água, energia elétrica, linhas telefônicas, etc. 
Há também os Problemas de Atribuição ou Designação, que são geralmente utilizados para 
escalas de profissionais, distribuição de tarefas, com objetivo de minimizar custo (ou tempo). 
 
Características dos Problemas de Transporte: 
1. O modelo exige um equilíbrio entre fontes e destinos, ou seja, a soma dos valores que há nas fontes 
deve ser igual a soma dos valores solicitados pelos destinos. 
2. Modelo que possui (m + n) incógnitas e (m + n – 1) equações de restrições. 
3. Os coeficientes das variáveis nas restrições serão sempre 0 ou 1. 
4. A matriz formada pelas restrições de absorção pelos destinos é a transposta da matriz formada pelas 
restrições das fontes. 
 
SOLUÇÃO INICIAL 
 
1. CUSTO MÍNIMO: 
 Encontrar a célula com menor custo e colocar a maior quantidade possível na mesma. 
 Eliminar a linha (ou coluna) que foi zerada. 
 Repetir o processo até que todas as quantidades disponíveis sejam distribuídas, atendendo todos os 
pedidos. 
 
2. MÉTODO DE VOGEL 
 Diminuir os menores custos de cada linha e de cada coluna. 
 Escolher a linha (ou coluna) com a maior diferença. 
 Nesta linha (ou coluna) escolher a célula de menor custo e colocar a maior quantidade possível na 
mesma. 
 Eliminar a linha (ou coluna) que foi zerada. 
 Repetir o processo até que todas as quantidades disponíveis sejam distribuídas, atendendo todos os 
pedidos. 
 
ITERAÇÃO  VERIFICAR SE É SOLUÇÃO ÓTIMA: 

 Definir as variáveis que representam cada fonte (ui) e cada destino ( vj). 
 A cada variável xij da solução inicial associar a equação: cij - ui - vj = 0  cij = ui + vj 
 Encontrar o aumento ou a diminuição na função objetivo ao inserir uma unidade em uma variável não 
básica. 
A cada variável não básica (xij) calcular Pij = cij – ui – vj. 
 Se Pij > 0 a solução é ótima e única. 
 Se Pij = 0 esta é uma das soluções ótimas (há outras com o mesmo valor) 
 Se Pij < 0 existe solução melhor. 
 
 
 
 
 
 
 
 
PROBLEMA DE TRANSPORTE 
 21 
Problema Exemplo 1: Uma empresa possui dois depósitos para suas mercadorias localizados em cidades 
diferentes, com quantidades diferentes de produtos. O depósito a1 possui 15 unidades em estoque e o 
depósito a2 possui 25 unidades. Três lojas solicitaram estes produtos nas seguintes quantidades/destinos, 
b1 = 20, b2 = 10 e b3 = 10 unidades. Devido às distâncias entre os depósitos e as lojas, os custos de 
transporte são os seguintes c11 = 10, c12 = 3, c13 = 5; c21 = 12; c22 = 7; c23 = 9; Sendo cij = custo por 
unidade que sai do depósito i para a loja j. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 22 
Problema Exemplo 2: Dados os custos de uma carga de leite de determinadas fábricas para armazéns e, 
das ofertas (produção) e procuras em cargas de caminhão /dia. Calcular o menor custo de fazer esta 
distribuição satisfazendo os pedidos. 
 
 
 Custos por carga de caminhão 
Armazéns 
Fábricas 1 2 3 4 Ofertas 
1 
 1 2 3 4 OOffeerrttaa 
 6 
 
2 
 4 3 2 4 
 8 
 
3 
 0 2 2 1 
 10 
 
Demanda 4 7 6 7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 23 
* MODELOS DOS QUADROS UTILIZADOS ENCONTRAM-SE NO APÊNDICE 2. 
 
EEXXEERRCCÍÍCCIIOOSS 
 
01. Nas planilhas abaixo, encontre o custo máximo levando em consideração que as linhas representam as 
fontes e as colunas os destinos: 
 
 
1 2 3 4 
(a) 4 6 2 3 OOffeerrttaa 
1 
 100 
 
 3 1 7 3 
2 
 200 
 
 2 2 3 5 
3 
 300 
 
Demanda 80 160 100 260 
 
 
1 2 3 
(b) 4 6 2 OOffeerrttaa 
 
1 
 15 
 3 1 7 
 
2 
 25 
Demanda 20 10 10 
 
 
1 2 3 4 
(c) 10 9 7 12 OOffeerrttaa 
A 50 
 14 126 5 
B 80 
 12 14 20 17 
C 90 
 16 12 10 9 
D 180 
Demanda 100 100 100 100 
 
 
02. Um fabricante de artigos de plástico possui em estoque 1200 caixas transparentes em uma de suas 
fábricas e outros 1000 em uma segunda fábrica. O fabricante recebeu pedidos deste produto provenientes 
de três diferentes varejistas nas quantidades de 1000, 700 e 500 caixas, respectivamente. Os custos 
unitários de expedição (em cents por caixa) desde as fábricas até os varejistas são os seguintes: 
 
 Varejista 1 Varejista 2 Varejista 3 
Fábrica 1 14 13 11 
Fábrica 2 13 13 12 
 
 
 
 24 
03. Uma vinícola do sul de Santa Catarina possui três fábricas e três armazéns nos quais os vinhos são 
envelhecidos. Como as fábricas e os armazéns estão localizados em diferentes locais do estado, a empresa 
deseja saber quantos tonéis de vinho deve enviar de cada fábrica para cada armazém de forma a minimizar 
o seu custo de transporte. As capacidades das fábricas e dos armazéns (em número de tonéis), bem como 
os custos de transporte por tonel, estão explicitados na tabela a seguir: 
 
 Armazéns Capacidade das 
fábricas A1 A2 A3 
Fábricas F1 20 16 24 300 
F2 10 10 8 500 
F3 12 18 10 200 
Capacidade dos 
armazéns 
200 400 300 
 
Qual o custo mínimo de transporte? 
Os armazéns da empresa possuem espaço suficiente para armazenar a produção das fábricas? Caso não 
seja suficiente, qual fábrica deverá reduzir sua produção ou buscar um outro armazém para depositar parte 
da sua produção? Qual é a quantidade que sobrará? 
 
 
04. A Docelar é uma florescente fábrica de fogões domésticos, com escritórios centrais em São Paulo e 
fábricas em Londrina, Salvador e São Paulo. Atualmente, um dos modelos mais conceituados da Docelar é 
o Brasileirinho 05, um fogão de seis bocas de grande aceitação em todo o Brasil. Apesar de contar com 
uma rede de revendedores, a Docelar pretende agora trabalhar com três grandes armazéns próprios, 
localizados em Bauru, Porto Alegre e Campo Grande. Londrina é capaz de produzir 5.000 unidades 
mensais do Brasileirinho 05, enquanto a fábrica de São Paulo consegue produzir 30.000 unidades mensais. 
Já Salvador tem uma capacidade intermediária de produção: 10.000 unidades por mês. Por outro lado, os 
armazéns que devem ser reabastecidos têm as seguintes demandas: Bauru: 15.000 unidades por mês, 
Porto Alegre: 20.000 unidades por mês e Campo Grande: 10.000 unidades por mês. 
Os custos unitários de transporte, de cada fábrica a cada um dos armazéns são mostrados na tabela a 
seguir: 
 
 Bauru Porto Alegre Campo Grande 
Londrina 40 60 60 
Salvador 80 90 70 
São Paulo 40 60 50 
 
Pede-se: determinar as quantidades que devem ser despachadas de uma fábrica para cada armazém, de 
forma a minimizar o custo total de transporte. Calcular também quanto vale o custo mínimo de transporte. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 25 
 
 
 
 
Problema: alocação de recursos disponíveis para atividades de interesse de forma a otimizar alguma 
medida de efetividade do sistema. Os limites das restrições sempre serão “1”. 
 
Exemplos de aplicações 
 
RECURSO ATIVIDADE CRITÉRIO 
Operários Tarefas Tempo de execução 
Caminhões Rotas Custo de transporte 
Máquinas Locais Operacionalidade 
Vendedores Regiões Volume de vendas 
 
Algoritmo do Método Húngaro (adaptado): 
 
1. Em cada linha, diminua o menor valor que existe nela em todas as colunas. 
2. Verifique se você já obteve um zero em cada linha, de forma que não fique mais de um em cada 
coluna. Caso você tenha encontrado, eis a resposta final. Caso contrário vá ao passo 3. 
3. Repita o passo 1 em cada coluna. 
4. Verifique se você já obteve um zero em cada linha, de forma que não fique mais de um em cada 
coluna. Caso você tenha encontrado, eis a resposta final. Caso contrário vá ao passo 5. 
5. Cubra todos os zeros com o menor número de reta possível. 
6. Dentre os números que não estão cobertos por nenhuma reta, escolha o menor e diminua este valor de 
todos os números que não estão cobertos por nenhuma reta. Em seguida some este valor aos 
números que se encontram no cruzamento de duas retas. Volte ao passo 4. 
 
Observações: 
 
1. Matriz de custos não é quadrada: adicionar linhas ou colunas fictícias e custos nulos, para torna-la 
quadrada. 
2. Quando uma designação não é possível: coloque nesta célula que representará um custo muito 
grande. 
3. Quando buscamos a maximização e não a minimização: 
* Multiplicar todos os elementos da matriz inicial por (-1) 
* Identificar o elemento de maior valor em módulo de cada linha 
* Somar este elemento (em módulo) a todos os elementos, em cada linha. 
* continuar a resolução como se fosse minimização. 
 
 
 
 
 
 
 
 
 
PROBLEMAS DE DESIGNAÇÃO 
 26 
Problema Exemplo 1. Designar 4 operários [ I, II, III, IV ] para executar 4 tarefas (A, B, C, D) de maneira 
que o tempo total (em horas) para o término de todas as tarefas seja o menor possível. Conhece-se o tempo 
que cada operário gasta para desempenhar cada uma das 4 tarefas: 
 
 I II III IV 
A 5 24 13 7 
B 10 25 3 23 
C 28 9 8 5 
D 10 17 15 3 
 
 
Problema Exemplo 2. O presidente de uma grande empresa está estudando a transferência de quatro 
diretores para quatro locais de trabalho diferentes. Foram feitas estimativas dos custos (em R$ 1000,00) 
envolvidos na transferência de cada diretor para cada novo local de trabalho. Estes custos são dados a 
seguir: 
 
 Local 
 1 2 3 4 
Diretor 
A 12 11 14 12 
B 13 14 11 16 
C 11 12 16 15 
D 11 13 13 17 
 
Obter a designação de diretores para locais de trabalho de menor custo. 
 
Problema Exemplo 3. O Diretor de uma escola deseja inscrever quatro alunos num concurso de 
matemática que engloba os seguintes assuntos: Álgebra, Cálculo I, Geometria e Cálculo II. Somente um 
aluno pode ser inscrito em cada assunto porque as provas do concurso ocorrerão simultaneamente. Para 
isso ele seleciona seus quatro melhores alunos, A, B, C, D e lhes aplica testes cobrindo as quatro áreas do 
concurso. O quadro abaixo indica o número de pontos que cada aluno obteve em cada uma das áreas no 
exame simulado. 
 
 Álgebra Cálculo I Geometria Cálculo II 
A 7 10 8 3 
B 8 7 8 1 
C 4 9 3 5 
D 5 4 6 9 
 
Qual aluno deve ser selecionado para cada um dos assuntos do concurso. 
 
 
 
 
 
 
 
 27 
EEXXEERRCCÍÍCCIIOOSS 
 
1. Em uma empresa de construção civil, há três projetos que podem ser alocados a três equipes diferentes. 
Tanto o tempo (em meses) de experiência das equipes como suas orientações técnicas são diferentes, de 
modo que o tempo de término de cada projeto dependerá da equipe particular ao qual estará alocado. A 
matriz a seguir mostra os tempos de desenvolvimento dos projetos, conforme sejam alocados a cada uma 
das equipes. Utilizando o método da Alocação, identifique que equipe deverá desenvolver cada projeto de 
forma que o tempo total seja mínimo. 
 
 Projeto A Projeto B Projeto 
Equipe I 15 24 21 
Equipe II 17 22 18 
Equipe III 23 29 30 
 
 
2. Uma empresa está envolvida em um esforço para a abertura de quatro escritórios regionais de vendas, 
nas cidades de Salvador, Recife, Caxias do Sul e Florianópolis. Dentre seus funcionários, há três 
coordenadores de vendas (Matos, Pereira e Bernardes) que estão aptos a assumir qualquer um dos novos 
escritórios. Entretanto, os custos de realocação são diferentes, dependendo do par coordenador/escritório, 
segundo a matriz a seguir, estabelecida em reais (R$): 
 
 Salvador Recife Caxias do Sul Florianópolis 
Matos 4.000 5.500 6.000 5.000 
Pereira 2.500 8.000 6.500 4.000 
Bernardes 2.500 5.000 11.500 7.000 
 
Assumindo que a empresa deseja minimizar os custos de preenchimento dos cargos, fazer a distribuição 
dos coordenadores pelos escritórios regionais de acordo com o algoritmo do método da alocação, calcular o 
custo total mínimo. 
 
3. Uma empresa vende produtos em quatro regiõese possui quatro vendedores que devem atender quatro 
regiões diferentes, sendo um vendedor para cada região. 
As regiões não são igualmente ricas e apresentam o seguinte potencial de venda (em $) para cada 
vendedor: 
 Região 
 I II III IV 
Vendedor 
A 4200 3500 2800 3000 
B 4800 4000 3200 3000 
C 3000 2500 2000 3000 
D 6000 2000 4000 1200 
 
 
4. Quatro edifícios diferentes devem ser construídos em um campus universitário por quatro empreiteiras 
diferentes. Como todos os edifícios devem obrigatoriamente ser construídos ao mesmo tempo e a 
capacidade das empreiteiras é construir somente um edifício, a pró-reitoria de planejamento deve decidir 
qual construção deve ser designada para qual empreiteira a fim de minimizar o custo total para a 
universidade. Auxilie. 
Cada empreiteira fez suas propostas no tocante às quatro construções que aparecem na tabela em milhares 
de unidades monetárias (u.m.) 
 Edifício I Edifício II Edifício III Edifício IV 
Empreiteira A 480 480 500 440 
Empreiteira B 560 600 600 680 
Empreiteira C 960 940 900 850 
Empreiteira D 420 440 540 460 
 
Pede-se determinar, empregando o modelo da 
designação, como enviar os vendedores às 
regiões para que o volume de vendas total das 
quatro regiões seja o maior possível. 
 
 28 
5. Uma fábrica possui quatro locais diferentes para receber três máquinas novas. Em função do layout a 
máquina A não pode ser instalada no lugar 4. O custo de manuseio de materiais, em u.m./hora, envolvendo 
cada máquina com as respectivas posições, é dado a seguir. Sabe-se que não existe nenhum fluxo de 
material entra as novas máquinas. O objetivo é designas as novas máquinas aos locais disponíveis de 
mono a minimizar o custo total de manuseio de materiais. O gerente de produção também quer saber se 
existe mais de uma maneira de designar as máquinas aos locais com o mesmo custo mínimo total. 
 
 Lugar I Lugar II Lugar III Lugar IV 
Máquina A 50 10 30 X 
Máquina B 30 10 40 30 
Máquina C 30 30 40 20 
 
Problema Desafio. Uma Empresa necessita desenvolver um plano de produção para iniciar a fabricação de 
três novos produtos. A Empresa dispõe de cinco máquinas e apenas três destas deverão ser escolhidas 
para manufaturar os novos itens, sendo um produto por máquina. Os custos de produção e os custos de 
distribuição para todas as combinações produto-máquina são fornecidos a seguir: 
 Máquina 
1 2 3 4 5 
Produto 
A 20 23 38 15 37 
B 8 29 6 15 37 
C 5 8 3 4 7 
 
 Máquina 
1 2 3 4 5 
Produto 
A 20 50 20 10 13 
B 7 20 8 35 8 
C 5 5 4 15 6 
 
De acordo com os planos atuais é necessário manter uma determinada produção anual por item para haver 
demanda pelos preços unitários planejados, estes dados são fornecidos adiante: 
 
Produto Produção Planejada Preços Planejados 
A 35000 55 reais 
B 160000 50 reais 
C 54000 30 reais 
 
Formule um modelo da designação para tratar este problema e resolva-o buscando encontrar o máximo 
lucro. 
 
 
 
 
 
 
 
 
 
 
 
 
Custos de Produção (reais/unidade): 
 
Custos de Distribuição (reais/unidade): 
 
 29 
 
 
 
 
Em diversos momentos da nossa vida nos vemos de encontro com situações que, para serem melhor 
resolvidas, se faz necessária a elaboração de projetos, sejam eles grandes ou pequenos, e sua realização 
está diretamente relacionada com a obtenção de resultados ótimos. Podemos citar como exemplo a 
otimização de tempo, recursos ou de custos, pois em qualquer tarefa desejamos aproveitar da melhor forma 
possível o tempo e os recursos disponíveis para que os custos sejam mínimos. 
 
 
COMO SURGIU? 
 
Em 1958 foi criado, nos EUA, um grupo cujo objetivo era pesquisar e elaborar um sistema para 
aplicar na organização e controle de Mísseis Balísticos da Esquadra Aérea, o qual iria produzir o foguete 
Polaris. 
Para resolver este grande problema (grande porque envolvia cerca de 250 empreiteiros e 9.000 sub-
empreiteiros, sendo que o número de peças a serem produzidas era de 70.000) eles utilizaram o que foi 
denominado de sistema PERT (Program Evaluation and Review Technique). 
Ele possibilitou não só a resolução do problema, mas conseguiu reduzir o prazo de construção de 5 
para 3 anos. 
 
 
Mas, o que entendemos por PROJETO? 
 
No nosso entender, Prado (1988,p.210) define bem este termo quando fala que “Projeto é um 
empreendimento único e não repetitivo,: o determinada, formalmente organizado e que congrega e aplica 
recursos visando o cumprimento de objetivos preestabelecidos.” 
Um projeto é realizado em três etapas. 
 
(1) Planejamento. Etapa em que definimos quais atividades deverão ser realizadas e a sequência das 
mesmas. 
(2) Programação. É efetuada a análise do tempo necessário para cada atividade estabelecendo assim, as 
datas de início e término de cada uma delas no projeto.
1
 
(30 Controle. “A essência da execução é a realização dos planos para atingir o resultado esperado.” 
(Maximiliano, 1997, p80) E, para que isto seja possível é necessário que acompanhemos a realização do 
projeto verificando se o seu progresso está dentro do pré-estabelecido. 
 
NNeessttee mmoommeennttoo vvaammooss rreessoollvveerr aa eettaappaa ddee pprrooggrraammaaççããoo ddee uumm eexxeemmpplloo aattrraavvééss ddoo SSiisstteemmaa PPEERRTT.. 
 
Suponhamos que uma empresa pretenda construir um galpão para armazenar seus produtos e deseja que 
ele esteja pronto em 30 semanas. Para isto contratou uma empreiteira que fez um estudo das etapas para 
construção do mesmo e os tempos necessários para a execução de cada uma delas. A tabela abaixo 
apresenta a relação das etapas, já na de execução e o tempo necessário para as mesmas. Neste momento 
é preciso fazer a programação analisando as “datas” do projeto para verificar se a empreiteira conseguirá 
atender o pedido ou terá que reavaliar os tempos. 
 
 
 
 
 
1
 Esta etapa será melhor explicada durante a execução do exercício proposto. 
SISTEMA PERT 
 30 
Exemplo: Planejamento da construção de um galpão para servir como depósito. 
Código Descrição da Atividade DDuurraaççããoo Dependência 
A Preparo do local 2 - 
B Fundações 4 A 
C Alvenaria 4 B 
D Esgotos 1 B 
E Telhado 5 C 
F Piso 1 D 
G Instalação Elétrica 3 E 
H Instalação Hidráulica 4 E 
I Carpintaria 6 E,F 
J Pintura interna 4 G,H,I 
K Pintura externa 3 I 
L Limpeza Final 1 J,K 
* Duração em semanas 
 
Para fazermos a programação, na tabela, temos antes que conhecer alguns termos utilizados no 
Sistema PERT: 
 
O primeiro passo para a programação será encontrarmos as datas de Início Mais Cedo (IMC), 
Término Mais Cedo (TMC), Início Mais Tarde (IMT) e Término Mais Tarde (TMT). Estas “datas” são 
importantes porque é através delas que encontramos as folgas das atividades (o tempo que uma 
determinada atividade tem livre sem prejudicar o início da próxima), o caminho crítico (sequência de 
atividades que não podem atrasar) e o período real do projeto. 
 
Início Mais Cedo (IMC): é a data em que uma determinada atividade iniciará caso nenhuma das suas 
antecessoras atrase. 
 
O IMC das atividades iniciais será sempre 0 (zero) pois estamos começando o projeto. As outras 
terão seu IMC exatamente na data do TMC (Término Mais Cedo) da sua antecessora. Quando uma 
atividade tiver mais de uma antecessora utilizamos o maior período, pois devemos sempre ter em mente 
que todas atividades anteriores devem estar prontas para que esta seja realizada. 
 
Término Mais Cedo (TMC): será a sua data de início mais cedo mais a sua duração, sem atrasos. Assim: 
TMC = IMC + Duração 
 
Calculados o Início e o Término Mais Cedo de cada atividade é possível verificar qual o período do 
projeto. A data de término do projeto corresponde ao maior período obtido que será a data de término da 
última atividade, ou de uma das últimas. 
 
Sempre calculamos estes dois valores simultaneamente.Para entendermos melhor este processo vamos calculá-los para o problema inicial. 
 
Com estas duas colunas preenchidas encontramos o tempo mínimo necessário para que o projeto 
fique pronto. 
 
Término Mais Tarde (TMT): é a última data que a atividade em questão pode terminar sem comprometer a 
duração do projeto. 
 
A data de término da(s) última(s) atividade(s) corresponde(m) a data de término do projeto. O TMT 
das outras atividades corresponde a data de Início Mais Tarde das suas sucessoras. 
 
 31 
Início Mais Tarde (IMT): corresponde a sua data de término mais tarde menos a sua duração, ou seja, 
IMT = TMT - Duração 
 
Neste caso, se uma atividade tiver duas datas de término mais tarde, devemos utilizar o menor valor, 
pois estamos calculando o tempo a partir do fim do projeto e devemos deixar o maior período possível entre 
a atividade que estamos e a data de término do projeto, para que todas as que estão neste intervalo 
possam ser realizadas. 
 
Continuando a análise da programação, preenchemos das colunas de IMT e TMT. Devemos calculá-
las começando pelas últimas atividades do projeto tendo sempre em mente que não podemos ultrapassar o 
período estipulado, que já foi encontrado. 
Durante o preenchimento destas colunas é conveniente logo que encontramos a data de IMT de uma 
atividade, colocarmos este mesmo valor na coluna de TMT das atividades de que ela depende. (Para que 
uma atividade inicie em determinada data as anteriores já devem estas prontas). 
Quando preenchemos a coluna de TMT também é possível que existam atividades que tenham mais 
de uma data de término. Relembrando, como devemos deixar o maior tempo possível para que as 
atividades posteriores possam ser realizadas sem atrasar o final do projeto escolhemos o menor valor e 
calculamos o seu IMT. 
 
Obtidas as “datas” calculamos as folgas das atividades subtraindo-se os IMT dos IMC ou dos TMT 
dos TMC de cada atividade. 
 
Folga = IMT – IMC ou Folga = TMT – TMC 
 
Preenchida a tabela podemos encontrar o Caminho Crítico que é a seqüência de atividades que não 
podem atrasar, para que o projeto termine no período encontrado. A soma dos temos destas atividades 
deve sempre ser igual ao período do projeto. Ele é muito importante, pois informa em quais atividades 
devemos ter atenção redobrada durante a execução do projeto visto que, caso uma delas atrase, atrasará o 
projeto em um período equivalente. 
 
 
TABELA RELACIONADA AO EXEMPLO: 
 
Atividades Duração Dependência IMC TMC TMT IMT Folga 
A 2 - 
B 4 A 
C 4 B 
D 1 B 
E 5 C 
F 1 D 
G 3 E 
H 4 E 
I 6 E,F 
J 4 G,H,I 
K 3 I 
L 1 J,K 
 
 
 
 
 
 
 
 32 
DDIIAAGGRRAAMMAA DDEE GGAANNTTTT 
 
 
Também conhecido como Diagrama de Barras, é a técnica mais antiga e simples que objetiva o 
planejamento temporal de projetos. Ele é muito utilizado em todas as áreas de planejamento devido ao fato 
de possuir uma excelente comunicação visual. 
 
Apesar do Diagrama de Gantt ser de fácil construção apresenta a deficiência de não evidenciar as 
interdependências entre as atividades. No decorrer do tempo, com a explosão industrial, aumentou a 
complexidade dos projetos, relacionados com um número progressivamente maior de pessoas (físicas e 
jurídicas) e recursos. Novas técnicas de representação gráfica dos projetos foram sendo construídas para, 
de modo mais eficiente, controlar atividades. Mostraremos o projeto acima através do Gráfico de Setas. 
 
Descrição 
da 
Atividade 
Código 
0 
1 
0 
2 
0 
3 
0 
4 
0 
5 
0 
6 
0 
7 
0 
8 
0 
9 
1 
0 
1 
1 
1 
2 
1 
3 
1 
4 
1 
5 
1 
6 
1 
7 
1 
8 
1 
9 
2 
0 
2 
1 
2 
2 
2 
3 
2 
4 
2 
5 
2 
6 
2 
7 
2 
8 
2 
9 
3 
0 
3 
1 
3 
2 
3 
3 
3 
4 
3 
5 
3 
6 
3 
7 
3 
8 
3 
9 
Preparo do 
local 
A 
 
 
Fundações 
B 
 
 
Alvenaria 
C 
 
 
Esgotos 
D 
 
 
Telhado 
E 
 
 
Piso 
F 
 
 
Instalação 
Elétrica 
G 
 
 
Instalação 
Hidráulica 
H 
 
 
Carpintaria 
I 
 
 
Pintura 
interna 
J 
 
 
Pintura 
externa 
K 
 
 
Limpeza 
Final 
L 
 
 
 
 
 
DDIIAAGGRRAAMMAA DDEE SSEETTAASS SSEEMM EESSCCAALLAA 
 
Outra forma de representar graficamente o sistema PERT é através do Diagrama de Setas 
sem Escala. 
 
Problema Exemplo: Abaixo se apresenta um projeto cujo tempo em calculado em semanas 
representado por este Diagrama. 
 
 
 
 
 
 
 
 
 
 
 
 
 
Neste tipo de representação as SETAS representam as atividades. 
Sobre as setas irão, entre parênteses, o código da atividade e a sua duração. 
 
Exemplo: (A,2) 
 
 Atividade duração 
 
 Círculos: denominados EVENTOS marcam um estado. Eles indicam em qual situação o 
projeto se encontra em cada momento. 
 
Uma rede deve começar e terminar com um evento sendo que, a mudança de atividade e 
relação de precedência também é indicada pelo mesmo. Assim, uma atividade que está após um 
evento deve esperar todas as que vêm antes terminar, para somente depois poder iniciar. 
 
Observação: Podemos notar que no Diagrama de Barras há uma seta diferente, tracejada 
( ). Esta seta é denominada de Atividade Fantasma. A atividade fantasma é utilizada 
quando duas ou mais atividades possuem o mesmo evento inicial e terminal (isto forma o que 
chamamos, na teoria de redes de circuito, e que não pode acontecer). É importante salientarmos 
(B,300) 
(I,200) 
(E,70) 
(F,250) 
 
(G,450) 
(D,400) 
(K,250) 
 
(A,50) 
(C,120) 
(H,300) 
(J,180) 
 35 
que a atividade fantasma serve apenas para indicar precedência, não possui código próprio e nem 
tempo de realização, pois na realidade ela não existe. 
 
Como vimos nos exemplos anteriores o tempo total do projeto é composto pela soma dos 
tempos das atividades do caminho crítico, que por sua vez é o maior período total. Devido a este 
fato podemos facilmente descobrir o tempo do projeto e o caminho crítico de um projeto 
apresentado na forma de Diagrama de Setas, basta somar todos os caminhos possíveis e escolher 
o que possui o maior total. 
 
Vamos analisar o exemplo apresentado:: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 36 
EEXXEERRCCÍÍCCIIOOSS 
 
1. Encontre as datas, o caminho crítico e mostre o projeto graficamente através do Diagrama de 
Gantt. 
 
(a) 
Atividade Duração (sem.) Depend. IMC TMC TMT IMT Folgas 
A 2 - 
B 2 A 
C 3 A 
D 2 B,C 
E 1 D 
 
(b) 
Atividade Duração (sem.) Depend. IMC TMC TMT IMT Folgas 
A 1 - 
B 1 A 
C 4 A 
D 2 A 
E 2 B 
F 2 C 
G 1 D,E,F 
 
(c) 
Atividade Duração (sem.) Depend
. 
IMC TMC TMT IMT Folgas 
A 1 - 
B 5 A 
C 2 A 
D 4 A 
E 3 B 
F 2 E 
G 3 C,F 
H 2 D,G 
 
(d) 
Atividade Duração Dependência IMC TMC TMT IMT Folgas 
A 2 - 
B 7 - 
C 6 -D 3 A 
E 8 B 
F 4 C 
G 3 E 
H 2 G,F 
 
 37 
4. Nos casos abaixo, faça o diagrama de Setas para o projeto, determinando os Tempos Mais 
Cedo e os Tempos Mais Tarde: 
 
Atividade Duração Dependência IMC TMC TMT IMT Folgas 
A 2 - 
B 3 - 
C 6 - 
D 3 A 
E 4 B 
F 4 C 
G 2 D,E 
H 2 G,F 
 
 
 
5. Suponha o seguinte conjunto de atividades: 
(A) Estudo da viabilidade do empreendimento; (1 semana) 
(B) Instalação do canteiro (1 semana); 
(C) Sondagem (1 semana); 
(D) Projeto arquitetônico (2 semanas); 
(E) Cálculo estrutural (4 semanas); 
(F) Fundações (3 semanas). 
Em conversa com o Especialista no assunto você ficou sabendo: 
a) Que a primeira atividade a ser feita é o “Estudo de Viabilidade”; 
b) Que após esta atividade, as três atividades seguintes podem acontecer isoladamente, ao 
mesmo tempo; 
c) Que após a sondagem e de posse do projeto arquitetônico pode-se dar o cálculo estrutural; 
d) Que de posse do cálculo estrutural e com a instalação do canteiro podem-se realizar as 
fundações. 
 
Pede-se: 5.1) tabela com duração e dependência das atividades; 
 5.2) O diagrama de setas correspondente; 
 5.3) Qual a duração planejada do projeto? 
 5.4) Qual a duração do projeto caso a instalação do canteiro comece 6 semanas após a 
data prevista? 
 
 
 
 
 
 
 
 
 38 
6. Construa o diagrama de setas, encontre as datas e o caminho crítico. 
 
(a) 
Atividade Dependência
. 
Duração da ativ. 
(dias) 
IMC TMC TMT IMT Folgas 
A -x- 5 
B -x- 7 
C -x- 10 
D A 12 
E B,C 4 
F B 8 
G D,E 11 
H B,C 13 
I F 10 
 
 (b) 
Atividade Duração Dependência IMC TMC TMT IMT Folgas 
A 1 - 
B 2 A 
C 3 A 
D 2 B 
E 3 C 
F 2 D 
G 2 D,E 
H 3 D,E 
I 2 F,G,H 
 
 
(c) 
Atividade Duração Dependência IMC TMC TMT IMT Folgas 
A 6 - 
B 29 A 
C 13 A 
D 70 A 
E 20 B 
F 3 B 
G 15 C 
H 10 E,F 
I 5 D,G,H 
 
 39 
7. As redes a seguir representam projetos onde os eventos (círculos) marcam inícios e finais de 
etapas de produção de um produto qualquer e as setas representam as atividades em si e o seu 
tempo de duração (em semanas). Indique as sequências de atividades possíveis e o tempo de 
duração de cada uma delas, marcando qual o caminho, em cada uma delas. 
 
(a) 
 
 
 
 
 
 
 
 
 
 
(b) 
 
 
 
 
 
 
 
 
 
 
 
 
 
(c) 
 
 
 
 
 
 
 
 
 
 
(d) 
 
 
 
 
 
 
 (D,6) 
(B, 5) 
(E,2) 
(C, 8) 
(A, 3) 
 
(F,3) (E,5) 
(B,5) 
(C,7) 
 
(I,5) 
 
(D,3) 
 
(A,5) 
(G,3) 
(H,3) 
(L,1) 
(J,4) 
(F,4) (D,2) 
(B,2) 
 
(E,3) 
 
(C,1) 
 
(A,2) 
(H,2) 
(G,1) 
(C,300) 
(I,250) 
(E,70) 
(F,250) 
(G,450) 
(D,400) 
(J,250) (A,50) 
(B,120) 
 
(H,300) 
(L,180) 
 40 
 
 
 
Para projetos cujas atividades têm duração estocástica, aplica-se o CPM. 
Dentre as distribuições de probabilidades conhecidas, aceita-se ser a distribuição beta 
aquela que melhor explica a duração de uma atividade. A fim de se poder estabelecer 
convenientemente a distribuição beta a partir de poucos parâmetros fáceis de serem obtidos, toma-
se, para cada atividade i, três medidas de tempo que são: 
 
toi : é mínimo tempo que se estima como razoável para a execução de uma atividade, ou seja, o 
tempo mais otimista; 
tmi : é o tempo mais provável para a execução da atividade, ou seja, o que ocorre com maior 
frequência (a moda da distribuição); 
tpi : é o máximo tempo que se estima como razoável para a execução de uma atividade, ou seja, o 
tempo mais pessimista. 
 
Usam-se estas medidas para estimar a média e a variância da distribuição da variável 
aleatória Ti, o tempo de execução da atividade i. 
6
tt4t
)T(
pimioi
i

 
2
oipi
i
2
6
tt
)T( 






 
 
 
Imprecisões aliadas à obtenção exata destas três medidas acima impedem a obtenção de 
medidas de média e desvio-padrão exatas. No entanto, o erro absoluto limitante fica em torno de 
5%, o que pode ser considerado satisfatório, de modo geral. 
Pode-se assumir o pressuposto razoável de que a distribuição do tempo de realização do 
projeto é a soma dos tempos das atividades do caminho crítico, dado que as probabilidades dos 
tempos dos demais caminhos chegarem a ultrapassar este valor é muito reduzido. Assim, o tempo 
de realização do projeto, Tproj, é a soma de variáveis aleatórias beta, e as distribuições de tempo 
das atividades do caminho crítico . Assumindo a independência entre os tempos de realização 
das atividades, esta variável aleatória Tproj aproxima-se, de acordo com o teorema do limite central, 
à uma distribuição normal. Os parâmetros de média e variância de Tproj podem, então, ser assim 
estimados. 
 


i
iproj )T()T( )T()T( i
i
2
proj
2 

 
 
De acordo com a fórmula da média, a técnica CPM pode então calcular a duração média 
de um projeto, a partir das durações médias das atividades, assim como determinar o seu caminho 
crítico, do mesmo modo como o PERT faz para determinar o tempo mínimo de realização do 
projeto e seu caminho crítico a partir das durações de atividades determinísticas. 
O que se pode querer, muitas vezes, é determinar a probabilidade de se poder cumprir 
certos prazos, ou seja, calcular determinados riscos face a compromissos estabelecidos. Dado um 
TÉCNICA DO CAMINHO CRÍTICO - CPM 
 41 
prazo limite , a probabilidade de se cumprir o projeto até aquela data será, portanto, calculado por 
]Pr[ projT 
 
Para trabalhar com a Normal, como a média é diferente de zero e o desvio padrão diferente 
de um, temos que “padronizar” e para isso fazemos: 
 




































)T(
)T(
)T(
)T(
zPr
)T(
)T(
)T(
)T(T
Pr]TPr[
proj
proj
proj
proj
proj
proj
proj
projproj
proj 
 
onde  é a função de distribuição acumulada da distribuição normal padrão N(0,1). 
 
 
Problema Exemplo: Considere-se o projeto abaixo: 
Atividade 
i 
Depende toi tmi tpi 
Média 
µi 
Variância 
i 
IMC TMC TMT IMT FOLGA 
A -x- 1 2 3 
B -x- 1 2 9 
C -x- 4 4 16 
D A 1 2 9 
E B 2 4 6 
F C 1 4 7 
G D,E 1 2 3 
H G,F 1 1 7 
 
Pede-se: 
a) Encontre as datas mais cedo e as datas mais tarde, o tempo médio do projeto, o caminho crítico, 
variância e desvio padrão. 
b) Probabilidade do projeto não levar mais de 16 dias para acabar. 
c) Probabilidade do projeto não levar mais de 10 dias para acabar. 
d) Qual a duração do projeto que dará uma confiabilidade de 95%? 
 
 
 
 
 
 
 42 
Exercícios. 1. Analise o projeto a seguir 
Atividade 
i 
Depende toi tmi tpi 
Média 
µi 
Variância 
i 
IMC TMC TMT IMT FOLGA 
A -x- 4 5 6 
B -x- 5 6,5 11 
C -x- 7 9 17 
D A 7 11,5 19 
E B,C 3 4 5 
F B 5 7 15 
G D,E 2 12 16 
H B,C 3 14 19 
I F 8 9,5 14 
 
Pede-se: 
a) Encontre as datas mais cedo e as datas mais tarde, o tempo médio do projeto, o caminho crítico, 
variância e desvio padrão. 
b) Faça o diagrama de Setas que representa o projeto colocando os tempos médios de cada 
atividade e marcando o caminho crítico do tempo médio. 
c) Probabilidade do projeto não levar mais de 30 dias para acabar. 
d)) Probabilidade do projeto não levar mais de 20 dias para acabar. 
 
 
2. O tempo de conclusão esperado de um projeto é TE = 15 dias e CP
2
 = 4 dias. Qual a 
probabilidade de o projeto levar 18 ou mais dias para terminar? 
 
 
3. Para a tabela de atividades abaixo, construa o diagrama de setas sem escala correspondente e 
responda as seguintes questões: 
 
Atividade 
i 
Depende toi tmi tpi 
Média 
µi 
Variância 
i 
IMC TMC TMT IMT FOLGA 
A - 4 4 16 
B A 1 2 3 
C B 1 1 7 
D A 1 4 7 
E C 1