PESQUISA OPERACIONAL

Prévia do material em texto

Pesquisa Operacional
Felipe Kesrouani Lemos
Presidente Prudente
Unoeste - Universidade do Oeste Paulista
2017
Lemos, Felipe Kesrouani. 
 Pesquisa Operacional. / Felipe Kesrouani Lemos. – 
Presidente Prudente: Unoeste - Universidade do Oeste 
Paulista, 2017. 
 62 p.: il.
 Bibliografia.
 ISBN: 978-85-9492-019-5
 1. Pesquisa operacional. 2. Otimização matemática.
3. Variabilidade. I. Título.
CDD\22ª. ed.
© Copyright 2017 Unoeste - Todos os direitos reservados
Nenhuma parte desta publicação poderá ser reproduzida ou transmitida de qualquer modo ou 
por qualquer outro meio, eletrônico ou mecânico, incluindo fotocópia, gravação ou qualquer 
outro tipo de sistema de armazenamento e transmissão de informação, sem prévia autorização, 
por escrito, da Universidade do Oeste Paulista.
Pesquisa Operacional
Felipe Kesrouani Lemos
Reitora: Ana Cristina de Oliveira Lima
Vice-Reitor: Brunno de Oliveira Lima Aneas
Pró-Reitor Acadêmico: José Eduardo Creste
Pró-Reitor Administrativo: Guilherme de Oliveira Lima Carapeba
Pró-Reitor de Pesquisa, Pós-Graduação e Extensão: Adilson Eduardo Guelfi
Diretor Geral: Augusto Cesar de Oliveira Lima
Núcleo de Educação a Distância: Dayene Miralha de Carvalho Sano, Marcelo Vinícius Creres 
Rosa, Maria Eliza Nigro Jorge, Mário Augusto Pazoti e Sonia Sanae Sato
Coordenação Tecnológica e de Produção: Mário Augusto Pazoti
Projeto Gráfico: Luciana da Mata Crema
Diagramação: Aline Miyamura Takehana
Ilustração e Arte: Aline Miyamura Takehana e Rita de Cássia Miranda da Costa
Revisão: Renata Rodrigues dos Santos
Colaboração: Edwiges Inácia de Lima
Direitos exclusivos cedidos à Associação Prudentina de Educação e Cultura (APEC), 
mantenedora da Universidade do Oeste Paulista
Rua José Bongiovani, 700 - Cidade Universitária
CEP: 19050-920 - Presidente Prudente - SP
(18) 3229-1000 | www.unoeste.br/ead
Catalogação na fonte: Rede de Bibliotecas Unoeste
658.403.4
L558p
Felipe Kesrouani Lemos
Graduado em Engenharia de Produção pela Escola Politécnica da Universidade de São 
Paulo (Poli/USP), mestre em Engenharia de Produção pela mesma instituição, com tema 
em Pesquisa Operacional, e doutorando em Engenharia de Produção na Faculdade de 
Engenharia de Bauru, da Universidade Estadual Paulista (FEB/Unesp), também na área 
de Pesquisa Operacional. Trabalhou com planejamento, programação e controle da Pro-
dução (PCP) em multinacionais de diversos ramos, dentre os quais cosméticos, bens de 
consumo e aeronáutico. Atualmente, é docente da Universidade do Oeste Paulista (Uno-
este) e empresário no ramo de serviços, produção industrial e agrícola. É pesquisador 
na área de Pesquisa Operacional aplicada a problemas de planejamento, programação e 
controle da produção.
Sobre o autor
Carta ao aluno
O ensino passa por diversas e constantes transformações. São mudanças 
importantes e necessárias frente aos avanços da sociedade na qual está inserido. A 
Educação a Distância (EAD) é uma das alternativas de estudo, que ganha cada vez mais 
espaço, por comprovadamente garantir bons referenciais de qualidade na formação pro-
fissional. Nesse processo, o aluno também é agente, pois organiza o seu tempo confor-
me suas atividades e disponibilidade. 
Maior universidade do oeste paulista, a Unoeste forma milhares de profissio-
nais todos os anos, nas várias áreas do conhecimento. São 40 anos de história, sendo 
responsável pelo amadurecimento e crescimento de diferentes gerações. É com esse 
mesmo compromisso e seriedade que a instituição iniciou seus trabalhos na EAD em 
2000, primeiramente com a oferta de cursos de extensão. Hoje, a estrutura do Nead 
(Núcleo de Educação a Distância) disponibiliza totais condições para você obter os co-
nhecimentos na sua área de interesse. Toda a infraestrutura, corpo docente titulado e 
materiais disponibilizados nessa modalidade favorecem a formação em plenitude. E o 
mercado precisa e busca sempre profissionais capacitados e que estejam antenados às 
novas tecnologias.
Agradecemos a confiança e escolha pela Unoeste e estamos certos de que 
suas expectativas serão atendidas, pois você está em uma universidade reconhecida 
pelo MEC, que oportuniza o desenvolvimento constante de Ensino, Pesquisa e Extensão. 
Aqui, além de graduação, existe pós-graduação lato e stricto sensu, com mestrados e 
doutorado recomendados pela Capes (Coordenação de Aperfeiçoamento de Pessoal de 
Nível Superior), prêmios conquistados em âmbito nacional por suas ações extensivas e 
pesquisas que colaboram com o desenvolvimento da cidade, região, estado e país; en-
fim, são inúmeros os referenciais de qualidade.
Com o fortalecimento da EAD, a Unoeste reforça ainda mais a sua missão 
que é “desenvolver a educação num ambiente inovador e crítico-reflexivo, pelo exercício 
das atividades de Ensino, Pesquisa e Extensão nas diversas áreas do conhecimento cien-
tífico, humanístico e tecnológico, contribuindo para a formação de profissionais cidadãos 
comprometidos com a responsabilidade social e ambiental”.
Seja bem-vindo e tenha bons estudos!
Reitoria
Sumário
Capítulo 1
ModelageM MateMática de ProbleMas de otiMização
1.1 O Processo de Modelagem ........................................................................................12
1.2 Conceitos Básicos de Modelagem ...............................................................................14
1.3 Programação Linear (PL) ...........................................................................................15
1.4 Soluções de Problema de Programação Linear ............................................................17
1.5 Método Gráfico .........................................................................................................19
1.6 Um Segundo Exemplo de Fixação ..............................................................................22
1.7 O Problema de Transporte .........................................................................................24
Capítulo 2
resolução de ProbleMas de otiMização
2.1 A Forma Padrão de um Problema de Otimização Linear ...............................................30
2.2 Método Simplex ........................................................................................................33
2.3 Método das Duas Fases para Solução Inicial ...............................................................39
2.4 Análise de Sensibilidade ............................................................................................42
Capítulo 3
ProbleMas coM Variabilidade
3.1 Teoria de Filas ..........................................................................................................48
3.2 Notação de Kendall-Lee .............................................................................................50
3.2.1 Medidas de Desempenho em um Sistema de Filas ....................................................51
3.2.2 Um Exemplo de Modelo: M/M/1/FIFO/∞/∞ .............................................................51
3.3 Noções de Simulação ................................................................................................52
3.3.1 Classificação dos Sistemas de Simulação .................................................................53
3.3.2 Simulação Discreta ou Simulação por Eventos Discretos ...........................................54
3.3.3 Passos de um Estudo de Simulação .........................................................................55
3.3.4 Um Exemplo: Simulando uma Linha de Montagem ...................................................57
Referências ....................................................................................................................60
9
Apresentação
Caro aluno,
Com este livro, convido-o a entrar no mundo da Pesquisa Operacional, tam-
bém conhecida na língua inglesa como Management Science (“ciência da gestão”). A 
partir deste conteúdo, queremos introduzir uma forma diferente de tomar decisões do 
mundo real: a modelagem matemática e a soluçãocientífica de problemas de gestão.
O mundo empresarial é formado por muitos sistemas complexos e nos pe-
dem decisões a todo instante. Qualquer gestor ou analista de uma empresa – indepen-
dentemente de seu tamanho – é forçado a tomar decisões: quanto produzir, qual ordem 
deve ser feita primeiro, quanto e quando comprar matérias-primas, qual transporte uti-
lizar, quantas máquinas utilizar, quantas pessoas contratar, quais os melhores turnos de 
produção... e uma infinidade de outras!
A Pesquisa Operacional tem como objetivo elevar o nível da tomada de de-
cisão, saindo apenas do campo da experiência e intuição, para o uso de métodos quan-
titativos. Para isso, utiliza-se, sim, dessa experiência e intuição para criar um modelo 
conceitual do sistema de produção, a ser transformado em linguagem matemática para 
sua posterior solução.
Ao longo do estudo deste material, convido-o a refletir sobre suas experiên-
cias e o mundo ao seu redor, tentando traçar um paralelo com o que vivencia em sua 
prática profissional ou mesmo das pessoas a seu redor. Tente encontrar aplicações, pois 
estamos tratando de uma ciência que toma sentido à medida em que tais aplicações são 
encontradas.
Dividiremos nosso estudo em três partes: uma primeira em que nos dedica-
remos à modelagem matemática, isto é, a tradução de nosso conhecimento do mundo 
real em equações e inequações; um segundo momento em que veremos métodos para 
solucionar esses modelos que encontramos; e, finalmente, analisaremos sistemas em 
que a variabilidade dos dados é importante, os chamados sistemas probabilísticos.
Boa leitura!
11
ModelageM MateMática de ProbleMas de otiMização
Capítulo 1
12
Esta etapa do nosso livro é dedicada à modelagem matemática de problemas 
de otimização. Qual o nosso objetivo aqui? Queremos traduzir sistemas de produção re-
ais em modelos que os representem, para que possamos analisá-los matematicamente.
Ao terminar este estudo, queremos que você tenha a capacidade de enxer-
gar no mundo real as oportunidades de modelagem para que possa, posteriormente, 
resolver seus problemas.
Introdução
Importante
No decorrer do estudo deste livro, faça sempre um paralelo com o mundo ao seu redor. 
Não se esqueça que a teoria sem a prática fica perdida e sem sentido!
1.1 O Processo de Modelagem
Um modelo é uma simplificação da realidade com o objetivo de representá-la. 
Antes de adentrar propriamente na construção de um modelo, precisamos entender como 
é esse processo, integrando-o com a prática. Para isso, veja a Figura 1.
FIGURA 1 - Processo de modelagem
Fonte: Elaboração própria (2017).
A Figura 1 ilustra esse processo, que é um ciclo. Inicialmente, temos um 
sistema de produção real, com suas questões e seus problemas a serem resolvidos. Por 
meio da análise e modelagem, transformamos essa realidade em um modelo matemá-
13
tico, que o representa por equações e inequações. Resolvendo o modelo, teremos uma 
proposta de solução a ser obtida, que precisamos verificar se atende às necessidades do 
problema que estamos analisando. Se a solução obtida não é boa, voltamos ao nosso 
modelo para entender o que representamos de maneira inadequada. Fazemos isso até 
que a solução seja boa o suficiente para ser usada.
Para entender melhor, vamos fazer um exemplo disso. Na Figura 2, vamos 
analisar esse processo com um problema clássico da Pesquisa Operacional e também 
do mundo real: os problemas de corte e empacotamento. Esses problemas consistem 
em reduzir os desperdícios de matéria-prima quando precisamos cortar peças menores 
a partir de uma maior. 
FIGURA 2 - Exemplo de processo de modelagem com o problema de corte
Fonte: Acervo Nead/Unoeste (2017).
Observe que, inicialmente, temos uma questão de entendimento do proble-
ma: notamos os comprimentos dos objetos em estoque, os comprimentos dos itens a 
serem cortados, a demanda de cada um desses itens e que nosso objetivo é utilizar o 
mínimo de matéria-prima possível.
Entendido o problema, partimos para sua elaboração matemática. Na Figura 
2, mostramos o modelo de Kantorovich (1960), um dos pioneiros na modelagem dessa 
área. Resolvendo o problema, temos uma solução, que é uma proposta de como cortar 
as peças. Finalmente, temos que implementar a solução, levando o plano de corte até a 
máquina e verificando se todas as características foram contempladas. Caso contrário, 
deve-se retornar e melhorar a modelagem.
14
a) Variáveis de decisão: são variáveis matemáticas que vão refletir as 
decisões que queremos tomar em nosso sistema de produção, ou seja, as respostas que 
queremos do nosso modelo.
b) Parâmetros: são os dados que coletamos no mundo real para alimen-
tarmos nosso modelo, ou seja, aquilo que já conhecemos.
c) Função objetivo: é aquilo que queremos que nosso modelo otimize, ou 
seja, o que reflete o nosso desejo com o modelo.
d) Restrições: são as características técnicas do nosso problema que nos 
impedem de fazer o que queremos, ou seja, são as imposições que temos que respeitar.
Vamos analisar todos esses conceitos com um exemplo: você possui um ca-
minhão do tipo “baú” com o qual faz fretes de diversos tipos de produtos. Esse caminhão 
tem capacidade, em termos de peso, para carregar no máximo 15.000 kg. Por outro 
lado, as dimensões do baú só permitem um máximo de 28.800 litros de volume.
Você acaba de receber duas propostas de fretes: pode levar bananas, ga-
nhando para isso R$ 140 por tonelada transportada; ou pode levar lâmpadas, ganhando 
para isso R$ 160 por tonelada transportada. Você pode misturar os dois produtos dentro 
do seu baú, desde que respeite os limites de peso e volume dele. 
FIGURA 3 – Propostas de fretes
Fonte: Acervo Nead/Unoeste (2017).
Você pesquisou que cada quilo de bananas ocupa 1,2 litros de volume, já 
contando as caixas que as armazenam. Já as lâmpadas, ocupam um total de 2,4 litros por 
quilo do produto, pois têm uma densidade muito baixa. A carga máxima de bananas dispo-
níveis é de 10,5 toneladas, enquanto o máximo disponível de lâmpadas é de 18 toneladas.
1.2 Conceitos Básicos de Modelagem
O processo de modelagem pode ser comparado a uma arte, já que depende 
da experiência e criatividade daquele que está conduzindo. Entretanto, tentaremos es-
tabelecer um método que ajude você a enxergar como fazer esses modelos no mundo 
real. Começaremos identificando pontos comuns a todos os modelos. São eles:
15
Pare e Reflita
Antes de continuar a leitura, pense como você faria sua própria carga. Lembre-se de com-
parar ao final do capítulo com o que você aprendeu! 
Vamos identificar, na situação proposta, os elementos básicos que apren-
demos, transformando todas as unidades para toneladas (t). Para isso, veja a Tabela 1.
TABELA 1 - Identificação dos elementos básicos de modelagem no exemplo
Elemento Explicação No exemplo
Variáveis de decisão O que queremos descobrir, o que não sabemos, o desconhecido
Toneladas de bananas
Toneladas de lâmpadas
Parâmetros O que coletamos no mundo real, o que já sabemos, o conhecido
Receita com bananas (R$ 140/t)
Receita com lâmpadas (R$ 160/t)
Ocupação das bananas (1.200 L/t)
Ocupação das lâmpadas (2.400 L/t)
Demanda de bananas (10,5 t)
Demanda de lâmpadas (18 t)
Função objetivo O que queremos melhorar com a nossa solução
Maximizar (aumentar ao máximo) 
a receita total
Restrições O que nos impede de ter uma solução ainda melhor
Peso máximo carregado: 15 t
Volume máximo carregado: 28.800 L
Máximo de bananas: 10,5 t
Máximo de lâmpadas: 18 t
Fonte: Elaboração própria (2017).
1.3 Programação Linear (PL)
Uma vez entendido o problema, passamos à etapa de modelagem matemáti-
ca. Nosso primeiro passo será o de modelagem por meio de programação linear, ou seja, 
transformando os elementos que identificamos na seção anterior em funções lineares. 
De maneira simplificada, podemos caracterizar aqui uma função linear como combina-
ções de funções do primeiro grau com as variáveis de decisão. Isso implica que as vari-
áveis de decisão não podem se multiplicar e não podemter expoentes diferentes de 1.
Vamos utilizar o exemplo da seção “Conceitos Básicos de Modelagem” para 
sermos mais claros. Em primeiro lugar, temos que dar nomes às nossas variáveis de 
decisão, pois escreveremos todas as nossas funções utilizando-as. Vamos chamar aqui 
a quantidade de toneladas de bananas que iremos transportar de x1 e a quantidade de 
toneladas de lâmpadas que iremos transportar de x2.
Agora, vamos escrever nossa função objetivo! Identificamos que nosso obje-
tivo é maximizar a receita total com nosso caminhão de fretes. Isso significa que quere-
16
mos obter o máximo de receita com uma combinação de bananas e lâmpadas a serem 
transportadas. Como podemos traduzir o que iremos ganhar em termos matemáticos?
Ora, se ganhamos R$ 140 por tonelada transportada de banana, isso signifi-
ca que se transportarmos 1 tonelada, ganharemos R$ 140 (140 x 1); se transportarmos 
2 toneladas, ganharemos R$ 280 (140 x 2); se transportarmos 10 toneladas, ganhare-
mos R$ 1.400 (140 x 10). E se transportarmos x1 toneladas de bananas? Ganharemos 
R$ 140 vezes x1, ou seja, 140x1. Da mesma maneira, se transportarmos x2 toneladas de 
lâmpadas, ganharemos 160x2.
Assim, como queremos maximizar nossa receita total (RT) com a carga que 
escolhermos, temos a seguinte função objetivo:
maximizar RT=140x1+160x2
Pare e Reflita
Se você substituir valores em x1 e x2, irá obter a receita total com o frete daquela solução. 
Por exemplo: se eu resolver levar 5 toneladas de bananas e 6 toneladas de lâmpadas, mi-
nha receita total será de 140 x 5 + 160 x 6 = R$ 1.660,00.
Vamos passar agora a modelar nossas restrições.
Nossa primeira restrição era de peso: nosso caminhão só carrega 15 tonela-
das. Se x1 é a quantidade de toneladas de bananas e x2 é a quantidade de toneladas de 
lâmpadas, fica claro que a soma dessas duas variáveis não pode ultrapassar 15. Observe 
que o fato de não poder ultrapassar não significa que é obrigatório que a carga some 
15 toneladas. Pode haver uma solução boa que não lote o caminhão. Dessa forma, a 
soma das cargas de bananas e lâmpadas deve ser menor ou igual a 15. Assim, nossa 
restrição de peso é a seguinte:
(Restrição de peso): x1 + x2 ≤ 15
Passemos à restrição de volume. Sabemos, vendo nossos parâmetros, que 
cada tonelada de bananas ocupa 1.200 L. Ou seja, se levarmos 1 tonelada, ocuparemos 
1.200 L; se levarmos 3, ocuparemos 3.600 L (3 x 1.200); se levarmos 5, ocuparemos 
6.000 L (5 x 1.200) e se levarmos x1, ocuparemos 1.200x1 L em nosso caminhão. Da 
mesma forma, se levarmos x2 toneladas de lâmpadas, ocuparemos 2.400x2 L do cami-
nhão. Assim, se levarmos x1 toneladas de bananas e x2 toneladas de lâmpadas, juntas, 
o volume total ocupado é de 1.200x1 + 2.400x2. Nossa restrição é que esse volume não 
pode ultrapassar (deve ser menor ou igual a) 28.800 litros, ou seja:
17
(Restrição de volume): 1.200x1 + 2.400x2 ≤ 28.800
Para finalizar as restrições, temos as restrições de demanda, que são mais 
simples. O total de bananas levadas não pode ultrapassar 10,5 toneladas, pois não há 
demanda suficiente para isso. Ou seja, x1 não pode ultrapassar (deve ser menor ou 
igual a) 10,5 toneladas. Da mesma forma, a demanda de lâmpadas é de 18 toneladas, 
de forma que x2 não pode ultrapassar 18 toneladas. Assim:
(Restrição de demanda de bananas): x1 ≤ 10,5
(Restrição de demanda de lâmpadas): x2 ≤ 18
Um elemento final na programação linear é dizer que tipo de números as 
variáveis de decisão podem tomar: se podem ser número reais, inteiros, binários, etc. 
Nesse caso, o peso levado é uma variável contínua e pode tomar valores decimais (posso 
resolver levar 4,7 toneladas de bananas, por exemplo). Dessa forma, no exemplo, as 
variáveis são reais. Entretanto, só podem ter valores positivos.
Assim, nossa formulação matemática final para o problema em programação 
linear é:
max RT = 140x1 + 160x2
sujeito a x1 + x2 ≤ 15
 1.200x1 + 2.400x2 ≤ 28.800
 x1 ≤ 10,5
 x2 ≤ 18
