Unidade 01

Prévia do material em texto

- -1
PESQUISA OPERACIONAL
UNIDADE 1 - A PESQUISA OPERACIONAL E 
SUAS APLICAÇÕES
Luciano Wallace Gonçalves Barbosa
- -2
Introdução
A tomada de decisão é um dos termos mais comuns em ambientes corporativos e corresponde à necessidade de
se escolher, entre opções viáveis, aquela que trará mais benefícios à organização. Assim como uma escolha pode
render ótimos frutos, também pode levar a empresa a deixar de lucrar com seus recursos disponíveis e, no pior
dos cenários, trazer prejuízos. Porém, primeiramente, devemos responder: quais são as opções viáveis de um
negócio?
No ambiente organizacional, a tomada de decisão está, geralmente, dentro dos níveis estratégicos e táticos, que
dispendem de maiores responsabilidades. Em nível de longo prazo, essas decisões são uma das mais estudadas
pelos especialistas, já que, nesse patamar, interferem de maneira ainda mais pronunciada que os demais.
Essa lógica está relacionada a uma questão importante: a vantagem competitiva, que é quando uma empresa está
aferindo retornos acima da média de seus concorrentes. Com o mercado cada dia mais acirrado, dependendo da
estratégia adotada pela empresa, manter vantagem competitiva acaba sendo uma maneira de sobrevivência,
principalmente para aquelas que adotam a estratégia de foco em custos.
Assim, elucidada a importância da tomada de decisão, surge uma questão importante para aqueles que estão
encarregados dessa tarefa: qual a melhor opção, entre as viáveis, que se deve escolher? Evidentemente, em uma
lógica de apreciação de lucros, deve-se optar por aquela que maximize esse lucro e, analogamente, quando se
tratar de mensuração de custos, a opção ótima será aquela que garante o custo mínimo.
Entendida essa questão e dentro do contexto da Engenharia, que é responsável, entre outras coisas, por resolver
problemas por meio de desenvolvimentos matemáticos, outra questão aparece: como garantir que a melhor
opção foi a escolhida? Bom, essa pergunta é, sem sombra de dúvidas, mais complexa que a anterior. Mas a
grande vantagem é que existe uma resposta para ela: utilizando-se técnicas matemáticas que sustentem a
investigação. Nesse contexto, falaremos aqui sobre a Pesquisa Operacional, que é responsável por apoiar a
tomada de decisão, por meio de modelagem e resolução de problemas matemáticos. Legal, não é mesmo? Nada
melhor que uma decisão, algo tão complexo, podendo ser embasada por métodos matemáticos, que trazem
resultados exatos ou estimados com alto índice de confiança.
Vamos, então, conhecer essa incrível ciência denominada Pesquisa Operacional ou, simplesmente, PO?
1.1 Definição e contexto histórico
Você sabia que grande parte da ciência em todo o mundo foi desenvolvida durantes as guerras? Isso mesmo.
Agora, você imagina o porquê? Durante os períodos bélicos, os países precisam mostrar quem são os mais
poderosos em nível de desenvolvimento tecnológico, armamentista, de tropas e tudo mais. Tudo isso se dá com a
ciência. Imagine a fabricação de centenas de milhares de armas em um rápido espaço de tempo, considerando-se
reduzir ao máximo esse custo. Nessa questão, estão envolvidas diversas ciências, como as Engenharias, para
resolver esses problemas.
A Engenharia Mecânica, a de Materiais, assim como outras, ficam responsáveis pelos projetos de fabricação,
enquanto a Engenharia de Produção precisa resolver toda a logística de as necessidades estarem no tempo certo,
na qualidade e quantidade exatas, no destino necessário e por aí vai. Além disso, demais suprimentos eram
necessários nesse processo logístico, como roupas, alimentos, medicamentos etc. Então, durante a Segunda
Guerra Mundial (1939-1945), militares e cientistas reuniram-se para estudar como resolver isso, gerando, então,
a Pesquisa Operacional (do inglês ), em que o termo ‘Operacional’ tem referência aosOperational Research
problemas militares, e ‘Pesquisa’ é a criação do novo método. Por isso, a ciência ficou conhecida como ‘ ’,war baby
ou ‘bebê da guerra’ (ARENALES , 2007; TAHA, 2008; BELFIORE; FÁVERO, 2013; HILLIER; LIEBERMAN,et al.
2013).
A PO é um ramo muito promissor, você deve ter notado, já que resolve problemas por meio de modelos
- -3
A PO é um ramo muito promissor, você deve ter notado, já que resolve problemas por meio de modelos
matemáticos que auxiliam a garantia de otimalidade da solução encontrada. Assim, muitas áreas das ciências
estudam a Pesquisa Operacional, cada qual com sua especificação: por exemplo, por ser uma parte da
Matemática Aplicada, matemáticos estão sempre aprimorando modelos e encontrando suas soluções. Já os
cientistas da computação, analisam esses modelos e os trazem para algoritmos, que devem ser modelados e
resolvidos para trazerem a solução ótima. Outras ciências também buscam a PO nessa perspectiva, como
Engenharias de Computação, Elétrica etc. A Engenharia de Produção, por sua vez, trata a PO no sentido de trazer
os problemas da realidade para uma modelagem matemática e busca os métodos desenvolvidos até então, os
quais podem ser aplicados na solução dessa realidade trazida para equações, gráficos, modelos etc.
Todo problema de PO está relacionado a um objetivo, conforme falado, geralmente de custos ou minimizar
 lucros, acompanhados de restrições que o ambiente traz a esse problema, podendo ser de aspectosmaximizar
