Pesquisa Operacional

Prévia do material em texto

2009
Pesquisa OPeraciOnal
Prof. Paulo Afonso Lunardelli
Prof. Roy Wilhelm Probst
Copyright © UNIASSELVI 2009
Elaboração:
Prof. Paulo Afonso Lunardelli
Prof. Roy Wilhelm Probst
Revisão, Diagramação e Produção:
Centro Universitário Leonardo da Vinci – UNIASSELVI
Ficha catalográfica elaborada na fonte pela Biblioteca Dante Alighieri 
UNIASSELVI – Indaial.
003
L961p Lunardelli, Paulo Afonso.
Caderno de Estudos: Pesquisa Operacional/ Paulo Afonso 
Lunardelli [e] Roy Wilhelm Probst. Centro Universitário 
Leonardo da Vinci – Indaial: Grupo UNIASSELVI, 2009. x ; 
138 p. : il.
Inclui bibliografia.
ISBN 978-85-7830-212-2
1. Pesquisa Operacional
2. Teoria de Sistema
I.Centro Universitário Leonardo da Vinci
II. Probst, Roy Wilhelm
III. Núcleo de Ensino a Distância
III
aPresentaçãO
Caro(a) acadêmico(a)!
A Segunda Guerra Mundial foi o marco inicial para os estudos da 
Pesquisa Operacional. A convocação de um grupo de cientistas ingleses para 
estudar problemas de estratégia para a defesa do país levou-os a pesquisar as 
operações e recursos militares mais eficazes no campo de batalha.
Logo os Estados Unidos perceberam o grande avanço desencadeado 
pelos cientistas da Inglaterra e começaram a estudar atividades semelhantes. 
Os métodos mais conhecidos hoje na área de Pesquisa Operacional têm 
fontes reconhecidas nos trabalhos de equipes como a liderada por George B. 
Dantzig, dos Estados Unidos, convocada durante a Segunda Guerra Mundial, 
em 1947, com seu Método Simplex. 
Ao término da guerra, ficou o aprendizado e as técnicas de Pesquisa 
Operacional logo caíram no agrado de outras áreas, especialmente a 
administração e a economia. As indústrias perceberam a grande ideia do 
planejamento e as técnicas desenvolvidas para a tomada de decisões fizeram-
nas observar os processos industriais com outros aspectos e melhoras 
significativas foram sendo elaboradas com o passar dos anos.
O avanço da informática trouxe mais facilidade na elaboração de 
projetos cada vez mais arrojados, e o uso de computadores mais rápidos e 
sofisticados trouxe modernidade aos métodos que já faziam grande diferença 
na competitividade do mercado. 
A Pesquisa Operacional firmou-se como ferramenta imprescindível 
nas diversas áreas do conhecimento, fazendo com que sua aplicação, em 
conjunto com a intuição e o know-how de grandes setores do mercado, seja de 
fundamental importância na busca de avanços no planejamento de processos.
“A modelagem matemática, atualmente usada, tem contribuído 
sobremaneira para a evolução do conhecimento humano, seja nos fenômenos 
microscópicos, em tecnobiologia, seja nos macroscópicos, com a pretensão 
de conquistar o universo. Mas não é um processo próprio dos cientistas”. 
(BIEMBENGUT, 2002, p. 17). 
Assim, nossos estudos voltam-se para a pesquisa operacional, 
buscando novos conhecimentos que melhorem não apenas nossa qualidade 
de vida como indivíduo, mas também a de todos em nossa volta.
E a você, caro(a) acadêmico(a), bons estudos e que este caderno seja 
uma referência nos trabalhos de sucesso que lhe aguardam em breve.
Professor Paulo Afonso Lunardelli
Professor Roy Wilhelm Probst
IV
Você já me conhece das outras disciplinas? Não? É calouro? Enfim, tanto para 
você que está chegando agora à UNIASSELVI quanto para você que já é veterano, há 
novidades em nosso material.
Na Educação a Distância, o livro impresso, entregue a todos os acadêmicos desde 2005, é 
o material base da disciplina. A partir de 2017, nossos livros estão de visual novo, com um 
formato mais prático, que cabe na bolsa e facilita a leitura. 
O conteúdo continua na íntegra, mas a estrutura interna foi aperfeiçoada com nova 
diagramação no texto, aproveitando ao máximo o espaço da página, o que também 
contribui para diminuir a extração de árvores para produção de folhas de papel, por exemplo.
Assim, a UNIASSELVI, preocupando-se com o impacto de nossas ações sobre o ambiente, 
apresenta também este livro no formato digital. Assim, você, acadêmico, tem a possibilidade 
de estudá-lo com versatilidade nas telas do celular, tablet ou computador. 
 
Eu mesmo, UNI, ganhei um novo layout, você me verá frequentemente e surgirei para 
apresentar dicas de vídeos e outras fontes de conhecimento que complementam o assunto 
em questão. 
Todos esses ajustes foram pensados a partir de relatos que recebemos nas pesquisas 
institucionais sobre os materiais impressos, para que você, nossa maior prioridade, possa 
continuar seus estudos com um material de qualidade.
Aproveito o momento para convidá-lo para um bate-papo sobre o Exame Nacional de 
Desempenho de Estudantes – ENADE. 
 
Bons estudos!
NOTA
V
VI
VII
UNIDADE 1 – PROGRAMAÇÃO LINEAR .....................................................................................1
TÓPICO 1 - PROBLEMAS DE PROGRAMAÇÃO LINEAR ........................................................3
1 INTRODUÇÃO ...................................................................................................................................3
2 FORMULAÇÃO DE MODELOS DE PPL ......................................................................................3
3 MODELAGEM MATEMÁTICA ......................................................................................................5
3.1 INDÚSTRIA MOVELEIRA ...........................................................................................................6
3.2 PLANEJAMENTO DE PRODUÇÃO AGRÍCOLA ...................................................................8
3.3 DIETA ALIMENTAR .....................................................................................................................9
3.4 PROBLEMAS DE TRANSPORTE ................................................................................................11
RESUMO DO TÓPICO 1......................................................................................................................14
AUTOATIVIDADE ...............................................................................................................................15
TÓPICO 2 - SOLUÇÃO GRÁFICA DE PROBLEMAS DE PROGRAMAÇÃO LINEAR ........17
1 INTRODUÇÃO ...................................................................................................................................17
2 REPRESENTAÇÃO GRÁFICA ........................................................................................................17
3 VETOR GRADIENTE - ▼ Z .............................................................................................................20
4 CONSIDERAÇÕES SOBRE O MÉTODO GRÁFICO .................................................................22
RESUMO DO TÓPICO 2......................................................................................................................24
AUTOATIVIDADE ...............................................................................................................................25
TÓPICO 3 - PROGRAMAÇÃO LINEAR INTEIRA .......................................................................27
1 INTRODUÇÃO ...................................................................................................................................27
2 UM MODELO DE PL INTEIRA ......................................................................................................27
3 O MÉTODO DE BRANCH AND BOUND ......................................................................................29
3.1 CONSIDERAÇÕES SOBRE O MÉTODO DE BRANCH AND BOUND.................................33
4 APLICAÇÃO DE PLI ..........................................................................................................................34
4.1 CONSIDERAÇÕES FINAIS SOBRE A PLI ................................................................................39
LEITURA COMPLEMENTAR .............................................................................................................40
RESUMO DO TÓPICO 3......................................................................................................................44AUTOATIVIDADE ...............................................................................................................................45
UNIDADE 2 - SOLUÇÃO ÓTIMA .....................................................................................................47
TÓPICO 1 - MÉTODO SIMPLEX .......................................................................................................49
1 INTRODUÇÃO ...................................................................................................................................49
2 FORMA PADRÃO DO PPL ..............................................................................................................49
2.1 NÃO NEGATIVIDADE DA MÃO DIREITA .............................................................................50
2.2 VARIÁVEIS NÃO RESTRITAS ....................................................................................................50
2.3 VARIÁVEIS DE FOLGA ...............................................................................................................51
2.4 VARIÁVEIS DE EXCESSO ............................................................................................................52
2.5 ALTERAÇÕES NA FUNÇÃO OBJETIVO ..................................................................................53
3 O ALGORÍTMO SIMPLEX ...............................................................................................................53
4 TABLEAU SIMPLEX ...........................................................................................................................60
sumáriO
VIII
4.1 DEGENERESCÊNCIA...................................................................................................................67
4.2 MÉTODO DAS DUAS FASES ......................................................................................................68
5 DUALIDADE .......................................................................................................................................73
5.1 ALGORITMO PRIMAL-DUAL ....................................................................................................73
RESUMO DO TÓPICO 1......................................................................................................................78
AUTOATIVIDADE ...............................................................................................................................80
TÓPICO 2 - UTILIZAÇÃO DO COMPUTADOR ...........................................................................81
1 INTRODUÇÃO ...................................................................................................................................81
2 RESOLVENDO MODELOS NO EXCEL ........................................................................................82
3 ANÁLISE DE PÓS-OTIMALIDADE ..............................................................................................87
3.1 ANALISANDO A FUNÇÃO OBJETIVO ....................................................................................87
3.2 ANALISANDO OS COEFICIENTES DA MÃO DIREITA DAS RESTRIÇÕES ....................89
RESUMO DO TÓPICO 2......................................................................................................................91
AUTOATIVIDADE ...............................................................................................................................92
UNIDADE 3 - PROGRAMAÇÃO DE PROJETOS ..........................................................................93
TÓPICO 1 - ANÁLISE DE REDES......................................................................................................95
1 INTRODUÇÃO ...................................................................................................................................95
2 TEORIA DOS GRAFOS ....................................................................................................................95
2.1 O PROBLEMA DO CAIXEIRO VIAJANTE ...............................................................................97
2.2 PROBLEMAS DE FLUXO MÁXIMO ..........................................................................................100
2.3 PROBLEMAS DE CAMINHO MAIS CURTO ...........................................................................102
RESUMO DO TÓPICO 1......................................................................................................................108
AUTOATIVIDADE ...............................................................................................................................109
TÓPICO 2 - TÉCNICAS PERT/CPM ..................................................................................................111
1 INTRODUÇÃO ...................................................................................................................................111
2 APLICAÇÃO DE PERT/CPM ...........................................................................................................111
2.1 REDE DE ATIVIDADES ................................................................................................................112
2.2 CAMINHO CRÍTICO ....................................................................................................................113
2.3 PROGRAMAÇÃO DAS ATIVIDADES - PERT .........................................................................114
2.4 PROGRAMAÇÃO DAS ATIVIDADES – CPM .........................................................................118
RESUMO DO TÓPICO 2......................................................................................................................121
AUTOATIVIDADE ...............................................................................................................................122
TÓPICO 3 - SIMULAÇÃO ...................................................................................................................125
1 INTRODUÇÃO ...................................................................................................................................125
2 SIMULAÇÃO DE MONTE CARLO ...............................................................................................125
2.1 GERANDO NÚMEROS ALEATÓRIOS NO COMPUTADOR................................................126
3 PLANEJAMENTO DE SIMULAÇÕES ...........................................................................................128
3.1 EXEMPLO DE SIMULAÇÃO .......................................................................................................129
LEITURA COMPLEMENTAR .............................................................................................................132
RESUMO DO TÓPICO 3......................................................................................................................135
AUTOATIVIDADE ...............................................................................................................................136
REFERÊNCIAS .......................................................................................................................................137
1
UNIDADE 1
PROGRAMAÇÃO LINEAR
OBJETIVOS DE APRENDIZAGEM
PLANO DE ESTUDOS
A partir do estudo desta unidade, você será capaz de:
• reconhecer um Problema de Programação Linear (PPL);
• identificar as variáveis de decisão de um PPL;
• escrever a Função Objetivo de um modelo de PPL;
• escrever o conjunto de restrições de um modelo de PPL;
• reconhecer um modelo de Problema de Transporte;
• representar graficamente o conjunto de restrições de um PPL;
• representar o Vetor Gradiente da Função Objetivo;
• determinar a solução do PPL por via gráfica;
• construir um modelo de Programação Linear Inteira;
• resolver um modelo de PLI através do Método de Branch and Bound;
• representar a resolução de um PLI por diagramas.
Esta primeira unidade será dividida em três tópicos. No final de cada tópico, 
você encontrará atividades que contribuirãopara sua reflexão e análise dos 
estudos já realizados.
TÓPICO 1 – PROBLEMAS DE PROGRAMAÇÃO LINEAR
TÓPICO 2 – SOLUÇÃO GRÁFICA DE PROBLEMAS DE PROGRAMAÇÃO 
LINEAR
TÓPICO 3 – PROGRAMAÇÃO LINEAR INTEIRA
2
3
TÓPICO 1
UNIDADE 1
PROBLEMAS DE 
PROGRAMAÇÃO LINEAR
1 INTRODUÇÃO
Os Problemas de Programação Linear (PPL) são, em sua maioria, 
problemas de otimização que visam maximizar ou minimizar uma função linear 
de várias variáveis. Essa função é chamada de Função Objetivo (FO) e está sujeita 
a respeitar certo número de relações lineares de igualdade ou desigualdade, 
chamadas de restrições do problema.
Nesta unidade, estudaremos como é feita a formulação dos problemas de 
programação linear através da modelagem matemática, e como se dá a busca pela 
solução ótima de um PPL de duas variáveis através do método gráfico.
2 FORMULAÇÃO DE MODELOS DE PPL
Segundo Wagner (1985, p. 6), a construção de modelos é a essência da 
abordagem de pesquisa operacional. Normalmente, a formulação de um problema 
de PPL envolve três etapas:
1. A definição do objetivo básico do problema, ou seja, se queremos otimizar 
por meio de maximização (por exemplo, de lucros, ou de um processo que envolva 
tempo, ou desempenho, etc.) ou minimização (de custos, perdas, tempo etc.).
2. A escolha das variáveis de decisão envolvidas (como exemplo, podemos 
citar a colheita de algum tipo de alimento, cuja área destinada ao plantio de diversas 
espécies de alimentos é uma variável a ser decidida) para a formulação da Função 
Objetivo.
3. Escrever o sistema de restrições do PPL em relação às variáveis de decisão 
do problema (no caso da colheita, podem-se levar em conta as condições ambientais, 
a demanda pelos alimentos, a disponibilidade de mão de obra para plantio, a 
capacidade de estocagem etc.).
Deve-se tomar o cuidado para que todas as relações do PPL sejam, realmente, 
lineares.
UNIDADE 1 | PROGRAMAÇÃO LINEAR
4
Os problemas de PL ficam são definidos da seguinte maneira:
(max ou min)Z = c1x1 + c2x2 + ... + cnxn É a função objetivo
Neste modelo, interpretamos:
• x1, x2,...,xn como o conjunto de variáveis de decisão (estruturais) do problema
• c1, c2,...,cn são os coeficientes da função objetivo do problema de PL
• aij e bi são os coeficientes das restrições.
Loesch e Hein (1999, p. 20) chamam os coeficientes bi de coeficientes da 
mão direita. Utilizaremos essa nomenclatura para referenciá-los posteriormente. E 
ainda, para o Método Simplex de resolução de PPL, esses coeficientes deverão ser 
necessariamente não-negativos.
A última restrição é chamada restrição de não negatividade das variáveis 
de decisão. Normalmente, essa restrição é utilizada em problemas de PL cujas 
variáveis envolvidas não podem assumir valores negativos, como por exemplo, 
tempo, área, quantidade de mão de obra etc., afinal, não faria sentido falar em oito 
homens negativos trabalhando, por exemplo. Por outro lado, alguns problemas 
podem envolver variáveis que aceitam sinais negativos (como exemplo, podem-
se citar problemas que envolvam saldos bancários ou temperaturas).
Perceba, no modelo, que as restrições podem ter três opções de sinal ≤ 
(menor que ou igual a), ≥ (maior que ou igual a) e = (igual a). É claro que só 
podemos usar um sinal em cada restrição.
A função objetivo traduz o tipo de otimização que se deseja obter 
(maximização ou minimização, optando por uma das duas).
Todos os coeficientes, tanto da Função Objetivo, quanto das restrições são 
determinados na modelagem do problema. Já os valores das variáveis dependem 
de um algoritmo de resolução para serem calculados. Essas variáveis devem ser 
valores reais, mas, eventualmente, podem assumir valores inteiros, dependendo 
do tipo de problema que se deseja resolver. Se o problema for definir a quantidade 
de operários necessários a otimizar certa produção, não há sentido em declarar 
TÓPICO 1 | PROBLEMAS DE PROGRAMAÇÃO LINEAR
5
que a solução ótima é, por exemplo, 1,4 homens. Nesse caso, esse tipo de problema 
de PL é chamado de Problema de Programação Linear Inteira e estudaremos 
métodos de resoluções específicos para sua resolução, como o Método de Branch 
and Bound.
3 MODELAGEM MATEMÁTICA
A modelagem matemática é a mais importante etapa na resolução de 
problemas de PL, constitui o começo do trabalho na busca por soluções. Após 
a modelagem, podem ser usados vários métodos, inclusive computacionais, 
para a resolução, mas é na modelagem que a experiência e o conhecimento do 
pesquisador atuam com maior ênfase.
Para modelar um problema deve-se saber selecionar o que é mais 
importante para a resolução e, consequente, solução. Um trabalho em equipe, 
com profissionais de áreas diversas, que possam ajudar a esclarecer as variáveis 
do problema, é muito bem vindo. Geralmente, a multidisciplinaridade contribui, 
e muito, para uma melhor formação do modelo, tendendo a uma melhor solução 
para o mesmo.
Conforme Loesch e Hein (1999, p. 21):
Um modelo é uma representação da realidade. Através de um modelo 
procura-se capturar os aspectos relevantes de algum problema ou 
sistema e representar a situação. Os modelos matemáticos constituem 
uma abstração da realidade, representada por um conjunto de 
equações e relações.
Alguns aspectos devem ser considerados na formulação de um modelo 
de PPL:
• se existir a possibilidade, pode-se separar o problema em um grupo de 
problemas menores, resolvendo-os, resolve-se o problema todo;
• as variáveis de decisão devem ser cuidadosamente selecionadas e definidas (se 
é real ou inteira, qual sua unidade de medida e se pode ser negativa ou não);
• definir claramente o objetivo, a meta a ser alcançada. Se maximizar ou 
minimizar as variáveis, e qual a função objetivo;
• construir a rede de relações entre as variáveis, seus limites ou fatores restritivos. 
Determinar o sistema de restrições do problema;
• deve-se verificar a possibilidade de haver aspectos ou situações que sejam 
repetitivas, redundantes, ou que não tragam relevância à solução do problema. 
Muitas restrições podem fazer o modelo ficar muito grande e talvez sua 
resolução seja impraticável. Conferir a necessidade de trabalhar com algumas 
dessas restrições, ou não, é uma boa prática.
UNIDADE 1 | PROGRAMAÇÃO LINEAR
6
Podemos dizer que modelar é uma arte e, por isso, a experiência é um 
fator importante para que se tenha um bom modelo. A prática, o treinamento, o 
estudo de casos, o comprometimento com o problema, as informações extras que 
possam ser levantadas sobre ele, tudo isso leva a uma melhor formulação de um 
modelo matemático.
Para que você possa ver como tudo isso funciona, selecionamos alguns 
exemplos de situações reais (com algumas considerações, é claro) e os modelamos 
em termos de problemas de programação linear com sua função objetivo e suas 
restrições. Confira:
Problema: Uma grande fábrica de móveis dispõe em estoque de 800m de 
tábuas, 600m de pranchas e 500m de painéis de conglomerado. A fábrica oferece 
uma linha de móveis composta pelos seguintes produtos: escrivaninha, mesa de 
reunião, armário e prateleira. Cada tipo de móvel consome certa quantidade de 
matéria prima, conforme a Tabela 1. A escrivaninha é vendida por R$ 100,00, a 
mesa por R$ 80,00, o armário por R$ 120,00 e a prateleira por R$ 20,00.
3.1 INDÚSTRIA MOVELEIRA
FONTE: Os autores
Modelagem: Vamos supor que o fabricante deseje obter o maior 
lucro possível com a venda de seus produtos, não nos preocupando com as 
especificidades do mercado consumidor, digamos que o que se produz se vende. 
Assim, nossa função objetivo é definida como uma busca pelo máximo lucro. Este 
será calculado através da venda dos produtos por seus respectivos valores, assim, 
é natural que tenhamos as seguintes variáveis de decisão:
XE=quantidade de escrivaninhas que a fábrica deve produzir;
XM=quantidade de mesas que a fábrica deve produzir;
XA=quantidade de armários que a fábrica deve produzir;
XP=quantidade de Prateleiras que a fábrica deve produzir.
TABELA 1 - DISTRIBUIÇÃODOS MATERIAIS DOS PRODUTOS
Quantidade de material consumido por produto Disponibilidade 
do materialEscrivaninha Mesa Armário Prateleira
Tábua 0 2 2 3 800
Prancha 2 0 1 1 600
Painel 2 1 2 0 500
Valor do 
produto 100 80 120 20 -
TÓPICO 1 | PROBLEMAS DE PROGRAMAÇÃO LINEAR
7
Escrevendo a função objetivo em termos de suas variáveis de decisão, 
temos;
max L = 100xE + 80xM + 120xA + 20xP , em que max L descreve o lucro 
máximo.
Com a função objetivo definida, passamos a formulação do sistema de 
restrições do modelo, escrevendo-os em função das variáveis de decisão. Vamos 
considerar cada um dos tipos de matéria-prima como uma restrição quanto ao uso 
da mesma em cada produto. Assim:
• Restrição quanto ao uso de tábuas: As unidades produzidas de mesa e 
de armário consomem 2m de tábuas cada, e cada unidade de prateleira 
produzida consome 3m de tábuas, mas não é necessário o uso de tábuas 
na produção de escrivaninhas. Lembrando que a fábrica dispõe de 800m 
de tábuas, podemos traduzir essas condições através da expressão 0xE 
+ 2xM + 2xA + 3xP ≤ 800. O sinal de ≤ indica que a fábrica pode consumir 
qualquer quantidade menor que 800m de tábuas ou igual a este valor.
• Restrição quanto ao uso de pranchas: A fábrica dispõe de 600m de pranchas, 
podendo distribuir 2m para cada escrivaninha produzida, 1m para cada 
armário e 1m para cada prateleira. Assim, escrevemos a restrição 2xE + 0xM + 
1xA + 1xP ≤ 600.
• Restrição quanto ao uso de painéis: Da mesma forma, temos 2xE + 1xM + 2xA + 0xP 
≤ 500. Dessa vez, xP fica de fora por não utilizar painéis em sua composição. E 
o limite de uso desse material é de até 500m.
• Essas são as restrições quanto ao uso dos materiais, mas devemos lembrar que 
estamos tratando de produção de unidades de móveis, e essa fábrica não pode 
produzir, ou vender, por exemplo, meio armário, ou uma mesa de reuniões e 
meia, ou então quatro prateleiras negativas. Desse modo, devemos restringir 
as variáveis de decisão para que sejam todas inteiras e não negativas, ou seja, 
maiores que zero, ou iguais a zero (pode-se optar pela não produção de um 
tipo de produto se isso significar um melhor lucro para a empresa).
Assim, nosso problema de PL fica traduzido no modelo:
max L = 100xE + 80xM + 120xA + 20xP Função Objetivo (maximizar o lucro)
Sujeito a
0xE + 2xM + 2xA + 3xP ≤ 800 Restrição ao uso de tábuas
2xE + 0xM + 1xA + 1xP ≤ 600 Restrição ao uso de pranchas
2xE + 1xM + 2xA + 0xP ≤ 500 Restrição ao uso de painéis
xE , xM , xA , xP ≥ 0 e inteiros Restrição à não negatividade e a natureza 
da variável
UNIDADE 1 | PROGRAMAÇÃO LINEAR
8
3.2 PLANEJAMENTO DE PRODUÇÃO AGRÍCOLA
Problema: Um sitiante, possuidor de 50 ares de terra fértil, está planejando 
sua estratégia de plantio para o próximo ano. Por informações obtidas nos órgãos 
governamentais, sabe-se que as culturas de trigo e milho serão as mais rentáveis 
na próxima safra. Por experiência, ele sabe que a produtividade de sua terra 
é de oito sacas por cada are cultivado de trigo, necessitando de três homens-
hora de trabalho por are, e dez sacas por cada are cultivado de milho, com dois 
homens-hora de trabalho por are. A mão de obra custa $100,00 por homem-hora 
e a disponibilidade é de 120 hh. Também é sabido que o mercado de consumo 
se limita a 240 sacas de trigo, vendidas a $75 cada uma, e 400 sacas de milho, 
vendidas a $60 cada uma.
Modelagem: Esse agricultor deseja planejar sua produção de modo a 
conseguir o maior lucro possível com o plantio desses dois produtos (ou um 
deles, se for o caso). Desse modo, nosso modelo representa, novamente, um 
problema de maximização de lucros, em que lucro é a diferença entre receita (o 
que se ganha) e custo (o que se gasta) da produção. Para as variáveis de decisão, 
usaremos então:
xT = quantidade de ares de terra destinados ao plantio de trigo;
xM = quantidade de ares de terra destinados ao plantio de milho.
A receita é proveniente da venda de seus produtos (venda das sacas de 
trigo e milho) e o custo vem dos gastos com mão de obra. Assim, nossa função 
objetivo será escrita com base nessas informações. Para o cálculo da receita, 
sabemos que 1 are de trigo rende 8 sacas do produto ao valor de $75 por saca, e, 
portanto, 1 are de trigo rende 8 • $75 = $600, e que um are de milho rende dez 
sacas do produto ao valor de $60 por saca, e, portanto, um are de milho rende 10 
• $60 = $600. Assim, a receita se resume a 600xT + 600xM.
Já os custos de mão de obra também podem ser calculados em função das 
quantidades de ares, já que um are de cultivo de trigo necessita de três homens-
hora ao custo de $100 por homem-hora, temos que um are de trigo custa 3 • $100 
= $300. E como um are de cultivo de milho necessita de dois homens-hora ao 
custo de $100 por homem-hora, temos que um are de milho custa 2 • $100 = $200. 
Assim o custo se resume a 300xT + 200xM.
Como devemos tratar com o lucro, calculamos a diferença (600xT + 600xM)–
(300xT + 200xM) e temos 300xT + 400xM. Nossa função objetivo fica definida então 
por max L = 300xT + 400xM .
As restrições do modelo referem-se à quantidade de terra, mão de obra 
disponível, e necessidades do mercado consumidor. Como as variáveis de 
decisão são referentes à quantidade de ares cultivados, não temos necessidade 
de restringi-los a unidades inteiras, já que há a possibilidade de plantar partes 
de ares (por exemplo, 35,7 ares de trigo). Mas lembre-se de que não há medidas 
negativas para terras. Vamos detalhar cada restrição:
TÓPICO 1 | PROBLEMAS DE PROGRAMAÇÃO LINEAR
9
• Restrição quanto ao tamanho do terreno: Esse agricultor possui cinquenta ares 
de terra para dividir entre a produção de trigo e milho, então, xT + xM ≤ 50.
• Restrição quanto ao consumo de mão de obra: Dispomos de 120 homens-hora 
de mão de obra para distribuir três hh para cada are cultivado de trigo (3 • xT) 
e 2 hh para cada are cultivado de milho (2 • xM). Resumindo em 3xT + 2xM ≤ 120.
• Restrição quanto às necessidades de mercado: É sabido que o mercado de 
consumo se limita a 240 sacas de trigo, então a produção deve se limitar a esse 
valor. Note que a unidade de medida em questão é saca, portanto, devemos 
fazer uma transformação de unidades de sacas para ares, lembrando que cada 
are de trigo rende oito sacas, para a produção de 240 sacas são necessários 
trinta ares. Assim, 8xT ≤ 240, ou simplificando, xT ≤ 30.
• De maneira análoga, podemos calcular a restrição quanto ao consumo de milho, 
lembrando que cada are cultivado de milho produz dez sacas e que o mercado 
demanda, no máximo, quatrocentas sacas (ou seja, quarenta ares). Assim, 10xM 
≤ 400, ou simplificando, xM ≤ 40.
• É preciso ainda restringir as variáveis quanto à não negatividade, ou seja, xT ≥ 
0 e xM ≥ 0.
Finalmente, nosso problema de PL fica modelado da seguinte forma:
max L = 300xT + 400xM Função Objetivo (maximizar o lucro)
Sujeito a
xT + xM ≤ 50 Restrição ao tamanho do terreno
3xT + 2xM ≤ 120 Restrição ao uso de mão de obra
xT ≤ 30 Restrição a demanda por trigo
xM ≤ 40 Restrição a demanda por milho
xT , xM ≥ 0 Restrição à não-negatividade
3.3 DIETA ALIMENTAR
Problema: Devemos determinar, em uma dieta para redução calórica, 
as quantidades de certos alimentos que deverão ser ingeridos diariamente, 
de modo que determinados requisitos nutricionais sejam satisfeitos a custo 
mínimo. Suponha que uma dieta alimentar esteja restrita a leite desnatado, 
carne magra de boi, peixe e uma salada pré-definida. Sabe-se ainda que os 
requisitos nutricionais deveriam ser expressos em termos de vitaminas A, C e 
D e controlados por suas quantidades mínimas (em mg). A tabela 2 resume a 
quantidade de cada vitamina em disponibilidade nos alimentos e a necessidade 
diária para a boa saúde da pessoa.
UNIDADE 1 | PROGRAMAÇÃO LINEAR
10
TABELA 2 - QUANTIDADE DE VITAMINAS DISPONÍVEL NOS ALIMENTOS
Vitamina (mg) Leite (l) Carne (kg) Peixe (kg) Salada (kg) Requisito Nutricional
A 2 2 10 20 11
C 50 20 10 30 70
D 80 70 10 80 250
Custo (R$) 2,004,00 1,50 1,00 -
FONTE: Disponível em: <www.decom.ufop.br/prof/marcone>. Acesso em: 19 maio 2009.
Modelagem: Nesse caso, buscamos não maximizar e sim minimizar o custo 
de uma alimentação que equilibre as quantidades ingeridas de cada alimento e 
as quantidades de vitaminas, não podendo ultrapassar os limites mínimos a uma 
alimentação saudável.
Nossas variáveis de decisão serão:
x1 quantidade de leite a ser consumida
x2 quantidade de carne de boi a ser consumida
x3 quantidade de carne de peixe a ser consumida
x4 quantidade de salada a ser consumida
E nossa função objetivo será dada em relação aos custos de cada alimento:
min C = 2x1 +4x2 + 1,5x3 +1x4, em que C representa o custo total.
As restrições do problema são determinadas pelos requisitos nutricionais 
mínimos de vitaminas que devem ser incluídas nessa dieta. Assim:
• Restrição quanto ao consumo de vitamina A: Cada litro de leite ingerido 
acrescenta 2mg de vitamina A na dieta; cada kg de carne acrescenta, também, 
2mg; cada kg de peixe acrescenta 10mg de vitamina A; e cada kg de salada, 
20mg; restritos a um mínimo de 11mg dessa vitamina, então podemos escrever 
essa restrição na forma 2x1 +2x3+ 10x3 +20x4 ≥ 11.
• Restrição quanto ao consumo de vitamina C: De modo análogo, podemos 
escrever 50x1 +20x2 + 10x3+30x4 ≥ 70.
• Restrição quanto ao consumo de vitamina D: Da mesma forma, temos 
80x1 +70x2+ 10x3+80x4 ≥ 250.
E ainda é necessária a restrição de não-negatividade, pois não há 
possibilidade de ingerir, por exemplo, uma quantidade negativa de leite (Você já 
pensou em beber meio litro negativo de leite?). Então x1 , x2, x3 , x4 ≥ 0 .
Organizando nosso modelo, obtemos:
min C = 2x1 +4x2+ 1,5x3+1x4 Função objetivo
Sujeito à
2x1 +2x2+ 10x3+20x4 ≥ 1 Restrição ao consumo de vitamina A
TÓPICO 1 | PROBLEMAS DE PROGRAMAÇÃO LINEAR
11
50x1 +20x2+ 10x3+30x4 ≥ 70 Restrição ao consumo de vitamina C
80x1 +70x2+ 10x3+80x4 ≥ 250 Restrição ao consumo de vitamina D
x1, x2, x3, x4 ≥ 0 Restrição à não negatividade
3.4 PROBLEMAS DE TRANSPORTE
Um dos problemas de Programação Linear mais comum é o problema 
de transporte. Envolve o transporte de cargas entre uma (ou mais) fonte(s) e um 
(ou mais) destino(s). Conhecidos os custos de transporte entre cada fonte e cada 
destino, conhecidas as capacidades de produção das fontes e as capacidades de 
estoque dos destinos, deseja-se determinar o custo mínimo dos transportes.
Acompanhe o exemplo para entender melhor esse tipo de problema.
Duas fábricas (F1 e F2) de brinquedos devem enviar sua produção para 
três Centros de Distribuição (D1, D2 e D3). Os brinquedos são transportados 
em contêineres fechados em um número inteiro de caminhões. Os custos de 
transporte de cada fábrica (fonte) para cada centro de distribuição (destino), as 
capacidades de produção das fábricas e capacidades de estoque dos centros de 
distribuição estão especificados na tabela 3.
Vamos à modelagem do problema.
TABELA 3 - CUSTOS DE TRANSPORTE, CAPACIDADES DE PRODUÇÃO DAS FÁBRICAS E 
CAPACIDADES DE ESTOQUE DOS CENTROS DE DISTRIBUIÇÃO
FÁBRICA\CENTRO DE DISTRIBUIÇÃO D1 D2 D3 PRODUÇÃO
F1 8 5 6 120
F2 3 9 10 80
Capacidade de Estoque 90 40 70 200
FONTE: Os autores
Perceba que o total produzido pelas fábricas é igual à capacidade total de 
estoque dos centros de distribuição. Nesse caso, chamamos esse problema de Problema 
de Transporte Balanceado.
UNI
UNIDADE 1 | PROGRAMAÇÃO LINEAR
12
Nosso objetivo é minimizar os custos de transporte das cargas entre as 
fábricas e os centros de distribuição, portanto min C. Para isso, nossas variáveis 
de decisão são seis:
x11 quantidade a ser transportada da Fábrica F1 para o Centro de 
Distribuição D1
x12 quantidade a ser transportada da Fábrica F1 para o Centro de 
Distribuição D2
x13 quantidade a ser transportada da Fábrica F1 para o Centro de 
Distribuição D3
x21 quantidade a ser transportada da Fábrica F2 para o Centro de 
Distribuição D1
x22 quantidade a ser transportada da Fábrica F2 para o Centro de 
Distribuição D2
x23 quantidade a ser transportada da Fábrica F2 para o Centro de 
Distribuição D3
Como minimizar os custos de transporte das cargas depende das 
quantidades transportadas, temos a função objetivo definida por: 
min C = 8x11 + 5x12 + 6x13 + 3x21 + 9x22 + 10x23.
As restrições do nosso problema são de duas naturezas: quanto à produção 
e quanto ao estoque:
• Restrições quanto à produção: A quantidade de unidades produzidas a serem 
transportadas da Fábrica F1 para D1, D2 e D3 deve ser igual ao total de unidades 
produzidas por F1, ou seja, x11 + x12 + x13 = 120. E a quantidade de unidades 
produzidas a serem transportadas da Fábrica F2 para D1, D2 e D3 deve ser igual 
ao total de unidades produzidas por F2, ou seja, x21 + x22 + x23 = 80.
• Restrições quanto à capacidade de estoque: A quantidade de unidades 
produzidas a serem transportadas das fábricas F1 e F2 para D1 deve ser igual 
à capacidade total de estoque de D1, ou seja, x11 + x21 = 80. A quantidade de 
unidades produzidas a serem transportadas das fábricas F1 e F2 para D2 deve 
ser igual à capacidade total de estoque de D2, ou seja, x12 + x22 = 40. A quantidade 
de unidades produzidas a ser transportada das fábricas F1 e F2 para D3 deve ser 
igual à capacidade total de estoque de D3, ou seja, x13 + x23 = 70.
• Não negatividade e tipo da variável: Não há como transportar quantidades 
negativas de cargas. Então, todas as variáveis devem ser maiores que zero ou 
iguais a zero. Podemos representar matematicamente essa restrição por xij ≥ 0, 
com i = 1, 2 e j = 1, 2, 3. As variáveis devem ser inteiras.
Assim, podemos resumir nosso modelo através de 
min C = 8x11 + 5x12 + 6x13 + 3x21 + 9x22 + 10x23.
Função objetivo
Sujeito à 
TÓPICO 1 | PROBLEMAS DE PROGRAMAÇÃO LINEAR
13
14
RESUMO DO TÓPICO 1
Neste tópico, você estudou que:
• A formulação de um problema de PL envolve três etapas:
• A definição do objetivo básico do problema (Maximizar ou Minimizar) e das 
variáveis de decisão.
• A função objetivo com base nas variáveis de decisão (max ou min)Z = c1x1 + c2x2 
+ ... + cnxn. 
• O sistema de restrições do PPL em relação às variáveis de decisão do
• A modelagem matemática é a principal ferramenta para a formulação dos 
problemas de programação linear.
• Um dos tipos mais comuns de problemas de PL envolve transportes.
15
AUTOATIVIDADE
Agora é sua vez de escrever modelos matemáticos para algumas 
situações encontradas em nossa volta. Tome o devido cuidado na escolha das 
variáveis de decisão e preste muita atenção ao escrever a função objetivo e o 
conjunto de restrições. Bom trabalho!
1 Para uma boa alimentação, o corpo necessita de vitaminas e proteínas.
A necessidade mínima de vitaminas é de 32 unidades por dia e a de 
proteínas é de 36 unidades por dia.
Uma pessoa tem disponível carne e ovos para se alimentar.
Cada unidade de carne contém quatro unidades de vitaminas e seis 
unidades de proteínas, a um custo de três unidades monetárias por unidade.
Cada unidade de ovo contém oito unidades de vitaminas e seis unidades 
de proteínas, a um custo de 2,5 unidades monetárias por unidade.
Qual o modelo matemático que descreve a quantidade diária de carne e 
ovos que deve ser consumida para suprir as necessidades de vitaminas e 
proteínas com o menor custo possível?
2 Uma indústria têxtil produz três tipos de produtos, cada um dos quais 
necessariamente precisa ser processado em uma máquina de costura reta, 
em uma máquina de costura overlock e embalado. Os tempos consumidos 
por cada unidade de produto em cada processo, a disponibilidade de 
tempo, os custos e a receita pela venda de cada unidade dos produtos 
seguem na tabela a seguir.
Produto
Tempo de processo (minutos) C o n s u m o 
de matéria 
prima (kg)
Receita 
unitária (RS)Máquina 
reta
Máquina 
overlock Embalagem
Tipo I 15 10 5 1,5 50
Tipo II 10 12 8 0,8 65
Tipo III 5 4 3 0,6 30
Disponibilidade 4800 4000 3600 480 -
Deseja-se planejar a produção da próxima semanade forma que o lucro 
dessa indústria seja o máximo possível.
Assumindo com variáveis de decisão:
x1 = quantidade de unidades a produzir do produto tipo A
x2 = quantidade de unidades a produzir do produto tipo B
x3 = quantidade de unidades a produzir do produto tipo C
Responda:
a) Escreva a função objetivo que representa o modelo.
b) Escreva as restrições do problema quanto:
16
(i) ao tempo de processo na máquina de costura reta;
(ii) ao tempo de processo na máquina de costura overlock;
(iii) ao tempo de processo de embalagem;
(v) à não negatividade.
(vi) ao consumo de matéria-prima.
3 Modele, sem resolver, os seguintes PPLs:
a) Uma indústria produz porcas, parafusos e pregos, podendo usar dois 
métodos (distintos e não simultâneos) para produzi-los. O primeiro 
método produz 3000 porcas, 2000 parafusos e 2500 pregos por hora, 
enquanto que o segundo método produz 4000 parafusos e 4000 pregos por 
hora, mas nenhuma porca. A indústria trabalha dezoito horas por dia e 
tem uma encomenda de 5000 parafusos, 5000 pregos e 5000 porcas. Ela 
deve empregar os dois métodos de modo a entregar sua encomenda o mais 
rápido possível, planejando o tempo de operação de cada método.
b) Segundo Wagner (1986, p. 47), o presidente Antônio Castor, da Companhia 
Ramos de Carvalho, quer utilizar do melhor modo possível os recursos 
de madeira de uma de suas regiões florestais. Dentro dessa região, há 
uma serraria e uma fábrica de compensados; assim, as toras podem ser 
convertidas em madeira beneficiada ou compensada.
Produzir uma mistura comercializável de um metro cúbico de produtos 
beneficiados requer um metro cúbico de pinho e quatro metros cúbicos de 
canela. Produzir cem metros quadrados de madeira compensada requer 
dois metros cúbicos de pinho e quatro metros cúbicos de canela. Essa região 
tem disponível 32 metros cúbicos de pinho e 72 metros cúbicos de canela.
Compromissos de venda exigem que sejam produzidos, durante o período 
do planejamento, pelo menos cinco metros cúbicos de madeira beneficiada 
e 1200 m2 de madeira compensada. As contribuições ao lucro são $45 por 
um metro cúbico de produtos beneficiados e $60 por 100 m2 de madeira 
compensada.
17
TÓPICO 2
SOLUÇÃO GRÁFICA DE PROBLEMAS 
DE PROGRAMAÇÃO LINEAR
UNIDADE 1
1 INTRODUÇÃO
A solução ótima (Z*), ou seja, o máximo lucro ou mínimo custo, por 
exemplo, de um problema de programação linear que tenha duas, ou até 
três, variáveis de decisão pode ser encontrada usando-se representações no 
sistema de eixos cartesianos ortogonais (plano cartesiano). Para simplificar 
sua compreensão, usaremos o exemplo 2, sobre o planejamento de produção 
agrícola, buscando a solução ótima, ou seja, o máximo lucro que pode ser obtido 
com o plantio dos cereais. 
Segue o modelo do problema de PL para facilitar a leitura dos dados:
maxL = 300xT + 400xM Função Objetivo (maximizar o lucro)
Sujeito a
xT + xM ≤ 50 Restrição ao tamanho do terreno
3xT + 2xM ≤ 120 Restrição ao uso de mão de obra
 xT ≤ 30 Restrição a demanda por trigo