com x1, x2 ∈ ℝ+
1.4 Soluções de Problema de Programação Linear
Agora que já formulamos o problema, passamos a uma próxima etapa de 
análise, que é das soluções. Antes de mais nada, temos que definir o que é uma solução 
para um problema. 
Uma solução é qualquer atribuição de valores às variáveis de decisão. Por 
exemplo: se eu disser que x1 vale 10 e x2 vale 20, essa é uma solução, porque atribuí 
valores às variáveis de decisão. Matematicamente, escrevemos essas soluções como um 
par ordenado, ou seja, (x1, x2) = (10, 20).
Para problemas de apenas duas variáveis de decisão, podemos representar 
uma solução como um ponto no plano cartesiano. Isso significa que cada ponto desse 
gráfico é um plano de frete, ou seja, uma possível configuração da carga a ser montada.
18
FIGURA 4 - Exemplo de solução retratada no plano cartesiano
Fonte: Elaboração própria (2017).
Note que, essa é uma solução qualquer; entretanto, ela desrespeita as res-
trições do nosso modelo, porque desrespeita a restrição de demanda de lâmpadas (que 
deve ser menor que 18), de peso (cuja soma deve ser menor do que 15 toneladas) e de 
volume (cuja soma deve ser menor do que 28.800 L).
Disso, decorre um segundo conceito que é o de solução viável, ou seja, 
qualquer solução (atribuição de valores) que respeite as restrições do problema. Uma 
solução viável para esse problema, por exemplo, é transportar 4 toneladas de bananas 
e 5 toneladas de lâmpadas, ou seja, (x1, x2) = (4, 5). 
FIGURA 5 - Exemplo de solução viável retratada no plano cartesiano
Fonte: Elaboração própria (2017).
19
Da mesma forma, não carregada NADA, ou seja, (x1, x2) = (0, 0), também 
é uma solução viável, pois respeita todas as restrições do problema (não ultrapassa 
o peso, nem o volume, nem as demandas). Isso não significa que é uma solução boa 
(neste caso, é péssima). Assim, evoluímos para o conceito de solução ótima, que é a 
solução que respeita as restrições e otimiza a função objetivo do problema.
Na próxima seção, veremos como encontramos a solução ótima para pro-
blemas de duas variáveis, através do método gráfico, e mais à frente veremos como 
encontrar para um problema qualquer, utilizando o Método Simplex.
Atenção
No mundo corporativo é muito comum utilizar a palavra “viável” como sinônimo de 
“economicamente boa”. Preste atenção que qualquer solução factível, ou seja, que 
atenda às restrições, é viável. Isso não significa que ela é boa, apenas que é possível!
1.5 Método Gráfico
Para problema de até duas variáveis de decisão, podemos utilizar o método 
gráfico para resolução. Embora poucos problemas no mundo real tenham apenas duas 
variáveis de decisão, trata-se de um método interessante em termos didáticos, para en-
tender a relação entre as restrições, soluções viáveis e solução ótima.
Como chamamos a atenção na seção anterior, vamos entender o plano car-
tesiano como um espaço de soluções, em que cada ponto é um par (x1, x2) com uma 
configuração do nosso caminhão.
Se quisermos retratar o conjunto de pontos que obedecem à restrição de 
peso (x1 + x2 ≤ 15), teremos que desenhar a reta (x1 + x2 = 15) e ressaltar a região de 
pontos abaixo dessa reta. Veja a Figura 6.
Para encontrar essa reta no plano cartesiano, temos que nos recordar como 
fazíamos isso nas aulas de matemática e geometria descritiva. Uma reta pode ser deter-
minada por dois pontos distintos dela quaisquer. Por uma questão de facilidade, costu-
mamos (mas não é obrigatório) localizar os pontos que encontram os eixos. Assim, na 
equação x1 + x2 = 15, quando x1 = 0, então x2 = 15. Da mesma forma, quando x2 = 0, 
então x1 = 15. Desse modo, se unirmos os pontos (0, 15) e (15, 0), encontramos a reta 
da restrição de peso.
20
FIGURA 6 - Restrição de peso retratada no plano cartesiano
Fonte: Elaboração própria (2017).
Seguindo o mesmo processo, podemos agora analisara restrição de volume 
(1.200x1 + 2.400x2 ≤ 28.800). Em primeiro lugar, temos que encontrar os pontos ex-
tremos dessa reta, onde ela cruza os eixos. Quando x1 = 0, então x2 = 12. Quando x2 = 
0, então x1 = 24. Assim, se unirmos os pontos (0, 12) e (24, 0), encontramos a reta da 
restrição de volume. Veja a Figura 7.
FIGURA 7 - Restrições de peso e volume retratadas no plano cartesiano
Fonte: Elaboração própria (2017).
21
Por analogia, desenhamos as últimas duas restrições de demanda e chega-
mos, por fim, à região viável do nosso problema. A região viável é, portanto, aquela que 
obedece todas às restrições simultaneamente. Qualquer ponto dentro dela representa 
soluções viáveis (isto é, possíveis) para o nosso problema de carregamento do caminhão.
FIGURA 8 - Restrições do problema e região viável
Fonte: Elaboração própria (2017).
Nosso próximo passo, agora, é encontrar a melhor solução dentro dessa re-
gião viável. Para definir melhor, temos que utilizar a função objetivo. No nosso problema, 
a função objetivo é RT = 140x1 + 160x2. 
Imagine que iremos desenhar em nosso gráfico todas as soluções que pos-
suem receita igual a um valor qualquer, por exemplo, R$ 1.120. Isso seria o equivalente 
a desenhar a reta 140x1 + 160x2 = 1.120. Se você fizer o mesmo processo com diversos 
valores, encontrará diversas retas paralelas, como ilustrado na Figura 9. Essas retas, 
também chamadas de isocurvas, são conjuntos de pontos (soluções) que possuem o 
mesmo valor de função objetivo, ou seja, dentro de cada reta, as soluções possuem 
valores iguais, isto é, são formas diferentes de chegar ao mesmo valor.
Qual é nosso objetivo? Obter o maior valor possível de receita, certo? Portan-
to, a minha solução ótima estará na última isocurva que ainda tiver algum ponto dentro 
da região viável. Traçando retas paralelas sucessivamente, chegamos à conclusão de 
que o ponto ótimo é no encontro das restrições de volume e peso. Isso acontece no par 
(x1, x2) = (6, 9). 
Desse modo, chegamos à nossa solução. Conforme você verá na Figura 9, a 
seguir, nosso motorista deve carregar 6 toneladas de bananas e 9 toneladas de lâmpa-
das, tendo com isso uma receita total de R$ 2.280,00. 
22
FIGURA 9 - Representação das isocurvas da função objetivo e o ponto ótimo
Fonte: Elaboração própria (2017).
1.6 Um Segundo Exemplo de Fixação
Para reforçarmos nosso raciocínio de construção de modelagem em progra-
mação linear, vamos trabalhar com um exemplo de problema de minimização.
Imagine que você é gestor de uma fábrica de rações e precisa encontrar a 
mistura ótima entre milho e farelo de soja. A tonelada de milho custa R$ 600,00 e possui 
80 kg de proteínas e 3.520 mega calorias (Mcal) de energia. Já o farelo de soja custa R$ 
1.200,00 por tonelada e possui 450 kg de proteínas, fornecendo 2.200 Mcal de energia.
Seu objetivo é formular uma batelada para atender um contrato de 10 tone-
ladas que tenha como resultado uma ração com 1.800 kg de proteínas e 25.000 Mcal, 
obtendo o mínimo custo possível.
E agora, como formulamos o problema? 
Passo 1: Definir variáveis de decisão
Meus valores desconhecidos são quanto colocar de milho e quanto colocar 
de soja na mistura para fazer 10 toneladas de ração. Vamos chamar a quantidade de 
toneladas de milho de x1 e a quantidade de toneladas de soja de x2.
Passo 2: Definir minha função objetivo em função das variáveis de 
decisão e dos parâmetros do problema
Meu objetivo é minimizar o custo total (CT) da ração. Esse custo é dado 
pelos gastos com milho e os gastos com soja. Para cada tonelada de milho, eu gasto R$ 
23
600,00, ou seja, meu gasto com milho é 600x1. Analogamente, meus gastos com farelo 
de soja são de 1.200x2. Assim, minha função objetivo será:
minimizar CT = 600x1 + 1.200x2
Passo 3: Definir minhas restrições
Em meu problema, tenho três restrições: a quantidade de proteína tem que 
ser superior (maior ou igual a) 1.800 kg; a quantidade de calorias deve ser superior 
a 7.000 Mcal; e a quantidade total produzida deve ser de 10 toneladas. Assim, minhas 
restrições serão:
(Proteínas) 80x1 + 450x2 ≥ 1.800
(Energia) 3.520x1 + 2.200x2 ≥ 25.000
(Total produzido) x1 + x2 ≥ 10
Passo 4: Definir que tipo de valor assumem as variáveis de decisão 
(domínio)
Nesse problema, novamente, os valores podem ser decimais, mas devem ser 
positivos (não podem ser negativos).
Assim, nosso modelo será:
min CT=600x1+ 1.200x2
sujeito a 80x1+ 450x2 ≥ 1.800 
 3.520x1+ 2.200x2 ≥ 25.000
 x1+ x2 ≥ 10
