Transcript

MB – 756

PESQUISA OPERACIONAL

APLICADA À PRODUÇÃO

Professor: Rodrigo A. Scarpel

[email protected]

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

Aplicação do processo de ECBD em Produção:

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

• Uso de técnicas multivariadas de visualização:

Mineração dos dados: Sumarização

• Exemplo 1: Análise de Correspondência (código.1)

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

Mineração dos dados: Sumarização

• Exemplo 2: Wordcloud (código.2)

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 1: Análise de Correspondência (código.5)

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.


Recommended