Upload
lythuy
View
213
Download
0
Embed Size (px)
Citation preview
MB – 756
PESQUISA OPERACIONAL
APLICADA À PRODUÇÃO
Professor: Rodrigo A. Scarpel
www.mec.ita.br/~rodrigo
Programa do curso:
Semana Conteúdo
1
Princípios de POAP :
1. O processo decisório no âmbito da produção e da pesquisa operacional;
2. Abordagens de pesquisa operacional para suportar o processo decisório:
2.1. Criação de Modelos de Previsão
2.2. Extração de Conhecimento de Bases de Dados
2.3. Otimização
2.4. Simulação
2
Métodos de Previsão em POAP :
1. Propósitos da Previsão
2. Processo de Criação de Modelos de previsão
2.1. Previsão por séries temporais
2.2. Previsão por modelos causais
2.3. Previsão para variáveis categóricas
3
Extração de Conhecimento de Bases de Dados em POAP :
1. Aplicações do Processo ECBD em problemas de Produção
2. O Processo de Extração de Conhecimento de Bases de Dados (ECBD):
2.1. Redução de dimensão e visualização
2.2. Segmentação
2.3. Classificação
4
Otimização em POAP :
1. Aplicação de métodos de Otimização em problemas da Cadeia de Suprimentos:
1.1. Planejamento logístico: transporte e distribuição, localização e cobertura, caminho mais curto.
1.2. Planejamento da Produção: planejamento agregado, otimização em múltiplos períodos, dimensionamento de
estoques.
1.3. Avaliação de eficiência: análise de envoltória de dados
1.4. Gerenciamento de projetos: seleção de projetos, problema do caminho crítico.
5 Prova: 04/12/14
Abordagens em modelos para ECBD:
1. Processo de ECBD:
2. CRISP-DM (Cross Industry Standard Process for Data Mining): 3. SEMMA:
Abordagem em modelos para extração de
conhecimento de bases de dados:
Observações:
• É um processo sequêncial com possibilidade de retorno
• As etapas de seleção, pré-processamento e transformação dos
dados consomem cerca de 80% do tempo.
Objetivos da seleção:
• Criar um sub-conjunto dos dados em função dos objetivos da
análise
• Colocar dados no “formato analítico”:
• Observações (linhas): uma linha por instância
• Atributos ou variáveis (colunas)
• Operações necessárias:
• Transposição,
• Sumarização, …
Etapa 1: Seleção dos dados
Objetivos do pré-processamento:
• Colocar dados no “formato analítico”: observações (linhas) e
atributos (colunas)
• Verificar a qualidade dos dados
Fatores que degradam a qualidade dos dados:
• Dados com erro: respostas falsas, erros na tabulação das
respostas,…
• Outliers: observações que aparentemente são inconsistentes
quando comparadas às outras observações.
• Dados faltantes (missing values)
Etapa 2: Pré-processamento dos dados
Etapa 2: Pré-processamento dos dados
DETECÇÃO DE OUTLIERS:
Origem: dados com erro ou observação pertencente a outra
população.
Critério: O critério para a definição de outliers varia muito conforme os
autores. De maneira geral, considera-se outlier uma medida
acima ou abaixo de 2,5 desvios-padrão da média.
Forma de detecção: estatísticas de sumarização, histogramas,
boxplot.
Tratamento: eliminação dos outliers
ou transformação dos dados
Etapa 2: Pré-processamento dos dados
DADOS FALTANTES (MISSING VALUES)
• Missing values é zero (não ocorreu) ou é falta de informação
(não sei se ocorreu)?
• Deve-se tomar cuidado no tratamento dos missing values.
• Tratar? Eliminar a variável? Eliminar a observação?
?
?
? ?
? ?
?
?
observações
variáveis Apenas 8 dos 144 valores são
missing (5,55%), porém apenas
6 observações seriam utilizadas.
Etapa 2: Pré-processamento dos dados
DADOS FALTANTES (MISSING VALUES)
Tratamento: depende de quantos dados estão faltando (percentual de
missing values) e de sua distribuição.
Alternativas:
• Omitir observações: é aceitável quando os dados faltantes estão
concentrados em algumas observações.
• Omitir variáveis: é aceitável quando os dados faltantes estão
concentrado em algumas variáveis.
• Atribuir valores:
• Substituir pela média
• Método analítico.
Objetivos da transformação dos dados:
• Criação de índices e taxas: são amplamente utilizados em
gerenciamento.
• Padronização e normalização dos dados: para eliminar efeitos de
escala ou adequar os dados às hipóteses do modelo.
• Eliminar outliers:
• Log (ou Ln), Raiz, …
• Categorização
Etapa 3: Transformação dos dados
Etapa 4: Mineração dos dados
Objetivos da mineração dos dados:
1. Análise de associação (link analysis)
2. Análise de sequência
3. Sumarização (por Visualização)
4. Modelagem de dependência
5. Formação de agrupamentos (clustering)
6. Classificação
7. Previsão: Criar um mapeamento dos dados a uma variável
contínua
Mineração dos dados: Sumarização
• Objetivo: Descrever um conjunto de dados considerando
• Conjunto de variáveis existentes e suas relações
• Instâncias ou observações
• Alternativa:
• Usar técnicas multivariadas de visualização:
• Análise de correspondência
• Wordclouds
• Análise de Homogeneidade
Mineração dos dados: Sumarização
• Análise de correspondência:
Baseada na decomposição em valores singulares (SVD) da matriz
de dados. Exemplo:
Posicionamento de cinco airlines
AA UA US Con SW
Convenience 5 8 3 3 3
Punctuality 6 5 5 4 8
Overall_service 8 7 5 4 6
Comfort 6 6 4 4 3
MD: Modelagem de Dependência
• Objetivo: Descrever as relações de um conjunto de variáveis
• Alternativas:
• Usar técnicas multivariadas de visualização:
• Análise de correspondência múltipla (MJCA)
• BIPLOT
• Estabelecer uma função que relacione as variáveis:
• Análise Fatorial Exploratória
MD: Modelagem de Dependência
• Exemplo 1: Pesquisa de mercado – Cervejas (código.3)
• 162 respondentes
• Atributos:
• Marca: Brahma, Antárctica
• Faixa de Renda: AB, C, DE
• Sexo: Masculino, Feminino
• Faixa de idade: 18-29, 30-39, 40-49, 50+
• Tipo: Regular (Pilsen), Chopp, Outras
Mineração dos dados: Sumarização
• Análise de componentes principais / Biplot:
X1
X2
X1
X2
21,211,11 XwXwCP
211,21,1
2
2
2
1,2
2
1
2
1,1
1,2
1,1
2212
2111
1,21,1
2
wwww
w
wwwVMax
1
..
2
1,2
2
1,1 ww
AS
Formulação
Mineração dos dados: Sumarização
• Princípios de Análise Fatorial:
Objetivo: mensurar fatores não observáveis (também chamados de
constructos)
Experimento de Spearman (1904):
Desta forma, esperavasse que o desempenho dos alunos, em cada
disciplina, dependesse de um fator comum e de um fator específico.
MATEMÁTICA
(M)
FÍSICA
(F)
QUÍMICA
(Q)
INGLÊS
(I)
HISTÓRIA
(H)
L. PORTUGUESA
(L)
FATOR
()
eM eF eQ eI eH eL
M
F Q I
H L
Mineração dos dados: Sumarização
• Princípios de Análise Fatorial:
Formulação do problema da análise fatorial:
No exemplo:
jixxAS
MinouMaxOF
jiji
p
i
p
i
ii
,,..
1..
1 1
22
MATEMÁTICA
(M)
FÍSICA
(F)
QUÍMICA
(Q)
INGLÊS
(I)
HISTÓRIA
(H)
L. PORTUGUESA
(L)
FATOR
()
eM eF eQeI eH
eL
M
F QI
HL
MATEMÁTICA
(M)
FÍSICA
(F)
QUÍMICA
(Q)
INGLÊS
(I)
HISTÓRIA
(H)
L. PORTUGUESA
(L)
FATOR
()
FATOR
()
eMeM eFeF eQeQeIeI eHeH
eLeL
M
F QI
HL
=0,8
=0,7 0,9= =0,6 =0,5
=0,65
0,36 0,51 0,19 0,64 0,75 0,58
Variância explicada (comum) = 2,973 (49,5%)
MD: Modelagem de Dependência
• Exemplo 3: Análise Financeira de empresas (código.4)
• 172 Empresas de capital aberto (com ações na Bovespa)
• Índices financeiros:
• Margem de lucro líquido (MLL)
• Retorno sobre o ativo total (ROA)
• Giro do ativo total (GA)
• Endividamento Geral (EG)
• Endividamento Financeiro (EG)
• Liquidez corrente (LC)
MD: Formação de Agrupamentos
• Objetivo: Agrupar observações e/ou atributos, de acordo com
algum critério de similaridade.
• Alternativas:
• Utilização de métodos hierárquicos:
• Método do vizinho mais próximo
• Método do centróide
• Método de Ward
• Utilização de métodos não-hierárquicos: K-médias
• Utilização de métodos baseados em inteligência artificial: SOM
Clientes desenvolvem preferências por marcas que atendem melhor
suas necessidades e entregam mais valor
Segmentation
Identificar segmentos
Targeting
Selecionar alvo
Positioning
Criar vantagem
competitiva
Recursos são focados para melhor atender as necessidades dos
clientes e entregar mais valor
Clientes se tornam leais a marcas / fornecedores, repetem compras,
comunicam experiências favoráveis
Lealdade a Marcas / fornecedores geram aumento na fatia de
mercado e criam barreiras a entrada de novos competidores
Menos recursos são necessários, ao longo do tempo, para manter a
fatia de mercado devido a lealdade às marcas / fornecedores
Lucratividade (valor da empresa) aumentam
Como o STP cria valor:
MD: Formação de Agrupamentos
Níveis de segmentação:
MD: Formação de Agrupamentos
Mercado
de Massa
Macro
Segmentos
Micro
Segmentos
Segmentos
de Um
A B C
Método da ligação simples (vizinho mais próximo) :
S1 S2 S3 S4 S5 S6
S1 0 2 181 221 625 821
S2 2 0 145 181 557 745
S3 181 145 0 2 136 250
S4 221 181 2 0 106 212
S5 625 557 136 106 0 26
S6 821 745 250 212 26 0
CLUSTER Observ Renda Educação
1 S1 5 5
2 S2 6 6
3 S3 15 14
4 S4 16 15
5 S5 25 20
6 S6 30 19
0
5
10
15
20
25
30
35
0 2 4 6 8
S1&S2 S3&S4 S5 S6
S1&S2 0 145 557 745
S3&S4 145 0 106 212
S5 557 106 0 26
S6 745 212 26 0
0
5
10
15
20
25
0 10 20 30 40
Renda (R$ mil)
Ed
uca
çã
o (
an
os)
DKL
Cluster KCluster K
Cluster LCluster L
),( min min K jiLKL xxdCjCiD DKL
Cluster KCluster K
Cluster LCluster L
DKL
Cluster KCluster K
Cluster LCluster L
),( min min K jiLKL xxdCjCiD ),( min min K jiLKL xxdCjCiD
MD: Formação de Agrupamentos
S1&S2 S3&S4 S5&S6
S1&S2 0 145 557
S3&S4 145 0 106
S5&S6 557 106 0
1 2 3 4 5 6
0,00
5,25
10,51
15,76
Observations
Distance DENDOGRAMA
S1&S2 S3&S4 S5 S6
S1&S2 0 145 557 745
S3&S4 145 0 106 212
S5 557 106 0 26
S6 745 212 26 0
0
5
10
15
20
25
0 10 20 30 40
Renda (R$ mil)
Ed
uca
çã
o (
an
os)
S1&S2 S3&S4&S5&S6
S1&S2 0 145
S3&S4&S5&S6 145 0
Método da ligação simples (vizinho mais próximo) :
MD: Formação de Agrupamentos
Média = (21/2+ ...+1451/2) / 5 = 6,05
Diferenças:
NÚMERO IDEAL DE AGRUPAMENTOS:
Há diversas abordagens para determinar o número ideal de agrupamentos:
1. Arbitrar o número (valor conhecido, razões práticas).
2. Escolher o número que resulte nos agrupamentos de mais fácil
interpretação.
3. Distância entre os agrupamentos:
1 2 3 4 5 6
0,00
5,25
10,51
15,76
Observations
DistanceDENDOGRAMA
21/2 21/2
261/2
1061/2 1451/2
- 21/2 = 3,68
1061/2 - 261/2 = 5,19
261/2 1451/2 - 1061/2 = 1,75
MD: Formação de Agrupamentos
Método do centróide:
S1 S2 S3 S4 S5 S6
S1 0 2 181 221 625 821
S2 2 0 145 181 557 745
S3 181 145 0 2 136 250
S4 221 181 2 0 106 212
S5 625 557 136 106 0 26
S6 821 745 250 212 26 0
CLUSTER Observ Renda Educação
1 S1 5 5
2 S2 6 6
3 S3 15 14
4 S4 16 15
5 S5 25 20
6 S6 30 19
0
5
10
15
20
25
30
35
0 2 4 6 8
CLUSTER Observ Renda Educação
1 S1&S2 5,5 5,5
2 S3&S4 15,5 14,5
3 S5 25 20
4 S6 30 19
0
5
10
15
20
25
30
35
0 1 2 3 4 5
2
LKKL xxD
X
X DKLCluster KCluster K
Cluster LCluster LX
X DKLCluster KCluster K
Cluster LCluster L
0
5
10
15
20
25
0 10 20 30 40
Renda (R$ mil)
Ed
uca
çã
o (
an
os)
S1&S2 S3&S4 S5 S6
S1&S2 0 181 590,5 782,5
S3&S4 181 0 120,5 230,5
S5 590,5 120,5 0 26
S6 782,5 230,5 26 0
MD: Formação de Agrupamentos
0
5
10
15
20
25
0 10 20 30 40
Renda (R$ mil)
Ed
uca
çã
o (
an
os)
S1&S2 S3&S4 S5 S6
S1&S2 0 181 590,5 782,5
S3&S4 181 0 120,5 230,5
S5 590,5 120,5 0 26
S6 782,5 230,5 26 0
CLUSTER Observ Renda Educação
1 S1&S2 5,5 5,5
2 S3&S4 15,5 14,5
3 S5&S6 27,5 19,5
0
5
10
15
20
25
30
0 1 2 3 4
S1&S2 S3&S4 S5&S6
S1&S2 0 181 680
S3&S4 181 0 169
S5&S6 680 169 0
CLUSTER Observ Renda Educação
1 S1&S2 5,5 5,5
2 S3&S4&S5&S6 21,5 17
0
5
10
15
20
25
30
0 1 2 3 4
0
5
10
15
20
25
0 10 20 30 40
Renda (R$ mil)
Ed
uca
çã
o (
an
os)
Método do centróide:
MD: Formação de Agrupamentos
0
5
10
15
20
25
0 10 20 30 40
Renda (R$ mil)
Ed
uca
çã
o (
an
os)
S1&S2 S3&S4 S5&S6
S1&S2 0 181 680
S3&S4 181 0 169
S5&S6 680 169 0
CLUSTER Observ Renda Educação
1 S1&S2 5,5 5,5
2 S3&S4&S5&S6 21,5 17
0
5
10
15
20
25
30
0 1 2 3 4
S1&S2 S3&S4&S5&S6
S1&S2 0 388,25
S3&S4&S5&S6 388,25 0
1 2 3 4 5 6
0,00
5,25
10,51
15,76
Observations
Distance
DENDOGRAMA
1 2 3 4 5 6
0,00
5,25
10,51
15,76
Observations
Distance
DENDOGRAMA
Método do centróide:
MD: Formação de Agrupamentos
CLUSTERS
POSSÍVEIS 1 2 3 4 5 QM
1 S1, S2 S3 S4 S5 S6 0,5
2 S1, S3 S2 S4 S5 S6 45,25
3 S1, S4 S2 S3 S5 S6 55,25
4 S1, S5 S2 S3 S4 S6 156,25
5 S1, S6 S2 S3 S4 S5 205,25
6 S2, S3 S1 S4 S5 S6 36,25
7 S2, S4 S1 S3 S5 S6 45,25
8 S2, S5 S1 S3 S4 S6 139,25
9 S2, S6 S1 S3 S4 S5 186,25
10 S3, S4 S1 S2 S5 S6 0,5
11 S3, S5 S1 S2 S4 S6 34,0
12 S3, S6 S1 S2 S4 S5 62,5
13 S4, S5 S1 S2 S3 S6 26,5
14 S4, S6 S1 S2 S3 S5 53,0
15 S5, S6 S1 S2 S3 S4 6,5
MEMBROS DOS CLUSTERS
Por esse método os agrupamentos são formados pela maximização da
homogeneidade dentros dos grupos. Para o cálculo da homogeneidade
utiliza-se a média de quadrados:
CLUSTER Observ Renda Educação
1 S1 5 5
2 S2 6 6
3 S3 15 14
4 S4 16 15
5 S5 25 20
6 S6 30 19
0
5
10
15
20
25
30
35
0 2 4 6 8
((5-5,5)2+(6-5,5)2+ (5-5,5)2+(6-5,5)2)/2
ANOVA
ANOVA
LK
LK
KL
nn
xxD
11
2
Método de Ward:
MD: Formação de Agrupamentos
CLUSTERS MEMBROS DOS CLUSTERS
POSSÍVEIS 1 QM
1 S1, S2,S3,S4,S5,S6 58,5
CLUSTERS
POSSÍVEIS 1 2 3 4 QM
1 S1, S2,S3 S4 S5 S6 54,7
2 S1, S2,S4 S3 S5 S6 67,335
3 S1, S2,S5 S3 S4 S6 197,335
4 S1, S2,S6 S3 S4 S5 261,335
5 S1, S2 S3,S4 S5 S6 1,0
6 S1, S2 S3,S5 S4 S6 34,5
7 S1, S2 S3,S6 S4 S5 63,0
8 S1, S2 S4,S5 S3 S6 27,0
9 S1, S2 S4,S6 S3 S5 53,5
10 S1, S2 S5,S6 S3 S4 7,0
MEMBROS DOS CLUSTERS
...
Método do centróide:
MD: Formação de Agrupamentos
Para o método Ward, além das abordagens anteriores, utiliza-se:
1. R2 = 1 – (SQW / SQT), em que
SQW é a soma de quadrados “within-cluster”,
SQT é a soma de quadrados total
SQT = nT * HeightT
SQW = n1*Height1 + n2*Height2 + n3*Height3
Método do centróide: número ideal de agrupamentos
MD: Formação de Agrupamentos
• Exemplo 2: Pesquisa de mercado – Cervejas (código.6)
• 162 respondentes
• Atributos:
• Marca: Brahma, Antárctica
• Faixa de Renda: AB, C, DE
• Sexo: Masculino, Feminino
• Faixa de idade: 18-29, 30-39, 40-49, 50+
• Tipo: Regular (Pilsen), Chopp, Outras
MD: Formação de Agrupamentos
• Exemplo 3: Análise Financeira de empresas (código.7)
• 172 Empresas de capital aberto (com ações na Bovespa)
• Índices financeiros:
• Margem de lucro líquido (MLL)
• Retorno sobre o ativo total (ROA)
• Giro do ativo total (GA)
• Endividamento Geral (EG)
• Endividamento Financeiro (EG)
• Liquidez corrente (LC)
MD: Formação de Agrupamentos
MD: Modelos de classificação
• Objetivo: Associar as instâncias (observações) a categorias pré-
definidas.
• Alternativas:
• Árvores de regressão e classificação (CART)
• Análise discriminante
• Regressão logística
• Redes neurais artificiais
• Modelos de programação matemática
• Support vector machine
MD: Modelos de classificação
• Boas práticas na criação de modelos de classificação:
Dividir os dados em bases de treinamento e validação (pode ter
uma terceira que é a base de teste).
Training Set Test SetTraining Set Test Set
Training Set Test SetTraining Set Test Set
Overfitting:
Better Fitting:
• Sistema de classificação que particiona o espaço de atributos de forma a criar regras para definir as classes
• Resultado: um conjunto de regras e uma árvore (diagrama)
• Algoritmo: CART (Classification And Regression Trees)
• Elementos da árvore de decisão
▫ Nó raiz (primeira questão)
▫ Ligações ou ramos (possíveis respostas)
▫ Outros nós (outras questões)
▫ Nó terminal (decisão final)
• A classificação de uma observação inicia no nó raiz e segue as ligações correspondentes às respostas corretas até chegar no nó terminal.
AUTOMATIC INTERACTION DETECTION
MD: Modelos de classificação
AUTOMATIC INTERACTION DETECTION
Esse modelo é construído a partir de um conjunto de treinamento seguindo algumas regras:
• Partição: escolha da melhor partição
• Parada: quando parar de particionar
A acurácia é obtida a partir de um conjunto de teste.
Ilustração: classificação em risco
IDADE > 35
NÃO SIM
Alto risco Renda anual maiorque R$100.000,00
NÃO SIM
Médio risco Baixo risco
Acurácia = 92.54 %
IDADE > 35
NÃO SIM
Alto risco Renda anual maiorque R$100.000,00
NÃO SIM
Médio risco Baixo risco
Acurácia = 92.54 %Idade (anos)
Ren
da
an
ual
(R$)
MD: Modelos de classificação
• Critério de partição:
▫ Índice de Gini=
▫ Entropia=
C
jjp
1
21
C
jjj pp
1
)log(
AUTOMATIC INTERACTION DETECTION
MD: Modelos de classificação
C
jjj pp
Entropia
1
5452,0)8/1log()8/1(2)8/3log()8/3(2)log(
:
C
jjj pp
1
1781,0)7/6log()7/6()7/1log()7/1()log(
Exemplo:
• Exemplo 1: Detecção de falhas (código.8)
• Variável dependente: Falha (Sim ou Não)
• Variáveis independentes:
• Viscosidade da tinta
• Temperatura da tinta
• Umidade do papel
• Velocidade da impressora
• Percentual de tinta
• Percentual de solvente
MD: Modelos de classificação AUTOMATIC INTERACTION DETECTION
• Sistema de classificação que se baseia nas médias das variáveis independentes por classe
• Resultado: Equação de partição e ponto de corte
• Algoritmo: Análise de Regressão
ANÁLISE DISCRIMINANTE
MD: Modelos de classificação
TREINO PARA
+ -
DE + 92,9 7,7
- 7,1 92,3
VALIDAÇÃO PARA
+ -
DE + 92,4% 7,8%
- 7,6% 92,2%
ACERTO GLOBAL = 92,6% ACERTO GLOBAL = 92,3%
Acerto global = (n11+n22+…+nNN)/N
Etapa 5: Avaliação
• Exemplo 1: Detecção de falhas
• Variável dependente: Falha (Sim ou Não)
• Variáveis independentes:
• Viscosidade da tinta
• Temperatura da tinta
• Umidade do papel
• Velocidade da impressora
• Percentual de tinta
• Percentual de solvente
MD: Modelos de classificação ANÁLISE DISCRIMINANTE
• Exemplo 2: Previsão de Insolvência de Empresas
MD: Modelos de classificação ANÁLISE DISCRIMINANTE
Distribuição das
empresas insolventes
() e solventes () nos
conjuntos de treino e
de validação em
função das 3 variáveis
utilizadas (ROA, LC e
GA)
TOTAL DE EMPRESAS: 99 (60 SOLVENTES e 39 INSOLVENTES)
VALIDAÇÃO: 49 EMPRESAS
(32 SOLVENTES E 17 INSOLVENTES)
TREINO: 50 EMPRESAS
(32 SOLVENTES E 18 INSOLVENTES)
OBSERVAÇÃO
Este material refere-se às notas de aula do curso
MB-756 (Pesquisa Operacional Aplicada à
Produção) do Instituto Tecnológico de Aeronáutica
(ITA). Não substitui o livro texto, as referências
recomendadas e nem as aulas expositivas. Este
material não pode ser reproduzido sem autorização
prévia do autor. Quando autorizado, seu uso é
exclusivo para atividades de ensino e pesquisa em
instituições sem fins lucrativos.