PESQUISA OPERACIONAL (16)

Prévia do material em texto

INTRODUÇÃO À PESQUISA OPERACIONAL 
1 - INTRODUÇÃO 
 
Apresentação 
Esta apostila é derivada de uma compilação de diversas fontes, como: notas de aula do 
professor Otoniel Marcelino de Medeiros (grande parte), parafrases e citações de trechos de 
livros (principalmente do Lieberman), e uma contribuição mínima minha. 
 
Carlo Ralph De Musis, M.Sc. 
 
1.1 - O QUE É PESQUISA OPERACIONAL 
 
 A Pesquisa Operacional é uma ciência aplicada cujo objetivo é a melhoria da 
performance em organizações, ou seja, em sistemas produtivos usuários de recursos 
materiais, financeiros, humanos e ambientais (os chamados "meios de produção"). Ela 
trabalha através da formulação de modelos matemáticos a serem resolvidos com o 
auxílio de computadores, sendo feita em seguida a análise e a implementação das 
soluções obtidas. Dessa forma, a técnica é precedida pela modelagem e seus resultados 
são sujeitos à análise de sensibilidade. 
 
A modelagem tem muito de arte e exige o desenvolvimento de uma capacidade (em 
grande parte não lógica) de interação com o problema, seus agentes e seu meio 
ambiente. O modelo matemático, que é uma simplificação, dificilmente pode levar em 
conta muitos aspectos não qualificáveis que aparecem no exame do problema e por isso 
a análise de sensibilidade deve ser realizada para avaliar o seu significado e a sua 
influência. Enfim, a implementação da decisão reata o contato com a realidade do 
problema e com o meio no qual ele se encontra inserido. 
 
 O campo de atuação da PO se estende da produção de matérias-primas e bens de 
consumo ao setor de serviços e às aplicações de interesse social como as relacionadas à 
saúde, à educação e à psico-sociologia, no que concerne a modelos organizacionais e 
descritivos. Esta multiplicidade de aplicações aponta para a necessidade de se evitar a 
estreiteza da especialização, o que levou a Área a adotar uma orientação metodológica, 
facultando a seus alunos, tanto como a seus docentes/pesquisadores, uma ampla gama 
de oportunidades em termos de novos problemas. Esta orientação foi adotada no trabalho 
didático associado à formação de mestres, resultando daí uma formação bastante eclética 
que procura abranger os diversos aspectos do mercado de trabalho no que se refere ao 
instrumental teórico. 
 
Segundo Hillier/Lieberman no seu livro Introdução À Pesquisa Operacional, “Em 
resumo, pesquisa operacional diz respeito `a tomada de decisão ótima em, e modelação 
de, sistemas determinísticos que se originam na vida real.” 
 
1.2 - ORIGEM DA PESQUISA OPERACIONAL 
 
A pesquisa operacional (PO) teve suas origens na II Guerra Mundial, como 
resultado do trabalho de equipes multidisciplinares na busca de soluções para problemas 
operacionais e de alocação de recursos escassos. 
 
Após o final do conflito, essas técnicas começaram a ser aplicadas a diversos 
problemas de gerenciamento de atividades produtivas e à análise de situações complexas 
envolvidas nessas atividades, o que permitiu grande economia no uso dos meios de 
produção e popularizou o seu uso nesta área de conhecimento. Em vista disso, a 
engenharia de produção, dentre todas as especialidades tecnico-científicas, é a que mais 
extenso uso faz da PO. Ao longo dos anos a teoria e as aplicações da PO se 
diversificaram, fazendo dela, hoje em dia, um campo em franca expansão cujos usos 
abrangem indústria, comércio, serviços e setores governamentais. 
 
 1.3 - O IMPACTO DA PESQUISA OPERACIONAL 
 
A Pesquisa Operacional tem tido um grande impacto crescente na administração de 
empresas nos anos recentes. Tanto o número quanto a variedade de suas aplicações 
 1
continuam a crescer rapidamente. Algumas de suas técnicas envolvem idéias bastante 
sofisticada em ciências políticas, matemática, economia, teoria da probabilidade e 
estatística. Como também sendo usada amplamente em outros tipos de organizações, 
inclusive negócios e indústria. Segundo Hillier quase todas as doze maiores empresas do 
mundo, e uma considerável proporção das organizações indutriais pequenas, têm grupos 
de pesquisa operacional bem estabelecidos. Muitas indústrias, inclusive a de aviação e 
mísseis, automóveis, comunicações, computadores, energia elétrica, eletrônica, 
alimentos, metalúrgica, mineração, papel, petróleo e transporte, têm feito uso extensivo da 
pesquisa operacional. Mesmo instituições financeiras, agências governamentais e 
hospitais têm aumentado rapidamente o uso que fazem da pesquisa operacional. 
 
Vejamos alguns dos problemas que têm sido resolvidos por técnicas particulares de 
pesquisa operacional: 
- PROGRAMAÇÃO LINEAR: tem sido usada com sucesso na solução de problemas 
relativos à alocação de pessoal, mistura de materiais, distribuição, transporte, carteira de 
investimento. 
- PROGRAMAÇÃO DINÂMICA: tem sido aplicada também com sucesso a áreas 
como planejamento de despesas de publicidade, distribuição do esforço de vendas e 
programação de produção. 
- TEORIA DAS FILAS: tem tido aplicação na solução de problemas relativos a 
congestionamento de tráfego, máquinas de serviços sujeitas a quebra, determinação do 
nível de uma força de serviço, programação do tráfego aéreo, projetos de represas, 
programação de produção e operação de hospitais. 
 
Outras técnicas de pesquisa operacional, tais como teoria de estoque, teoria dos 
jogos e simulação, também têm sido aplicadas com sucesso a diversos contextos. 
 
INTRODUÇÃO À PESQUISA OPERACIONAL 
 
2 - APLICAÇÃO 
 
2.1 - UM CASO PRÁTICO 
 
Apresentamos um exemplo que é uma aplicação direta de Teoria das Filas / 
Simulação, desenvolvido na UFRJ e publicado na INTERNET (www.producao.ufrj.br), 
uma busca pela otimização lucrativa melhorando a qualidade dos serviços em um posto 
de gás natural no Rio de Janeiro - RJ. 
 
SIMULAÇÃO COMO FERRAMENTA PARA ANÁLISE DE NÍVEL DE SERVIÇO E 
CAPACIDADE DE ATENDIMENTO EM UM POSTO DE GÁS NATURAL 
 
 
TRABALHO DESENVOLVIDO POR: 
Peter Wanke 
Centro de Estudos em Logística - COPPEAD/UFRJ 
Edifício do COPPEAD, Cidade Universitária - Ilha do Fundão, Rio de Janeiro-RJ. 
Cep.21949-000 
 
Leonardo Barros, Milene Cauzin 
Centro de Estudos em Logística - COPPEAD/UFRJ 
Edifício do COPPEAD, Cidade Universitária - Ilha do Fundão, Rio de Janeiro-RJ. 
Cep.21949-000 
 
2.2 - A problemática do abastecimento 
 
 Conforme revelado por diversas pesquisas, o Gás Natural de Petróleo (GNP) é o 
combustível automotor de mais baixo custo por quilômetro rodado. Sua venda foi 
regulamentada em 1991, atendendo, assim, aos anseios de um grande número de 
frotistas e de taxistas, possibilitando a conversão de seus veículos ao gás. 
 Com o decorrer do tempo, os poucos postos inaugurados mostraram-se 
insuficientes para atender à crescente demanda, concorrendo para deterioração dos 
níveis de serviço (medidos em TEMPO DE ESPERA do taxi na FILA e TAMANHO DE FILA). 
 2
 As principais motivações deste trabalho são: avaliar o atual nível de serviço de um 
posto de abastecimento de GNP: determinar métodos para aumentar produtividade e 
quantificar incrementos no volume de vendas. Dessa forma, são vários os fatores que 
concorrem para este cenário:(a) escassez de oferta do serviço: somente 5 postos 
distribuem gás natural no Rio de Janeiro; (b) elevados investimentos necessários para 
montagem de um posto de serviço, principalmente em compressores, demais 
equipamentos e obras civis, da ordem de um milhão de dólares; (c) métodos empregados 
nas operações de abastecimento ainda não estudados cientificamente, bem como os 
procedimentos de segurança que tornam o atendimento mais demorado, obrigando 
também cada táxi conter somente um tanque para carga de gás, o que reduz a 
autonomia. 
 Os fatores acima mencionados evidenciam um sistema complexo, de difícil 
tratamento analítico, justificando-se, portanto, a aplicação de simulação computacionalpara estudar o tamanho de filas, bem como o comportamento característico do sistema 
face à demanda. 
 
2.3 - Modelagem do problema 
 
 Uma característica da fonte de chegada ou população potencial é seu "tamanho", 
ou a quantidade potencial de táxis a gás que podem abastecer no posto. Como são 
poucos os postos de gás natural na cidade do Rio de Janeiro e como os veículos movidos 
a GNP apresentam menor autonomia, podemos supor uma fonte de chegadas infinitas. 
Por outro lado, o padrão estatístico dentro do qual os clientes são gerados no tempo foi 
suposto POISSON. 
 Foi medido, portanto, quantos táxis chegavam em média a cada intervalo duas 
horas e, aplicando teste de aderência Qui-quadrado, a DISTRIBUIÇÃO DE POISSON foi aceita 
a 5% de significância. 
 Deve-se ressaltar que para avaliar as taxas de chegada em faixas horárias não 
levantadas, como por exemplo de madrugada, recorreu-se a experiência do operador do 
posto, que a estimou em 1 táxis a cada 10 minutos. 
 Para levantar os tempos de abastecimento, fragmentamos este processo em 
várias atividades principais, desde o momento em que o táxi entra no sistema até o 
momento em que ele o deixa. Foram identificadas quatro atividades principais, conforme a 
tabela abaixo: 
 
Atividade Início Fim 
Inércia e deslocamento ao vagar a bomba táxi parado ao lado da bomba c/ 
motor desligado 
Preparação do 
abastecimento 
ausência de 
movimento 
abertura de válvula do dispenser
Abastecimento abertura da válvula observar fim de abastecimento 
no marcador 
Preparação da saída do 
posto 
fim do abastecimento início do deslocamento 
Descrição das atividades básicas do posto de gás natural 
 
 Foram coletadas diversas amostras da duração dessas atividades, ao longo de 
diversas faixas horárias, estabelecendo-se um tempo médio e seus respectivos desvios-
padrão. 
 Evidenciou-se, mediante Anova para três amostras de tamanhos diferentes e uma 
classificação (10:00 - 11:00 hs, 11:40 - 12:40 hs e 14:50 - 16:50 hs), que os tempos 
médios de abastecimento diferem significativamente, ao nível de 5%, com a equipe de 
frentistas,. havendo mudança de turnos de trabalho às 7:00, 15:00 e às 23:00. 
 Finalmente, foi constatado estatisticamente que a emissão da nota fiscal para 
cooperativas de taxistas aumenta a permanência do táxi no posto. 
 
2.4 - Modelagem computacional 
 
 Foi adotado como ferramenta de trabalho a simulação digital. A simulação tem 
como objetivos tornar viável a realização de testes na configuração do posto, sem que se 
torne necessário nenhuma mudança real na estrutura do mesmo. Basicamente, a 
 3
simulação compreende duas etapas: a modelagem do problema e a simulação 
computacional. 
 Para modelagem do sistema foi utilizado o pacote de simulação Simul, que é, 
basicamente, um conjunto de subrotinas que organiza e gerencia um conjunto de 
atividades que deve começar sob certas condições e terminar após certo período de 
tempo. No processo de modelagem do problema foi utilizado o conceito do Diagrama do 
Ciclo de Atividades (DCA), que traz uma informação geral do sistema simulado e é 
recomendado aos usuários do pacote de simulações em questão. O DCA é uma 
representação esquemática do modelo de simulação e possui três conceitos básicos: 
entidade, atividade e fila, conforme a tabela apresentada a seguir : 
 
Entidade Atividade Fila 
Preserva sua identidade 
durante todo o período 
de simulação. Todas as 
entidades de uma 
mesma classe têm 
comportamento similar. 
 
Estado ativo durante o qual uma 
ou mais entidades trabalham 
juntas por um certo período de 
tempo. Durante a execução de 
uma atividade as entidades 
envolvidas ficam indisponíveis 
 
Estado passivo de uma 
entidade enquanto 
aguarda condições 
favoráveis para 
participar de uma 
atividade. Cada fila 
comporta apenas uma 
classe de entidade. 
 
Descrição dos conceitos básicos de um D.C.A. 
 
A figura abaixo representa o D.C.A. do sistema atual do posto e na tabela 4 são 
apresentadas as atividades relacionadas, as entidades que participam delas e seus 
atributos, bem como as filas pelas quais as entidades passam. 
 
R u aD e s l o c a m e n t o E s p e r a C h e g a d a
 F e c h a d a
O c i o s o
A b a s t e c i m e n t o
B i c o
o c i o s o
E s p
I n i _ A b
T a x i
B i c o
F r e n t i s t a
P o r t a
Diagrama do Ciclo de Atividades 
 
 Baseado nos tempos de operação e nas taxas de chegada, foram programados 
os eventos que simulariam as atividades do posto, utilizando, para tal, o conceito de 
geração de variáveis aleatórias (normal e exponencial), com médias e desvios padrão 
calculados à partir dos dados reais. 
 O número de bicos pode ser escolhido pelo usuário do sistema e varia entre 3 e 5. 
Já o número de frentistas foi estabelecido como de n, onde n é a metade do número de 
bicos. Na verdade, um frentista opera dois bicos simultaneamente, sem sobrecarga de 
trabalho. Ou seja, um frentista, quando está participando de uma atividade pode também 
participar de outra ao mesmo tempo, sem que sua performance seja prejudicada. Além 
disso, o sistema é capaz de realizar simulações para vários dias consecutivos, sem re-
inicialização de variáveis e de coletar os dados estatísticos por faixas horárias, facilitando 
assim futuras análises. 
 
2.5-Projeto de experimentos 
 
 Foram simuladas três configurações básicas alternativas (experimentos) ao atual 
funcionamento do posto. São elas: (a) emissão automática de nota fiscal por dispositivo 
eletrônico, atualmente, vinte por cento dos táxis que abastecem no posto diariamente 
exigem nota fiscal; (b) suposição que o tempo médio de abastecimento diário alcançasse 
 4
o nível do melhor tempo médio coletado por amostragem, mediante treinamento das 
equipes de frentistas; (c) emissão automática de nota fiscal e melhor equipe de frentistas. 
 Vejamos, agora, os ganhos no nível de serviço ao taxista avaliados através de 
simulações dessas configurações alternativas. 
 
 
2.6 - Emissão automática de nota fiscal 
 
 A simulação desta alternativa para 50 dias consecutivos, apresentou reduções 
consideráveis no tamanho médio de fila e no tempo médio de espera na fila, em especial 
nas faixas horárias de pico, (15 às 17, de 17 às 19 e de 19 às 21 horas) conforme 
podemos verificar no gráfico abaixo, comparativamente à configuração atual de operação 
do posto. 
 Reduções expressivas em faixas horárias de menor movimento (0 às 5, 5 às 7, 7 
às 9 e 21 às 24 horas) devem ser analisadas com cautela, já que o tamanho médio de fila 
por intervalo não é suficientemente grande a ponto de se estabelcer uma diferença 
significativa. Esta ressalva esta implícita em todas as análises feitas daqui por diante. 
0 À 5 5 À 7 7À 9 9 À 11 11 À 13 13 À 15 15 À 17 17 À 19 19 À 21 21 À 24
Faixas horárias
0
5
10
15
20
25
30
0 À 5 5 À 7 7À 9 9 À 11 11 À 13 13 À 15 15 À 17 17 À 19 19 À 21 21 À 24
Faixas horárias
emissão automática
posto atual
Ta
m
an
ho
 m
éd
io
 d
e 
fil
a
 
Gráfico comparativo de tamanho médio de fila (emissão automática) 
 
 
 
2.7 - Melhor equipe de frentistas sem emissão automática de nota fiscal 
 
 Esta configuração apresenta melhorias de nível de serviço muito mais expressivas, 
que a anterior para os horários de pico (15 às 17, 17 às 19 e 19 às 21:00). 
 Para a faixa horária de 17 às 19:00 hs, sobretudo, a simulação indicou uma 
redução dramática de 80% no tamanho médio da fila de espera, conforme o gráfico 
abaixo que indica uma queda de 25 para 5 táxis em média. 
0 À 5 5 À 7 7À 9 9 À 11 11 À 13 13 À 15 15 À 17 17 À 19 19 À 21 21 À 24
Faixas horárias
0
5
10
15
20
25
30
Ta
m
an
ho
 m
éd
io
 d
e 
fil
a
0 À 5 5 À 7 7À 9 9 À 11 11 À 13 13 À 15 15 À 17 17 À 19 19 À 21 21 À 24
Faixas horárias
melhorequipe de
frentistas
posto atual
Gráfico comparativo de tamanho médio de fila (frentistas) 
 
 
 
 
2.8 - Melhor equipe de frentistas com emissão automática de nota fiscal 
 5
 
Esta última configuração é a que apresenta maiores ganhos para os horários de 
pico; em particular, mais uma vez, para o horário de 17 às 19:00 hs, conforme nos mostra 
o gráfico abaixo. 
Ta
m
an
ho
 m
éd
io
 d
e 
fil
a
0 À 5 5 À 7 7À 9 9 À 11 11 À 13 13 À 15 15 À 17 17 À 19 19 À 21 21 À 24
Faixas Horárias
0
5
10
15
20
25
30
0 À 5 5 À 7 7À 9 9 À 11 11 À 13 13 À 15 15 À 17 17 À 19 19 À 21 21 À 24
Faixas Horárias
melhor equipe de
frentistas e emissão
automática
posto atual
Gráfico comparativo de tamanho médio de fila (dois parâmetros) 
 
2.9 - Quantificação do aumento do volume anual de vendas 
 
 Apresentaremos os ganhos decorrentes da implantação das configurações 
descritas acima. Os pressupostos básicos para que tal potencial de vendas se converta 
em aumento de receita são: (a) a demanda aumentará até que o nível de serviço da nova 
configuração se iguale ao nível da configuração antiga (em termos de tempo de espera), 
estabilizando-se a partir daí; (b) população (número potencial de táxis) infinita. 
 Desta forma podemos estimar o aumento da demanda em número de táxis/dia em 
função do tamanho de fila desejado (nível de serviço) para a faixa horária mais crítica. 
 
2.10 - Emissão automática de nota fiscal 
 
 É fácil perceber que, para o tamanho médio de fila voltar a 25 táxis, é necessário 
um aumento na demanda da ordem de 3%. Isto significa apenas mais treze carros no 
sistema ao longo do dia e um aumento no volume anual de vendas da ordem de trinta mil 
reais. 
 O parágrafo acima traduz uma informação de grande relevância: o posto estava 
em seu ponto crítico de saturação, onde o impacto dos experimentos testados se traduziu 
em consideráveis aumentos de produtividade. Entretanto, um pequeno aumento no 
volume de carros atendidos diariamente trouxe de volta o sistema ao seu estado de 
saturação 
 
2.11 - Melhor equipe de frentistas sem emissão automática de nota fiscal 
 
 Este experimento apresentou maiores ganhos de produtividade que o anterior. Em 
outras palavras, numa situação de operação próxima a saturação, o posto é mais sensível 
ao treinamento de seus recursos humanos, em termos de aumentos de produtividade, 
que a implementação da emissão automática de nota fiscal.. 
 É fácil perceber que, para o tamanho médio de fila voltar a 25 táxis, é necessário 
um aumento na demanda da ordem de 16%. Isto significa mais setenta e oito carros no 
sistema ao longo do dia e um aumento no volume anual de vendas da ordem de cento e 
sessenta mil reais. 
 
2.12 -Melhor equipe de frentistas com emissão automática de nota fiscal 
 
 Conforme esperado, esta configuração apresenta como característica principal um 
aumento de produtividade que não é equivalente a soma dos aumentos de produtividade 
dos outros experimentos anteriores. 
 Se com a emissão automática de nota fiscal o tamanho médio de fila para a pior 
faixa horária caiu de 25 para 15 carros, e com a melhor equipe o tamanho médio cai de 
25 para 5 carros, a execução dois experimentos simultaneamente não significa 
necessariamente que a fila vá cair a zero carro. Há interferências entre os experimentos, 
e um estudo mais detalhado foge do escopo de nosso trabalho. 
 
 6
 É fácil perceber que para o tamanho médio de fila voltar a 25 táxis, é necessário 
um aumento na demanda da ordem de 18%. Isto significa mais oitenta e oito carros no 
sistema ao longo do dia e um aumento no volume anual de vendas da ordem de cento e 
oitenta mil reais. 
611
587
562
538
513
490
Volume
diário
(carros)
Aumento
demanda
 0%
 5%
10%
15%
20%
25%Somente emissão
automática 
Somente melhor
equipe
Melhor equipe e 
emis. automática 
Tamanho médio de fila
A
um
en
to
 d
o 
vo
lu
m
e 
an
ua
l d
e 
ve
nd
as
(R
$1
00
0)
0
40
80
120
160
200
240
0 5 10 15 20 25 30 35
Somente emissão
automática
Somente melhor equipe
Melhor equipe, emissão
automática
Gráfico comparativo dos três experimentos 
 
Conclusão 
 
 Este trabalho, através do uso de simulação computacional, avaliou soluções 
alternativas para aumentar a produtividade num sistema saturado, sem perspectivas 
imediatas de aumento na capacidade de atendimento. 
 Procurou-se avaliar o impacto destas configurações alternativas em termos de 
nível de serviço ao taxista (tamanho de fila e tempo de espera), bem como estimar um 
provável aumento no volume anual de vendas. 
 
Bibliografia 
 
* Costa Neto, Pedro Luiz de Oliveira, “Estatística”, Editora Edgard Blücher, São 
Paulo, 1977. 
 
* Hillier, Frederick S., “Operations Research”, Holden-Day, San Francisco, 1974 
 
* Saliby, Eduardo; Pimentel, Milton, Relatório COPPEAD nº 255 - Simul: Um Sistema 
Computacional para a Simulação a Eventos Discretos em Turbo Pascal, Rio de Janeiro, 
1991. 
 7
3.1) PROGRAMAÇÃO LINEAR 
 
Programação Linear é uma técnica de otimização bastante utilizada na resolução 
de problemas que tenham seus modelos representado por expressões lineares. Pela sua 
simplicidade e a possibilidade de aplicação em uma considerável diversidade de 
problemas, tornou-se um recurso bastante difundido. 
 
Podemos assim resumir a técnica de Programação Linear: 
 
 
 - Conjunto de restrições 
 Problema RESOLUÇÃO 
 - Função Objetivo 
 
 
Chamamos de conjunto de restrições, as expressões contornais do problema, ou 
seja, todas as disponibilidades e limitações levantadas do problema, numa linguagem 
matemática comparativa: desigualdades ou igualdades (<, = ou >). A função objetivo, é 
obtida com as mesmas variáveis das restrições, com o objetivo de ser maximizada ou 
minimizada, com a resolução do sistema restritivo. 
 
Quanto a resolução, pode ser: 
 
a) Problema com duas variáveis 
 - Gráfica 
 - Análise matemática 
 - Algoritmo (Método Simplex). 
 
b) Problema com um número qualquer de variáveis 
 - Análise matemática 
 - Algoritmo (Método Simplex) 
 
Por questão prática sempre procuramos uma resolução dos problemas com o uso 
de aplicativos computacionais. Pela Internet se consegue bons aplicativos, por exemplo, o 
aplicativo, Linear programming, por ser obtido pela Internet, no seguinte endereço: 
 
http://www.producao.ufrj.br 
 
Inicialmente mostraremos um problema dentro de uma visão geral, ou seja, partindo 
do enunciado, montamos as restrições, a função objetivo e em seguida processamos a 
resolução gráfica (apenas com duas variáveis). 
 
3.1.2) APLICAÇÃO 1: RESOLUÇÃO GRÁFICA 
 
Um fazendeiro deseja otimizar as plantações de arroz e milho na sua fazenda. O 
fazendeiro quer saber as áreas de arroz (x1) e milho (x2) que devem ser plantadas para 
que o seu lucro nas plantações sejam o máximo. O seu lucro por unidade de área 
plantada de arroz é 5 u.m., e por unidade de área plantada de milho é 2 u.m. 
As áreas plantadas de arroz e milho não devem ser maiores que 3 e 4 
respectivamente. Cada unidade de área plantada de arroz consome 1 homem-hora. 
Cada unidade de área plantada de milho consome 2 homens-hora. O consumo total de 
homens-hora nas duas plantações não deve ser maior que 9. 
 
 
SOLUÇÃO: 
 
Chamemos de x1 a área a ser plantada de arroz e x2 a de milho. 
 
Do enunciado concluímos as restrições: 
 
x1 ≤ 3 (I) 
x2 ≤ 4 (II) sendo a função objetivo: Zmáx = 5x1 + 2x2 
 8
x1 + 2x2 ≤ 9 (III) 
 
Como o problema tem apenas duas variáveis (x1 e x2), podemos resolve-lo graficamente,conforme a Fig. 1. 
 
A Fig. 1 é o resultado do lançamento gráfico das 
retas (I), (II) e (III); Conseqüentemente 
determinamos os pontos vértices A(00), B(3,0), 
C(3,3), D(1,4) e E(0,4). 
 
 
 
 
 
Como a função objetivo é Z = 5x1 + 2x2, que 
aplicada em cada vértice do polígono restritivo 
nos fornece os seguintes valores: 
 
ZA(0,0) = 0 
ZB (3,0) = 15 
ZC(3,3) = 21 Verifica-se que o ponto “C” é o que fornece o maior 
ZD(1,4) = 13 valor para a função objetivo (Zmáx = 21). 
ZE(0,4) = 8 
 
Concluímos que o lucro máximo do fazendeiro de 21 unidades monetárias, desde que 
plante 3 unidades de área de arroz e 3 unidades de área de milho. 
 
3.1.3) APLICAÇÃO 2: MÉTODO SIMPLEX (APLICATIVO COMPUTACIONAL) 
 
Procuraremos examinar apenas um dos aspectos deste problema complexo, a 
saber, o do corte econômico de laminado em séries de peças de várias configurações. 
Dadas as variantes de corte tecnologicamente aceitáveis (a escolha destas sendo 
um problema técnico à parte) a otimização propriamente dita estabelece a freqüência de 
emprego de cada uma das variantes de corte que minimiza o refugo global. 
Suponhamos que se tenha, no intuito de obter 360 unidades da peça A e 1800 
unidades da peça, proposto as variantes de corte I a V (figura abaixo) do laminado 
disponível 4x12. 
 
É fácil constatar que para cada uma destas variantes de corte de uma placa de 
laminado o número de peças e o volume de refugo (em unidades de área) se darão pelo 
quadro: 
 
 VARIANTES DE CORTE 
PEÇA I II III IV V 
“A” 4 3 1 0 2 
“B” 0 4 9 12 7 
 9
REFUGO 12 5 3 0 2 
 
Se x1, x2, x3 e x4 (que corresponde ao número de variantes de corte) denotarem o 
número de placas de laminado cortadas de acordo com as variantes I, II, III, IV e V, 
respectivamente, as condições do problema fornece as restrições: 
 
4x1 + 3x2 + x3 + 2x5 = 360 (1) 
4x2 + 9x3 + 12x4 + 7x5 = 1800 (2) 
 
Ë lógico que xi será o número de chapas cortadas para cada alternativa, que 
obedece a uma matriz de corte. 
O melhor plano de corte é o que minimiza o refugo total, que de acordo com o 
quadro das alternativas de corte, podemos montar a função objetivo: 
 
Zmín = 12x1 + 5x2 + 3x3 + 2x5 (3) 
 
Com as restrições (1), (2) e a função objetivo (3), podemos resolver o problema 
usando o método SIMPLEX. No nosso caso usamos um aplicativo computacional, que é 
exatamente o método Simplex e encontramos a solução deste problema de programação 
linear, sendo: 
x1 = 0 
x2 = 0 
x3 = 0 
x4 = 45 (Solução) 
x5 = 180 
Zmín = 360 
 
O sentido prático da solução é que a alternativa IV será usada 45 vezes, ou seja 45 
chapas serão cortadas conforme a matriz IV, e a alternativa V, 180 vezes. Com isto temos 
a segurança técnica, ou seja a otimização deste plano de produção que no final teremos 
um desperdício menor possível, ou seja, 360 unidades de área. 
 
3.1.4 ) CONCLUSÃO 
 
Na realidade usamos um modelo de programação linear, para otimização de cortes 
de chapas. Vê-se que é necessário traduzir o problema prático numa linguagem 
matemática, ou seja, num conjunto restritivo do primeiro grau, e uma função objetivo. 
Resolver o problema é encontrar as variáveis do problema de tal forma que a função 
objetivo seja satisfeita, no nosso caso, uma minimização. 
 
A solução do sistema de restrições satisfazendo a função objetivo (maximização ou 
minimização) é com o Algoritmo Simplex, para maior facilidade, na forma de aplicativo 
computacional. O aplicativo usado foi o QBS (The Quantitative Business Systems). 
 
EXERCÍCIO - 4.1.5 
 
1) Resolver graficamente (para todas as questões x1 e x2 ≥ 0): 
 
1.1 ) Max Z = x1 + 2x2, sendo: 
 
-x1 + 2x2 ≤ 12 
 x2 ≤ 8 
 x1 + 3x2 ≤ 33 
 x1 + x2 ≤ 19 
 x1 ≤ 15 
1.2) Max Z = 3x1 + 7x2, para: 
 
-3x1 + x2 ≤ 9 
 x2 ≤ 12 
3x1 + 7x2 ≤ 105 
 x1 + x2 ≤ 23 
 x1 ≤ 18 
 
 
1.3) Max Z = 3x1 + 2x2
 
-2x1 + 3x2 ≤ 8 
-x1 + 3x2 ≤ 13 
 x2 ≤ 8 
1.4) Max Z = x1 + 2x2 
 
-3x1 + x2 ≤ 6 
-3x1 + 2x2 ≤ 15 
-2x1 + 3x2 ≤ 30 
 10
 
 
1.5) Max Z = -x1 + 2x2
 x1 - x2 ≥ -1 
-0,5x1 + x2 ≤ 2 
 
 
1.7) Max Z = x1 + x2 
 
x1 - x2 ≥ 0 
3x1 - x2 ≤ -3 
 
 
1.9) Min Z = 2x1 - 3x2
 -x1 + x2 ≤ 6 
 x1 + 3x2 ≤ 42 
-2x1 + 9x2 ≥ 36 
 x1 + x2 ≥ 15 
 
 
 
1.11) Min Z = x1 + x2
x1 ≤ 3 
x2 ≤ 4 
x1 + 3x2 ≤ 9 
 -x1 + 3x2 ≥ 3 
x1 + 3x2 ≥ 6 
1.6) Max Z = 3x1 - 2x2
 x1 + x2 ≤ 1 
 2x1 + 2x2 ≥ 4 
 
 
1.8) Max Z = 2x1 + x2
 -x1 + x2 ≤ 6 
 x1 + 3x2 ≤ 42 
-2x1 + 9x2 ≥ 36 
 x1 + x2 ≥ 15 
 
1.10) Max Z = 5x1 + 2x2
 x1 ≤ 3 
 x2 ≤ 4 
 x1 + 2x2 ≤ 9 
 -x1 + 3x2 ≥ 3 
 x1 + 3x2 ≥ 4 
 x1 + 3x2 ≥ 6 
 
2. Uma companhia fabrica um produto a partir de dois ingredientes, A e B. Cada quilo de 
A contém 5 unidades do produto P1, 4 unidades do produto P2, 2 unidades do produto P3 
e custa 100 u.m. Cada quilo de B contém 3 unidades de produto P1, 5 unidades de 
produto P2, 10 unidades de produto P3 e custa 150 u.m. A mistura deve conter pelo menos 
20 unidades de P1, 18 unidades de P2 e 30 unidades de P3. 
Formule este problema como um problema de programação linear para que o custo do 
produto seja o menor possível. 
 
3. Uma rede de televisão local tem o seguinte problema: foi descoberto que o programa 
“A” com 20 minutos de música e 1 minuto de propaganda chama a atenção de 30.000 
telespectadores, enquanto o programa “B”, com 10 minutos de música e 1 minuto de 
propaganda chama a atenção de 10.000 telespectadores. No decorrer de uma semana, o 
patrocinador insiste no uso de no mínimo, 5 minutos para sua propaganda e que não há 
verba para mais de 80 minutos de música. Quantas vezes por semana cada programa 
deve ser levado ao ar para obter o número máximo de telespectadores. 
 
4.Uma empresa, após um processo de racionalização de produção, ficou com 
disponibilidade de 3 recursos produtivos, R1, R2 e R3. Um estudo sobre o uso desses 
recursos indicou a possibilidade de se fabricar 2 produtos P1 e P2. Levantando os custos e 
consultando o departamento de vendas sobre o preço de colocação no mercado, 
verificou-se que P1 daria um lucro de $120,00 por unidade e P2, $150,00 por unidade. O 
departamento de produção forneceu a seguinte tabela de uso de recursos. 
 
Produto Recurso R1 por unidade 
Recurso R2 por 
unidade 
Recurso R3 por 
unidade 
P1 2 3 5 
P2 4 2 3 
Disponibilidade de 
recursos por mês 100 90 120 
 
Que produção mensal de P1 e P2 traz o maior lucro da empresa. 
 
 
 11
02) A fabricação de álcool envolve a destilação de uma massa fermentada, resultando 
daí um líquido residual ou "destilado” que após secagem e outros tratamentos torna-
se um valioso alimento. Uma determinada empresa tem comercializado uma mistura 
alimentar com base neste produto destilado enriquecida com constituintes 
vitamínicos. 
 
As especificações, fatores de produção e condições mercadológicas estão no 
quadro abaixo: 
 Destilado 
(seco) 
Aditivos 
Comprados 
Total
Custo (u.m./Kg) 0,2 2 
Quantidade normal de unidade de vitamina 
por quilograma de mistura alimentar 
A 
B 
C 
 
 
1 
2 
6 
 
 
15 
10 
50 
 
Unidades mínimas de vitamina que devem 
estar em uma carga de mistura 
A 
B 
C 
 
 
 
 
 
600 
800 
3000
Capacidade produtiva do destilado (Kg/mes) 
 
 
1800 
 
Suprimento de constituintes vitamínicos 
disponíveis no mercado (Kg/mes) 
 
2400 
 
Número de Cargas de mistura produzidas por mês 30 
 
Determinar as quantidades de aditivo e destilado seco por carga de mistura para se 
ter o custo mínimo. Resolver o problema graficamente. 
 
03) A indústria Latal produz dois tipos de peças para o carro Ferrugem. A peça “A” 
demanda duas horas detorno e mais quatro horas na furadeira. A peça tipo “B” 
demanda somente três horas no torno, não passando pela furadeira. São disponíveis 
200 horas no torno, na furadeira a 150 horas no torno, sendo as demais horas 
utilizadas na manutenção, limpeza e preparação. O gerente desta indústria de 
autopeças está interessado em saber quantas peças de cada tipo devem ser 
produzidas; sabe ele que cada peça do tipo “A” fornece um lucro de 40 u.m. e do tipo 
“B” um lucro de 30 u.m. 
 
04) Uma fábrica tem 3 tipos de máquinas, M1, M2 e M3, a serem utilizadas na fabricação 
dos produtos P1 e P2. O quadro abaixo descreve como a fábrica opera, diariamente: 
 
Produtos 
Máquinas 
 
P1 
 
P2 
Disponibilidade 
Diária 
M1 3 2 20h 
M2 4 0 12h 
M3 2 5 18h 
 
Formule o problema como um modelo de programação linear para planejar a 
produção diária a fim de que o lucro seja o máximo possível, sabendo que o produto P1 
dá lucro de 200 u.m. e P2, um lucro de 50 u.m. . Resolva graficamente. 
 
05) Um companhia fabrica um produto a partir de dois ingredientes, A e B. Cada 
quilograma de A contém 5 unidades de produto P1, 4 unidades de produtos P2, 2 
unidades de produtos P3 e custa 100 u.m., Cada quilograma de B contém 3 
unidades de produto P1, 5 unidades de P2, 10 unidades de produto P3 e custa 150 
u.m.. A mistura deve conter pelo menos 20 unidades de P1, 18 unidades de P2 e 30 
unidades de P3. Formule este problema como um problema de programação linear 
para que o custo do produto seja o menor possível. 
 
 12
06) A Indústria SIDENOX S.A. produz chapas finas (bobinadas) de aço inoxidável com 68 
u.c. de largura. Os clientes da SIDENOX encomendam bobinas de largura menor 
com valores padrão de 22, 20 e 12 u.c., com demandas diárias, respectivamente, 
iguais a 110, 120 e 80 unidades. Estas bobinas são cortadas da bobina padrão de 68 
u.c.. A empresa deseja cortar as bobinas de forma a minimizar os desperdícios. 
Elaborar um plano de corte otimizado. 
 
07) Uma empresa fabrica 5 produtos: P1, P2, P3, P4 e P5. Cada um deles requer 3 tipos 
de matérias-primas M1, M2 e M3. As quantidades utilizadas por cada produto, as 
disponibilidades das matérias primas e o lucro líquido de cada produto são dados na 
tabela abaixo: 
 
Produtos 
Matéria Primas 
P1 P2 P3 P4 P5 Disponibilidade de 
matérias-primas 
M1 2 5 3 2 1 100 unidades 
M2 3 1 4 7 2 80 unidades 
M3 6 2 3 1 4 150 unidades 
Lucro líquido unitário 2000 100 60 50 150 unidades monetárias
 
Supondo que o lucro é proporcional à quantidade produzida (vendida), formule o 
problema como um modelo programação linear para determinar a quantidade de cada 
produto que deve ser fabricada para que o lucro seja o máximo possível. 
 
08) Um fabricante de ligas metálicas deseja maximizar seu lucro. As ligas são vendidas 
aos preços de 30 u.m. e 50 u.m., respectivamente, a unidade. Os metais básicos 
utilizados para a fabricação das ligas são sobre, zinco e chumbo, sendo as 
disponibilidades limitadas aos máximos de 16, 11 e 15 toneladas. Determine a 
quantidade (em t) que deve ser fabricada da cada liga, de acordo com o quadro: 
 
COMPOSIÇÃO DAS LIGAS (proporção) 
Metais Básicos Liga “A” Liga “B” 
Cobre 2 t 1 t 
Zinco 1 t 2 t 
Chumbo 1 t 3 t 
Observação: 
 - Lucro é diretamente proporcional ao preço de venda. 
 - Resolver o problema graficamente. 
 
09) Uma determinada companhia produz quatro artigos numerados de 1 a 4. As 
exigências de matéria-prima, espaço para estocagem, taxa de produção assim como 
lucros por artigos estão no quadro abaixo: 
 
 1 2 3 4 
Matéria-prima (Kg/artigos) 2 2 1,5 4 
Espaço (m3/artigo) 2 2,5 2 1,5 
Taxa de produção (artigos/h) 15 30 10 15 
Lucro (u.m. / artigo) 5 6,5 5 3,5 
A quantidade total de matéria-prima disponível por dia para todos os quatro artigos é 
de 180 kg, e o espaço disponível é de 230 m3 e empregam-se 7h e 30 min por dia de 
produção. 
Quantas unidades de cada artigo devem ser produzidas por dia para se maximizar o 
lucro? (Elaborar apenas as restrições e a função objetivo). 
 
10): A Própolis Utilidades Elétricas fabrica dois modelos simples de secador para cabelo, 
que designa pó HX20 e HX30. Dois dos departamentos que participam da produção dos 
secadores, o Departamento A e o Departamento B, têm restrições quanto ao total de 
horas semanais disponíveis para aqueles produtos. O Departamento A possui um máximo 
de 100 homens hora, contra 80 homens hora do Departamento B. Embora a demanda 
pelos secadores esteja muito acima da capacidade produtiva da Própolis, e, portanto 
possa ser considerada ilimitada, as restrições correm por conta dos departamentos A e B. 
O secador HX20 requer 0,4 homens hora por unidade do departamento A e 0,2 homem 
hora no Departamento B; para o secador HX30 as necessidades são de 0,2 e 0,4 
 13
respectivamente para os Departamentos A e B. O lucro unitário derivado da venda dos 
secadores é de $1500,00 e de $2000,00 respectivamente para os secadores HX20 e 
HX30. Formular o problema como um modelo de Programação Linear e determinar 
graficamente as quantidades ótimas dos secadores HX20 e HX30 a produzir. 
 
11) A Wyndor Glass Co. produz vidros de alta qualidade, incluindo janelas e portas de 
vidro. Ela tem três fábricas. Na Fábrica 1 são feitas as esquadrias e ferragens de 
alumínio; as esquadrias de madeira são feitas na Fábrica 2 e a Fábrica 3 é usada para 
produzir o vidro e montar os produtos. 
 Por causa do declínio da receita, a alta gerência decidiu reformular a linha 
de produtos. Diversos produtos não-lucrativos estão sendo tirados de linha e isso irá 
liberar a capacidade de produção para se encarregar de um ou dos dois novos produtos 
potenciais que têm estado em demanda. Um destes produtos propostos (produto 1) é uma 
porta de vidro de 2,40 m, com esquadria de alumínio. O outro produto (produto 2) é uma 
grande janela (1,20 x 1,80m) de duas folhas esquadria de madeira. O Departamento de 
Marketing concluiu que a companhia poderia vender tantos destes dois produtos quantos 
pudessem ser produzidos pela capacidade disponível. Entretanto, como ambos os 
produtos estariam competindo com a mesma capacidade de produção na Fábrica 3, não 
fica claro qual combinação entre os dois produtos seria mais lucrativa. Por isso a gerência 
pediu ao Departamento de Pesquisa Operacional que estudasse a questão. 
 Depois de alguma investigação, o Departamento de PO determinou (1) a 
percentagem de capacidade de produção de cada fábrica que estaria disponível para 
estes produtos, (2) as percentagens requeridas por produto para cada unidade produzida 
por minuto e (3) o lucro unitário de cada produto. Estas informações estão resumidas na 
Tabela a seguir. Como toda capacidade que for usada por um produto na Fábrica 3 torna-
se não-disponível para o outro, tratando-se de um problema de programação linear do tipo 
clássico de “composto de produto”, encontre a sua formulação e solução. 
 
Capacidade usada por 
taxa de produção unitária Produto Fábrica (1) (2) 
Capacidade 
disponível 
(1) Esq. e ferr. de alumínio. 1 1 8 
(2) Esq. de madeira. 1 2 12 
(3) Prod. vidro e montar os produtos. 3 2 18 
Lucro por unidade $ 3,00 $ 5,00 
 
12. Um fabricante está iniciando a última semana de produção de quatro diferentes 
modelos de consoles em madeira para aparelhos de televisão, designados 
respectivamente, I, II, III e IV. Cada um deles deve ser montado e em seguida decorado. 
Os modelos necessitam, respectivamente de 4, 5, 3 e 5 horas para montagem e de 2, 1, 
5, 3 e 3 horas para decoração. Os lucros sobre as vendas dos modelos são 
respectivamente 7, 7,6 e 9 dólares. O fabricante dispõe de 30.000 horas para a montagem 
destes produtos (750 montadores trabalhando 40 horas por semana) e de 20.000 horas 
para decoração (500 decoradores trabalhando40 horas semanais). Quanto de cada um 
dos modelos deve ser produzido durante esta última semana a fim de maximizar o lucro? 
Admita que todas as unidades produzidas possam ser vendidas. 
 
 14
3.1.5 - MÉTODO SIMPLEX - CONDIÇÕES DE PREPARAÇÃO 
 
I) - Todos bis devem ser maiores ou iguais a zero 
 x1 + 3x2 ≥ - 7 bi negativo 
 - x1 - 3x2 ≤ 7 bi positivo 
 
II) - Todas restrições devem ser transformadas em igualdade (necessário uma base 
óbvia): 
 
a) Se a restrição é do tipo MENOR OU IGUAL (≤ ), com bi positivo, introduz-se 
variável de folga: 
 
 3x1 + x2 ≤ 5 desigualdade 
 3x1 + x2 + x3 = 5 igualdade 
 sempre x1, x2 e x3 ≥ 0 
 
b) Se a restrição é do tipo MAIOR OU IGUAL ( ≥ ), com bi positivo, introduzem-se 
uma variável de folga (com sinal negativo) e uma variável artificial: 
 
 x1 + 3x2 ≥ 5 desigualdade 
 x1 + 3x2 - x3 + x4 = 5 igualdade 
 variável de artificial 
 variável de folga 
 
 Da mesma forma, x1, x2, x3 e x4 ≥ 0 
 
c) Se a restrição é do tipo IGUAL ( = ), com bi positivo, introduz-se uma variável 
artificial: 
 2x1 + 7x2 = 10 
 2x1 + 7x2 + x3 = 10 igualdade com variável artificial 
 
 Sendo, x1, x2 e x3 ≥ 0 
 
III) - Toda minimização poderá ser transformada em maximização. Minimizar uma função 
Z é equivalente a maximizar o simétrico dessa função: 
 
 Min Z = 2x1 - 3x2, equivale a Max (-Z) = -2x1 + 3x2
 
OBSERVAÇÕES ADICIONAIS: 
 
a) A informação de varáveis artificiais sempre implica no surgimento da função objetivo 
artificial, sendo o problema resolvido em duas fases. 
b) Por questão de ordenação, deve-se primeiro introduzir todas variáveis de folga em 
todas restrições, para depois introduzir as variáveis artificiais. 
c) O quadro estruturado mostra explicitamente uma solução básica inicial. As variáveis 
básicas formam, com seus coeficientes, uma matriz identidade. 
 
3.1.6 - MÉTODO SIMPLEX: CONDIÇÃO BÁSICA PARA APLICAÇÃO 
 
Para aplicação do Algoritmo Simplex é necessário a estruturação do quadro (tableau), 
obedecendo as condições: 
- bis não negativos. 
- Restrições transformadas em igualdades, pela introdução de 
variáveis de folga e/ou artificiais. 
- Função objetivo sujeita `a maximização (não obrigatório). 
 
O quadro genérico explicito tem a forma: 
 
 Base 
 x1 x2 . . . xn xn+1 xn+2 . . . xn+m bi
xn+1 a11 a12 . . . a1n 1 0 . . . 0 b1
xn+2 a21 a22 . . . a2n 0 1 . . . 0 b2
 15
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
xn+m am1 am2 . . . amn 0 0 . . . 1 bm
Z c1 c2 . . . cn 0 0 . . . 0 0 
 
PASSOS DO ALGORITMO SIMPLEX 
 
PASSO 1 - Verificar se os coeficientes Cjs da função objetivo Z são maiores ou iguais a 
zero, caso afirmativo, pare, a solução é ótima. Caso contrário, escolha a 
variável que tem o menor coeficiente Cj (Cs) para entrar na base. 
 
Cs = min (Cjs) 
Xs = variável que entra na base 
 
PASSO 2 - Verificar os coeficientes ais da variável xs que vai entrar na base. Se todos ais 
forem menores ou iguais a zero, pare, Z = infinito. Caso contrário, divida cada 
bi pelo respectivo ais > 0. O menor quociente bi/ais, ais > 0, indica a variável de 
índice r que sai da base. 
 
PASSO 3 - Calcular os novos coeficientes do quadro (operação pivotal) para que a troca 
de variáveis na base se processe. Os novos coeficientes serão: 
 
ars = pivot 
 
nova linha r = (linha r anterior)/ars
nova linha i i = r = (linha anterior) - (nova linha r) . ais 
 
PASSO 4 - Voltar ao PASSO 1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 16
3.1.7 - ALGORÍTMO SIMPLEX COMPLETO INCLUINDO DUAS FASES 
 
 
 Problema 
 Preparado 
com 2 fases 
 
 
 
 2 FASES Problema 1 FASE 
 com 1 fase ou 
 2 fases? 
 
 Existem Existem NÃO 
 djs < 0 Cjs < 0 
 NÃO SIM 
 W = 0 SOLUÇÃO 
 Encontrar o menor ? ÓTIMA 
 dj(ds). “Xs” é a 
 variável que entra 
 na base Não Existe 
 Solução Encntrar 
 Cj(Cs). “Xs” é 
 a variável que 
 entra na base 
 
 
 
 
 Existem Solução com 
 ais > 0 ? Z = ∞ 
 
 
 
 Calcular bi/ais para ais > 0; o menor quociente indica 
 a variável de índice r que sai da base 
 
 
 Calcular os novos coeficientes do quadro com as 
 variáveis trocadas na base 
 
 
 O problema 
 se encontra na 
 fase 1 
 
 
OBSERVAÇÕES: 
 