com x1, x2 ∈ ℝ+
Para resolver o problema pelo método gráfico, devemos desenhar as três 
restrições do problema, destacando a região viável (nesse caso, acima das retas) em 
comum das três. Veja a Figura 10, que mostra as equações representadas e a região 
viável destacada em verde. 
Feito esse processo, é hora de traçar isocurvas de custos de ração. Repare 
que, como esse é um problema de minimização, queremos encontrar o ponto da região 
viável que faz parte da isocurva de função objetivo de valor menor.
Nesse caso, esse ponto ocorre no encontro das restrições de total produzido 
e proteínas. Ou seja, o ponto ótimo é: (x1, x2) = (7,3; 2,7). Portanto, nossa mistura ótima 
será de 7,3 kg de milho com 2,7 kg de farelo de soja.
24
FIGURA 10 - Resolução gráfica do problema da mistura
Fonte: Elaboração própria (2017).
1.7 O Problema de Transporte
Vamos finalizar nosso capítulo com um terceiro exemplo de um problema 
clássico de Pesquisa Operacional: o problema de transporte!
Suponha que você é o gestor de logística de uma fábrica, que possui três 
fábricas e quatro centros de distribuição. Cada uma dessas fábricas possui uma capaci-
dade máxima de produção e cada centro de distribuição possui uma demanda mínima a 
ser atendida. Veja a Tabela 2 com estes dados:
TABELA 2 - Dados de demanda e capacidade dos centros de distribuição e fábricas (em unidades)
Centros de distribuição Demanda
A 45.000
B 20.000
C 30.000
D 30.000
Fábricas Capacidade
1 35.000
2 50.000
3 40.000
Fonte: Elaboração própria (2017).
Para levar produtos de um lugar para o outro, você tem custos distintos, veja 
na Tabela 3 o custo de levar cada unidade de uma fábrica para determinado centro de 
distribuição.
25
TABELA 3 - Custos de transporte das fábricas aos centros de distribuição
Centros de distribuição
A B C D
Fábricas
1 8 6 10 9
2 9 12 13 7
3 14 9 16 5
Fonte: Elaboração própria (2017).
E agora, como formulamos o problema?
Passo 1: Variáveis de decisão
Quero saber quanto levar de cada fábrica para cada centro de distribuição. 
Em outras palavras, minhas variáveis de decisão são quanto levar de 1 para A (x1A), 
quanto levar de 1 para B (x1B), e assim por diante, até quanto levar de 3 para D (x3D).
Passo 2: Função objetivo
Meu objetivo é minimizar o custo total de transporte. Esse custo é a soma 
dos custos de cada trecho, ou seja, quanto é o custo por unidade vezes o número de 
unidades levadas. Assim, minha função objetivo é:
minimizar CT = 8x1A + 6x1B + 10x1C + 9x1D +
 + 9x2A+ 12x2B + 13x2C + 7x2D +
 + 14x3A + 9x3B + 16x3C + 5x3D
Passo 3: Restrições
Aqui, minhas restrições são atender o mínimo de demanda dos centros de 
distribuição; e o máximo de oferta das plantas. Em outras palavras, tudo que sai de uma 
fábrica tem que ser menor ou igual à oferta dela. E tudo que chega de uma fábrica tem 
que ser maior ou igual à demanda dela.
26
Resumo
Neste capítulo, aprendemos a modelar matematicamente sistemas de produ-
ção por meio da Programação Linear.
Aprendemos que modelos são representações simplificadas da realidade, 
que fazemos com o objetivo de estudá-la. Com os resultados de um modelo, verificamos 
sua aderência à realidade para ajustá-lo ou implantá-lo na prática.Vimos que o processo de modelagem matemática de problemas de otimiza-
ção por Programação Linear pode ser feito percorrendo as seguintes etapas:
• Passo 1 - Definir variáveis de decisão: representar matematicamente as 
decisões a serem tomadas, ou seja, as variáveis de valores desconhecidos.
• Passo 2 - Definir a função objetivo: escrever por meio de uma função 
linear o que se quer otimizar com o modelo.
• Passo 3 - Definir as restrições: descrever por meio de inequações lineares 
o que limita as variáveis de decisão de tomarem valores quaisquer.
Também abordamos os conceitos das soluções, distinguindo uma solução 
qualquer, que é uma simples atribuição de valores às variáveis de decisão; de uma solu-
ção viável, que são valores que respeitam as restrições; de uma solução ótima, que são 
valores que respeitam as restrições e otimizam a função objetivo.
Por fim, aprendemos o método gráfico para solução de problemas de Pro-
gramação Linear para duas variáveis de decisão.
(Fábrica 1) x1A + x1B + x1C + x1D ≤ 35.000
(Fábrica 2) x2A + x2B + x2C + x2D ≤ 50.000
(Fábrica 3) x3A + x3B + x3C + x3D ≤ 40.000
(CD A) x1A + x2A + x3A ≥ 45.000
(CD B) x1B + x2B + x3B ≥ 20.000
(CD C) x1C + x2C + x3C ≥ 30.000
(CD D) x1D + x2D + x3D ≥ 30.000
27
Atividades
1. Uma fábrica de ligas metálicas tem que produzir 50 toneladas de um produto com 0 a 
10% de carbono; e 20% a 40% de silício em sua composição. Não há restrição quanto 
ao restante de sua composição. 
Para isso, essa empresa possui três matérias-primas: sucata, grafite e argila. A sucata 
custa R$ 35,00 por tonelada, possui 10% de carbono e 25% de silício, havendo 40 tone-
ladas em estoque. O grafite custa R$ 250,00 por tonelada, possui 90% de carbono e 0% 
de silício, havendo 25 toneladas em estoque. Já a argila custa R$ 150,00 por tonelada, 
possui 1% de carbono e 17% de silício, havendo 25 toneladas em estoque.
Formule um modelo de otimização linear que determine as quantidades a serem utiliza-
das de cada matéria-prima para otimizar o custo da liga, cumprindo as especificações 
técnicas e produtivas disponíveis. 
2. Reveja o exemplo do caminhão do livro-texto. Suponha que sejam oferecidos a você 
quatro serviços: (i) uma campanha de marketing para aumentar a demanda por bana-
nas; (ii) uma campanha de marketing para aumentar a demanda por lâmpadas; (iii) uma 
adaptação nos eixos para aumentar a capacidade de peso a ser transportado; (iv) uma 
expansão no baú para aumentar o volume de transporte. Quais deles são interessantes? 
Justifique com o resultado do método gráfico.
3. Resolva o seguinte problema pelo método gráfico.
max x1 + x2
sa 2x1 + x2 ≤ 48
 x1+ 2x2 ≤ 36