humanos, sociais, políticos, econômicos, tecnológicos etc. (MURTHY, 2007).
Como a PO nasceu há várias décadas e várias áreas da ciência a aprimoram cada vez mais, atualmente sua
utilização, como uma eficiente ferramenta em todos os níveis de gestão, é uma realidade acessível (ANDRADE,
2009). Avanços em programas computacionais também são responsáveis por esse desenvolvimento, pois a PO
necessita desses programas para encontrar a solução ótima dos problemas (GOLDBARG; LUNA, 2005).
Murthy (2007) apresenta, de forma clara, como a PO é dividida e aplicada em cada um dos seus diferentes
problemas e ambientes. A figura a seguir apresenta essa divisão.
Figura 1 - Métodos quantitativos versus qualitativos.
Fonte: Elaborada pelo autor, baseada em MURTHY, 2007.
Nota-se, então, que quanto mais simples e bem estruturados são os problemas (os quais, geralmente, se
encontram em ambientes tranquilos e uniformes), mais bem aplicável é a utilização de métodos quantitativos –
isso em relação aos ambientes turbulentos, que contam com problemas complexos e mal estruturados, sendo
que, a esses, as técnicas qualitativas são mais utilizáveis. Taha (2008) traz uma importante consideração: nem
sempre soluções matemáticas são a pedra fundamental, já que, em alguns casos, o ‘bom senso’ pode ser levado
em consideração para encontrar soluções por meio de simples observações.
Para ficar mais claro, Belfiore e Fávero (2013) dividem os problemas resolvidos por PO em três grupos. Clique
nas abas e conheça-os.
• Modelos determinísticos•
- -4
• Modelos determinísticos
As variáveis envolvidas são conhecidas e constantes. Esse tipo de modelo quantitativo traz a resposta
ótima ao problema, ou seja, caso você siga à risca o que foi proposto, seu objetivo será o mais ótimo
possível, respeitando as restrições do problema. A Programação Linear, uma das mais poderosas
ferramentas da PO, é um exemplo de modelo determinístico.
• Modelos estocásticos
As variáveis são aleatórias e definidas por funções de probabilidade. Esse tipo é muito comum em
simulação de processos e outros modelos que contem com estatísticas para solução. Por mais que não
sejam exatos como o primeiro tipo, esses modelos podem trazer confianças de solução de até 99%,
dependendo de como os dados são tratados.
• Outros modelos advindos do avanço computacional
Nesses, mais complexos, podem os dois tipos de variáveis estarem associados. Geralmente, são
desenvolvidos para casos específicos.
Está curioso para saber como que um problema real pode ser modelado por meio de técnicas matemáticas?
Então, venha ver. Abordaremos, primeiramente, a Programação Linear (PL), clássica da PO. Ninguém pode dizer
que sabe Pesquisa Operacional se não souber PL. Depois, veremosmodelagem em grafos ou redes, que é também
interessantíssima para a resolução de problemas.
Uma consideração é importante mencionar: conforme você já deve imaginar, existem muitas técnicas de PO e,
evidentemente, você não verá todas. Nem mesmo os grandes especialistas de Pesquisa Operacional conseguem
acompanhar todo o desenvolvimento da área. Mas fique tranquilo: as principais e mais utilizadas técnicas serão
abordadas, o que fará com que você tenha uma vasta noção de modelagem. A partir daí, caso sua necessidade
futura dentro do ambiente empresarial venha a pedir novas técnicas, você saberá exatamente de onde partir
para conseguir chegar até lá.
1.2 Problemas de Programação Linear (PPLs)
A Programação Linear (PL) é uma das mais poderosas, eficientes e eficazes ferramentas dentro da Pesquisa
Operacional. Devido a sua importância, os estudos de PO geralmente se iniciam a partir dessa técnica. Além
disso, diversos outros problemas podem ser convertidos em PPLs, para serem resolvidos pelos métodos
tradicionais de PO, como os modelos em rede/grafos, que serão vistos na próxima subseção.
A PL é uma técnica que produz resultados significativos dentro do contexto da PO, reduzindo sistemas reais em
um conjunto de equações e/ou inequações lineares (BELFIORE; FÁVERO, 2013), ou seja, estas devem conter
apenas incógnitas de primeiro grau. Antes de começarmos a modelar um PPL, saibamos o que nele devem
•
•
•
VOCÊ O CONHECE?
Felipe Martins Müller é o atual presidente da Sociedade Brasileira de Pesquisa Operacional.
Graduado, mestre e doutor em Engenharia Elétrica, o pesquisador tem muita experiência na
área de PO, tendo em seu currículo mais de 150 publicações na área, além de ter orientado
diversos alunos em nível de graduação e pós-graduação. É professor da Universidade Federal
de Santa Maria, no Rio Grande do Sul (CURRÍCULO LATTES, 2019).
- -5
um conjunto de equações e/ou inequações lineares (BELFIORE; FÁVERO, 2013), ou seja, estas devem conter
apenas incógnitas de primeiro grau. Antes de começarmos a modelar um PPL, saibamos o que nele devem
constar os itens a seguir. Clique nas abas.
Variáveis de decisão
Uma etapa muito importante do problema, as variáveis de decisão descrevem as decisões a serem tomadas
(WINSTON, 2004). Geralmente, estão relacionadas à quantidade de produção, quando se trata de PPLs. Então,
por exemplo, em um modelo que se quer determinar quantas unidades de cada produto dentro de um portfólio
devem ser produzidas para se alcançar o maior lucro, cada produto terá uma variável de decisão x_i, que
assumirá um valor ao fim da resolução do modelo. Esse valor é exatamente a quantidade que deve ser produzida
de cada item.
Função objetivo
Esta define aquilo que o tomador de decisão precisa para seu problema, seja maximizar o seu retorno ou
minimizar o seu custo (BELFIORE; FÁVERO, 2013). Nesta função, os coeficientes das variáveis de decisão
acompanham os valores que cada uma dessas variáveis representa no objetivo, da seguinte forma: considerando
que a variável de decisão x_1 represente a quantidade a ser produzida de um item e esse item gere um lucro de
R$ 10,00, então, na função objetivo de maximizar o lucro, essa representação será feita como: max 〖10 x〗_1… e
assim sucessivamente, até que todas as variáveis que contribuam com o objetivo sejam aqui representadas.
Restrições
São descritas por meio de equações e/ou inequações lineares que correspondem a requisitos básicos para que o
modelo seja viável e totalmente parecido com a realidade. Geralmente, estão relacionadas às disponibilidades do
sistema, seja de matérias-primas, mão de obra, recursos tecnológicos etc. (BELFIORE; FÁVERO, 2013). Esse
passo é de extrema importância, pois é o que transforma o problema real em um problema matemático. Os
coeficientes das variáveis de decisão em uma restrição acompanham o quanto essa variável afeta dentro da
restrição. É usual as restrições serem escritas em forma de inequações (≤,≥), que representam a quantidade
máxima ou mínima que um recurso deve ser utilizado no modelo.
Agora, é hora de praticar o que você viu até aqui. Leia o texto a seguir.
E a parte mais interessante da PL: sua aplicabilidade. A Programação Linear pode ser usada para resolução de
problemas das mais variadas áreas existentes, principalmente no contexto produtivo. Pode determinar a
quantidade de cada produto a ser fabricado, dentro de um portfólio de uma empresa ou, até mesmo, determinar
as quantidades ótimas de cada matéria-prima que compõe um produto, visando a minimizar os custos de
produção. Podem também, na área financeira, determinar quais são as aplicações mais interessantes para se
selecionar em uma carteira de investimentos.
Ainda, na logística, métodos de PL podem ser utilizados para determinação de rotas mais curtas entre um Centro
VAMOS PRATICAR?
Agora você já conhece os componentes de um Problema de Programação Linear: as variáveis
de decisão, as restrições e a função objetivo. Antes de prosseguir a leitura, faça o seguinte:
imagine um problema que você precise os custos ou os lucros. Pode serminimizar maximizar
de uma lanchonete que você costuma frequentar. Pense que o gestor do lugar o contratou para
auxiliar na tomada de decisão. Elabore o problema e descreva, suscintamente, quais seriam os
componentes envolvidos nesse problema: as variáveis, as restrições e a função objetivo. Ao
prosseguir a leitura da unidade, repare nos aspectos que você acertou e os que ficaram a
desejar, para ficar ainda mais claro o entendimento do conteúdo.
- -6
Ainda, na logística, métodos de PL podem ser utilizados para determinação de rotas mais curtas entre um Centro
de Distribuição (CD) e outro (ou vários outros) cliente(s), ou pode-se, então, utilizar o método apresentado na
próxima subseção. Na mineração, é muito comum o uso de PO na determinação da composição do minério de
ferro, o que chamamos de blendagem mineral.
Legal, mas ciências exatas devem ser aprendidas na prática, não é mesmo? Então, acompanhe esse exemplo,
retirado da obra de Silva (2010, p. 5), para ficar ainda mais claro o que estamos vendo sobre a modelagemet al. 
de PPL.
Exemplo 1
Certa empresa fabrica dois produtos: P1 e P2. O lucro unitário do produto P1 é de R$ 1.000,00, e o lucro de P2 é
R$ 1.800,00. A empresa precisa de 20 horas para fabricar uma unidade de P1, e de 30 horas para fabricar uma
unidade de P2. O tempo anual de produção disponível para isso é de 1.200 horas. A demanda esperada para cada
produto é de 40 unidades anuais para P1, e 30 unidades anuais para P2. Sendo assim, qual seria o plano de
produção para que a empresa maximize seu lucro nesses itens? Construa o modelo de PPL para esse caso.
Esse é um clássico problema de de produção. Para a modelagem desse problema, precisamos destacar osmix
três itens que acabamos de definir:
a) Variáveis de decisão: como a decisão é um plano de produção, as variáveis correspondem a quantos
produtos de cada, P1 e P2, devem ser produzidos.
Assim, as variáveis de decisão do modelo são:
b) Função objetivo: o próprio enunciado traz que se trata de um problema de maximização de lucro. Como cada
produto rende um lucro específico, a f.o fica da seguinte forma:
Assim, como as variáveis de decisão são responsáveis por, ao fim do modelo, trazer a quantidade a ser produzida
de cada item, ao substituirmos seus valores na função objetivo, será dado o valor do lucro gerado pela
otimização, que é o maior lucro possível do problema, segundo suas características.
c) Restrições: são definidas pelo próprio enunciado. Devem ser cuidadosamente analisadas, de modo que
retratem exatamente o problema real.
- Restrições de horas disponíveis para a produção: sabendo-se que existem 1.200 horas disponíveis para esse
plano e que o produto P1 exige 20 horas de fabricação e o P2 necessita de 30 horas, essa restrição fica assim:
- Restrições de demanda: cada produto, segundo o problema, possui uma demanda mínima, que deve ser
cumprida no plano de produção para evitar perda de vendas. Note que, como se trata de demandaesperada, as
restrições são de fabricar no máximo o que se espera para evitar geração de estoques.
Esses dois conjuntos de restrições, que geraram três inequações lineares, formam o conjunto denominado
VOCÊ QUER VER?
Quer fixar ainda mais o entendimento do conteúdo? Então, assista aos vídeos Pesquisa
 (IFORMEI VIDEO AULAS, 2015a; 2015b).operacional – modelagem em programação linear
