Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Prof. Marco Antonio M. Carvalho
Temas de Pesquisa
BCC501 – Introdução a Computação
Universidade Federal de Ouro Preto – MG
01/09/2011
Quem Sou Eu?
• Bacharel em Ciência da Computação (2005) – FaculdadesIntegradas de Caratinga
• Mestre em Engenharia Eletrônica e Computação (2008) – ITA• Doutorando em Engenharia Eletrônica e Computação (2009-??)
– ITA• Interesses:
• Teoria da Computação, Otimização Combinatória, Pesquisa Operacional.
• Problemas de Corte e Empacotamento;• Sequenciamento de Padrões;• Programação de Torneios Esportivos;• Problemas em Matrizes e Grafos;• Problemas de Escalonamento de Pessoal;• Análise de Risco;• Maratona de Programação.
• Professor do DECOM/UFOP desde 2010/2• Disciplinas de programação.
2
Otimização Combinatória
• Área da Computação e Matemática Aplicada queestuda problemas combinatórios:
• Temos um problema em mãos;
• Temos um conjunto de elementos, e precisamoscombiná-los (não necessariamente todos) para geraruma solução para nosso problema
• Existem várias combinações;
• Cada uma com uma importância diferente;
• Queremos sempre a melhor!
• Podem haver restrições para criarmos umacombinação.
4
Um Problema Combinatório
5
Começando a Complicar…
6
Nada é Tão Ruim Que NãoPossa Piorar…
7
Um Problema CombinatórioDifícil
8
Um problema CombinatórioBeeeeeem Difícil
9
Um Exemplo Mais Prático
• Um ladrão está prestes a roubar algumas barras de ouro e transportar em sua “mochila”
• Na verdade parece mais uma lancheira…
• (In)felizmente, sua “mochila” só suporta 15 quilos de peso
• Existem 4 barras de 12 Kg, 2 Kg, 8kg e 4 Kg.
• Quais barras ele deve levar para “lucrar” o máximo e evitar que sua “mochila” quebre?
10
Um Exemplo Mais Prático
• O Problema:
• Maximizar o peso das barras contidas na mochila;
• Os Elementos
• As 4 barras de ouro
• A Restrição
• A soma dos pesos das barras transportadas não podeexceder 15 Kg.
11
Um Exemplo Mais Prático
• As possíveis soluções:• 12 Kg.
• 12 Kg + 2Kg;
• 8 Kg + 4 Kg;
• 8 Kg + 4 Kg + 2 Kg;
• 4 Kg;
• 8 Kg;
• 2 Kg;
• 8 Kg + 2 Kg;
• 4 Kg + 2 Kg;
• 12 Kg + 8 Kg + 4 Kg + 2 Kg;
(Nosso amigo ladrão é meio limitado…)12
O Quê a Computação Tem a VerCom Isso?
13
O Quê A Computação Têm a Ver Com Isso?
• Se tivermos n objetos, podemos ter até n! combinações
• Alguém vai testar cada possível solução?
• Quanto tempo vai demorar?
14
O Quê A Computação Têm a Ver Com Isso?
• É possível criar algoritmos que “cortamcaminho” e testam apenas algumas soluções
• Podem garantir que acharão a melhor solução, oupelo menos vão achar uma solução razoávelrapidamente.
• Quem cria estes algoritmos são profissionais da Ciência da Computação, Matemática, e algumasEngenharias.
15
Pesquisa Operacional
• Muito resumidamente (e sem rigor), a PesquisaOperacional é a Otimização Combinatória aplicada a problemas de aplicação prática, geralmenterelacionados à otimização de processos produtivos;
• Aplicações:
• Militares;
• Em Comunicações;
• Em Logística;
• Em Saúde;
• Em Indústrias;
• Etc.16
Problemas de Corte
• Algumas indústrias realizam o corte de chapas de metal, papel, vidro etc.
• As chapas são muito grandes, e devem ser cortadaspara produzir peças menores;
• É necessário cortar uma certa quantidade de cadatipo de peça;
• Quase nunca as peças aproveitam toda a chapa
• Desperdício de chapa é prejuízo!
17
Problemas de Corte
• É necessário determinar quais peças serão cortadasem cada chapa, de modo que o desperdício sejaminimizado.
18
Problemas de Corte
19
Problemas de Corte
20
Escalonamentode Pessoal
• Outro problema de grande aplicação prática é o de escalonamento
• Temos funcionários que realizam tarefas específicas;
• Precisamos elaborar uma escala de trabalho de forma que todos os serviços de uma empresa sejamprestados corretamente;
• Precisamos respeitar a legislação trabalhista
• Não podemos fazer um funcionário trabalhar 12 horastodos os dias.
• Não desejamos contratar mais funcionários. 21
Escalonamentode Pessoal
• Este problema se aplica a qualquer meio de transporte
• Aviões;
• Ônibus;
• Trens;
• Navios;
• Etc.
• O objetivo é economizar.22
Problemas de
Empacotamento
• Coleção de problemas industriais em que é necessário“empacotar” objetos em caixas, contêineres, paletes e baús de caminhões;
• As restrições são relativas a:
• Estabilidade física dos objetos (3D);
• Ordem de inserção e retirada dos objetos do “pacote”.
• O objetivo é maximizar a quantidade de objetosempacotados, diminuindo a quantidade de “pacotes”.
23
23
Problemas de Empacotamento
24
Alocação de Torneios Esportivos• Um problema não aplicado à administração;
• Na liga americana de Beisebol, os times saem emturnê• Fazem viagens longas enfrentando adversários e
retornam para casa.
• As viagens dos times devem ser justas• Quilometragem parecida;
• Um time não pode cansar mais que o outro.
• Além disso, é necessário respeitar as regras do campeonato• Todos os times devem jogar no máximo 3 vezes for a
de cada em sequência.25
Alocação de Torneios
Esportivos
26
Santos
Grêmio
Atlético
Vitória
1372Km
3090Km
1712Km
586Km
1
2
33
Grêmio
Santos
Atlético
Vitória
1
2
3 3
1712Km
1712Km
1372Km
586Km
Vitória x Atlético | Grêmio x Atlético | Atlético x Santos
Distância total percorrida: 6760 Km
Atlético x Vitória | Grêmio x Atlético | Atlético x Santos
Distância total percorrida: 5382 Km
Economia: 1378 Km
(1) (2)
Alocação de Torneios
Esportivos
• O problema consiste em elaborar a tabela de um campeonato esportivo por pontos corridos;
• O objetivo é: • Minimizar a distância total percorrida pelos times;
• Minimizar a diferença entre as distânciaspercorridas por cada time;
• Minimizar a alternância entre jogos comomandante e visitante;
• Etc.27
Alocação de Torneios
Esportivos
28
Vários Outros Problemas
• Como visto, qualquer problema de uma indústriaque envolva combinação de elementos e minimização/maximização/equilíbrio de um objetivoé um problema de Pesquisa Operacional
• Elaborar rotas de veículos de transporte;
• Determinar onde serão fixadas antenas de telefonia;
• Determinar onde serão localizados serviços básicos emuma cidade;
• Planejar o “estacionamento” de navios em um porto
• Determinar a melhor forma de produzir/transportarminérios.
29
E daí?
30
O que eu ganho com isso se não
possuo uma linha áerea, não
corto nada, não tenho
contêineres, não sou o Ricardo
Teixeira e não sou ladrão?
Epic
• O gasto com tripulações é até 20% dos gastos de uma empresa aérea• A Air New Zealand economizou $ 15 milhões em 2010.
• A Gerdau manipula 4,178 milhões de toneladas de metal laminado por ano• 16% de margem, e lucrou R$ 503 milhões no último
trimestre.
• Um contêiner precisa ser alugado ou comprado• Taxa para permanecer no porto de saída;
• Taxa para embarcar em navio;
• Taxa de manipulação;
• Taxa para permanecer no porto de chegada.31
Win!
Quanto uma empresa destas estariadisposta a pagar para economizarem
cifras milionárias?
32
Carreira no Mercado e na Academia
33
Gapso - RJ
34
UniSoma - SP
35
Neolog - SP
36
Periódico e Congresso Nacional
37
Periódicos Internacionais
38
Sociedades Internacionais
39
O Que É Necessário?• Saber programar bem;
• Gostar de programar;
• Programar;
• Aceitar desafios;
• Criatividade;
• Leitura em inglês;
• Responsabilidade;
• Dedicação;
• Disposição;
• Transpiração;
• Persistência.
40
Como Começar?
• Introdução à Programação;
• Estruturas de Dados;
• Grafos;
• Introdução à Otimização;
• Iniciação Científica.
41
42
Perguntas?
FIM
43