com x1, x2 ∈ ℝ+
4. No problema apresentado no exercício 3, dê três exemplos de soluções viáveis e três 
exemplos de três soluções não viáveis.
5. Você tem um sítio de 10 hectares e quer saber quanto plantar de milho ou de soja. 
Cada hectare de milho rende 100 sacas, requerendo 5 horas de trabalho por semana. 
Um hectare de soja rende 50 sacas e requer 8 horas de trabalho por semana. Cada saca 
de milho pode ser vendida a R$ 40, enquanto a saca de soja está sendo comercializada 
a R$ 70. Um financiamento adquirido previamente exige que pelo menos 2 hectares de 
milho sejam plantados. Sendo x1 o número de hectares de milho e x2 o número de hec-
tares de soja, determine a formulação que maximize a receita do sítio. 
28
Anotações
29
resolução de ProbleMas de otiMização
Capítulo 2
30
Agora que já aprendemos como modelar problemas reais por meio da Pro-
gramação Linear, nesta segunda etapa nosso objetivo é resolvê-los!
Já vimos anteriormente como resolver problemas pequenos, restritos a ape-
nas duas variáveis de decisão. Mas, no mundo real, temos problemas muito maiores do 
que esses e precisamos de ferramentas para enfrentá-los.
É para isto que aprenderemos agora a resolver problemas de Programação 
Linear pelo Método Simplex!
Além de aprender a resolver os problemas, também vamos entender os im-
pactos de mudanças nos parâmetros na resolução de problemas. Para isso, usaremos a 
técnica da Análise de Sensibilidade.
Introdução
2.1 A Forma Padrão de um Problema de Otimização 
Linear
Para podermos aplicar os métodos que serão ensinados neste capítulo, é 
importante que façamos a adoção de uma convenção padronizada de escrita dos proble-
mas, que chamaremos aqui de “forma padrão”.
A forma padrão de um problema possui as seguintes características:
min c1x1 + c2x2 + c3x3 + ... + cnxn
sujeito a a11x1 + a12x2 + a13x3 + ... + a1nxn= b1
 a21x1 + a22x2 + a23x3 + ... + a2nxn = b2
 …
 am1x1 + am2x2 + am3x3 + ... + amnxn = bm
com x1, x2, x3, …, xn ∈ ℝ+
As três características fundamentais da forma padrão estão destacadas em 
vermelho:
• A função objetivo deve ser de minimização.
• As restrições devem ser equações (igualdades) lineares.
• As variáveis de decisão devem ser não negativas.
Caso uma das três condições não seja cumprida, temos como transformar o 
problema na forma padrão. Veja na Tabela 4 como fazer tais transformações.
31
TABELA 4 - Transformações a serem feitas para a forma padrão
Característica Forma padrão Como transformar
Função objetivo de maximização A função objetivo deve ser de minimização
Maximizar uma função é o 
mesmo que minimizar seu 
negativo, ou seja, basta 
multiplicar a função objetivo 
por (-1). 
Exemplo:
max 4x1 + 3x2 + 2x3
Equivale a:
min -4x1 - 3x2 - 2x3
Restrições de ≤ As restrições devem ser igualdades (=)
Para transformar em igualda-
de, basta acrescentar uma va-
riável de folga (xk) que retrata 
quanto “falta” para atingir a 
igualdade. 
Exemplo:
8x1 - 2x2 + 5x3 ≤ 80
Equivale a:
8x1 - 2x2 + 5x3 + x4 = 80
Restrições de ≥ As restrições devem ser igualdades (=)
Para transformar em igualda-
de, basta subtrair uma variá-
vel de excesso (xk) que retrata 
quanto “sobra” para atingir a 
igualdade. 
Exemplo:
5x1 - 7x2 + 6x3 ≥ 100
Equivale a:
5x1 - 7x2 + 6x3 – x5 = 100
Variáveis irrestritas em sinal 
(pode ser negativa ou positiva)
Variáveis devem ser não 
negativas
Uma variável irrestrita deve 
ser substituída por duas 
variáveis, uma representan-
do a parte positiva e outra a 
negativa. 
Exemplo:
min 5x1 + 2x2 
s.a. x1 + x2 = 5 
com x1 ≥ 0, x2 livre
Na forma padrão, substituímos 
x2 por (x2 – x3)
min 5x1 + 2x2 – 2x3 
s.a. x1 + (x2 – x3) = 5 
com x1 ≥ 0, x2 ≥ 0 , x3 ≥ 0
Fonte: Elaboração própria (2017).
Tendo em vista a forma padrão, também podemos entender o problema 
de otimização linear como uma multiplicação de matrizes. A mesma representação que 
acabamos de ver pode ser escrita na forma matricial:
32
Chamamos o vetor (c1, c2, ..., cn) de vetor de custos; o vetor (x1, x2, ..., xn) de 
vetor de variáveis de decisão; a matriz (a11, ..., amn) de matriz tecnológica; e o vetor (b1, 
..., bm) de vetor de recursos.
Vamos voltar ao nosso exemplo do capítulo 1 para identificar esses elemen-
tos e colocar tudo na forma padrão! No caso do caminhão, vamos transformar nosso 
exemplo para a forma padrão. Veja no Quadro 1 as mudanças destacadas em vermelho.
Perceba que a função objetivo é alterada para se tornar uma função de mini-
mização. As restrições, que são todas do tipo ≤, têm uma variável de folga acrescentada 
a cada uma delas e transformadas em igualdades. Sendo assim, temos o problema na 
forma padrão.
QUADRO 1 - Transformação da forma original para a forma padrão
Forma original
max RT=140x1 + 160x2
sujeito a x1 + x2 ≤ 15
 1.200x1 + 2.400x2 ≤ 28.800
 x1 ≤ 10,5
 x2 ≤ 18
com x1, x2 ∈ ℝ+
Forma padrão
min -140x1 -160x2
s.a +x1 + x2 + x3 = 15
 1.200x1 + 2.400x2 + x4 = 28.800
 x1 + x5 = 10,5
 x2 + x6 = 18
com x1, x2, x3, x4, x5, x6 ∈ ℝ+
Fonte: Elaboração própria (2017).
33
Assim, nossos vetores da forma matricial são:
2.2 Método Simplex
Nesta seção, vamos aprender a resolver um problema qualquer de otimiza-
ção linear. Iremos continuar com o exemplo do caminhão para entendermos bem como 
o método funciona.
Vamos resumir o método nos passos que estão ilustrados no Quadro 2 e 
depois faremos cada um dos passos no nosso exemplo.
QUADRO 2 - Método Simplex
Passo 1: Coloque o problema na forma padrão.
Passo 2: Construa a forma matricial do problema.
Passo 3: Encontre uma solução básica viável e coloque o problema na forma canônica.
Passo 4:
a) verifique se a solução atual já é ótima;
b) escolha a variável não básica de menor custo para tornar-se básica;
c) escolha a variável básica de menor relação bj/aij positiva para tornar-se não básica;
d) atualize a tabela escalonando pelo método de Gauss-Jordan;
e) volte para o passo 4a até que a solução seja ótima. 
Fonte: Elaboração própria (2017).
Já fizemos os passos 1 e 2 na seção anterior, colocando nosso problema na 
forma padrão e matricial. Vamos para o passo 3: mas o que é uma solução básica vi-
ável? Sabemos que uma solução viável é aquela que atende a todas as restrições. Uma 
solução básica de um sistema com n variáveis e m equações (no nosso caso, um sistema 
de 6 variáveis com 4 equações), uma solução básica é aquela em que n – m variáveis 
são zeradas e m tem valor positivo (no nosso caso, 4 variáveis com valor positivo e 2 
zeradas. Chamamos as variáveis com valor zero de variáveis não básicas; e as variáveis 
com valores positivos de básicas.
Vamos dar um exemplo simples de solução básica viável em nosso proble-
ma: se fizermos x1 = 0 e x2 = 0, teremos nosso sistema de equações das restrições da 
seguinte forma:
34
Multiplicando as matrizes, temos:
1 x 0 + 1 x 0 + 1x3 + 0x4 + 0x5 + 0x6 = 15 ∴x3 = 15
1.200 x 0 + 2.400 x 0 + 0x3 + 1x4 + 0x5 + 0x6 = 28.800 ∴x4 = 28.800
1 x 0 + 0 x 0 + 0x3 + 0x4 + 1x5 + 0x6 = 10,5 ∴x5 = 10,5
0 x 0 + 1 x 0 + 0x3 + 0x4 + 0x5 + 1x6 = 18 ∴x6 = 18
Ou seja, nossa solução básica viável é x1=0, x2=0, x3=15, x4=28.800, 
x5=10,5 e x6=18.
Atenção
Em qualquer problema em que as restrições sejam do tipo ≤, uma solução básica viável 
simples é dar o valor zero a todas as variáveis originais do problema (nesse caso, x1 e x2). 
Repare que a solução encontrada corresponde, no método gráfico, ao pri-
meiro vértice do nosso plano de soluções viáveis (veja a Figura 11).
FIGURA 11 - Solução básica viável encontrada ilustrada no plano cartesiano
Fonte: Elaboração própria (2017).
35
Antes de realizar o passo 4, temos que lembrar que o método nos pede para 
colocar o problema na forma canônica. Para fazer isso, vamos introduzir a partir de agora 
a tabela do Simplex. Ela é formatada do seguinte modo:
Colocando em nosso problema, teremos o seguinte formato:
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha - 140 - 160 0 0 0 0 0
x3 1 1 1 0 0 0 15
x4 1.200 2.400 0 1 0 0 28.800
x5 1 0 0 0 1 0 10,5
x6 0 1 0 0 0 1 18
Na forma canônica, a linha dos custos tem que estar zerada para as variáveis 
básicas (nesse caso, x3, x4, x5 e x6). Além disso, em suas colunas correspondentes só 
pode haver o coeficiente 1 na linha correspondente e 0 nos demais. Repare que a tabela 
já se encontra na forma canônica. Exemplificamos isso com a cor verde na tabela.
Agora estamos prontos para ir para o passo 4!
No passo 4a, nosso método nos manda verificar se a solução atual já é óti-
ma. Quando a solução é ótima, todos os custos da primeira linha da Tabela do Simplex 
são positivos ou zero. Repare que temos dois coeficientes de custos negativos (-140 e 
-160). Portanto, a solução não é ótima!
No passo 4b, o método manda escolher a variável não básica de menor cus-
to para tornar-se básica. Lembre-se de que temos duas variáveis não básicas (aquelas 
que estão valendo zero na solução atual), que são x1 e x2. Lembre-se também de que o 
menor custo é aquele que é MAIS NEGATIVO. Nesse caso, o -160. Assim, a variável que 
se tornará básica será x2, pois tem o custo menor (mais negativo).
36
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha - 140 - 160 0 0 0 0 0
x3 1 1 1 0 0 0 15
x4 1.200 2.400 0 1 0 0 28.800
x5 1 0 0 0 1 0 10,5
x6 0 1 0 0 0 1 18
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha - 140 - 160 0 0 0 0 0
x3 1 1 1 0 0 0 15
x2 1.200 2.400 0 1 0 0 28.800
x5 1 0 0 0 1 0 10,5
x6 0 1 0 0 0 1 18
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha - 140 - 160 0 0 0 0 0
x3 1 1 1 0 0 0 15
x2 0.5 1 0 1 0 0 12
x5 1 0 0 0 1 0 10,5
x6 0 1 0 0 0 1 18
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha - 140 - 160 0 0 0 0 0
x3 1 1 1 0 0 0 15 15 ÷ 1 = 15
x4 1.200 2.400 0 1 0 0 28.800 28.800 ÷ 2.400 = 12
x5 1 0 0 0 1 0 10,5 10,5 ÷ 0 g∞
x6 0 1 0 0 0 1 18 18 ÷ 1 = 18
No passo 4c, o método nos pede para escolher a variável básica com a me-
nor relação bj/aij, veja a ilustração seguinte para entender o processo realizado.
Ou seja, no passo 4c pegamos o vetor de recursos atual e dividimos pela 
coluna que escolhemos no passo 4b. O menor resultado positivo (nesse caso, 12) é o 
escolhido. Importante ressaltar que resultados negativos são descartados.
Agora, vamos ter atenção com o passo mais trabalhoso do nosso método. No 
passo 4d temos que atualizar a matriz, trocando a variável que entra na base (x2) pela 
que sai da base (x4). Temos ainda que colocar a matriz na forma canônica novamente, 
utilizando o método de Gauss-Jordan.
Para fazer isso, primeiro divida toda a linha pelo pivô, que é a célula do en-
contro da linha e da coluna onde a troca ocorreu (pintada de amarelo na tabela anterior). 
Nesse caso, dividiremos a linha 3 inteira por 2.400.
37
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha -140+160x0,5 -160+160 0+0 0+160 0+0 0+0 0+12x160
x3 1-0,5 1-1 1-0 0-1 0-0 0-0 15-12
x2 0,5 1 0 1 0 0 12
x5 1 0 0 0 1 0 10,5
x6 0 – 0,5 1 – 1 0 – 0 0 – 1 0 – 0 1 – 0 18 – 12
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha –60 0 0 160 0 0 1920
x3 0,5 0 1 –1 0 0 3
x2 0,5 1 0 1 0 0 12
x5 1 0 0 0 1 0 10,5
x6 –0,5 0 0 –1 0 1 6
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha –60 0 0 160 0 0 1920
x3 0,5 0 1 –1 0 0 3 3 ÷ 0,5 = 6
x2 0,5 1 0 1 0 0 12 12 ÷ 0,5 = 24
x5 1 0 0 0 1 0 10,5 10,5 ÷ 1 = 10,5
x6 –0,5 0 0 –1 0 1 6 6 ÷ (-0,5) < 0
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha - 140 - 160 0 0 0 0 0 Somar a linha do pivô vezes 160
x3 1 1 1 0 0 0 15
Subtrair a linha do 
pivô vezes 1
x4 0,5 1 0 1 0 0 12
x5 1 0 0 0 1 0 10,5 Já está zerada
x6 0 1 0 0 0 1 18
Subtrair a linha do 
pivô vezes 1
Agora, temos que fazer todos os elementos da coluna dessa nova variável 
(x2) ficarem zerados por meio de operações de soma e multiplicação entre as linhas e a 
linha do pivô. Para isso, faremos as operações a seguir:
Veja as contas e os resultados:
Resultado (observe no destaque em amarelo que já temos a forma canônica):
Segunda rodada do Simplex: agora, temos que repetir todo esse proce-
dimento do passo 4 até que a solução seja ótima. Veja na tabela anterior, que a solução 
ainda não é ótima, porque existe um coeficiente negativo na linha dos custos (no caso, -60 
no custo da variável x1). Como é a única negativa que resta, será x1 que entrará na base.
Novamente, a escolha de quem sai será pelas divisões de bj/aij, veja na tabela.
38
O pivô, nesse caso, será o valor 0,5, que é o encontro da linha que sai com 
a coluna que entra. Dividindo a linha pelo pivô, temos:
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha –60 0 0 160 0 0 1920
x1 1 0 2 –2 0 0 6
x2 0,5 1 0 1 0 0 12
x5 1 0 0 0 1 0 10,5
x6 –0,5 0 0 –1 0 1 6
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha –60+60 0+0 0+120 160-120 0+0 0+0 1920 + 60x6
x1 1 0 2 –2 0 0 6
x2 0,5-0,5 1-0 0-1 1+1 0-0 0-0 12 - 0,5x6
x5 1-1 0-0 0-2 0+2 1-0 0-0 10,5 - 6
x6 –0,5+0,5 0+0 0+1 –1 - 1 0+0 1+06+0,5x6
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha 0 0 120 40 0 0 2.280
x1 1 0 2 –2 0 0 6
x2 0 1 –1 2 0 0 9
x5 0 0 –2 2 1 0 4,5
x6 0 0 1 –2 0 1 9
Para transformar para a forma canônica, faremos as seguintes operações:
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha –60 0 0 160 0 0 1920 Somar a linha do pivô vezes 60
x1 1 0 2 –2 0 0 6
x2 0,5 1 0 1 0 0 12
Subtrair a linha do 
pivô vezes 0,5
x5 1 0 0 0 1 0 10,5
Subtrair a linha do 
pivô vezes 1
x6 –0,5 0 0 –1 0 1 6
Somar a linha do 
pivô vezes 0,5
Veja as contas das operações:
Resultado:
Terceira rodada do Simplex: todos os coeficientes dos custos são posi-
tivos, de forma que chegamos à solução ótima. Veja que nossa solução ótima coincide 
com o que encontramos no método gráfico anteriormente, ou seja, x1 = 6 e x2 = 9.
39
Para entender o raciocínio por trás do Método Simplex, veja a Figura 12. A 
ideia do método é partir de um vértice da região viável (uma solução básica viável, que 
era a origem) e ir percorrendo os vértices até encontrar o ótimo do problema. Cada ro-
dada do Simplex corresponde a uma mudança de vértice. Observe a primeira seta, que 
sai do ponto (0, 0) e vai para o ponto (0, 12). É justamente a solução que encontramos 
após a primeira rodada do Simplex. Depois, na segunda seta, saímos de (0, 12) e vamos 
para (6, 9), que corresponde à segunda rodada do Simplex. Como a solução é ótima, 
paramos neste ponto. 
FIGURA 12 - Caminho percorrido pelo Método Simplex
Fonte: Elaboração própria (2017).
A diferença aqui é que podemos resolver problemas de quantas variáveis 
quisermos, ao contrário do método gráfico, que só se limita a duas variáveis.
2.3 Método das Duas Fases para Solução Inicial
No Método Simplex temos um passo muito importante que vimos de maneira 
muito breve: no passo 3, temos que encontrar uma solução básica viável inicial.
Quando temos um problema apenas com restrições de menor ou igual, a so-
lução inicial é bastante simples: basta atribuir o valor zero a todas as variáveis originais, 
pois sempre será uma solução viável.
Entretanto, em problemas nos quais existem restrições de maior ou igual, 
temos o problema de que essas soluções podem não ser viáveis.
Veja, por exemplo, o caso apresentado na seção “Um Segundo Exemplo de 
Fixação”. Vamos colocá-lo na forma padrão:
40
Forma original
min CT = 600x1 + 1.200x2
sujeito a 80x1 + 450x2 ≥ 1.800 
 3.520x1 + 2.200x2 ≥ 25.000
 x1 + x2 ≥ 10
com x1, x2 ∈ ℝ+
Forma padrão
min CT = 600x1 + 1.200x2
s.a 80x1 + 450x2 - x3 = 1.800 
 3.520x1 + 2.200x2 - x4 = 25.000
 x1 + x2 - x5 = 10
com x1, x2, x3, x4, x5 ∈ ℝ+
Nesse caso, se propusermos a solução x1 = 0 e x2 = 0, ela não respeitará as 
restrições. Veja, por exemplo, pela última restrição que x1 teria que ser -10, o que faria 
com que não fosse positivo.
Assim, precisamos de um método para obter uma solução básica viável ini-
cial. O método que aprenderemos aqui chama-se método das duas fases.
Sua ideia é muito simples e consiste em:
• Passo 1: acrescentar variáveis artificiais de folga em cada restrição de ≥ ou =
• Passo 2: minimizar a soma dessas variáveis artificiais.
• Passo 3: se chegar a uma solução em que a soma seja zero, você obteve 
uma solução básica viável para o problema original.
O método chama-se das duas fases porque essa seria a primeira fase do 
Simplex, para depois continuar com o método normal.
Façamos um exemplo com o problema proposto.
Passo 1: Acrescentar variáveis artificiais de folga
 80x1 + 450x2 - x3 + a1 = 1.800 
3.520x1 + 2.200x2 - x4 + a2 = 25.000
 x1 + x2 - x5 + a3 = 10
Passo 2: Minimizar a soma dessas variáveis
min a1 + a2 + a3
Colocando na Tabela do Simplex:
41
Básica x1 x2 x3 x4 x5 a1 a2 a3 Solução
1ª linha 0 0 0 0 0 1 1 1 0
a1 80 450 -1 0 0 1 0 0 1800
a2 3520 2200 0 -1 0 0 1 0 25.000
a3 1 1 0 0 -1 0 0 1 10
Básica x1 x2 x3 x4 x5 a1 a2 a3 Solução
1ª linha -3601 -2651 1 1 1 0 0 0 -26.810
a1 80 450 -1 0 0 1 0 0 1.800
a2 3520 2200 0 -1 0 0 1 0 25.000
a3 1 1 0 0 -1 0 0 1 10
Básica x1 x2 x3 x4 x5 a1 a2 a3 Solução
1ª linha 0 -400,375 1 -0,023 1 0 1,02 0 -1.234,7
a1 0 400 -1 0,023 0 1 -0,02 0 1.231,8
x1 1 0,625 0 -,0003 0 0 0,0003 0 7,1022
a3 0 0,375 0 0,0003 -1 0 -0,0003 1 2,898
Básica x1 x2 x3 x4 x5 a1 a2 a3 Solução
1ª linha 0 0 -0,001 -0,000263 1 1,001 1 0 -1,7429
x2 0 1 -0,0025 0 0 0,0025 0 0 3,0795
x1 1 0 0,00156 -000320 0 -0,00156 0,00032 0 5,1776
a3 0 0 0,0009 0,0002628 -1 -0,001 -0,000263 1 1,7429
Básica x1 x2 x3 x4 x5 a1 a2 a3 Solução
1ª linha 0 -400,375 1 -0,023 1 0 1,02 0 -1.234,7
a1 0 400 -1 0,023 0 1 -0,02 0 1.231,8
x1 1 0,625 0 -,0003 0 0 0,0003 0 7,1022
a3 0 0,375 0 0,0003 -1 0 -0,0003 1 2,898
Básica x1 x2 x3 x4 x5 a1 a2 a3 Solução
1ª linha -3601 -2651 1 1 1 0 0 0 -26.810
a1 80 450 -1 0 0 1 0 0 1.800
a2 3520 2200 0 -1 0 0 1 0 25.000
a3 1 1 0 0 -1 0 0 1 10
Colocando na forma canônica (linha da função objetivo subtraída das linhas 
1, 2 e 3):
Fazendo a primeira rodada do Simplex:
Segunda rodada do Simplex:
42
Terceira rodada do Simplex:
Básica x1 x2 x3 x4 x5 a1 a2 a3 Solução
1ª linha 0 0 -0,001 -0,000263 1 1,001 1 0 -1,7429
x2 0 1 -0,0025 0 0 0,0025 0 0 3,0795
x1 1 0 0,00156 -000320 0 -0,00156 0,00032 0 5,1776
a3 0 0 0,0009 0,0002628 -1 -0,001 -0,000263 1 1,7429
Básica x1 x2 x3 x4 x5 a1 a2 a3 Solução
1ª linha 0 0 0 0 0 1 1 1 0
x2 0 1 0 0 -2,67 0 0 2,67 7,7272
x1 1 0 0 0 1,67 0 0 -1,67 2,2727
x3 0 0 1 0,28 -1.066,67 -1 -0,28 1.066,7 1.859,09
Atenção
Talvez você encontre dificuldade de replicar os cálculos devidos às inúmeras casas deci-
mais do exemplo apresentado. Sugerimos que tente fazer com o auxílio de uma planilha 
eletrônica. 
Veja que não existem mais coeficientes negativos na linha dos custos da 
Tabela. Mas chegamos ao nosso objetivo: nenhuma variável artificial está mais na 
base. Isso significa que podemos utilizar como solução inicial: x1= 2,2727; x2= 7,7272; 
x3= 1.859,09.
2.4 Análise de Sensibilidade
Para finalizar nosso capítulo sobre soluções de problemas de otimização, 
vamos falar de análise de sensibilidade. Até agora, descrevemos todos os nossos 
problemas com dados coletados da realidade como se fossem um valor fixo, que não 
varia. Sabemos que, no mundo real, preços, quantidades e demandas podem variar com 
o tempo.
A análise de sensibilidade serve para obter conclusões a partir da resolução 
do problema sobre eventuais mudanças nos dados. Assim, podemos verificar como a 
solução ótima se comporta perante variações dos dados de entrada. Além disso, nos dá 
subsídios para negociar recursos e custos.
Para exemplificar nossa análise, vamos utilizar, novamente, nosso exemplo 
do caminhão. A seguir, está a última tabela da resolução do problema pelo Simplex.
43
Básica x1 x2 x3 x4 x5 x6 Solução
1ª linha 0 0 120 40 0 0 2.280
x1 1 0 2 –2 0 0 6
x2 0 1 –1 2 0 0 9
x5 0 0 –2 2 1 0 4,5
x6 0 0 1 –2 0 1 9
A linha de custos de uma solução do Simplex nos traz um vetor de custos 
modificado pelas rodadas do método. O valor abaixo de cada variável original do pro-
blema é chamado de custo reduzido (reduced cost) e o valor abaixo de cada variável 
adicionada das restrições é chamado de preço-sombra (shadow price).
Vamos analisar primeiro os preços-sombra. Na tabela anterior, verificamos 
que o preço sombra de x3 é 120, o preço-sombra de x4 é 40, enquanto o preço-sombra 
de x5 e x6 é zero (veja o vetor destacado em azul). O que isso significa?
Cada uma dessas variáveis está associada a uma restrição. Lembra-se de 
que adicionamos essa folga a cada uma das variáveis? Portanto, x3 está associada à res-trição de peso, x4 está associada à restrição de volume, x5 está associada à restrição de 
demanda de bananas e x6 está associada à restrição de demanda de lâmpadas.
Note que o preço-sombra da restrição de peso é 120. Isso significa que a 
cada tonelada a mais que eu puder carregar aumentaria o meu ótimo em R$ 120,00 (ou 
a cada tonelada a menos que eu puder carregar, ele diminuiria no mesmo valor).
Pare e Reflita
Pare e Reflita
Se um serralheiro oferecesse uma adaptação em seu baú para que ele suportasse 16 to-
neladas, qual seria seu novo ótimo? É preciso resolver tudo de novo ou podemos utilizar 
o preço-sombra? 
Olhando os preços-sombra desse problema, o que você preferiria: poder carregar 1 tone-
ladas a mais ou 1 L a mais? 
Da mesma forma, cada L a mais que o nosso caminhão puder carregar vai 
nos dar um incremento de R$ 40,00 na receita da carga. Veja como essa informação é 
útil para negociar recursos, pesquisar soluções e priorizar esforços, tudo sem ter que 
resolver o problema de novo.
44
Por que os preços-sombra das variáveis de demanda estão zerados? Eles 
estão assim porque se houvesse mais demanda, nada mudaria na formação da nossa 
carga ótima. Veja que na solução final existe uma folga de demanda de bananas de 4,5 
toneladas (x5 = 4,5 toneladas). Da mesma forma, existe uma folga de demanda de 9 to-
neladas de lâmpadas (x6 = 9 toneladas). Isso é coerente com os dados do problema, pois 
havia mais demanda do que foi usado. E é por isso que de nada adianta mais demanda!
Para analisar os custos reduzidos, vamos alterar um pouco nosso proble-
ma original. Imagine que tivéssemos um terceiro produto a ser carregado pelo nosso 
caminhão: chapas de isopor. Suponha que cada tonelada de isopor ocupe 5.000 L e nos 
dê uma receita de R$ 50,00. Suponha também que não haja restrição de demanda. Se 
resolvermos nosso novo problema pelo Simplex, teremos a seguinte tabela final:
Básica x1 x2 x3 x4 x5 x6 x7 Solução
1ª linha 0 0 153,33 120 0,1 0 0 2.280
x1 1 0 0 0 0 0 0 6
x2 0 1 0 0 0 0 0 9
x5 0 0 2 –2 0 1 0 4,5
x6 0 0 -3 1 0 0 1 9
Note que, embora tenha a nova opção, a solução ótima continua sendo a 
mesma: levar 6 toneladas de bananas e 9 toneladas de lâmpadas. Isso porque não está 
sendo compensatório levar placas de isopor. Mas, se o vendedor de isopor insistisse, por 
que preço ele passaria a ser interessante?
É essa informação que o custo reduzido nos dá! Veja que o custo reduzido 
das placas de isopor é de R$ 153,33. Isso significa que o preço do frete das placas de 
isopor teria que aumentar em R$ 153,33 para compensar levá-las. Em termos práticos, 
ao recusar a carga do isopor, se o contratante insistisse em negociar o preço, você só 
deveria aceitar o frete se o preço passasse a ser acima de 50 + 153,33 = R$ 200,33.
O custo reduzido das variáveis básicas é sempre zero, pois já está compen-
sando levá-las.
Pare e Reflita
No problema de mistura de rações, no mundo real, existem diversos produtos candidatos 
a serem misturados. O que significaria o custo-reduzido de cada alternativa? E o preço 
sombra de cada recurso?
45
Resumo
O objetivo deste capítulo era aprender um método que solucionasse qual-
quer problema de Programação Linear, com a quantidade de variáveis que quiséssemos. 
O método gráfico só nos permitia resolver até duas variáveis de decisão.
Aprendemos, então, o Método Simplex. Para utilizá-lo, temos que percorrer 
os seguintes passos:
1. Colocar o problema na forma padrão.
2. Construir a forma matricial do problema.
3. Encontrar uma solução básica viável e colocar o problema na forma canônica.
4. Rodadas do Simplex:
a. verificar se a solução atual já é ótima;
b. escolher a variável não básica de menor custo para tornar-se básica;
c. escolher a variável básica de menor relação bj/aij positiva para tornar-se 
não básica;
d. atualizar a tabela escalonando pelo método de Gauss-Jordan;
e. voltar para o passo 4a até que a solução seja ótima.
Aprendemos também que a obtenção de uma solução básica viável no passo 
3 nem sempre é simples e, para isso, temos o método das duas fases para nos auxiliar.
Por fim, verificamos como podemos utilizar as informações na Tabela final 
do Simplex para nos auxiliar a analisar o contexto dos dados coletados e suas variações.
Atividades
1. Resolva o seguinte modelo pelo Método Simplex:
max x1 + x2
sa 2x1 + x2 ≤ 48
 x1 + 2x2 ≤ 36
com x1, x2 ∈ ℝ+
2. Uma empresa de peças usinadas possui três produtos: eixos, discos de freio e man-
cais. Os eixos são vendidos a R$ 60, requerendo 8 kg de ferro, 4 horas de usinagem e 
2 horas de acabamento. Os discos de freio são vendidos a R$ 30, requerendo 6 kg de 
ferro, 2 horas de usinagem e 1,5 hora de acabamento. Já os mancais são vendidos a R$ 
20, requerendo 1 kg de ferro, 1,5 hora de usinagem e 0,5 hora de acabamento. Havendo 
48 kg de ferro, 20 horas de usinagem e 8 horas de acabamento, formule o modelo que 
maximiza a receita da empresa e resolva pelo Método Simplex.
46
Anotações
3. Resolva pelo Método Simplex:
max 2x1 - x2 + x3
sa 3x1 + x2 + x3 ≤ 60
 x1 - x2 + 2x3 ≤ 10
 x1 + x2 - x3 ≤ 20
com x1, x2, x3 ∈ℝ+
4. Resolva pelo Método Simplex, utilizando o método das duas fases para solução inicial:
max 3x1 + 2x2
sa x1 + 22 ≤ 12
 x1 + x2 ≥ 5
com x1, x2 ∈ ℝ+
5. No exercício 2, indique os custos reduzidos e os preços-sombra e interprete-os 
economicamente.
47
ProbleMas coM Variabilidade
Capítulo 3
48
Anteriormente, aprendemos a modelar e resolver problemas de Programação 
Linear. Embora a análise de sensibilidade tenha nos fornecido algumas ferramentas para 
analisar mudanças de comportamentos nos dados, no geral tratamos o mundo de maneira 
determinística, isto é, como se os dados fossem todos previamente dados e constantes.
Entretanto, sabemos que o mundo, na verdade, apresenta diversas variações. 
A demanda oscila, os fornecedores atrasam, os preços variam, as produtividades mudam 
dia a dia, enfim, existe uma infinidade de efeitos aleatórios que fazem com que nossos 
dados não sejam estáticos. Eles são, na realidade, probabilísticos, ou seja, nós sabemos 
parte do comportamento deles (média, variações comuns, etc.), mas não exatamente 
como eles são.
Para dar esse devido tratamento aos dados, a Pesquisa Operacional conta com 
diversas técnicas de modelagem que podem ser utilizadas. Neste capítulo, exploraremos 
os campos da teoria de filas e da simulação.
A primeira se dedica a analisar processos de filas, ou seja, aqueles sistemas 
em que existe uma espera associada às variabilidades de chegadas e atendimentos.
Já a simulação, de maneira bastante simples, pode ser definida como uma imi-
tação da realidade com o intuito de retratar sistemas complexos, em que temos dificuldade 
de analisar por meio de sistemas lineares ou mesmo outros frameworks típicos.
Portanto, neste capítulo, iremos nos dedicar menos à otimização e mais à ca-
racterização desses sistemas para seu entendimento.
Introdução
3.1 Teoria de Filas
Como dito anteriormente, a teoria de filas consiste de uma modelagem de 
processos em que existe uma espera associada às variabilidades de chegadas e aten-
dimentos. É fácil entender o que é uma fila, já que nós conhecemos diversas delas em 
nosso cotidiano: na padaria, no banco, no supermercado em centrais de atendimento 
telefônico, no correio ou no médico, nós somos atores de diversos processos de fila.
49
Pare e Reflita
A maior parte de nós é usuário de sistemas de filas, tendo sempre uma perspectiva nega-
tiva desses sistemas. Ao longo deste capítulo, temos que tomar a posição dos gestores das 
filas, ou seja, responsáveis por equilibrar custos adequados e um bom atendimento. 
Já que todos nós temos esse conhecimento tácito do que é uma fila, vamos 
tentar definir mais formalmente o que é o sistema com fila.
FIGURA 13 - Ilustração de um sistema com fila
Fonte: Elaboração própria (2017).
Um sistemade filas é definido pelos seguintes elementos:
• Processo de chegadas: caracteriza como é o comportamento de entrada 
de usuários no sistema, ou seja, o fluxo de novos clientes a serem atendidos. Pode ser 
caracterizado pelo tempo entre chegadas sucessivas de usuários. Por exemplo: podemos 
pensar que em um determinado banco, a taxa de chegadas de usuários é de 1 pessoa a 
cada 30 segundos.
• Processo de atendimento ou serviço: caracteriza como é o tempo de 
atendimento ao usuário, ou seja, quanto tempo cada cliente gasta sendo efetivamente 
atendido, não contando o tempo de espera em fila. Por exemplo: podemos imaginar que 
em um certo salão de beleza, um cliente é atendido a cada 2 horas em um determinado 
posto de atendimento.
• Postos de atendimento: são os locais onde os clientes são efetivamente 
servidos, ou seja, onde é feito o processo de atendimento. Existem sistemas de filas com 
postos únicos ou postos em paralelo.
• Capacidade do sistema: trata-se do número total de usuários que o 
sistema comporta, ou seja, quantas pessoas podem estar em um dado momento em 
50
atendimento ou em fila. Existem filas que podem ser consideradas infinitas, dado que 
a capacidade do sistema é muito maior do que o número de usuários que costumam 
frequentá-las. Por exemplo: a fila para comprar ingressos para um show pode ser consi-
derada infinita, já que não existe uma limitação física que impede novos clientes quando 
está muito grande.
• Disciplina da fila: é o conceito que se relaciona à forma como os usuários 
são atendidos, ou seja, a ordem como isto acontece. Em nosso cotidiano, estamos acos-
tumados com as filas FIFO (first in, first out, isto é, o primeiro que chega é o primeiro 
que sai). Sendo assim, a disciplina da fila é dada pela ordem de chegada. Embora seja 
um sistema igualitário, nem sempre é o mais eficiente para o sistema como um todo. 
Existem diversas variações dos sistemas de filas, por exemplo: as prioridades a idosos, 
ou gestantes, ou doadores de sangue. Também podemos pensar, no caso de filas de or-
dens de serviço em uma máquina, em outras disciplinas de fila, como o prazo mais curto 
(conhecido como EDD, do inglês earliest due date) ou o menor tempo de processamento 
(também conhecido como SPT, do inglês shortest processing time).
Pare e Reflita
Pense na última fila que você pegou e caracterize-a. Como são as chegadas dos clientes? 
Como é o atendimento? Como é a disciplina da fila? Quantos são os postos de atendi-
mentos? Qual a capacidade do sistema? 
3.2 Notação de Kendall-Lee
As notações são formas de universalizar a caracterização de um sistema, 
de modo que qualquer estudioso ou gerente que conheça a notação entenda como ele 
funciona. A notação mais conhecida e adotada para sistemas de filas é chamada de 
Kendall-Lee, que possui o seguinte formato:
A/B/m/C/K/N
Sendo:
A = distribuição de probabilidade do processo de chegada
B = distribuição de probabilidade do processo de atendimento
m = número de servidores em paralelo
C = disciplina da fila
K = número máximo de usuários no sistema (capacidade)
N = tamanho da população de onde provém os usuários
51
Por exemplo: uma fila M/M/1/FIFO/∞/∞, que é o estudo mais comum, sig-
nifica que o processo de chegada é uma função exponencial, o processo de saída é 
uma função exponencial também, existe apenas um servidor, o primeiro que chega é o 
primeiro a ser atendido, a capacidade do sistema é infinita e a população de possíveis 
usuários também é infinita.
3.2.1 Medidas de Desempenho em um Sistema de Filas
Ao analisar um sistema de filas, temos alguns objetivos a serem atingidos 
e, para isso, existem algumas medidas clássicas de desempenho a serem mensuradas.
As medidas de desempenho mais comuns são:
• Número médio de usuários na fila (Lq) e no sistema (L).
• Tempo médio de espera de um usuário na fila (Wq) e no sistema (W).
• Probabilidade de ter, no máximo, um número n de usuário no sistema 
(P(N≤n)).
• Probabilidade de um usuário aguardar mais do que um certo tempo t em 
fila (P(Tq > t)).
3.2.2 Um Exemplo de Modelo: M/M/1/FIFO/∞/∞
Como dito anteriormente, uma fila M/M/1/FIFO/∞/∞ é um modelo de comple-
xidade matemática razoável e que atende a diversas situações práticas a serem analisadas.
Os processos de chegada e atendimento são exponenciais (M) e caracteriza-
mos as taxas de chegada e atendimento (em termos de clientes por unidade de tempo) 
pelas letras gregas λ e μ, respectivamente.
Por exemplo: imagine um processo de filas em que chegam clientes seguin-
do uma distribuição exponencial com média de 1,28 cliente por minuto (ou seja, um 
cliente chega, em média, a cada 76,8 segundos) e o tempo de atendimento também é 
uma exponencial de média 1,6 clientes por minuto (ou seja, o cliente é atendido, em 
média, a cada 96 segundos). Nesse caso λ = 0,5 cliente/minuto e μ = 0,8 cliente/minuto.
No caso de filas desse tipo, temos algumas medidas de desempenho de fácil 
cálculo. Vamos exemplificar com os dados que acabamos de mencionar. Importante res-
saltar que tais relações somente são válidas para taxas de atendimento maiores do que 
de chegadas (caso contrário, o sistema tende a uma fila infinita):
• Taxa de ocupação ou utilização do sistema: 
52
• Número médio de clientes no sistema:
• Número médio de clientes na fila:
• Probabilidade de o sistema estar vazio:
P0 = 1 - ρ = 1 - 0,8 = 0,2 =20%
• Tempo médio de espera de qualquer cliente na fila: 
• Tempo médio de permanência no sistema:
• Probabilidade de um cliente ter que esperar por mais de 5 minutos:
P(Tq > 5) = ρe
-(μ-λ)t = 0,8e-(1,6-1,28)×5 = 0,1615 = 16,15%
• Probabilidade de haver 10 clientes no sistema:
P(N >10) = ρN = 0,810 = 0,1074 = 10,74%
Pare e Reflita
Que tal um exercício prático? Meça a média de chegadas em um consultório médico (que 
é um sistema com um único posto) e a média dos tempos de atendimento. Faça os cálculos 
anteriores e veja se correspondem à realidade. 
3.3 Noções de Simulação
Ao contrário da teoria de filas e outras técnicas de análise de sistemas pro-
babilísticos, que analisam situações que se adequam a determinadas premissas com 
fórmulas analíticas para o desempenho do sistema, a simulação é uma técnica mais 
versátil, utilizada para analisar sistemas reais de difícil modelagem.
53
Por meio da simulação, temos a oportunidade de retratar situações comple-
xas. Para fazer isso, podemos utilizar softwares específicos de simulação como ProMo-
delR e ArenaR ou mesmo utilizar linguagens de programação genéricas para programar 
as condições que queremos.
A ideia por trás da simulação é bastante simples: colocar em um sistema 
computacional as lógicas que regem um determinado fenômeno e coletar as respostas 
de como esse sistema se comportaria em tais condições.
Um exemplo de estudo computacional com simulação pode ser visto na Fi-
gura 14, retirada do artigo de Correia et al. (2012), que utilizaram a técnica para simular 
o desempenho operacional de um terminal de integração de ônibus urbanos em João 
Pessoa (PB).
FIGURA 14 - Ilustração de um diagrama de blocos para simulação
Fonte: Correia et al. (2012).
Muitos estudiosos caracterizam a simulação como um “último recurso” para 
estudar sistemas complexos, dado que existe uma complexidade de construção do mo-
delo e ele só pode ser utilizado para aquela situação específica. Por outro lado, como já 
dito, a simulação nos dá a possibilidade de estudar problemas que são impossíveis ou 
muito difíceis de serem tratados analiticamente.
3.3.1 Classificação dos Sistemas de Simulação
Os modelos de simulação podem ser classificados de acordo com diversos 
critérios.
Segundo a representação do sistema:
• Modelos estáticos: não existe a utilização da variável tempo, ou seja, o 
sistema é representado num determinado instante.
54
• Modelos dinâmicos: a evolução do tempo é importante na simulação, 
portanto esse fator é representado como uma das suas variáveis.
Segundo a caracterização do comportamento das entidades envolvidas:
• Modelos determinísticos:os valores dos dados de entrada são conhe-
cidos e determinados.
• Modelos probabilísticos: os valores dos dados de entrada são estimados 
e seguem distribuições estatísticas, com o componente de aleatoriedade associado.
Segundo a forma de tratar o tempo:
• Modelos discretos: o estado do sistema (ou seja, suas mudanças simu-
ladas) varia em instantes determinados, ou seja, de tempo em tempo. 
• Modelos contínuos: o estado do sistema pode variar continuamente, o 
tempo todo.
Observe que os sistemas vistos na teoria de filas são casos particulares da 
simulação. Por exemplo: uma fila M/M/1/FIFO/∞/∞ poderia ser retratada por um mo-
delo de simulação dinâmico, probabilístico e discreto. Seria dinâmico porque o tempo é 
importante em sua análise, pois os eventos de chegadas e atendimentos vão acontecen-
do continuamente. Seria probabilístico porque os eventos de chegadas e atendimentos 
seguem uma distribuição exponencial, com seu componente aleatório associado. E, por 
fim, seria discreto porque os eventos acontecem de tempo em tempo e o estado do sis-
tema de fila só se altera quando alguém entra ou sai do sistema.
3.3.2 Simulação Discreta ou Simulação por Eventos Discretos
A forma mais estudada e utilizada de simulação é a simulação discreta ou por 
eventos discretos, devido a sua grande aplicabilidade e versatilidade. Quando falamos 
em simulação discreta, estamos falando de modelos discretos, dinâmicos e probabilís-
ticos, seguindo a classificação da seção “Um Exemplo de Modelo: M/M/1/FIFO/∞/∞”.
Algumas definições são importantes para este tipo de caracterização:
a) Eventos: qualquer ocorrência em um determinado momento e que provo-
ca uma mudança do estado do sistema em estudo. Por exemplo: chegada de um cliente, 
atendimento de um cliente, produção de uma peça, realização de uma venda, etc.
b) Entidades: são os “personagens” do sistema simulado, ou seja, os par-
ticipantes da simulação cujas características se quer analisar. Por exemplo: em um siste-
ma de filas, as entidades são os clientes e os postos de atendimento. Em uma simulação 
de uma fábrica, as entidades podem ser as máquinas, as ordens de produção, os traba-
lhadores, o estoque de matérias-primas ou o estoque de produtos acabados.
55
c) Processos: são transformações às quais as entidades são submetidas 
ao longo da simulação. No exemplo do sistema de filas, são processos as chegadas e os 
atendimentos; no caso da fábrica, são processos a chegada de um pedido ou a fabrica-
ção de uma ordem.
d) Variáveis de estado: são características ou atributos das entidades que 
são importantes de se medir ou registrar para verificar como evolui a simulação. Por 
exemplo: em um sistema de filas, são variáveis de estado se o posto de atendimento 
está vazio ou ocupado, a quantidade de clientes na fila, o tempo de atendimento de 
cada cliente. Já na simulação de uma fábrica, são variáveis de estado se a máquina está 
ocupada ou vazia, quantas ordens estão esperando para ser fabricadas, quanto há de 
matéria-prima no estoque, quanto há estocado dos produtos vendidos, etc.
3.3.3 Passos de um Estudo de Simulação
Não existe um método fechado e pronto para construir um sistema de si-
mulação. Entretanto, vamos propor aqui uma sequência de passos lógicos para ajudar a 
construir o raciocínio associado a um estudo desse tipo.
FIGURA 15 - Ilustração de um diagrama de blocos para simulação
Fonte: Elaboração própria (2017).
56
Passo 1: Entender o objeto de estudo e todas as suas entidades, 
estados possíveis e regras lógicas
Aqui é importante formularmos muito bem o problema que queremos ana-
lisar, bem como nossos objetivos com a simulação. Importante listar as respostas que 
esperamos alcançar, os critérios de avaliação do sistema, como cada entidade e cada 
processo funcionam e quais são as limitações do nosso modelo.
Passo 2: Coletar dados sobre o objeto de estudo
Por meio da observação, experiência e apontamentos/dados históricos, é 
possível verificar o padrão de funcionamento das entidades e dos processos do nosso 
sistema. Por exemplo: podemos cronometrar o tempo de produção de uma máquina 
para encontrar o tempo médio, o tempo máximo e o tempo mínimo de processamento 
das peças ali. É importante também coletar as informações de como o sistema se com-
porta de acordo com suas variáveis de estado. Por exemplo: se um posto de atendimen-
to finaliza um cliente, somente entrará um novo cliente se houver 1 ou mais esperando 
na fila (que é uma variável de estado). Também é essencial coletar dados de custos de 
cada um dos processos e das entidades, pois, no final do modelo feito, é possível com-
parar diversas formas diferentes de se trabalhar.
Passo 3: Criar um modelo que represente a realidade e testar com 
exemplos simples
O modelo, neste caso, é a representação gráfica das interações entre en-
tidades, eventos, processos e variáveis de estado. Podem ser utilizados fluxogramas, 
algoritmos ou qualquer representação lógica que permita o entendimento para posterior 
codificação computacional. Via de regra, inicia-se com um modelo bastante simplificado 
para posterior detalhamento. É sempre muito interessante tentar fazer um exemplo sim-
ples, talvez até mesmo manualmente, para ter certeza de que as relações lógicas estão 
todas contempladas. Aqui é importante definir se o modelo é discreto ou contínuo, está-
tico ou dinâmico, probabilístico ou determinístico.
Passo 4: Construir uma representação computacional do modelo
Para utilizar a técnica de simulação, é preciso codificar o modelo em uma 
linguagem apropriada. Como já dito, existem pacotes prontos dedicados à simulação, e 
existe também a possibilidade de codificar em uma linguagem de programação genérica.
Passo 5: Testar o modelo computacional com os mesmos exemplos 
simples e verificar se a representação é válida com as premissas delimitadas
Basta validar com parâmetros de entrada bastante simples se os resultados 
lógicos esperados estão ocorrendo. É interessante também testar situações extremas 
para verificar se o código está tratando todas as possibilidades.
57
Passo 6: Planejar os cenários a serem analisados com os modelos
O conjunto de experimentos a ser analisado deve ser feito de acordo com 
os fatores (dados de entrada) que se quer testar, quais os valores a serem analisados e 
quais as respostas esperadas.
Passo 7: Rodar o modelo de simulação para coletar os dados
Passo 8: Analisar os resultados e utilizar como suporte para a to-
mada de decisão
Com os resultados em mãos, é possível fazer inferências sobre o sistema es-
tudado e a melhor forma de agir com ele. Quando se trata de um modelo probabilístico, 
é interessante obter a média e o desvio dos resultados também para analisar o risco de 
cada alternativa.
3.3.4 Um Exemplo: Simulando uma Linha de Montagem
Um sistema complexo suficiente para ser simulado pode ser um processo de 
produção em linha, como uma linha de montagem com diversas estações.
Vamos planejar um modelo de simulação para um exemplo com três má-
quinas que fazem processos sucessivos: A, B e C. As matérias-primas (peças a serem 
montadas) todas entram na estação A e são pré-montadas; na estação B é feito o aperto 
dos encaixes; e na estação C são feitos os testes em uma máquina que opera com duas 
unidades de cada vez. A estação A começa um novo produto sempre que uma unidade 
do estoque final é retirada (vendida), ou seja, trabalha-se em programação puxada.
• Entidades: máquinas A, B e C, matérias-primas, produtos finais, fila de A, 
fila de B e fila de C.
• Eventos: retirada de produto em estoque, entrada na fila A; processamen-
to em A, entrada na fila B; processamento em B, entrada na fila C, processamento em C.
• Processos: processamento em A, B e C.
• Variáveis de estado: quantidade de matérias-primas, quantidade em 
estoque final, quantidade na fila de A, B e C; preenchimento das filas A, B e C.
FIGURA 16 - Ilustração conceitual do processo
Fonte: Elaboração própria (2017).
58
Coleta de dados:
• Verificar a médiado tempo entre retiradas do estoque de PA.
• Média do tempo de processamento em A, B e C.
• Demais processos: consequências dos quatro listados anteriormente:
	 • matéria-prima sai do estoque quando ocorre uma retirada do estoque 
