Atividade - Pesquisa Operacional

Prévia do material em texto

INTRODUÇÃO À PESQUISA OPERACIONAL 
 
“A PO como ciência aplica-se a pessoas (organização e gerência, relações de 
trabalho, economia, decisões individuais, pesquisa do mercado, etc) a pessoas 
e máquinas (eficiência e produtividade, organização de fluxos em fábricas, 
métodos de controle de qualidade, organização de mudanças tecnológicas, etc) 
e ao movimento (transporte, estoque, distribuição, manipulação, comunicação, 
localização, etc)” (MIRSHAWKA, 1981). 
 
 
“No mundo em que hoje vivemos a sobrevivência de uma organização impõe o 
planejamento. 
 
“Para auxiliar os planejadores a PO utiliza informações provenientes de todos 
os elementos do sistema de ação, inclusive informações da própria 
organização e as relativas ao meio ambiente e a concorrência” (MIR-SHAWKA, 
1981). 
“É por isto que as características da PO são: pesquisa sobre as operações de 
toda a organização, a otimização das operações, aplicação dos mais recentes 
métodos e técnicas científicas, desenvolvimento e utilização dos modelos 
analíticos, projeto e utilização de operações experimentais, e, emprego de 
equipes mistas de pesquisa” (MIRSHAWKA, 1981). 
 
Devido a importância da Pesquisa Operacional, para finalizar, um trecho 
extraído do livro de Costa (1973): “Em 1973, a disciplina citada (Pesquisa 
Operacional) já está incluída nos currículos de Engenharia, Economia, 
Administração, Química Agronomia, Atuária e Estatística”. 
 
 
 
 
 
 
Um pouco de história 
 
Por volta de 1938 surge o termo operational research que está estreitamente 
vinculado à inven-ção do radar, que ocorreu em 1934, na Inglaterra. O radar 
era utilizado principalmente para detectar presença de inimigos em território 
britânico. Pesquisa Operacional é a tradução direta do termo para o português. 
Em 1941, foi criado a Seção de Pesquisa Operacional do Comando da Força 
Aérea de Combate da Inglaterra com o intuito de auxiliar decisões de guerra 
para que estas fossem tomadas da melhor forma.“A análise científica do uso 
operacional de recursos militares de maneira sistemática foi iniciada na 
Segunda Guerra Mundial” (ARENALESET al., 2007). Ao final da guerra, tanto 
na Inglaterra como nos EUA, a pesquisa operacional evolui consideravelmente. 
Em 1947, foi implantado um projeto militar no Pentágono, onde faziam parte 
deste projeto o matemático George Dantzig. Este projeto tinha por objetivo 
apoiar decisões operacionais das forças aéreas americanas. No decorrer deste 
projeto, Dantzig desenvolveu o método simplex para resolução de problemas 
de programação linear. Na década de 50 foram fundadas a ORSA (sociedade 
científica americana de pesquisa operacional), a ORS (sociedade inglesa de 
pesquisa operacional) e a TIMS (sociedade americana de ciências de 
administração). Nesta mesma década foi realizada a primeira conferência 
internacional de pesquisa operacional, 
realizada em Oxford. Esta conferência foi a primeira oportunidade de troca de 
informações e constatações de trabalhos diferentes em diversas áreas 
apresentados pelos cientistas ingleses (apresentaram problemas específicos) e 
americanos (apresentaram modelos e métodos matemáticos em termas 
diversos). 
 
Em 1967, o periódico inglês Operational Research propôs uma definição para 
pesquisa operacional que diz, segundo a tradução de Arenaleset al. (2007), “ 
Pesquisa Operacional é a aplicação de métodos científicos a problemas 
complexos para auxiliar no processo de tomadas de decisão, tais como 
projetar, planejar e operar sistemas em situações que requerem alocações 
eficientes de recursos escassos”.Na década de 60 a pesquisa operacional 
conquista os pesquisadores brasileiros e em 1968, em São José dos Campos - 
SP, no ITA, foi realizado o primeiro simpósio brasileiro de pesquisa operacional 
e, logo em seguida, foi fundada a Sociedade Brasileira de Pesquisa 
Operacional (SO-BRAPO). 
 