a) Os djs são os coeficientes das variáveis na função objetivo artificial. 
b) Na fase 1 se operam com todos os coeficientes, inclusive os da linha Z, na 
operação pivotal. 
c) Quando W = 0 e djs ≥ 0, pode-se abandonar a linha W e as colunas das 
variáveis artificiais. 
 
3.1.8) CASOS DE DIFICULDADES NA APLICAÇÃO DO MÉTODO SIMPLEX 
 
I) Empate na variável que entra na base, isto é, mais de uma variável não básica com o 
mesmo valor para seus respectivos Cjs. 
- A escolha da variável que entra na base é aleatória. 
 
 17
II) Empate na variável que sai da base, isto é, dois ou mais quocientes bi /ais com mesmo 
valor. 
 
- Neste caso caracteriza-se a presença de uma solução degenerada, isto é, uma variável 
básica com valor igual a zero. 
 
- A escolha da variável que sai da base é aleatória. 
 
III) Variáveis sem restrição de sinal, sem a condição de não negatividade. 
 
- A solução alternativa para a questão específica: as variáveis sem restrição de sinal são 
substituídas pela diferença entre duas novas variáveis maiores ou iguais a zero. 
 
IV) Ausência de soluções: 
 
- A dificuldade caracteriza-se por não se conseguir zerar o valor de W ( função objetivo 
artificial) e por conseguinte as variáveis artificiais. 
 
V) Ausência de soluções: 
 
- A dificuldade caracteriza-se quando o problema atinge o ótimo (todos Cjs ≥ 0) e o 
coeficiente Cj de uma das variáveis não básicas, na função objetivo é zero. 
- Para se encontrar o outro extremo, introduz-se na base a variável não básica que tem Cj 
igual a zero; calcula-se o novo quadro e verifica-se que o valor de Z não se altera, 
indicando um novo ponto ótimo. Como solução geral, temos a combinação convexa dos 
dois extremos. 
 
VI) Problema com minização, neste caso, temos: 
 
 Min Z = Máx (-Z) 
VII) Problema com solução Z = infinito: 
 
- Este problema caracteriza-se quando existe uma variável xs em condições de entrar na 
base de forma a provocar um aumentono valor de Z e todos seus coeficientes ais são 
menores ou iguais a zero. Não permitindo, assim, encontrar a variável que sairia da 
base. 
 
3.1.9 - ILUSTRAÇÃO 1: PROBLEMA COM UMA FASE 
 
Máx Z = 5x1 +2x2 (Função objetivo), para as seguintes restrições: 
 
x1 ≤ 3 
x2 ≤ 4 
x1 + 2x2 ≤ 9 
 
Problema já resolvido graficamente na página 6. 
 
Sempre em qualquer problema, temos como solução x1 e x2 ≥ 0 
 
Inicialmente transformemos o sistema de restrições em igualdades com introdução 
das variáveis de folga, ficando o sistema com a seguinte disposição: 
 
 x1 + x3 = 3 
 x2 + x4 = 4 
x1 + 2x2+ x5 = 9 
 
 Sendo as variáveis x3, s4 e x5, as variáveis de folga. 
Antes de aplicarmos o algoritmo simplex, façamos a resolução do problema por 
análise matemática, ou seja uma solução algébrica. Então quebremos a indeterminação 
do sistema fazendo x1 = 0 e x2 = 0, também, já que o sistema possui sete incógnitas e 
apenas cinco equações, temos: 
 
 18
x1= 0 Consideremos as linhas de x1 e x2 a formação da base 
x2= 0 
x3= 3 Essas demais linhas forma a “não base”, resolver o sistema é processar uma 
x4= 4 Seqüência de troca de variáveis básicas por não básicas, de uma forma 
otimizada 
x5= 9 até a maximização da função objetivo. 
 
Quando abordamos uma seqüência de troca de variáveis otimizada, significa pelo 
caminho menor possível. E esta seqüência corresponde a passagem de um vértice para 
outro, no polígono restritivo, até chegar ao vértice solução. Posteriormente, é exatamente 
o que algoritmo irá fazer. 
 
 Pela função objetivo percebe-se que a variável x1 é a que deve inicialmente sair da 
base, ou seja, adquirir um valor maior do que zero, pelo fato de ter o maior coeficiente, o 
que implica num crescimento mais rápido para Z. 
 
Como x2 continua na base, logicamente com o valor nulo, é necessário procurarmos 
a variável de folga que primeiro se anula, para substituir x1 na base, o que podemos 
concluir: 
 
x3 = 3 - x1 (x3 se anula primeiro) 
x4 = 4
x5 = 9 - x1
 
Então, x3 é exatamente a variável que irá entrar na base. O que concluimos: 
x2 = 0 
x3 = 0 
x1 = 3 
x4 = 4 
x5 = 6, ficando a função objetivo: Z = 15 + 2x2 - 5x3, o que é possível o seu 
crescimento com a saída de x2 da base. Procuremos verificar qual a variável que entra na 
base: x4 = 4 - x2 
x5 = 6 - 2x2 (x5 se anula mais rápido, par x2 = 3) 
 
Ficamos com a seguinte disposição: 
x1 = 3 
x2 = 3 
x3 = 0 
x4 = 1 
x5 = 0, ficando a função objetivo: Z = 21 - 5x3 - x5
 
Como a função objetivo não tem mais possibilidade de crescimento, o seu valor 
máximo é Zmáx = 21, para: 
 x1 = 3 
 x2 = 3 
 
Agora apliquemos o algoritmo SIMPLEX ao mesmo problema. Considerando o 
sistema já com a inclusão das variáveis de folga, temos: 
 
 x1 + x3 = 3 
 x2 + x4 = 4 
x1 + 2x2 + x5 = 9, sendo a função objetivo na forma, Z - 5x1 - 2x2 = 0 
 
 
Q1 x1 x2 x3 x4 x5 b 
x3 1 0 1 0 0 3 3/1 = 3 Menor quociente, indicação da variável que sai 
da base (x3) 
x4 0 1 0 1 0 4 - 
x5 1 2 0 0 1 9 9/1 = 9 
Z -5 -2 0 0 0 0 
 O elemento a11 = 1 é exatamente o PIVOT 
 Coeficiente menor, indica a variável que entra na base (x1)
 19
 
O Novo quadro tem a seguinte disposição: 
 
Obtenção das linhas do quadro Q2: 
 
a11 = 1/1 = 1 a21 = 0 - 1x0 = 0 a31 = 1 - 1x1 = 0 c1 = -5 - 1(-5) = 0 
a12 = 0/1 = 0 a22 = 1 - 0x0 = 1 a32 = 2 - 0x1 = 2 c2 = -2 - 0(-5) = -2 
a13 = 1/1 = 1 a23 = 0 - 1x0 = 0 a33 = 0 - 1x1 = -1 c3 = 0 - 1(-5) = 5 
a14 = 0/1 = 0 a24 = 1 - 0x0 = 1 a34 = 0 - 0x1 = 0 c4 = 0 - 0(-5) = 0 
a15 = 0/1 = 0 a25 = 0 - 0x0 = 0 a35 = 1 - 0x1 = 1 c5 = 0 - 0(-5) = 0 
a16 = 3/1 = 3 a26 = 4 - 3x0 = 4 a36 = 9 - 3x1 = 6 c6 = 0 - 3(-5) = 15 
 
 
Q2 x1 x2 x3 x4 x5 b 
x1 1 0 1 0 0 3 - Primeira linha obtida 
x4 0 1 0 1 0 4 4/1 = 4 
x5 0 2 -1 0 1 6 6/2 = 3 O menor quociente indica a variável que sai da 
base: x5
Z 0 -2 5 0 0 1
5 
 
 
 Pivot = a32 = 2 
 O menor coeficiente na linha Z indica a varíavel x2 que entra na 
base 
No quadro temos: x1 = 3 
 x2 = 0, por não aparecer na base 
 
 Com esses valores na função objetivo temos Z = 15, que é exatamente o 
valor de Z obtido do quadro Q2. 
 
Q3 x1 x2 x3 x4 x5 b 
x1 1 0 1 0 0 3 
x4 0 0 ½ 1 -1/2 1 
x2 0 1 -1/2 0 ½ 3 Primeira linha obtida 
Z 2 0 7 0 0 21 SOLUÇÃO ÓTIMA: todos Cjs ≥ 0 
 
O quadro Q3 é solução ótima porque todos os coeficientes da linha Z ou são nulos 
ou positivos (Cjs ≥ 0). Temos: x1 = 3 e x2 = 3. Como Zmáx = 5x1 + 2x2, concluímos que o 
maior valor para Z é 21. 
 
Solução: 
x1 = 3 
x2 = 3 
Zmáx = 21 
 
 
 
 
 
 20
3.2 PROBLEMAS DE TRANSPORTES 
 
3.2.1-APRESENTAÇÃO DO PROBLEMA
 
 ORIGEM DESTINO 
 
MÁQ 1 X11 POSTO 1 
 
Xij=Quantidade transportada da 
origem i para o destino j. 
Cij=Custo relativo ao transporte no 
caminho ij. 
ai=Quantidade disponível na origem.
bj=Quantidade absorvida no destino 
j 
 C11
MÁQ 2 POSTO 2 
. . 
. . 
. X1n . 
MÁQ m C1n POSTO n 
 
 
3.2.2-FORMULAÇÃO GERAL DO PROBLEMA DE TRANSPORTE 
 
A função objetivo é dada pela expressão: 
 
Zmín = C11X11 + ...+ C1n + C21X21 +...+ C2nX2n + ...+ Cm1Xm1 +...+ CmnXmn
 
O algorítmo determina, portanto, Zmín. Como já foi visto, de houver necessidade da 
determinação de Zmáx, teremos: máx(Z) = mín(-Z). De acordo com o modelo apresentado, 
temos o seguinte conjunto de restrições: 
 
X11 + X12 + ... + X1n = a1 Xij ≥ 0 
X21 + X22 + ... + X2n = a2 i = 1, 2, ... , m 
........................................ j = 1, 2, ... , n 
Xm1 + Xm2 + ... + Xmn = am 
X11 + X21 + ... + Xm1 = b1
X12 + X22 + ... + Xm2 = b2 
........................................ 
X1n + X2n + ... + Xmn = bn 
 
 
 
3.2.3-PREPARAÇÃO DO QUADRO (TABLEAU) PARA UM PRBLEMA DE 
TRANSPORTE 
 
Para aplicação do algorítmo de TRANSPORTE usaremos quadros coma a disposição 
de acordo com o quadro genérico abaixo. Levando em consideração que . a bi j∑ ∑=
 
Então o problema consiste em fornecer uma matriz de custos de tranportes, o 
pontencial de origem (cada ai), os correspondentes valores de destino (cada bj), para se 
determinar com esses dados as quantidades que devem ser transportadas (Xij)¸ para que o 
custo total de transporte seja o mínimo possível. 
 
 21
 
Quadro genérico do Algorítmo de Transporte 
 
3.2.4-EXEMPLO BÁSICO DE UM PROBLEMA DE TRANSPORTE 
 
Neste exemplo consideremos 
o seguinte potencial de origem: 
 
a1 = 150 
a2 = 40 
a3 = 80 
 
O potencial de destino, com o 
mesmo valor de origem, tem a 
seguinte distribuição: 
 
b1 = 90 
b2 = 70 
b3 = 50 
b4 = 60 
 
O custo de tranporte é dada pela matriz: 
Com esses dados fornecidos 
estruturamos o QUADRO 1 e a partir 
daí aplicamos o agorítmo de 
TRANSPORTE. 
 
Usamos o algorítmo de busca da 
solução ótima - Método de 
Distribuuição Modificado (MODI). 
 
 P1 P2 P3 P4
M1 27 23 31 69 
M2 10 45 40 32 
M3 30 54 35 57 
 
 
Então, os quadros obtidos seguem a seguinte sequência: 
1 . Estrutura-se o quadro com solução inicial obtida, pelo canto noroeste, que tem a 
seguinte seqüência: 
a) Começar pela célula superior esquerda. 
b) Alocar nessa célula a maior quantidade permitida pela ofertae demanda 
correspondentes, considerando os valores já alocados. 
c) Seguir para célula da direita se houver alguma oferta restante evoltar ao passo ii. Caso 
contrário seguir para a célula inferior e voltar ao passo ii. 
 
Observação: O processo estará concluído quando a célula inferior direita for alcançada. 
 
 22
2. Calculam-se todos os Uijs e Vijs. Os C’ijs das variáveis básicas são iguais a zero. Arbritra-
se U1 = 0 e calcula-se os demais C’ijs. Se todos os C’ijs forem ≥ 0 PARE, solução ótima. 
Caso contrário , escolha a variável de menor C’ij paara entrar na base. Para o cálculo de 
C’ temos a seguinte expressão: 
 
C’ij = Cij - Ui - Vj 
 
- Não esquecer que a expressão Cij - Ui - Vj deve ser igualada a zero nas variáveis 
básicas. 
- Nas células com Xij ≥ 0 o novo coeficiente na função objetivo será igual a zero, 
correspondem as variáveis básicas. 
- Nas demais células, variáveis não-básicas, os coeficientes serão dados por: Cij - Ui - Vj. 
 
3. A partir da célula que contém a variável que entra na base, forme uma linha poligonal 
fechada cujos vértices sejam células de varáveis básicas e cujos ângulos internos sejam 
retos; na célula inicial põe-se um sinal de adição e alternam-sem a partir daí sinais de 
menos e mais nos vértices-células da linha poligonal fechada. A célula com sinal de 
menos, que contiver o menor valor, indicará a variável que sairá da base. 
 
4. A cada vértice-célula que tiver sinal mais, adiciona-se o valor da variável que sairá da 
base e a cada vértice-célula com sinal menos, subtrai-se. Voltar ao passo 2. 
 
 
 
Este exemplo apresentado está 
resolvido nesta seqüência de 
cinco quadro, seguindo o 
algorítmo descrito acima. 
 
O Quadro 5 é solução ótima pelo 
fato de todos os C’ serem ≥ 0. 
 
Multiplicando cada ai pelo Ui 
correspondente, no Quadro 
cinco temos a seuinte soma: S1 = 
0 + (-880) + 240 = - 660. 
Da mesma forma, multiplicando 
cada bj por cada Vj 
correspondente é obtida a soma S2 = 2430 + 1610 + 1550 = 8830. 
 
O cuto total mínimo (Zmín), passa a ser: Zmín = -660 + 8830 = 8190. Este valor é 
exatamente o somatório de cada Xij (cada quantidade transportada) pelo respectivo custo de 
transporte. Custo total = Zmín = X cij ij∑
 
 
 
 
Neste Quadro 4 temos um custo total 
igual a 8290. Este valor é obtido da 
seguinte forma: Z = 40(-17) + 80.8 + 
90.27 + 70.23 + 50.27 + 60.49 = 8290. 
 
 
 
 
 
 23
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
No Quadro 4 temos Z = 8240, valor 
este que além da forma anterior 
também pode ser obtido: Z = 80.27 + 
70.23 + 40.32 + 10.30 + 50.35 + 
20.57, ou seja, Z = . X cij ij∑
 
Obeserve que cada quadro obtido, o 
custo total é menor do que o anterior. 
 
 
 
 
 
 
 
 
 
Quadro 5, é SOLUÇÃO 
ÓTIMA, pois apresenta todos 
os C’ ≥ 0, consequentemente 
um custo total menor possível 
de 8190 unidades monetárias. 
 
 
 
 
Para que isto aconteça temos 
a seguinte disposição de 
transporte: 
 
 
 
P1 P2 P3 P4
M1 30 70 50 0 
M2 0 0 0 40 
M3 60 0 0 20 
 
 
EXERCÍCIO 
 
 24
1) Uma determinada empresa de transportes terrestres compra ovos nas granjas A, B, C, 
para vendê-los nas cidades 1, 2 e 3. São dados: 
 
a) Preço da dúzia de ovos (em u.m.): 
 Granja A: 40 e cidade 1:80 
 Granja B: 50 e cidade 2:100 
 Granja C: 60 e cidade 3:120 
 
b) Disponibilidade de ovos (dúzia): 
 Granja A: 40 
 Granja B: 30 
 Granja C: 20 
 
c) Consumo nas cidades (dúzias): 
 Cidade 1: 30 
 Cidade 2: 40 
 Cidade 3: 20 
 
 
Custo de transporte: 
(u.m./dúzia) 
 
 1 2 3 
A 10 8 9 
B 12 6 5 
C 2 X 4 
 
Não existe estrada ligando a granja C à 
cidade 2. Quanto a empresa deve 
transportar p/ cada cidade, p/ lucro 
máximo? Qual o lucro? 
 
 
 
 
 
 25
3.3. PROBLEMAS DE DESIGNAÇÃO 
 
3.3.1 - INTRODUÇÃO 
 
 O problema de DESIGNAÇÃO é um caso particular de TRANSPORTE e 
consequentemente de programação linear. 
 
 O problema de designação se caracteriza quando se tem de distribuir uma 
determinada quantidade de itens (homens, máquinas, equipamentos, recursos financeiros) 
em uma quantidade igual de localizações ou tarefas. 
 
Seja a matriz abaixo: 
 
 
MATRIZ EFICIÊNCIA 
 
As células indicam (podem indicar) o tempo que 
cada homem gasta na execução de cada uma das 
tarefas. Os valores poderiam também indicar 
custos, grau de desempenho, outros. 
 
O modelo de designação encontra a rebi-
unívoca homens-tarefa, isto é, minimiza o 
volume de mão-de-obra. 
 
OPERÁRIOS 
 
 I II III IV 
A 5 24 13 7 
B 10 25 3 23 
C 28 9 8 5 
D 10 17 15 3 
 
 
3.3.2 - ALGORITMO DA DESIGNAÇÃO 
 
PASSO 1 - Escolher para cada linha “i” o menor elemento da linha. Subtrair de todos os 
elementos da linha, o menor. 
 
PASSO 2 - Escolher para cada coluna “j” o menor elemento da coluna “j” o menor 
elemento da coluna. Subtrair de todos os elementos da coluna, o menor. 
 
PASSO 3 - Traçar linhas verticais e (ou) horizontais, o mínimo possível, de forma que 
todos os zeros fiquem cortados: 
 
PROCEDIMENTO: 
 
 - Traça-se a 1a linha, na linha ou coluna que tiver o maior números de zeros. 
Procede-se, seguidamente, para as linhas e (ou) colunas levando-se em conta sempre o 
maior número de zeros (zeros já cortados não contam para o corte seguinte); 
 
 Se o número mínimo de linhas for igual à ordem da matriz eficiência, pare, 
solução ótima, caso contrário siga para o PASSO 4. 
 
PASSO 4 - Escolha o menor dentre as células não cortadas, subtraia das células não 
cortadas, o menor, adicione as células intercessão de linhas, o menor, siga 
para o PASSO 3. 
 
OBSERVAÇÃO: 
 
 a) Ao atingir o ótimo, a designação ocorrerá nas células que contém zeros. Procura-
se a linha e (ou) coluna que tenha o menor números de zeros; atribui-se a célula que contém 
o zero a indicação “X”. Eliminam-se a linha e a coluna atribuídas. Repete-se o 
procedimento. 
 
 
 26
 
 b) Para maximização, antes de tudo, determina-se o complemento da matriz em 
relação à célula de maior valor. 
 
3.3-ILUSTRAÇÃO 1: MINIMIZAÇÃO 
 
Q1 A B C D E F 
II 8 7 6 9 5 6 
II 10 4 7 8 8 7 
III 11 6 9 8 9 8 
IV 9 8 10 13 8 11 
V 7 9 8 7 9 7 
VI 8 9 10 11 13 12 
PASSO 1 - Subtrai-se o menor de cada linha, da 
mesma. 
 
 
 
Q2 A B C D E F 
I 3 2 1 4 0 1 
II 6 0 3 4 4 3 
III 5 0 3 2 3 2 
IV 1 0 2 5 0 3 
V 0 2 1 0 2 0 
VI 0 1 2 3 5 4 
PASSO 2 - Subtrai-se o menor de cada coluna, da 
mesma. 
 
 
 
 
 
 
 
 
5 linhas traçadas (cortes) 
 
 
Q3 A B C D E F 
I 3 2 0 4 0 1 
II 6 0 2 4 4 3 
III 5 0 2 2 3 2 
IV 1 0 1 5 0 3 
V 0 2 0 0 2 0 
VI 0 1 1 3 5 4 
 
 
 
5 linhas traçadas (cortes) 
 
Q4 A B C D E F 
I 3 5 0 4 1 1 
II 5 0 1 3 4 2 
III 4 0 1 1 3 1 
IV 0 0 0 4 0 2 
V 0 3 0 0 3 0 
VI 0 2 1 3 6 4 
Menor dos não cortados = 1. Subtraem-se dos não 
cortados o valor 1 e adiciona-se o mesmo às células 
intercessão. 
.Como o número de linhas traçadas (cinco) é menor 
do que a ordem da matriz (6 por 6), continuamos em 
busca da solução ótima. 
 
 27
 
 
Q5 A B C D E F 
II 2 3 0 3 0 0 
II 4 0 1 2 3 1 
III 3 0 1 0 2 0 
IV 0 1 1 4 0 2 
V 0 4 1 0 3 0 
VI 0 3 2 3 6 4 
 
 
 
 
 
 
 
 
 
 
 
 
PROCESSO DE DESIGNAÇÃO: 
 
Escolher linha e (ou) coluna com menor número de zeros. 
 
LINHA 2 (um zero) 
POSIÇÃO ATRIBUÍDA: X22
- Eliminadas linha 2 e coluna 2 
 
LINHA 4 (um zero) 
POSIÇÃO ATRIBUÍDA: X45
- Eliminadas linha 4 e coluna 5 
 
LINHA 6 (um zero) 
POSIÇÃO ATRIBUÍDA: X61
- Eliminadas linha 6 e coluna 1 
 
LINHAS 3 e 5 
COLUNAS 4 e 6 
Com dois zeros permitem 2 alternativas 
 
ATRIBUIR X34 e X56
ou 
ATRIBUIR X54 e X36
 
QUADRO SOLUÇÕES POSSÍVEIS: 
 
 
S1 A B C D E F 
II X 
II X 
III X 
IV X 
V X 
VI X 
 Zmín = 8 + 4 + 6 + 8 + 7 
 
 Zmín =41 (ver custos iniciais) 
Número de linhas traçadas (cortes) é igual a 6, 
SOLUÇÃO ÓTIMA. 
 28
 
OU 
S2 A B C D E F 
II X 
II X 
III X 
IV X 
V X 
VI X 
 Zmín = 8 + 4 + 6 + 7 + 8 
 
 Zmín = 41 (ver custos iniciais) 
 
OBSERVAÇÃO: Como o algorítimo de designação fornece Zmín, caso se queira calcular 
Zmáx, incialmente determina-se o complemento da matriz, ou seja, do 
maior elemento matricial, subtrai-se todos, então: máxZ =mín(-Z). 
 
 
 
 
EXERCÍCIO 
 
 
01) Resolva os seguintes problemas de DESIGNAÇÃO tanto para Zmáx como para Zmín: 
 
a) 
 1 2 3 4 5 
A 12 8 7 15 6 
B 7 9 17 14 10 
C 9 6 12 6 7 
D 7 6 14 6 10 
E 9 6 12 10 4 
 
 
 
b) 
 1 2 3 4 5 
A 9 15 6 14 18 
B 7 5 10 4 13 
C 11 14 13 10 14 
D 19 22 15 26 24 
E 12 8 10 9 13 
 
 
 
c) Zmín e Zmáx: 
 
 
 
 1 2 3 4 
A 25 20 15 10 
B 50 40 30 5 
C 40 35 20 15 
D 40 50 15 10 
 
 
 
02) O diretor de uma escola deseja inscrever quatro alunos num concurso de matemática 
que engloba os seguintes assuntos: Álgebra, Análise, Lógica e Geometria. Somente 
 29
um aluno pode ser inscrito em cada assunto e nenhum aluno pode ser inscrito em mais 
de um assunto porque as provas do concurso ocorrerão simultaneamente. Para isso ele 
seleciona seus quatro melhores alunos, A, B, C, D, e lhes aplica os mesmos exames 
cobrindo as quatro áreas do concurso. O quadro abaixo indica o número de pontos que 
foi deduzido da nota de cada aluno em cada uma das áreas: 
 
 
 
 
 Álgebra Análise Lógica Geometria 
A 7 10 6 3 
B 8 7 8 1 
C 4 9 3 5 
D 5 4 6 9 
 
 Qual aluno deve ser selecionado para cada um dos assuntos do concurso? 
 
3) Uma empresa vende produtos em quatro regiões e possui quatro vendedores para serem 
destacados, um para cada região. As regiões não são igualmente ricas e apresentam o 
seguinte potencial de vendas: 
 
Região I 60.000,00 u.m. 
Região II 50.000,00 u.m. 
Região III 40.000,00 u.m. 
Região IV 30.000,00 u.m. 
 
 
 
Os vendedores, por outro lado, não são igualmente hábeis e as suas eficiências, que 
refletem a capacidade de atingir o mercado potencial da região, são dadas pelo quadro que 
se segue: 
 
 I II III IV 
A 0,7 0,7 0,7 1,0 
B 0,8 0,8 0,8 1,0 
C 0,5 0,5 0,5 1,0 
D 1,0 0,4 1,0 0,4 
 
 30
4 - TEORIA DAS FILAS 
 
 
4.1 - INTRODUÇÃO 
 
A teoria das filas envolve o estudo matemático das filas ou linhas de espera. A 
formação de filas excede a capacidade de fornecer aquele serviço. Os modelos 
matemáticos se tornam complexos porque normalmente utilizam ferramentas que 
envolvem um tratamento estatístico ou estocástico. Fornecer uma capacidade excessiva de 
atendimento gera ociosidade, fornecer um atendimento deficitário gera insatisfação, perda 
de clientes, perda de produção; tudo isto leva a uma relação muito forte entre as condições 
de um sistema de filas e a minização dos custos no atendimento do mesmo. 
 
O estudo de sistemas de filas tem larga utilidade: 
 
a) No planejamento e controle da produção. 
b) No dimensionamento de sistemas de armazenamento. 
c) Nos sistemas de transportes. 
d) Nos sistemas de tráfego (rodo-porto-aéreo-ferroviário). 
e) Na manutenção de máquinas. 
f) em qualquer sistemas em que seja provável a formação de filas para determinado 
atendimento. 
g) Nos sistemas de saúde. 
h) Sistemas comerciais. 
 
 
SISTEMA DE FILAS 
 
 
 
 MECANISMO 
Potencial clientes CLIENTES 
 de F I L A DE 
clientes chegando ATENDIDOS 
 ATENDIMENTO 
 
 
 
 
 
Observações: 
 
 a) Potencial de clientes pode ser finito ou infinito; 
 b) Os clientes podem chegar um de cada vez ou em blocos; 
 c) A fila pode ter capacidade finita ou infinita; 
 d) O mecanismo de atendimento pode ter um posto ou vários, paralelos; 
 e) O sistema engloba os clientes da fila e os clientes em atendimento. 
 
TERMINOLOGIA E NOTAÇÃO 
 
L = número médio de clientes no sistema; 
LQ = número médio de clientes na fila; 
W = número médio de permanência de um cliente no sistema; 
WQ = número médio de permanência de um cliente na fila; 
Pn = probabilidade de ter exatamente “n” clientes no sistema ou porcentagem do tempo em 
que o sistema fica com “n” clientes; 
 31
P(w>t) = probabilidade do tempo de espera no sistema ser maior que o tempo “t”. 
 
 
PROCESSO DE CHEGADA DOS CLIENTES NA FILA E PROCESSO DE 
ATENDIMENTO 
 
- As funções que definem os processos de chegada e atendimento são variáveis aleatórias. 
A maioria dos problemas práticos têm seus processos de chegadas regidos por uma 
distribuição semelhante a de POISSON e os processos de atendimento, semelhante a uma 
distribuição EXPONENCIAL. 
 
 
4.2 - A DISTRIBUIÇÃO DE POISSON 
 
 Uma variável aleatória tem uma distribuição de Poisson se sua função de 
probabilidade for dada por: 
P n
e
k
k k
( )
!
=
−λ λ
 send k = 0, 1, 2, 3, 4,... 
 
Onde λ é uma constante maior do que zero. 
 
DISTRIBUIÇÃO DE POISSON 
MÉDIA λ 
VARIÂNCIA λ 
 
4.3 - EXERCÍCIO 
 
 
DISTRIBUIÇÃO DE POISSON 
 
1) Numa rua passam em média 2 carros por minuto. Calcular a probabilidade de que em 2 
minutos, passem 
 
a) exatamente 4 carros 
b) mais de 4 carros 
 
 
2) Uma máquina produz tela de arame em rolos de 1m de largura. Cada 10 m corridos de 
tela apresentam em média 5 defeitos. Pensa-se reformar essa máquina para permitir que 
ela produza rolos de 1,20m de largura. Qual a probabilidade de uma amostra de 7,5 m de 
comprimento da nova produção apresentar: 
 
a) 9 defeitos 
b) 10 ou mais defeitos 
 