Neles são abordados dois problemas de Programação Linear, os quais são mostrados passo a
passo. Além disso, poderão ficar ainda mais claros os conceitos de função objetivo, variáveis de
decisão e restrições.
- -7
Esses dois conjuntos de restrições, que geraram três inequações lineares, formam o conjunto denominado
restrições técnicas do modelo. Ainda, todos os problemas de PL devem apresentar as restrições de nãosempre
negatividade, que garantem que as variáveis de decisão não assumam valores negativos, por uma questão lógica:
pode-se produzir ou deixar de produzir itens, porém produzir negativamente é impossível.
Dessa forma, as restrições de não negatividade do exemplo são:
Pronto, o problema está todo modelado. Em resumo, sua representação fica da seguinte forma:
Sujeito a
E como seria, então, a formulação de um problema que visa à minimização? Bom, é um modelo de PPL que segue
as mesmas lógicas do de maximização: possui as variáveis de decisão, a função objetivo e, claro, as restrições –
porém, a meta do problema é outra. Venha ver.
Viu só que legal? Não é incrível esse poder de transformar um problema real em um conjunto de funções
matemáticas a serem resolvidas por métodos exatos, a fim de trazerem a solução ótima do problema?
CASO
O custo de produção do produto A é de R$ 50,00, e do produto B é de R$ 60,00. O setor de
marketing define que a produção de A e B deve ser, no mínimo, 100 e 200 itens,
respectivamente. Para a produção de A, necessita-se de 40 kg de matéria-prima, ao passo que
B exige 30 kg. O total de matéria-prima disponível são 200 kg mensais. Qual o modelo de
fabricação que retorne no mínimo custo?
Analogamente ao exemplo anterior, neste, as variáveis de decisão são:
O modelo fica assim:
Sujeito a
- -8
Lembre-se de um detalhe importante: quando se fala em uma , quer dizer que, dentro do contextosolução ótima
do problema, considerando as suas restrições e sua função objetivo, ela é aquela que traz o melhor valor global
do problema, ou seja, o máximo de retorno possível em uma função de maximizar, ocorrendo, de forma análoga,
para funções de minimizar.
Existe também o conceito de que, diferentemente da anterior, não necessariamente é a ótimasolução otimizada
global, mas pode ser uma ótima local. Geralmente, esse termo é utilizado em problemas qualitativos, em que
encontrar o ótimo global é uma tarefa complexa. Portanto, grande parte dos problemas com solução ótima
advém do tipo determinístico, porém a recíproca não é verdadeira: nem todo problema determinístico gerará
uma solução ótima, podendo, então, responder a uma solução otimizada.
1.3 Problemas em grafos
Agora que já conhecemos uma parte importante da Pesquisa Operacional, a Programação Linear, sigamos para
outro tipo de modelagem também bastante aplicável em diversos conceitos de Engenharia: as que, nesseredes
contexto, apresentam-se como similares a grafos, são conjuntos de nós, ligados por arcos (ou ramos).
Cada nó representa algo fixo, como a localização de um cliente ou fornecedor, uma cidade etc. Os arcos, que
ligam esses nós, representam as possibilidades e capacidades de conexão entre os nós. Em cada rede existe a
associação de um fluxo, que geralmente é limitado pela capacidade de cada arco que conecta dois nós.
Nesta subseção, serão utilizados exemplos e demonstrações do livro de Taha (2008) que, além de apresentar a
PO em redes de uma forma muito clara e de fácil entendimento, é uma das obras de referência da disciplina, que
podem auxiliá-lo a compreender ainda melhor os conteúdos abordados.
Para melhor entendimento, veja um exemplo de rede abaixo:
Figura 2 - Exemplo de rede.
Fonte: TAHA, 2008, p. 105.
VOCÊ QUER LER?
Quer ver como é aplicada, na prática das indústrias, a PL? Veja como foi utilizada a técnica para
a solução de um problema fabril. No artigo de Barbosa (2014), você também conseguirá
observar todos os detalhes da formulação do problema, igualmente fizemos aqui.
- -9
Por definição, os nós e arcos dessa rede são:
N= {1, 2, 3, 4, 5} – os cinco nós existentes;
A= {(1,2), (1,3), (2,3), (2,5), (3,4), (3,5), (4,2), (4,5)} – as oito conexões existentes entre os nós.
Um arco pode ser (ou dirigido) se ele possuir fluxo em determinada direção, apenas. É o caso de arcosorientado
com setas: o arco (1,2) do exemplo permite fluxo de 1 para 2, mas não permite o inverso. Uma érede orientada
composta por todos os seus arcos orientados. Um é uma sequência de arcos distintos que conectamcaminho
dois nós, passando por outros nós. Uma é uma rede que conecta um subconjunto de nós, enquanto uma árvore
 é uma árvore que conecta todos os nós presentes na rede (TAHA, 2008).árvore geradora