xM ≤ 40 Restrição a demanda por milho
xT , xM ≥ 0 Restrição à não-negatividade
2 REPRESENTAÇÃO GRÁFICA
Para essa representação, usaremos o eixo das abscissas do plano (eixo Ox) 
para representar a variável xT (a quantidade de ares de terra destinados ao plantio 
de trigo). E usaremos o eixo das ordenadas (eixo Oy) para a representação da 
variável xM (quantidade de ares de terra destinados ao plantio de milho). Assim, 
temos o plano mostrado na Figura 1.
UNIDADE 1 | PROGRAMAÇÃO LINEAR
18
FONTE: Os autores
Inicialmente, faremos a representação da 1ª restrição do problema usando 
a equação da reta xT + xM = 50. Os pontos abaixo dessa reta correspondem à 
desigualdade < da restrição do PPL. O gráfico fica definido conforme a Figura 2.
FONTE: Os autores
Fazemos o mesmo com a segunda restrição do problema, usando a 
equação da reta 3xT + 2xM ≤ 120. Os pontos abaixo dessa reta correspondem à 
desigualdade < da restrição do PPL. O gráfico fica definido conforme a Figura 3.
FIGURA 1 - PLANO CARTESIANO COM AS COORDENADAS DE x
T
 E x
M
FIGURA 2 - PLANO CARTESIANO COM A RESTRIÇÃO x
T
 + x
M 
≤ 50
Região onde
x1 + x2 ≤ 50
x
1 + x
2 = 50
50
50
TÓPICO 2 | SOLUÇÃO GRÁFICA DE PROBLEMAS DE PROGRAMAÇÃO LINEAR
19
FONTE: Os autores
Como as restrições devem ser respeitadas simultaneamente, deve-se 
mostrar no gráfico a intersecção entre as regiões delimitadas pelas restrições. 
Imagine-se colando a Figura 2 sobre a Figura 3.
FONTE: Os autores
Mas você deve lembrar que o PPL deve considerar todas as restrições 
juntas na busca pela solução ótima. Então, devemos graficar todas as equações 
de retas referentes às desigualdades relativas às restrições, tomando o devido 
cuidado de destacar a área (acima ou abaixo da reta da restrição) conforme o sinal 
da desigualdade (> ou <). O PPL fica graficado como mostra a Figura 5.
FIGURA 3 - PLANO CARTESIANO COM A RESTRIÇÃO 3x
T
 + 2x
M
 ≤ 120
FIGURA 4 - PLANO CARTESIANO COM A REGIÃO DE INTERSECÇÃO DAS 
RESTRIÇÕES x
T
 + x
M
 ≤ 50 E 3x
T
 + 2x
M
 ≤ 120
Região onde
3x1 + 2x2 ≤ 120
3x
1 + 2x
2 = 120
40
60
Região onde
3x1 + 2x2 ≤ 120 e x1 + x2 ≤ 50
x
1 + x
2 = 50
3x
1 + 2x
2 = 120
40 60
60
50
UNIDADE 1 | PROGRAMAÇÃO LINEAR
20
FONTE: Os autores
Perceba que intersecção das restrições do PPL limita o gráfico a uma figura 
poligonal fechada convexa que contém todos os pontos (xT , xM) chamados de 
Soluções Compatíveis do problema de PL, que formam o Conjunto das Soluções 
Compatíveis. A solução ótima Z* = (x*T , x*M) deve ser um destes pontos (ou mais 
de um ponto, se o problema permitir essa possibilidade).
3 VETOR GRADIENTE - ▼ Z
Uma ferramenta importante na busca da solução ótima é o vetor gradiente 
da função objetivo, que indica a direção do máximo crescimento dela, ou seja, onde 
devemos procurar o ponto do Conjunto de Soluções Compatíveis que faça com 
que a função objetiva adquira seu maior valor. Esse vetor gradiente, representado 
agora por ▼L (já que queremos o máximo lucro), tem como extremidades os 
coeficientes da função objetivo, ou seja, ▼L = (300, 400). 
Representar esse vetor em nosso gráfico seria loucura, visto o tamanho 
do vetor, mas como o que nos importa é a direção do vetor, basta simplificá-lo 
dividindo por dez as suas coordenadas e então teremos a direção do máximo 
crescimento de L em (30,40), representado na Figura 6.
FIGURA 5 - PLANO CARTESIANO COM O SISTEMA DE RESTRIÇÕES, MOSTRANDO 
A REGIÃO DE INTERSECÇÃO DE TODAS AS RESTRIÇÕES
TÓPICO 2 | SOLUÇÃO GRÁFICA DE PROBLEMAS DE PROGRAMAÇÃO LINEAR
21
FONTE: Os autores
Podemos observar como usar o vetor gradiente para encontrar a solução 
ótima (L*), usando para isso, nada mais do que um simples esquadro (aquele 
usado na escola). Basta colocar um dos lados retos do esquadro em cima do vetor 
gradiente e deslizá-lo no sentido do vetor, desde a origem, observando as retas 
perpendiculares ao vetor gradiente que são definidas pelo outro lado do esquadro 
(se o problema for de minimização usa-se o sentido oposto ao de ▼L). Deve-
se manter esse movimento até encontrar o último ponto da região de soluções 
compatíveis que toque o esquadro.
FONTE: Os autores
FIGURA 6 - USO DO VETOR GRADIENTE NA BUSCA DE L*
FIGURA 7 - USO DO ESQUADRO COMO APOIO AO VETOR GRADIENTE NA BUSCA DE Z*
UNIDADE 1 | PROGRAMAÇÃO LINEAR
22
Em nosso exemplo, a reta definida pelo esquadro determina um único 
ponto que fornece o máximo lucro para a função objetivo, que é um vértice do 
polígono (conjunto) de soluções compatíveis. Esse ponto é determinado pelo 
encontro (intersecção) das equações das retas xM = 40 e xT + xM = 50. Para descobri-
lo basta calcular o sistema de equações lineares
 
em que temos x*T = 10 e x*M = 40.
A solução ótima para o problema de PL é dada pela função objetivo 
calculada para estes valores. Assim, maxL = 300xT + 400xM = 300 . x*T + 400 . x*M 
= 300 . 10 + 400 . 40 = 19000.
Podemos ainda interpretar os resultados da seguintemaneira: se o sitiante 
destinar dez ares de sua terra à plantação de trigo e quarenta ares à plantação de 
milho, seu lucro com a venda da safra será de $19.000,00.
Apenas para fins didáticos iremos conferir se a solução ótima encontrada 
respeita todos os limites impostos pelas restrições:
Restrição ao tamanho do terreno xT + xM ≤ 50 
Temos 10 + 40 = 50 ≤ 50 OK!
Restrição ao uso de mão de obra 3xT + 2xM ≤ 120
Temos 3 . 10 + 2 . 40 = 30 + 80 = 110 ≤ 120 
OK!
Restrição a demanda por Trigo xT ≤ 30
Temos x*T = 10 ≤ 30
OK!
Restrição a demanda por Milho xM ≤ 40
Temos x*M = 40 ≤ 40 OK!
E é evidente que as varáveis não são negativas. 
Portanto, nossa solução ótima L* = (x*T , x*M) = (10,40) = 19000 respeita 
todas as restrições.
xT + xM = 50
xM = 40{
4 CONSIDERAÇÕES SOBRE O MÉTODO GRÁFICO
Quando o número de restrições do PPL for muito grande, ou os coeficientes 
da função objetivo e restrições forem valores muito “distantes” (um muito grande 
e outro muito pequeno), pode haver uma grande dificuldade em representar esse 
PPL graficamente. Muitas restrições deixam o gráfico “poluído” e dificultam o 
trabalho com o vetor gradiente.
TÓPICO 2 | SOLUÇÃO GRÁFICA DE PROBLEMAS DE PROGRAMAÇÃO LINEAR
23
Para problemas de PL com três variáveis de decisão, devem-se usar não 
retas para as restrições, mas sim planos no espaço (3D) e assim exige-se de você 
uma grande (diríamos espetacular) capacidade para a representação gráfica. 
Você pode optar por resolver graficamente o exemplo 1 (da fábrica de 
móveis), mas entenda isso como muito trabalho e muito tempo dedicado. Vale 
pela experiência, mas não há necessidade. Como veremos adiante, outras técnicas 
serão muito bem-vindas!
24
RESUMO DO TÓPICO 2
Neste tópico, vimos que:
• A solução ótima de um PPL de duas variáveis pode ser encontrada através do 
gráfico das restrições em planos cartesianos, com a ajuda do vetor gradiente.
• Basta traçar num plano cartesiano as equações de cada restrição e definir a 
região de soluções compatíveis como a intersecção das regiões limitadas pelas 
restrições.
• Com a direção do vetor gradiente e a ajuda de um esquadro, a solução ótima é 
o último ponto de contato do esquadro na região de soluções compatíveis.
• A solução ótima do PPL é o ponto de intersecção das equações no ponto 
encontrado com o esquadro, que pode ser determinada resolvendo um sistema 
de equações lineares.
25
AUTOATIVIDADE
Mãos à obra! Resolva as atividades a seguir em uma folha separada. 
Capriche nos gráficos, usando régua ou esquadro, para que fiquem bem visíveis 
e para que você possa compreender perfeitamente os pontos (soluções), as retas 
(equações) e os planos (região compatível).
1 Faça um plano cartesiano ortogonal e represente nele o Vetor Gradiente da 
função objetivo definida por Max Z = 3x1 + 5x2.
2 Em relação ao modelo referente à autoatividade 1 do tópico anterior:
a) Faça o gráfico que representa o conjunto de restrições do modelo.
b) Encontre as coordenadas dos vértices da região de soluções compatíveis 
do modelo.
c) Indique a direção do Vetor Gradiente no plano cartesiano.
c) Qual a solução ótima do problema?
3 Resolva, graficamente, o modelo referente à autoatividade 3(b) do tópico 
anterior.
26
27
TÓPICO 3
PROGRAMAÇÃO LINEAR INTEIRA
UNIDADE 1
1 INTRODUÇÃO
Os Problemas de Programação Linear Inteira são uma classe de problemas 
de PL que contém uma particularidade: alguma restrição em relação ao tipo de 
uma ou mais variáveis de decisão, como por exemplo, variáveis que podem 
assumir apenas valores inteiros.
Esse tipo de problema pode ser resolvido do mesmo modo como os 
problemas de PL, mas devem-se utilizar alguns métodos especiais quando a 
solução encontrada não respeita a restrição quanto ao tipo das variáveis. Um dos 
métodos mais utilizados é o Método de Branch and Bound (Ramificação e Limite), 
que adotaremos em nossos estudos nesse caderno.
2 UM MODELO DE PL INTEIRA
Para compreender melhor esse tipo de problema vamos recorrer a um 
exemplo.
Seja o problema de PL modelado da seguinte maneira:
max Z = 6x1 + 1x2 É a função objetivo
Sujeito à
 
 
 
Que são as restrições do PPL
Perceba que a última restrição indica duas restrições, a não negatividade 
das variáveis e a restrição quanto ao tipo de variável (são aceitos apenas 
números inteiros, os decimais estão descartados). Resolvendo o PPL através 
do método gráfico conforme figura 8, sem se preocupar com essa restrição 
encontramos a solução que corresponde a x1 = 0 e x2 ≅ 5,67, que nos leva a 
um máximo Z ≅ 62,37.
5x1 + 3x2 ≤ 17
x1 , x2 ≥ 0 e inteiros }
UNIDADE 1 | PROGRAMAÇÃO LINEAR
28
FONTE: Os autores
Mas essa solução encontrada não é aceita pelo problema, pois o valor da 
variável não é um número inteiro.
Podemos ficar tentados a resolver esse mero detalhe fazendo um simples 
arredondamento do valor encontrado para o número inteiro mais próximo e 
recalculando a solução do PPL. Assim teríamos x*2 = 6, e a solução ótima, nesse 
caso, seria Z* = 6 . 0 + 11 . 6 = 66 . Mas se fizermos um teste de verificação dessa 
solução para a compatibilidade com o sistema de restrições do problema veremos 
que a restrição não aceita a solução encontrada:
5x1 + 3x2 ≤ 17 ⇒ 5 
. 0 + 3 . 6 = 18 ≤ 17 Não aceita!
Ou seja, a solução ótima arredondada encontrada não satisfaz as restrições 
do PPL e, portanto, não é uma solução compatível com o PPL.
Outra maneira de encontrar a solução ótima inteira e compatível com o 
sistema de restrições do PPL seria procurar, na região do plano cartesiano, as 
soluções inteiras que se encontram dentro da área de soluções compatíveis. Mas 
há o inconveniente de poder haver muitos pontos com essa característica dentro 
da área de compatibilidade e esse processo pode tornar-se demorado e cansativo.
Considerando as alternativas, faz-se necessário um algoritmo de busca 
que possa encontrar a solução ótima de maneira mais eficaz e que obedeça às 
FIGURA 8 - SOLUÇÃO GRÁFICA DO PPL DE EXEMPLO
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
29
3 O MÉTODO DE BRANCH AND BOUND
Nosso problema origina-se ao perceber que a solução ótima encontrada, 
x*1 = 0 e x*2 ≅ 5,67 , não obedece à restrição quanto ao tipo da variável, ou seja, 
não é um numero inteiro e a solução arredondada não satisfaz às restrições 
do PPL. Para resolver esses problemas, vamos imaginar a solução como 5 ≤ x2 
≤ 6 e criar dois novos modelos de PL, baseados no PPL original, um PPL com 
a restrição x2 ≤ 5 e outro com a restrição x2 ≥ 6. Esse é o chamado processo de 
ramificação. 
Assim o PPL original, que chamaremos de PL0, que era
max Z = 6x1 + 11x2
Sujeito à
5x1 + 3x2 ≤ 17
x1 , x2 ≥ 0 e inteiro
Fica ramificado em:
PL1 e PL2
max Z = 6x1 + 11x2 max Z = 6x1 + 11x2 
Sujeito à Sujeito à
5x1 + 3x2 ≤ 17 5x1 + 3x2 ≤ 17
x2 ≤ 5 x2 ≥ 6
x1 , x2 ≥ 0 e inteiro x1 , x2 ≥ 0 e inteiro
Agora, temos o trabalho de resolver dois problemas de PPL, porém, 
ignorando as restrições sobre valores inteiros.
restrições do problema. Empregaremos o Método de Branch and Bound, pois é o 
mais conhecido e utilizado na resolução desse tipo de problema.
UNIDADE 1 | PROGRAMAÇÃO LINEAR
30
FONTE: Os autores
Através do método gráfico, podemos observar que:
• A solução encontrada para o PL1 é dada por x*1 = 0,4 e x*2 = 5 , que fornece 
Z* = 57,4.
• Mas o PL2 não tem solução. Observando as restrições, não há valor de x2 que 
as satisfaça simultaneamente, visto que x1 não pode ser negativo e o mínimo 
valor para x2 é 6 (restrição x2 ≥ 6) Mas a restrição 5x1 + 3x2 ≤ 17 não aceita 
valores de x2 maiores que 6.
Se o PL2 tivesse solução faríamos uma comparação entre os valores de Z 
nos PPL 1 e 2, continuando a busca de Z* pelo PPL que tivesse maior valor.
Para compreender a situação em que nos encontramos, vamos organizar 
nosso trabalho em um diagrama:
FIGURA 9 - GRÁFICO DO PL
1
 COM AS SUAS RESTRIÇÕES
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
31
Como o PL2 não tem solução (é eliminado),e a solução encontrada 
para o PL1 ainda não é viável, já que x1* não é inteiro, seguimos a resolução do 
problema usando o PL1, lembrando que temos novamente uma variável com 
valor decimal. Dessa vez temos que pensar em 0 ≤ x1 ≤ 1, e a partir disso, criar 
dois novos PPLs, ramificando mais uma vez nosso problema.
Criamos então os PPLs:
PL3 e PL4
max Z = 6x1 + 11x2 max Z = 6x1 + 11x2
Sujeito à Sujeito à
5x1 + 3x2 ≤ 17 5x1 + 3x2 ≤ 17
x2 ≤ 5 x2 ≤ 5
x1 ≤ 0 x2 ≥ 1
x1 , x2 ≥ 0 e inteiro x1 , x2 ≥ 0 e inteiro 
 
