Aula1 - Introdução à Pesquisa Operacional

Prévia do material em texto

Programação Linear - Aula 01
Introdução à Pesquisa Operacional
Profa. Laura Silva de Assis
Engenharia de Computação
7o Peŕıodo
CEFET/RJ - Centro Federal de Educação Tecnológica Celso Suckow da Fonseca
Campus Petrópolis
1
Sumário
1 Otimização
2 Pesquisa Operacional
3 Exerćıcios
4 Referências
2
Otimização Definições
Conceitos
Otimização
Área da Pesquisa Operacional que utiliza o método cient́ıfico para apoiar na
tomada de decisões, procurando determinar como melhor projetar e operar um
sistema, usualmente sob condições que requerem a alocação de recursos escassos.
Trabalha com modelos determińısticos, assumindo que informações
relevantes são conhecidas (sem incertezas).
Exemplos:
Roteamento de véıculos: dentre todas rotas posśıveis, determinar a que
minimiza a distância total percorrida.
3
Otimização Definições
Conceitos
Roteamento de véıculos
4
Otimização Definições
Conceitos
Otimização
Área da Pesquisa Operacional que utiliza o método cient́ıfico para apoiar na
tomada de decisões, procurando determinar como melhor projetar e operar um
sistema, usualmente sob condições que requerem a alocação de recursos escassos.
Trabalha com modelos determińısticos, assumindo que informações
relevantes são conhecidas (sem incertezas) .
Exemplos:
Roteamento de véıculos: dentre todas rotas posśıveis, determinar a que
minimiza a distância total percorrid.a
Escala de motorista: Dentre todas as viagens minimizar o uso da equipe.
5
Otimização Definições
Conceitos
Escala de motorista - Crew Scheduling
6
Otimização Definições
Conceitos
Escala de motorista - Crew Scheduling
7
Otimização Definições
Conceitos
Escala de motorista - Crew Scheduling
8
Otimização Definições
Conceitos
Escala de motorista - Crew Scheduling
9
Otimização Definições
Conceitos
Escala de motorista - Crew Scheduling
10
Otimização Definições
Conceitos
Escala de motorista - Crew Scheduling
11
Otimização Definições
Conceitos
Otimização
Área da Pesquisa Operacional que utiliza o método cient́ıfico para apoiar na
tomada de decisões, procurando determinar como melhor projetar e operar um
sistema, usualmente sob condições que requerem a alocação de recursos escassos.
Trabalha com modelos determińısticos, assumindo que informações
relevantes são conhecidas (sem incertezas.)
Exemplos:
Roteamento de véıculos: dentre todas rotas posśıveis, determinar a que
minimiza a distância total percorrida.
Escala de motorista: dentre todas as viagens minimizar o uso da equipe.
Programação de jogos para competições esportivas: montar uma tabela de
jogos entre os times participantes da competição que satisfaça as restrições da
comptetição e minimizae os custos reltivos ao deslocamento dos times.
12
Otimização Definições
Conceitos
Programação de jogos
1 Vitória × Atlético | Grêmio × Atlético | Atlético × Santos.
Distância total percorrida: 6.760km
2 Atlético × Vitória | Grêmio × Atlético | Atlético × Santos.
Distância total percorrida: 5.382km
Economia de 1378km
13
Otimização Definições
Conceitos
Programação de jogos considerando otimização - O que ganhamos?
Justificativa:
Redução de gastos com deslocamento.
Influência no desempenho dos times.
Enquadra-se na classe de problemas NP-dif́ıceis.
Número de tabelas posśıveis para uma competição envolvendo n times
confrontando-se entre si em turnos completos (Conćılio & Zuben (2002)):
(n − 1!)(n − 3)!(n − 5)! · · · (n − (n − 1))! × 2(n−1)×
n
2 .
Competição com 20 participantes: 2.9062 × 10130 tabelas.
Aproximadamente 10114 anos para analisar todas as tabelas em um
computador que analisa uma tabela em 10−8 segundos.
14
Otimização Definições
Conceitos
Programação de jogos considerando otimização
Exemplo: Programação de jogos da primeira divisão do campeonato
brasileiro de futebol (Biajoli et al. 2004).
Problema considerado:
1a Divisão do Campeonato Brasileiro de Futebol 2004, 2005 e 2006.
2a Divisão do Campeonato Brasileiro de Futebol 2006.
Competições realizadas em dois turnos completos e espelhados.
15
Otimização Definições
Conceitos
Programação de jogos considerando otimização
Exemplo: Programação de jogos da primeira divisão do campeonato
brasileiro de futebol (Biajoli et al. 2004).
Restrições:
1 Dois times jogam entre si duas vezes, uma no turno e a outra no returno,
alternando-se o mando de campo entre os mesmos.
2 Nas duas primeiras rodadas de cada turno, cada time alternará seus jogos,
sendo um em casa e o outro na casa do adversário. Ex.: 1a fora, 2a em casa.
3 As duas últimas rodadas de cada turno devem ter a configuração inversa das
duas primeiras rodadas de cada turno com relação ao mando de campo. Ex.:
Penúltima em casa, Última fora.
4 Não pode haver jogos entre times do mesmo estado na última rodada.
5 A diferença entre os jogos feitos em cada turno em casa e fora de casa de um
time não pode ser maior que uma unidade.
6 Um time não pode jogar mais que duas vezes consecutivas dentro ou fora de
casa.
15
Otimização Definições
Conceitos
Programação de jogos considerando otimização
Exemplo: Programação de jogos da primeira divisão do campeonato
brasileiro de futebol (Biajoli et al. 2004).
Restrições:
1 Dois times jogam entre si duas vezes, uma no turno e a outra no returno,
alternando-se o mando de campo entre os mesmos.
2 Nas duas primeiras rodadas de cada turno, cada time alternará seus jogos,
sendo um em casa e o outro na casa do adversário. Ex.: 1a fora, 2a em casa.
3 As duas últimas rodadas de cada turno devem ter a configuração inversa das
duas primeiras rodadas de cada turno com relação ao mando de campo. Ex.:
Penúltima em casa, Última fora.
4 Não pode haver jogos entre times do mesmo estado na última rodada.
5 A diferença entre os jogos feitos em cada turno em casa e fora de casa de um
time não pode ser maior que uma unidade.
6 Um time não pode jogar mais que duas vezes consecutivas dentro ou fora de
casa.
15
Otimização Definições
Conceitos
Programação de jogos considerando otimização
Exemplo: Programação de jogos da primeira divisão do campeonato
brasileiro de futebol (Biajoli et al. 2004).
Restrições:
1 Dois times jogam entre si duas vezes, uma no turno e a outra no returno,
alternando-se o mando de campo entre os mesmos.
2 Nas duas primeiras rodadas de cada turno, cada time alternará seus jogos,
sendo um em casa e o outro na casa do adversário. Ex.: 1a fora, 2a em casa.
3 As duas últimas rodadas de cada turno devem ter a configuração inversa das
duas primeiras rodadas de cada turno com relação ao mando de campo. Ex.:
Penúltima em casa, Última fora.
4 Não pode haver jogos entre times do mesmo estado na última rodada.
5 A diferença entre os jogos feitos em cada turno em casa e fora de casa de um
time não pode ser maior que uma unidade.
6 Um time não pode jogar mais que duas vezes consecutivas dentro ou fora de
casa.
15
Otimização Definições
Conceitos
Programação de jogos considerando otimização
Exemplo: Programação de jogos da primeira divisão do campeonato
brasileiro de futebol (Biajoli et al. 2004).
Restrições:
1 Dois times jogam entre si duas vezes, uma no turno e a outra no returno,
alternando-se o mando de campo entre os mesmos.
2 Nas duas primeiras rodadas de cada turno, cada time alternará seus jogos,
sendo um em casa e o outro na casa do adversário. Ex.: 1a fora, 2a em casa.
3 As duas últimas rodadas de cada turno devem ter a configuração inversa das
duas primeiras rodadas de cada turno com relação ao mando de campo. Ex.:
Penúltima em casa, Última fora.
4 Não pode haver jogos entre times do mesmo estado na última rodada.
5 A diferença entre os jogos feitos em cada turno em casa e fora de casa de um
time não pode ser maior que uma unidade.
6 Um time não pode jogarmais que duas vezes consecutivas dentro ou fora de
casa.
15
Otimização Definições
Conceitos
Programação de jogos considerando otimização
Exemplo: Programação de jogos da primeira divisão do campeonato
brasileiro de futebol (Biajoli et al. 2004).
Restrições:
1 Dois times jogam entre si duas vezes, uma no turno e a outra no returno,
alternando-se o mando de campo entre os mesmos.
2 Nas duas primeiras rodadas de cada turno, cada time alternará seus jogos,
sendo um em casa e o outro na casa do adversário. Ex.: 1a fora, 2a em casa.
3 As duas últimas rodadas de cada turno devem ter a configuração inversa das
duas primeiras rodadas de cada turno com relação ao mando de campo. Ex.:
Penúltima em casa, Última fora.
4 Não pode haver jogos entre times do mesmo estado na última rodada.
5 A diferença entre os jogos feitos em cada turno em casa e fora de casa de um
time não pode ser maior que uma unidade.
6 Um time não pode jogar mais que duas vezes consecutivas dentro ou fora de
casa.
15
Otimização Definições
Conceitos
Programação de jogos considerando otimização
Exemplo: Programação de jogos da primeira divisão do campeonato
brasileiro de futebol (Biajoli et al. 2004).
Restrições:
1 Dois times jogam entre si duas vezes, uma no turno e a outra no returno,
alternando-se o mando de campo entre os mesmos.
2 Nas duas primeiras rodadas de cada turno, cada time alternará seus jogos,
sendo um em casa e o outro na casa do adversário. Ex.: 1a fora, 2a em casa.
3 As duas últimas rodadas de cada turno devem ter a configuração inversa das
duas primeiras rodadas de cada turno com relação ao mando de campo. Ex.:
Penúltima em casa, Última fora.
4 Não pode haver jogos entre times do mesmo estado na última rodada.
5 A diferença entre os jogos feitos em cada turno em casa e fora de casa de um
time não pode ser maior que uma unidade.
6 Um time não pode jogar mais que duas vezes consecutivas dentro ou fora de
casa.
16
Otimização Definições
Conceitos
Programação de jogos considerando otimização
Exemplo: Programação de jogos da primeira divisão do campeonato
brasileiro de futebol (Biajoli et al. 2004).
Melhores soluções obtidas:
Instâncias CBF Biajoli 2004 ILS-MRD
Dist Dif Dist Dif Dist Dif %MDIST %MDIF
bssp2004 905.316 86.610 789.480 53.309 754.935 51.199 16,61 40,89
bssp2005 838.464 70.655 - - 696.800 46.821 16,90 33,73
bssp2006-A 658.195 50.769 - - 562.886 37.628 14,48 25,88
bssp2006-B 998.675 61.454 - - 967.374 23.848 3,13 61,19
Considerando o custo do quilômetro aéreo a R$0, 70.
Delegação de 20 pessoas.
Campeonatos 2004 e 2005, Série A: Aprox. R$2 milhões.
Campeonato 2006, Série A: Aprox. R$1 milhão.
Campeonato 2006, Série B: Aprox. R$500 mil.
17
Otimização Definições
Problemas de Otimização
Linear
ax + b
x1 + 3x2
Não Linear
x4 − 4x3 − x + 5
sin(x1) + 3x2
Cont́ınua
x ∈ Rn
Discreta
x ∈ Z
Multicritério · · ·
18
Otimização Definições
Modelos de Otimização
Duas grandes classes:
Modelos de Programação Matemática.
Modelos Heuŕısticos.
19
Otimização Definições
Modelos de Otimização
Modelos de Programação Matemática.
Fundamentados na matemática.
Métodos exatos: garantem a geração da solução ótima.
Foco da disciplina : Programação Linear.
Desvantagem:
Modelagem mais complexa.
Em problemas combinatórios, podem exigir um tempo proibitivo para
encontrar a solução ótima.
Vantagem:
Garantia do ótimo global.
20
Otimização Definições
Modelos de Otimização
Modelos Heuŕısticos
Fundamentados na Inteligência Artificial.
Inspirados:
Na forma humana de se pensar e resolver problemas.
Processos biológicos.
Processos f́ısicos e qúımicos.
Comportamento social de uma colônia de formigas, enxame de abelhas, etc.
Desvantagem:
Métodos aproximados: Não garantem a otimalidade da solução final.
Vantagem:
De fácil modelagem.
Em geral, produzem boas soluções com um bom compromisso custo ×
benef́ıcio.
21
Pesquisa Operacional Definição
PO
A Pesquisa Operacional (PO) indica “pesquisa sobre operações”.
Aplicada a problemas que envolvem a condução e coordenação das operações
(atividades) em uma organização.
Aplicações distintas: manufatura, transporte, construção, planejamento
financeiro, assistência médica, serviços públicos, etc.
PO é uma área de estudo que lida com a aplicação de métodos para ajudar
na tomada de (melhores) decisões.
22
Pesquisa Operacional Definição
Áreas
Pesquisa Operacional - Sub-área:
Matemática Aplicada.
Engenharia de Produção.
Administração.
Emprega técnicas de outras ciências matemáticas, como: modelagem
matemática, análise estat́ıstica e otimização.
A pesquisa operacional chega a soluções ótimas ou quase para problemas
complexos de tomada de decisão.
23
Pesquisa Operacional Definição
PO
Definição
Pesquisa Operacional (PO) estuda as operações de uma organização e utiliza
modelos matemáticos e/ou computacionais para encontrar maneiras melhores
de realizá-las.
24
Pesquisa Operacional Histórico
Origem
A expressão “Pesquisa Operacional” foi utilizada pela primeira vez durante
a Segunda Guerra Mundial.
Necessidade de alocar de forma eficiente os escassos recursos para as
diversas operações militares.
Os militares necessitavam gerenciar seus recursos de forma eficiente até os
campos de batalha.
Pesquisadores foram convocados para lidarem com estes problemas táticos e
estratégicos.
Como consequência dessa “pesquisa” garantiram-se as vitórias nas Batalhas
Aéreas na Grã-Bretanha e no Atlântico Norte, igualmente auxiliaram na
Campanha Britânica no Paćıfico.
25
Pesquisa Operacional Histórico
Origem
Com o fim da guerra e expansão econômica de alguns páıses pequenas
oficinas se tornaram em grandes empresas.
Organizações não militares tinham operações cada vez mais complexas.
No ińıcio da década de 1950, a PO passou a ser aplicada em organizações das
mais variadas áreas de atuação.
A alavanca foi o crescimento do uso de computadores.
26
Pesquisa Operacional Histórico
A natureza da PO
Genericamente, a solução de problemas em PO compreende:
Coleta de dados.
Análise meticulosa do problema.
Construção de um modelo mantemático que rerpesente o problema em
estudo.
Modelo
Uma representação simplificada da realidade.
Abstração do problema real.
Validação do modelo.
Realização de testes (conforme técnica escolhida) para obtenção de soluções
para o problema modelado.
27
Pesquisa Operacional Histórico
A natureza da PO
Ponto de vista abrangente.
Procura encontrar uma melhor solução (solução ótima) para o modelo que
rerepresenta o problema em estudo.
A necessidade de um trabalho com uma boa equipe.
Permite a experimentação - a possibilidade de uma tomada de decisão ser
melhor avaliada e testada antes de ser implementada.
28
Pesquisa Operacional Histórico
Técnicas mais comuns - Programação matemática
Programação Linear (PL):
Técnica que pressupõe a relação linear entre as caracteŕısticas do problema
buscando a solução ótima.
Tais caracteŕısticas são representadas por uma série de equações lineares.
Programação não Linear (PNL):
Processo de resolução de um problema de otimização definido por um sistema
de equações e desigualdades (restrições), função objetivo (FO), onde algumas
das restrições ou FO são não lineares .
29
Pesquisa Operacional Histórico
Técnicas mais comuns - Programação matemática
Programação Inteira (PLI):
É um modelo de programação linear onde uma ou todas variáveis do
problema pertencem ao conjunto dos números inteiros.
Podendo ser um problema de programação inteira pura ou mista.
Programação Dinâminca:
É um método de programação especialmente usado para resolver problemas de
otimização combinatória.
É aplicável a problemas onde a solução ótima do problemaé composta por
soluções ótimas de seus subproblemas.
As soluções ótimas de subproblemas são previamente computadas e
memorizadas.
30
Pesquisa Operacional Histórico
Técnicas mais comuns - Programação matemática
Progamação Estocástica:
Técnica de programação onde temos no modelo variáveis estocásticas.
Custos, lucros, ganhos não são determińısticos. Existem vários cenários que
devem ser considerados simultâneamente.
Heuŕıstica:
Os métodos heuŕısticos são algoritmos exploratórios que buscam resolver
problemas sem garantia de solução ótima.
Iniciam de soluções viáveis e sucessivas aproximações direcionadas ao ótimo.
31
Pesquisa Operacional Histórico
Técnicas mais comuns
Simulação computacional:
Técnica que simula as caracteŕısticas estudadas em um modelo de
computador.
Considera a variabilidade dos comportamentos do ambiente e seus
participantes.
Possibilita testar mudanças e conhecer com maior probabilidade de sucesso o
impacto dessas mudanças no sistema.
Teoria dos Jogos:
É uma técnica matemática que busca antecipar as posśıveis decisões de
participantes de uma situação de competição.
32
Pesquisa Operacional Histórico
Técnicas mais comuns
Teoria das Filas
É o estudo das esperas existentes nos mais diversos sistemas.
Filas comuns como: de banco, do caixa no supermercado, etc.
Até outras não tão comuns como: as ordens de produção aguardando para
serem liberadas, véıculos que aguardam para serem descarregados.
É necessário o balanceamento adequado dos recursos visando um ńıvel de
atendimento satisfatório.
Busca pelo melhor custo-benef́ıcio entre as esperas e suas implicações.
33
Pesquisa Operacional Aplicações práticas de PO
Aplicações
Empresa Aplicação Economia Anual
Continental Airlines
Otimizar a realocação de
tripulações quando ocorrem
desajustes nos horários de
voo.
US$ 40 milhões
Samsung
Redução de tempos de
fabricação e ńıveis de
estoque.
US$ 200 milhões mais
receitas
Sears
Programação de rotas de
véıculos para as frotas de
entrega e atendimento domiciliar
US$ 42 milhões
General Motors
Aumentar a eficiência das
linhas de produção.
US$ 90 milhões
AT&T
Projeto e operação de call
centers.
US$ 750 milhões mais
lucros
34
Pesquisa Operacional Aplicações práticas de PO
Aplicações
Federal Express
Maior empresa de transporte expresso do mundo.
Todos os dias entrega 6,5 bilhões de documentos, pacotes, etc nos EUA e
em mais de 220 páıses ao redor do mundo.
A loǵıstica envolvida no fornecimento desse serviço é estarrecedora
Milhões de embarques classificados direcionados corretamente, recebidos e
entregues a um destino exato (véıculo motorizado).
Tudo isso em um peŕıodo surpreendentemente curto, como é posśıvel?
35
Pesquisa Operacional Aplicações práticas de PO
Aplicações
Federal Express
A PO é o motor tecnológico dessa empresa.
Desde sua fundação (1973), a PO auxiliou na tomada das principais
decisões de negócio.
Investimento de equipamento, rotas, cronograma, finanças, localização de
instalações.
Vários diretores hoje provêm do destacado grupo de PO da FedEx.
36
Exerćıcios Atividade de pesquisa
Empresas que utilizam PO como ferramenta
1 Selecione 2 das aplicações de Pesquisa Operacional enumeradas na tabela
abaixo (Livro 2 da aula 0).
Empresa Seção
Continental Airlines 2.2
Swift Company 3.2
Memorial Sloan-Kettering Cancer Center 3.4
United Airlines 3.4
Welch’s 3.5
Sansung Eletronics 4.3
Pacific Lumber Company 6.7
Procter & Gsmblr 8.1
Canadian Pacific Railway 9.3
Air New Zeland 11.2
Taco Bell 11.5
Waste Management 11.7
General Motors 17.9
37
Exerćıcios Atividade de pesquisa
Empresas que utilizam PO como ferramenta
1 Para as 2 aplicações selecionadas, leia o artigo referenciado da aplicação na
seção apropriada. É fornecido um link para esses artigos no site da Bookman.
Para cada uma faça uma apresentação (10min) e entregue um resumo de 1
página explicando a aplicação e os benef́ıcios gerados.
38
Exerćıcios Atividade de pesquisa
Empresas que utilizam PO como ferramenta
2 Leia o artigo referente a Federal Express (FedEx) que descreve
completamente o estudo de PO sintetizado no Exemplo de Aplicação (Seção
1.3). Enumere os diversos benef́ıcios financeiros ou não resultantes desse
estudo.
Entrega e apresentação: 20/02/2020.
Local: Sala de aula e e-mail.
39
Referências
Referências
1 Hillier, F. S. Introdução à pesquisa operacional / 9. ed. 2013.
2 de Andrade, E. L. Introdução à pesquisa operacional: métodos e modelos
para a análise de decisão / 5.ed. 2015.
3 Rodrigues, L. H. et al. Pesquisa Operacional - Programação Linear passo a
passo. 2014.
	Otimização
	Definições
	Pesquisa Operacional
	Definição
	Histórico
	Aplicações práticas de PO
	Exercícios
	Atividade de pesquisa
	Referências