3) Os números de defeitos de solda e acabamento de uma certa peça são variáveis de 
Poisson independentes, de médias respectivamente 1,2 e 0,8. Calcular a probabilidade 
de que uma peça qualquer, não seja perfeita. 
 
 
4) X é uma variável com distribuição de POISSON de média igual a 10. Calcule: 
 a) P (k > 6) b) P(2 ≤ k ≤ 4) 
 c) P(k ≤ 8 ) d) P(6 ≤ k ≤ 12) 
 
 
 32
5) O número de componentes defeituosos por aparelho de televisão montado tem sido 
observado como uma distribuição de Poisson com média α = 2. Se 5 aparelhos são 
testados, qual é a probabilidade de que o número de componentes defeituosos ultrapasse 
10? 
 
 
6) Numa fábrica determinado produto tem uma demanda que segue uma distribuição de 
Poisson com média diária α = 25 unidades. Qual deve ser a quantidade mantida em 
estoque para que não haja falta em 95% dos casos? 
 
 
7) Um sinal luminoso de tráfego tem período de 1 minuto. Uma fase do ciclo de operação 
consiste em parar o tráfego de veículos a travessia de pedestres tendo em vista que os 
pedestres chegam aleatoriamente a razão de 150 por hora. Deseja-se decidir se a fase 
deve ser automática ou manual. Qual a probabilidade de durante 1 minuto não haver 
pedestres para ultrapassar? 
 
 
4.4- DISTRIBUIÇÃO EXPONENCIAL 
 
 
 Diz-se que uma variável aleatória tem uma distribuição EXPONENCIAL quanto: 
 
 
e k−λ se k ≥ 0 
 
P n( ) = 
0 se k < 0 
 
DISTRIBUIÇÃO EXPONENCIAL 
MÉDIA 1/λ 
VARIÂNCIA 1/λ2
 
4.5-EXERCÍCIO 
 
DISTRIBUIÇÃO EXPONENCIAL 
 
 
1) Um determinado componente mecânico tem sua vida útil ajustada a uma distribuição 
exponencial com média igual a 1000 dias. Calcule a probabilidade de uma peça durar 
mais de 1000 dias. 
 
 
2) Certo tipo de parafuso tem uma vida útil que segue uma distribuição exponencial com 
vida média de 100 horas, cada parafuso tem um custo de 10 U.M. e, s e durar menos de 
200 horas, existe um custo adicional de 8 U.M.. 
 
a) Qual a probabilidadede um parafuso durar mais de 150 horas? 
b) Foi proposta a compra de uma outra marca que tem uma vida média de 200 horas e 
custo de 15 U.M.. Considerando também a incidência do custo adicional, deve ser feita 
a troca das marcas? 
 
3) A duração de certo tipo de condensador tem distribuição exponencial com média de 200 
horas. Qual a proporção de condensadores que duram. 
 
a) menos de 100 horas? 
 33
b) mais de 500 horas? 
c) Entre 200 e 400 horas? 
 
 
4) Uma companhia fabrica lâmpadas com uma produção média de 100 horas e distribuição 
exponencial. 
 
a) Qual deve ser a garantia do fabricante para repor apenas 5% da produção? 
b) Qual a probabilidade de uma lâmpada durar de 163 a 185 horas? 
 
5) Um mecânico supervisiona uma máquina cujo intervalo de tempo entre enguiços segue 
uma distribuição exponencial com taxa de um enguiço a cada 20 horas. Por quanto 
tempo o mecânico não enguiça enquanto ele se ausenta? 
 
 
6) A vida da lâmpada de um projetor de cinema é completamente aleatória com média de 
100 horas. Os fabricantes desejam oferecer uma garantia por estas lâmpadas. Por 
quantas horas as lâmpadas podem ser garantidas, de modo a se ter uma probabilidade de 
0,95 de que elas funcionem pelo menos o número de horas garantido? 
 
7) O papel fabricado por um máquina rasga-se durante o processo de fabricação, 
aleatoriamente, a uma razão média de um ruptura a cada 40 minutos. Se foi observado 
que o papel não rasgou nos últimos 20 minutos, qual a probabilidade de que ele venha a 
se rasgar nos próximos 20 minutos? 
 
 
8) Uma firma especializada em reparos de prensas atende a serviços de emergência. Cada 
trabalho demora 4 horas para ser concluído e o tempo entre a chegada de ordens 
sucessivas e distribuído exponencialmente com média de 5 dias. Por causa das 
condições de emergência, os fregueses devem ser atendidos imediatamente. Calcule as 
probabilidades de que: 
 
a) Não haja demanda de serviços enquanto um determinado reparo estiver em execução. 
b) Depois de concluída uma tarefa se passem no mínimo seis dias seguidos sem trabalho. 
 
 
9) Considere uma loja na qual os clientes cheguem ao acaso numa média de 30 por hora. 
Que percentagem de intervalos de tempo entre chegadas sucessivas será: 
 
a) maior do que 2 minutos? 
b) menor do que 4 minutos? 
c) entre 1 e 3 minutos? 
 
4.6 - SISTEMAS 
 
I) Modelo 
 P / E / 1 / ∞ 
 capacidade de fila ilimitada 
 um servidor 
 processo de atendimento EXPONENCIAL 
 processo de chegada POISSON 
 
 
FORMULÁRIO 
 
 
 34
 
1) Número médio de clientes no sistema 
 
L = −
λ
µ λ 
 
 
2) Número médio de clientes na fila 
 
LQ = −
λ
µ µ λ
2
( )
 
3) Tempo médio de permanência de um cliente no sistema 
 
W = −
1
µ λ 
 
4) Tempo médio de permanência de um cliente na fila 
 
QQ = −
λ
µ µ λ( ) 
 
5) Probabilidade de ter “n” clientes no sistema 
 
P n Pn( ) ( )= λµ 0 
 
 
P0 1= − λµ 
 
W WQ= + 1µ 
 
L =λW 
 
LQ = λWQ
 
 
 
6) Probabilidade do tempo de espera na fila ser maior do que o tempo t (tempo qualquer) 
 
P w t e t( ) ( )> = −λ µ 
 
 
 
 
 
 
 
II) Modelo 
 P / E / S / ∞ 
capacidade de fila ilimitada 
número de servidores qualquer 
processo de atendimento EXPONENCIAL 
 35
processo de chegada POISSON 
 
 
 
 
 
FORMULÁRIO 
 
1) Probabilidade de ter zero clientes na fila 
 
 
P
n S
S
n S
n
S
0
0
1
1
1
=
+
−=
−∑ ( )!
( )
!( )
λ
µ
λ
µ
λ
µ
 
 
 
2) Probabilidade de n clientes na fila 
 
P
n
Pn
n
=
( )
!
.
λ
µ
0 se 0 ≤ n ≤ S 
 
 
P
S S
Pn
n
n S= −
( )
!
λ
µ
0 se n ≥ S 
 
 
3) Número médio de clientes na fila 
 
 
 L
P
S
S
S
Q
S
=
−
0
21
( ) ( )
!( )
λ
µ
λ
µ
λ
µ
 
 
4) Número médio de clientes no sistema 
 
L LQ= + λµ 
 
5) Tempo médio de permanência de um cliente na fila 
 
W
L
Q
Q= λ
 
 
 
 
6) Tempo médio de permanência de um cliente no sistema 
 
 36
W WQ= + 1µ 
 
 
Probabilidade de n ≥ S 
 
 
P n
P
S
S
S
S
( )
( )
!( )
=
−
0
1
λ
µ
λ
µ
 
 
 
P W t e
P e
S
S
S
t
S t S
( ) [
( ) ( )
!( )( )
]
( )
> = +
−
− − −
−
− − −
µ
µ λµλ
µ
λ
µ
λ
µ
1
1
1 1
0
1
 
 
 
4.7 - APLICAÇÃO (Dimensionamento de uma equipe de trabalho) 
 
Numa fábrica o número de quebra observados é de 3 unidades/hora segundo uma 
distribuição de POISSON. A empresa dispõe de 2 técnicos especializados que cuidam 
desses defeitos. O tempo de atendimento segue uma distribuição EXPONENCIAL com 
taxa média de 30 minutos/unidade. As máquinas normlmente operam 8 hora/dia. O custo 
médio por conserto é de 2000 u.m./hora e o lucro perdido por máquina parada é de 2500 
u.m./hora, determinar o número ótimo de técnicos. 
 
Do enunciado concluímos que λ = 3 unidades/hora e µ = 2 unidades/hora 
 
O CUSTO MÉDIO DIÁRIO (CMD) = (8)(L)(2500) +(8)(S)(2000) 
 
Com esses dados podemos elaborar o quadro: 
 
S S=2 S=3 S=4 
P0 0,143 0,210526 0,2040816 
LQ 1,93 0,236842 0,047093 
L 3,43 1,7236842 1,547093 
CMD 100.541,43 82.473,68 94.941,86 
 
Verifica-se que o ideal é que o número de técnicos seja de TRÊS (S=3), que tem 
um CMD menor do que S=2 voltando a aumentar para S ≥ 4 técnicos. 
 
 
BIBLIOGRAFIA 
 
 
[01] OPERATIONS RESEARCH 
 Frederick Hillier / Geral Lieberman 
 Editora: Holden Day, INC 
 
[02] PESQUISA OPERACIONAL 
 Albert Von Ellenrider 
 Editora: Almeida Neves Ltda 
 37
 
[03] PESQUISA OPERACIONAL 
 Pierre Jaccques Ehrlich 
 Editora: Atlas S.A. 
 
[04] PESQUISA OPERACIONAL 
 Abelardo de Lima Puccini 
 Editora: LTC S.A. 
 
[05] LINEAR PROGRAMMING 
 G. Hadley 
 Editora: Addison - Voesley Co. 
 
[06] PESQUISA OPERACIONAL E TRANSPORTES 
 Antônio Galvão Novaes 
 Editora: EDUSP / McGraw-Hill do Brasil S.A. 
 
[07] ADMINISTRAÇÃO DE ESTOQUES 
 Paulo Sérgio Gonçalves / Enrique Schwember 
 Editora: INTERFERÊNCIA 
 
[08] PROGRAMAÇÃO LINEAR 
 Luzia Kazuko Yoshida 
 Editora: Atual Editora 
 
[09] APLICAÇÕES DE PESQUISA OPERACIONAL (Vol. I e II) 
 Victor Mirshawaka 
 Editora: Novel 
 
[10] PESQUISA OPERACIONAL EM ENGENHARIA, ECONOMIA 
 E ADMINISTRAÇÃO 
 Tamio Shimizu 
 Editora: Guanabara Dois 
 
[11] PROGRAMAÇÃO LINEAR 
 A. Barsov, A. Okhlopkova 
 Editora: Mir Moscou 
 
[12] APOSTILA 
INTRODUÇÃO À PESQUISA OPERACIONAL 
Prof. Dr. Domingos Fernandes Campos - DEPT/UFRN 
Módulo I 
 
[13] INTRODUÇÃO À PESQUISA OPERACIONAL 
Hillier/Lieberman 
1a Edição em Português 
Editora Campus Ltda 
Editora da Universidade de São Paulo 
 
[14] PEQUISA OPERACIONAL 
Russell Ackoff / Maurice W. Sassienei 
Coleção Universitária de Administração 
 
 38
	Produto