PESQUISA OPERACIONAL 1

Prévia do material em texto

Pesquisa Operacional I 
1 , 
Pesquisa Operacional I 
Edison Alves Portela Junior 
1ª
 e
di
çã
o 
Pesquisa Operacional I 
11 
Programação Matemática 1 
Pesquisa Operacional I 
 
12 
 
Nesta unidade, faremos uma análise do contexto sócio histórico que propiciou 
o seu surgimento: O que é pesquisa operacional? A partir daí poderemos entender 
melhor o seu conceito e o seu objeto de estudo. 
 
Objetivos da unidade: 
Analisar a condição da pesquisa operacional como ferramenta na tomada de 
decisão e o uso da programação linear como solução. 
 
Plano da unidade: 
 O que é a Pesquisa Operacional? 
 Problemas de otimização. Exemplos. 
 Programação Linear. 
 Formulação do problema 
 Convenção da solução 
 
Bons estudos! 
 
Pesquisa Operacional I 
 
13 
 
O que é a Pesquisa Operacional? 
 
A origem histórica da pesquisa operacional (PO) foi realizada por indivíduos 
como Charle Baggage. Sua pesquisa sobre o custo de transporte e triagem do 
correio para a "Penny Post" da Inglaterra universal em 1840, e estudos sobre o 
comportamento dinâmico de veículos ferroviários em defesa de bitola larga do 
GWR. Percy Bridgman trouxe a pesquisa operacional para dar suporte sobre 
problemas em física na década de 1920 e, mais tarde, tentar estender estes para as 
ciências sociais. 
A Pesquisa operacional moderna teve origem na Estação de Pesquisa Bawdsey 
no Reino Unido em 1937 e foi o resultado de uma iniciativa do superintendente da 
estação, AP Rowe. Rowe concebeu a ideia como um meio para analisar e melhorar 
o funcionamento do sistema de radar de alerta, nos seus primórdios, no Reino 
Unido, Chain Home (CH). Inicialmente, ele analisou o funcionamento do 
equipamento de radar e de suas redes de comunicação, expandindo 
posteriormente para incluir o comportamento do pessoal de operação. Isto revelou 
limitações não reconhecidas da rede CH e permitiu medidas corretivas a tomar. 
O termo pesquisa operacional foi atribuído a algumas iniciativas militares na 
Segunda Guerra Mundial. Por conta do esforço requerido pela guerra na alocação 
de recursos escassos às várias operações militares e às atividades dentro de cada 
operação de uma maneira efetiva. Várias seções de pesquisa operacional foram 
estabelecidas nas forças armadas britânicas. Logo depois, esses esforços similares 
foram empreendidos nos Estados Unidos. Muitos cientistas foram reunidos para 
aplicar uma abordagem científica a problemas estratégicos e táticos. Esses 
cientistas foram chamados a realizar pesquisas operacionais militares, daí vem o 
nome. 
Um passo natural tomado foi estender o sucesso da Pesquisa Operacional nos 
esforços de guerra para as organizações civis. A indústria pós-guerra havia crescido 
muito e se deparava com os problemas causados pela crescente complexidade das 
organizações. Vale lembrar que após a guerra houve inúmeros movimentos para a 
reconstrução dos países arrasados. Os problemas que apareceram durante a guerra 
Pesquisa Operacional I 
 
14 
e a complexidade das organizações na reconstrução dos países eram muito 
semelhantes, porém em um contexto diferente. Em 1948, o Massachusetts Institute 
of Tecnology (MIT) instituiu o primeiro programa formal de estudos em Pesquisa 
Operacional para campos não militares. A “idade de ouro” da PO vai de 1945 até 
meados da década de 1970, devida à rápida expansão. 
Dois fatores foram cruciais para o crescimento da PO naquele período: O 
primeiro foi o avanço na melhoria nas técnicas de PO e na formulação dos 
problemas - Ex. o método simplex para resolver problemas de programação linear. 
O segundo foi a popularização dos computadores. 
 
Problemas de otimização 
 
A construção de modelos. 
O desafio da PO é transformar um problema real de produção ou de processo 
em um modelo matemático que reproduza fielmente essa realidade; destacar as 
variáveis que se queira controlar - variáveis essas que estão sujeitas a restrições de 
ordem técnica; validar o modelo matemático e implementá-lo. Para facilitar nosso 
estudo vamos dividir esse problema em etapas: 
 Definição da situação-problema; 
 Formulação de um modelo quantitativo; 
 Resolução do modelo e encontro da melhor solução; 
 Consideração de fatores imponderáveis; 
 Implementação da solução. 
 
Agora vamos ver cada uma destas etapas. 
 
Pesquisa Operacional I 
 
15 
Definição da situação-problema 
Nessa fase os gerentes do projeto deverão discutir o problema de forma mais 
clara e coerente, definir o escopo do projeto, definir os objetivos a serem 
alcançados e quais são os possíveis caminhos a seguir. 
As limitações técnicas devem ser levantadas e as relações deste sistema com 
os demais da empresa ou do ambiente externo. Sejam micro clientes ou micro 
fornecedores internos da corporação e stakeholders de outras organizações, com a 
finalidade de validar esse modelo. 
 
Formulação de um modelo quantitativo 
Em PO os modelos quantitativos são modelos matemáticos formados por um 
conjunto de equações e inequações. 
A eficiência do modelo é medida pela função objetivo, que pode ser de 
maximização ou de minimização. Por exemplo, maximizar o lucro ou minimizar o 
custo. Quanto melhor o valor obtido na função objetivo para cada solução 
proposta, melhor a eficiência do modelo: A solução ótima. 
 
Resolução do modelo e encontro da melhor solução 
Variáveis controladas ou de decisão: são aquelas cujo valor está sob o controle 
do administrador. Cabe a ele decidir um particular valor a cada uma dessas 
variáveis. Numa programação de produção uma possível variável a ser controlada 
pode ser a quantidade a ser produzida em um período de tempo, o que é 
competência do administrador. 
Variáveis não controladas: são aquelas cujos valores são arbitrados por 
sistemas fora do controle do administrador. Custos de produtos ou insumos, 
demanda de produtos, preços de mercado, são alguns exemplos desse tipo de 
variável. 
Podemos afirmar que um bom modelo é aquele que tem desempenho que 
mais chega próximo da realidade. O modelo deve ser rodado sempre, comparado 
com a realidade e revisado a fim de chegar o mais próximo possível dessa 
Pesquisa Operacional I 
 
16 
realidade. O modelo se torna mais fiel à realidade, incorporando características, 
com a adição de variáveis. 
Consideração de fatores imponderáveis 
Por outro lado, existem fatores que podem ser importantes, mas são difíceis de 
quantificar. O comportamento humano é um deles. A interação homem-máquina 
também. Faz-se necessário estimar o impacto desses fatores na solução que foi 
gerada pelo modelo matemático. Providências preliminares devem ser tomadas 
visando esses fatores. 
Implementação da solução 
Essa é a fase final. Deve ser apresentado ao administrador. A implantação deve 
ser acompanhada observando o comportamento do sistema com a solução 
adotada. Novos ajustes serão requeridos. É desejável que nessa fase do processo as 
pessoas que serão atingidas pelas mudanças estejam envolvidas. 
Figura 1.1 – Processo de solução de um problema de Pesquisa Operacional. 
 
Fonte: Adaptado de Moreira (2004 apud Moreira, 2010). 
Figura 1.1 – Processo de solução de um problema de Pesquisa Operacional. 
Pesquisa Operacional I 
 
17 
 
Programação Linear 
 
A programação linear é um dos mais populares modelos matemáticos 
estruturados utilizados para resolver problemas que apresentam variáveis que 
podem ser medidas e cujos relacionamentos podem ser expressos por meio de 
equações e/ou inequações lineares. As aplicações podem ser em vários campos das 
áreas científicas ou sociais, tais como administração da produção, análise de 
investimento, controle de estoque, economia, logística e etc. 
O modelo matemático de programações linear, que de agora em diante 
denominaremos de Problema de Programação Linear (PPL) é constituído de uma 
função objetivo linear; de restrições técnicas representadas por um grupo de 
equaçõese/ou inequações também lineares; e da restrição matemática de não 
negatividade. 
Otimizar: 
),,,()( 21 nxxxfXf  – Função objetivo 
Sujeito a: 

















mnm
n
n
b
b
b
xxxg
xxxg
xxxg





2
1
21
212
211
),,,(
),,,(
),,,(
 
Onde: 
nnn xcxcxcxxxfXf   221121 ),,,()( 
),,1(
),,,( 33221121
mi
xaxaxaxaxxxg niniiini




 
 
Pesquisa Operacional I 
 
18 
 
n é o número de variáveis do problema 
m é o número de restrições do problema 
i é o índice de determinada restrição ),,1( mi  
j é o índice de determinada variável ),,1( nj  
jc é o coeficiente (constante) da variável jx , da função objetivo 
ija é o coeficiente (constante) na i-ésima restrição e da variável jx 
ib é constante da i-ésima restrição 
 
Um problema de programação linear está na sua forma padrão, quando o 
problema de otimização linear tiver as seguintes características: 
 A função objetivo deve ser minimizada ou maximizada; 
 As restrições do problema são definidas por um sistema de equações e/ou 
inequações lineares; 
 As condições de não negatividade de todas as variáveis de decisão 
complementam as restrições do problema. 
 
Matematicamente, podemos representar um problema na forma-padrão por: 
nnxcxcxcMaxZ  2211 
S.R. 
11212111 bxaxaxa nn   
0,,, 21
2211
22222121







xx
bmxaxaxa
bxaxaxa
nmnmm
nn
 
Pesquisa Operacional I 
 
19 
 Ou na forma reduzida: 
j
n
j j
xcMaxZ   1 
S.R. 
ij
n
j ij
bxa  1 ),,1( mipara  
0,,, 21 nxxx  
Agora iremos introduzir alguns termos: 
 Solução: qualquer valor obtido dentro do domínio da função objetivo, 
)(Xf , para as variáveis de decisão; 
 Solução viável: são soluções que satisfaçam todas as restrições; 
 Solução ótima: uma solução viável que tenha o melhor valor da função 
objetivo, )(Xf , isto é, que maximiza ou minimiza a função objetivo, 
podendo ser única ou múltipla; 
 Proporcionalidade: o valor da função objetivo é diretamente proporcional 
ao valor de cada variável de decisão. 
 
Formulação do Problema 
 
Não há uma regra fixa para a construção do modelo matemático. Mas a 
maioria dos problemas de programação linear (PPL) segue um roteiro que norteia o 
raciocínio. Veremos a seguir um roteiro básico em quatro etapas: 
1.Definir as variáveis de decisão ),,1( njxj  . Se estivermos estudando 
uma programação da produção, as variáveis de decisão podem representar as 
quantidades produzidas de produtos; se for uma programação de investimento, as 
variáveis representarão o tipo de portfólio escolhido. 
Pesquisa Operacional I 
 
20 
2.Definir a função objetivo da tomada de decisão. Que pode ser maximizar 
lucro, minimizar custos e etc. Ela é uma expressão formada por uma combinação 
linear das variáveis de decisão. 
3.Definir as restrições técnicas as quais estará sujeito. Como por exemplo, 
quantidade em estoque; homem-hora disponível na produção; 
4.A não negatividade. Sempre. 0,,, 21 nxxx  
 
Exemplo 1.1: 
Na fábrica de Brinquedos Eletrônicos X-Playhouse, são produzidos dois tipos 
de brinquedos: B1 e B2. O setor de contabilidade e custos informa que o lucro 
unitário do brinquedo B1 é de R$ 20,00 e do brinquedo B2 é de R$ 35,00. Na linha de 
produção o brinquedo B1 consome 2 horas e o brinquedo B2 consome 4 horas de 
trabalho. Essa linha de montagem tem 24 horas de trabalho disponíveis por dia. 
Sabe-se ainda que a demanda esperada pelo brinquedo B1 é de 8 unidades e de B2 
é de 4 unidades por dia. Como o engenheiro de produção da fábrica Brinquedos 
Eletrônicos X-Playhouse, monte o plano de produção de forma que o lucro seja 
maximizado. 
 
Solução: 
1. Comece definindo as variáveis de decisão, ou seja, as quantidades a 
serem produzidas de cada brinquedo. 
1x = quantidade de B1 a produzir; 
2x = quantidade de B2 a produzir; 
2. Formule a função objetivo que irá maximizar o lucro da empresa. 
O objetivo é maximizar o lucro, que pode ser calculado da seguinte 
forma: 
Lucro auferido com a venda de B1: 20 x 1x (lucro por unidade de B1 x 
quantidade produzida de B1). 
Pesquisa Operacional I 
 
21 
Lucro auferido com a venda de B2: 35 x 2x (lucro por unidade de B2 x 
quantidade produzida de B2). 
Então o lucro total obtido será: 2121 3520);( xxxxL  
Objetivo: 2121 3520);( xxxxLMax  
 
3. Sujeito às restrições técnicas: 
4
8
2442
2
1
21



x
x
xx
 
4. A não negatividade. 
0, 21 xx 
 
Convenção da solução 
 
A solução de um problema de programação linear, P.P.L., pode ter uma única 
solução ótima ou pode ter infinitas soluções ótimas, como veremos nos próximos 
capítulos. 
A função objetivo pode ser de maximização, por exemplo, maximizar o lucro 
de uma empresa; como pode ser de minimização, minimizar custos. 
As restrições técnicas podem ser =,  ou : se um insumo será utilizado em 
sua totalidade, a restrição será de igualdade (=); se um insumo que está estocado, 
então, esta restrição será ( ), porque ele vai até a quantidade que está disponível 
no estoque; se há a necessidade desse insumo ser pelo menos, então, esta restrição 
será ( ). 
 
Pesquisa Operacional I 
 
22 
Estamos encerrando a unidade. Sempre que tiver uma dúvida entre em 
contato com seu tutor virtual através do ambiente virtual de aprendizagem e 
consulte sempre a biblioteca do seu polo. 
 
É hora de se avaliar 
Lembre-se de realizar as atividades desta unidade de estudo. Elas irão 
ajudá-lo a fixar o conteúdo, além de proporcionar sua autonomia no processo de 
ensino-aprendizagem. 
 
 
Pesquisa Operacional I 
 
23 
 
Exercícios – Unidade 1 
 
1.Certa fabrica produz dois produtos P1 e P2. O lucro unitário do produto P1 é 
de R$ 100,00, enquanto o lucro do produto P2 é de R$ 180,00. A empresa precisa de 
20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade 
de P2. O tempo de produção disponível para isso é de 1.200 horas. A demanda 
esperada para cada produto é de 40 unidades para P1 e 30 unidades para P2. Qual é 
o plano de produção para que a empresa maximize o seu lucro nesses itens? 
Construa o modelo de programação linear. 
 
 
 
 
 
 
2.Um vendedor de legumes pode transportar 800 caixas de legumes para sua 
região de vendas. Ele necessita transportar 200 caixas de cenouras a R$ 20,00 de 
lucro por caixa, pelo menos 100 caixas de batata a R$ 10,00 de lucro por caixa, e no 
máximo 200 caixas de mandioca a R$ 30,00 por caixa. De que forma deverá ele 
carregar o caminhão para obter o lucro máximo? Construa o modelo do P.P.L. 
 
Pesquisa Operacional I 
 
24 
3.Na fabricação de dois de seus produtos, uma empresa utiliza dois 
equipamentos que limitam a produção. Em um dado período de tempo, estão 
disponíveis 30 horas do equipamento 1 e 60 horas do equipamento 2. Para a 
fabricação de uma unidade do produto A, usa-se 1 hora do equipamento 1 e 2 
horas do equipamento 2. Já para uma unidade do produto B, são gastas 2 horas do 
equipamento 2. O equipamento 1 não toma parte na produção do produto B. Por 
outro lado, uma unidade do produto A leva a um lucro de R$120,00, enquanto cada 
unidade do produto B gera um lucro de R$ 52,00. Formule o modelo de 
programação linear para maximizar o lucro da empresa. 
 
 
 
 
 
 
 
4.Uma alfaiataria está considerando quanto deve produzir de seus dois 
modelos de terno, denominados de Executivo e Despojado, de forma a maximizar 
o lucro. Será impossível fabricar quanto se queira de cada um dos modelos, porque 
existem limitações nas horas disponíveis para a operação de costura e a operação 
de acabamento, as duas operações são básicas na fabricação. No caso da costura, 
existem 160 horas-máquinas disponíveis, enquanto para o acabamento, que é feito 
manualmente, haverá, no máximo, 220 homens-horas. Em termos de lucro unitário 
e produção, os dois modelos apresentam as seguintes características:a. Executivo: 
i. Lucro unitário: R$ 105,00 
ii. Horas-máquina de costura por unidade: 2 
iii. Homens-hora de acabamento por unidade: 2 
b. Despojado: 
i. Lucro unitário: R$ 70,00 
ii. Horas-máquina de costura por unidade: 1 
iii. Homens-hora de acabamento por unidade: 4 
Pesquisa Operacional I 
 
25 
5.Uma rádio FM local tem o seguinte problema: foi descoberto que o 
programa de sertanejo com 20 minutos de música e 1 minuto de propaganda 
chama a atenção de 30.000 ouvintes, enquanto o programa de MPB, com 10 
minutos de musica e 1 minuto de propaganda chama a atenção de 10.000 
ouvintes. No decorrer de uma semana, o patrocinador insiste no uso mínimo, 5 
minutos pra 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: Construa o modelo do P.P.L.