“De forma sucinta, podemos dizer que a pesquisa operacional é um enfoque 
científico sobre a tomada de decisões. A denominação pesquisa operacional é 
comumente motivo de críticas e re-flexões, pois não revela a abrangência da 
área e pode dar a falsa impressão de estar limitada análise de operações... O 
com ponente científico está relacionado a idéias e processos para articular e 
modelar problemas de decisão, determinando os objetivos do tomador de 
decisão e as restrições sob as quais se deve operar. Também está relacionado 
métodos matemáticos para otimizar sistemas numéricos que resultam quando 
se usam dados nos modelos” (ARENALES et al., 2007). APÍTU 
 
 
Conceitos 
 
È uma metodologia administrativa que agrega, em sua teoria, quatro ciências 
fundamentais para o processo de preparação, analise e tomada de decisão: 
Economia, matemática, estatística e informática. ( professor Leopoldino de 
Andrade) Especialista na área. 
Ela trabalha através da formulação de modelos matemáticos a serem 
resolvidos, com auxílio de computadores, sendo feita em seguida a análise, e 
as implementações das soluções obtidas. 
 
Abordagem acadêmica do P.O 
 
1- Aplicabilidade Gerencial ( em sistema de apoio a decisão ou não) 
2- Desenvolvimento de métodos Matemáticos e estatísticos para obtenção 
das soluções dos problemas a serem resolvidos. 
3- Desenvolvimentos de modelos algoritmos computacionais. 
 
 
PROBLEMAS TÍPICOS 
 
 Para facilitar a compreensão deste capítulo, vamos citar novamente o 
trecho do livro de Mirshawka (1981): “as características da PO são: pesquisa 
sobre as operações de toda a organização, a otimização das operações, 
aplicação dos mais recentes métodos e técnicas científicas, desenvolvimento e 
utilização dos modelos analíticos, projeto e utilização de operações 
experimentais,e,emprego de equipes mistas de pesquisa”. Com base nesta 
frase, podemos começar o capítulo afirmando a importância da PO em 
qualquer tomada de decisão em uma organização. 
 Estas decisões devem ser tomadas de forma concisa, tentando atingir 
um determinado objetivo e é neste ponto que entram os problemas de 
otimização.Os problemas de otimização buscam maximizar ou minimizar uma 
quantidade (objetivo), sendo esta quantidade vinculada a um número finito de 
variáveis. As variáveis são, grosso modo, a resposta que procuro no meu 
problema. Um problema de otimização que possui seu objetivo e as suas 
restrições expressas como funções matemáticas e relações funcionais ( ; ; >; <; 
=) são chamados de problemas de programação matemática. Problemas de 
programação matemática podem ser classificados de acordo com a técnica 
utilizada para a resolução dos modelos matemáticos: problemas lineares, 
problemas inteiros, problemas não-lineares. 
 
Neste curso nos preocuparemos apenas com os problemas lineares. 
 
 
Modelos matemáticos. 
 
Para Goldbarg& Luna (2000) um modelo tenta a representação substitutiva da 
realidade. Intui-tivamente a maioria das pessoas já utilizou algum modelo para 
explicar algo a alguém, por exemplo, quando plotamos gráficos, utilizamos 
equações que representam sólidos (cone, cubo,pirâmide, etc), entre outras 
situações, ou seja, tentamos transmitir e fazer interpretações da realidade 
através de metáforas/modelos. 
 
“Um modelo não é igual à realidade, mas suficientemente similar para que as 
conclusões obtidas através de sua análise e/ou operação, possam ser 
estendidas à realidade” (GOLDBARG&LUNA,2000). 
A PO reúne as mais diversas técnicas e algoritmos que tentam estruturar e 
solucionar modelos quantitativos expressos matematicamente. Os principais 
modelos de pesquisa operacional são denominados de programação (no 
sentido de planejamento) matemática. 
A Programação Matemática destaca-se principalmente devido a sua grande 
aplicabilidade na solução de problemas de otimização. Problemas de 
programação matemática podem ser classificados de acordo com as técnicas 
utilizadas para a resolução dos modelos matemáticos: problemas lineares(variáveis são contínuas e apresentam comportamento linear), problemas 
inteiros (se alguma variável está condicionada a assumir valores discretos), 
problemas não lineares (quando exibe qualquer tipo de não-linearidade). 
A dificuldade em modelar matematicamente um problema está em representar 
de forma adequada a realidade. Assim, um modelo que conseguir representar 
mais precisamente a realidade será de melhor qualidade. 
Dentre os diversos modelos de programação citados anteriormente, o foco 
deste curso concentra-se em problemas de programação linear. 
 
 
 Programação Linear 
 
É uma técnica matemática que visa a análise dos recursos de produção para 
que se possa maximizar o lucro e minimizar o custo. É uma técnica de solução 
de problemas que requer a definição dos valores das variáveis envolvidas na 
decisão para otimizar um objetivo a ser alcançado dentro de um conjunto de 
limitações ou restrições, que constituem as regras do jogo. 
 
Programação Linear consiste em métodos para resolver problemas de 
Otimização com restrições (injunções) em que a Função Objetivo é LINEAR 
em relação as variáveis de controle x1, x2,...,xn, e o domínio destas variáveis é 
injuncionado por um sistema de inequações linear 
 
Exemplos de modelos de programação linear 
 
A PO se aplicada à grande variedade de problemas. A maioria consiste em 
problemas de natureza tática e não estratégica. A distinção entre problemas 
táticos e problemas estratégicos se baseia em três aspectos: 
§ Alcance do problema: Um problema é mais tático que outro se sua solução 
produzir efeito de duração mais curta ou, o que e essencialmente se a solução 
pode ser modificada ou abandonada com facilidade. 
§ Extensão do problema: Um problema é tanto mais estratégico quanto maior 
for a parte da organização diretamente afetada pela solução. 
 
§ Orientação do problema: Um problema é tanto mais estratégico quanto mais 
envolver a determinação de finalidades, metas ou objetivos. 
A aplicação da PO a grande variedade de problemas táticos pode ser 
representada por um pequeno número de problemas típicos. Desenvolveram-
se técnicas para modelá-los e obter soluções a partir dos modelos. 
 
Problemas típicos: 
 
 
• Alocação; Estoque; 
• Substituição ou reposição; Filas de espera; 
• Sequência e coordenação; Determinação de rotas; 
• Situações de competição; Busca de informação 
 
Algumas das técnicas matemáticas empregadas para resolução dos modelos e 
aplicam-se a modelos de diferentes tipos. Os modelos são freqüentemente 
classificados segundo de métodos e técnicas matemáticas empregadas na 
obtenção da sua solução. Estas técnicas e métodos são: 
 
 
 Programação Linear; 
• Programação Dinâmica; Programação Inteira; 
• Teoria dos Estoques; Teoria das Filas; 
• Simulação; 
• Teoria dos Jogos; Teoria dos Grafos; 
• Análise de Risco, etc. 
 
 
 
 
 
 
 
ROGRAMAÇÃO LINEAR 
 
Os modelos de programação linear (PL) são importantes pois são a base para a 
compreensão de todos os demais problemas da programação matemática. 
 
Conceitos básicos Para que um sistema possa ser representado utilizando um 
PL, as grandezas envolvidas devem obedecer as seguintes características. 
 
Proporcionalidade: a quantidade de recurso consumido por uma determinada 
atividade deve ser proporcional ao nível desta atividade na solução final do 
problema. E, ainda, o custo de cada atividade deve ser proporcional ao nível de 
operação da atividade. Por exemplo, se 1kg de um ingrediente possui 0,3kg de 
proteína, então 0,5kg deste mesmo ingrediente contém 0,15kg de proteína; 
 
 
Aditividade: o custo total é soma das parcelas associadas a cada atividade. 
Por exemplo, se um ingrediente (1kg) que compõe determinada ração possui 
0,3 kg de proteína e, em outro ingrediente (1kg) possui 0,1kg de proteína, a 
mistura de 1kg de cada um destes dois componentes conterá 0,4 kg de 
proteína; 
 
Fracionamento: as variáveis podem assumir valores fracionados. Por 
exemplo, em uma mistura (ração) pode-se utilizar 0,4kg de um determinado 
ingrediente. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Exemplo1 
Suponha que para construir uma casa popular por mês uma construtor 
necessite de 2 pedreiros e 4 serventes. Para construir um apartamento no 
mesmo intervalo de tempo, a mesma construtora necessita de 3 pedreiros e 8 
serventes. A construtora possui um efetivo total de 30 pedreiros e 70 serventes 
contratados. A construtora obtém um lucro de R$3.000,00 na venda de cada 
casa popular e de R$5.000,00 na venda de cada apartamento e toda 
"produção" da construtora é vendida. 
 
Qual é a quantidade ótima de casas populares e apartamentos que a 
construtora deve construir para que está obtenha lucro máximo. 
 
Solução 
 
Vamos inicialmente representar este problema em forma de tabela. 
 
 
 Casa Popular Apartamento Disponibilidade de 
Mao de Obra 
Pedreiro 2 3 30 
Servente 3 8 70 
Lucro 4 5 
 
A Função Objetivo (que deve expressar o lucro total) é dada por: 
 
F(x1; x2) = 3x1 + 5x2 
Onde as variáveis são : 
x1 é a quantidade de casas populares construídas; 
 
x2 é a quantidade de apartamentos construídos. 
 
 
 
 
 
 
 
 
A modelagem matemática da Função Objetivo neste exemplo é muito simples, 
pois o lucro total vai ser dado pela soma do lucro obtido com 
casas populares e apartamentos multiplicados por suas respectivas 
quantidades produzidas (x1e x2). 
 
Por exemplo, se a construtora construir 2 casas populares (x1=2) e 3 
apartamentos (x2=3) o lucro total vai ser: 
 
F(x1; x2) = 3 x 2 + 5 x 3 
F(x1; x2) = 21 
 
Como o lucro está dado em milhares de Reais, a construtora terá um lucro de 
R$21.000,00. 
No entanto, será que este lucro de R$21.000,00 é o melhor resultado que está 
construtora pode obter ? 
 
Prestando atenção no enunciado do problema, podemos reparar que existe 
uma limitação de mão de obra (não existem infinitos pedreiros e serventes!) e 
portanto, este fato limitará a "produção" desta construtora. 
Esta limitação é denominada de maneira mais formal de Restrição ou Injunção 
. 
Vamos ver como estas injunções pode ser modeladas matematicamente: 
Para cada casa construída a construtora necessita de 2 pedreiros e para cada 
apartamento construído a construtora necessita de 3 pedreiros. Existem 30 
pedreiros contratados. Portanto, podemos modelar está restrição de maneira 
matemática por: 
 
2x1 + 3x2 ≤ 30 (inequação de injunção de pedreiros) 
 
De maneira análoga a expressão 50, a construtora necessita de 4 serventes 
para cada casa construída e 8 serventes para cada apartamento construído. 
Existem 70 serventes contratados. Esta injunção é dada por 
 
 
4x1 + 8x2 ≤ 70 (inequação de injunção de serventes) 
 
 
 
 
Exemplo 2 – 
 
