EPRi30.01_-_Introduo_e_Modelagem

Prévia do material em texto

Prof. Dr. Emerson J. Paiva 2EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Exemplo de Modelagem – Alocação de Recursos
Uma companhia de aluguel de caminhões possui veículos 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 precisa transportar no mínimo 50 e no máximo 90
metros cúbicos de produto refrigerado e no mínimo 80 e no máximo 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 custa $0,30
por km e o do B, $0,40 por km. Elabore o modelo de programação linear.
Prof. Dr. Emerson J. Paiva 3EPRi30 – Pesquisa Operacional
Introdução
A Pesquisa Operacional (simplesmente PO) tem como
principal propósito o auxilio na TOMADA DE DECISÃO.
Segundo Chiavenato (1997), consiste no “processo de
análise entre várias alternativas disponíveis do curso de
ação que a pessoa deverá seguir”.
Segundo Liczbinski (2002), a tomada de decisões envolve:
◼ Ambiente;
◼ Risco e incerteza;
◼ Custo e qualidade requerida pelo produto ou serviço;
◼ Agentes tomadores de decisão;
◼ Cultura organizacional;
◼ Mercado.
Prof. Dr. Emerson J. Paiva 4EPRi30 – Pesquisa Operacional
A “TOMADA DE DECISÃO” envolve analisar todos os
elementos listados anteriormente, a fim de encontrar
valores para todas as variáveis envolvidas num problema,
que satisfaçam a todas as condições impostas e que
busquem o melhor resultado final de maximização ou
minimização.
Introdução
Esse decisão deve ser 
a melhor possível, ou, 
em termos de PO, 
ÓTIMA.
Prof. Dr. Emerson J. Paiva 5EPRi30 – Pesquisa Operacional
Condições de Otimização
Como realizar uma otimização?
Durante a 2a.Guerra Mundial, um grupo de cientistas ingleses foram
convocados para estudar problemas de estratégia e de tática associados com a
defesa do país; Objetivo: decidir sobre a utilização mais eficaz de recursos
militares limitados. Os métodos utilizados deram origem à Pesquisa Operacional
(PO).
Com o fim da guerra, a utilização das técnicas de PO atraiu o interesse de
diversas outras áreas.
A premissa dessas técnicas dita que um processo qualquer é transformado
em um modelo (fluxogramas, grafos, equações, etc.), o qual, depois de
resolvido, apresenta as melhores configurações para as variáveis
estudadas e o melhor resultado global para todas elas.
Vamos identificar, agora, quais as definições são 
necessárias para se promover um estudo de PO!
Prof. Dr. Emerson J. Paiva 6EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Definições
• Aplicação do método científico a problemas que dizem respeito ao controle
de sistemas organizados;
• Tem como finalidade obter soluções que melhor satisfaçam aos objetivos
traçados;
• Uma atividade que pode colocar a serviço dos gestores, pesquisadores,
líderes, etc., novas atitudes, conceitos e técnicas, ajudando a resolver
problemas complexos e tomar decisões importantes;
• Aplicação de análises quantitativas dos problemas reais; o objetivo da
análise é encontrar as melhores soluções para esses problemas;
• Preparação científica das decisões, visando a modificação do binômio
“Experiência/Intuição” pela “Informação/Racionalidade”.
Prof. Dr. Emerson J. Paiva 7EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Metodologia de Aplicação
• Um estudo de PO consiste em construir um modelo da situação real. Um
modelo, por sua vez, é definido como uma representação idealizada de um
sistema, que pode já ser existente ou pode, ainda, ser uma ideia a espera
de execução
• A complexidade de um sistema real resulta do grande número de variáveis
que comandam as operações do sistema; entretanto, em muitos casos, uma
pequena fração destas variáveis domina essas operações
• Então, a simplificação do sistema real em termos de um modelo
condensado, identificando apenas as variáveis dominantes e as relações
entre elas, é o empregado;
• Não há regras fixas para determinar o nível de abstração necessário para
se modelar o sistema;
• A validade do modelo representativo do sistema depende da criatividade e
imaginação dos analistas de PO e a equipe de trabalho no projeto.
Prof. Dr. Emerson J. Paiva 8EPRi30 – Pesquisa Operacional
Pesquisa Operacional
O processo de Modelagem
Prof. Dr. Emerson J. Paiva 9EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Razões para se modelar
Modelos nos forçam a ser explícitos em relação a nossos objetivos e ainda:
• nos forçam a identificar e registrar os tipos de decisões que influenciam
esses objetivos;
• nos forçam a identificar e registrar interações e concessões entre essas
decisões;
• nos forçam a pensar cuidadosamente sobre as variáveis a serem incluídas
e suas definições em termos que sejam quantificáveis;
• nos forçam a considerar que dados são pertinentes para a quantificação
dessas variáveis e a determinar suas interações;
• nos forçam a reconhecer restrições (limitações) nos valores que estas
variáveis quantificadas podem assumir;
• permitem a comunicação de nossas ideias e percepções para facilitar o
trabalho da equipe.
Prof. Dr. Emerson J. Paiva 10EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Etapas
Para se chegar a resultados de otimização, é necessário cumprir as seguintes
etapas:
• formulação (ou definição) do problema;
• construção do modelo (mapeado, gráfico, matemático, etc.);
• obtenção de uma solução a partir do modelo;
• teste do modelo e avaliação da solução obtida;
• estabelecimento de controle sobre a solução;
• implantação da solução.
A seguir essas etapas serão demonstradas, a partir do desenvolvimento
de um modelo de solução para um problema meramente didático...
Prof. Dr. Emerson J. Paiva 11EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Exemplo de Modelagem
Formulação – Uma empresa virtual distribui diversos produtos para várias
regiões do país.
Para alavancar as vendas de dois determinados produtos, resolveu, a título de
promoção, bancar os custos relativos a frete, distribuindo esses dois produtos
com frete gratuito.
O PRODUTO1, típico da Região 1, é
vendido a $27 e o custo do frete é de
$10. Taxas, impostos e mão-de-obra
equivalem a $14.
A mão-de-obra é representada por
Montagem, que requer 1h de trabalho,
mais 2h de deslocamento, manuseio e
embalagem.
Prof. Dr. Emerson J. Paiva 12EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Exemplo de Modelagem
O PRODUTO2, típico da Região 2, é vendido a $21 e o custo do frete é de $9.
Taxas, impostos e mão-de-obra equivalem a $10.
A mão-de-obra é representada por Montagem, que requer 1h de trabalho, mais
1h de deslocamento, manuseio e embalagem.
A cada semana a empresa dispõe de 100h de
montagem e 80h de deslocamento, manuseio
e embalagem. A demanda pelo PRODUTO2 é
ilimitada, mas a do PRODUTO1 é de, no
máximo, 40 unidades/semana.
Quantas unidades de cada produto deveriam ser
distribuídas semanalmente, para que o lucro fosse o
maior possível?
Prof. Dr. Emerson J. Paiva 13EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Exemplo de Modelagem
Construção do modelo – A solução se inicia pela
construção de um modelo matemático.
Um modelo matemático de um Problema de Otimização é definido por:
• um número N de decisões a serem tomadas, denominadas Variáveis de
Decisão;
• uma função matemática, que representa a medida da vantagem (ou
desvantagem) da tomada de decisão, denominada Função Objetivo;
• um conjunto de restrições associadas às variáveis de decisão,
denominadas Restrições do Modelo.
Em alguns casos, existem restrições que não estão explícitas no problema,
denominadas restrições adicionais
Prof. Dr. Emerson J. Paiva 14EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Exemplo de Modelagem
Construção do modelo – A PO, como visto, vem
sendo aplicada a problemas de estratégia, marketing,
finanças, recursos humanos, operações e logística, etc.
Sumariamente, o objetivo é decidir sobre a utilização mais eficaz de recursos,geralmente escassos.
A Programação Linear (PL) é uma das principais ferramentas da PO, e sua
aplicação está cada vez mais difundida.
Nesses problemas, a função objetivo, as restrições do modelo e as restrições
adicionais, caso existam, são representadas por funções lineares,
considerando-se todas as variáveis de decisão como contínuas, ou seja,
devem assumir quaisquer valores em um intervalo de números reais.
Prof. Dr. Emerson J. Paiva 15EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Exemplo de Modelagem
A questão, portanto, é:
Sobre o quê se deseja decidir?
Para o exemplo em questão, necessita-se saber quantos itens do Produto1 e
quantos do Produto2 a empresa deve distribuir, para que o lucro seja o
máximo possível. Portanto:
Variáveis de Decisão:
X1 = quantidade de itens do Produto1 que devem ser entregues;
X2 = quantidade de itens do Produto2 que devem ser entregues.
Função Objetivo: Maximizar Receitas – Despesas
Receitas Semanais: 27X1 + 21X2
Custos relativos a fretes: 10X1 + 9X2
Custos relativos a taxas, impostos e mão-de-obra: 14X1 + 10X2
Prof. Dr. Emerson J. Paiva 16EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Exemplo de Modelagem
Então, o que se deseja é:
Maximizar (27X1 + 21X2) (10X1 + 9X2)
Receitas
Despesas Frete
Despesas Mão-de-Obra
Assim, o objetivo da empresa é escolher X1 e X2 para 
Maximizar 3X1 + 2X2 ou Max Z = 3X1 + 2X2
(14X1 + 10X2)
Prof. Dr. Emerson J. Paiva 17EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Exemplo de Modelagem
Entretanto, existem elementos que impedem que os
valores assumidos pelas variáveis de decisão sejam
os máximos. Observem:
Para executar a tarefa de montagem, a empresa dispõe de, apenas, 100h
semanais. Assim, os valores máximos para as variáveis de decisão, somando-
se os dois produtos, não devem exceder esse limite. Portanto:
2X1 + X2 ≤ 100
Apenas 80h estão disponíveis, semanalmente, para deslocamentos, manuseio
e embalagem, resultando em:
X1 + X2 ≤ 80
Além disso, não existem garantias de que se consiga entregar mais do que 40
unidades do Produto1. Então:
X1 ≤ 40
Por último, não faz sentido pensar em entregas negativas. Dessa forma:
X1 ≥ 0; X2 ≥ 0
Prof. Dr. Emerson J. Paiva 18EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Exemplo de Modelagem
O modelo matemático completo será, portanto:
Max Z = 3X1 + 2X2
Sujeito a:
2X1 + X2 ≤ 100
X1 + X2 ≤ 80
X1 ≤ 40
X1 ≥ 0; X2 ≥ 0
Esse sistema de equações, o chamado Modelo Matemático, deverá ser
resolvido a partir de técnicas adiante apresentadas, obtendo-se, como
resultado, os valores que maximizam a Função Objetivo, considerando
devidamente as restrições do problema.
Prof. Dr. Emerson J. Paiva 19EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Características Gerais
Max ou Min z = f(x1, x2, ..., xn) = c1 x1 + c2 x2 + ... + cn xn
Sujeito a: 
a11 x1 + a12 x2 + ... + a1n xn {≤, =, ≥} b1
a21 x1 + a22 x2 + ... + a2n xn {≤, =, ≥} b2
.................................................................
am1 x1 + am2 x2 + ... + amn xn {≤, =, ≥} bm
x1, x2, …, xn ≥ 0
Genericamente, um modelo de PL pode descrito como:
onde: z é função objetivo;
xj são as variáveis de decisão;
aij é a constante ou coeficiente da i-ésima restrição da j-ésima variável, i = 1, 2, ...,
m, j = 1, 2, ..., n;
bj é o termo independente ou coeficiente da j-ésima variável da função objetivo,
j = 1, 2, ..., m);
cj é a constante ou coeficiente da j-ésima variável da função objetivo, j = 1, 2, ..., n;
Imagem disponível em 
http://www.ime.usp.br/~mpmmf/htm/discip.htm
Prof. Dr. Emerson J. Paiva 20EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Características Gerais
Resumidamente, “os problemas de PL buscam determinar valores ótimos para
as variáveis de decisão x1, x2, ..., xn, que devem ser contínuas, a fim de
maximizar ou minimizar a função linear z, sujeita a um conjunto de m
restrições lineares de igualdade e/ou desigualdade”.
As soluções que satisfazem todas as restrições, inclusive as de não
negatividade, são chamadas soluções factíveis, e aquela que apresenta
melhor valor para a função objetivo é chamada de solução ótima.
(BELFIORE e FÁVERO, 2013).
Imagem disponível em 
http://www.ime.usp.br/~mpmmf/htm/discip.htm
Prof. Dr. Emerson J. Paiva 21EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Hipóteses dos Modelos de PL
Para que um modelo possa ser tratado como um problema de PL, o conjunto
de seus elementos constituintes devem satisfazer as seguintes hipóteses:
Imagem disponível em 
http://www.ime.usp.br/~mpmmf/htm/discip.htm
Proporcionalidade: essa hipótese requer que, para cada variável de decisão
considerada no modelo, a sua contribuição em relação à função objetivo seja
diretamente proporcional ao valor da variável de decisão;
Aditividade: os relacionamentos entre as variáveis não podem, em hipótese
alguma, indicar interdependência entre elas; se isso ocorrer, o modelo utilizado
não poderá ser linear;
Divisibilidade: cada uma das variáveis de decisão pode assumir quaisquer
valores não negativos dentro de um intervalo, incluindo valores fracionários;
Certeza: essa hipótese afirma que os coeficientes da função objetivo e das
restrições, além dos termos independentes do modelo são determinísticos
(constantes e conhecidos com certeza).
Prof. Dr. Emerson J. Paiva 22EPRi30 – Pesquisa Operacional
Pesquisa Operacional
Exemplo de Modelagem II – Alocação de Recursos
Uma companhia de aluguel de caminhões possui
veículos 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 precisa transportar no mínimo 50 e no
máximo 90 metros cúbicos de produto refrigerado e
no mínimo 80 e no máximo 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 custa $0,30 por
km e o do B, $0,40 por km. Elabore o modelo de
programação linear.
Voltando ao exemplo inicial de alocação de recursos, aplique os conceitos
apresentados de Programação Linear para a formulação do modelo, como se
segue: