ALGUMAS APLICAÇÕES DE
PESQUISA OPERACIONAL
Maria Teresinha Arns Steiner
Cursos de Graduação (Matemática Industrial; Engenharia de Produção;
outros)
Programa de Pós-Graduação em Métodos Numéricos em Engenharia –
PPGMNE (Mestrado e Doutorado)
Programa de Pós-Graduação em Engenharia de Produção-PPGEP
(Mestrado)
1. Modelagem Matemática
Otimização no Dimensionamento de Equipes de
Trabalho
• em uma Central de Atendimento Telefônico;
• em um Serviço de Rádio-Táxi;
• em uma Companhia de Distribuição de Energia Elétrica;
• outros.
Solução: Modelos Matemáticos (PLI); Simulação;
Meta-Heurísticas; outros.
No caso da COPEL, por exemplo, temos:
A COPEL, no Paraná, está dividida em cinco regionais: Cascavel; Maringá;
Londrina; Ponta Grossa e Curitiba. Os consumidores de energia elétrica da
regional de Curitiba, por sua vez, estão distribuídos em seis agências: Centro;
Portão; Sítio Cercado; Vila Hauer; Bacacheri e Santa Felicidade. Cada
agência é dividida em setores / regiões, e, estas, em rotas de leitura. A
agência do Portão possui 7 setores e 48 rotas de leitura.
Mapa da agência do Portão (7 setores e 48 rotas de leitura)
Dados: Foram considerados os dados do mês de outubro de 2004,
totalizando 21.358 registros, sendo 20.443 ocorrências comerciais
(9.170 executadas e 11.273 com impedimento) e 915 ocorrências
emergenciais.
Foram considerados: a) tempo de atendimento, em minutos, dos serviços
comerciais (com e sem impedimentos) e emergenciais ocorridos na agência
a cada hora do dia;
b) possibilidade das equipes terem jornadas de 4 e/ou 6 e/ou 8 horas,
podendo iniciar a cada hora "cheia" do dia. A demanda por equipes na hora
i é dada por:
Di=Ti/(60x31), já que deseja-se o número de equipes por hora (60 minutos)
e o mês de outubro possui 31 dias.
Sendo xij = número de equipes de jornada j que inicia seu trabalho na hora i e
considerando que cada equipe trabalha 4 e/ou 6 e/ou 8 horas por dia
ininterruptamente e, ainda, que as equipes possuem custos cij diferenciados (ou não),
o modelo matemático fica (72 variáveis xij e 24 restrições):
Função Objetivo:
Minimizar (número e custo de equipes) = i j=4 cij xij + ij=6 cij xij + ij=8 cij xij
sujeito às seguintes restrições:
as equipes que estarão atendendo no intervalo (0:00-1:00) são:
x0,4 + x23,4 + x22,4 + x21,4 + x0,6 + x23,6 + x22,6 + x21,6 + x20,6 + x19,6 + x0,8 + x23,8 +
x22,8 + x21,8 + x20,8 + x19,8 + x18,8 + x17,8  D0
as equipes que estarão atendendo no intervalo (1:00-2:00) são:
x1,4 + x0,4 + x23,4 + x22,4 + x1,6 + x0,6 + x23,6 + x22,6 + x21,6 + x20,6 + x1,8 + x0,8 + x23,8
+ x22,8 + x21,8 + x20,8 + x19,8 + x18,8  D1
... e assim, analogamente, para os demais horários, até:
as equipes que estarão atendendo no intervalo (23:00-0:00) são:
x23,4 + x22,4 + x21,4 + x20,4 + x23,6 + x22,6 + x21,6 + x20,6 + x19,6 + x18,6 + x23,8 + x22,8 +
x21,8 + x20,8 + x19,8 + x18,8 + x17,8 + x16,8  D23
xij  0 e inteiras.
Pode-se simular diversos cenários para este modelo (demandas
mensais; custos diferenciados; outros). Para um dos cenários, as
variáveis xij são: x0,6 = 1; x8,8 = 3; x9,8 = 7; x14,8 = 2; x18,6 = 1; x4,8 = 1,
totalizando 15 equipes..
Cronograma
para o problema
Otimização em Redes (Grafos)
13
12
15
3
14
2
11
1
4
5
10
6
9
8
7
Parte do Mapa Digitalizado da cidade de Curitiba, Pr,
contendo 15 pontos (nós) e 22 arcos
13
1
2
12
15
3
4
3
14
2
11
1
6
5
10
9
1 0 0 0 0 0 0 0 0 0 0 0
0
0
0 1
8
2 1 0 0 0 0 0 0 0 0 0 0
0
0
0 1
10
3 0 1 0 1 0 0 0 0 0 0 0
0
0
0 0
11
4 0 0 0 0 1 0 0 0 0 0 0
0
0
0 0
12
5 0 1 0 0 0 1 0 0 0 0 0
0
0
0 0
6 1 0 0 0 0 0 0 0 0 0 0
0
0
0 0
7 0 0 0 0 0 1 0 1 0 0 0
0
0
0 0
8 0 0 0 0 1 0 0 0 1 0 0
0
0
0 0
9 0 0 0 0 1 0 0 0 0 1 0
0
0
0 0
10 0 0 0 0 0 0 0 0 0 0 0
0
0
0 0
11 0 0 0 1 0 0 0 0 0 1 0
0
0
0 0
12 0 0 1 0 0 0 0 0 0 0 1
0
0
0 0
13 0 0 0 0 0 0 0 0 0 0 0
1
0
0 0
14 0 0 0 0 0 0 0 0 0 0 1
0
1
0 0
15 0 0 0 0 0 0 0 0 0 0 0
0
0
0 0
13
14
8
7
Grafo G(X, A)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
7
9
4
6
5
15
Matriz de Adjacência do Grafo G
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
13
1
2
12
15
3
4
3
14
2
6
C=
7
11
1
5
8
9
4
10
5
10
6
9
11
12
13
1 0 0 0 0 0 0 0 0 0 0 0
0
0
0 1
2 1 0 0 0 0 0 0 0 0 0 0
0
0
0 1
3 2 1 0 1 2 3 0 0 0 0 0
0
0
0 2
4 3 2 0 0 1 2 0 0 0 0 0
0
0
0 3
5 2 1 0 0 0 1 0 0 0 0 0
0
0
0 2
6 1 0 0 0 0 0 0 0 0 0 0
0
0
0 2
7 2 3 0 0 2 1 0 1 2 3 0
0
0
0 3
8 3 2 0 0 1 2 0 0 1 2 0
0
0
0 3
9 3 2 0 0 1 2 0 0 0 1 0
0
0
0 3
10 0 0 0 0 0 0 0 0 0 0 0
0
0
0 0
11 4 3 0 1 2 3 0 0 0 1 0
0
0
0 4
12 3 2 1 2 3 4 0 0 0 2 1
0
0
0 3
13 4 3 2 3 4 5 0 0 0 3 2
1
0
0 4
14 5 4 3 2 3 4 0 0 0 2 1
2
1
0 5
15 0 0 0 0 0 0 0 0 0 0 0
0
0
0 0
14
8
15
7
Algoritmo de Floyd:
Mínimos Custos (C)
e seus Trajetos (T)
T=
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1 1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2 2
3
2
3
3
3
4
5
3
3
3
3
3
3
3
3 2
4
2
5
4
4
4
5
4
4
4
4
4
4
4
4 2
5
2
5
5
5
5
5
5
5
5
5
5
5
5
5 2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6 1
7
6
5
7
7
8
7
7
7
8
9
7
7
7
7 1
8
2
5
8
8
8
5
8
8
8
9
8
8
8
8 2
9
2
5
9
9
9
5
9
9
9
9
9
9
9
9 2
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
11 2
5 11 11 4
5
11 11 11 11 11 11 11 11 2
12 2
3 12 3
4
5
12 12 12 11 12 12 12 12 2
13 2
3 12 3
4
5
13 13 13 11 12 13 13 13 2
14 2
5 12 11 4
5
14 14 14 11 14 13 14 14 2
15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15
2. Problemas de Localização de Instalações
Dado um conjunto de Pontos de Demanda, podemos querer
localizar:
Novos: Postos de Saúde; Caixas Automáticas; Creches;
Escolas; Farmácias; Postos de Gasolina; Outros.
ou, ainda, expandir as instalações já existentes (quais
expandir?)
Onde localizar? Quantas serão as novas instalações?
Dado um conjunto de Pontos de Demanda, podemos querer
formar grupos (clusters) de atendimento.
Para as situações acima;
Leituristas da COPEL; SANEPAR; Fiscais do ESTAR;
para a formação de rotas; locais de prova para o
vestibular.
Os problemas citados podem ser enquadrados como
Problemas das p-medianas (reais ou fictícias)
Solução:
Métodos Exatos; Métodos Heurísticos; ... !!!
Modelos Matemáticos (Exatos);
Algoritmo de Teitz & Bart (Heurístico);
Meta-Heurísticas: Algoritmos Genéticos; Simulated
Annealing; Busca Tabu; outras.
Problema dos Leituristas da SANEPAR.
Mapa da cidade de Pato Branco, PR, destaque à região estudada.
Região em estudo a nível mais detalhado (ruas e quadras).
Pontos de Demanda (774) localizados no centro de cada Trecho.
Os 774 Pontos de Demanda que definem a região estudada.
Deseja-se definir 12 medianas (12 leituristas da SANEPAR).
Solução Heurística (aproximada) para o problema utilizando o
Algoritmo Genético + Algoritmo de Teitz & Bart
Formação dos grupos de Pontos de Demanda em torno das 12
Medianas utilizando o Algoritmo de Gillett & Johnson
3. Problemas de Roteamento de Veículos
Dado um conjunto de Pontos de Demanda, podemos querer
definir a melhor rota a ser feita (minimizando: distância, tempo,
estradas não pavimentadas, outros).
Qualquer serviço de distribuição de mercadorias ou
pessoas; Leituristas da SANEPAR; Carteiros;
Transporte Escolar; Transporte de Funcionários; outros.
Qual a seqüência de pontos de demanda?
Modelos Matemáticos; Ramificação de Christofides; Algoritmos:
Savings de Clarke & Wright; Inserção; Algoritmo do Carteiro
Chinês; ...; Meta-Heurísticas;...
Formação de uma das Rotas utilizando o
Algoritmo do Carteiro Chinês
Determinação do Melhor Trajeto entre Curitiba e Castro
utilizando o Algoritmo de Floyd
(mapa digitalizado do Paraná: vias pavimentadas;
vias pavim. e não pavim.)
Problema dos Correios: Divisão de um Centro de Distribuição
Domiciliar em 13 Distritos Postais (13 carteiros)
4. Problemas de Designação
Podemos querer fazer a Designação Ótima (de acordo com as
preferências):
Motoristas para Horários de Trabalho;
Enfermeiras para Horários de Trabalho;
Jogadores de Futebol para Times;
Turmas de Alunos para Salas de Aulas;
Professores para Turmas de Alunos;
Militares para Horários de Trabalho;
Professores orientadores para orientados;
Alunos para Escolas;
Outros...
Como fazer a Designação?
Modelos Matemáticos; Algoritmos: Húngaro, Matching, ...;
Meta-Heurísticas;...
N.AL.\N.PR.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
4
5
4
3
4
4
6
2
3
4
4
5
8
5
4
5
3
3
5
7
2
4
4
4
4
8
1
5
3
1
2
5
3
6
4
2
3
2
2
2
4
3
6
8
5
5
5
5
8
7
3
8
7
7
5
6
6
7
5
3
8
6
4
2
2
3
1
2
1
4
4
3
3
1
2
3
3
3
2
3
3
3
2
5
1
1
2
2
1
1
2
1
1
1
2
1
4
1
1
1
1
1
1
1
6
3
3
4
3
7
2
3
5
2
5
6
6
7
7
4
4
1
1
4
3
7
5
6
1
4
6
6
1
6
3
6
8
8
1
8
5
8
1
3
6
8
8
6
7
5
5
3
3
7
7
2
7
3
4
2
2
2
6
4
1
7
5
Preferências dos Alunos com relação aos Professores Orientadores
(Modelo Matemático / Algoritmo de Designação)
Militares \ Dias do Mês 1
1
2
3
X
4
5
6
7
8
9
*
10
11
*
12
X
13
14
15
16
17
18
19
20
21
X
22
23
24
25
26
X
27
X
28
29
30
31
32
X
33
34
35
36
X
37
X
38
39
40
41
X
42
43
44
X
45
46
2
3
-
4
5
-
6
X*
7
-
X*
X
*
X
X*
-
X
X*
X
-
X
X
X*
-
X
X
X*
-
X
8
X
X*
X
-
9
10
-
X*
-
X
X
*
-
-
X
-
X*
X
X*
X*
X*
X*
-
X
-
X
X
-
X*
X*
X
-
X*
-
X*
X
X
-
X*
X*
X*
X
X*
-
X*
X
-
X
X*
-
-
X*
X*
-
-
X*
*
X*
-
X*
-
X*
X
X*
-
X
X
X
-
X
-
X
-
-
X
X*
X*
X
X*
-
X*
-
-
X
X
X*
-
X*
X*
-
*
X
X-
X*
-
X
-
X*
X
-
X
X*
X*
X*
X
X
X
X
-
X*
-
X
X*
-
*
X*
-
X
-
X
-
X
X*
-
XX
*
X
-
X
X*
X
X*
X*
X*
-
*
X
-
-
X
-
X
X
-
-
-
X*
X*
-
X
X*
X*
-
X*
-
X*
X
-
X*
X
X*
-
-
X
X
X
X*
X
-
X
X
X
-
X
X*
X
-
-
X*
-
-
X*
X
-
X
-
30
-
X*
X*
X*
-
29
X
X
X
X
-
X*
X
X*
28
-
-
-
X*
-
X*
X
-
-
27
X
X
X
26
X*
X
X*
-
X
25
X
-
X
X
-
X*
-
X*
X*
-
X
X*
-
X
X*
X*
X
X
-
-
X
-
-
X
-
24
X*
X
X
X*
X
23
*
-
-
22
-
-
X*
-
-
X*
X*
X*
-
X
X
X*
X
-
X*
-
X*
X*
X*
X*
X
X*
-
21
X
X*
-
X
-
20
X
-
-
-
19
X*
X
X*
X
X*
18
-
-
X
X
X
-
X*
X*
-
-
-
X*
X*
X
X
-
X
X
*
X*
X
X*
X
-
-
-
X
X*
X*
X*
-
-
X*
X*
17
-
X
-
X*
X*
-
X
-
16
X
X*
X
X
-
15
-
X
X
14
X
-
X*
*
X*
-
X
-
X*
X*
X
-
X*
-
X
X
-
*
13
X
X
X
X
X
X*
X
X*
X*
-
X*
X
X
*
X
X
-
12
X*
-
X
-
X*
-
11
X
-
-
X*
X*
*
X
X
-
-
X
X
X*
-
X*
-
X
X
X
Problema da Escala dos Militares. Resultados 24/24 sem Finais de Semana Seguidos (# mil.: 90; # dias
para escala: 30; demanda diária de mil.: 19; máx. de finais de semana trabalhados: 2; total de escolhas
para plantão: 3x90=270; total de escolhas para não trab.: 6x90=540)
Militares \ Dias do Mês
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
1
2
3
-
4
X
5
6
-
X*
X*
-
X
X
-
X*
X
X*
X
*
*
X
X-
X
X
X*
X
-
X
*
-
X
*
X
X
X
X*
X
X*
X*
XX*
X*
*
X
X
X
X*
X*
X*
X
X*
X
X
-
X*
X
-
X
X*
-
X*
X
*
-
X
-
X*
X*
-
X*
X*
-
*
-
X*
X*
X*
X
X
X
-
*
X
-
X
-
X
X
-
*
X
-
-
X*
X*
X
-
X
-
X
*
X
X
X*
*
-
XX*
X
-
*
X
-
X*
-
X*
X
X*
X
X*
-
*
X*
*
X
-
X
X
-
-
X
X
X*
X
-
X
-
X
X*
X
-
-
*
*
X*
X
X*
X
X
X
-
X
-
X*
X*
X
X
-
X
X-
*
X*
X
-
*
X
-
X
X
X
X
X*
X
X
X
X*
XX
-
-
-
-
X
-
-
X*
-
-
X
-
X
-
X*
-
30
X
X
X
X*
X*
29
X*
-
X
X
X
X
X
X*
X
-
28
X*
X
X
-
X
-
27
X*
X
X*
X
-
X*
-
X*
X
X
X*
-
26
-
X-
X
X
-
X
-
X*
-
-
X
X
*
X
-
X
X
X*
X*
*
X
-
-
X
X
X*
-
X
-
25
-
X*
X*
X
-
24
X
X
X*
-
23
X
-
X*
X
X*
-
X
X
22
X*
-
X
-
X*
X
X
-
X*
-
X*
*
X
*
-
21
X
-
X*
X*
X
X
-
20
X
-
-
X
X*
-
-
X
-
19
X
X
-
X
X*
X
18
X*
X
-
X*
-
17
X*
X*
X
X*
-
X
X*
-
X
X*
X-
-
X
-
X
X
X
X
-
-
-
-
X-
X*
-
X
-
*
X*
X
X
-
-
X*
X
X
-
X
-
X*
X*
-
16
X
X*
X
X
*
X
X
X
X*
X
-
X
-
15
-
X*
X
-
14
X*
-
X*
X
-
X
X
X*
X
13
X*
X
X
-
12
XX
X*
X*
X
X
X
X
11
X
X
X*
X
X
X*
-
10
-
X
-
X
X*
-
X
-
9
X
X
X*
X*
X
X
8
X
-
*
-
X
X
7
*
X*
-
-
X
X
X*
X*
X
X*
-
*
X*
-
X*
X
X
X
X*
X
-
X
X
X
X*
-
5. Problemas de Reconhecimento de Padrões
Como fazer o Reconhecimento (e Previsão) de Padrões
pertencentes a diferentes classes.
 Diagnóstico Médico (reconhecer clientes com cálculo de
clientes com câncer no duto biliar);
 Crédito Bancário (reconhecer clientes adimplentes de
clientes inadimplentes);
 Controle de Qualidade (reconhecer azulejos de boa
qualidade de azulejos de baixa qualidade), (idem para
bobinas de papel);
 Engenharia de Avaliações (prever o valor de um
imóvel);
 Processos Jurídicos (prever o tempo de trâmite de um
processo);
Um certo padrão P pertence à classe A ou B?
Etapas do Processo Descoberta de Conhecimento em Bases
de Dados (Knowledge Discovery in Databases - KDD)
Solução
São muitos os métodos de RP, dentre os quais podemos citar:
Modelos Matemáticos (PL);
Métodos Estatísticos (Fisher, Regressão Logística, ...);
Meta-Heurísticas (Redes Neurais, AG, AS, BT, ...);
Algoritmos para Extração de Regras de uma RN
Treinada;
Árvores de Decisão.
Ilustração gráfica do método “Geração de uma Superfície que Minimiza Erros”
(Programação Linear)
Ilustração Gráfica da “Função
Discriminante Linear de Fisher”
(Método Estatístico)
Ilustração Gráfica do Método
“Regressão Logística”
(Método Estatístico)
Ilustração Gráfica de uma
“Rede Neural de Múltiplas
Camadas” (Metaheurística)
Exemplo de uma Rede Neural de Múltiplas (3) Camadas
(Configuração: 54 - 4 - 1)
Exemplo de uma Árvore de Decisão para um Problema Médico
6. Otimização em uma Rede de Distribuição de Energia
Elétrica
Problemas: da Restauração da Rede;
Reconfiguração (Minimizar as Perdas de Energia);
Expansão da Rede (Localização Ótima de novas Sub
Estações; de novos alimentadores; ...)
Dimensionamento Ótimo de Equipes de Trabalho;
Outros.
Problema da Restauração da Energia Elétrica em uma Rede:
Ocorrida a falha de energia em uma determinada região de uma
cidade e localizado e isolado o bloco, causa do problema, o objetivo
é determinar de que forma restaurar a energia (seqüência de
operações com as chaves - abertura e fechamento) de forma a
minimizar o tempo sem energia.
Objetivos da Restauração:
1) o plano de restauração deve ser executado em curto intervalo
de tempo;
2) restaurar tanta carga quanto possível na área “fora de
serviço”;
3) o número necessário de operações de chaveamento
(abertura e fechamento) deve ser mínimo;
4) a configuração do sistema restaurado deve estar o mais
próximo possível da configuração original;
5) a estrutura do sistema radial deve ser mantida;
6) nenhum componente deve ficar sobrecarregado.
Dados:
No Paraná há cerca de 350 sub-estações (SE), sendo que em
Curitiba há cerca de 20 SE e 130 alimentadores. Em um único
alimentador podemos ter, por exemplo, 50 blocos, 60 chaves, 450
trechos.
Fluxograma para Solução do Problema de Restauração
Uma Rede Elétrica representada como um Grafo (X, A):
3 SE; 3 alimentadores; 35 blocos e 44 arcos.
Se, por exemplo, ocorrer uma falha no bloco 2, como fica?
Resultado após a execução do Algoritmo Heurístico desenvolvido (RHP =
Restoration Heuristic Procedure). Se a falha ocorreu no bloco 2: teremos 9
chaveamentos (manobras) : [(1,2), (3,2), (4,2), (7,2)] para isolar o defeito;
abrir: (7,8), (10,11); fechar: (5,24), (12,17), (13,26). Não há como alimentar
alimentar os blocos 3 e 8.
OBRIGADA!!!
[email protected]