Ainda do exemplo exibido na figura, veja outros exemplos de árvore e árvore geradora:
Figura 3 - Exemplos de árvore e árvore geradora.
Fonte: TAHA, 2008, p. 105.
Quando vir uma rede, certamente você imaginou diversos problemas que podem ser resolvidos com esse tipo de
modelagem, não é mesmo? Enumeraremos alguns, presentes também na literatura de Taha (2008). Clique nas
abas.
• Determinação de conexões mínimas entre pontos
Imagine um projeto que seja interligar algumas cidades com pavimentação asfáltica. Essas cidades
possuem diferentes conexões, e o projeto é fazer a conexão entre todas. Nesse caso, cada cidade será
representada por um nó, e as conexões entre elas pelos arcos. O objetivo é encontrar a árvore geradora
mínima que interligue esses pontos.
• Determinação do caminho mínimo entre um ponto a outro
Um Centro de Distribuição (CD) pode estar presente em um nó de uma rede e seus clientes
representados nos outros nós. A utilização de algoritmos de caminho mínimo permite dizer, com
exatidão, quais são os caminhos a serem seguidos para se chegar de um nó ao outro com a menor
distância possível.
• Determinação do fluxo máximo possível em uma rede
Muitos produtos podem ser escoados por uma rede de dutos, onde a origem e o destinatário são
definidos como nós, assim como os sistemas de bombeamento ao longo da rede, ao passo que os arcos
são os próprios dutos com suas respectivas capacidades de transferência de material. A aplicação do
algoritmo de fluxo máximo, nesse caso, viabiliza encontrar qual a quantidade máxima de material pode
ser escoada da origem ao destino, considerando a malha modelada. Analogias para circulação de carros
em estradas, por exemplo, podem ser aplicadas a esse caso.
•
•
•
- -10
• Determinação de durações de projetos
Projetos com atividades definidas podem ser modelados em formato de rede, onde os nós representam o
início e o fim de cada atividade, e essa atividade é definida por um arco, com capacidade igual à sua
duração. A modelagem da rede deve considerar as dependências entre as atividades, e a otimização da
rede trará aspectos relacionados ao tempo mínimo em que o projeto pode ser executado, quão cedo e
quão tarde pode-se iniciar e terminar cada tarefa e quais são as atividades críticas desse projeto, ou seja,
aquelas que dispendem mais atenção.
É hora de fixar os conceitos que vimos. Vamos lá? Leia o texto a seguir.
Definidos os tipos clássicos de modelagem em redes e grafos, tem-se uma ideia de como é a modelagem
relacionada a esses métodos da Pesquisa Operacional. Geralmente, as informações a serem transferidas a uma
modelagem em redes podem vir de um mapa, que apresenta as distâncias entre os pontos a serem conectados,
por exemplo.
Distância é um dos tipos de limitadores dos arcos das redes mais utilizados, porém outros tipos podem ser
empregados, dependendo da sua demanda: custos de transporte, transação, quantidade suportada de tráfego
por unidade de tempo e outros tambémpodem ser usados com a devida interpretação.
Similar às PPLs, os problemas em redes também precisam de objetivo e restrições, porém são realizados de uma
maneira diferente. O objetivo, geralmente, está ligado a uma das quatro opções que listamos acima, seja
minimizar distâncias, maximizar fluxos etc. Já as restrições são dadas ao desenhar a rede, que consiste na
definição das possíveis conexões e seus limitadores. Uma observação muito importante é notar se o arco é
direcional ou não.
Caso o arco seja direcional, ele comportará apenas um valor, que é o quantitativo suportado para a direção. Um
arco bidirecional deverá ter dois valores, isto é, o valor que ele suporta no processo de ida e no processo de
volta, considerando o caminho de um nó para o outro. Caso, em arcos bidirecionais, seja dado apenas um valor,
indica que ele é válido para a ida e para a volta. Veja o exemplo a seguir, retirado da obra de Taha (2008):
•
VAMOS PRATICAR?
Agora você já conhece os quatro principais tipos de problemas dentro do contexto da
Engenharia, que podem ser modelados e resolvidos por meio de grafos. Para exercitar a
aplicabilidade, pense em problemas reais que você vive em seu cotidiano que poderiam ser
resolvidos por Pesquisa Operacional. Imagine o fluxo de carros em ruas e rodovias, a conexão
de cabos de energia da cidade... Levante os casos e assimile cada um a um tipo de rede que
pode auxiliar na otimização.
- -11
Figura 4 - Exemplo de rede bidirecional.
Fonte: TAHA, 2008, p. 107.
Conforme podemos verificar na rede apresentada na figura anterior, como não apresenta setas, os fluxos são
bidirecionais, ou seja, a uma milha de distância entre os nós 1 e 2 é válida tanto de 1 indo para 2 quanto de 2
indo para 1. Essa rede pode ser utilizada para diversos casos: pode-se requerer a conexão entre todas as cidades
com a menor distância possível; pode-se querer sair do nó 1 e ir até o nó 6 usando-se o menor caminho possível
(note que existem várias possibilidades de se fazer esse trajeto); e também pode-se imaginar que isso seja uma
rota de estradas, em que os valores apresentam a quantidade (em milhares) de carros por hora que cada pista
(arco) consegue escoar, visando a encontrar qual o fluxo máximo de carros essa malha viária comporta.
 Adaptação à necessidade específica é um dos termos próprios quando o assunto é Pesquisa Operacional. Os
modelos clássicos são apresentados de forma que você desenvolva o conhecimento e, quando submetido a
aplicações práticas, saiba exatamente qual o modelo se encaixa melhor para a resolução do problema, mesmo
que sejam necessárias adaptações no que se encontra na literatura.
1.3.1 Pesquisa Operacional aplicada à Gestão de Projetos
Como visto, as redes podem apresentar similaridades na construção, mantendo objetivos diferentes, porém
algumas delas possuem formas peculiares de serem construídas, como é o caso das redes relacionadas a projetos.
Para a modelagem de problemas em projetos, são utilizadas as técnicas Program Evaluation and Review
(PERT) e (CPM), as quais, por mais que tenham sido desenvolvidas de formaTechnique Critical Path Method 
independente na década de 1950, são corriqueiramente utilizadas simultaneamente, apenas como técnica PERT
/CPM (TUBINO, 2009).
Uma rede PERT/CPM, portanto, é formada por um conjunto de nós e arcos, em que os nós apresentam os inícios
e o fim das atividades – as quais são representadas pelos arcos. Os arcos, por sua vez, trazem a duração de cada
atividade. A construção da rede em si representa as dependências entre as atividades. É importante ressaltar que
existem três regras para construção da rede (TAHA, 2008). Clique nos itens para conhecê-las.
- -12
1ª regra
Cada atividade é representada por um, e apenas um, arco.
2ª regra
Cada atividade deve ser identificada por dois nós finais distintos.
3ª regra
Todas as relações de precedência devem ser respeitadas.
Para garantir que as três regras sejam cumpridas, observe a figura a seguir. Como as regras não permitem a
primeira representação, foram criadas aquilo que chamamos de , que são utilizadasatividades fantasmas
apenas para garantir a dependência entre atividades. É feita por um arco tracejado, de nome qualquer, com
duração igual a zero. Na primeira representação do segundo retângulo, por exemplo, está mostrando que, para
iniciar qualquer atividade a partir do nó 3, as atividades A e B já devem ter sido concluídas.
Figura 5 - Atividades fantasmas para redes.
Fonte: TAHA, 2008, p. 125.
- -13
Fonte: TAHA, 2008, p. 125.
A primeira parte de todo problema de PO é a modelagem, e aqui não é diferente. Após a modelagem é que podem
seguir os demais cálculos que auxiliarão na otimização. Por enquanto, preocupemo-nos apenas com a construção
da rede PERT/CPM, que será exibida a seguir, em um exemplo extraído de Tubino (2009).
Exemplo 2
No quadro a seguir, é apresentada a lista de atividades de um projeto, com suas respectivas durações e
dependências. Pede-se que seja modelada a rede PERT/CPM que represente o problema.
Quadro 1 - Lista de atividades e dependências.
Fonte: Elaborado pelo autor, baseado em TUBINO, 2009.
As atividades apresentadas vão de acordo com cada projeto. Esse é um modelo genérico, mas poderia se tratar
de qualquer projeto, como a construção de um edifício, um evento de casamento etc. Mais detalhes de projetos
são encontrados em literaturas e disciplinas específicas, cabendo à PO se preocupar apenas na otimização deles.
Para a montagem da rede, o quadro como um todo deve ser observado. Primeiramente, parte-se daquelas
atividades que não possuem nenhuma dependência, no caso, as atividades A e B. Assim, do primeiro nó dessa
rede, que aqui também podemos chamar de evento, saem essas duas atividades com suas respectivas durações.
Posteriormente, as atividades seguintes são representadas respeitando suas dependências. Note que a atividade
C depende da conclusão da atividade A, portanto, seu nó de início é comum ao nó de fim da atividade A.
Duas são as atividades que dependem da finalização da atividade B: portanto, do nó (evento) de conclusão da
atividade B, sairão dois arcos com as atividades D e E. Essa lógica se repete até o fim da modelagem, que é
apresentada na figura a seguir.
- -14
Figura 6 - Modelagem da rede do problema.
Fonte: Elaborada pelo autor, baseada em TUBINO, 2009.
Legal, vimos como é modelada uma rede PERT/CPM, mas ainda faltou um detalhe que foi mencionado: a
utilização de atividades fantasmas. Agora, vejamos um exemplo retirado de Taha (2008) utilizando o conceito de
caminho fantasma.
Exemplo 3 
Construa a rede PERT/CPM das atividades listadas no quadro a seguir.
Quadro 2 - Lista de atividades e dependências.
Fonte: Elaborado pelo autor, baseado em TAHA, 2008.
Seguindo as regras já mencionadas, a modelagem desse problema se dá assim:
- -15
Seguindo as regras já mencionadas, a modelagem desse problema se dá assim:
Figura 7 - Modelagem da rede do problema.
Fonte: TAHA, 2008, p. 125.
Assim como no exemplo anterior, as atividades A, B, C e D, sem dependências, partem do evento inicial (1). Como
a atividade E depende da finalização das atividades A e B, é criada uma atividade fantasma de duração zero, para
garantir que a atividade E apenas se inicie quando A e B tenham sido completadas.
Agora você já conhece os quatro tipos principais de redes e como cada um deles é modelado. Use a abuse desse
conhecimento em prol da otimização dos problemas que possam vir a ficar sob sua responsabilidade no futuro.
1.4 Fundamentos matemáticos da PO
Como você já deve ter percebido no decorrer desta unidade, a Pesquisa Operacional demanda de muitos
conceitos matemáticos para sua modelagem, resolução e análise, principalmente de conceitos relacionados à
álgebra linear, para os Problemas de Programação Linear, certo? Já que existem várias funções lineares,
conceitos como resolução de sistemas lineares, por exemplo, são muito úteis dentro dessa área.
Imagine a solução deste tipo de problema: você possui uma função objetivo e algumas restrições, todasem
formato de equações ou inequações lineares. Como ambas tratam do mesmo assunto, podem ser traçadas dentro
de um plano cartesiano, por exemplo, para buscar a solução por meio de técnicas matemáticas.
VAMOS PRATICAR?
Acabamos de conhecer a modelagem de redes do tipo PERT/CPM. Vimos que devemos
obedecer às dependências das atividades e, quando necessário, utilizarmos os caminhos
fantasmas. Agora, faremos algo para você levar para a prática os conceitos aqui estudados:
analisando a rede modelada na Figura 7, delineada pelo Quadro 2, esboce nesse quadro um
projeto real: imagine um projeto que deva possuir essas atividades e suas respectivas
dependências, como um casamento, a realização de um churrasco, a abertura de uma empresa,
enfim... Faça o ‘fluxo reverso’ da modelagem, para entender a aplicabilidade do conceito.
- -16
Já para os problemas em redes que vimos, as lógicas que devem estar na nossa cabeça estão relacionadas ao que
o problema deseja e como é feita a relação dos arcos e nós. A partir daí, busca-se o objetivo.
A sugestão, no momento, é que você entenda como é feita a transformação de problemas reais em métodos
matemáticos. Em hipótese alguma deixe de transformar alguma restrição de sua realidade em uma restrição
matemática, pois isso pode descaracterizar totalmente sua otimização. Além disso, quando for planejar uma
rede, trace exatamente todas as conexões possíveis com suas respectivas capacidades. Se os mesmos arcos
possuírem diferentes capacidades, não deixe de deixar isso claro também, para que a solução traga a resposta
ótima.
Síntese
Acabamos de conhecer, nesta unidade, os conceitos introdutórios de Pesquisa Operacional, ciência responsável
por auxiliar gestores na tomada de decisão nos mais variados níveis organizacionais. A princípio, conhecemos os
fundamentos principais de um modelo de PO, que estão relacionados à modelagem do problema.
Nesta unidade, você teve a oportunidade de:
• ser apresentado à Pesquisa Operacional, ciência responsável por transformar os problemas reais em 
modelos matemáticos;
• ver que, assim como outras importantes ciências, a PO surgiu durante o período da Segunda Guerra 
Mundial;
• aprender que existem várias técnicas diferentes de PO, em que cada uma é aplicável em determinados 
tipos de problemas;
• conhecer a Programação Linear, a função objetivo, as variáveis de decisão e as restrições e como é 
modelado um problema por meio dessa técnica;
• acompanhar os principais tipos de programação em redes/grafos, além de ver como é a transformação 
de uma lista de atividades de projetos em uma rede matemática;
• entender alguns conceitos da matemática que são necessários para o completo entendimento da 
Pesquisa Operacional.
VOCÊ SABIA?
A Programação Linear trabalha com várias soluções que atendem às restrições do problema,
denominadas , e dentro dessas soluções viáveis, existe aquela que retorna osoluções viáveis
valor máximo (em funções de ) ou mínimo (em funções de ), as quais são denominadas max min
. Uma solução ótima é sempre viável, mas a recíproca não é verdadeira. Umsoluções ótimas
problema pode apresentar mais de uma solução ótima, contanto que o valor da função
objetivo, para as diferentes soluções, seja o mesmo.
•
•
•
•
•
•
- -17
Bibliografia
ANDRADE, E. L. : métodos e modelos para análise de decisões. 4. ed. Rio deIntrodução à pesquisa operacional
Janeiro: LTC, 2009.
ARENALES, M. N. . Rio de Janeiro: Elsevier, 2007.et al. Pesquisa operacional 
BARBOSA, G. M. Utilização da programação linear na otimização de resultados de produção na empresa. Revista
, São Paulo, USJT, ano XX, n. 66, p. 49-58, 2014. Disponível em: Integração https://www.usjt.br/prppg/revista
. Acesso em: 21 jul. 2019./integracao/assets/pdf/66/ri-2014-art9-barbosa.pdf
BELFIORE, P.; FÁVERO, L. P. : para cursos de administração, contabilidade e economia.Pesquisa operacional 
Rio de Janeiro: Elsevier, 2013.
CURRÍCULO LATTES. . Disponível em: Felipe Martins Müller http://buscatextual.cnpq.br/buscatextual
. Acesso em: 21 jul. 2019./visualizacv.do?id=K4723058U1
GOLDBARG, M. C.; LUNA, H. P. L. : modelos e algoritmos. 2. ed.Otimização combinatória e programação linear 
Rio de Janeiro: Elsevier, 2005.
HILLIER, F. S.; LIEBERMAN, G. J. . 9. ed. São Paulo: McGraw-Hill, 2013.Introdução à pesquisa operacional
IFORMEI VIDEO AULAS. – Modelagem em programação linear I. 4 nov. 2015a. DisponívelPesquisa operacional
em: . Acesso em: 20 jul. 2019.https://www.youtube.com/watch?v=vHEbb2hko8k
IFORMEI VIDEO AULAS. – Modelagem em programação linear II. 4 nov. 2015b.Pesquisa operacional
Disponível em: . Acesso em: 20 jul. 2019.https://www.youtube.com/watch?v=uTVQQhtuqxU
MURTHY, P. R. . 2. ed. New Delhi: New Age International Publication, 2007.Operations research
SILVA, E. M. : para os cursos de administração e engenharia. 4. ed. São Paulo: Atlas,et al. Pesquisa operacional 
2010.
TAHA, H. A. . 8. ed. São Paulo: Pearson, 2008.Pesquisa operacional
TUBINO, D. F. : teoria e prática. Planejamento e controle da produção 2. ed. São Paulo: Atlas, 2009.
WINSTON, W. L. . Operations research, applications and algorithms 4. ed. Belmont: Thomson Learning, 2004.
https://www.usjt.br/prppg/revista/integracao/assets/pdf/66/ri-2014-art9-barbosa.pdf
https://www.usjt.br/prppg/revista/integracao/assets/pdf/66/ri-2014-art9-barbosa.pdf
http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4723058U1
http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4723058U1
https://www.youtube.com/watch?v=vHEbb2hko8k
https://www.youtube.com/watch?v=uTVQQhtuqxU
	Introdução
	1.1 Definição e contexto histórico
	Modelos determinísticos
	Modelos estocásticos
	Outros modelos advindos do avanço computacional
	1.2 Problemas de Programação Linear (PPLs)
	1.3 Problemas em grafos
	Determinação de conexões mínimas entre pontos
	Determinação do caminho mínimo entre um ponto a outro
	Determinação do fluxo máximo possível em uma rede
	Determinação de durações de projetos
	1.3.1 Pesquisa Operacional aplicada à Gestão de Projetos
	1.4 Fundamentos matemáticos da PO
	Síntese
	Bibliografia