Aula 01 - Introdução à Pesquisa Operacional

AULA 01
INTRODUÇÃO À PESQUISA
OPERACIONAL
Eduardo Camargo de Siqueira
PESQUISA OPERACIONAL
TECNÓLOGO EM ANÁLISE E
DESENVOLVIMENTO DE SISTEMAS
CONCEITO
• O que é Pesquisa Operacional?
• “Pesquisa Operacional é o conjunto de
conhecimentos relacionados com o processo
científico de tomada de decisão, aplicados no
projeto e operação de sistemas homemmáquina, em um ambiente com recursos
restritos”. SOBRAPO
CONCEITO
• O que é Pesquisa Operacional?
• É um método científico que fornece instrumentos para
a tomada de decisões.
• É uma ciência aplicada cujo objetivo é a melhoria da
performance em organizações.
• Trabalha através da formalização de modelos
matemáticos a serem resolvidos com auxílio do
computador.
ORIGENS DA PO
• Desde o advento da Revolução Industrial, o
mundo
presencia
um
crescimento
extraordinário das organizações.
• As pequenas oficinas evoluíram
corporações bilionárias de hoje.
para
• Divisão do Trabalho e a segmentação das
reponsabilidades.
ORIGENS DA PO
• Apesar dos pontos
problemas surgiram.
positivos,
novos
• Setores desenvolvem seus próprios objetivos
e valores. Perdendo a visão do todo.
• Unidades podem acabar trabalhando em
objetivos conflitantes.
ORIGENS DA PO
• À medida que aumenta a complexidade em
uma organização.
• Torna-se mais
disponíveis.
difícil
alocar
• Da maneira mais eficiente
organização como um todo.
recursos
para
a
ORIGENS DA PO
• Esses tipos de problema e a necessidade
de encontrar o melhor caminho para
solucioná-los criaram as condições
necessárias para o surgimento da
Pesquisa Operacional (PO).
ORIGENS DA PO
• A PO surgiu décadas atrás na tentativa inicial de
uma abordagem científica na gestão das
organizações.
• Porém, o termo “Pesquisa Operacional” é
atribuído às atividades militares nos primórdios da
2ª GM.
• Havia a necessidade de alocar recursos escassos
nas operações militares.
ORIGENS DA PO
• Os comando militares (EUA e Inglaterra)
convocaram diversos cientistas.
• Na prática lhes foi solicitado fazer pesquisas
sobre operações.
• Esses esforços ajudaram em vitórias de
diversas batalhas.
ORIGENS DA PO
• Ao final da guerra o sucesso da PO
despertou interesse na sua aplicação fora
do ambiente militar.
• No início dos anos 50, a PO estava
inserida em diversas organizações
comerciais, industriais e governamentais.
ORIGENS DA PO
• Dois fatores impulsionaram o crescimento
da PO:
– Melhoria das Técnicas.
– A revolução computacional.
ORIGENS DA PO
• Após a Guerra, muitos cientistas se
motivaram para desenvolver pesquisas
importantes.
• Um exemplo é o “método Simplex”,
desenvolvido por Dantzig em 1947.
• Várias ferramentas da PO, se desenvolveram
antes do final dos anos 50.
ORIGENS DA PO
• Problemas complexos requer um grande
volume de cálculo.
• O desenvolvimento dos computadores e de
suas capacidades de processamento deu um
impulso enorme na PO.
• Outro estímulo foi nos anos 80 com
surgimento dos computadores pessoais.
A NATUREZA DA PO
• A PO desenvolve pesquisa sobre operações.
• A PO é aplicada a problemas envolvendo
como conduzir e coordenar as operações.
• A natureza da organização é secundária,
pois a PO tem sido aplicada em áreas
distintas.
A NATUREZA DA PO
• Manufatura:
– Dimensionamento de lotes (Lot-Sizing Problem).
– Otimização de layouts (Facility Layout Problem).
– Formação de células de fabricação.
A NATUREZA DA PO
• Sistemas de Transporte e Distribuição:
– Roteamento
Problem).
de
veículos
(Vehicle
Routing
– Otimização de tabela de horários de ônibus
urbano.
– Programação de tripulações de ônibus urbano
(Bus Crew Scheduling).
A NATUREZA DA PO
• Instituições de ensino:
– Programação de Horários em Escolas (School
Timetabling).
– Alocação de
Assignment).
Salas
de
Aula
(Classroom
• Hospitais:
– Programação de horários de enfermeiras (Nurse
scheduling).
A NATUREZA DA PO
• Construção:
– Otimização de estruturas metálicas.
• Finanças:
– Análise de risco.
• Agricultura:
– Planejamento da produção agrícola.
A NATUREZA DA PO
• Programação Matemática:
– Programação Linear.
– Programação Não Linear.
– Programação Dinâmica.
– Programação Inteira.
A NATUREZA DA PO
• Teoria de Jogos.
• Teoria de Filas.
• Simulação.
• Gestão de estoques.
A NATUREZA DA PO
• Uma característica marcante da PO é que
ela procura encontrar uma melhor solução
(Solução ótima).
• A busca pela “otimalidade” é um tema
importante na PO.
• Otimização.
O IMPACTO DA PO
• A PO teve um impacto enorme na melhoria
da eficiência de inúmeras organizações.
• A PO deu uma contribuição significativa no
aumento da produtividade de diversos
países.
• Ásia e Europa possuem federações de PO.
O IMPACTO DA PO
Organização
Aplicação
Economia Anual
US$
Monsanto
Produção nas fábricas
químicas.
2 milhões
United Airlines
Turnos de trabalho nos
balcões.
6 milhões
Texaco
Misturar os componentes
químicos da gasolina.
30 milhões
IBM
Rede de inventários de
peças.
270 milhões
AT&T
Projeto de call center.
750 milhões
O IMPACTO DA PO
Organização
Aplicação
Economia Anual
US$
Delta Airlines
Alocação de aeronaves.
100 milhões
China
Projetos de produção de
energia.
425 milhões
África do Sul
Sistema de defesa e de
armamentos.
1,1 bilhão
HP
Linha de produção.
280 milhões
Samsung
Fabricação e níveis de
estoque
200 milhões
EXEMPLO
• Uma empresa de comida canina produz dois tipos
de rações: Tobi e Rex. Para a manufatura das
rações são utilizados cereais e carne. Sabe-se
que:
– A ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e
a ração Rex utiliza 4 kg de carne e 2 kg de cereais;
– O pacote de ração Tobi custa $ 20 e o pacote de
ração Rex custa $ 30;
EXEMPLO
– O kg de carne custa $ 4 e o kg de cereais custa $ 1;
– Estão disponíveis por mês 10 000 kg de carne e 30
000 kg de cereais.
• Deseja-se saber qual a quantidade de cada
ração a produzir de modo a maximizar o lucro.
EXEMPLO - RESOLUÇÃO
EXEMPLO - RESOLUÇÃO
FASES DE UM ESTUDO DE PO
• Definir o problema e coletar dados.
• Formular o modelo matemático.
• Desenvolver um procedimento
computacional.
• Testar o modelo e melhorá-lo.
DEFINIÇÃO DO PROBLEMA
• Determinar os objetivos.
• Coletar dados relevantes sobre o
problema.
• Definir o escopo do problema.
FORMULANDO UM MODELO
• Após o problema ser definido a próxima
fase é formular um modelo que seja
conveniente para análise.
• O método da PO é através da construção
de um modelo matemático.
FORMULANDO UM MODELO
• Os modelos são partes integrantes da vida
do dia-a-dia.
• O que é um modelo?
• “Representação simplificada e abstrata de
fenômeno ou situação concreta, e que serve
de referência para a observação, estudo ou
análise” - Aurélio
FORMULANDO UM MODELO
• Os modelos desempenham importante papel
nas ciências.
• Modelos de átomos, estruturas genéticas,
equações
matemáticas
descrevendo
fenômenos físicos.
• Gráficos, organogramas, fluxogramas.
FORMULANDO UM MODELO
• Os
modelos
matemáticos
são
representações idealizadas, expressos em
termos de símbolos e expressões
matemáticas.
• O modelo de um problema de negócios é
um conjunto de equações e expressões
matemáticas que descrevem o problema.
FORMULANDO UM MODELO
• Se houver n decisões quantificáveis a serem
feitas, elas são representadas pelas
variáveis de decisão.
• X , X , ..., X .
1
2
n
• Por exemplo, número de cadeiras em uma
sala de aula.
FORMULANDO UM MODELO
• A medida de desempenho apropriada é
expressa por uma função matemática.
• Por exemplo, o lucro.
• Essa função é chamada de função objetivo
(P = 3X + 2X – X ).
1
2
3
FORMULANDO UM MODELO
• Quaisquer limitações nos valores que podem
ser atribuídos são expressas por meio de
desigualdades ou equações.
• X + 3X < 10.
1
2
• Essas
limitações
Restrições.
são
denominadas
FORMULANDO UM MODELO
• Os valores constantes nas restrições e na
função objetivo são chamados de
parâmetros.
• O modelo matemático nos diz que o
problema é escolher os valores das
variáveis de decisão de forma a otimizar
a função objetivo sujeita às restrições.
FORMULANDO UM MODELO
PROCEDIMENTO
COMPUTACIONAL
• Sequência de ações para a obtenção de
uma solução para um determinado
problema.
• O projeto de algoritmos é fortemente
influenciado pelo estudo de seus
comportamentos.
COMPLEXIDADE DE
ALGORITMOS
• É necessário estudar as várias opções de
algoritmos, considerando os aspectos de
tempo de execução e espaço ocupado.
• Esses algoritmos são encontrados em
áreas
como
pesquisa
operacional,
otimização, teoria dos grafos, estatística,
probabilidades, entre outras.
COMPLEXIDADE DE
ALGORITMOS
• Qual é o custo de usar um dado algoritmo
para resolver um problema específico?
• Análise do número de vezes que cada parte
do algoritmo deve ser executada.
• Estudo
da
necessária.
quantidade
de
memória
COMPLEXIDADE DE
ALGORITMOS
• Podem existir vários algoritmos para
resolver o mesmo problema.
• Se a mesma medida de custo é aplicada a
diferentes algoritmos, então é possível
compará-los e escolher o mais adequado.
COMPLEXIDADE DE
ALGORITMOS
• Para medir o custo de execução de um
algoritmo é comum definir uma função de
complexidade f(n).
• A complexidade de tempo não representa
tempo diretamente, mas o número de
vezes
que
determinada
operação
considerada relevante é executada.
COMPLEXIDADE DE
ALGORITMOS
COMPLEXIDADE DE
ALGORITMOS
COMPLEXIDADE DE
ALGORITMOS
COMPLEXIDADE DE
ALGORITMOS
• Notação O
– Escrevemos g(n) = O(f(n)) para expressar
que f(n) domina assintoticamente g(n).
– Lê-se g(n) é da ordem de f(n).
• Exemplo:
– g(n) = (n + 1)2
– g(n) = O(n2)
COMPLEXIDADE DE
ALGORITMOS
• g(n) = 3n3+ 2n2+n é O(n3)
• g(n) = log5n é O(logn).
• g(n) = 2n + 1 é O(2n)
COMPLEXIDADE DE
ALGORITMOS
• Algoritmo exponencial tem função de
complexidade O(cn).
• Algoritmo polinomial tem função de
complexidade O(p(n)).
A CLASSE NP
• Um problema A pertence à classe P se
existe um algoritmo polinomial para A.
• Um problema A pertence à classe NP se A
pode ser verificado por um algoritmo
polinomial.
A CLASSE NP
• A grosso modo, problemas NP-difíceis:
somente
possuem
algoritmos
exponenciais para resolvê-los.
• Dizemos que um problema B é NPcompleto se B ∈ NP e B é NP-difícil.
A CLASSE NP
FIM
• Dúvidas?
• Obrigado pela atenção!