Analisando as restrições do PL3, percebemos que não há a necessidade de 
fazer o gráfico. As restrições x1 ≥ 0 e x1 ≤ 0 só aceitam uma solução: x1 = 0. Em 
conseqüência disso, usando a restrição 5x1 + 3x2 ≤ 17, temos x2 = 5, que é o máximo 
valor aceito pela restrição x2 ≤ 5.
Assim, para o PL3 temos: x1 = 0, x2 = 5 e Z = 6 • 0 + 11 • 5 = 55.
Resolvendo o PL4 utilizando o método gráfico, temos:
FONTE: Os autores
FIGURA 10 - GRÁFICO DO PL
4
 COM SUAS RESTRIÇÕES E O VETOR GRADIENTE
UNIDADE 1 | PROGRAMAÇÃO LINEAR
32
A solução ótima é o ponto de intersecção das retas de equações:
Assim, para o PL4 temos: x1 = 1, x2 = 4 e Z = 6 . 1 + 11 . 4 = 6 + 44 = 50.
Vamos organizar novamente todo o trabalho em um diagrama.
Comparando as soluções dos PPLs, criados a partir do PPL original (PL0) 
temos, nesse caso, duas possíveis soluções (Z = 55, no PL3 e z = 50, no PL4).
Como nosso objetivo é encontrar o valor máximo para Z, obedecendo às 
restrições, obviamente devemos concluir que:
max Z = 6x1 + 11x2
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
33
Sujeito à
5x1 + 3x2 ≤ 17
x1 , x2 ≥ 0 e inteiro
E o PPL tem como solução ótima: x*1 = 0, x*2 = 5 e Z* = 55.
3.1 CONSIDERAÇÕES SOBRE O MÉTODO 
DE BRANCH AND BOUND
Esse método de resolução para problemas de Programação Linear Inteira 
(PLI) trabalha em dois momentos:
• Ramificação: 
Resolve-se o PPL buscando valores inteiros para as variáveis. Caso não 
os encontre, ramifica-se o PPL em dois novos, atribuindo a cada um deles novas 
restrições, delimitando novos conjuntos de soluções compatíveis, eliminando a 
possibilidade de reencontrar os valores que originaram a ramificação. 
O processo de ramificação continua até que:
• Encontramos um PPL sem solução;
• Encontramos as soluções de todos os PPLs ramificados que obedeça a restrição 
quanto ao tipo de variável (inteira).
• Limite: 
Ao encontrar um ramo do PPL que apresente solução compatível (inteira), 
define-se o valor de Z desse ramo do PPL como o Limite Inferior. Qualquer ramo 
que apresente solução (inteira ou não) menor que o limite inferior é imediatamente 
eliminado (poupando trabalho).
As ramificações continuam nos PPLs que tenham soluções não inteiras 
cujo valor de Z seja maior que o limite inferior. Se um PPL apresentar uma solução 
inteira maior que o Limite inferior, então esse valor de Z passa a ser o novo Limite 
Inferior, e o PPL que fazia esse papel anteriormente também é eliminado, assim 
como todos os ramos que tenham solução menor que o novo limite inferior.
Fazemos esse procedimento até que se eliminem todos os ramos sem 
solução ou com solução menor que o Limite Inferior, e esse limite é a solução 
ótima do PPL original.
34
UNIDADE 1 | PROGRAMAÇÃO LINEAR
Vamos, novamente, analisar nosso PPL de exemplo:
O PPL original (PL0) não tem solução inteira e foi ramificado em:
• PL1 que também não tem solução inteira (mas tem solução);
• PL2 que não tem solução e por isso é eliminado.
O PL1 é ramificado em:
PL3 que tem solução inteira (x1 = 0 e x2 = 5) definindo o limite inferior Z = 55.
PL4 que tem solução inteira (x1 = 1 e x2 = 4), mas seu valor Z = 50 é menor 
que o limite inferior, portanto, também é eliminado.
Como não há mais necessidade de ramificar o PL3, este traz a solução 
ótima para o PL0, dada pelo limite inferior Z* = 55.
4 APLICAÇÃO DE PLI
Um técnico em eletrônica produz dois tipos de componentes eletrônicos. 
Ele dispõe de 6 capacitores, usados na produção, e de 9 horas de trabalho. O 
componente do tipo 1 necessita de 2 capacitores e 2 horas de trabalho para ser 
produzido, enquanto que o componente do tipo 2 necessita apenas 1 capacitor, mas 
de 3 horas de trabalho para sua produção. Esse técnico vende seus componentes 
eletrônicos ganhando três reais pela venda de uma unidade do componente 
do tipo 1 e quatro reais pela venda de uma unidade do componente do tipo 2. 
Quantos componentes de cada tipo ele deve produzir de modo a obter o maior 
lucro possível com a venda?
Vamos ao modelo:
• Variáveis de decisão:
x1 – unidade a produzir do componente tipo 1
x2 – unidade a produzir do componente tipo 2
• Função Objetivo:
Deve-se buscar o máximo lucro com a venda, logo, max L.
Os ganhos são de três reais para cada x1 e mais quatro reais para cada x 2. 
Podemos representar por 3x1 + 4x2.
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
35
Assim, a função objetivo é dada por Max L = 3x1 + 4x2.
• Restrições:
Quanto ao material utilizado: 2 capacitores para cada x1 e 1 capacitor para 
cada x2, não excedendo ao limite de 6 capacitores. Portanto, 2x1 + x2 ≤ 6.
Quanto ao tempo: 2 horas para cada x1 e 3 horas para cada x2, não 
excedendo ao limite de 9 horas. Portanto, 2x1 + 3x2 ≤ 9.
Não negatividade: Não há como produzir quantidades negativas de x1 e 
x2, então x1 ≥ 0 e x2 ≥ 0.
Integralidade: Não há ganho na venda de componentes inacabados, logo 
esse deverão ser produzidos em unidades inteiras. Assim, x 1 inteiro e x2 inteiro.
Nosso modelo de PLI fica:
Max L = 3x1 + 4x2.
Sujeito a
2x1 + x2 ≤ 6
2x1 + 3x2 ≤ 9
x1 , x2 ≥ 0 e inteiros
Ao resolver o PLI (agora PL0), graficamente chegamos à solução x1 = 2,55 e 
x2 = 1,5, com L = 12,75. Mas x1 e x2 não são inteiros, então devemos ramificar o PL0 
em dois novos. Nesse caso escolhendo entre uma das variáveis para criar a nova 
restrição dos PPLs. Optamos por x2, e usando 1 ≤ x2 ≤ 2, criamos PL1 e PL2.
AUTOATIVIDADE
Por ser um problema de apenas duas variáveis (x1 e x2), a solução pode 
ser através do método gráfico. Como o espaço em nosso caderno é reduzido, 
fica ao seu encargo fazer os gráficos para a verificação das soluções.
36
UNIDADE 1 | PROGRAMAÇÃO LINEAR
Nos dois casos a solução (x1, x2) não é inteira e devem-se criar ramificações 
a partir dos dois PPLs. Vamos começar ramificando o PL2 (L = 12,5) por apresentar 
uma solução melhor que o PL1 (L = 11,5). A ramificação a partir do PL2 gera PL3, 
com a restrição x1 ≤ 1, e PL4, com a restrição x1 ≥ 2, criadas com base no fato de que 
1 ≤ x1 ≤ 2 no PL2.
Um critério de escolha para decidir que variável usar na criação das novas 
restrições é usar a variável que possui valor mais “longe” de um número inteiro. No nosso 
caso, x
2
. 
UNI
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
37
Novamente, deve-se resolver os dois PPLs, e as soluções são:
• Para o PL3: x1 = 1, x2 = 2,33 e L = 12,33.
• Para o PL4: Não há solução. (Tente usar os valores mínimos x1 = 2 e x2 = 2 na 2ª 
restrição do PL4 para certificar-se dessa afirmação.)
Eliminando o PL4, podemos escolher entre ramificar o PL1 ou o PL3. 
Escolhemos esse último por ter o maior valor para L (que não é o Limite Inferior).
No PL3, usamos 2 ≤ x2 ≤ 3 para criar PL5 com a restrição x2 ≤ 2 e o PL6 com 
a restrição x2 ≥ 3.
Comparando as soluções encontradas (que são inteiras), podemos definir 
12 como o Limite Inferior para os ramos do PPL e todos os ramos que têm solução 
menor que 12 são eliminados. 
Perceba que a restrição de não negatividade do PL
4
 é redundante já que temos 
x
1
 ≥ 2 e x
2
 ≥ 2.
UNI
38
UNIDADE 1 | PROGRAMAÇÃO LINEAR
No diagrama vemos que:
• PL4 é eliminado, pois não tem solução.
Vamos analisar o diagrama de soluções encontradas até agora e verificar 
o que resta no PPL para que se possa encontrar a solução ótima.
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
39
4.1 CONSIDERAÇÕES FINAIS SOBRE A PLI
Como vimos no início dos estudos sobre PLI, a solução pode ser encontrada 
pelo arredondamento do PPL, sem levar em contaa restrição de integralidade. 
Mas essa técnica acarreta em uma série de dificuldades.
Vamos relembrar a primeira solução encontrada no PPL do exemplo 
de aplicação, em que tínhamos x1 = 2,25 e x2 = 1,5. Desrespeitando os acordos 
matemáticos para arredondamentos, poderíamos arredondar os valores das 
soluções encontrando quatro pares de soluções: x1 = 2 e x2 = 1, x1 = 2 e x2 = 2, 
x1 = 3 e x2 = 1 e, por último, x1 = 3 e x2 = 2. Dessas soluções, apenas encontra-se 
dentro da região de soluções compatíveis o par x1 = 2 e x2 = 1, que nos traz L = 
10. Comparando esse valor com a solução ótima encontrada através do Método 
de Branch and Bound, em que L = 12, temos uma variação de, aproximadamente, 
16% na solução ótima do PPL. Por mais esse motivo, é interessante perceber a 
necessidade de utilizar os algoritmos corretamente para que se possa chegar às 
melhores conclusões.
• PL6 é definido como Limite Inferior, pois apresenta a maior solução inteira (L 
= 12).
• PL1 e PL5 são eliminados, pois apresentam soluções menores que o Limite 
Inferior.
• PL6 define a solução ótima do PPL, pois é o único ramo restante e apresenta a 
solução compatível com as restrições.
Assim, fica definida a solução ótima do problema como x*1 = 0 , x*2 = 3 e L* 
= 12, o que pode ser interpretado da seguinte forma: O técnico em eletrônica deve 
produzir apenas o componente do tipo 2, pois vendendo três unidades desse 
produto seu lucro será de doze reais.
40
UNIDADE 1 | PROGRAMAÇÃO LINEAR
SOBRE A DEFINIÇÃO DE UM PROBLEMA DE PESQUISA 
OPERACIONAL E A COLETA DE DADOS
Frederick S. Hillier e Gerald J. Liebermann
A maioria dos problemas práticos enfrentados pelas equipes de PO é 
inicialmente descrita a eles de uma forma vaga e imprecisa. Consequentemente, a 
primeira ordem do dia é estudar o sistema relevante de e desenvolver um enunciado 
bem-definido do problema a ser considerado. Isso abrange determinar coisas como 
os objetivos apropriados, restrições sobre o que pode ser feito, relação entre a área a 
ser estudada e outras áreas da organização, possíveis caminhos alternativos, limites 
de tempo para tomada de decisão e assim por diante. Esse processo de definição de 
problema é crucial, pois afeta enormemente quão relevantes serão as conclusões do 
estudo. É difícil obter uma resposta “correta” a partir de um problema “incorreto”!
A primeira coisa a ser reconhecida é que uma equipe de PO normalmente 
trabalha na qualidade de consultores. Aos membros da equipe não somente é 
apresentado um problema e solicitado a resolvê-lo conforme julguem apropriado. 
Em vez disso, eles aconselham a gerência (geralmente um tomador de decisões 
importante). A equipe realiza uma análise técnica detalhada do problema e 
a seguir apresenta recomendações à gerência. Frequentemente, o relatório à 
gerência identificará uma serie de alternativas particularmente atrativas de acordo 
com diversas suposições ou segundo um intervalo de valores diferente de algum 
parâmetro da política adotada que pode ser avaliado somente pela a gerência 
(por exemplo, o conflito entre custos e benefício). A gerência avalia o estudo e suas 
recomendações, leva em consideração uma série de fatores intangíveis e toma 
a decisão final baseada em seu melhor julgamento. Consequentemente, é vital 
para a equipe de PO sintonizar-se com a gerência e obter o seu apoio ao longo do 
projeto.
Determinar os objetivos apropriados é um aspecto muito importante na 
definição de um problema. Para tanto, é necessário, primeiramente, identificar o 
membro (ou membros) da gerência que efetivamente decidirá(ão) no que se refere 
ao sistema em estudo e, depois sondar o pensamento desse(s) indivíduo(s) no que 
tange aos objetivos pertinentes (envolver o tomador de decisões desde o princípio 
é essencial para obter seu apoio à implementação do estudo).
Em razão de sua natureza, a PO se preocupa com o bem-estar de toda 
a organização e não apenas com aquele de certos membros da organização. Um 
estudo de PO busca soluções que são ótimas para a organização subotimizadas 
que são boas apenas para um membro. Portanto, os objetivos que são formulados 
idealmente devem ser aqueles de toda a organização. Entretanto, isso nem 
LEITURA COMPLEMENTAR
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
41
sempre é conveniente. Muitos problemas referem-se primariamente apenas a 
uma porção da organização, de forma que a análise passaria a ser incontrolável 
caso os objetivos declarados fossem muito genéricos e se fosse dada consideração 
categórica a rodos os efeitos colaterais no restante da organização. Em vez disso, 
os objetivos usados no estudo devem ser os mais específicos possíveis e, ao 
mesmo tempo, englobar os principais objetivos do tomador de decisões e manter 
um grau de consistência razoável com objetivos mais altos da organização.
Para organizações com fins lucrativos, uma abordagem possível para 
contornar o problema de subotimização é usar a maximização de lucros no logo 
prazo (levando-se em conta o valor do dinheiro no tempo) como o único objetivo. 
A qualificação no longo prazo indica que esse objetivo fornece a flexibilidade 
de considerar atividades que não se traduzem imediatamente em lucros, por 
exemplo, projetos de pesquisa e desenvolvimento, mas precisam fazê-lo com o 
tempo de modo a valer a pena. Essa abordagem tem seus méritos. Esse objetivo 
é suficientemente especifico para ser usado de forma conveniente e ainda assim 
ser suficientemente abrangente para abarcar o objetivo básico das organizações 
que visam ao lucro. De fato, algumas pessoas acreditam que todos os demais 
objetivos legítimos podem ser traduzidos nesse único.
Entretanto, na prática, muitas organizações com fins lucrativos não 
adotam esse enfoque. Uma série de estudos de corporações norte-americana 
revela que a gerência tende a adotar o objetivo de lucros satisfatórios, combinados 
com outros objetivos, em vez de focalizar na maximização de lucros no longo prazo. 
Tipicamente, alguns desses outros objetivos podem ser o de manter lucros estáveis, 
aumentar (ou manter) a fatia de mercado, propiciar a diversificação de produtos, 
manter preços estáveis, levantar o moral dos trabalhadores, manter o controle 
familiar do negócio e aumentar o prestígio da companhia. Completando-se esses 
objetivos, pode ser que se alcance a maximização, porém o inter-relacionamento 
pode ser suficientemente obscuro para não ser conveniente incorporar todos eles 
nesse único objetivo. 
Além disso, há considerações adicionais envolvendo responsabilidades 
sociais que são distintas do motivo lucro. As cinco partes, geralmente afetadas 
por uma empresa comercial localizada em um único país são: (1) os proprietários 
(acionistas etc.) que desejam lucros (dividendos, valorização das ações e assim 
por diante); (2) os empregados, que desejam emprego estável com salários 
razoáveis; (3) os clientes, que desejam um produto confiável a preços razoáveis; 
(4) os fornecedores, que desejam integridade e um preço de venda razoável para 
suas mercadorias; e (5) o governo e, consequentemente, a nação, que desejam o 
pagamento de impostos razoáveis e consideração pelo interesse nacional. Todas 
as cincos partes dão contribuições essenciais para a empresa e essa não deve ser 
vista como um servidor exclusivo de qualquer uma das partes para exploração 
das demais. Pelo mesmo critério, corporações internacionais assumem obrigações 
adicionais para seguirem práticas socialmente responsáveis. Portanto, mesmo que 
42
UNIDADE 1 | PROGRAMAÇÃO LINEAR
a principal responsabilidade da gerência seja a de gerar lucros (o que, em ultima 
instância, acabará beneficiando as cinco partes envolvidas), percebemos que suas 
responsabilidades sociais mais amplas também devam ser reconhecidas.
As equipes de PO tipicamente investem uma quantidade de tempo 
surpreendentemente grande coletando dados relevantes sobre o problema. Grande 
parte dos dados normalmente é necessário tanto para se obter o entendimento 
preciso sobre o problema como também parafornecer a entrada necessária para 
o modelo matemático que está sendo formulado na próxima fase do estudo. 
Frequentemente, grande parte dos dados necessários não estará disponível 
quando se inicia o estudo, seja porque as informações jamais foram guardadas, 
seja pelo fato de o que foi registrado se encontrar desatualizado ou, então, na 
forma incorreta. Consequentemente, às vezes, normalmente é necessário instalar 
um sistema de informações gerenciais baseados em computadores para coletar 
regularmente os dados necessários e no formato desejado. A equipe de PO, em 
geral, precisa obter o apoio de diversos outros indivíduos-chave da organização 
para conseguir todos os dados vitais. Mesmo com esse empenho, grande parte 
dos dados pode ser relativamente “frágil”, isto é, estimativas grosseiras baseadas 
apenas em conjeturas. Tipicamente, uma equipe de PO despenderá um tempo 
considerável tentando melhorar a precisão dos dados para depois se adequar e 
trabalhar com o que de melhor possível possa ser obtido.
Com a ampla difusão do emprego de banco de dados e o crescimento 
explosivo m seus tamanhos em anos recentes, as equipes de PO agora 
frequentemente acham que o maior problema relativo a dados não são aqueles 
pouco disponíveis, mas sim o fato de haver dados particularmente relevantes e 
identificar os padrões de interesse nesses dados torna-se uma tarefa assustadora. 
Uma das ferramentas mais novas para as equipes de PO é uma técnica chamada 
data mining que atende a essa tarefa. Os métodos de data mining pesquisam 
grandes bancos de dados na busca de padrões de interesse que possam levar a 
decisões úteis.
 
Um estudo de uma equipe de PO realizado para o Departamento de Polícia 
de São Francisco, Califórnia – USA, resultou no desenvolvimento de um sistema 
computadorizado para a escala e emprego de patrulheiros. O novo sistema gerou 
uma economia anual de US$ 11 milhões e um aumento de US$ 3 milhões em 
receitas por multas de trânsito e melhoria em 20% em tempos de respostas. Ao 
avaliar os objetivos apropriados para esse estudo, três objetivos foram identificados:
1. Manter alto nível de segurança para o cidadão.
2. Manter o moral da tropa elevado.
3. Minimizar o custo de operações.
 
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
43
Para satisfazer o primeiro objetivo, o Departamento de Polícia e o governo 
municipal estabeleceram conjuntamente um nível de proteção desejado. O 
modelo matemático propôs então a necessidade de que esse nível de proteção 
fosse atingido. De modo semelhante, o modelo impôs a exigência de equilibrar 
a carga de trabalho entre os policiais de modo a trabalhar rumo ao segundo 
objetivo. Finalmente, o terceiro objetivo foi incorporado adotando o objetivo de 
longo prazo de minimizar o número de policiais necessários para atender esses 
dois primeiros objetivos.
FONTE: HILLIER, Frederick S.; LIEBERMANN, Gerald J. Introdução à pesquisa operacional. São 
Paulo: McGraw-Hill, 2006. p. 8.
44
RESUMO DO TÓPICO 3
Neste tópico, você viu que:
• Um PPLI é um problema de Programação Linear em que uma ou mais variáveis 
pode ser apenas números inteiros.
• Resolve-se o PPL sem se preocupar com essa restrição.
• Caso as soluções encontradas não sejam inteiras, ramifica-se o PPL em dois 
novos, atribuindo a cada um deles novas restrições.
• O processo de ramificação continua até que:
• Encontramos um PPL sem solução;
• Encontramos as soluções de todos os PPLs ramificados que obedeçam a 
restrição quanto ao tipo de variável (inteira).
• Ao encontrar um ramo do PPL que apresente solução compatível (inteira), 
define-se o valor de Z desse ramo do PPL como o Limite Inferior. Qualquer 
ramo que apresente solução (inteira ou não) menor que o limite inferior é 
imediatamente eliminado (poupando trabalho).
• As ramificações continuam nos PPLs que tenham soluções não inteiras onde o 
valor de Z seja maior que o limite inferior. 
• Se um PPL apresentar uma solução inteira maior que o Limite inferior, então 
esse valor de Z passa a ser o novo Limite Inferior, e o PPL que fazia esse papel 
anteriormente também é eliminado, assim como todos os ramos que tenham 
solução menor que o novo limite inferior.
• Fazemos esse procedimento até que se eliminem todos os ramos sem solução 
ou com solução menor que o Limite Inferior, e esse limite é a solução ótima do 
PPL original.
45
AUTOATIVIDADE
1 Modele e resolva o problema de PLI:
Uma fábrica de cristais procura planejar a produção de dois tipos de 
produtos de modo a maximizar seu lucro. Essa fábrica possui um forno para 
a fabricação de cristais que pode operar no máximo 16 horas por dia. Nesse 
forno, são produzidos dois produtos: um elefante de cristal, que precisa de 
15 minutos de forno para ficar pronto, e uma borboleta de cristal, que precisa 
de 25 minutos para ficar pronta. Cada elefante é vendido por R$ 12,00 e a 
borboleta é vendida por R$ 15,00. Quanto de cada produto essa fábrica deve 
produzir num dia de trabalho?
2 Segundo Loesch e Hein (1999, p. 146), encontre a solução ótima dos 
problemas de PLI:
a) MaxZ = 7x1 + 5x2
Sujeito a
–2x1 + x2 ≤ 2
10x1 + 6x2 ≤ 60
6x1 + 10x2 ≤ 60
x1 ≤ 5
x1 , x2 ≥ 0
x1 e x2 inteiros.
b) MinZ = 4x1 + 3x2
Sujeito a
8x1 +3 x2 ≤ 24
5x1 + 6x2 ≤ 30
x1 + 2x2 ≤ 8
x1 , x2 ≥ 0
x1 e x2 inteiros.
46
47
UNIDADE 2
SOLUÇÃO ÓTIMA
OBJETIVOS DE APRENDIZAGEM
PLANO DE ESTUDOS
A partir desta unidade, você estará apto(a) a:
• escrever um PPL na sua forma normal;
• representar um PPL no tableau Simplex;
• encontrar a solução ótima de um PPL através do método Simplex e do 
método das duas fases;
• encontrar o problema dual de um problema primal;
• representar um PPL no Microsoft Excel;
• encontrar a solução ótima de um PPL através do Solver;
• realizar a análise de pós-otimalidade de um PPL.
Esta unidade está dividida em dois tópicos. No final de cada um deles, você 
encontrará atividades que reforçarão o seu aprendizado.
TÓPICO 1 – MÉTODO SIMPLEX
TÓPICO 2 – UTILIZAÇÃO DO COMPUTADOR
48
49
TÓPICO 1
MÉTODO SIMPLEX
UNIDADE 2
1 INTRODUÇÃO
O Simplex é um método de resolução de problemas de Programação 
Linear que se baseia em operações matriciais na busca da solução ótima. Esse 
método utiliza-se de uma solução conhecida no PPL para encontrar as principais 
soluções compatíveis do problema, determinando a maior dentre elas, em 
problemas de maximização, ou a menor dentre as soluções compatíveis, em 
problemas de minimização.
A aplicação do método Simplex se dá através de um quadro específico 
que contém as informações necessárias à resolução. Seguindo uma sequência de 
procedimentos padrão, já definidos, a solução ótima e os valores das variáveis 
de decisão são determinados facilmente. Mas, para isso, é necessário que o 
modelo do PPL esteja escrito de uma maneira especial, chamada de Forma 
Padrão do PPL.
2 FORMA PADRÃO DO PPL
A fim de trabalhar com os modelos de PLs utilizando o Método Simplex, 
precisaremos reescrevê-los em sua forma padrão, obedecendo alguns critérios. 
Essa forma padrão visa organizar os modelos de PL de uma mesma forma, 
facilitando os cálculos nos quadros do Método Simplex, minimizando o tempo de 
busca pela solução ótima do PPL.
Para escrever um modelo de PPL em sua forma padrão devemos:
1. fazer com que os coeficientes da mão direita sejam números não negativos;
2. restringir todas as variáveis de decisão não restritas;
3. substituir as restrições definidas por ≤ usando variáveis de folga;
4. substituir as restrições definidas por ≥ usando variáveis de excesso;
5. ajustar, se necessário, a Função Objetivo.
UNIDADE 2 | SOLUÇÃO ÓTIMA
50
A seguir, vamos detalhar como realizar cada um dos procedimentos 
acima mencionados, utilizando um exemplo para ilustrar as alterações ocorridas 
no PPL para reescrevê-lo na forma padrão.
2.1 NÃO NEGATIVIDADE DA MÃO DIREITA
Se alguma restrição tiver como coeficiente da mão direita um número 
negativo, devemos multiplicar todos os termos da restrição por –1 para que os 
sinais sejam opostos e, dessemodo, o coeficiente da mão direita fique positivo.
Exemplo:
Max Z = 2x1 – x2 + 4x3 
Sujeito a
5x1 + 2x2 – 3x3 ≥ – 7 (Possui coeficiente da mão direita negativo)!
2x1 – 2x2 + x3 ≥ 8
com x1 e x3 não negativo
Na forma padrão, devemos alterar o sinal do coeficiente da mão direita 
da primeira restrição, que é negativo. Basta trocar todos os sinais da restrição, 
obtendo:
Max Z = 2x1 – x2 + 4x3
Sujeito a
–5x1 – 2x2 + 3x3 ≤ 7 
2x1 – 2x2 + x3 ≥ 8
com x1 e x3 não negativos
2.2 VARIÁVEIS NÃO RESTRITAS
Alguns PPLs podem assumir variáveis que não necessitem da condição de 
não negatividade (controles de caixa, por exemplo), mas na forma padrão essas 
variáveis são substituídas pela diferença entre duas novas variáveis não negativas.
Perceba que o sinal ≤ da 1ª restrição é trocado pelo sinal ≥ devido à multiplicação 
por –1. Se a restrição fosse definida pelo sinal de ≥ , este seria trocado por ≤. Nas restrições 
em que o sinal é =, ele não é alterado.
UNI
TÓPICO 1 | MÉTODO SIMPLEX
51
2.3 VARIÁVEIS DE FOLGA
O método Simplex utiliza sistemas de equações lineares na sua resolução 
(busca por Z*), nesse caso não podemos utilizar restrições definidas por 
desigualdades. Assim, toda restrição desse tipo deve ser reescrita em uma 
igualdade, obedecendo ao sinal da desigualdade.
Em restrições definidas pelo sinal ≤, devemos acrescentar uma variável 
de folga xf no 1º membro da restrição, correspondente à diferença entre os 
valores calculados na solução ótima e os máximos da restrição. Essas folgas serão 
melhores analisadas no estudo sobre Análise de Pós-Otimalidade.
Max Z = 2x1 – x2 + 4x3
Sujeito a
–5x1 – 2x2 + 3x3 ≤ 7
2x1 – 2x2 + x3 ≥ 8
com x1 e x3 não negativos (Variável x2 não restrita)!
Veja que o PPL do exemplo não especifica que a variável x2 seja não 
negativa, ou seja, que é irrestrita. Nesses casos, substituiremos a variável x2 
nas restrições pela diferença dada por x2 = x’2 – x”2 , de modo que restringimos 
x’2 e x”2 como variáveis não negativas.
E reescrevendo as restrições do modelo, temos:
 Max Z = 2x1 – x2 + 4x3
Sujeito a
–5x1 – 2(x’2 – x”2)+ 3x3 ≤ 7
2x1 – 2(x’2 – x”2) + x3 ≥ 8
x1 , x’2 , x”2 , x3 ≥ 0 
Fazendo algumas simplificações (inclusive na Função Objetivo), 
obtemos o PPL:
Max Z = 2x1 – x”2 + x”2+ 4x3
Sujeito a
–5x1 – 2x’2 + x”2+ 3x3 ≤ 7
2x1 – 2x’2 + 2x”2) + x3 ≥ 8
x1 , x’2 , x”2 , x3 ≥ 0 
UNIDADE 2 | SOLUÇÃO ÓTIMA
52
Exemplo:
Max Z = 2x1 – x’2 + x”2 + 4x3
Sujeito a
–5x1 – 2x’2 + 2x”2+ 3x3 ≤ 7 (Restrição definida por ≤)!
2x1 – 2x’2 + 2x”2+ x3 ≥ 8
x1 , x’2 , x”2 , x3 ≥ 0
A primeira restrição é definida pela desigualdade ≤, então acrescentamos 
uma variável de folga xf nas restrições e na F.O., reescrevendo a primeira restrição 
como uma igualdade.
Max Z = 2x1 – x’2 + x”2 + 4x3 + 0xf
Sujeito a
–5x1 – 2x’2 + 2x”2+ 3x3 + xf = 7 
2x1 – 2x’2 + 2x”2+ x3 + 0xf ≥ 8
x1 , x’2 , x”2 , x3 , xf ≥ 0
2.4 VARIÁVEIS DE EXCESSO
Assim como as variáveis de folga, as variáveis de excesso xe são introduzidas 
no PPL com o intuito de reescrever a restrição definida por ≥ em uma igualdade. 
Exemplo:
Max Z = 2x1 – x’2 + x”2 + 4x3 + 0xf
Sujeito a
–5x1 – 2x’2 + 2x”2+ 3x3 + xf = 7
2x1 – 2x’2 + 2x”2+ x3 + 0xf ≥ 8 (Restrição definida por ≥)!
x1 , x’2 , x”2 , x3 , xf ≥ 0
A segunda restrição é definida pela desigualdade ≥, então acrescentamos 
uma variável de excesso xe nas restrições e na F.O., reescrevendo a segunda restrição 
como uma igualdade.
Max Z = 2x1 – x’2 + x”2 + 4x3 + 0xf + 0xe
Sujeito a
–5x1 – 2x’2 + 2x”2+ 3x3 + xf + 0xe= 7
2x1 – 2x’2 + 2x”2+ x3 + 0xf + xe= 8
x1 , x’2 , x”2 , x3 , xf , xe ≥ 0
Fazemos essas alterações apenas quando for necessário. Para facilitar 
as resoluções, não usaremos as nomenclaturas xf e xe para as variáveis de folga 
e excesso, apenas usaremos índices numéricos como as variáveis de decisão 
originais do PPL.
TÓPICO 1 | MÉTODO SIMPLEX
53
Exemplo:
Max Z = 2x1 – x’2 + x”2 + 4x3 + 0x4 + 0x5
Sujeito a
–5x1 – 2x’2 + 2x”2+ 3x3 + x4 + 0x5= 7
2x1 – 2x’2 + 2x”2+ x3 + 0x4 + x5= 8
x1 , x’2 , x”2 , x3 , x4 , x5 ≥ 0
2.5 ALTERAÇÕES NA FUNÇÃO OBJETIVO
Ao longo do exemplo, necessitamos várias vezes fazer modificações na 
F.O. Essas alterações se devem ao fato de termos alterado o sistema de restrições, 
introduzindo novas variáveis, e essa inclusão ocasiona algumas modificações 
no modelo do PPL.
As variáveis de folga e de excesso não causam modificações nas 
restrições, nem na Função Objetivo, mas esta última deve ser reescrita levando 
também em conta esse tipo de variável, utilizando zeros como coeficientes das 
variáveis na F.O.
3 O ALGORÍTMO SIMPLEX
Vamos verificar o funcionamento do método simplex, passo a passo, 
através de um exemplo, e depois veremos como utilizar esse método, de maneira 
mais rápida e econômica, através do Tableau Simplex, um quadro que nos ajuda a 
realizar os cálculos necessários.
Primeiramente, vamos nos basear no nosso exemplo 2, do planejamento 
agrícola, já resolvido pelo método gráfico. Assim, poderemos comparar as 
resoluções por ambos os métodos e verificar a eficácia de cada um.
No próximo tópico, usaremos métodos computacionais para resolver esse 
mesmo problema de Programação Linear.
ESTUDOS FU
TUROS
UNIDADE 2 | SOLUÇÃO ÓTIMA
54
Para a implementação do Método Simplex, necessitamos do nosso PPL 
original:
Max L = 300xT + 400xM Função Objetivo (maximizar o lucro)
Sujeito a
xT + xM ≤ 50 Restrição ao tamanho do terreno
3xT + 2xM ≤ 120 Restrição ao uso de mão de obra
xT ≤ 30 Restrição a demanda por trigo
xM ≤ 40 Restrição a demanda por milho
xT , xM ≥ 0 Restrição à não negatividade
E agora, reescrevemos o PPL na forma padrão, usando os procedimentos 
descritos anteriormente.
Para lembrar:
1. fazer com que os coeficientes da mão direita sejam números não negativos;
2. restringir todas as variáveis de decisão não restritas;
3. substituir as restrições definidas por ≤ usando variáveis de folga;
4. substituir as restrições definidas por ≥ usando variáveis de excesso;
5. ajustar, se necessário, a Função Objetivo.
Então, vamos ao trabalho!
1. Nosso PPL original não tem coeficientes da mão direita negativos, então 
não há necessidade de alterações nesse ponto.
2. Estamos tratando de duas variáveis de decisão xT e xM, que são restritas 
quanto à não negatividade e, portanto, também não há necessidade de alterações 
nesse ponto. Mas, para nossa comodidade faremos uma pequena diferenciação 
na nomenclatura das variáveis, chamando-as de x1 e x2, respectivamente. Já que 
vamos precisar de variáveis de folga ou excesso, é natural que usemos números 
para não confundirmos todas as letras.
3. As restrições do PPL Original são desigualdades do tipo ≤ , ou seja, 
devemos introduzir em cada restrição desse tipo, uma variável de folga para 
escrevê-la numa igualdade.
Assim, ficam reescritas as restrições:
Max L = 300x1 + 400x2 Alterando xT e xM por x1 e x2
Sujeito a
x1 + x2 + x3 = 50 Introduzindo a variável de folga x3
3x1 + 2x2 + x4 = 120 Introduzindo a variável de folga x4
x1 + x5 = 30 Introduzindo a variável de folga x5
x2 + x6 = 40 Introduzindo a variável de folga x6
xi ≥ 0, com i = 1,...,6 Não negatividade de todas as variáveis
TÓPICO 1 | MÉTODO SIMPLEX
55
4. Não há restrições no PPL Original escritas por desigualdades do tipo 
≥, ou seja, não há a necessidade de introduzir em cada restrição desse tipo uma 
variável de excesso para escrevê-la numa igualdade.
5. Mas precisamos ajustar nossa Função Objetivo, visto que foram 
introduzidas as variáveis de folga no PPL. Assim, temos o modelo na sua forma 
padrão escrito por:
Max L = 300x1 + 400x2 + 0x3 + 0x4 + 0x5 + 0x6 Nova Função Objetivo
Sujeito a
x1 + x2 + x3 = 50 Introduzindo a variável de folga x3
3x1 + 2x2 + x4 = 120 Introduzindo a variável de folga x4
x1 + x5 = 30 Introduzindo a variável de folga x5
x1 + x6 = 40 Introduzindo a variável de folga x6
xi ≥ 0, com i = 1,...,6 Não negatividade de todas as variáveis
Se escrevermos o PPL usando uma forma padrão organizada teremos a 
seguinte configuração:
Max L = 300x1+ 400x2 + 0x3 + 0x4 + 0x5 + 0x6
Sujeito a
Agora, fazemos x1 = 0 e x2 = 0, chamando essas variáveis de Variáveis Não 
Básicas (VNB), e substituímos esses valores no sistema de restrições, assim:
Em Álgebra Linear, você estudou a representação de sistemas de equações 
lineares usando a forma matricial. Podemos, então, reescrever nosso sistema de 
restrições acima usando a operação de multiplicação de matrizes como segue:
UNIDADE 2 | SOLUÇÃO ÓTIMA
56
Essa forma nos mostra o porquê de as variáveis x3, x4, x5 e x6 serem 
chamadas, nesse momento, de Variáveis Básicas (VB). Seus coeficientes formam 
uma matriz Identidade, e o sistema formado representa uma base canônica 
para um subespaço vetorial de R4. Mas deixemos esses detalhes de lado, e nos 
concentremos no PPL.
A vantagem dessa representação consiste em determinar uma solução 
básica inicial para o PPL. Assim, com 
 
Variáveis não básicas
 
 Variáveis básicas
E, desse modo, temos a solução inicial que pode ser escrita por x = 
(0,0,50,120,30,40). E o valor da função objetivo para essa solução é dado por
Que nos dá um lucro nulo.
Observando os coeficientes da Função Objetivo para x1 e x2 (coeficientes 
+300 e +400), vemos que, mudando os valores de x1 ou x2 para um número 
positivo diferente de zero, o valor de L na F.O. também será positivo. Como nosso 
objetivo é maximizar o valor de L, e qualquer valor positivo é maior do que zero, 
verificamos que a presente solução x = (0,0,50,120,30,40) não é a solução ótima 
do PPL, já que L pode se aumentado se aumentarmos o valor de x1 ou x2. Isso 
significa fazer com que x1 ou x2 se torne uma VB (entre na base). Mas, para isso, 
devemos fazer uma troca de variáveis.
Devemos escolher que variável entra na base (deixando de ter valor zero) 
e que variável sai na base (assumindo o valor zero).
A escolha da variável que entra na base é simples, basta verificar que 
VNB possui maior coeficiente na F.O. Consequentemente, haverá uma maior 
contribuição para o valor de L se usarmos a variável com maior coeficiente.
TÓPICO 1 | MÉTODO SIMPLEX
57
Em nosso exemplo, x2 tem maior coeficiente (+400) e por isso deve entrar 
na base.
Mas para a entrada de x2 na base, uma das variáveis da base deve sair. 
Qual delas?
Ao aumentarmos o valor da variável x2, as variáveis x3, x4 e x6 devem ter 
seus valores reduzidos para que se mantenham as igualdades das restrições, já 
que x1 = 0. Assim, devemos procurar qual a VB que primeiro se anula com o 
aumento de x2.
Temos que:
x3 = 0 quando x2 = 50, pois x1 +x2 +x3 = 0 + 50 + 0 = 50
x4 = 0 quando x2 = 60, pois 3x1 + 2x2 + x4 = 3 • 0 + 2 • 60 + 0 = 120
x5 não depende de x2 e com isso não se altera
x6 = 0 quando x2 = 40, pois 2x2 + x6 = 40 + 0 = 40
Logo, x6 deve sair da base, já que o aumento de x2 fará com que x6 diminua, 
podendo admitir um valor negativo, o que não pode ocorrer (restrição à não 
negatividade).
Fazendo a troca das variáveis da base, tirando x6 (que passa a valer zero) 
e colocando x2, devemos reescrever o PPL em função das variáveis não básicas (x1 
e x6) usando a relação x2 = 40 – x6 para as substituições, mantendo a restrição x2 
+ x6= 40. 
Assim fica o PPL: E simplificando as expressões:
Max L = 300x1 + 400(40 – x6) Max L = 300x1 – 400x6 + 16000
Sujeito a Sujeito a
E analisando a função objetivo, percebemos que (para x1 = x6 = 0) Z = 
16000, valor maior do que aquele obtido pela solução básica inicial (Z = 0). Mas 
podemos observar que o coeficiente da variável x1 é um número positivo e com 
UNIDADE 2 | SOLUÇÃO ÓTIMA
58
isso qualquer valor maior que zero para essa variável faz com que o valor de Z 
seja maior. Ou seja, x1 deve entrar na base, forçando uma nova troca de variáveis 
da base.
Verificamos qual variável se anula primeiro quando aumentamos o valor 
da variável x1 nas igualdades das restrições, com x6 = 0:
A variável x2 não depende de x1 e por isso não se altera.
Se aumentarmos o valor da variável x1, a primeira variável que se anula 
com esse aumento é x3, logo, é essa variável que deve sair da base.
Trocando as variáveis, devemos reescrever o PPL em função das variáveis 
não básicas (x3 e x6) usando a expressão x1 = 10 – x3 + x6 para as substituições, 
mantendo a primeira restrição:
E simplificando as expressões:
Max L = 300 . (10 – x3 + x6) – 400x6 + 16000
Sujeito a
x1 + x3 – x6 = 10
3 . (10 – x3 + x6) + x4 – 2x6 = 40
10 – x3 + x6 + x5 = 30
x2 + x6 = 40
xi ≥ 0, com i = 1,...,6
Aplicando as propriedades distributivas e simplificando as expressões, 
temos o PPL:
Max L = –300x3 – 100x6 + 19000
Sujeito a
x1 + x3 – x6 = 10
x3 + x4 – x6 = 10
–x3 + x6 + x5 = 20
x2 + x6 = 40
x1 ≥ 0, com i = 1,...,6
Agora Z está escrito em função das variáveis não básicas x3 e x6, que 
possuem coeficientes negativos. A entrada de qualquer uma das variáveis na base 
x1 + x3 – x6 = 10 ⇒ x1 + x3 – 0 = 10 ⇒ x3 = 10 – x1 , ou seja, x3 = 0 quando x1 = 10
3x1 + x4 – 2x6 = 40 ⇒ 3x1 + x4 – 0 = 40 ⇒ x4 = 40 – 3x1 , ou seja, x4 = 0 quando x1 = 
x1 + x5 = 30 ⇒ x5 = 30 – x1 , ou seja, x5 = 0 quando x1 = 30 
40
3 .
TÓPICO 1 | MÉTODO SIMPLEX
59
trará um valor negativo para a função objetivo e, consequentemente, o valor de Z 
diminuirá. Assim, estamos diante da solução ótima do PPL.
Os valores da solução são calculados fazendo x3 = 0 e x6 = 0, e assim:
Que, se substituídos na FO, trazem Z = – 300 . 0 – 100 . 0 + 19000 = 19000.
O mesmo valor de Z pode ser verificado na função objetivo original do 
PPL onde tínhamos 
Z = 300x1 + 400x2 ⇒ Z = 300 . 10 + 400 . 40 ⇒ Z = 3000 + 16000 ⇒ Z = 19000.
A busca pela solução ótima de um PPL através do método simplex se dá 
por uma sequência de procedimentos a serem seguidos. Esses procedimentos 
podem ser resumidos conforme a seguir:
1º Solução básica inicial: inicia-se escrevendo o PPL na sua forma padrão, 
adotando os coeficientes da mão direita como valores para as variáveis artificiais, 
usando-as como uma solução básica inicial.
2º Teste de otimalidade: verificam-se os coeficientes das variáveis não 
básicas na função objetivo:
• se todos os coeficientes forem positivos, então a presente solução é ótima;
• se há coeficientes negativos, escolhe-se o coeficiente negativo de maior valor 
absoluto para a variável que deve entrar na base.
3º Troca da base: escrevem-se as variáveis básicas do PPL em função das 
variáveis não básicas e verifica-se qual VB anula-se primeiro ao aumentar o valor 
da variável escolhida para entrar na base.
4º Reformulação do PPL: escreve-se a função objetivo e as restrições do 
PPL em função das novas VNB, simplificando-se o quanto for possível.
5º Solução do PPL: adotando-se 0 como valor das VNB, calcula-se o valor 
das VB e da função objetivo.
6º Repete-se o procedimento a partir do 2º passo.
UNIDADE 2 | SOLUÇÃO ÓTIMA
60
4 TABLEAU SIMPLEX
O tableau simplex nada mais é do que um quadro resumo do método 
simplex. Nele são feitos todos os cálculos efetuados pelo método, mas de uma 
maneira resumida. 
A estrutura do tableau simplex é baseada na tabela a seguir:
TABELA 4 - ESTRUTURA DO TABLEAU SIMPLEX
VARIÁVEIS 
BÁSICAS X1 X2 X3 ... Xn b CÁLCULOS
xB1
xB2
xB3
...
xBm
FUNÇÃO 
OBJETIVO
FONTE: Os autores
A primeira linha do quadro contém os nomes de todas as variáveis do PPL.
A última linha contém os coeficientes da Função Objetivo.
As demais linhas contêm os valores das restrições do PPL.
Na primeira coluna indicamos quais são as variáveis básicas.
Na coluna b, indicamos os coeficientes da mão direita, ou seja, os limites 
das restrições. É essa coluna que nos indicará quais os valores das variáveis para 
determinar a solução ótima.
A última coluna é reservada para efetuar os cálculos necessários para 
decidir que variável deixa a base.
A célula destacada em cinza nos indicará qual será o valor da Função 
Objetivo quando encontrarmos a solução ótima.
Novamente, vamos usar nosso exemplo do planejamento agrícola para 
explicar o funcionamento desse quadro e as alterações realizadas na busca da 
soluçãoótima.
TÓPICO 1 | MÉTODO SIMPLEX
61
Primeiro, vamos relembrar (se é que já não o decoramos) o PPL do 
exemplo, já na sua forma padrão.
Max L = 300x1 + 400x2 + 0x3 + 0x4 + 0x5 + 0x6
Sujeito a
Lembrando um pouquinho da disciplina de Álgebra Linear, podemos 
representar o sistema de equações das restrições na forma matricial a seguir:
Que pode, ainda, ser representado pela matriz ampliada associada ao 
sistema:
É essa matriz ampliada que preencherá nossas linhas no tableau simplex. 
Assim:
TABELA 5 - TABLEAU SIMPLEX
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 X6 b CÁLCULOS
x3 1 1 1 0 0 0 50
x4 3 2 0 1 0 0 120
x5 1 0 0 0 1 0 30
UNIDADE 2 | SOLUÇÃO ÓTIMA
62
x6 0 1 0 0 0 1 40
Max L -300 -400 0 0 0 0 0
FONTE: Os autores
Já podemos perceber que a coluna b traz os valores das variáveis básicas 
como solução básica inicial do PPL.
Percebemos também que a linha da Função Objetivo recebeu os valores 
de Max L, que indica o objetivo do PPL, e os coeficientes -300 e -400. Isso acontece 
porque, na forma padrão para o tableau simplex, escrevemos a função objetivo 
colocando todos os coeficientes à esquerda da igualdade. Assim, Max L = 300x1 + 
400x1 fica Max L – 300x1 + 400x1 = 0.
Sem nos preocuparmos com detalhes matemáticos, essas alterações 
nos sinais são necessárias para combinar com os testes de otimalidade que são 
realizados no método simplex formal, como visto anteriormente. Esses coeficientes 
servem para duas coisas:
• para verificar se a solução ótima foi encontrada. Isso acontece quando não 
houver mais nenhum coeficiente negativo nessa linha;
• e, caso haja coeficientes negativos, para definir qual variável entra na base. 
Nesse caso, devemos escolher o coeficiente “mais negativo” para definir qual 
a variável deve entrar na base. 
No nosso exemplo, temos dois coeficientes negativos na linha da F.O., 
então, ainda não temos a solução ótima. Devemos decidir que variável entra na 
base, como -400 é o coeficiente mais negativo da linha, definimos a variável x2 
para entrar na base.
A coluna que contém a variável x2 agora será tratada de forma especial, e 
por isso chamaremos a coluna em que esse número aparece de coluna de trabalho, 
como faz Bronson (1985, p. 29). É com a ajuda dessa coluna que definimos qual 
variável sai da base. Para isso, devemos fazer uma simples divisão entre os 
coeficientes da coluna b, por seus respectivos coeficientes da coluna de trabalho. 
Se houver mais de um coeficiente com o mesmo valor, gerando um empate 
para decidir qual variável entra na base, pode-se escolher qualquer uma dessas variáveis.
IMPORTANT
E
TÓPICO 1 | MÉTODO SIMPLEX
63
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 X6 b CÁLCULOS
x3 1 1 1 0 0 0 50 50/1 = 50
x4 3 2 0 1 0 0 120 120/2 = 60
x5 1 0 0 0 1 0 30 30/0 = ?
x6 0 1 0 0 0 1 40 40/1 = 40
Max L -300 -400 0 0 0 0 0 x2 entra na base e x6 sai da base
Para continuar a busca pela solução ótima, devemos reescrever o quadro a 
fim de converter o pivô em 1 e, todos os demais coeficientes da coluna de trabalho 
em zeros. Para isso, utilizaremos as operações sobre linhas de matriz (método 
de eliminação de Gauss), como visto em Álgebra Linear. Para simplificar, vamos 
escrever o sistema associado ao quadro simplex:
Se nenhum coeficiente da coluna de trabalho for positivo, então o PPL não 
terá solução!
IMPORTANT
E
TABELA 6 - TABLEAU SIMPLEX – TROCA DE VARIÁVEIS ( x
2
 e x
6
)
 
FONTE: Os autores
Assim, definimos a variável x6 para deixar a base, pois o resultado da 
divisão da coluna b (40) pelo coeficiente da coluna de trabalho (1) é o menor 
dentre os resultados, visto que não podemos dividir por zero (como ocorreu na 4ª 
linha do quadro). O coeficiente, 1 situado na intersecção da linha x6 com a coluna 
de trabalho é chamado de pivô (destacado em cinza mais escuro).
Vamos usar o elemento a42 como pivô para eliminar todos os elementos da 
segunda coluna da matriz:
UNIDADE 2 | SOLUÇÃO ÓTIMA
64
Para eliminar o elemento a12, vamos fazer L1 = L1 – L4.
Para eliminar o elemento a22, vamos fazer L2 = L2 – 2L4.
Para eliminar o elemento a52, vamos fazer L5 = L5 + 400L4.
Assim,
Agora, vamos reescrever nossa tabela simplex:
TABELA 7 - TABELA SIMPLEX (EXEMPLO)
Se você tiver dificuldades em compreender o que foi feito na eliminação de 
Gauss, reveja seu caderno de Álgebra Linear.
DICAS
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 X6 b CÁLCULOS
x3 1 0 1 0 0 -1 10
x4 3 0 0 1 0 -2 40
x5 1 0 0 0 1 0 30
x2 0 1 0 0 0 1 40
Max L -300 0 0 0 0 400 16000
FONTE: Os autores
TÓPICO 1 | MÉTODO SIMPLEX
65
TABELA 8 - TABELA SIMPLEX (EXEMPLO)
Perceba que a variável x2 assumiu o lugar da variável x6 na coluna das 
variáveis básicas. Também não é difícil notar que as colunas de x 3, x4, x5 e x2, nesta 
ordem, formam uma matriz identidade, ou seja, uma base canônica.
Então, devemos recomeçar o trabalho. Nesse momento, nossa solução 
é dada por x3 = 10, x4 = 40, x5 = 30, x2 = 40 e o valor da função objetivo é 16.000. 
Ainda não estamos diante da solução ótima, visto que ainda há coeficientes 
negativos na linha da função objetivo (-300). Assim, devemos fazer com que a 
variável x1 entre na base e decidir qual variável deve deixar a base. Para isso, 
devemos dividir os coeficientes da coluna b pela nova coluna de trabalho (x1).
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 X6 b CÁLCULOS
x3 1 0 1 0 0 -1 10 10/1 = 10
x4 3 0 0 1 0 -2 40 40/3 = 13,33...
x5 1 0 0 0 1 0 30 30/1 = 30
x2 0 1 0 0 0 1 40 40/0 = ?
Max L -300 0 0 0 0 400 16000 x1 entra na base e x3 sai da base
FONTE: Os autores
Agora, usaremos o coeficiente 1 da linha x3 e coluna x 1 como pivô para 
zerar todos os demais elementos da coluna de trabalho. Vamos escrever a matriz 
que representa o quadro simplex. Futuramente, deixaremos esse passo de lado, 
mas, por enquanto, é mais fácil para fazer o escalonamento com a matriz do que 
com a tabela simplex.
Vamos usar o elemento a11 como pivô para eliminar todos os elementos da 
primeira coluna da matriz:
Para eliminar o elemento a21, vamos fazer L2 = L2 – 3L1.
Para eliminar o elemento a31, vamos fazer L3 = L3 – L1.
UNIDADE 2 | SOLUÇÃO ÓTIMA
66
Para eliminar o elemento a51, vamos fazer L3 = L3 + 300L1.
Assim,
E, de volta à tabela simplex, substituindo a variável x1 no lugar da variável 
x3 na coluna das variáveis básicas, temos:
TABELA 9 - TABELA SIMPLEX (EXEMPLO)
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 X6 b CÁLCULOS
x1 1 0 1 0 0 -1 10
x4 0 0 -3 1 0 1 10
x5 0 1 0 0 0 1 20
x2 0 1 0 0 0 1 40
Max L 0 0 300 0 0 100 19000
FONTE: Os autores
Novamente, vamos verificar os coeficientes da última linha do quadro 
(da F.O.). Percebemos que não há coeficientes negativos na linha e, portanto, 
estamos diante da solução ótima do PPL. Essa solução é dada pelos valores 
das variáveis básicas especificados na coluna b. Logo, por x1 = 10, x4 = 10, x5 
= 20, x2 = 40 e o valor da função objetivo é 19.000, que pode ser verificado 
através da função objetivo original do PPL, Max L = 300 • 10 + 400 • 40 + 0 • 0 
+ 0 • 10 + 0 • 20 + 0 • 0 = 3000 + 16000 = 19000 
TÓPICO 1 | MÉTODO SIMPLEX
67
Para que possamos ver a evolução do método simplex no tableau, vamos 
organizar a resolução colocando as tabelas utilizadas em sequência:
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 X6 b CÁLCULOS
x3 1 1 1 0 0 0 50 50/1 = 50
x4 3 2 0 1 0 0 120 120/2 = 60
x5 1 0 0 0 1 0 30 30/0 = ?
x6 0 1 0 0 0 1 40 40/1 = 40
Max L -300 -400 0 0 0 0 0
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 X6 b CÁLCULOS
x3 1 0 1 0 0 -1 10 10/1 = 10
x4 3 0 0 1 0 -2 40 40/3 = 13,333...
x5 1 0 0 0 1 0 30 30/1 = 30
x2 0 1 0 0 0 1 40 40/0 = ?
Max L -300 0 0 0 0 400 16000
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 X6 b CÁLCULOS
x1 1 0 1 0 0 -1 10
x4 0 0 -3 1 0 1 10
x5 0 1 0 0 0 1 20
x2 0 1 0 0 0 1 40
Max L 0 0 300 0 0 100 19000
4.1 DEGENERESCÊNCIA
No método simplex, pode ocorrer de estarmos trabalhando com um PPL 
em que a troca de variáveis da base não altera o valor da função objetivo, ou 
então, a troca de variável gera um ciclo em que uma variável que deixou a base 
volta a entrar na base, para depois sair, e entrar novamente,e assim por diante, 
repetindo a mesma solução periodicamente.
Conforme Loesch e Hein (1999, p. 84), o tratamento da degenerescência 
pode ser previsto no método simplex. O método da perturbação de Charnes é uma 
UNIDADE 2 | SOLUÇÃO ÓTIMA
68
das técnicas que previnem contra a formação do possível laço infinito que pode ser 
causado pela situação de degenerescência. No entanto, dado que, em problemas 
reais, essa situação praticamente não ocorre, ou pelo menos, não há evidências ou 
registros de que tenham ocorrido, não apresentaremos essas situações.
4.2 MÉTODO DAS DUAS FASES
Quando o sistema de restrições do PPL apresenta todas as restrições do tipo 
≤, não há problemas em resolvê-lo pelo método simplex, mas quando existe uma 
ou mais restrições do tipo ≥ temos mais uma alteração a fazer. O problema ocorre 
porque, na forma padrão, uma restrição do tipo ≥ recebe uma variável de excesso 
cujo coeficiente é -1, o que não nos dá uma solução básica inicial compatível. Pode-
se resolver esse problema utilizando-se o método das duas fases.
Esse método consiste em introduzir uma variável de excesso (com 
coeficiente -1) para as restrições do tipo ≥ e ainda uma variável artificial (com 
coeficiente +1) nessa mesma restrição. Assim, sempre teremos uma solução básica 
inicial, desde que usemos as variáveis artificiais nas restrições.
Para trabalhar com o método das duas fases, devemos imaginar uma 
nova função objetivo formada pela soma das variáveis artificiais que deverá ser 
minimizada. Devemos fazer o processo do método simplex com essa nova função 
Min W até que se tenha o valor 0 como solução.
Vamos acompanhar o exemplo para melhor entender o método das duas 
fases:
MaxZ = x1 + x2
Sujeito à
5x1 + 2x2 ≤ 2
2x1 – x2 ≥ 0,2
3x1 + 5x2 ≥ 1,5
x1 , x2 ≥ 0
Vamos colocá-lo em sua forma padrão, adicionando uma variável de folga 
na primeira restrição e uma variável de excesso e uma variável artificial em cada 
restrição do tipo ≥. Assim,
MaxZ = x1 + x2
TÓPICO 1 | MÉTODO SIMPLEX
69
Sujeito a
5x1 + 2x2 +x3 = 2
2x1 – x2 –x4 +xa1 = 0,2
3x1 + 5x2 – x5 + xa2 = 1,5
x1 , x2 , x3 , x4 , x5 , xa2 , xa2 ≥ 0
Agora vamos escrever nossa função objetivo artificial MinW = xa1 + xa2. 
Mas essa função deve ser escrita em função das variáveis não básicas:
xa1 = 0,2 – 2x1 + x2 + x4
xa2 = 1,5 – 3x1 – 5x2 + x5
W = 1,7 – 5x1 – 4x2 + x4 + x5
Assim, nossa função objetivo artificial na forma padrão simplex fica 
MinW = 5x1 + 4x2 – x4 – x5 = 1,7. 
Vamos escrever o nosso PPL no tableau simplex:
TABELA 10 - TABLEAU SIMPLEX
Como queremos minimizar o valor de W, devemos verificar se há coeficientes 
positivos na linha da função objetivo W. Lembre-se que, quando a função é de 
maximização, procuramos o coeficiente mais negativo. Então, nesse caso, devemos 
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 Xa1 Xa2 b CÁLCULOS
x3 5 2 1 0 0 0 0 2
xa1 2 -1 0 -1 0 1 0 0,2
xa2 3 5 0 0 -1 0 1 1,5
Max Z -1 -1 0 0 0 0 0 0
Min W 5 4 0 -1 -1 0 0 1,7
FONTE: Os autores
Veja que colocamos uma nova linha no quadro referente à função objetivo 
auxiliar. Na primeira fase do método, devemos fazer com que o valor de W (atualmente -1,7) 
chegue a zero, usando as operações sobre a tabela.
IMPORTANT
E
UNIDADE 2 | SOLUÇÃO ÓTIMA
70
procurar o coeficiente mais positivo, ou seja, 5, fazendo com que a coluna x1 seja 
nossa coluna de trabalho. Vamos à coluna de cálculos:
TABELA 11 - TABLEAU SIMPLEX
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 Xa1 Xa2 b CÁLCULOS
x3 5 2 1 0 0 0 0 2 =2/5 = 0,4
xa1 2 -1 0 -1 0 1 0 0,2 0,2/2 = 0,1
xa2 3 5 0 0 -1 0 1 1,5 1,5/3 = 0,5
Max Z -1 -1 0 0 0 0 0 0 x1 entra na base e xa1 
sai da baseMin W 5 4 0 -1 -1 0 0 1,7
FONTE: Os autores
Devemos dividir a linha xa1 por 2, para que o pivô seja 1, e zerar todos os 
demais elementos da coluna de trabalho. Escrevendo a matriz associada, aplicamos 
a eliminação de Gauss. Seu trabalho, por enquanto, é conferir os cálculos.
TABELA 12 - TABLEAU SIMPLEX
Variáveis 
Básicas x1 x2 x3 x4 x5 xa1 xa2 b Cálculos
x3 0 4,5 1 2,5 0 -2,5 0 1,5
x1 1 -0,5 0 -0,5 0 0,5 0 0,1
xa2 0 6,5 0 1,5 -1 -1,5 1 1,2
Max Z 0 -1,5 0 -0,5 0 0,5 0 0,1
Min W 0 6,5 0 1,5 -1 -2,5 0 1,2
FONTE: Os autores
Perceba que trocamos a variável xa1 por x1 na coluna das variáveis básicas, 
e que os valores de Z e W mudaram: Z aumentou e W diminuiu. Mas ainda há 
TÓPICO 1 | MÉTODO SIMPLEX
71
coeficientes positivos na linha de Min W. Então, não temos a solução ótima da 
primeira fase ainda.
O coeficiente 6,5 da coluna x2 é o mais positivo e, por isso, x2 deve entrar 
na base. Quem sai?
TABELA 13 - TABLEAU SIMPLEX
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 Xa1 Xa2 b CÁLCULOS
x3 0 4,5 1 2,5 0 -2,5 0 1,5 1,5/4,5 = 0,333...
x1 1 -0,5 0 -0,5 0 0,5 0 0,1
xa2 0 6,5 0 1,5 -1 -1,5 1 1,2 1,2/6,5 = 0,185
Max Z 0 -1,5 0 -0,5 0 0,5 0 0,1 x2 entre na base 
e xa2 sai da baseMin W 0 6,5 0 1,5 -1 -2,5 0 1,2
FONTE: Os autores
Assim, dividimos a linha de xa2 por 6,5 para deixar o pivô 1, e zeramos os 
demais elementos da coluna de trabalho x2. Assim, fica a nova tabela simplex:
TABELA 14 - TABLEAU SIMPLEX
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 Xa1 Xa2 b CÁLCULOS
x3 0 0 1 1,462 0,692 -1,462 -0,692 0,669
x1 1 0 0 -0,385 -0,077 0,385 0,077 0,192
x2 0 1 0 0,231 -0,154 -0,231 0,154 0,185
Max Z 0 0 0 -0,154 -0,231 0,154 0,231 0,377
Min W 0 0 0 0 0 -1 -1 0
FONTE: Os autores
Para evitar números com muitas casas decimais, fizemos um arredondamento 
para apenas três casas.
UNI
UNIDADE 2 | SOLUÇÃO ÓTIMA
72
Nessa nova tabela, as variáveis artificiais não estão mais na base e, por 
isso, seus valores são zero. Assim, W = 0 e chegamos ao final da 1ª fase.
Para a segunda fase, eliminamos a linha Min W e continuamos com o 
método simplex até que tenhamos a solução ótima, ou seja, até que a linha Max Z 
não tenha mais coeficientes negativos.
Veja que o coeficiente mais negativo da linha Max Z é -0,231, e assim, a 
coluna x 5 será nossa coluna de trabalho. De novo, aos cálculos!
TABELA 15 - TABLEAU SIMPLEX
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 b CÁLCULOS
x3 0 0 1 1,462 0,692 0,669 0,669/0,692 = 0,967
x1 1 0 0 -0,385 -0,077 0,192
x2 0 1 0 0,231 -0,154 0,185
Max Z 0 0 0 -0,154 -0,231 0,377 x5 entra, x 3 sai
FONTE: Os autores
Usando a coluna de trabalho x5 chegamos à tabela:
TABELA 16 - TABLEAU SIMPLEX
VARIÁVEIS 
BÁSICAS
X1 X2 X3 X4 X5 b CÁLCULOS
x5 0 0 1,445 2,113 1 0,967
x1 1 0 0,111 -0,222 0 0,266
x2 0 1 0,223 0,556 0 0,334
Max Z 0 0 0,334 0,334 0 0,6
FONTE: Os autores
E como não há mais coeficientes negativos na linha Max Z, esta é a solução 
ótima do PPL. Assim: x1 = 0,266 , x2 = 0,334 , x5 = 0,967 e Z* = 0,6.
Sempre que, durante a primeira fase do método, não encontrarmos 
coeficientes positivos na linha Min W, mas o valor de W ainda não for zero, estaremos 
diante de um PPL sem solução.
IMPORTANT
E
TÓPICO 1 | MÉTODO SIMPLEX
73
5 DUALIDADE
Na Teoria da Dualidade, vamos estudar o algoritmo primal-dual e 
verificar como podemos usar algumas características especiais dos modelos de 
Programação Linear para buscar maneiras mais fáceis de encontrar a solução 
ótima sob certas condições.
5.1 ALGORITMO PRIMAL-DUAL
Os problemas de PL podem ser escritos em forma de matrizes como:
MaxZ = cT . x
Sujeito à
 
 A . x ≤ b
 x ≥ 0
 
Assim, c é uma matriz de ordem 1xn, cujos elementos são os coeficientes 
da função objetivo, A é uma matriz mxn, com os coeficientes das restrições, e b é 
uma matriz mx1, com os coeficientes da mão direita das restrições.
O que buscamos é uma matriz x que contenha a solução ótima do PPL.
A esse problema daremos o nome de primal (primitivo).
Acontece que “todo problema de programação linear nas variáveis x1, x2, 
..., xn tem associado a ele um outro problema de programação linear nas variáveis 
y1, y 2, ..., ym (onde m é o número de restrições do problema original) conhecido 
como o seu dual. O problema original, conhecido como primal determina 
completamente o seu dual” (BRONSON, 1985, p. 40).
Vamos então determinar qual é o problema dual do nosso PPL original:
Se o primal é um problema de maximização,então, o dual será de 
minimização, e vice-versa.
Os coeficientes da mão direita do primal (matriz b) são os coeficientes da 
função objetivo do dual (bT), e vice-versa.
A matriz transposta dos coeficientes das restrições do primal será a matriz 
dos coeficientes das restrições do dual. E as variáveis do problema dual serão uma 
reformulação das restrições do problema primal.
Assim, fica o problema dual:
UNIDADE 2 | SOLUÇÃO ÓTIMA
74
MinZ = bT . y
Sujeito à
 AT . y ≥ c
 y ≥ 0
Tomemos um exemplo para compreender melhor:
Seja o Problema de Programação Linear dado por
MaxZ = 3x1 + 5x2
Sujeito a
x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 , x2 ≥ 0
Chamando nosso PPL de problema primal, representamos as restrições do 
primal na forma matricial por
E escrevemos o problema dual usando essas matrizes. A matriz b nos 
dá os coeficientes da função objetivo do dual. E identificando as linhas de A por 
y1, y2 e y3 como as variáveis do dual, escrevemos ATy para as suas restrições. Os 
coeficientes da mão direita do dual serão os coeficientes da função objetivo do 
primal. Assim, temos o dual
Min Z = 4y1 + 12y2 + 18y3
Sujeito à
1y1 + 3y3 ≥ 3
2y2 + 2y3 ≥ 5
y1 , y2 , y3 ≥ 0
x1 ≤ 4
 2x2 ≤ 12 ⇒
3x1 + 2x2 ≤ 18
1 0
0 2
3 2
4
12
18
x1
x2
⇒ Ax ≤ b{ [ [[] ]] ≤•
TÓPICO 1 | MÉTODO SIMPLEX
75
Agora, acompanhe com muita atenção o exemplo a seguir, pois nele há 
diversas situações que devem ser consideradas na teoria da dualidade:
Seja o PPL 
MinZ = –5x1 + 2x2 + x3
Sujeito a
 3x1 + 7x2 ≤ 23
 5x1 – x3 ≥ 8
 x1 + x2 + x3 = 15
 x1 , x2 , x3 ≥ 0
Que organizamos alterando a função objetivo para
Max Z = +5x1 – 2x2 – x3
E alterando as restrições conforme segue:
 3x1 + 7x2 ≤ 23
 –5x1 – x3 ≤ –8
 x1 + x2 + x3 ≥ 15
 x1 + x2 + x3 ≤ 15
 x1 , x2 , x3 ≥ 0
Veja que a segunda restrição teve seu sinal alterado de ≥ para ≤ , alterando 
os sinais dos coeficientes das variáveis e da mão direita (multiplicamos a restrição 
por -1), e note, também, que a terceira restrição x1 + x2 + x3 = 15 foi separada em duas 
restrições correspondentes. Vamos agora multiplicar a nova terceira restrição por 
-1 para alterar o sinal da desigualdade, escrevendo então nosso PPL primal:
Note que os sinais das restrições são alterados de ≤ para ≥. Isso ocorre devido 
ao fato de que as variáveis x
1
 e x
2
 são maiores que 0. Usamos os mesmos sinais da 
restrição ao valor das variáveis do primal para as restrições do dual.
IMPORTANT
E
UNIDADE 2 | SOLUÇÃO ÓTIMA
76
Max Z = 5x1 – 2x2 – x3
Sujeito a
E vamos escrever o PPL dual, usando as variáveis y1, y2, y3 e y4, associadas 
as quatro restrições do primal. Os coeficientes da mão direita serão os coeficientes 
da função objetivo, que agora será de minimização, ou seja, MinZ = 23y1 – 8y2 – 
15y3 + 15y4.
O conjunto de restrições do primal (fazendo a matriz transposta) será o 
conjunto de restrições do dual, com os coeficientes da função objetivo no lugar 
dos coeficientes da mão direita. Assim,
 3y1 –5y2 –y3 +y4 ≥ 5
 7y1 +0y2 –y3 +y2 ≥ –2
 0y1 +y2 –y3 +y4 ≥ –1
 y1, y2, y3, y4 ≥ 0 
Assim, temos o comparativo entre primal e dual:
PPL Primal PPL Dual
MaxZ = 5x1 – 2x2 – x3
Sujeito à
3x1 + 7x2 ≤ 23
–5x1 + x3 ≤ –8
–x1 – x2 – x3 ≥ –15
x1 + x2 + x3 ≤ 15
x1 , x2 , x3 ≥ 0
MinZ = 23y1 – 8y2 – 15y3 + 15y4.
Sujeito à
3y1 – 5y2 – y3 + y4 ≥ 5
7y1 – y3 + y2 ≥ –2
+ y2 –y3 +y4 ≥ –1
y1, y2, y3, y4 ≥ 0
Perceba que no modelo PPL Dual há restrições cujos coeficientes da 
mão direita são negativos, o que não permitimos na forma padrão. Essa nova 
característica dos PPLs tem grande utilidade se pensarmos em resolver um PPL 
TÓPICO 1 | MÉTODO SIMPLEX
77
Dual ao invés de seu primal. Isso melhora se entendermos a importância do 
seguinte Teorema:
Se existe uma solução ótima para o problema primitivo ou para o dual 
simétrico, então o outro problema tem uma solução ótima e as duas 
funções objetivo apresentam o mesmo valor ótimo. (BRONSON, 1985, 
p. 40).
Você compreendeu? Isso quer dizer que tanto faz se resolvermos o primal 
ou o dual de um PPL, se houver uma solução ótima, ela será igual para os dois 
casos. Ou seja, dependendo da situação, podemos escolher entre resolver o 
problema primal ou o dual, como no caso de haver muitas restrições do tipo ≥ 
ou com os coeficientes da mão direita negativos. Também modelos que tenham 
muitas restrições e poucas variáveis (que usam muitas linhas no tableau simplex, 
por exemplo) podem ser resolvidos usando-se poucas restrições, já que as 
restrições do dual serão em mesmo número que as variáveis do primal.
Também é importante saber que, dado um modelo primal, o modelo dual do 
dual é igual ao modelo primal, ou seja, se escrevermos o dual de um modelo e, depois, 
escrevermos o dual desse modelo dual, teremos novamente o modelo primal.
UNI
78
RESUMO DO TÓPICO 1
Neste tópico, você viu que: 
• Para escrever um modelo de PL em sua forma padrão, devemos:
 1° Fazer com que os coeficientes da mão direita sejam números não negativos;
 2° Restringir todas as variáveis de decisão não restritas;
 3° Substituir as restrições definidas por ≤ usando variáveis de folga;
 4° Substituir as restrições definidas por ≥ usando variáveis de excesso;
 5° Ajustar, se necessário, a Função Objetivo.
• Para resolver um modelo através do modelo simplex, vimos os procedimentos:
 1º Solução básica inicial: inicia-se escrevendo o PPL na sua forma padrão, 
adotando os coeficientes da mão direita como valores para as variáveis 
artificiais, usando-as como uma solução básica inicial.
 2º Teste de otimalidade: verificam-se os coeficientes das variáveis não básicas 
na função objetivo:
• se todos os coeficientes forem positivos, então a presente solução é ótima;
• se há coeficientes negativos, escolhe-se o coeficiente negativo de maior valor 
absoluto para a variável que deve entrar na base.
 3º Troca da base: escrevem-se as variáveis básicas do PPL em função das 
variáveis não básicas e verifica-se qual VB anula-se primeiro ao aumentar o 
valor da variável escolhida para entrar na base.
 4º Reformulação do PPL: escreve-se a função objetivo e as restrições do PPL 
em função das novas VNB, simplificando-se o quanto for possível.
 5º Solução do PPL: adotando-se 0 como valor das VNB, calcula-se o valor das 
VB e da função objetivo.
 6º Repete-se o procedimento a partir do 2º passo.
• É mais fácil fazer a representação do modelo no tableau simlex para resolvê-lo.
79
VARIÁVEIS 
BÁSICAS X1 X2 X3 ... Xn b CÁLCULOS
xB1
xB2
xB3
...
xBm
Função 
Objetivo
Em modelos com restrições ≥, usamos o método das duas fases, inserindo 
variáveis artificiais e resolvendo um a função objetivo artificial no tableau simplex.
• Todo modelo de PL chamado de primal tem, associado a ele, um modelo dual:
PPL Primal PPL Dual
MaxZ = c1x1 +c2x2 + c3x3 +... + cnxn
Sujeito à
a11x1 +a12x2 + a13x3 +... + a1nxn ≤ b1
a21x1 +a22x2 + a23x3 +... + a2nxn ≤ b2. . . . . .. . . . . .. . . . . .
am1x1 +am2x2 + am3x3 +... + amnxn ≤ bm
xj ≥ 0,j = 1,...,n
MinZ = b1y1 +b2y2 + b3y3 +... + bmym
Sujeito à
a11y1 +a12y2 + a13y3 +... + a1mym ≤ c1
a21y1 +a22y2 + a23y3 +... + a2mym ≤ c2. . . . . .. . . . . .. . . . . .
an1y1 +an2y2 + an3y3 +... + amnym ≤ cn
yj ≥ 0,i = 1,...,m
Se o primal tem solução ótima, então o dual dele também tem, e o valor da 
função objetivo de ambos é o mesmo.
80
AUTOATIVIDADE
Para exercitar seus conhecimentos adquiridos, resolva as questões que 
seguem:
1 Escreva o modelo dado no exemplo 1, da Unidade 1, sobre a indústria 
moveleira, na forma padrão.
2 Escreva o modelo dado no exemplo 3, da Unidade 1, sobre a dieta alimentar, 
na forma padrão.
3 Resolva o modelo da indústria moveleira através do método simplex.
4 Resolva o modelo da dieta alimentar através do método das duas fases.
5 Escreva o modelo dual do modelo da dieta alimentar.
6 (BOLDRINI, 1980, p. 401, adaptado). Um aluno do curso de Engenharia 
quer resolver um grave problema usando o que aprendeuem Programação 
Linear. Atualmente, ele possui duas namoradas: Maria e Luíza. Ele sabe, 
por experiência, que:
Maria gosta de frequentar lugares mais caros, de modo que uma saída 
de três horas custará 24 reais. Já Luíza prefere um divertimento mais popular, 
de modo que uma saída de quatro horas custará 16 reais. Seu orçamento 
permite dispor de 96 reais mensais para a diversão.
Cada saída com Maria consome 500 calorias, mas com Luíza, mais 
alegre e extrovertida, gasta o dobro. Seus afazeres escolares lhe dão liberdade 
de, no máximo, 18 horas e 4000 calorias de sua energia para atividades sociais. 
Ele gosta das duas com a mesma intensidade.
Tomando por base as conclusões acima, ele quer planejar sua vida 
social de modo a obter o número máximo de saídas. Formule o modelo e 
resolva-o pelo método simplex. Após conseguir o resultado, comunique-o à 
classe para que este aluno (que prefere que seu nome não seja revelado, por 
motivos óbvios) possa conferir com a solução ótima obtida por ele.
81
TÓPICO 2
UTILIZAÇÃO DO COMPUTADOR
UNIDADE 2
1 INTRODUÇÃO
Muito bem, você deve pensar em largar o lápis e o papel e, finalmente, 
ver as coisas acontecendo mais rapidamente no computador. Não queremos 
desanimá-lo, mas para melhor entender como resolver nossos modelos de PL 
no computador, precisamos acompanhá-lo passo a passo, muitas vezes fazendo 
cálculos mais simples em um ambiente fora da tela, ou seja, o bom e velho papel. 
Mas fique tranquilo, as grandes equipes de PO trabalham muito mais com papel 
e lápis do que com computadores. Lembre-se que ele é apenas uma ferramenta 
de trabalho para nós e que, mais importante que resolver um modelo, é resolver 
um bom modelo, e por isso, antes de encontrar soluções computadorizadas, 
é necessário que tenhamos na mão um modelo de PL para introduzir no 
computador, e a máquina não faz modelos. 
Quando houver a impossibilidade de resolução pelo método gráfico, ou 
os métodos por nós vistos forem muitos trabalhosos, ou ainda, para a maioria 
dos problemas de PL, a busca pela solução ótima é feita através de ferramentas 
computacionais adequadas e disponíveis. 
Existem diversos softwares matemáticos, freewares (grátis) ou não, que 
processam dados na resolução de modelos de PL. Como exemplos, podemos 
citar o Maple, produzido pela empresa Waterloo Maple Inc., que é um poderoso 
programa que trabalha nas mais variadas áreas da matemática, engenharia e 
educação, inclusive na Pesquisa Operacional. Esse software é vendido em lojas 
especializadas e é mais indicado para usuários avançados nos estudos dessas 
áreas. Como alternativa, e por ser distribuído gratuitamente na internet, temos o 
WinMat, um programa educacional livre, que pode ser de grande utilidade nas 
operações com matrizes envolvidas na Programação Linear. Um dos softwares 
mais utilizados nesses problemas é o LINDO (Linear and Interactive and Discrete 
Optmizer), comercializado pela Lindo System Inc., e que pode operar modelos com 
até 50.000 restrições e 200.000 variáveis, e acredite, alguns modelos chegam a 
superar esse números.
Em nossos estudos, utilizaremos a ferramenta Solver, que é um suplemento 
do software Microsoft Excel, por se tratar o Microsoft Office de um pacote de 
programas, na maioria das vezes, disponibilizado junto aos computadores 
pessoais e que você terá fácil acesso. Usaremos a versão Microsoft Excel 2007 para 
nossas explicações.
A ferramenta Solver utiliza o Método Simplex e o Método de Branch and 
Bound, que serão vistos adiante, para resolver problemas de PL com restrições 
UNIDADE 2 | SOLUÇÃO ÓTIMA
82
reais ou inteiras, e ainda problemas de programação não linear, que não serão 
abordados nesse caderno, pela sua extensão e complexidade. Mas nada impede 
que você busque informações sobre esse tipo de problema em outras fontes. Vários 
textos, artigos, sites e livros tratam deles com melhor destaque.
Acreditamos que você tenha alguma experiência com a planilha Excel ou 
que pelo menos queira aprender como trabalhar com a ferramenta Solver. Mas, 
para facilitar a compreensão, novamente nos utilizaremos do problema de PL 
no planejamento agrícola (Exemplo 2 da Unidade 1) para ilustrar o uso dessa 
poderosa ferramenta computacional.
Você talvez precise habilitar a ferramenta Solver utilizando os seguintes 
comandos no Excel: No Menu superior esquerdo da tela você encontra a opção 
mais comandos..., e clicando nela uma janela de diálogo mostra, no menu à 
esquerda, a aba suplementos. Procure a ferramenta Solver na lista de suplementos e 
clique no botão ir... (embaixo da lista). Nesse momento aparece uma nova lista de 
suplementos, entre os quais, você, enfim, escolhe Solver. Pronto, essa ferramenta 
já está disponível para uso nas Barras de Ferramentas de Acesso Rápido da planilha. 
Como acessá-la veremos adiante.
Caso tenha dúvidas em relação ao uso da planilha Excel, ou queira 
aprofundar-se nesse programa e seus suplementos e ferramentas, também 
são encontradas diversas bibliografias sobre o assunto. Indicamos algumas na 
bibliografia deste caderno, ao final do mesmo.
2 RESOLVENDO MODELOS NO EXCEL
Para que você possa acompanhar melhor essa explicação, é interessante 
que você possa ler esse texto diante de um computador, já com uma planilha Excel 
aberta e em branco, para que você possa fazer, junto conosco, a programação do 
problema de PL e descobrir sua solução ótima.
Inicialmente, vamos colocar na planilha as informações indicando quais 
células serão destinadas à função objetivo, às restrições e seus coeficientes e 
sinais, e quais serão destinadas aos valores da solução ótima e do lucro máximo. 
Novamente, vamos ver o modelo do PL:
Max L = 300xT + 400xM Função Objetivo (maximizar o lucro)
Sujeito a
xT + xM ≤ 50 Restrição ao tamanho do terreno
3xT + 2xM ≤ 120 Restrição ao uso de mão de obra
xT ≤ 30 Restrição a demanda por trigo
xM ≤ 40 Restrição a demanda por milho
xT , xM ≥ 0 Restrição à não-negatividade
TÓPICO 2 | UTILIZAÇÃO DO COMPUTADOR
83
Veja o Quadro 5 a seguir, e digite as informações na planilha Excel como 
estão mostradas.
QUADRO 1 - DIGITAÇÃO DOS DADOS DO PL NA PLANILHA EXCEL
A B C D E F
1 Nome da variável Xt Xm
2 Valor da variável
3 Função Objetivo 300 400 max L =
4 Restrições Coeficientes Produtos Sinal b
5 Área disponível 1 1 <= 50
6 Homens-hora 3 2 <= 120
7 Demanda por trigo 1 0 <= 30
8 Demanda por milho 0 1 <= 40
FONTE: Os autores
Perceba que as células B2 e C2 destinam-se aos valores das variáveis xT e 
xM (no Excel é difícil trabalhar com letras sobrescritas e subscritas, por isso usamos 
Xt e Xm). E perceba também que a célula F3 está destinada a receber o valor da 
solução ótima do PL, ou seja, o valor máximo que se pode obter do lucro. 
Nesta célula, digite a função =SOMARPRODUTO(B2:C2;B3:C3). Esta 
função multiplica o valor da célula B2 pelo coeficiente da célula B3 e o valor da 
célula C2 pelo coeficiente da célula C3, e depois soma os resultados. Ora esse é o 
cálculo feito pela função objetivo. 
Por enquanto, o valor encontrado é 0 (zero) já que não temos os valores de 
xT e xM ainda calculados. O Solver nos fará esse trabalho.
Na célula D3 usamos a mesma fórmula, fazendo alguns ajustes, para calcular 
os valores das variáveis, aplicados à restrição quanto à área a ser plantada. Assim, 
você deve digitar nessa célula a fórmula =SOMARPRODUTO(B$2:C$2;B5:C5). 
Veja que foi usado o sinal $ na primeira parte da fórmula. Isso se deve ao fato de 
que iremos usá-la nas células logo abaixo. Para não ficar digitando-a várias vezes, 
basta arrastá-la para as próximas linhas. O sinal $ serve para “travar” a célula 
referenciada ao copiar a fórmula de uma célula para outra.
Nossa planilha está pronta para calcular a solução ótima. Vamos ao Solver!
Na Barras de Ferramentas de Acesso Rápido que indica Dados, você encontrará, 
à direita, um botão para acesso à ferramenta Solver. Clicando nele aparece a caixa 
de diálogo mostrada na Figura 11, intitulada Parâmetros do Solver.UNIDADE 2 | SOLUÇÃO ÓTIMA
84
FONTE: Os autores
FIGURA 11 - CAIXA DE DIÁLOGO PARÂMETROS DO SOLVER
Você deverá preencher os campos em branco, observando o seguinte:
• na caixa de texto Definir célula de destino: digite a célula que contém a fórmula 
da solução ótima, ou seja, F3;
• na caixa de texto Células das variáveis, digite B2:C2;
• no botão Opções, você deve selecionar as opções Presumir modelo linear e 
Presumir não negativos. Esse passo é muito importante, pois ele informa ao 
Solver que estamos trabalhando com um problema de Programação Linear e 
que existe a restrição de não negatividade das variáveis. Clique em OK para 
voltar e adicionar as outras restrições;
• clique em Adicionar e aparece outra caixa de diálogo chamada Adicionar restrição. 
Como todas as nossas restrições (nesse PL) têm o mesmo sinal, podemos incluí-
las numa única restrição, digitando no campo Referências de célula: D5:D8, 
escolhendo o sinal <= e digitando no campo Restrição: F5:F8. Clique OK;
Nesse momento, apresenta-se na tela, a caixa conforme mostra a Figura 12.
Agora é só clicar em Resolver e... (mantendo as soluções do Solver). Pronto! 
Temos a solução ótima 19000 na célula F3, que corresponde ao lucro obtido na 
produção de 10 ares de xT e 40 ares de xM , conforme mostrado nas células B2 e C2.
TÓPICO 2 | UTILIZAÇÃO DO COMPUTADOR
85
FONTE: Os autores
FIGURA 12 - CAIXA DE DIÁLOGO COM OS PARAMETROS PREENCHIDOS
Analisando os resultados obtidos na planilha, você pode observar que a 
célula D5 contém o número de homens-hora utilizados na solução ótima, que é de 
110. Há, portanto, uma folga na restrição de 10 homens-hora. Essas folgas serão 
analisadas com mais detalhes quando tratarmos da Análise de pós-otimalidade, 
mais adiante nesse caderno.
Agora, vamos verificar qual a solução ótima para o problema da Dieta 
Alimentar (exemplo 3 da Unidade 1) cujo objetivo é minimizar o custo, mantendo 
uma alimentação saudável em vitaminas. Aqui está o modelo do PL:
Mim C = 2x1 + 4x2 + 1,5x3 + 1x4 Função objetivo
Sujeito à
2x1 + 2x2 + 10x3 + 20x4 ≥ 11 Restrição ao consumo de vitamina A
5x1 + 2x2 + 1x3 + 3x4 ≥ 7 Restrição ao consumo de vitamina C
8x1 + 7x2 + 1x3 + 8x4 ≥ 25 Restrição ao consumo de vitamina D
x1 , x2 , x3 , x4 ≥ 0 Restrição à não negatividade
Do mesmo modo, vamos recorrer ao Solver para a resolução do PL. O 
procedimento é o mesmo, mas algumas alterações são necessárias. Primeiro, 
aumenta a quantidade de variáveis, mas basta inserir algumas células e mudar 
poucas fórmulas. Veja o Quadro 2.
FONTE: Os autores
UNIDADE 2 | SOLUÇÃO ÓTIMA
86
FONTE: Os autores
As alterações nas fórmulas são as seguintes:
• mudam os nomes das variáveis e das restrições;
• na célula G3 digitamos Min C, já que queremos minimizar os custos;
• na célula H3 deve-se digitar =SOMARPRODUTO(B$2:E$2;B3:E3);
• na célula F5 deve-se digitar =SOMARPRODUTO(B$2:E$2;B5:E5), e pode-se 
copiar (arrastando a fórmula para baixo) nas células F6 e F7;
• nas células G5, G6 e G7, usamos agora o sinal >=, já que expressamos que essas 
vitaminas são requisitos mínimos para a saúde.
Mas as grandes alterações são feitas na caixa de diálogo do Solver, onde 
devemos:
• escolher Mín em Parâmetros do Solver;
• fazer as alterações da célula de destino e das células variáveis;
• alterar as restrições mudando seu sinal para >=, a fim de respeitar os requisitos;
• não se esqueça de verificar se as Opções Presumir modelo linear e Presumir não 
negativos estão selecionadas.
Clicando em Resolver encontramos a solução ótima X*1 = 0, X*2 = 0, X*3 = 0, e 
X*1 = 3,125, que nos dá o custo mínimo C* = 3,125. Observe atentamente os valores 
encontrados pelo Solver no Quadro 3 e tente interpretar seus resultados.
A B C D E F G H
1 Nome da variável X1 X2 X3 X4
2 Valor da variável
3 Função Objetivo 2 4 1,5 1 Min C = 0
4 Restrições Coeficientes Produtos Sinal b
5 Vitamina A 2 2 10 20 0 >= 11
6 Vitamina C 5 2 1 3 0 >= 7
7 Vitamina D 8 7 1 8 0 >= 25
QUADRO 2 - DIGITAÇÃO DOS DADOS DO PL NA PLANILHA EXCEL
TÓPICO 2 | UTILIZAÇÃO DO COMPUTADOR
87
Realmente, resolver um problema de PL usando o computador é muito 
mais fácil. Mas há ainda, algumas informações a serem tratadas.
A B C D E F G H
1 Nome da variável X1 X2 X3 X4
2 Valor da variável 0 0 0 3,125
3 Função Objetivo 2 4 1,5 1 Min C = 3,125
4 Restrições Coeficientes Produtos Sinal b
5 Vitamina A 2 2 10 20 62,5 >= 11
6 Vitamina C 5 2 1 3 9,375 >= 7
7 Vitamina D 8 7 1 8 25 >= 25
QUADRO 3 - SOLUÇÃO ÓTIMA ENCONTRADA PELO SOLVER
FONTE: Os autores
3 ANÁLISE DE PÓS-OTIMALIDADE
Também conhecida como análise de sensibilidade, seu objetivo é verificar 
se alterações realizadas em alguns valores do modelo interferem na solução 
ótima do mesmo. Depois de resolver um modelo de PL, podemos determinar 
alguns limites para variações em alguns coeficientes do problema. Assim, em 
situações que exijam adaptações ao modelo original podem ser estudadas e, com 
isso, podemos definir até que ponto podemos ou não fazer essas adaptações sem 
ter que resolver novamente o modelo.
A análise de pós-otimalidade é feita apenas sobre o último quadro do 
tableau simplex, e pode ser feita sobre a função objetivo ou sobre os coeficientes da 
mão direita.
3.1 ANALISANDO A FUNÇÃO OBJETIVO
O que fazemos é uma pequena variação em um dos coeficientes c da F.O., 
verificando o que acontece com seu valor Z. Para isso, escreveremos um novo 
valor Ẑ = Z + Δcx.
Vamos usar nosso “famoso” exemplo para entender melhor como proceder. 
Para isso, vejamos o modelo e a última tabela do tableau simplex novamente:
Modelo na forma padrão:
Max L – 300x1 – 400x2 = 0
Sujeito a
UNIDADE 2 | SOLUÇÃO ÓTIMA
88
TABELA 18 - ÚLTIMA TABELA SIMPLEX
VARIÁVEIS 
BÁSICAS X1 X2 X3 X4 X5 X6 B CÁLCULOS
x1 1 0 1 0 0 -1 10
x4 0 0 -3 1 0 1 10
x5 0 1 0 0 0 1 20
x2 0 1 0 0 0 1 40
Max L 0 0 300 0 0 100 19000
FONTE: Os autores
Observando a última linha do quadro, que representa a função objetivo, 
temos, na forma padrão simplex, MaxL – 300x3 – 100x6 = 19000.
Agora, vamos criar uma pequena variação no coeficiente de x1 (que 
chamaremos c1), usando a linha da variável básica x1 em que x1 + x3 – x6 = 10, ou 
seja, x1 = – x3 + x6 + 10. Agora, substituindo essa expressão em Ẑ = Z + Δc1x1, teremos
Ẑ = Z + Δc1x1
Ẑ = –300x3 –100x6 + 19000 + Δc1 • (– x3 + x6 + 10)
Ẑ = –300x3 –100x6 + 19000 + Δc1 • (– x3) + Δc1 • x6 + Δc1 • 10)
Ẑ = –(300x3 + Δc1 )x3 –(100 – Δc1)x6 + 19000 + 10Δc1
 Vamos reescrever essa expressão como última linha do tableau simplex:
Max L 0 0 300 + Δc1 0 0 100 + Δc1 19000 + 10Δc1 
Para manter a solução ótima do problema (x1 =10, x4 =10, x5 =20, x2 =40), 
precisamos fazer 300 + Δc1 ≥ 0 e 100 + Δc1 ≥ 0 que podem ser representados por –300 
≤ Δc1 ≤ 100. Essa última expressão nos apresenta que a variação do coeficiente c1 
(Δc1) pode ser de até 100 a mais ou 300 a menos. Dizemos que c1 pode sofrer um 
permissível acréscimo de 100 ou um permissível decréscimo de 300 sem alterar o valor 
ótimo da função objetivo.
Fazendo a análise de pós-otimalidade para c2 teremos, pela linha de x2 
no tableau, x2 + x6 = 40 ⇒ x2 = 40 – x6 e substituindo em Ẑ = Z + Δc2x2:
TÓPICO 2 | UTILIZAÇÃO DO COMPUTADOR
89
Ẑ = Z + Δc2x2
Ẑ = –300x3 –100x6 + 19000 + Δc2 (40 – x6)
Ẑ = –300x3 –100x6 + 19000 + 40Δc2 – Δc2 x6
Ẑ = –300x3 – (100 + Δc2)x6 + 19000 + 10Δc2 
Que nos dá a nova linha:
Max L 0 0 300 0 0 100 + Δc2 19000 + 10Δc2 
E assim, para manter a solução, temos 100 + Δc2 ≥ 0, que significa –100 
≤ Δc2, ou seja, c2 pode sofrer um permissível decréscimo de 100 ou um permissível 
acréscimo ilimitado sem alterar o valor ótimo da função objetivo.
3.2 ANALISANDO OS COEFICIENTES DA MÃO 
DIREITA DAS RESTRIÇÕES
Para analisar esses coeficientes, vamos novamente utilizar os recursos da 
ferramenta Solver. Basta abrir nosso modelo de PL digitado na planilha Excel e 
selecionar a ferramenta Solver. Após inserir as informações necessárias na caixa 
de diálogo Parâmetros do Solver, sem esquecer de selecionar as opções de modelo 
linear e nãonegativo, ao clicar em Resolver, aparece uma nova caixa de dialogo 
Resultados do Solver, mostrada na Figura 13. Nessa caixa, devemos clicar em cima 
da opção Sensibilidade e depois OK.
FIGURA 13 - CAIXA DE DIÁLOGO RESULTADOS DO SOLVER, CLICAR EM SENSIBILIDADE 
GERA A NÁLISE DE PÓS-OTIMALIDADE
FONTE: Os autores
Automaticamente, o Excel cria uma planilha chamada Relatório de 
sensibilidade 1, que pode ser acessada clicando embaixo, à esquerda, no rodapé da 
planilha atual.
Esse relatório nos dá as informações contidas no Quadro 4, que devem ser 
interpretadas com muito rigor.
UNIDADE 2 | SOLUÇÃO ÓTIMA
90
QUADRO 4 - RELATÓRIO DE SENSIBILIDADE DO MODELO DE PL DE PLANEJAMENTO 
AGRÍCOLA, DADO PELO SOVER DO EXCEL.
CÉLULAS AJUSTÁVEIS
 Final Reduzido Objetivo Permissível Permissível
Célula Nome Valor Custo Coeficiente Acréscimo Decréscimo
$B$2 Valor da variável Xt 10 0 300 100 300
$C$2 Valor da variável Xm 40 0 400 1E+30 100
Restrições
 Final Sombra Restrição Permissível Permissível
Célula Nome Valor Preço Lateral R.H. Acréscimo Decréscimo
$D$5 Área disponível Produtos 50 300 50 3,333333333 10
$D$6 Homens-hora Produtos 110 0 120 1E+30 10
$D$7 Demanda por trigo Produtos 10 0 30 1E+30 20
$D$8 Demanda por milho Produtos 40 100 40 10 10
FONTE: Os autores
As células ajustáveis são referentes à função objetivo. Perceba que essa 
parte do relatório nos dá informações sobre as variáveis xT e xM, lembrando que os 
coeficientes da função objetivo são, respectivamente, 300 e 400, e que os valores 
da solução ótima para essas variáveis são xT = 10 e xM = 40. As últimas colunas 
desse relatório nos dizem que o coeficiente de xT pode sofrer um permissível 
acréscimo de 100 e um permissível decréscimo de 300, e que o coeficiente de xM 
pode sofrer um permissível decréscimo de 100 e um permissível acréscimo de 
1E+30. Esse valor é uma representação para o infinito (1E+30 = 1 • 1030, que é um 
grande número!).
A parte de baixo do relatório nos diz quais os acréscimos e decréscimos 
permissíveis para cada um dos coeficientes da mão direita nas restrições. Para 
entender o que isso quer dizer, vejamos a restrição quanto à demanda por 
milho, que é de trinta ares, no máximo. Se diminuíssemos essa demanda para 
25 ares (usando o permissível decréscimo de 20), ainda assim, nosso lucro seria 
de 19000, visto que as outras restrições encarregam-se de manter o valor das 
variáveis em 10 e 40.
91
RESUMO DO TÓPICO 2
Nesse Tópico vimos que: 
• Para resolver um modelo de PL através do computador, basta digitar 
corretamente as informações do modelo numa planilha Excel, e habilitando 
a ferramenta Solver. Ela nos dá a solução ótima desse modelo, assim como os 
possíveis acréscimos e decréscimos da análise de pós-otimalidade.
• A análise de pós-otimalidade da função objetivo pode ser feita também 
através do tableau simplex, examinando as equações da última linha da tabela e 
acrescentando pequenas variações nos coeficientes da função, usando Ẑ = Z + 
Δcx para a verificação.
92
AUTOATIVIDADE
Para exercitar seus conhecimentos adquiridos, resolva as questões a 
seguir:
1 Resolva todos os exercícios do Tópico 1 da Unidade 1 através do Solver.
2 Resolva os exercícios 3 e 6 do Tópico 1 da Unidade 2 através do Solver.
3 Resolva o exercício 1, sobre a fábrica de cristais, do Tópico 3 da Unidade 1, 
através do Solver, e faça a análise de pós-otimalidade gerando o relatório 
de sensibilidade.
93
UNIDADE 3
PROGRAMAÇÃO DE PROJETOS
OBJETIVOS DE APRENDIZAGEM
PLANO DE ESTUDOS
A partir desta unidade, você estará apto(a) a:
• representar um modelo por redes, grafos ou árvores;
• identificar e resolver uma aproximação para os problemas de caixeiros 
viajantes;
• resolver problemas de fluxo máximo e de caminho mais curto em uma 
rede;
• planejar atividades usando as técnicas de PERT e CPM;
• gerar simulações para modelos matemáticos via computador.
Esta unidade está dividida em três tópicos. No final de cada um deles, você 
encontrará atividades que reforçarão o seu aprendizado.
TÓPICO 1 – ANÁLISE DE REDES
TÓPICO 2 – TÉCNICAS PERT/CPM
TÓPICO 3 – SIMULAÇÃO
94
95
TÓPICO 1
ANÁLISE DE REDES
UNIDADE 3
1 INTRODUÇÃO
Diversos problemas de programação linear, como os problemas de transporte 
(controle de tráfego de veículos em rodovias e trevos, vazão em tubulações e 
estações de tratamento, linhas telefônicas, controle de voo em aeroportos etc.), de 
planejamento e de controle de atividades (construção civil, mecânica etc.) podem 
ser modelados como problemas de fluxo de redes. A análise dessas redes nos 
permite identificar algoritmos específicos para determinados tipos de problemas 
que podem ser mais convenientes para a sua solução do que algoritmos mais 
genéricos. A teoria dos grafos nos ajuda a compreender como resolver esses tipos 
de problemas, e o estudo de técnicas como PERT ou CPM nos mostra que a solução 
ótima desses problemas pode ser determinada facilmente, com bom planejamento 
e execução correta das atividades.
2 TEORIA DOS GRAFOS
Definição 1: Um grafo é um conjunto de nós (vértices ou pontos) conectados 
ou não por arcos (arestas ou ramos).
Um grafo pode representar, por exemplo, as rodovias que interligam 
várias cidades de uma região. No exemplo indicado pela Figura 14, consideramos 
os nós como as cidades e os arcos como as rodovias (sem as curvas, para facilitar 
a visualização).
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
96
FONTE: Os autores
No grafo acima, temos os nós A, B, C, D, E e os arcos AB, AD, BC, BD, BE, 
DE, CE, CF, DF e EF.
Definição 2: Um grafo direto é aquele em que o fluxo ao longo de um arco 
pode ser feito apenas em um sentido.
Dizemos que o arco AB tem origem no vértice A e término no vértice B, 
mas podemos ter um arco BA com origem em B e término em A, e nesse caso, o 
grafo não é direto, pois há um arco com duplo sentido (como uma rua de mão 
dupla. Nos grafos diretos, só há ruas de mão única).
Definição 3: Um caminho é um conjunto de arcos que conectam dois nós 
através de nós intermediários.
Um exemplo de caminho, segundo o exemplo, é ABCE, que conecta os 
nós A e E, passando por B e por C.
Definição 4: Um grafo conectado é aquele em que sempre existe pelo 
menos um arco ligando qualquer par de nós do grafo.
Nosso exemplo é um grafo conectado. Não há nós isolados (como se uma 
cidade não pudesse ser alcançada por uma rodovia).
Definição 5: Um laço é um caminho que conecta um nó a ele mesmo. No 
exemplo, o caminho ABDA é um laço.
Definição 6: Uma árvore é um grafo sem laços. Uma árvore tem n arcos e 
n+1 nós.
FIGURA 14 - EXEMPLO DE UM GRAFO OU REDE
TÓPICO 1 | ANÁLISE DE REDES
97
2.1 O PROBLEMA DO CAIXEIRO VIAJANTE
Um dos problemas mais famosos da teoria dos grafos é o problema do 
caixeiro viajante. Claro que não usamos mais essa nomenclatura, mas o princípio 
é o mesmo: um representante comercial precisa visitar seus clientes em suas 
cidades, sem visitar duas vezes a mesma cidade e sem deixar de visitar nenhuma 
cidade. Deve-se também considerar que esse representante deve tentar fazer 
todas as visitas andando o mínimo possível.
Como exemplo, vamos imaginar um vendedor que precise visitar quatro 
cidades A, B, C e D, cujo mapa está representado pelo grafo da Figura 15 e as 
distâncias (em km) entre as cidades são dadas na Tabela 19.
FONTE: Os autores
TABELA 19 - DISTÂNCIAS ENTRE AS 4 CIDADES
Para começar, podemos pensar em todos os possíveis caminhos que 
o vendedor pode tomar para atingir todas as cidades através de uma árvore, 
ilustrada na Figura 16 (sem considerar o retorno à cidade A.
FIGURA 15 - EXEMPLO DE PROBLEMA DE CAIXEIRO VIAJANTE COM 4 CIDADES
 CIDADES A B C
A - 
B 35 - 
C 28 32 -
D 21 19 26
FONTE: Os autores
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
98
FONTE: Os autores
Cada caminho pode ser considerado. Então, podemos ter seis caminhos: 
ABCDA, ABDCA, ACBDA, ACDBA, ADDCA e ADCBA. Mas entre eles temos 
caminhos que possuem a mesma extensão, como por exemplo, ABCDA e ADCBA, 
ou seja, são simétricos, e porisso, podemos desconsiderar metade dos caminhos, 
que nos deixam apenas:
• ABCDA, que tem extensão de 35 + 32 + 26 + 21 = 114 km
• ABDCA, que tem extensão de 35 + 19 + 26 + 28 = 108 km
• ACBDA, que tem extensão de 28 + 32 + 19 + 21 = 100 km
Assim, o vendedor deve optar pelo caminho ACBDA.
Mas essa escolha fica muito difícil quando aumentamos o número de cidades 
a serem visitadas. Como o número de caminhos é calculado pela permutação de n 
cidades, excluindo-se a repetição de caminhos, ou seja, . Quando o número 
de cidades é muito grande, temos um problema maior ainda, pois o número de 
permutações é consideravelmente “muito maior”.
FIGURA 16 - ÁRVORE REPRESENTANDO OS POSSÍVEIS CAMINHOS PARA O PROBLEMA 
DO CAIXEIRO VIAJANTE COM 4 CIDADES
TÓPICO 1 | ANÁLISE DE REDES
99
Eficiência significa resolver problemas, encontrando uma solução ótima, 
sem se preocupar com o tempo que isso leva. Já eficácia significa resolver 
um problema, isto é, encontrar uma solução, não necessariamente a 
melhor, dentro de um tempo razoável. O tempo pode ser uma restrição 
na busca de uma solução. Nos processos de busca de solução para 
problemas complexos, com muitas alternativas, existe sempre o dilema 
eficiência x eficácia. (LOESCH; HEIN, 1999, p. 196). 
Mesmo um bom computador levaria anos para conseguir realizar todos 
os cálculos de distâncias envolvidos num problema com vinte cidades. E temos 
que lembrar que, atualmente, um vendedor que tenha apenas vinte clientes 
pode passar dificuldades para levar uma boa vida, mas essas questões não nos 
interessam.
Para o caso do caixeiro viajante, costuma-se empregar uma técnica de 
solução para a busca da solução ótima conhecida como técnica do vizinho mais 
próximo.
Seleciona-se, arbitrariamente, uma cidade inicial, verifica-se qual a 
distância entre as cidades que ainda falta visitar, e escolhe-se a que estiver 
mais perto. Chegando lá, repete-se o procedimento, excluindo-se as cidades já 
visitadas, até que não sobre mais nenhuma.
No exemplo do nosso vendedor, podemos verificar que, se ele partir da 
cidade A, a próxima cidade a ser visitada deve ser D, por estar mais perto (21 km). 
De D ele deve ir até B (pois entre B e C, B é mais próximo), e de lá para a cidade 
C. Depois, é só retornar para A. Daí temos o caminho ADBCA, que é o mesmo 
caminho que tínhamos determinado, só que agora fazendo o percurso de volta.
Outra maneira é reduzir a complexidade do problema trabalhando com 
sublocalidades (ou regiões, por exemplo). Assim, o vendedor pode dividir seu 
mapa de clientes em regiões e analisar essas regiões como cidades.
Ou ainda, combinar as duas maneiras, dividindo as regiões e procurando 
dentro de cada região as cidades mais próximas umas às outras. Terminando de 
visitar uma região, ele procura a região mais próxima e recomeça o trabalho.
Lembre-se das aulas de análise combinatória, cujo número de permutações de 
n com repetição a é dado por , de modo que ! é chamado fatorial e representa, 
por exemplo, 3! = 3 . 2 . 1 = 12. Assim, se tomarmos, por exemplo, 20 cidades, teremos 
 
caminhos. Não dá pra testar todos eles!
UNI
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
100
2.2 PROBLEMAS DE FLUXO MÁXIMO
Outro tipo de problema comum na análise de redes é o problema de 
fluxo máximo, que pode ser, por exemplo, o problema de uma distribuidora de 
água tratada que queira determinar qual o maior fluxo de água que pode ser 
distribuído por sua rede de tubulação.
FONTE: Os autores
Na Figura 17, estão representadas as capacidades da tubulação, em 
milhões de litros por dia, e deseja-se saber qual o fluxo máximo de água que essa 
rede comporta, considerando que o nó A representa a Estação de Distribuição 
(origem) de água e o D representa uma localidade (destino) que deve receber a 
água tratada.
Neste problema, podemos considerar que a quantidade de água que 
chega ao ponto D é igual à quantidade de água que sai do ponto A. Isso pode 
ser representado por um arco ligando o ponto D ao ponto A. Desta forma, o 
problema pode ser representado como um problema de programação linear em 
que se deseja maximizar o fluxo do nó D ao nó A (que é igual ao fluxo que sai 
do nó A, ou ao fluxo que chega ao nó D). As restrições deste problema, além da 
capacidade de cada arco da rede, é o fato de que a quantidade de água que chega 
a qualquer nó é igual à quantidade de água que sai deste mesmo nó. As variáveis 
de decisão para este problema são:
• x0: fluxo do nó D ao nó A;
• x1: fluxo do nó A ao nó B;
• x2: fluxo do nó A ao nó B;
• x3: fluxo do nó B ao nó D;
FIGURA 17 - REDE DE TUBULAÇÃO DE ÁGUA E CAPACIDADE DOS TUBOS
TÓPICO 1 | ANÁLISE DE REDES
101
• x4: fluxo do nó C ao nó A;
• x5: fluxo do nó C ao nó D.
A função objetivo é maximizar o fluxo que chega ao nó D, representado 
neste problema por x0.
Para cada nó, o fluxo de água que chega é igual ao fluxo de água que sai. 
Representando com um sinal negativo o fluxo de água que chega e positivo o 
fluxo de água que sai, temos as seguintes restrições:
• Nó D: x0 - x3 - x5 = 0
• Nó A: - x0 + x1 + x2 = 0
• Nó B: - x1 + x3 - x4 = 0
• Nó C: - x2 + x4 + x5 = 0
As restrições de capacidade são x1 ≤ 20, x2 ≤ 28, x3 ≤ 25, x4 ≤ 14 e x5 ≤ 20. E 
assim temos o problema dado por:
Max F = x0
Sujeito a
 x0 –x3 +x5 = 0
 – x0 +x1 +x2 = 0
 –x1 +x3 –x4 = 0
 –x2 +x4 +x5 = 0
 x1 ≤ 20
 x2 ≤ 28
 x3 ≤ 25
 x4 ≤ 14
 x5 ≤ 21
Isto pode ser resolvido pela ferramenta Solver.
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
102
AUTOATIVIDADE
Esta aí um bom problema de PL para você resolver.
Esse é um tipo de problema que a teoria dos grafos aborda com mais 
atenção. Algumas técnicas são reconhecidamente eficientes na busca da solução 
ótima desse tipo de problema. Vamos estudar uma dessas técnicas, que é mais, 
digamos assim, famosa, o algoritmo de Djikstra (Edsger Wybe Dijkstra, 1930-
2002, cientista da computação, estudou os métodos de busca de solução ótima 
para problemas de caminho mais curto).
Vamos a um exemplo para poder compreender melhor o funcionamento 
do algoritmo. Dada a rede representada pela Figura 18, deseja-se determinar o 
caminho mais curto entre os nós A e G.
FONTE: Os autores
Vamos utilizar duas tabelas: uma tabela de distâncias mínimas e uma 
tabela auxiliar. Na tabela de distâncias mínimas, teremos três colunas (nó, nó de 
onde vem o caminho mínimo – ou nó anterior – e distância do caminho mínimo) e 
na tabela auxiliar teremos três colunas (nó, nó de origem do caminho considerado 
e a distância desse caminho).
FIGURA 18 - REDE DE NÓS E ARCOS
2.3 PROBLEMAS DE CAMINHO MAIS CURTO
TÓPICO 1 | ANÁLISE DE REDES
103
DISTÂNCIAS MÍNIMAS AUXILIAR
Nó Nó Ant. Distância Nó Nó Ant. Distância
Começamos analisando o nó de origem, ou seja, A, e sua distância em 
relação ao nó de origem, ou seja, 0. Este nó será colocado na tabela de distâncias 
mínimas (na coluna Nó) e sua distância até a origem também. Na tabela auxiliar, 
colocamos todos os nós que podemos alcançar a partir de A, assim como o nó de 
onde eles são alcançados (o próprio A) em suas distâncias até a origem. Nesse 
caso, a tabela fica assim:
DISTÂNCIAS MÍNIMAS AUXILIAR
Nó Nó Ant. Distância Nó Nó Ant. Distância
A - 0 B A 16
C A 10
D A 24
Agora, analisamos qual é o nó mais próximo da origem, ou seja, aquele 
que tem a menor distância em relação à origem. Nesse caso, C é o nó colocado na 
tabela de distâncias mínimas. E todos os nós que podem ser alcançados a partir 
de C são colocados na tabela auxiliar com suas distâncias em relação à origem, 
passando pelos nós anteriores. Temos então:
DISTÂNCIAS MÍNIMAS AUXILIAR
Nó Nó Ant. Distância Nó Nó Ant. Distância
A - 0 B A 16
C A 10 C A 10 (x)
D A 24
D C 18
F C 14
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
104
Simbolizamos com (x) os nós da tabela auxiliar que não devem mais entrar 
na tabela de distâncias mínimas. Perceba que as distâncias dos nós D e F na tabela 
auxiliar são equivalentes às somas das distâncias AC e CD (10 + 8 = 18) e AC e CF 
(10 + 4= 14). A menor distância apontada pela tabela auxiliar indica que o nó F 
deve entrar na tabela. O único nó alcançado a partir de F é G, e, portanto:
DISTÂNCIAS MÍNIMAS AUXILIAR
Nó Nó Ant. Distância Nó Nó Ant. Distância
A - 0 B A 16 = 16 + 0
C A 10 C A 10 = 10 + 0 (x)
F C 14 D A 24 = 24 + 0
D C 18 = 10 + 8
F C 14 = 10 + 4(x)
G F 38 = 14 + 24
O próximo nó que entra na tabela é B, vindo de A, com distancia 16. Os 
nós alcançados a partir de B são D e E.
DISTÂNCIAS MÍNIMAS AUXILIAR
Nó Nó Ant. Distância Nó Nó Ant. Distância
A - 0 B A 16 (x)
C A 10 C A 10 (x)
F C 14 D A 24
B A 16 D C 18
F C 14 (x)
G F 38
D B 20 = 16 + 4
E B 24 = 16 + 8
O próximo a entrar é D, vindo de C, com distância 18. De D alcançamos E e F:
TÓPICO 1 | ANÁLISE DE REDES
105
 Distâncias Mínimas Auxiliar
Nó Nó Ant. Distância Nó Nó Ant. Distância
A - 0 B A 16 (x)
C A 10 C A 10 (x)
F C 14 D A 24
B A 16 D C 18 (x)
D C 18 F C 14 (x)
G F 38
D B 20
E B 24
E D 24 = 18 + 6
F D 20 = 18 + 2
O próximo a entrar é D, vindo de B, com distância 20. Mas D já foi incluído 
na tabela de distâncias mínimas, então passamos ao próximo nó, que é F, vindo de D 
(distância 20) que também já está incluído. Passamos ao nó E, vindo de B, distante 24, 
e a partir dele alcançamos F e G:
DISTÂNCIAS MÍNIMAS AUXILIAR
Nó Nó Ant. Distância Nó Nó Ant. Distância
A - 0 B A 16 (x)
C A 10 C A 10 (x)
F C 14 D A 24 (x)
B A 16 D C 18 (x)
D C 18 F C 14 (x)
E B 24 G F 38
D B 20 (x)
E B 24 (x)
E D 24 (x)
F D 20 (x)
G E 36
F E 36
O nó F já está na tabela e por isso quem entra agora é G, vindo de E, com 
36 de distância, e assim:
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
106
DISTÂNCIAS MÍNIMAS AUXILIAR
Nó Nó Ant. Distância Nó Nó Ant. Distância
A - 0 B A 16 (x)
C A 10 C A 10 (x)
F C 14 D A 24 (x)
B A 16 D C 18 (x)
D C 18 F C 14 (x)
E B 24 G F 38 (x)
G E 36 D B 20 (x)
E B 24 (x)
E D 24 (x)
F D 20 (x)
F E 36 (x)
G E 36 (x)
Todos os nós já estão na tabela de distâncias mínimas e, com isso, o 
problema está resolvido. A tabela mostra a distância mínima até o nó de origem 
para cada nó do grafo. O caminho mínimo vem do nó indicado na coluna de nó 
anterior. Desta forma, pode-se determinar o caminho mínimo repetindo-se este 
passo sucessivamente até que o nó de origem seja encontrado. Para encontrarmos 
o caminho mínimo do nó G, por exemplo, pegamos o nó anterior a ele (E). O nó 
anterior ao nó E é o nó B, cujo nó anterior é o nó de origem A. E, dessa forma, o 
caminho mais curto é dado por ABEG.
Em resumo, o algoritmo pode então ser definido da seguinte maneira:
1º Inserir o nó de origem na tabela de distâncias mínimas. Sua distância 
até o nó de origem é 0.
2º Coloca-se na tabela auxiliar todos os nós atingidos por este nó. Para os 
nós incluídos na tabela auxiliar, o nó de onde vem o caminho é o nó recém-inserido 
na tabela de distâncias mínimas. A distância do nó de origem é a distância do arco 
percorrido, somada com a distância do nó recém inserido na tabela de distâncias 
mínimas até a origem.
3º O próximo nó a entrar na tabela de distâncias mínimas será o nó entre 
os nós não marcados com um (x), de menor distância até a origem. Marca-se este 
nó com um (x). Caso este nó já esteja inserido na tabela de distâncias mínimas, 
devemos retornar ao 3º passo.
TÓPICO 1 | ANÁLISE DE REDES
107
4º Após inserir o nó na tabela de distâncias mínimas, volta-se ao 2º passo 
até que todos os nós do grafo tenham sido inseridos na tabela de distâncias 
mínimas.
5º A tabela de distâncias mínimas indica a distância do caminho mínimo 
de cada nó até o nó de origem, e o nó de onde vem o caminho mínimo.
108
RESUMO DO TÓPICO 1
Neste tópico, estudamos os seguintes conteúdos:
• Definimos o que é grafo, nó e arco, e fizemos a representação de alguns tipos 
de problemas, como o do caixeiro viajante, do fluxo máximo e do caminho 
mais curto, usando a teoria dos grafos.
• Vimos alguns métodos de busca da solução ótima para redes ou grafos:
 • como a técnica do vizinho mais próximo para o caixeiro viajante;
 
 • as técnicas de programação linear para problemas de fluxo máximo;
 
 • e o algoritmo de Djikstra para problemas de caminho mais curto.
109
AUTOATIVIDADE
Para exercitar seus conhecimentos adquiridos, resolva as questões que 
seguem:
1 Dadas as distâncias (em km) indicadas no quadro a seguir, determine o 
caminho ótimo para um representante comercial que queira visitar essas 
cidades, partindo da cidade A, e voltando para ela. 
A B C D 
60 B
91 78 C
49 50 43 D
41 93 35 81 E
2 A rede a seguir representa a tubulação de gás de uma empresa, de modo 
que cada nó representa uma estação de trabalho, e cada arco os tubos com 
suas capacidades (em litros de gás). Determine o fluxo máximo de gás que 
percorre essa rede do ponto A ao ponto H.
3 Usando o grafo da questão anterior, determine o caminho mais curto entre 
os pontos A e H, utilizando os valores dos arcos como distâncias.
110
111
TÓPICO 2
TÉCNICAS PERT/CPM
UNIDADE 3
1 INTRODUÇÃO
Segundo Loesch e Hein (1999, p. 210), em 1957, surgiu o Critical Path 
Method (CPM – Método do Caminho Crítico), com o objetivo de planejar e 
controlar a construção de uma das fábricas da Du Pont. Já em 1958, surgiu o 
Program Evaluation and Review Technique (PERT – Técnica de Avaliação e Revisão 
de Projetos), dentro de uma grande empresa de consultoria associada à equipe de 
projetos especiais da marinha dos EUA, com o objetivo de auxiliar na construção 
de submarinos atômicos equipados com projetos balísticos Polaris, um projeto 
que envolvia 250 empresas, 9000 contratos e numerosas agências americanas. O 
emprego do PERT permitiu reduzir em cerca de dois anos o prazo de conclusão 
do projeto Polaris, o que lhe valeu rápida e notória popularidade. 
2 APLICAÇÃO DE PERT/CPM
Um exemplo muito utilizado na ilustração dos métodos PERT e CPM é 
o da indústria de construção civil. Vamos usar uma adaptação de um problema 
proposto por Hillier e Lieberman (2006, p. 400), segundo o qual uma empreiteira 
ganhou uma licitação para construir uma planta industrial no valor de $5,4 milhões. 
O contrato inclui duas cláusulas que, por sua vez, incluem uma penalidade de $ 
300 mil se a empreiteira não concluir a obra em 47 semanas. Ou um bônus de $ 
150 mil se concluir em 40 semanas.
De acordo com a experiência da empresa, foi organizada uma lista com as 
atividades e os tempos de duração das mesmas, assim como a dependência das 
atividades em relação umas às outras. Essa lista está representada pelo Quadro 
5 a seguir.
ATIVIDADE DESCRIÇÃO DA ATIVIDADE
ATIVIDADES 
ANTECESSORAS DURAÇÃO PREVISTA
A Escavação - 2 Semanas
B Fundações A 4 Semanas
QUADRO 5 - LISTA DE ATIVIDADES PROGRAMADAS PARA A CONSTRUÇÃO
112
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
C Levantar paredes e alvenaria B 10 Semanas
D instalar o teto C 6 Semanas
E Instalar a tubulação externa C 4 Semanas
F Instalar a tubulação interna E 5 Semanas
G Revestimento externo D 7 Semanas
H Pintura externa E, G 9 Semanas
I Instalação elétrica C 7 Semanas
J Revestimento interno F, I 8 Semanas
K Colocação de pisos J 4 Semanas
L Pintura interna J 5 Semanas
M Acessórios externos H 2 Semanas
N Acessórios internos K, L 6 Semanas
FONTE: Hillier; Lieberman (1985, p. 400)
Conforme o quadro, se as atividades forem realizadas uma de cada vez 
a construção ficará pronta em 79 semanas. Mas há atividades que podem ser 
realizadas simultaneamente, reduzindo o tempo de construção. Nosso objetivo é 
minimizar esse tempo, respeitando as condições impostas pela tabela.
2.1 REDE DE ATIVIDADES
Para facilitar a visualização das atividades, podemos organizá-las em 
uma rede (ou grafo) em que cada nó representa uma atividade e cada arco 
representa as relações de dependência entre elas. A Figura 19 nos dá a rede de 
relações nesse problema.
TÓPICO 2 | TÉCNICAS PERT/CPM
113
FONTE: Os autores
De acordo com a análise da rede, podemos estabelecer dois questionamentos 
muito importantes para a realização da obra: Qual o tempo total necessário para a 
construção sem atrasos? E quais asatividades que não podem sofrer atrasos que 
comprometam a conclusão da obra?
2.2 CAMINHO CRÍTICO
Analisando a rede de atividades, podemos identificar seis caminhos 
possíveis para conectar o início da obra com seu fim. O comprimento desses 
caminhos é dado pela soma das durações das atividades que compõem o caminho. 
Assim temos o Quadro 6 com as durações:
FIGURA 19 - REDE DE RELAÇÕES DE DEPENDÊNCIA ENTRE AS ATIVIDADES
QUADRO 6 - DURAÇÕES PREVISTAS PARA OS POSSÍVEIS CAMINHOS DA REDE DE ATIVIDADES
CAMINHO 
(ATIVIDADES)
COMPRIMENTO ( EM 
SEMANAS)
Inicio-ABCDGHM-Fim 2 + 4 + 10 + 6 + 7 + 9 + 2 = 40
Inicio-ABCEHM-Fim 2 + 4 + 10 + 4 + 9 + 2 = 31
Inicio-ABCEFJKN-Fim 2 + 4 + 10 + 4 + 5 + 8 + 4 +6 = 43
Inicio-ABCEFJLN-Fim 2 + 4 + 10 + 4 + 5 + 8 + 5 + 6 = 44
Inicio-ABCIJKN-Fim 2 + 4 + 10 + 7 + 8 + 4 + 6 = 41
Inicio-ABCIJLN-Fim 2 + 4 + 10 + 7 + 8 + 5 + 6 = 42
FONTE: Hillier; Lieberman (1985, p. 403)
114
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
O caminho com o maior comprimento é chamado de Caminho Crítico, já 
que todos os demais caminhos devem chegar ao nó fim antes do Caminho Crítico. 
Isso responde a primeira questão, ou seja, o tempo total para completar o projeto 
sem atraso é de 44 semanas.
As atividades sobre esse caminho são as Atividades Críticas (gargalos) e 
o atraso em uma dessas atividades ocasionará o atraso de toda a obra. Assim, as 
atividades não integrantes desse caminho podem sofrer algum tipo de atraso sem 
comprometer todo o projeto. A seguir temos, em destaque, o Caminho Crítico.
FONTE: Os autores
2.3 PROGRAMAÇÃO DAS ATIVIDADES - PERT
Nesse momento, devemos determinar quando uma atividade deve 
começar e terminar. Em princípio, uma atividade deveria começar imediatamente 
após o término de sua atividade antecedente, mas algumas atividades dependem 
de mais de uma atividade e, assim, pode haver necessidade de aguardar que 
todas as atividades antecedentes terminem antes de iniciar uma nova atividade. 
As atividades não críticas podem ter um tempo de folga, dependendo de suas 
atividades antecedentes, já que ela não se encontra no caminho critico. A técnica 
PERT/CPM utiliza quatro variáveis para formalizar essas informações:
IMC = Data de início mais cedo para uma atividade.
A data de início mais cedo IMCi de uma atividade i é igual à maior TMCj 
de sua atividade antecedente j, ou seja, IMCi = {TMCji} j ∈ Pi, onde Pi é o 
conjunto de atividades antecedentes da atividade i.
FIGURA 20 - REDE DE ATIVIDADE INDICANDO O CAMINHO CRÍTICO
 max 
j
TÓPICO 2 | TÉCNICAS PERT/CPM
115
Data de Término mais cedo:
Como o tempo de duração da atividade J é de oito semanas, temos:
TMCJ = IMCJ + DJ = 25 + 8 = 33
Data de término mais tarde:
TMCJ = min {IMTK,IMTL} = min{34,33} = 33
TMC = Data de término mais cedo para uma atividade.
Para uma atividade, TMCi = IMCi + Di, onde Di é a duração da atividade i.
IMT = Data de início mais tarde de uma atividade. 
As atividades não críticas podem sofrer atrasos, ou seja, podem iniciar 
mais tarde, e assim, é dada por TMCi = TMTi - Di, onde TMT é definido a seguir.
TMT = Data de término mais tarde de uma atividade. 
A data de término mais tarde TMTi de uma atividade i é igual ao menor 
IMTk de suas atividades sucessoras k, ou seja,TMTi = 
 min {IMTk},k ∈ Si, onde Si é 
o conjunto de atividades sucessoras da atividade i.
Para melhor compreender, vamos calcular as datas de início e término, 
mais cedo e mais tarde, da atividade J que representa a colocação das divisórias:
Data de início mais cedo:
IMCJ = max {TMCF,TMCI} = max{25,23} = 25
k
Os valores 25 e 23 representam a soma dos tempos de duração dos dois 
caminhos que levam do início do projeto até a atividade J, que podem ser analisados 
através da rede de atividades.
UNI
116
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
Os valores 34 e 33 são calculados de acordo com o tempo de duração do 
caminho crítico, ou seja, 44 semanas. Daí são descontadas as durações de Término Mais 
Tarde das atividades K e L, usando-se as durações dos caminhos dessas atividades até o nó 
fim. Para entender melhor, veja a rede de atividades: Se pensarmos em 44 semanas para 
concluir a obra, a atividade K antecede a atividade N em quatro semanas e esta antecede o 
Fim em seis semanas, assim 44 – 4 – 6 = 34 semanas (TMT
K
 = 34) e a atividade L antecede 
a atividade N em cinco semanas, assim 44 – 5 – 6 = 33 semanas (TMT
L
 = 33).
UNI
Data de início mais tarde:
TMCJ = TMTJ - DJ = 33 – 8 = 25
É importante perceber que as datas de início mais cedo e mais tarde são 
iguais, e que isso ocorre também com as datas de término mais cedo e mais tarde, ou 
seja, a atividade J não pode sofrer adiantamento e nem atrasos, o que já sabíamos, 
visto que a atividade J é uma das atividades críticas (integra o caminho crítico).
Observando ainda que TMT – TMC = IMT – IMC percebemos que essas 
diferenças são iguais à folga que existe em uma atividade. 
No caso da atividade J, não há folga, pois FJ = TMTJ – TMCJ = IMTJ – IMCJ = 0.
É interessante que possamos observar a rede de atividades com todos as 
datas de início, mais cedo e mais tarde, e término, mais cedo e mais tarde, e as 
folgas de todas as atividades. Podemos fazer isso avaliando a Figura 21, a seguir:
FONTE: Os autores
FIGURA 21 - REDE DE ATIVIDADES COM AS DATAS PREVISTAS NO PROJETO
TÓPICO 2 | TÉCNICAS PERT/CPM
117
Que tal um pouco de cálculos? Verifique os valores das datas e folgas colocados 
na Figura 21.
Também há a possibilidade de visualizar as datas das atividades através de 
tabelas conhecidas como Diagramas de Gantt. Como fazemos na Tabela 20 a seguir:
AUTOATIVIDADE
TABELA 20 - PROGRAMA DAS DATAS DAS ATIVIDADES ATRAVÉS DE DIAGRAMA DE GANTT
A
tiv
.
0 1 2 3 4 5 6 7 8 9 10
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
4
0
4
1
4
2
4
3
4
4
A
B
C
D
E
F
G
H
I
J
K
L
M
N
FONTE: Os autores
Nesse diagrama, representamos as datas mais cedo em amarelo e as datas mais 
tarde em preto.
UNI
118
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
2.4 PROGRAMAÇÃO DAS ATIVIDADES – CPM
Algumas atividades podem ter suas durações alteradas devidos a fatores 
não previstos no planejamento inicial. Assim, essas atividades podem ser 
adiantadas ou atrasadas devido à escassez ou abundância de recursos, variações 
climáticas ou econômicas etc.
Com o objetivo de conseguir um planejamento mais confiável, muitas vezes 
é necessária a introdução de algumas variáveis probabilísticas aparentemente 
conhecidas. A fim de se estabelecer uma distribuição de probabilidades 
compatível com os problemas por nós abordados, a Técnica do Caminho Crítico 
(CPM) utiliza a distribuição beta e, a partir de poucos parâmetros fáceis de serem 
obtidos, estabelece, para cada atividade i, três medidas de tempo, que são:
TOi = é o tempo mínimo estimado com razoável para a execução da 
atividade i, também conhecido como o tempo mais otimista; 
TMi = é o tempo mais provável para a execução da atividade i, ou seja, o 
que ocorre com maior frequência (na estatística é a moda da distribuição);
TPi = é o máximo tempo estimado razoável para execução da atividade i, 
também conhecido como tempo mais pessimista.
Usamos essas medidas para estimar a média e a variância da distribuição 
de uma variável aleatória Ti, que representa o tempo de execução da atividade 
i. Essas medidas derivam do desvio-padrão da média, e podem ser calculadas 
aproximadamente por:
 que representa a média da atividade i
 que representa a variância da atividade i
Podemos expandir nossa tabela de atividades com as durações 
probabilísticas, como no exemplo a seguir:
 TABELA 21 - DURAÇÕES PROBABILÍSTICAS DAS ATIVIDADES DOPROJETO DE CONSTRUÇÃO.
ATIVIDADE
DURAÇÃO PREVISTA PARÂMETROS
OTIMISTA MAIS PROVÁVEL PESSIMISTA MÉDIA VARIÂNCIA
A 1 2 3 2 0,111
B 2 3,5 8 4 1
C 6 9 18 10 4
D 4 5,5 10 6 1
E 1 4,5 5 4 0,444
TÓPICO 2 | TÉCNICAS PERT/CPM
119
F 4 4 10 5 1
G 5 6,5 11 7 1
H 5 8 17 9 4
I 3 7,59 7 1
J 3 9 9 8 1
K 4 4 4 4 0
L 1 5,5 7 5 1
M 1 2 3 2 0,111
N 5 5,5 9 6 0,444
FONTE: Os autores
Com os valores dados na tabela 20, podemos imaginar, por exemplo, o pior 
cenário possível para o projeto em andamento, ou seja, determinar o Caminho 
Crítico, usando as durações pessimistas. A Tabela 22 mostra os cálculos feitos 
para os seis caminhos já determinados anteriormente.
TABELA 22 - DURAÇÕES PESSIMISTAS (PIOR CENÁRIO) PARA OS POSSÍVEIS CAMINHOS 
DA REDE DE ATIVIDADES
Caminho (Atividades) Comprimento (em semanas)
Inicio-ABCDGHM-Fim 3 + 8 + 18 +10 + 11 + 17 + 3 = 70
Inicio-ABCEHM-Fim 3 + 8 + 18 + 5 +17 + 3 = 54
Inicio-ABCEFJKN-Fim 3 + 8 + 18 + 5 + 10 + 9 + 4 + 9 = 66
Inicio-ABCEFJLN-Fim 3 + 8 + 18 + 5 + 10 + 9 + 7 + 9 = 69
Inicio-ABCIJKN-Fim 3 + 8 + 18 + 9 + 9 + 4 + 9 = 60
Inicio-ABCIJLN-Fim 3 + 8 + 18 + 9 + 9 + 7 + 9 = 63
FONTE: Os autores
De acordo com a tabela 21, o pior cenário se dá pela construção em setenta 
semanas, o que inviabiliza o projeto. Mas, qual a probabilidade de que isso ocorra?
Consideramos então o Caminho Crítico calculando a média da duração 
total do projeto, fazendo:
µ (TProj)= µ (TA) + µ (TB) + µ (TC) + ... + µ (TN)
E a variação total do projeto fazendo:
σ2 (TProj)= σ2 (TA) + σ2 (TB) + σ2 (TC) + ... + σ2 (TN) 
Em nosso exemplo, o Caminho Crítico Médio é dado por Início-
ABCEFJLN-Fim, com µ (TProj)=44 e σ2 (TProj)=9.
120
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
Kα =
d – µ (TProj)
σ (TProj)
Para calcular o Caminho Médio, devemos calcular a média de cada atividade 
Caminho Crítico e somar essas médias. Verifique os valores calculados µ 
(TProj) = 44 e σ2 (TProj)=9 com a ajuda da tabela 20.
E para determinar a probabilidade de terminar o projeto em d 
unidades de tempo em relação à distribuição normal padrão (com média 0 
e desvio-padrão 1), buscando P(TProj ≤ d) = P(Z ≤ Kα) = 1 – P(Z > Kα)
Onde 
 
.
Assim, a probabilidade de terminar o projeto a fim de evitar a multa do 
contrato é dada pela probabilidade de terminar o projeto em 47 semanas, ou seja:
E assim
P(TProj ≤ 47) = P(Z ≤ 1) = 1 – P(Z > 1) = 1 – 0,159 = 0,841, ou seja, temos 
84,1% de probabilidade de terminar o projeto em 47 semanas. Mas, a empreiteira 
receberá um bônus de $ 150 mil se terminar o projeto em quarenta semanas. 
Então, podemos calcular a probabilidade de que isso ocorra, fazendo:
E assim
P(TProj ≤ 40) = P(Z ≤ –1,333) = P(Z > 1,333) = 0,092,, ou seja, a probabilidade 
de que a empreiteira consiga terminar a obra em quarenta semanas é de, 
aproximadamente, 9%.
AUTOATIVIDADE
Kα =
d – µ (TProj) 40 – 44 –4
σ (TProj) 3 3
= = = 1,333
Kα =
d – µ (TProj) 47 – 44 3
σ (TProj) 3 3
= = = 1
Para encontrar o valor P(Z ≤ Kα), consulte a tabela de distribuição normal no 
apêndice, no final do caderno. Devemos procurar na primeira coluna da tabela o valor de 
Kα com uma casa decimal, e na primeira linha os centésimos de Kα. O valor de P está na 
intersecção entre a coluna e a linha.
Se Kα >0, 1 – P(Z).
Se Kα <0, P(Z).
IMPORTANT
E
121
RESUMO DO TÓPICO 2
Neste tópico, estudamos as técnicas PERT/COM, e vimos:
• que a programação de projetos que envolvem atividades dependentes entre 
si pode ser representada através da organização de uma rede (ou grafo) de 
atividades.
• como utilizar as técnicas PERT/CPM para resolver os problemas de caminho 
crítico e desenvolvimento do projeto.
• como determinar as datas de início e término mais cedo e mais tarde para as 
atividades e para o projeto.
• como representar essas datas através do Diagrama de Gantt.
• como programar as atividades e determinar quais delas podem ou não sofrer 
folgas ou atrasos.
• e como calcular as probabilidades de terminar um projeto em um dado tempo 
d, com base na tabela de distribuição de probabilidades.
122
AUTOATIVIDADE
Para exercitar seus conhecimentos adquiridos, resolva as questões a 
seguir:
1 Um latoeiro recebeu um automóvel usado para reformá-lo. Neste, devem 
ser feito os serviços de latoaria, pintura, e também a reforma do motor. 
As durações e as dependências entre as atividades são dadas no quadro a 
seguir:
ATIVIDADE DESCRIÇÃO ATIVIDADE ANTECEDENTE
DURAÇÃO (EM 
DIAS)
A Latoaria - 6
B Pintura A 8
C Reforma do motor - 9
Pede-se o tempo total que o latoeiro necessitará para concluir a reforma.
2 (LOESCH; HEIN, 1999, p. 212) - Uma empresa deve realizar o projeto 
determinado pelas atividades dadas no quadro a seguir.
ATIVIDADE ATIVIDADE ANTECEDENTE
DURAÇÃO 
(EM DIAS)
A - 5
B - 7
C - 10
D A 12
E B e C 4
F B 8
G D e E 11
H B e C 13
I F 10
Diante dessa situação:
a) represente as atividades dadas numa rede de atividades, obedecendo às 
dependências entre as atividades.
123
b) Determine o caminho crítico do projeto.
c) Determinas as datas de início e término, mais cedo e mais tarde de cada 
atividade.
d) Represente o projeto usando um esboço do Diagrama de Gantt.
e) Qual o menor tempo necessário para realizar o projeto, nessas condições.
3 Considere o mesmo projeto da questão 2, agora com tempos de duração 
mais provável, mais otimista e mais pessimista de cada uma das atividades 
dadas no quadro a seguir:
ATIVIDADE
DURAÇÃO PREVISTA PARÂMETROS
OTIMISTA MAIS PROVÁVEL PESSIMISTA MÉDIA VARIÂNCIA
A 4 5 6
B 5 6,5 11
C 7 9 17
D 7 11,5 19
E 3 4 5
F 5 7 15
G 2 12 16
H 3 14 19
I 8 9,5 14
a) Complete as colunas do quadro, calculando o tempo médio e a variância de 
cada atividade.
b) Calcule o tempo médio e a variância do projeto todo.
c) Qual a probabilidade de terminar esse projeto em até vinte dias?
d) Qual a probabilidade de terminar esse projeto em até trinta dias?
124
125
TÓPICO 3
SIMULAÇÃO
UNIDADE 3
1 INTRODUÇÃO
Loesch e Hein (1999, p. 227) expõem que a palavra simular tem sua 
origem no trabalho de Von Neumann que, em 1940, utilizou a expressão análise 
de Monte Carlo para significar uma técnica matemática empregada na solução 
de problemas de Física Nuclear, para os quais um solução experimental seria 
muito dispendiosa, ou um tratamento analítico seria muito complicado. 
Simular é essencialmente uma técnica que envolve a construção de um 
modelo de uma situação real para posterior experimentação. 
2 SIMULAÇÃO DE MONTE CARLO
Imagine uma roleta de jogos de cassino numerada de 00 a 99. Os números 
dessa roleta são utilizados para dar uma interpretação a alguns resultados e uma 
interpretação a outros resultados. Podemos, por exemplo, imaginar que se queira 
simular o sexo de uma criança ao nascer, baseados no fato de que: se der um 
número entre 00 e 49, o sexo é masculino; se der um número de 50 a 99, o sexo é 
feminino. Pela repetição de experimentos, ou seja, se rodarmos a roleta e anotarmos 
o resultado uma considerável quantidade de vezes, teremos uma distribuição 
aproximada de 50% de chance de ocorrência de sexo masculino e 50% de chance 
de ocorrência de sexo feminino. Assim, o procedimento para a simulação é obtido 
por gerar uma tabela de valores aleatórios, sorteados pela roleta de Monte Carlo. 
A Tabela 23 a seguir, nos dá alguns valores e suas interpretações.
TABELA 23 - REPRESENTAÇÃO DE SIMULAÇÃO PARA O PROBLEMA DE SEXO DE BEBÊS USANDO 
NÚMEROS ALEATÓRIOS SORTEADOS POR UMA ROLETA
Roleta 13 20 40 64 19 90 75 10 12 26 45 82 13 51
Sexo M M M F M F F M M M M F M F
FONTE: Os autores
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
126
Se continuarmos o experimento um número expressivamente grande de 
vezes, essa distribuição tenderá a 50% para cada sexo. A lei dos grandes números 
nos diz que quanto maior o número de experimentos, mais a frequência relativa 
de um evento se aproxima da probabilidade teórica.
Isso nos leva a crer que um processo de simulação deve trabalhar com 
muitos dados para podermos chegar a uma conclusão com certo nível de certeza.
A questão é como gerar números aleatórios suficientes sem se cansar, 
girando roletas, por exemplo? No Apêndice desse caderno, são encontradas 
tabelas de números aleatórios, mas o procedimento mais eficaz atualmente é a 
utilização do computadorcomo gerador. Novamente vamos utilizar o software 
Microsoft Excel como recurso ao nosso objetivo.
2.1 GERANDO NÚMEROS ALEATÓRIOS NO COMPUTADOR
Existem duas funções padrão do Excel para gerar números aleatórios: a 
função ALEATÓRIO(), para a geração de números uniformemente distribuídos 
entre 0 e 1; e a função ALEATÓRIOENTRE(A,B), para a geração de números 
uniformemente distribuídos entre um valor dado A e outro B.
Podemos fazer o processo de simulação do sexo dos bebês:
• gerando uma coluna de números aleatórios usando a função ALEATÓRIO(): 
digitamos a função na 1ª linha (célula A1) e a copiamos para um número 
considerável de linhas abaixo dela;
• na 2ª coluna usamos uma função SE para definir o sexo do bebê baseado no 
número da coluna anterior para cada linha da tabela. Assim, podemos definir 
para a célula B1 a fórmula =SE(A1<0,50;”M”;”F”). Essa fórmula analisa o número 
que se encontra na célula à esquerda de B1. Assim, se o número for menor que 
0,50, a célula recebe o valor M (masculino), se o número não for menor que 0,50, 
a célula recebe o valor F (feminino).
Vamos fazer o experimento setenta vezes (setenta células), copiando a 
função ALEATÓRIO() nas células A1 até A70 e a fórmula =SE(A1<0,50;”M”;”F”) 
até =SE(A70<0,50;”M”;”F”).
Para calcular o número de vezes que os valores M e F aparecem, na 
célula C1 vamos utilizar uma função de contagem dada pela fórmula =CONT.
SE(B1:B70;”M”) que nos dá a quantidade de letras M que aparecem na tabela. 
Podemos fazer o mesmo com a letra F, na célula C2. Para indicar a frequência 
relativa de M e F, podemos dividir os valores calculados em C1 e C2 por 100, 
encontrado o percentual de bebês do sexo masculino e feminino. Quanto mais 
linhas forem consideradas no experimento, mais próximos de 50% serão esses 
quocientes.
TÓPICO 3 | SIMULAÇÃO
127
Outra maneira de gerar números aleatórios no Microsoft Excel é utilizar 
as ferramentas de Análise de dados disponível como suplemento desse software. 
Possivelmente será necessário habilitar o uso da ferramenta Análise de Dados 
seguindo os procedimentos:
• clicar no Menu do Excel e selecionar o botão Opções do Excel;
• na Guia Suplementos, clicar em Ir... , para a opção Gerenciar Suplementos do Excel;
• selecionar Ferramentas de Análise e clicar OK.
Na aba Dados é habilitada (à direita e em cima) um botão de Análise de 
Dados. Clicando nele temos a caixa de diálogo de mesmo nome, onde selecionamos 
a opção Geração de número aleatório. Abre-se uma nova caixa de diálogo intitulada 
Geração de Número Aleatório, mostrada na Figura 22.
FONTE: Microsoft Excel
Nessa caixa de diálogo devemos definir alguns valores:
• Número de variáveis: quantas variáveis de decisão queremos simular
• Número de números aleatórios: quantos números queremos simular para cada 
variável.
FIGURA 22 - CAIXA DE DIÁLOGO GERAÇÃO DE NÚMEROS ALEATÓRIOS
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
128
• Distribuição: que tipo de distribuição probabilística queremos usar (Uniforme, 
Normal, Bernoulli, Poisson, Padronizada ou Discreta). Essas distribuições são 
melhor estudadas nas disciplinas de Estatística ou Probabilidade e Estatística.
• Parâmetros: dependem da distribuição adotada. No caso da distribuição 
Normal, os parâmetros são Média e Desvio Padrão.
• Semente aleatória: um valor que é gerador de números aleatórios. Se não 
especificado, o Excel usa um número qualquer.
• Opções de saída: é o intervalo de células em que queremos colocar nossos 
números aleatórios.
3 PLANEJAMENTO DE SIMULAÇÕES
Para elaborar um projeto ou modelo que simule uma situação real deve 
obedecer a uma estrutura, adotada como padrão para a maioria dos profissionais 
que trabalham com simulação. Essa estrutura é definida por:
1. Formulação do problema: em que são especificadas as informações 
de que o modelo necessita e identificados os tipos de questões que devem ser 
respondidas. 
2. Identificação das variáveis relevantes: são variáveis que representarão 
aspectos de interesse do sistema que foram identificadas no primeiro passo, e 
também, outras geradas dentro do modelo, para chegar à solução final. 
3. Formalização das equações do modelo: uma vez definido o conjunto de 
variáveis significativas, as relações entre elas devem ser formalmente escritas em 
termos matemáticos. Essas relações podem ser definidas pela lógica do problema 
ou empíricas, obtidas por técnicas de estimação, segundo as quais alguns fatores 
são estimados a partir de dados históricos. 
4. Codificação do modelo: geralmente os modelos são grandes e 
complexos, podendo ser programados para solução por computadores. Como 
essa programação influencia o desempenho do modelo, esta fase deve ser realizada 
por especialistas no assunto, com o objetivo de se obter a melhor programação 
possível. As planilhas eletrônicas têm sido utilizadas atualmente, além de outros 
programas especiais. 
5. Teste do modelo: esta é uma fase que deve ser realizada cuidadosamente. 
São realizados testes com o objetivo de ajustar o modelo ao que se espera dele 
e validá-lo de forma a promover sua aceitação. Às vezes, são aplicados dados 
históricos para verificar se os resultados obtidos correspondem aos conseguidos 
na realidade. 
TÓPICO 3 | SIMULAÇÃO
129
6. Aplicação do modelo: uma vez que tenha sido validado, o modelo pode 
ser utilizado para produzir respostas para as questões identificadas no passo 1.
3.1 EXEMPLO DE SIMULAÇÃO
“Uma máquina de encher frascos de perfume opera a um custo de $ 0,50 por 
ml colocado em cada frasco e mais um custo fixo de $ 10,00. A quantidade colocada no 
frasco é uma variável aleatória normal de desvio-padrão 15 ml, cujo valor médio vai 
depender do ajuste da máquina. O frasco tem capacidade para 140 ml e é vendido por 
$ 75,00 a unidade. Se forem colocados no frasco menos de 80 ml, o cliente tem direito 
a reembolso. Se forem embalados mais de 140 ml, o frasco transborda, ocasionando 
desperdício, e assim, prejuízo. Qual a regulagem ideal da máquina, de forma que se 
maximize o lucro esperado da venda?”
As variáveis envolvidas no problema são: lucro com a venda e a quantidade 
média (em ml) que a máquina deve colocar em cada frasco. Chamando L o lucro, 
que depende da quantidade média x de perfume, podemos escrever a função que 
determina o lucro através da diferença entre a receita obtida pela venda e os custos de 
produção. A receita é de R$ 75,00 por unidade vendida, não importando a quantidade 
de perfume colocada no frasco, e o custo é dado por C(x) = 5x + 10. Assim, o lucro 
é calculado por L(x)75 – (5x + 10), ou melhor, L(x)65 – 5x, onde x é a quantidade 
média de perfume (em ml) colocado no frasco. Assim, devemos determinar qual é 
essa quantidade média x através de simulações.
Para essas simulações, vamos utilizar a ferramenta Análise de Dados: geração de 
números aleatórios do Excel.
O que devemos fazer é gerar simulações para os ajustes da máquina e verificar 
qual dos ajustes nos dá o maior lucro médio. Para isso, fazemos simulações ajustando 
a máquina para colocar, em média, 80 ml de perfume em cada frasco, depois 90 ml 
em cada frasco, depois 100 ml, 110 ml, 120 ml, 130 ml e, por último, 140 ml em cada 
frasco, que é a capacidade deste frasco.
Antes de partir para as simulações, vamos explorar um pouquinho esses 
valores: se ajustarmos a máquina com média 80 ml por frasco, usando o desvio-
padrão 15 ml dado pelo problema, teremos muitos frascos com menos de 80 ml, 
e, assim, a empresa deverá fazer muitas devoluções. Por outro lado, se usarmos o 
desvio-padrão de 15 ml com uma média de 140 ml colocados em cada frasco no 
ajuste da máquina, o desperdício será muito grande, já que a máquina colocará, em 
alguns frascos, mais perfume do que a capacidade do mesmo. Com essas medidas o 
lucro, definitivamente, não será o melhor. Assim, podemos reduzir nosso número de 
simulações, ou melhor, diminuir as simulações feitas a partir das médias estipuladas. 
Para não alongar demais o problema, não vamos simular médias intermediárias 
(como95, 105, 115 etc.), pois assim deveríamos simular todas as médias entre 80 e 140 
ml (80, 81, 82, 83 etc.), o que nos daria muito trabalho.
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
130
Vamos então à simulação!
Numa planilha do Microsoft Excel, vamos colocar números aleatórios, 
seguindo uma distribuição normal com a média definida por nós e o desvio-padrão 
quinze. Assim, podemos definir uma coluna da planilha para cada média simulada. 
Por exemplo, a coluna A terá os números aleatórios referentes à média noventa e 
desvio-padrão quinze; a coluna B terá os números aleatórios referentes a média cem 
com mesmo desvio-padrão; a coluna C terá os números aleatórios gerados a partir da 
média 110; a coluna D para a média 120 e a coluna E para a média 130.
O que colocar nas colunas? Na primeira linha, escreva Média noventa, 
Média cem, Média 110, Média 120 e Média 130, nas células A1, B1, C1, D1 e E1, 
respectivamente. O restante deixe que o Excel o faça por você. Na aba Dados clique 
na opção que habilitamos anteriormente, Análise de Dados, e na caixa que abre escolha 
Geração de números aleatórios. Na caixa de diálogo que aparece, vamos definir os 
seguintes parâmetros:
Número de variáveis: 1
Número de números aleatórios: 1000
Distribuição: Normal
Parâmetros: Média noventa e desvio-padrão quinze
Semente aleatória: podemos deixar em branco
Opções de saída: selecione Intervalo de saída e escreva A2
Na planilha aparecerão 1000 números aleatórios na coluna A. Faça o mesmo 
procedimento para as colunas B, C, D e E, apenas alternado o valor da média da 
distribuição Normal para 100, 110, 120 e 130, respectivamente. Pronto, estão geradas 
as simulações. Agora, vamos aos cálculos para verificar qual média dará o melhor 
ajuste, mas o Excel também nos fará os cálculos. Claro que temos que informar a ele 
o que fazer. Lembre-se de que a máquina não trabalha sozinha. Nas células G1, H1, 
I1, J1 e K1, escreva, respectivamente, Lucro (90), Lucro (100), Lucro (110), Lucro (120) 
e Lucro (130).
Vamos usar a função SE do Excel para calcular o lucro, se houver lucro, 
fazendo o seguinte:
Na célula G2, escreva a função =SE(A2>80;65-0,5*A2;-75). Essa função faz o 
seguinte: se o valor da célula A2 for maior que oitenta (nosso limite mínimo), então 
o lucro será calculado por 65 reais de receita menos o custo de R$ 0,50 para cada ml 
dado na célula A2. Caso contrário (se A2 for menor que 80), então, o lucro é de R$ 75 
negativos, ou seja, prejuízo de setenta e cinco reais.
Agora, para as outras colunas, basta clicar na célula G2 e arrastar a função Se 
para as células vizinhas e o Excel dá o resultado do lucro para cada valor das colunas 
A até E. Em seguida, selecione as células G2 até K2 a arraste a função SE até o final 
da simulação, ou seja, até as células G1001 e K1001. Assim, são calculados lucros de 
todas as simulações realizadas nas cinco colunas.
TÓPICO 3 | SIMULAÇÃO
131
Só falta determinar o lucro médio. Este pode ser calculado também usando 
uma função do Excel, na célula G1002. Logo abaixo dos lucros da simulação para 
Média noventa, escrevemos a função =MÉDIA(G2:G1001), e arrastamos essa função 
para as células vizinhas H1002, I1002, J1002 e K1002. Nessas células, estão os lucros 
médios obtidos pela simulação para os ajustes da média de 90 até 130 ml. E só escolher 
o maior lucro.
Fizemos uma simulação para testes e os resultados estão mostrados na 
Tabela 24.
TABELA 24 - EXEMPLO DE SIMULAÇÃO REALIZADO PARA O PROBLEMA DO PERFUME
A B C D E F G H I J K
1 Média 90
Média 
100
Média 
110
Média 
120
Média 
130
Lucro 
(90)
Lucro 
(100)
Lucro 
(110)
Lucro 
(120)
Lucro 
(130)
2 85,50 97,68 94,51 104,41 118,91 22,25 16,16 17,74 12,80 5,55
3 70,83 86,17 108,85 106,35 128,62 -75,00 21,92 10,58 11,82 0,69
4 93,66 104,92 143,60 121,11 146,84 18,17 12,54 -6,80 4,45 -8,42
5 109,15 133,98 116,37 123,99 140,66 10,43 -1,99 6,81 3,01 -5,33
6 107,98 82,53 109,42 105,29 157,77 11,01 23,74 10,29 12,35 -13,88
7 116,00 101,77 103,73 107,74 132,34 7,00 14,11 13,14 11,13 -1,17
8 57,25 119,21 119,50 107,22 105,43 -75,00 5,40 5,25 11,39 12,29
9 86,49 83,63 108,61 121,06 131,38 21,76 23,19 10,69 4,47 -0,69
10 106,43 99,94 114,38 103,76 127,23 11,79 15,03 7,81 13,12 1,38
999 97,25 78,89 117,47 107,04 132,08 16,38 -75,00 6,26 11,48 -1,04
1000 98,63 86,83 96,94 128,80 128,06 15,69 21,59 16,53 0,60 0,97
1001 95,02 108,41 111,51 101,53 107,99 17,49 10,80 9,25 14,24 11,00
1002 Lucro Médio: -7,93 5,74 7,60 4,70 0,06
FONTE: Os autores
Perceba que ocultamos parte da tabela (da linha 11 à linha 998) por questão 
de espaço. E como os números foram gerados aleatoriamente, se você repetir os 
procedimentos, seus valores poderão ser diferentes dos valores calculados aqui, 
mas os resultados devem ser os mesmos esperados. Analisando os lucros médios 
obtidos a partir dessa simulação, temos as seguintes conclusões:
• se a máquina for regulada com média de 90 ml por frasco, teremos um lucro 
médio esperado de -7,93 reais, ou seja, um prejuízo de R$ 7,93;
• se a máquina for regulada com média de 100 ml por frasco, teremos um lucro 
médio esperado de 5,74 reais;
• se a máquina for regulada com média de 110 ml por frasco, teremos um lucro 
médio esperado de 7,60 reais;
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
132
LEITURA COMPLEMENTAR
• se a máquina for regulada com média de 120 ml por frasco, teremos um lucro 
médio esperado de 4,70;
• se a máquina for regulada com média de 130 ml por frasco, teremos um lucro 
médio esperado de R$ 0,06, ou seja, seis centavos.
Desse modo, podemos concluir que o melhor lucro médio esperado 
(solução ótima) para o problema do perfume será obtido ao ajustar a máquina 
com uma média de 110 ml por frasco, obedecendo ao desvio-padrão 15 ml. O 
lucro médio é de R$ 7,60 por frasco de perfume.
ONDE ENCONTRAR NÚMEROS ALEATÓRIOS?
Com o surgimento das primeiras linguagens de programação, os 
programadores escreviam rotinas para a geração de números aleatórios. Ou 
melhor: pseudo-aleatórios, pois o computador não consegue sortear de fato, 
como o faz uma pessoa ao girar a roda de uma roleta e anotar o resultado. 
Rotinas matemáticas foram escritas, baseadas no Método Congruencial Misto, para 
a geração de sequências numéricas que parecem de fato ser números sorteados 
ao acaso: só que não o são. Estes números são calculados, sequencialmente, 
um usando o resultado do anterior. Parte-se de um número aleatório inicial x0, 
chamado de semente, e a partir daí, calculam-se os demais valores da seqüência 
através da função recorrente xn = (axn–1 + c)(módulom)param = 1,2,3... 
Onde a, c e m são constantes inteiras e positivas tais que a < m e c < m. 
Esta notação significa que xn é o resto da divisão de ax + c por m. Isto significa 
que 0 ≤ xn < m, de forma que a sequência pode apresentar no máximo m valores 
diferentes antes de voltar a ser repetida. Por exemplo, suponha tomar-se xn = 
(1257xn-1 + 2471)(módulo 32768). Partindo-se de x0 = 12345, é gerada a seqüência
12345 20872 24175 14510 22533 14900 21243
31770 25937 1120 1287 14598 2077 24588
9363 8050 28777 32056 24991 24414 20021
Você pode fazer outras simulações para comprovar esses valores. Lembre-se de 
que pode haver diferenças nos lucros médios devido às diferentes simulações.
UNI
TÓPICO 3 | SIMULAÇÃO
133
3044 27691 10442 20865 15376 29751 11190
10829 15804 ...
Caso se desejem números aleatórios reais entre 0 e 1, basta dividir cada 
um dos números inteiros da sequência por 32768. A escolha de a e c deve ser no 
sentido de produzir boas séries de números aleatórios. A sequência deve passar 
pelo teste de aderência à distribuição uniforme e inexistência de autocorrelação 
na série para que se possam utilizar esse números pseudo-aleatórios como se 
realmente fossem resultados de experimentos realizados em uma população 
uniformemente distribuída.
Atualmente, muitas linguagens de programação incluem em suas 
bibliotecas de rotinas o método congruencial para a obtenção de números 
aleatórios inteiros equiprováveis ou números aleatóriosreais distribuídos no 
intervalo [0, 1).
Para simular resultados de distribuições discretas empíricas, pode-
se utilizar números aleatórios uniformemente distribuídos no intervalo [0, 1). 
Para isso, deve-se previamente fixar os limites das faixas dentro das quais o 
número aleatório gerado determina um resultado em particular, segundo uma 
distribuição discreta empírica. Tome-se, por exemplo, uma distribuição discreta 
empírica como a da tabela a seguir.
k P(k) F(k) = P(x ≤ k) Limites dos números aleatórios
1 0,20 0,20 [0,000 , 0,200)
2 0,45 0,65 [0,200 , 0,650)
3 0,25 0,90 [0,650 , 0,900)
4 0,1 1,00 [0,900 , 1,000)
Assim, se um números aleatório for 0,29194, ele pertence ao intervalo 
[0,200 , 0,650), que corresponde a um valor simulado k = 2.
Pode-se utilizar a tabela 1 de números aleatórios uniformemente 
distribuídos do apêndice para gerar simulações de distribuições uniformes 
e de distribuições discretas empíricas. A tabela pode ser utilizada para criar 
uma sequência de números aleatórios, independente da forma como for lida: 
sequencialmente em linha, em comula, em forma alternada, de trás para frente 
etc.
Porém, caso se deseje simular determinados eventos estocásticos, pode 
ser que a distribuição de probabilidade ocorra segundo algum modelo clássico 
UNIDADE 3 | PROGRAMAÇÃO DE PROJETOS
134
da Teoria das Probabilidades, contínuo (normal, exponencial, etc.) ou discreto 
(binomial, Poissom, Pascal etc.).
No caso de estaturas de pessoas, caso se verifique ser esta variável aleatória 
uniformemente distribuída em torno de um valor médio, com um determinado 
desvio-padrão, estes valores devem ser tomados a partir de uma função que gera 
números aleatórios, sendo a distribuição normal com esses parâmetros. Porém, 
é necessário, antes, submeter os dados empíricos a um teste não paramétrico 
de aderência a uma distribuição. Aceita a hipótese, tomam-se os parâmetros 
estimados para efetuar as simulações.
Como exemplo, suponha-se que a estatura de X homens de uma certa 
população seja uniformemente distribuída segundo uma normal padrão de 
média µ = 1,70 m e desvio-padrão σ = 0,12m. Para se proceder a simulação 
com emprego da tabela 2 do apêndice, embora ela seja uma tabela de números 
aleatórios provindos de uma distribuição padronizada, deve-se considerar o uso 
da relação.
Onde Z=N(0,1) e X = N(µ, σ2), para gerar valores de X. Desta forma, a 
tabela 2 pode ser utilizada para obter o valor de Z, e a relação acima permite 
transformá-lo em estaturas simuladas X. Assim, por exemplo, tomando-se um 
número aleatório da tabela, como Z = -0,30023, este irá simular uma estatura x = 
–0,30023 • 0,12 + 1,70, ou seja, 1,66 metros.
FONTE: LOESCH, Claudio; HEIN, Nelson. Pesquisa operacional: fundamentos e modelos. 
Blumenau: Furb, 1999. p. 228.
Z = ⇒ X = Zσ +µ 
X – µ 
 σ 
135
RESUMO DO TÓPICO 3
Neste tópico, você viu que:
• A simulação é utilizada quando experimentos reais são muito dispendiosos ou 
demorados.
• Dentre as técnicas de simulação se destaca a Simulação de Monte Carlo, 
baseada em sorteio aleatório de números numa roleta. Podemos ainda realizar 
esses sorteios através de moedas, dados, tabelas de números aleatórios ou 
outros dispositivos como o computador.
• Um problema de simulação deve passar por alguns procedimentos estruturais:
 • formulação do problema;
 
 • identificação das variáveis relevantes;
 • formalização das equações do modelo;
 • codificação do modelo;
 • teste do modelo;
 • aplicação do modelo.
136
AUTOATIVIDADE
Exercite seus conhecimentos adquiridos, resolvendo as questões que 
seguem:
1 Usando o exemplo de simulação da máquina de perfumes, simule qual 
seria o lucro médio obtido se a máquina fosse ajustada:
a) com a média 80 ml e desvio-padrão 15 ml.
b) com a média 140 ml e desvio-padrão 15 ml.
2 Uma loja de autopeças deseja estabelecer uma política de reposição 
de estoque de um produto vendido por ela, ou seja, a partir de quantas 
unidades ela deve fazer um pedido de reposição ao fornecedor. O objetivo 
dessa loja é maximizar o lucro com as vendas desse produto. Como o 
fornecedor necessita de 3 a 5 dias para a reposição, segundo a distribuição 
de probabilidades discreta dada por:
Dias de espera (k) Probabilidade P(k)
3 0,2
4 0,5
5 0,3
A reposição por parte do fornecedor é feita em lotes de 1000 peças e 
tem um custo de R$ 100. Cada peça vendida dá um lucro de R$ 1,50 para a 
loja. Cada peça tem um custo de manutenção para a loja de R$ 0,10.
A procura pela peça na loja obedece uma distribuição de Poisson, com 
média 120 peças vendidas por dia. Na falta de peças, o cliente compra suas 
peças em outra loja e com isso o negócio não é feito.
Simule o lucro líquido obtido com a venda dessas peças, ou seja, 
descontando os custos de manutenção e reposição das peças. Verifique qual 
quantidade deve ser mantida em estoque para que a loja tenha maior ganho 
com a venda.
Dica: Para simular uma distribuição discreta no Excel, reproduza 
a tabela acima numa planilha, em um intervalo como A1:B3, e selecione a 
ferramenta geração de números aleatórios. Na definição da distribuição escolha 
Discreta e como parâmetro use o intervalo A1:B3.
137
REFERÊNCIAS
BIEMBENGUT, Maria Salett; HEIN, Nelson. Modelagem matemática no 
ensino. 2. ed. Blumenau: Contexto, 2002. 
BOLDRINI, Jose L.; COSTA, Sueli I. R.; FIGUEIREDO, Vera L.; WETZLER, 
Henry G. Álgebra linear. São Paulo: Harper e Row do Brasil, 1980. 
BRONSON, Richard. Pesquisa operacional. São Paulo: McGraw-Hill do Brasil, 
1985. 
HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à pesquisa 
operacional. 8. ed. São Paulo: McGraw-Hill, 2006. 
LISBOA, Erico F. A. Pesquisa operacional. Disponível em: <www.ericolisboa.
eng.br>. Acesso em: 21 abr. 2009.
LOESCH, Cláudio; HEIN, Nelson. Pesquisa operacional: fundamentos e 
modelos Blumenau: Editora da FURB, 1999. 
NOGUEIRA, Fernando. PERT/CPM. Disponível em: <www.engprod.ufjf.br/
fernando/epd015/programa%E7%E3o_linear.pdf>. Acesso em: 21 abr. 2009.
VARGAS, Saulo; SOUZA, André M. S. Probabilidade e estatística. Blumenau: 
Uniasselvi, 2007. 
WAGNER, Harvey M. Pesquisa operacional. 2. ed. Rio de Janeiro: Prentice-Hall, 
1986. 
138
ANOTAÇÕES
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________
____________________________________________________________