1

Investigação Operacional

• Metodologia científica para abordar problemas das ciências, gestão, economia e engenharia.

• As suas principais características são:– interdisciplinaridade.

– Manipular modelos matemáticos para apoiar a tomada de decisão.

– Utilizar o computador.

2

As 7 etapas do processo de modelação

1. Definir o problema2. Observar o sistema e recolher informação3. Formular um modelo matemático4. Validar o modelo.5. Escolher uma decisão com base no modelo6. Apresentar a análise7. Implementar e monitorar continuamente

3

As 7 etapas do processo de modelação

Definir o problema

Observar o sistema,recolher

informação

Formular um

modelo matemático

Validaro modelo

Escolher uma

decisão alternativa

Apresentar os

resultados

Implementare monitorar

continuamente

4

1. Definir o problema• Identificar:

– o agente de decisão (quem exerce controle)– os seus objectivos (e.g. minimizar custos)– as decisões alternativas com que são confrontados (i.e., as

variáveis controláveis)– os parâmetros que, não sendo controláveis, influenciam o

resultado das decisões (as variáveis incontroláveis).• Discutir:

– o tempo disponível para o estudo– o involvimento do agente de decisão (e organização) no estudo

5

2. Observar o sistema e recolher informação

• Estabelecer o diagnóstico inicial:– observar e analisar a forma como o sistema real opera:– recolher informação– conceber um sistema idealizado.

• Elaboração de um relatório que:– estrutura o conhecimento que se adquiriu do sistema– co-responsabiliza os elementos da organização

6

3. Formular um modelo matemático

• Objectivo: – Reproduzir as relações entre as componentes do

problema (objectivo, variáveis de decisão, variáveis incontroláveis, restrições).

• Passos essenciais:– Identificar a estrutura de relações causa-efeito.– Quantificar essas relações de forma determinística ou

probabilística.

7

3.1 Identificar as relações causa-efeito• Identificação de todas as relações entre variáveis,

controláveis ou não, e a medida (ou medidas) de utilidade.“A B” significa “A contribui para a definição de B”

• Identificação de variáveis auxiliares que agregam informação de diversas variáveis.

• Obriga a formular as primeiras hipóteses no sentido da simplificação do problema através da inclusão de apenas as relações relevantes.

3. Formular um modelo matemático

8

3.1 Identificar as relações causa-efeito

3. Formular um modelo matemático

9

3.2 Quantificar as relações causa-efeito

• Três abordagens distintas:

– método dedutivo– método de simulação– método de inferência estatística

3. Formular um modelo matemático

10

Método dedutivo (primeiro exemplo)

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

• A unidade de produção de uma empresa pretende fabricar os produtos A e B.

• Fabricar cada produto envolve quatro operações, com os seguintes tempos unitários de fabricação (em segundos)

• Operação: Produto A Produto BCorte de chapa 10 20Embutidura 15 5Soldadura 6 3Pintura 10 8

11

Método dedutivo (primeiro exemplo)

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

• As capacidade de produção das diferentes secções fabris são as seguintes:

• Os lucros unitários por peça produzida e vendida sãoEsc. 0.90 (Produto A) Esc. 1.20 (Produto B)

• Admitindo que o mercado absorve toda a produção, como maximizar o lucro total a operação?

Secção: Capacidadediária

Corte de chapa 30 000Embutidura 30 000Soldadura 20 000Pintura 40 000

12

Método dedutivo (primeiro exemplo)

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

13

Método dedutivo (segundo exemplo)

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

• Uma empresa pretende determinar qual a quantidade (Q) a produzir e a que preço (p) deve vender uma determinada peça de vestuário durante a estação de Inverno que se avizinha.

• Obtiveram-se estimativas para a procura (em função do preço de venda p) e custos unitário de produção (em função da quantidade produzida Q) - ver próximo slide.

• Se a produção exceder a procura, o valor em excesso fica reduzido a um preço de saldo.

• O objectivo da empresa é maximizar o lucro associado à operação.

14

Método dedutivo (segundo exemplo)

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

15

Método de simulação

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

• Quando não é possível explicitar as relações entre as componentes do modelo através do método dedutivo (seja de forma determinística ou probabilística).

• Quando as relações são de tal forma complexas que o melhor que analista consegue fazer é imitar o comportamento do sistema idealizado.

16

Método de simulação (exemplo)

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

• Uma empresa possui cinco linhas de produção em paralelo que funcionam sem interrupção.

• Uma equipa de manutenção repara avarias nas linhas de produção pela ordem em que ocorrem (FIFO). A equipa funciona 5 dias por semana, 3 turnos por dia.

• O tempo que decorre entre o início de funcionamento de uma linha e a avaria seguinte varia de forma imprevisível (ou aleatória). Da mesma forma, o tempo de reparação é varia de forma imprevisível. Ver gráficos seguintes.

• Que benefício advém de ter mais equipas de manutenção?

17

Método de simulação (exemplo)

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

18

Método de simulação

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

• Objectivos:– Reproduzir a sequência de acontecimentos pelos quais o sistema passa. – Recolher informação com base na qual se pode medir a eficiência do

sistema.

• Vantagens:– Possui enorme flexibilidade (“simula-se tudo o que se quiser”)

• Desvantagens:– Requer grande esforço computacional para estimar o valor esperado da

medida de utilidade face a apenas uma concretização das variáveis de decisão.

– A busca de melhores decisões é um processo difícil de sistematizar.

19

Método de inferência estatística

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

• Quando não é possível explicitar as relações entre as componentes do modelo através do método dedutivo (seja de forma determinística ou probabilística).

• Quando as relações são inúmeras e complexas mas é possível pela análise estatística de dados inferir aquelas que melhor reproduzem o comportamento do sistema sem demasiada complexidade.

20

Método de inferência estatística (exemplo)

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

• Em Janeiro, uma empresa importadora pretende prever o preço de determinada mercadoria agrícola durante todos os meses que se seguem até Junho.

• A produção dessa mercadoria concentra-se em larga escala num dado país que contribui contribui com 55% da produção mundial e 75% da exportação mundial.

• Em Janeiro de cada ano, o MA desse país publica previsões da oferta e da procura até ao final do ano agrícola (Outubro).

21

Método de inferência estatística (exemplo)

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

• Pretende-se construir um modelo descritivo que explique o preço da mercadoria nos vários meses até Junho para auxiliar o planeamento da aquisição do referido produto durante o período de Janeiro a Junho.

• Numerosos e complexos factores (variáveis controláveis e incontroláveis) contribuem para explicar o preço da mercadoria. Naturalmente uns são mais relevantes que outros.

• Deve o analista efectuar hipóteses sobre quais os factores que mais influenciam o preço da mercadoria.

22

Método de inferência estatística (exemplo)

3. Formular um modelo matemático 3.2 Quantificar as relações causa-efeito

23

4. Validar o modelo

• Validar o modelo significa averiguar se o impacto das decisões previsto pelo modelo corresponde ao impacto real das mesmas decisões.

24

4. Validar o modelo• Objectivo: detectar insuficiências que são apenas

detectáveis no contexto da definição global do modelo.• Métodos de validação (sem ser exaustivo):

– análise de sensibilidade– simulação.

• Nota: o modelo pode ser adequado ou inadequado conforme os valores das variáveis incontroláveis, estimados ou conhecidos no momento da decisão.

25

4. Validar o modelo

Análise de sensibilidade

• Averiguar como é que a alteração de valores das variáveis incontroláveis influencia a solução proposta pelo modelo.

• Averiguar como é que desvios à solução proposta pelo modelo influencia a utilidade (eficiência) do sistema representado.

26

4. Validar o modelo

Análise de sensibilidade

27

4. Validar o modelo

Recurso à simulação • Retomemos o exemplo da mercearia. Uma forma de

validar o modelo descritivo que se utilizou seria simular (pode-se simular quase tudo) a entrada de clientes, os seus tempos de espera e as desistências.

• Após diversas simulações, registar valores médios de: comprimento médio da fila, tempo de espera médio e percentagem de desistentes.

• Os valores obtidos devem ser muito semelhantes aos obtidos com o modelo.

28

5. Escolher uma decisão com base no modelo

• Determinar os valores das variáveis controláveis que, satisfazendo as restrições do modelo, conduzem ao valor máximo da medida de utilidade ou eficiência.

• Em geral há três formas de busca de soluções óptimas:– métodos analíticos– métodos de optimização– métodos heurísticos

29

5. Escolher uma decisão

Métodos analíticos• Métodos de Análise Infinitésimal

(diferenciação, procura de máximos e mínimos, extremos condicionados,etc.)

• Permitem obter uma representação explicita da solução.

• Leque de aplicações muito restrito.

30

5. Escolher uma decisão

Métodos analíticos (exemplo)

• Seja X uma variável aleatória de densidade f(x,), onde é um parâmetro desconhecido.

• Se x1, x2,..., xn forem realizações de X então a verosimelhança da amostra é uma função de definida por L() = f(x1, ) f(x2, )... f(xn, )

• A estimativa da máxima verosimelhança é o valor * que torna máximo o valor de L() ou, de modo equivalente, o valor máximo de log L() = log f(x1, ) + log f(x2, )+... + log f(xn, )

31

5. Escolher uma decisão

Métodos analíticos (exemplo)

• A condição necessária de optimalidade impõe

• Por exemplo, se X é uma variável aleatória com distribuição de Poisson de parâmetro então aquela condição é equivalente a

n

xx

n

n

ii

n

ii

11 ou 0

02

2

1

1 ),x(f),x(f

...),x(f),x(f

),x(f),x(f

n

n

32

5. Escolher uma decisão

Métodos de optimização• Processo sistemático de gerar aproximações

sucessivas para a solução.• Garantia de convergência ao fim de um número

finito ou infinito de passos.• Esforço computacional pode ser demasiado elevado. • Normalmente, convergência para a solução do

problema é assegurada apenas quando o modelo possui uma propriedade adicional - convexidade.

33

5. Escolher uma decisão

Métodos de optimização (exemplo)

• Seja f(x) uma função real unidimensional. Pretende-se o valor x que torna f(x)=0.

• O método de Newton-Raphson consiste no seguinte processo iterativo

a partir de um ponto inicial x0. • Sob hipóteses adicionais sobre f o método converge.

,...,,i,)x´(f)x(f

xxi

iii 2101

34

5. Escolher uma decisão

Métodos de optimização (exemplo)

Método de Newton-Raphson aplicado à determinação da maior raiz positiva de f(x)=x6-x-1

x0 =1 x0 =2 x0 =1.5x1 1.2 1.6806 1.300491x2 1.143576 1.43074 1.181480x3 1.134909 1.254971 1.139456x4 1.134724 1.161538 1.134778x5 1.134724138 1.136353 1.134724146x6 1.1347305 1.134724138x7 1.134724139x8 1.134724138

35

5. Escolher uma decisão

Métodos de optimização (exemplo)

• O método de Newton-Raphson impõe que f seja diferenciável.

• Quando f não é diferenciável deve utilizar-se o método da bissecção, entre outros.

• O facto de o método de Newton-Raphson usar informação da derivada de f faz com a sua convergência seja mais rápida.

36

5. Escolher uma decisão

Métodos heurísticos• São frequentes os problemas que não podem ser

resolvidos por métodos de optimização.• Os métodos heurísticos são também métodos

iterativos, mas que se baseiam em regras de “senso comum”.

• Em geral, não é possível garantir convergência para a solução do problema mas é possível encontrar uma boa solução rapidamente.

37

5. Escolher uma decisão

Métodos heurísticos (exemplo)

38

5. Escolher uma decisão

Análise crítica das soluções iniciais • As soluções propostas pelo modelo podem também servir de

instrumento para validação do modelo. • Esta análise deve ser conduzida com o agente de decisão.

Dificuldade: há que distinguir entre as críticas “genuínas” e a tendência natural de rejeição de soluções inovadoras.

• Deficiências que podem ser detectadas nesta fase:– deficiente definição de objectivos– falta de restrições– representação inadequada das relações entre componentes do

modelo.

39

6. Apresentar os resultados• Os elementos da organização a quem se destina a análise

devem ser envolvidos desde o início e não apenas nesta fase.

• A esses elementos deve ser facultado um atractivo e sistema de apoio à decisão e simples de manipular que lhes permita averiguar o comportamento do modelo em diversas circunstâncias (“what if ...”).

• Preferencialmente, o benefício da adopção do modelo deve ser demonstrado de forma prospectiva ou retrospectiva.

40

7. Implementar e monitorar continuamente

• Os elementos da organização que vão utilizar o modelo devem também ser envolvidos desde o início e não apenas nesta fase.

• O analista é responsável:– pela implementação do novo sistema até que este se torne

rotina.– pela monitorização do sistema de forma que o modelo

permaneça válido e eficaz ao longo do tempo.• Um caso de sucesso, mesmo que de pequena dimensão,

é chave para a análise de outros problemas.