Certa empresa fabrica dois produtos. P1 e P2. O lucro unitário do 
produto P1 é de 1.000,00R$ e o P2 de 1.800,00R$. A empresa precisa 
de 20h para fabricar uma unidade de P1 e de 30 h para fabricar uma 
unidade de P2. O tempo anual de produção disponível é 1.200 horas. A 
demanda esperada para cada produto é de 40 unidades anuais de P1 e 
30 unidades anuais de P2. 
 
Qual o plano de produção para que a empresa maximize o lucro nesses 
itens? Construa o modelo programação linear para esse caso. 
 
 
 
Quais as Variáveis de decisão? 
 
X1= quantidade produzida de P1 
X2= quantidade produzida de P2 
 
 
Qual o objetivo? 
 
Maximizar o Lucro 
 
L= 1000 . X1 + 1800 . X2 
 
Quais as restrições? 
 
 20 h – P1 
 30 h – P2 
 Total anual – 1.200 
 
40 peças-P1 
30 peças- P2 
Total- Demanda 
 
 
20h . X1 + 30h . X2 ≤1.200 horas 
 
 X1 ≤ 40 
 X2 ≤ 30 
 
 
 
 
 
 
 
 
LISTA DE EXERCÍCIOS 1 – PESQUISA OPERACIONAL 
 
 
1- A empresa Dalai lama deseja planejar a produção de incenso. Os incensos 
requerem dois tipos de recursos: Mãode Obra e Matéria prima. A epresa 
fabrica três tipos de incenso, cada qual com diferentes necessidades de 
mão de obra e matéria, conforme tabela abaixo. 
 
 A B C 
Mão de obra 
 ( horas unidade ) 
 
7 
3 6 
Materiais 
( unidades) 
4 4 5 
Lucro 4 2 3 
 
 
A disponibilidade de matéria prima é de 200g/dia. A mão de obra disponível por 
dia é de 150h. Formule um problema de programação linear para determinar 
quanto deve ser produzido de cada tipo de incenso, tal qual o lucro seja 
maximizada. 
 
A) Quais as variáveis de decisão? 
B) Quais as restrições? 
C) Função objetivo? 
 
 
2- Certa empresa fabrica dois produtos. P1 e P2. O lucro unitário do 
produto P1 é de 1.000,00R$ e o P2 de 1.500,00R$. A empresa precisa 
de 20h para fabricar uma unidade de P1 e de 30 h para fabricar uma 
unidade de P2. O tempo anual de produção disponível é 1.200 horas. A 
demanda esperada para cada produto é de 30 unidades anuais de P1 e 
20 unidades anuais de P2. Qual o plano de produção para que a 
empresa maximize o lucro nesses itens? Construa o modelo 
programação linear para esse caso. 
 
 
 
3- Uma companhia de aluguel de caminhões possuía-os de dois tipos: o tipo A com 2 
metros cúbicos de espaço refrigerado e 4 metros cúbicos de espaço não refrigerado 
e o tipo B com 3 metros cúbicos refrigerados e 3 não refrigerados. Uma 
fábrica precisou transportar 90 metros cúbicos de produto refrigerado e 
120 metros cúbicos de produto não refrigerado. Quantos caminhões de 
cada tipo ela deve alugar, de modo a minimizar o custo, se o aluguel do caminhão 
A era $0,30 por km e o do B, $0,40 por km. Elabore o modelo de 
programação linear. 
 
 
4- Um fabricante de bombons tem estocado bombons de chocolate, sendo 
130 kg com recheio de cerejas e 170 kg com recheio de menta. Ele 
decide vender o estoque na forma de dois pacotes sortidos diferentes. 
Um pacote contém uma mistura com metade do peso dos bombons de 
cereja e metade em menta e vende por R$ 20,00 por kg. O outro pacote 
contém uma mistura de um terço de bombons de cereja e dois terços de 
menta e vende por R$12,50 por kg. O vendedor deveria preparar 
quantos quilos de cada mistura a fim de maximizar seu lucro nas 
vendas?