de produto acabado e vai para a fila de A;
 • ordem espera na fila de A até que a máquina A esteja vazia;
 • ordem vai para a fila de B quando termina o processamento em A;
 • ordem espera na fila B até que a máquina B esteja vazia;
 • ordem vai para a fila de C quando termina o processamento em B;
 • ordem espera na fila C até que a máquina C esteja vazia e exista outra 
ordem para ser feita conjuntamente;
 • estoque de produto acabado aumenta assim que termina o processa-
mento em C.
Plano experimental:
• Testar a quantidade média em estoque, o tempo de espera dos clientes e 
a quantidade média de matérias-primas para:
 • 1 máquina A, 1 máquina B e 1 máquina C;
 • 2 máquinas A, 1 máquina B e 1 máquina C;
 • 1 máquina A, 2 máquinas B e 1 máquina C;
 • 1 máquina A, 1 máquina B e 2 máquinas C;
 • 2 máquinas A, 2 máquinas B e 1 máquina C;
 • 2 máquinas A, 1 máquina B e 2 máquinas C;
 • 1 máquina A, 2 máquinas B e 2 máquinas C;
 • 2 máquinas A, 2 máquinas B e 2 máquinas C;
 • com um aumento de demanda de 20%;
 • com a diminuição de demanda de 25%.
Resumo
Neste capítulo, vimos algumas das técnicas possíveis para lidar com proble-
ma probabilísticos: teoria de filas e simulação.
Teoria de filas são aplicadas a problemas em que haja formação de espera 
para um atendimento. Vimos que são elementos importantes das filas: processos de 
chegadas; processo de atendimento ou serviço; número de postos de atendimento; ca-
pacidade do sistema e disciplina da fila.
Verificamos que esses parâmetros são utilizados na notação de Kendall-Lee 
para unificar a caracterização de uma fila. Também foram passadas algumas medidas de 
desempenho típicas dos sistemas de filas, como número médio de usuários na fila (Lq) 
59
e no sistema (L); tempo médio de espera de um usuário na fila (Wq) e no sistema (W); 
probabilidade de um dado número de usuários; e probabilidade de um usuário aguardar 
mais do que um certo tempo.
Foi mostrado que existem casos especiais, como a fila M/M/1/FIFO/∞/∞, em 
que há soluções analíticas simples para essas medidas de desempenho.
Já a simulação é uma técnica mais versátil, utilizada para analisar sistemas 
reais de difícil modelagem. Vimos como classificar os modelos de simulação (estáticos x 
dinâmicos; determinísticos x probabilísticos; discretos x contínuos). Além disso, elenca-
mos quais os elementos importantes em um modelo de simulação: eventos, entidades, 
processos e variáveis de estado.
Por fim, descrevemos os passos típicos de um projeto de simulação.
Atividades
1. Explique cada um dos termos da notação de Kendall-Lee no exemplo de uma fila 
M/M/1/FIFO/∞/∞.
2. Em uma fila M/M/1/FIFO/∞/∞ , com taxa de chegada de 1 cliente por minuto e de 
atendimento de 1,5 cliente por minuto, calcule a taxa de ocupação do sistema, o número 
médio de clientes no sistema e o número médio de clientes na fila.
3. Ainda no exemplo anterior, calcule a probabilidade do sistema estar vazio; e a proba-
bilidade de um cliente ter que esperar mais do que 2 minutos.
4. Ainda no exemplo anterior, calcule o tempo médio de permanência de um cliente na 
fila e no sistema.
5. Explique as classificações de um modelo de simulação segundo sua representação, a 
caracterização do comportamento das entidades envolvidas e a forma de tratar o tempo.
60
Referências
ANDRADE, E. L. de. Introdução à Pesquisa Operacional: métodos e modelos para 
a análise de decisão. 2. ed. Rio de Janeiro: LTC, 2000. 
ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa Operacional 
para Cursos de Engenharia. Rio de Janeiro: Elsevier, 2015.
CORRAR, L. J.; THEÓPHILO, C. R. Pesquisa Operacional para Decisão em Conta-
bilidade e Administração. São Paulo: Atlas, 2004. 
CORREIA, R. R. et al. Simulação do fluxo de ônibus no terminal de integração do 
Varadouro: um estudo computacional. In: ENCONTRO NACIONAL DE ENGENHARIA 
DE PRODUÇÃO (ENEGEP), XXXII, 2012, Bento Gonçalves. Anais... Bento Gonçalves: 
ABEPRO, 2012. p. 02-12.
FOGLIATTI, M. C.; MATTOS, N. M. C. Teoria de Filas. Rio de Janeiro: Interciência, 2007.
HILLIER, F. S.; LIEBERMAN, G. J.; LEMOS, H. L. Introdução à Pesquisa Operacional. 
São Paulo: Campus, 1988. 
LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisões. 4. ed. São 
Paulo: Pearson Prentice Hall, 2009. 
LOESCH, C.; HEIN, N. Pesquisa Operacional: fundamentos e modelos. São Paulo: 
Saraiva, 2008. 
MOREIRA, D. A. Pesquisa Operacional: curso introdutório. São Paulo: Thomson, 2006. 
MUROLO, A. C. et al. Pesquisa Operacional para os Cursos de Economia, Admi-
nistração e Ciências Contábeis. 3. ed. São Paulo: Atlas, 1998. 
PINTO, K. C. R. Aprendendo a Decidir com a Pesquisa Operacional. Minas Gerais: 
Edufu, 2005. 
 
	Capa Pesquisa Operacional
	Branco
	Pesquisa Operacional
	Branco
	contra_capa