0 - sandro.eng.br

Transcrição

0 - sandro.eng.br

Curso: Administração | Prof. Sandro da Silva Pinto
Disciplina: Simulação Empresarial | Slides
Lins, SP, fevereiro de 2015
1
Simulação Empresarial
Objetivo da Disciplina
-Desenvolver a habilidade de simular processos cotidianos na tomada de decisão;
Metodologia
1. Aula expositiva;
2. Exercícios em aula (individual ou em grupo);
3. Exercícios/trabalhos dirigidos (individual ou em grupo);
4. Leitura/Resenha de Obras Essenciais (individual);
5. Provas Individuais.
Avaliação
- 20% (Prova Global Unilins)
- 30% (Exercícios em aula + Exercícios/Trabalhos Dirigidos) - ATIVIDADES
- 50% Prova Individual – PROVA
-Bibliografia Básica (Biblioteca Unilins):
KRAJEWSKI, L; RITZMAN, L; MALHOTRA, M; Administração da Produção e Operaçòes. 8a. Edição.
Pearson-Prentice Hall. São Paulo, 2008.
SILVA, E. M et all. PESQUISA OPERACIONAL: PROGRAMACAO LINEAR: SIMULACAO
Editora.: ATLAS . SAO PAULO, 1998.
2
Programação das Aulas
Conteúdo Programático do Curso
1. Introdução
2. Formulação de Problemas e Análise Gráfica
3. Programação Linear
4. Método de Transporte - MODI
5. Método da Designação
6. Modelos Gerais – Teoria da Decisão
7. Teoria dos Jogos
8. Teoria das Filas
9. Simulação, Softwares e Aplicação
3
Planejamento das Aulas
M A I O / 2015
F E V E R E I R O / 2015
dom
seg
ter
qua
qui
sex
sáb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
dom
ter
qua
sáb
1
2
5
6
7
8
9
21ª. Aula | 22ª. Aula
10
11
12
13
14
15
16
17
18
19
20
21
22
23
25
26
27
28
29
30
J U N H O / 2015
dom
seg
ter
qua
qui
sex
sáb
1
2
3
4
5
6
Prova Global Unilins
7
8
9
10
11
12
13
14
15
16
17
18
19
20
22
23
24
25
26
27
seg
ter
qua
qui
sex
sáb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
A B R I L / 2015
ter
sex
4
M A R Ç O / 2015
seg
qui
3
dom
dom
seg
qua
qui
sex
sáb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
4
Capítulo 1: Introdução
1a. Aula
Objetivo: apresentar os conceitos sobre „decisão‟ e
processos decisórios.
Metodologia
1. Aula expositiva;
2. Exercícios em aula.
5
Capítulo 1: Introdução – 1a. Aula
Histórico sobre Decisão
6
7
8
9
10
11
Considerações sobre Processo
Decisório
“Percebemos que, particularmente, as
decisões do administrador não podem
ser avaliadas por meios científicos”
Herbert Simon
12
Decisório
“No processo decisório, sua própria
mente pode ser seu pior inimigo”
John Hammond, Ralph Keeney e Howard
Raiffa
13
Decisório
“Organizações perseguem inteligência. Nessa
perseguição, elas processam informação, formulam
planos e aspirações, interpretam ambientes, geram
estratégias e decisões, monitoram experiências e
recebem aprendizado dessas experiências e imitam
as outras organizações, na medida em que elas
fazem o mesmo”
James March
14
Decisório
Tomar decisões:
• é um processo racional, mas também emocional;
• é um processo social e relativo;
• é um processo de aprendizagem;
• não é um processo prescritivo, mas contingencial.
15
Decisório
“Uma decisão complexa é como um grande rio que
traz de seus afluentes as premissas incontáveis que
constituem ou formam um processo de decisão (...)
muitos indivíduos e unidades organizacionais
contribuem em qualquer decisão importante e a
questão da centralização ou descentralização é um
problema de arranjar este sistema complexo em um
esquema eficiente”
Herbert Simon
16
Modelos de Tomada de Decisões
Alguns autores, porém, propõem modelos de
tomada de decisões, transformando esse processo
em algo prescritivo, ou seja, uma “receita de bolo”,
que pode ser aplicada em toda e qualquer
situação, e em qualquer organização.
17
Modelo do Homem Economista
(Herbert Simon)
1. O homem economista trabalha com o mundo
real com toda sua confusão e complexidade.
2. Ele considera todas as alternativas possíveis,
sendo a grande maioria delas supérfluas ou de
pequena importância.
3. O homem economista adota um padrão ótimo
da realidade, selecionando a melhor alternativa
existente.
18
Modelo do Administrador
(Herbert Simon)
1. O Administrador trabalha com um modelo
drasticamente simplificado da realidade
2. Ele percebe que a maior parte dos fatos desse
mundo real não tem grande relevância à
situação particular que ele enfrenta e que o elo
de ligação entre a causa e o efeito deve ser
simples.
19
Modelo do Administrador
(Herbert Simon)
3. O Administrador adota um padrão satisfatório
do mundo formado por determinado número
de alternativas de escolha que atendem
satisfatoriamente a seu problema e contenta-se
em achar soluções satisfatórias ou adequadas.
20
Decisão nas Organizações
Herbert Simon
modelo de decisão homem
administrador
Existência de uma racionalidade limitada - modelo simplificado da realidade;
O modelo simplificado da realidade pode ser o modelo de empresa moderna (empresa de
grande porte, manipulando múltiplos produtos e operando sob incerteza, em um mercado
imperfeito).
Tomada
de
Decisão
quatro
conceitos
•quase resolução do
conflito;
•minimizar a incerteza;
•busca de solução em
torno de um objetivo
principal;
d) aprendizagem.
21
Fatores influentes na tomada de decisão:
1. Responsabilidade - perante leis e penalidades;
2. Especialização - baseada em conhecimentos teóricos e práticos de
especialistas;
3. Coordenação - para transmitir as ordens que devem ser cumpridas e
coordenar o processo de decisão;
4. Cacife - para cobrir eventuais fracassos em algumas frentes; e,
5.Tempo - pois o tempo curto pode minimizar a incerteza, mas pode
aumentar o risco de uma decisão apressada, enquanto o tempo longo
pode trazer novas perspectivas de decisão, mas aumenta o nível de
incerteza.
Em geral, a empresa ou decisor gostaria de fazer a seguinte pergunta
(denominada pergunta do tipo WHAT-IF?):
"o que aconteceria se a condição fosse...?"
22
Processo de Tomada de Decisão
Tipos de Pessoas que tomam decisões:
1. As que têm preferência pelo risco;
2. As que são neutras ao risco;
3. As que têm aversão ou evitam o risco.
Essa variação do comportamento resulta na
tomada de decisão conservadora, moderada ou
dinâmica, associada à perseguição de ganhos
baixos, médios ou elevados.
23
Conceitos a serem adotados:
1. Raciocínio limitado
2. Quase resolução do problema
3. Minimização da incerteza
24
Fatores que podem contribuir:
1.
2.
3.
4.
5.
Responsabilidade e transparência;
Conhecimento especializado;
Coordenação entre as partes;
Habilidade política;
Administração do tempo.
25
Modelo Genérico
1.
2.
3.
4.
5.
Defina o problema;
Identifique os critérios;
Pondere os critérios;
Gere alternativas;
Classifique cada alternativa segundo cada
critério;
6. Identifique a solução ótima.
26
Modelo das Decisões Inteligentes
(Hammond, Keeney e Raiffa)
1.
2.
3.
4.
5.
6.
7.
8.
Trabalhar com o problema certo;
Definir os objetivos;
Criar alternativas com imaginação;
Compreender as conseqüências;
Confrontar itens de negociação;
Esclarecer as incertezas;
Analisar a tolerância a riscos;
Examinar as decisões interligadas.
27
Restrições da Racionalidade
• O modelo racional é baseado num conjunto de
premissas que determinam como uam decisão
deve ser tomada, em vez de descrever como uma
decisão é tomada.
• Herbert Simon sugeriu que o julgamento individual
fica restringido pela sua racionalidade.
28
• Os indivíduos tentam tomar decisões racionais, mas
falta aos tomadores de decisões informações
importantes referentes à solução do problema, aos
critérios relevantes e assim por diante.
29
Problema 1
As seguintes 10 corporações foram classificadas
pela revista Fortune entre as 500 maiores
empresas sediadas nos EUA segundo as receitas de
vendas de 1999:
• Grupo A: Avis Rent a Car, TWA, Hershey Foods, Barnes
and Noble, Hasbro.
• Grupo B: SBC Communications, McKesson, Ingram
Micro, United Technologies, Utilicorp United.
30
Problema 2
O melhor aluno de uma classe de MBA escreve
poesia e é bastante tímido e de baixa estatura. Qual
foi a matéria principal do seu curso de graduação?
• A) estudos chineses
• B) psicologia
31
Problema 3
Uma nova pontocom fez recentemente sua oferta
pública inicial passando a ter ações negociadas em
bolsa. Na abertura, as ações foram vendidas a $20
cada uma. A concorrente mais próxima dessa empresa
tornou-se uma S/A há um ano, também ao preço de
$20/ação. Agora o estoque de ações dessa
concorrente está cotado em $100/ação. Quanto a
nova empresa valerá daqui a um ano?
32
Exercício 1 – 1o. Bimestre
1. Defina “Processo Decisório”. Utilize exemplos.
2. Quais são os modelos mais utilizados na tomada
de decisão? Explique-os.
33
Capítulo 1: Introdução
2a. Aula
Objetivo: apresentar os conceitos sobre „heurísticas‟
e vieses cognitivos.
Metodologia
1. Aula expositiva;
34
Heurísticas e Vieses Cognitivos
• Heurísticas são regras práticas desenvolvidas
pelos indivíduos para reduzir as exigências de
processamento de informações da tomada de
decisões.
• Viés Cognitivo é aplicação da heurística de
maneira inadequada ao tomar uma decisão.
35
• O problema 1 ilustra a heurística da
disponibilidade. O grupo A consiste em empresas
de consumo, enquanto o grupo B é formado de
empresas
menos
conhecidas
pelos
consumidores.
representatividade. Tendemos a associar as
características do indivíduo às disciplinas e não a
considerar a provável razão entre o número de
alunos que escolheram a estudos chineses e os
que escolheram psicologia na graduação.
36
ancoragem. A resposta da maioria das pessoas
é afetada pela informação irrelevante da
valorização da outra empresa. Como seria sua
resposta se o valor da concorrente fosse
$10/ação?
37
A Heurística da Disponibilidade
• Pessoas avaliam a freqüência, a probabilidade ou
as causas prováveis de um evento pelo grau com
que exemplos ou ocorrências desse evento
estiverem imediatamente “disponíveis” na
memória.
• Essa estratégia pode ser útil, uma vez que
eventos de maior freqüência geralmente se
revelam mais rapidamente na mente.
38
Heurística da Disponibilidade
• Entretanto, ela é falível, porque a
disponibilidade de informações também é
afetada por fatores que não estão relacionados
com a freqüência objetiva do evento julgado.
• Esses fatores irrelevantes podem influenciar a
proeminência perceptual imediata de um
evento, a vividez com que é revelado ou a
facilidade com que é imaginado.
39
Heurística da Representatividade
• Ao fazer um julgamento sobre um indivíduo (ou
objeto ou evento), as pessoas tendem a
procurar peculiaridades que ele possa ter que
correspondam a estereótipos formados
anteriormente.
• Em alguns casos, o uso da heurística é uma boa
primeira aproximação.
40
Heurística da Representatividade
• Em outros casos, ela leva a comportamentos
irracionais e moralmente repreensíveis – como
a discriminação.
• Os indivíduos tendem a confiar em tal
estratégia mesmo quando a informação é
insuficiente e quando existem melhores
informações com as quais se pode fazer um
julgamento preciso.
41
Heurística da Ancoragem
• Pessoas fazem avaliações partindo de um
valor inicial e ajustando-o até produzir uma
decisão final.
• O valor inicial ou “âncora”, pode ser sugerido
a partir de antecedentes históricos, pela
maneira como um problema é apresentado
ou por informações aleatórias.
42
Heurística da Ancoragem
• Independente da base do valor inicial, os
ajustes feitos a partir desse valor tendem a
ser insuficientes.
• Valores iniciais diferentes podem produzir
decisões diferentes para o mesmo
problema.
• Problema da Acoragem: Dez Quantidades
Incertas.
43
1. O que é Heurística? Explique as heurísticas da
disponibilidade, representatividade e ancoragem.
44
Capítulo 2: Formulação de Problemas e Análise Gráfica
3a. Aula
Objetivo: Iniciar os estudos sobre formulação de
problemas.
Metodologia
1. Aula expositiva;
45
Capítulo 2: Formulação de Problemas e Análise Gráfica – 3a. Aula
Programação Matemática e Problemas de
Gestão
“Para entender um problema, temos que tentar ao menos
algumas soluções mais óbvias, e descobrir que elas falham:
então, redescobrimos que existe uma dificuldade - um
problema
(Karl R. Popper).”
IMPEDE
PROBLEMA
DIFICULDADE
REALIZAÇÃO DE
UM DESEJO
CRIAR
SOLUÇÃO
CAPACIDADE
MODELOS
REPRESENTATIVOS
PROBLEMA
46
Tipos de Problemas
* Decidíveis
* Não Decidíveis
Tipos de Problemas Decidíveis:
** Decisão
** Localização
** Otimização
Conceito de Modelo
Os modelos são representações simplificadas da realidade
que preservam, para determinadas situações e enfoques, uma
equivalência adequada.
O Modelo Sistêmico
Sistemas são unidades conceituais ou físicas, compostas de
partes interrelacionadas, interatuantes e interdependentes.
47
Classificação
Modelos

 Físicos
Concretos 
Geométrico
s



 M atemáticos

 Abstratos  Lógicos


 Esquemáticos


Outras classificações existentes:
Icônicos
Descritivos
Físicos
Simbólicos
Procedimentais
Analógicos
48
48
A Dimensão da Complexidade
49
Modelagem
Definição do Problema
Formulação e Construção
do Modelo Inicial
Simulação do Modelo
Validação do Modelo
Reformulação do Modelo
Aplicação do Modelo
50
Teorias de Decisão
Teoria de Utilidade
Teoria de Probabilidade
Pesquisa Operacional
Elementos na Tomada de Decisão
Decisor
Objetivo
Escala de Valor
Soluções ou Estratégias
Estados da Natureza ou Ambiente
Resultados ou Conseqüências
Situações na Tomada de Decisão
Risco
Certeza
Conflito
51
Fluxo da Análise Quantitativa
Formulação do
problema
Construção do
Modelo
Formulação do
Execução
problemadas
Análises
Implementação e
Utilização
Hiatos de Tradução
52
Modelo de Otimização
Minimizar f ( x)
Sujeito  a :
hi ( x)  0, i  1,..., mh
g j ( x)  0 j  1,..., mg
x  n
f:n

g:n
h:n
53
Programação Matemática
Programação Linear
Programação Não-Linear
Programação Inteira
Vantagens:
Melhorias Mensuráveis
Automatização de Processos
Análises Operacionais
Identificação de Gargalos
Determinação de Valores
Projetos e Reengenharia
* Os modelos quantitativos não tomam as decisões, mas as
tornam muito mais claras e fáceis.
54
Pesquisa Operacional
Origens
Antes da Segunda Guerra:
- FREDERICK TAYLOR: formato e tamanho ótimo de uma pá para minas de carvão (1885).
- A. K. ERLANG: modelos matemáticos para determinação de tempo de espera (1917).
- THOMAS EDISON: rotas para serem seguidas pelos navios para enganar submarinos (Primeira
Guerra) inimigos.
- FREDERICK LANCHESTER: modelos matemáticos para estratégias militares (1916).
- HORACE LEVINSON: modelos para estudo de mercado (déc. de 30).
Durante a Segunda Guerra Mundial:
- Problemas de detecção de navios e submarinos pelo radar;
- Relação entre o peso de bombas e os sinistros;
- Ações aéreas anti-submarinas;
- Dimensionamento ótimo dos comboios;
- Lançamento aéreo de minas;
- Manobras de navios para evitar kamikazes;
- Precisão dos bombardeios;
Após a Segunda Guerra:
- Programação da produção;
- Controle de estoques;
- Programação de vendas;
- Problemas de Transportes;
- Manutenção e substituição de equipamentos;
- Estudos de mercado;
- Planejamento de atividades quaisquer;
- Investimentos;
55
Técnicas de Pesquisa Operacional
- Programação Linear propriamente dita.
- Problemas de Distribuição.
- Problemas de Transporte.
- Programação Inteira.
- Programação Dinâmica.
- Programação Quadrática, Geométrica.
- Problemas de Estoques.
- Teoria da Filas.
- Teoria dos Jogos.
- Teoria dos Grafos.
- Teoria da Decisão.
- Simulação.
- Processos Estocásticos.
- Confiabilidade.
- Seqüenciamento.
56
Exemplo de Aplicação:
Utilização Racional de Materiais
Suponhamos que se tenha, no intuito de obter 360 unidades da peça A e 1800
unidades da peça B, proposto as variantes de corte I a V (figura abaixo) do
laminado disponível 4x12.
57
É fácil constatar que, para cada uma destas variantes de corte de uma placa de
laminado, o número de peças e o volume de refugo (em unidades de área) se
darão pelo quadro:
VARIANTES DE CORTE
PEÇA
I
II
III
IV
V
"A"
4
3
1
0
2
"B"
0
4
9
12
7
REFUGO
12
5
3
0
2
Se x1, x2, x3, x4 e x5 (que correspondem ao número de variantes de corte)
denotarem o número de placas de laminado cortadas de acordo com as
variantes I, II, III, IV e V, respectivamente, as condições do problema fornecerão
as restrições:
4x1 + 3x2 + x3 + 2x5 = 360
4x2 + 9x3 + 12x4 + 7x5 = 1800
[1]
[2]
58
É lógico que xi será o número de chapas cortadas para cada alternativa, que
obedece a uma matriz de corte.
O melhor plano de corte é o que minimiza o refugo total que, de acordo com o
quadro das alternativas de corte, podemos montar a função objetivo:
Zmín = 12x1 + 5x2 + 3x3 + 2x5
[3]
Com as restrições [1], [2] e a função objetivo [3], podemos resolver o problema
usando o chamado método SIMPLEX. Usando o método Simplex, a solução deste
problema de programação linear é:
x1 = 0
x2 = 0
x3 = 0
x4 = 45
x5 = 180
Zmín
=
360
(solução)
59
Sites que oferecem serviço de cálculo do sistema simples:
1. Finite Mathematics Utility:
http://www.zweigmedia.com/RealWorld/simplex.html
2. MathsTools:
http://www.mathstools.com/section/main/Simplex_On_Line#.VOor7vnF-T8
3. PHPSimplex: http://www.phpsimplex.com/simplex/simplex.htm?l=pt
60
1.
2.
3.
4.
Quais são os elementos de uma tomada de decisão?
Defina o que é um “problema”.
O que é Pesquisa Operacional?
Quais técnicas são utilizadas?
61
Capítulo 2: Formulação de Problemas e Análise Gráfica
4a. Aula
Objetivo: Iniciar os estudos sobre a análise gráfica
na resolução de problemas.
Metodologia
1. Aula expositiva;
62
Formulação de Problemas
Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade
de P1 é de 100 u.m. e o lucro unitário de P2 é de 150 u.m. A
empresa necessita de 2 horas para fabricar uma unidade de P 1
e 3 horas para fabricar uma unidade de P2. O tempo mensal
disponível para essas atividades é de 120 horas. As demandas
esperadas para os dois produtos levaram a empresa a decidir
que os montantes produzidos de P1 e P2 não devem
ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês.
- Construa e Resolva o modelo do sistema de produção mensal
com o objetivo de maximizar o lucro da empresa.
63
Resolução:
Precisamos, primeiramente, determinar as variáveis de decisão:
x1: Quantidade a produzir de P1;
Vamos agora montar uma tabela que facilite a visualização do problema
em questão, separando-o em dimensões, nas colunas, e itens a serem
produzidos nas linhas. A última linha corresponderá ao que chamaremos,
por enquanto, de LIMITE.
Tabela 1: Dimensionamento da questão
Restrições
Função
Objetivo
Empresa
Demanda/mês
Horas/unid.
Lucro/Unidade
P1 (x1)
40
2
100
P2 (x2)
30
3
150
Limite
*
120
64
A tabela 1 separa dimensionalmente os valores informados até então no
exercício. Percebam que foram identificadas três dimensões: a demanda
por mês esperada de cada produto (P1 e P2); a quantidade de horas
para se fazer cada produto; e o lucro unitário auferido por unidade
produzida.
A última linha da tabela simboliza um certo LIMITE por dimensão
utilizada. Nem sempre uma dimensão terá limites, mas quando tiver,
deverá ser informado o valor respectivo.
Precisamos montar um sistema de equações em que necessariamente
apareçam uma função objetivo (maximizar ou minimizar algo) e as
restriçoes do problema em questão.
De acordo com a tabela 1, vamos equacionar o problema observando
então a função objetivo e as restrições impostas ao problema. A função
objetivo, no caso maximizar o lucro por unidade produzida, e a restrição
colocada em relação à quantidade de horas/unidade produzida, são
imediatas,ou seja:
65
Função Objetivo - Lucro: 100x1 + 150x2 
Restrição1:
2x1 + 3x2  120 (restrição da dimensão
horas/unidade)
Este símbolo simboliza que a função objetivo é de máximo.
Contudo, a outra restrição colocada (dimensão demada/mês) não possui
limites impostos na última linha. Deveremos neste caso considerar que se
as demandas esperadas são as mencionadas, portanto as restrições
serão: x1  40 e x2  30.
Restrição2:
Restrição3:
x1  40 (restrição da dimensão demada/mês).
x2  30 (restrição da dimensão demanda/mês).
E finalmente não podemos esquecer que não existem quantidades
negativas a serem produzidas. Desta forma, basta apenas
condicionarmos que x1  0 e x2  0.
66
Modelo Final:
Restrição1:
Restrição2:
Restrição3:
Restrição4:
Restrição5:
2x1 + 3x2  120 (restrição da dimensão horas/unidade).
x1
 40 (restrição da dimensão demada/mês).
x1
 0 (restrição de que não pode existir produção negativa).
x2  0 (restrição de que não pode existir produção negativa).
67
Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1
é de 106 u.m. e o lucro unitário de P2 é de 158 u.m. A empresa
necessita de 4 horas para fabricar uma unidade de P 1 e 6 horas para
fabricar uma unidade de P2. O tempo mensal disponível para essas
atividades é de 240 horas. As demandas esperadas para os dois
produtos levaram a empresa a decidir que os montantes produzidos
de P1 e P2 devem ultrapassar 40 unidades de P1 e 30 unidades de
P2 por mês.
- Construa o modelo do sistema de produção mensal.
68
Capítulo 3: Programação Linear
5a. Aula
Objetivo: apresentar a estrutura e conceitos sobre a
programação linear na resolução de problemas.
Metodologia
1. Aula expositiva;
69
Capítulo 3: Programação Linear – 5a. Aula
• Programação linear: uma técnica que é útil para alocar
recursos escassos entre demandas concorrentes.
• Função objetivo: uma expressão em modelos de
programação linear que determina matematicamente o
que está sendo maximizado (por exemplo, lucro ou valor
presente) ou minimizado (por exemplo, custo ou refugo).
• Variáveis de decisão: variáveis que representam escolhas
que o tomador de decisão pode controlar.
• Restrições: limitações que restringem as escolhas
admissíveis para as variáveis de decisão.
• Região viável: uma região que representa todas as
combinações admissíveis de variáveis de decisão em um
modelo de programação linear.
70
• Parâmetro: um valor que o tomador de decisão não
pode controlar e que não se altera quando a solução é
implementada.
• Certeza: palavra que é usada para descrever que um
fato é conhecido sem dúvidas.
• Linearidade: uma característica de modelos de
programação linear que implica proporcionalidade e
aditividade – não pode haver nenhum produto ou
potência de variáveis de decisão.
• Não-negatividade: suposição de que as variáveis de
decisão devem ser positivas ou zero.
71
Formulando um problema
• Passo 1. Defina as variáveis de decisão.
• Passo 2. Escreva por extenso a função objetivo.
• Passo 3. Escreva por extenso as restrições.
• Problema do mix de produtos: um problema de planejamento do tipo
de um período, cuja solução gera quantidades de produto ótimos (ou mix
de produtos) de um grupo de serviços ou produtos sujeito a restrições de
capacidade de recursos e de demanda de mercado.
72
Formulando um problema – Exemplo E.1
•
A Companhia Stratton fabrica dois tipos básicos de tubo de plástico.
Três recursos são cruciais para a fabricação de tubo: horas de extrusão,
horas de embalagem e um aditivo especial à matéria-prima de plástico.
•
Os dados seguintes representam a situação da próxima semana.
73
Formulando um problema com desigualdades
• Normalmente as restrições de recursos têm limites superiores ou
inferiores.
• por exemplo, para a Companhia Stratton, o tempo de extrusão total
não deve superar as 48 horas de capacidade disponível, por isso
usamos o sinal ≤.
• Valores negativos para as restrições x1 e x2 não fazem sentido, por isso
acrescentamos restrições de não-negatividade ao modelo:
x1 ≥ 0 e x2 ≥ 0 (restrições de não-negatividade)
• Outro problema poderia ter restrições de recursos requerendo restrições
>, >, = ou <.
74
Análise gráfica
• A maioria dos problemas de programação linear é resolvida com um
computador.
• Entretanto, podem-se obter percepções sobre o significado da saída
de computador, e de conceitos de programação linear em geral,
analisando-se um problema de duas variáveis simples graficamente.
• Método gráfico de programação linear: um tipo de análise gráfica que
envolve os cinco passos seguintes:
• representar graficamente as restrições
• identificar a região viável
• encontrar a solução visual
• representar uma linha de função objetivo
• encontrar a solução algébrica
75
Análise gráfica – Exemplo E.2
76
•
•
A região viável é a área no gráfico que contém as soluções que
satisfazem todas as restrições simultaneamente.
Para encontrar a região viável, primeiro localize os pontos factíveis
para cada restrição e, em seguida, a área que satisfaz todas as
restrições.
•
Geralmente, as três regras seguintes identificam os pontos
factíveis para uma dada restrição:
77
Análise gráfica: identificar a região viável
78
79
Análise gráfica: representando graficamente a reta da função objetivo
• Agora queremos encontrar uma solução que otimize a função objetivo.
• Ainda que todos os pontos na região viável representem soluções
possíveis, podemos limitar nossa busca aos pontos de quina.
• Ponto de quina: um ponto que se encontra na interseção de duas (ou
possivelmente mais) linhas de restrição nos limites da região viável.
• Pontos interiores à região viável não precisam ser considerados
porque pelo menos um ponto de quina é melhor que qualquer ponto
interior.
• A melhor abordagem é representar graficamente a função objetivo
no gráfico da região viável para alguns valores arbitrários de Z.
80
Programação linear : representar
graficamente a reta da função objetivo
81
81
Encontrar a solução algébrica
• Passo 1: Desenvolva uma equação com apenas uma incógnita.
• Comece multiplicando ambos os lados de uma equação por uma
constante de forma que o coeficiente para uma das duas
variáveis de decisão seja idêntico em ambas as equações.
• Depois, subtraia uma equação da outra e resolva a equação
resultante para sua única incógnita.
• Passo 2: Insira esse valor da variável de decisão em qualquer uma
das duas restrições originais e resolva a outra variável de decisão.
82
Variáveis de folga e excesso
•
•
•
Restrição associada: uma restrição que ajuda a formar o ponto de
quina ótimo; limita a capacidade de aperfeiçoar a função objetiva.
Folga: a quantidade pela qual o lado direito é menor que o lado
esquerdo.
•Para encontrar algebricamente a folga para uma restrição ≤,
somamos uma variável de folga à restrição e a transformamos
em uma igualdade.
Excesso: a quantidade pela qual o lado esquerdo supera o lado
direito.
•Para encontrar algebricamente a folga para uma restrição ≤,
somamos uma variável de folga à restrição e a transformamos
em uma igualdade.
83
Análise de sensibilidade
•
•
•
•
Sensibilidade do coeficiente: medida de quanto o coeficiente da
função objetivo de uma variável de decisão deve melhorar
(aumentar para maximização ou diminuir para minimização) antes
que a solução ótima se altere e a variável de decisão se torne
algum número positivo.
Limite de faixa de viabilidade: o intervalo ao longo do qual o
parâmetro do lado direito pode variar enquanto seu preço sombra
permanece válido.
Faixa de otimalidade: os limites inferiores e superiores ao longo dos
quais os valores ótimos de variáveis de decisão se tornam
inalterados.
Preço sombra: a melhoria marginal em Z (aumento para
maximização e redução para minimização) causada pelo
relaxamento da restrição em uma unidade.
84
Solução de computador
•
•
Programas de computador reduzem dramaticamente a quantidade
de tempo requerida para resolver problemas de programação linear.
•
Programas de uso específico podem ser desenvolvidos para
aplicações que devem ser repetidas freqüentemente.
•
Esses programas simplificam a entrada de dados e geram a
função objetivo e as restrições para o problema. Além disso,
podem preparar relatórios administrativos personalizados.
Método simplex: um procedimento algébrico iterativo para resolver
problemas de programação linear.
•
A maioria dos problemas reais de programação linear é
resolvida em computadores. O procedimento de solução em
códigos de computador é alguma forma do método simplex.
85
86
Solução de computador – Resultado do OM Explorer para a Companha Stratton
87
Aplicações da programação linear
•
•
•
•
•
•
Mix de produtos: encontra o melhor mix de produtos para
fabricação, dadas restrições de capacidade e demanda.
Carregamento: encontra as designações de remessa ótimas.
Controle de estoque: determina a linha de produtos ótima a se
manter em estoque em um armazém.
Seleção de fornecedores: encontra a combinação ótima de
fornecedores para minimizar a quantidade indesejada de estoques.
Plantas ou armazéns: determina a localização ótima de uma planta
ou armazém.
Redução de estoques: encontra o padrão de redução que minimiza
a quantidade de material de refugo.
88
Aplicações da programação linear
•
•
•
•
•
•
Produção: encontra o programa de produção de custo mínimo.
Provimento de pessoal: encontra os níveis de provimento de pessoal
ótimos.
Combinações: encontra as proporções ótimas de vários ingredientes
usados para fabricar produtos.
Turnos: determina a designação de custo mínimo de trabalhadores
para turnos.
Veículos: designa veículos para produtos ou clientes.
Itinerário: encontra o itinerário ótimo de um serviço ou produto por
meio de vários processos consecutivos.
89
Problema resolvido 1
•
•
•
•
•
•
As linhas aéreas O‟Connel estão considerando serviços aéreos a
partir de seu centro de operações em Cicely, Alasca, para Rome,
Wisconsin e Seattle.
Elas têm um terminal de embarque no Aeroporto de Cicely, que opera
12 horas por dia. Cada vôo requer 1 hora de tempo do terminal de
embarque.
Cada vôo para Rome consome 15 horas do tempo da tripulação e
espera-se que gere um lucro de $ 2.500.
Atender a Seattle usa 10 horas do tempo de tripulação por vôo e tem
como resultado um lucro de $ 2.000 por vôo.
O trabalho da tripulação é limitado a 150 horas por dia.
O mercado de atendimento a Rome é limitado a nove vôos por dia.
•
•
Use o método gráfico de programação linear para maximizar os
lucros.
Identifique restrições de folga e excesso, se houver.
90
91
92
Um vendedor de frutas pode transportar 800 caixas de
frutas para a sua região de vendas. Ele necessita
transportar 200 caixas de laranjas a 20 u. m. de lucro por
caixa, pelo menos 100 caixas de pêssegos a 10 u. m. de
lucro por caixa e no máximo 200 caixas de tangerinas a 30
u.m. de lucro por caixa. De que forma deverá ele carregar
o caminhão para obter o lucro máximo? Construa o
modelo do problema e resolva-o utilizando o método
gráfico.
93
Capítulo 3: Programação Linear
6a. Aula
Objetivo: exercício de fixação sobre a programação
linear na resolução de problemas. Aplicação da
Ferramenta
Solver
(Excel).
Laboratório
de
Informática.
Metodologia
1. Aula expositiva;
94
Ferramenta Solver (Excel)
Diversas ferramentas para solução de problemas de otimização, comerciais
ou acadêmicos, sejam eles lineares ou não, foram desenvolvidas.
Dentre as ferramentas acessíveis existe o ‘Solver’, que acompanha o
Microsoft Excel.
Definindo e Resolvendo um Problema
Inicialmente, devemos definir o problema na planilha do Excel. Vamos
resolver o seguinte problema :
95
Para definir o problema na planilha, devemos definir células para representar as variáveis de
decisão e uma célula para representar o valor da função objetivo. Além disso, as restrições
também devem ser definidas. Abra um novo arquivo no Microsoft Excel e siga os seguintes
passos:
As células A2 e B2 guardarão os valores das variáveis de decisão x1 e x2, respectivamente.
Vamos agora definir a função objetivo. As equações do Excel são sempre precedidas do
sinal de igualdade (=), que indica que nesta célula será efetuada uma conta. Preencha as
células da planilha conforme indicado a seguir:
Na célula B4 será calculado automaticamente o valor da função objetivo, a partir da função
fornecida. Qualquer alteração nos valores das células B1 ou B2 fará com que o valor da
função objetivo seja recalculado.
96
Serão definidas agora as restrições do problema: As células de restrição devem
ser preenchidas da seguinte forma:
97
Após preenchidas as células, a planilha deve estar igual à
apresentada abaixo.
98
Para otimizar a função objetivo, vamos utilizar a ferramenta Solver.
* Na guia Dados, no grupo Análises, clique em Solver.
* Na caixa "Definir célula de destino", selecione a célula da função objetivo (B4)
clicando sobre ela, ou simplesmente digiteB4.
* Logo abaixo, é requerido que se escolha entre três opções: Máx, para
maximizar a função objetivo, Mín, para minimizar a função objetivo, e Valor,
que faz com que a função objetivo tenha determinado valor. No nosso exemplo,
como queremos maximizar a função objetivo, escolheremos a opção Máx.
* Na caixa "Células variáveis", devem ser inseridas as células ajustáveis, que
contêm os valores das variáveis de decisão. Deve-se inserir um nome ou uma
referência para cada célula ajustável, separando as células não-adjacentes por
ponto-e-vírgula. As células ajustáveis devem estar relacionadas direta ou
indiretamente à célula que contém o valor da função objetivo.
Podem ser especificadas até 200 células ajustáveis. Para que o Solver proponha
automaticamente as células ajustáveis com base na célula de destino, clique em
Estimar.
99
100
Para resolver o problema, clique no botão "Resolver". Se tudo estiver correto, a
janela abaixo será apresentada. Nesta janela, podemos escolher entre manter a
solução encontrada pelo Solver ou restaurar os valores originais. Também
podemos selecionar relatórios, que contém informações sobre o processo de
solução do problema.
O processo de solução pode ser interrompido pressionando-se ESC. O
Microsoft Excel recalculará a planilha com os últimos valores encontrados para
as células ajustáveis.
101
Após preenchidas as células, a planilha deve estar igual à apresentada abaixo.
102
Exercícios em Aula - Exemplo
1. Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de
P1 é de 100 u.m. e o lucro unitário de P2 é de 150 u.m. A empresa
necessita de 2 horas para fabricar uma unidade de P 1 e 3 horas para
fabricar uma unidade de P2. O tempo mensal disponível para essas
atividades é de 120 horas. As demandas esperadas para os dois
produtos levaram a empresa a decidir que os montantes produzidos de
P1 e P2 não devem ultrapassar 40 unidades de P1 e 30 unidades de P2
por mês.
Construa o modelo do sistema de produção mensal com o objetivo de
maximizar o lucro da empresa e resolva-o utilizando o Solver do Excel..
103
Resolução:
Vamos agora montar uma tabela que facilite a visualização do problema em
questão, separando-o em dimensões, nas colunas, e itens a serem produzidos
nas linhas. A última linha corresponderá ao que chamaremos, por enquanto, de
LIMITE.
Tabela 2: Dimensionamento da questão
Restrições
Empresa
Função Objetivo
Demanda/mês
Horas/unid.
Lucro/Unidade
P1 (x1)
40
2
100
P2 (x2)
30
3
150
Limite
*
120
104
Modelo Final:
Restrição1:
2x1 + 3x2  120 (restrição da dimensão horas/unidade)
Restrição2:
x1
 40 (restrição da dimensão demada/mês).
Restrição3:
Restrição4:
x1
Restrição5:
105
106
106
Exercícios em Aula - Exemplo
2. Um empresa fabrica 2 modelos de cintos de couro. O modelo M1, de
melhor qualidade, requer o dobro do tempo de fabricação em relação
ao modelo M2. Se todos os cintos fossem do modelo M2, a empresa
poderia produzir 1.000 unidades por dia. A disponibilidade de couro
permite fabricar 800 cintos de ambos os modelos por dia. Os cintos
empregam fivelas diferentes, cuja disponibilidade diária é de 400 para
M1 e 700 para M2. Os lucros unitários são de $ 4,00 para M1 e $ 3,00
para M2. Qual o programa ótimo de produção que maximiza o lucro
total diário da empresa?
Construa o modelo do sistema descrito e resolva-o utilizando o Solver
do Excel.
107
Modelo Final:
Restrição1:x1 + x2  800 (restrição da dimensão disponibilidade de couro)
Restrição2:x1
 400 (restrição da dimensão disponibilidade de fivelas)
Restrição3:
x2  700 (restrição da dimensão disponibilidade de fivelas)
Restrição4:2x1 + 1x2  1000 (restrição da dimensão tempo de fabricação).
Restrição5:x1
Restrição6:
108
109
Uma rede de televisão local tem o seguinte problema: foi
descoberto que o programa “A” com 20 minutos de
música e 1 minuto de propaganda chama a atenção de
30.000 telespectadores, enquanto o programa “B”, com
10 minutos de música e 1 minuto de propaganda chama a
atenção de 10.000 telespectadores. No decorrer de uma
semana, o patrocinador insiste no uso de no mínimo, 5
minutos para sua propaganda e que não há verba para
mais de 80 minutos de música. Quantas vezes por semana
cada programa deve ser levado ao ar para obter o número
máximo de te/espectadores?
Construa o modelo do sistema e resolva-o algebricamente,
graficamente e utilizando o Solver (Excel).
110
Capítulo 4: Método de Transporte M.O.D.I.
7a. Aula
Objetivo: aplicação da programação linear na
resolução de problemas utilizando um método
conhecido por MODI (método de transporte).
Metodologia
1. Aula expositiva;
111
Capítulo 4: Método de Transporte M.O.D.I. – 7a. Aula
Método MODI – Otimização de rotas
Existem problemas de otimização modelados através da pesquisa
operacional em que o “programação linear” pode ser simplificada.
Tal simplificação necessita da estabilidade de alguns parâmetros, como
origens e destinos “casados”.
Uma rede de depósitos de material de construção tem 4 lojas que devem ser
abastecidas com 50 m3 (loja 1), 80 m3 (loja 2), 40 m3 (loja 3) e 100 m3 (loja 4) de
areia grossa. Essa areia pode ser carregada em 3 portos P1, P2 e P3, cujas
distâncias às lojas estão no quadro a seguir (em km):
L1
P1 30
P2 12
P3 8
L2
20
36
15
L3
24
30
25
L4
18
24
20
O caminhão pode transportar 10m 3 por viagem. Os portos têm areia para suprir
qualquer exatamente a demanda solicitada. Estabelecer um plano de transporte
que minimize a distância total percorrida entre os portos e as lojas e supra as
necessidades das lojas. Construa o modelo linear do problema.
112
Exemplo de aplicação:
x11: Número de viagens do Porto 1 (P1) à Loja 1 (L1);
Iremos trabalhar com doze variáveis de decisão
(x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33 e x34).
Loja 1
50
Porto 1
Loja 2
80
Porto 2
Porto 3
Loja 3
40
Loja 4
100
113
Cada distância acima, por exemplo, do Porto 1 à Loja 1 (P1-L1), que será representado aqui por x11,
tem um valor. Além disso, cada Loja possui uma capacidade máxima para recebimento de areia,
conforme mostrado no esquema acima, ou seja, Loja 1 (50 m3), Loja 2 (80 m3), Loja 3 (40 m3) e loja 4
(100 m3).
Conforme mostra o esquema, deveremos impor condições que não extrapolem a capacidade
de recebimento de cada Loja. Desta maneira, podemos visualizar que se impusermos a
condição de que o número de viagens do porto 1 à Loja 1 (x11) + o número de viagens do
Porto 2 à loja 1 (x21) + o número de viagens do Porto 3 à loja 1 (x31) deverá ser igual à
capacidade de recebimento da Loja 1 (50 m3), ou seja:
Restrição1: x11 + x21 + x31 = 50
Analogamente, para as distâncias entre o Porto 1, 2 e 3 até a Loja 2 teríamos:
Restrição2: x12 + x22 + x32 = 80
Analogamente, para as distâncias entre o Porto 1, 2 e 3 até a Loja 3 teríamos:
Restrição3: x13 + x23 + x33 = 40
Analogamente, para as distâncias entre o Porto 1, 2 e 3 até a Loja 4
teríamos:
Restrição4: x14 + x24 + x34 = 100
114
Por outro lado deveremos considerar as distâncias envolvidas entre cada porto e loja. Assim,
conforme já definido anteriormente pelas varáveis de decisão (x11, x12, x13, x14, x21, x22, x23, x24,
x31, x32, x33 e x34), podemos associar cada trajeto com sua distância e supor que cada trajeto
multiplicado pela distância respectiva à loja, somados no total, minimize a distância total
percorrida. Da tabela abaixo (retirada do próprio exercício) temos os valores das distâncias a
serem percorridas.
P1
P2
P3
L1
30
12
8
L2
20
36
15
L3
24
30
25
L4
18
24
20
Portanto, para a função objetivo teremos:
Distância: 30x11 + 20x12 + 24x13 + 18x14 + 12x21 + 36x22 + 30x23 + 24x24 + 8x31 + 15x32 + 25x33
+ 20x34 
Não podemos deixar de considerar que cada caminhão poderá transportar no máximo até 10
m3 por viagem. Desta maneira, cada variável de decisão deverá ser restrita no máximo até 10.
115
Restrição5: x11
Restrição6: x12
Restrição7: x13
Restrição8: x14
Restrição9: x21
Restrição10: x22
Restrição11: x23
Restrição12: x24
Restrição13: x31
Restrição14: x32
Restrição15: x33
Restrição16: x34
 10
 10
 10
 10
 10
 10
 10
 10
 10
 10
 10
 10
E finalmente não podemos esquecer que não existem quantidades negativas a serem
encontradas. Desta forma teremos:
Restrição17: x11  0
116
Método
Novas restrições – adaptação para a
resolução
Loja 1
50
100
Porto 1
Loja 2
80
90
80
Porto 2
Loja 3
40
Porto 3
Loja 4
100
Loja 1
Loja 2
Loja 3
Loja 4
Disponibilidades
Porto 1
100
Porto 2
Porto 3
Capacidades
50
30
20
24
18
12
36
30
24
8
15
25
20
80
40
90
80
100
117
Resolução
Loja 1
Loja 2
Porto 1
Loja 3
Loja 4
Disponibilidades
100 0
x
30
x
20
x
24
100
18
Porto 2
x
12
50
36
40
30
x
24
Porto 3
50
8
25
x
20
Capacidades
50 0
30
15
15
80
50 0
x
40
0
100
90
50 0
80 30 0
0
Solução Final:
Porto 1 – Loja 4 = 100
Custo Total = (100 x 18) + (50 x 36) + (40 x 30) (50 x 8) + (30 x 15) = 5650
118
Uma rede de supermercados possui 4 lojas que devem ser abastecidas com 50
(loja 1), 80 (loja 2), 40 (loja 3) e 100 (loja 4) botijões de gás, que são fornecidos
por 3 distribuidoras D1, D2 e D3, cujas distâncias às lojas estão no quadro a
seguir (em km):
D1
D2
D3
L1
30
12
8
L2
20
36
15
L3
24
30
25
L4
18
24
20
O caminhão pode transportar até 10 botijões por viagem. As distribuidoras têm as
seguintes quantidades de oferta: D1 = 80 botijões, D2 = 90 botijões e D3 = 100
botijões.
Estabelecer um plano de transporte que minimize a distância total percorrida
entre os supermercados e as distribuidoras e supra as necessidades das lojas.
Quantas viagens de caminhões serão necessárias?
119
Capítulo 5: Método da Designação
8a. Aula
Objetivo: aplicação da programação linear na
resolução de problemas utilizando o método
conhecido por designação.
Metodologia
1. Aula expositiva;
120
Capítulo 5: Método da Designação – 8a. Aula
O Problema de designação
• Suponha ‘n’ trabalhadores a distribuir por ‘n’ tarefas de forma a que
cada trabalhador execute apenas uma tarefa, e que cada tarefa seja
executada apenas por um trabalhador.
• Conhecendo os custos da realização de cada tarefa por cada
trabalhador, o problema central consiste em designar os
trabalhadores às tarefas de forma a minimizar os custos!
• O problema de designação é um problema de dimensão (n x n).
121
Número de Possíveis Soluções
• O Problema de designação envolve a determinação de n! possíveis
soluções.
• Exemplo:
 para um problema com 5 trabalhadores e 5 tarefas o número
de soluções possíveis é igual a 5 ! = 120.
 para um problema com 10 trabalhadores e 10 tarefas o número
de soluções é igual a 10 ! = 3 628 800.
•Obter a solução ótima por tentativa é DIFÍCIL !
122
Problema de designação
Formulação
Destino
1
Origem
1
2
c11
x11
Procura
c12
x12
c22
c21
x21
.
.
.
n
2
x22
.
.
.
…
…
…
n
x1n
xn2
1
1
…
xnn
…
1
1
1
.
.
.
.
.
.
cm2
n2
xn1
c2n
x2n
.
.
.
cm1
n1
c1n
Oferta
cmn
nn
1
123
Problema de designação
Formulação
C
Minimizar
n
c x
i , j 1
ij ij
sujeito a:
n
x
ij
 1 , i  1,2,..., n
x
ij
 1 , j  1,2,..., n
j 1
n
i 1
xij  0,1 , i  1,2,..., n , j  1,2,..., n
124
Resolução do Problema de Designação
Método Húngaro
• Este método consiste em adicionar ou subtrair valores de forma
adequada às linhas e às colunas da matriz de custos de dimensão
‘nn’ para obter um problema equivalente com ‘n’ zeros
enquadrados na matriz de custos;
• Uma vez transformada a matriz de custos numa matriz com ‘n’
zeros enquadrados, esses zeros correspondem à designação ótima,
tomando:
xij = 1, para os zeros enquadrados da matriz de custos
transformada;
xij = 0, para os restantes valores;
125
Resolução do problema de designação
Método Húngaro - Exemplo
• Considere que existem 5 trabalhadores que devem ser designados a
5 tarefas. A matriz dos custos associados à realização de cada tarefa
por cada trabalhador é a seguinte:
1
2
3
1
17.5
15
9
2
16
16.5
3
12
15.5
4
4.5
5
13
4
5
5.5
12
10.5
5
10.5
14.5
11
5.5
8
14
17.5
13
9.5
8.5
12
17.5
126
126
Resolução do problema de Designação
Método Húngaro
• Início: Redução da Matriz de Custos.
• 1º. Subtrair aos elementos de cada coluna da matriz de custos o mínimo dessa
coluna.
• 2º. Na matriz resultante, subtrair a cada linha o respectivo mínimo.
• Iteração:
• 1º. Desenhar o número mínimo de traços que cobrem todos os
•
zeros da matriz;
• 2º. Critério de parada:
o número mínimo de traços é igual a n?.
• Sim – enquadrar n zeros, um por linha e um por coluna,
a solução é ótima. FIM.
• Não – passar a 3.
• 3º. Redução da matriz de custos.
• Determinar o menor valor não riscado .
• Subtrair  a todos os elementos não riscados e somar  a todos os
elementos duplamente riscados.
• Considerar de novo todos os zeros livres e voltar a 1 (Iteração)
127
127
Método Húngaro. Exemplo.
Início: Redução da Matriz de Custos.
1º: Subtrair o menor
elemento de cada coluna
de todos os elementos
dessa coluna
menor elemento da coluna 1
1
2
3
4
5
1
17.5
15
9
5.5
12
2
16
16.5
10.5
5
10.5
3
12
15.5
14.5
11
5.5
4
4.5
8
14
17.5
13
5
13
9.5
8.5
12
17.5
3
4
5
17.5 - 4.5 = 13
16 - 4.5 = 11.5
12 - 4.5 = 7.5
4.5 - 4.5 = 0
13 - 4.5 = 8.5
1
2
1
2
13
7
0.5
0.5
6.5
11.5
8.5
2
0
5
3
7.5
7.5
6
6
0
4
0
0
5.5
12.5
7.5
5
8.5
1.5
0
7
12
128
Início: Redução da Matriz de Custos.
2º: Subtrair o menor
elemento de cada linha de
todos os elementos dessa
linha
Existe empate na escolha do
menor elemento da linha 1 (igual a
0.5).
Nas linhas restantes o mínimo é
zero, sendo que as linhas
restantes não vão ser alteradas
13 - 0.5 = 12.5
7 - 0.5 = 6.5
0.5 - 0.5 = 0
6.5 - 0.5 = 6
1
2
3
4
5
1
13
7
0.5
0.5
6.5
2
11.5
8.5
2
0
5
3
7.5
7.5
6
6
0
4
0
0
5.5
12.5
7.5
5
8.5
1.5
0
7
12
1
2
3
4
5
1
12.5
6.5
0
0
6
2
11.5
8.5
2
0
5
3
7.5
7.5
6
6
0
4
0
0
5.5
12.5
7.5
5
8.5
1.5
0
7
12
129 129
Iteração: Critério de parada.
1º. Desenhar o número mínimo de traços que cobrem todos os
zeros da matriz.
1
2
3
4
5
1
12.5
6.5
0
0
6
2
11.5
8.5
2
0
5
3
7.5
7.5
6
6
0
4
0
0
5.5
12.5
7.5
5
8.5
1.5
0
7
12
2º. Critério de parada: o número mínimo de traços é igual a
5 (matriz ‘n x n’)? Se positivo o problema está resolvido. No
caso acima temos 4 traços e portanto um refinamento é
necessário.
130
Iteração: Redução da Matriz de Custos.
1º. min {elementos da submatriz dos
elementos não riscados } = 1.5
2º. Subtrair 1.5 a todos os elementos
não riscados.
3º. Somar 1.5 aos elementos na
intersecção dos traços.
4º. Os restantes elementos não são
alterados.
1
2
3
4
5
1
12.5
6.5
0
0
6
2
11.5
8.5
2
0
5
3
7.5
7.5
6
6
0
4
0
0
5.5
12.5
7.5
5
8.5
1.5
0
7
12
1
2
3
4
5
1
11
5
0
0
4.5
2
10
7
2
0
3.5
3
7.5
7.5
7.5
7.5
0
4
0
0
7
14
7.5
5
7
0
0
7
10.5
131
Iteração: Critério de parada.
1º. Desenhar o número mínimo de traços que cobrem todos
os
zeros da matriz.
1
2
3
4
5
1
11
5
0
0
4.5
2
10
7
2
0
3.5
3
7.5
7.5
7.5
7.5
0
4
0
0
7
14
7.5
5
7
0
0
7
10.5
2º. Critério de parada: o número mínimo de traços é igual
a 5?.
Sim – enquadrar 5 zeros, um por linha e um por coluna,
a solução é ótima. FIM
132
Método Húngaro. Exemplo
Solução Ótima.
Matriz inicial
de custos
1
2
3
1
17.5
15
9
2
16
16.5
3
12
15.5
4
4.5
5
13
4
5
5.5
12
10.5
5
10.5
14.5
11
5.5
8
14
17.5
13
9.5
8.5
12
17.5
solução ótima é : x13 = 9 , x24 = 5, x35 = 5,5, x41 = 4,5 , x52 = 9,5
com um custo total : 9 + 5 + 5.5 + 4.5 + 9.5 = 33.5
133
Quatro locais L1, L2, L3 e L4 necessitam de um equipamento, cada um.
Existem quatro equipamentos disponíveis (idênticos), D1, D2, D3 e D4. A
quilometragem entre os locais necessitados e os depósitos encontram-se
abaixo:
Determine a melhor alocação que envolva uma expedição de quilometragem
mínima.
Locais
Depósitos
L1
L2
L3
L4
D1
1B0
155
153
150
D2
152
15C
155
154
D3
155
154
15B
151
D4
151
156
152
15A
Orientação: aonde aparecer as letras A, B e C substitua respectivamente pelo
último, penúltimo e antepenúltimo algarismo do número de sua matrícula.
134
9a. Aula e 10a. Aula
Exercícios
Objetivo: Exercícios em Aula.
- Programação Linear, MODI e Designação.
Metodologia
1. Aula expositiva;
135
Semana de Prova – 11a. Aula e 12a. Aula
Revisão para Prova
136
Prova 1
137
Correção da Prova
Entrega de Notas
138
Capítulo 6: Modelos Gerais – Teoria da Decisão
17a. Aula
Objetivo: Apresentar os conceitos e estrutura de
vários modelos de tomada de decisão.
Metodologia
1. Aula expositiva;
139
Capítulo 6: Modelos Gerais – Teoria da Decisão – 17a. Aula
Análise do ponto de equilíbrio
• A análise do ponto de equilíbrio é usada para comparar
processos, encontrando o volume no qual dois processos
diferentes têm custos totais iguais.
• O ponto de equilíbrio é o volume no qual a receita total é
igual ao custo total.
• Custos variáveis (c) são custos que variam diretamente
com o volume do produto.
• Custos fixos (F) são aqueles custos que permanecem
constantes com as mudanças no nível de produto.
140
• “Q” é o volume de clientes ou unidades, “c” é o custo
variável unitário, F são os custos fixos e p é a renda por
unidade
• cQ é o custo variável total.
• Custo total = F + cQ
• Receita total = pQ
• O equilíbrio ocorre onde pQ = F + cQ
• (Receita total = Custo total)
141
A análise do ponto de equilíbrio pode mostrar…
• Se o volume de vendas previsto é suficiente para chegar
a um equilíbrio (não auferir lucro nem sofrer prejuízo)
• Quão baixo deve ser o custo por unidade para atingir o
equilíbrio dados os preços atuais e as vendas previstas.
• Quão baixo deve ser o custo fixo para atingir o equilíbrio.
• Como os níveis de preços afetam o volume do ponto de
equilíbrio?
142
Exemplo do hospital – Exemplo A.1
Um hospital está avaliando a possibilidade de oferecer
um novo procedimento ao custo de 200 dólares por
paciente. O custo fixo por ano seria de $100.000, com o
total de custos variáveis de $100 por paciente.
143
Dois processos e decisão: fazer ou comprar?
• A análise do ponto de equilíbrio pode ser usada para
escolher entre dois processos ou entre um processo
interno e a compra desses serviços ou matérias-primas.
• A solução é o ponto no qual os custos totais para duas
alternativas são iguais.
• O volume previsto é então aplicado para se verificar qual
alternativa tem o menor custo para aquele volume.
144
144
Dois processos e decisão: fazer ou comprar?
145
Matriz de preferências
•A matriz de preferências é uma tabela que permite ao gerente
classificar uma alternativa de acordo com vários critérios de
desempenho;
•Os critérios podem receber pontos em qualquer escala contanto que
a mesma escala seja aplicada a todas as alternativas que estão sendo
comparadas.
•Cada pontuação é pesada de acordo com sua importância percebida
e o total desses pesos normalmente é igual a 100.
•A pontuação total é a soma das pontuações ponderadas (peso x
pontos) para todos os critérios. O gerente pode comparar os graus
das alternativas entre si ou com um limite predeterminado.
146
147
148
1. Para o cálculo do ponto de equilíbrio entre dois processos de atendimento num
hospital obteve-se o gráfico abaixo:
a.
b.
c.
d.
e.
Qual é o ponto de equilíbrio?
Até que quantidade o processo 1 é mais vantajoso? Por quê?
A partir de qual quantidade o processo 2 é melhor? Por quê?
Na situação acima (demanda esperada de 25000) você manteria os dois processos?
Justifique.
Se o custo fixo do processo 1 fosse 10% maior, o que aconteceria com o ponto de
equilíbrio ?
149
18a. Aula
vários modelos de tomada de decisão. Apresentar a
Teoria da Utilidade
Metodologia
1. Aula expositiva;
150
Teoria da Utilidade
• A Teoria da Utilidade permite através de preceitos simples quantificar
o quanto é desejável (ou indesejável) uma determinada situação que
envolva valores que não são medidos por um único atributo;
• A teoria da utilidade ajuda a modelar as preferências de um tomador
de decisão, com base na sua propensão ou atitude em relação ao
risco.
• A função utilidade descreve a sua atitude para o risco.
•A função utilidade trata da propensão do tomador de decisão e não
de sua sistemática, seus métodos e suas práticas finais que podem
ser por ele dirigidas com base no autoconhecimento.
151
Teoria da Utilidade
DESEJOS ILIMITADOS E RECURSOS ESCASSOS
Recursos são todas as coisas existentes, desejos são todas as coisas
desejadas e bens são as coisas desejadas existentes.
Devemos atentar para que nem todos os nossos desejos podem ser
atendidos. Os desejos são ilimitados e os recursos que possuímos são
limitados ou escassos.
Esta escassez nos obriga a tomar decisão selecionando alternativas a
partir de oportunidades possíveis
152
Teoria da Utilidade
ALTERNATIVAS
Diferentes bens e serviços proporcionam uma utilidade ou satisfação
aos indivíduos ou consumidores e que são capazes de escolher o mais
benéfico em seu ponto de vista.
Dois critérios são estabelecidos para o processo decisório:
1) Acaso - (hábito e intuição), que existe, normalmente, quando o consumidor escolhe
coisas de pouca importância. O erro não traz grandes conseqüências para si ou para a
família;
2) Racional - é quando o comportamento segue um conjunto sistemático e consistente de
preferência. É preciso garantir que o consumidor conheça todas as alternativas disponíveis
e seja capaz de avaliar perfeitamente as conseqüências da escolha.
153
Teoria da Utilidade
TEORIA DA UTILIDADE COMO FORMA RACIONAL DE EXPLICAR AS
DECISÕES INDIVIDUAIS
A – Utilidade cardinal - consiste em estabelecer um sentido mensurável ao
consumo, ou seja, seria possível medir quantitativamente a utilidade de um bem em
relação há um outro;
B – Utilidade marginal decrescente – verifica a utilidade da última unidade
consumida de um bem, contribuindo para a utilidade total. A utilidade marginal
decresce ao aumentar a quantidade consumida;
C – Utilidade marginal ponderada – As pessoas vão utilizar a última unidade
monetária num bem ou serviço que aumente a sua utilidade;
D – Utilidade ordinal – Exige que o consumidor seja capaz de ordenar as
combinações de bens segundo uma ordem de preferências, isto é, que possua uma
hierarquização consistente, incluindo a possibilidade de declarar-se indiferente
diante de uma alternativa. São as chamadas cesta de consumo.
154
Teoria da Utilidade
Quando um problema de decisão leva em consideração mais de um objetivo, é
preciso transformar os valores de cada um desses objetivos numa mesma unidade
de medida.
Tal unidade de medida será chamada de valor utilidade, com níveis de 0 a 1.
Por exemplo, para a escolha de um imóvel, conforme tabela abaixo, ocorrem três
alternativas de compra baseadas em três objetivos distintos.
Critérios
A1
A2
A3
Ganho Líquido
R$ 470 mil
R$ 500 mil
R$ 420 mil
Distância ao centro comercial
150 m
250 m
500m
Área disponível
600 m2
400 m2
1500 m2
155
Teoria da Utilidade
Para resolver este tipo de problema precisamos criar utilidades que variam entre „0 e 1‟ para
cada critério. Para o critério Ganho Líquido temos que:
Critérios - Ganho Líquido
A1
A2
A3
Valores
R$ 470 mil R$ 500 mil R$ 420 mil
Utilidade
------
1
0
A „utilidade 0‟ é para o valor que menos interessa de ganho líquido e a „utilidade 1‟ é para o
maior ganho. Precisamos calcular qual seria a utilidade para o valor intermediário (entre o
maior e menor ganho):
1
1
X
Triângulo
menor
x
0
400
420
440
460
480
420
500
500
0
470
0
420
Regra de 3 simples:
X
(470-420)
---- = -------------1
(500-420)
x = 0,63
156
Teoria da Utilidade
Para o critério Distância ao Centro Comercial temos que:
Critérios – Distância Centro comercial
A1
A2
A3
Valores
150 m
250 m
500m
Utilidade
1
------
0
A „utilidade 0‟ é para o valor que menos interessa de distância (maior distância) e a
„utilidade 1‟ é para a menor. Precisamos calcular qual seria a utilidade para o valor
intermediário :
1
X
1
0
Triângulo
menor
250
500
0
150
500
0
150
250
350
450
550
Regra de 3 simples:
X
(500-250)
---- = -------------1
(500-150)
x = 0,71
157
Teoria da Utilidade
Para o critério Área Disponível temos que:
Critérios – Área Disponível
A1
A2
A3
Valores
600 m2
400 m2
1500 m2
Utilidade
------
0
1
A „utilidade 0‟ é para o valor que menos interessa de área disponível e a „utilidade
1‟ é para a maior área. Precisamos calcular qual seria a utilidade para o valor
intermediário (entre a maior e menor área):
1
1
X
Triângulo
menor
x
0
300
300
600
900
1200
600
0
0
300
1500 Regra de 3 simples:
X
(600-300)
---- = -------------1
(1500-300)
1500
x = 0,25
158
Teoria da Utilidade
Enfim podemos montar a matriz de decisão final, com os valores utilidades no lugar
dos antigos valores dos critérios relacionados.
Critérios
Peso
Peso
Relativo
A1
A2
A3
Ganho Líquido
3
0,50
0,63
1
0
Distância ao centro
comercial
2
0,33
1
0,71
0
Área disponível
1
0,17
0,25
0
1
Total
6
1,0
0,69
0,73
0,17
Nesta matriz final acrescenta-se um „Peso‟ que pondera a importância de cada
critério (conforme escolha de decisão pela pessoa). Calcula-se na sequência um
peso relativo, que é a porcentagem de cada peso pelo total deles.
O valor final calculado é uma soma ponderada de cada peso relativo com a nota
utilidade auferida a cada critério. O maior valor será a resposta. No caso acima
(0,73).
Exemplo: A1: (0,50x0,63) + (0,33x1) + (0,17x0,25) = 0,69
159
1. Haroldo está analisando três ofertas de emprego. Como cada
emprego possui vantagens e desvantagens, Haroldo gostaria de
efetuar a escolha do melhor emprego utilizando um método de
decisão. As condições consideradas são. Determine a melhor
decisão.
Condições/
Emprego
Salário Mensal
Localização
Contrato
Decisão I
Decisão II
Decisão III
Decisão IV
R$ 2.000,00
R$ 1.800,00
R$ 2.500,00
R$ 2.200,00
50 km
10 km
30 km
40 km
10 anos
5 anos
3 anos
4 anos
160
19a. Aula
vários modelos de tomada de decisão. Teoria do
Valor Esperado.
Metodologia
1. Aula expositiva;
161
Teoria do Valor Esperado
Em alguns problemas de decisão as alternativas ou estados que compõem um
cenário ocorrem com certo nível de possibilidade ou probabilidade, sendo assim
denominado „risco‟.
Por exemplo, numa decisão sobre investimentos em poupança, dólar ou fundos
em que há a possibilidade de se ter 3 cenários (recessão, estabilidade ou
expansão), a melhor decisão será por expectativa média do chamado Valor
Esperado:
E (x) = Retorno Médio
Retornos Associados à decisão
Cenários Possíveis
Probabilidades
A1 –
Inv. Poup
A2 –
Inv. Dólar
A3 –
Inv.
Fundos
Ganho Líquido
40%
R$ 300
R$ 400
R$ -100
comercial
40%
R$ 300
R$ 300
R$ 200
Área disponível
20%
R$ 300
R$ 200
R$ 700
162
Teoria do Valor Esperado
O cálculo é bastante simples. Basta ponderar as probabilidades de ocorrência de
cada cenário por cada estratégia prevista (A1, A2, A3).
A melhor
escolha
Exemplo:
calculada
E (x) = Retorno Médio
A1: (0,4x300)+(0,4x300)+(0,2x300) = 300
A2: (0,4x400)+(0,4x300)+(0,2x200) = 320
A3: (0,4x -100)+(0,4x200)+(0,2x700) = 180
Retornos Associados à decisão
Cenários Possíveis
Probabilidades
A1 –
Inv. Poup
A2 –
Inv. Dólar
A3 – Inv.
Fundos
Ganho Líquido
40%
R$ 300
R$ 400
R$ -100
comercial
40%
R$ 300
R$ 300
R$ 200
Área disponível
20%
R$ 300
R$ 200
R$ 700
300
320
180
163
1. Uma empresa deseja criar um método de escolha para investimentos em função
dos cenários econômicos existentes (recessão, estabilidade e expansão). Para
tanto resolveu analisar, baseando-se num especialista de mercado, os retornos
associados às seguintes estratégias: A1: investir em Poupança; A2: investir em
Dólar; A3: investir em Fundos de Investimento. A matriz abaixo apresenta o
resumo da análise do especialista. Determine a melhor decisão.
Estados
Possíveis da
Economia
Recessão
Estabilidade
Expansão
Estratégia
A1
Estratégia
A2
Estratégia A3
Possibilidades
a priori
Investir em
poupança
Investir em
dólar
0,30
0,20
0,50
R$ 300,00
R$ 300,00
R$ 300,00
R$ 800,00
R$ 500,00
R$ 350,00
Investir em
fundos de
investimento
- R$ 100,00
R$ 500,00
R$ 900,00
Estratégia A4
Investir em
títulos da
União
R$ 450,00
R$ 550,00
R$ 650,00
164
20a. Aula
Objetivo: Exercícios em Aula. Teoria da Utilidade e
Valor Esperado.
Metodologia
1. Aula expositiva;
165
Capítulo 7: Teoria dos Jogos
21a. Aula
Objetivo: Apresentar os conceitos da Teoria dos
Jogos.
Metodologia
1. Aula expositiva;
166
Capítulo 7: Teoria dos Jogos – 21a. Aula
Teoria dos Jogos
• A teoria da decisão é uma abordagem geral da tomada de
decisões quando os resultados vinculados às alternativas muitas
vezes são duvidosos.
• Um gerente toma decisões usando o processo seguinte:
1. Faz uma relação das alternativas viáveis.
2. Faz uma relação dos eventos (estados da natureza).
3. Calcula o payoff para cada alternativa em cada evento.
4. Faz uma estimativa da probabilidade de cada evento (as
probabilidades totais devem perfazer 1).
5. Seleciona a regra de decisão para avaliar as alternativas.
167
Teoria dos Jogos
Regras de decisão
•
Tomada de decisão com incerteza ocorre quando se é incapaz de
estimar as probabilidades dos eventos.
•
Maximin: a melhor entre as piores. Uma abordagem
pessimista.
•
Maximax: a melhor entre as melhores. Uma abordagem
otimista.
•
Arrependimento minimax: minimizar o arrependimento
(também pessimista).
•
Laplace: a alternativa com o melhor payoff ponderado
usando probabilidades supostas,
•
Tomada de decisão com risco ocorre quando se é capaz de estimar
as probabilidades dos eventos.
•
Valor esperado: a alternativa com o maior payoff ponderado
usando probabilidades previstas.
168
Teoria dos Jogos
Um jogo representa uma situação de competição ou conflito entre
dois ou mais oponentes. Estes oponentes são usualmente
chamados de jogadores (um jogador pode ser um time composto
de mais de uma pessoa, como num jogo de cartas de duplas buraco por exemplo - onde apesar de haver quatro pessoas, há
apenas dois jogadores). Alguns exemplos de jogos são:
• jogos de salão, como cara-e-coroa, jogo da velha, damas ou xadrez;
• competição econômica;
• conflitos militares ou guerras.
169
Teoria dos Jogos
Cada jogador tem um certo número de escolhas, finito ou infinito,
chamadas de estratégias. Um jogador supostamente escolhe sua
estratégia sem qualquer conhecimento prévio da estratégia escolhida
pelos outros jogadores. A partir das escolhas dos jogadores, o jogo
fornece o resultado, ou saída, definindo quanto cada jogador ganhou
ou perdeu. Cada jogador faz sua escolha de modo a otimizar o
resultado. Os jogos são categorizados da seguinte maneira:
1. Tipos de saída
a) Determinada - as saídas são precisamente definidas, dadas as
estratégias tomadas.
b) Probabilística - as probabilidades das diferentes saídas são
conhecidas, dadas as estratégias tomadas.
c) Indeterminada - as saídas possíveis são conhecidas dadas as
estratégias tomadas, mas não suas probabilidades.
170
Teoria dos Jogos
2. Número de jogadores
a) Um jogador - estes jogos são chamados de jogos contra a natureza. Se a
estratégia da natureza é determinada, o jogo é trivial; se a estratégia da
natureza é probabilística, estes jogos são chamados de problemas de decisão; se
é indeterminada, pode-se tratar o jogo como sendo de duas pessoas se for
atribuída alguma perversidade à natureza.
b) Dois jogadores.
c) n jogadores (n maior que 2).
3. Natureza dos pagamentos
a) Soma zero - a soma de todos os pagamentos é zero.
b) Soma constante - a soma de todos os pagamentos é constante e diferente de
zero.
c) Soma variável - não há nenhuma relação entre os pagamentos dos jogadores.
4. Natureza da informação
a) Informação perfeita - conhecimento total de todos os movimentos anteriores.
b) Informação imperfeita.
171
Teoria dos Jogos
Jogos de Dois Jogadores e Soma Zero
• Dois jogadores e soma zero é o tipo de jogo mais estudado pela
teoria dos jogos.
• De modo simplificado, neste tipo de jogo cada um dos dois
jogadores escolhe uma entre suas estratégias possíveis.
• Uma vez que ambos os jogadores tenham tomado suas decisões,
elas são anunciadas e uma tabela de pagamentos (conhecida
anteriormente pelos dois jogadores) é utilizada para determinar o
pagamento de um jogador ao outro.
• A matriz abaixo representa o jogo. Nesta notação, a matriz
representa o pagamento do jogador Y para o jogador X. Se o valor
for negativo, o pagamento se dará do jogador X para o jogador Y.
172
Teoria dos Jogos
O jogador X pode escolher entre as estratégias A, B e C. O jogador Y pode
escolher entre D, E, F e G. O valor da matriz representa o valor a ser pago ao
jogador X. Como é um jogo de duas pessoas e soma zero, um ganho do jogador
X implica uma igual perda do jogador Y. Isto significa que se o jogador X
escolher a estratégia A e o jogador Y escolher a estratégia G, o jogador X
ganhará 9, ao passo que o jogador Y perderá os mesmos 9. Se o pagamento for
negativo (por exemplo –4), o jogador X ganhará -4, ou seja, perderá 4, ao passo
que o jogador Y ganhará 4.
173
Teoria dos Jogos
Quando o jogador X escolhe a estratégia A, ele pode ganhar 8, 2, 9 ou 5,
dependendo da estratégia escolhida pelo jogador Y. Ele pode garantir,
entretanto, um ganho de pelo menos min{8, 2, 9, 5} = 2, independente da
escolha do jogador Y. Da mesma maneira, se ele escolher a estratégia B, ele
garante um ganho de min{6, 5, 7, 8} = 5 e se escolher a estratégia C, a pior
hipótese é min{7, 3, -4, 7} = -4.
Estes valores estão indicados à direita da matriz, chamados de mínimos. Se o
jogador X selecionar a estratégia B, ele está maximizando seu menor ganho,
dado por max{2, 5, -4} = 5. Esta seleção é denominada maximin, já que
maximiza o mínimo ganho de cada opção. O valor resultante desta estratégia
é chamado valor maximin.
174
Teoria dos Jogos
O jogador Y, do outro lado, deseja minimizar suas perdas. Ele percebe que, se
usar a estratégia D, não pode perder mais do que max{8, 6, 7} = 8. Para as demais
estratégias, as máximas perdas estão apresentadas na matriz, como sendo o
valor máximo de cada coluna. O jogador Y irá então escolher a alternativa que
minimize sua máxima perda, que é a estratégia E, uma vez que min{8, 5, 9, 8} = 5.
Esta seleção é denominada minimax, já que minimiza a máxima perda de cada
opção. O valor resultante desta estratégia é chamado valor minimax.
175
Teoria dos Jogos
Percebe-se que, para qualquer jogo de duas pessoas e soma zero, o valor
minimax é sempre maior ou igual ao valor maximin. No caso de igualdade, as
estratégias são chamadas estratégias ótimas e o jogo tem um ponto de sela.
Este ponto é o ponto ótimo do jogo, e é igual ao valor maximin e ao valor
minimax. O ponto é otimo, já que nenhum jogador mudará sua estratégia, uma
vez que o resultado será pior caso o outro jogador mantenha a estratégia.
Em geral, o valor do jogo deve satisfazer a inequação
176
Teoria dos Jogos
Estratégias Mistas
Na seção anterior, fo i apresentado um jogo que continha um ponto de sela.
Há casos, entretanto, nos quais este ponto de sela não existe. Como exemplo,
é apresentada a matriz abaixo.
Este jogo não possui um ponto de sela, e a estratégia minimax-maximin não é
a estratégia ótima, uma vez que os jogadores podem melhorar seus
resultados selecionando uma estratégia diferente. Neste caso, o jogo é
instável.
177
Teoria dos Jogos
Estratégias Mistas
Olhando para este jogo, percebe-se que algum tipo de troca de estratégias se faz
necessária. Se X escolher entre as alternativas A e B de maneira sistemática (por
exemplo, alternando entre A e B), esta troca sistemática será detectada pelo
jogador Y. Então Y escolherá F quando X escolher A e C quando X escolher B. Um
argumento similar serve para Y.
Portanto, a variação da escolha entre as alternativas deve ter alguma
aleatoriedade associada a ela. Suponhamos que o jogador X jogue uma moeda
para saber se escolhe a alternativa A ou B. Chamaremos de pA a probabilidade
de escolher A e de pB a probabilidade de escolher B.
Os pagamentos esperados para uma estratégia aleatória são os seguintes:
178
Teoria dos Jogos
Estratégias Mistas
Ao jogar uma moeda, as probabilidades pA e pB são iguais, e valem 0,5. Neste
caso, os pagamentos esperados são:
179
Teoria dos Jogos
Estratégias Mistas
Entretanto, pode-se escolher uma estratégia que defina as probabilidades de
modo a otimizar o resultado. Suponhamos que o jogador X deseje maximizar o
menor pagamento vindo de Y. Designando este pagamento por u, o problema
pode ser modelado como:
180
Teoria dos Jogos
Estratégias Mistas
É conveniente rearrumar o modelo de modo a ter todas as variáveis do lado
esquerdo das equações e inequações, ou seja:
181
Teoria dos Jogos
Estratégias Mistas
Em contrapartida, o jogador Y deseja variar entre suas alternativas de modo a minimizar o
maior pagamento ao jogador X. As probabilidades da escolha das alternativas C, D, E e F
são, respectivamente, qC, qD, qE e qF. Designando o pagamento ao jogador X por v, o
problema pode ser modelado como:
O modelo pode ser rearrumado da mesma forma que o modelo referente ao jogador X.
Desta forma, ao serem definidas as probabilidades de cada alternativa, o jogador deve
selecioná-las seguindo esta probabilidade, de modo aleatório, para que sua estratégia
não seja detectada pelo outro jogador.
182
1. A matriz abaixo representa um jogo de dois competidores (X e Y). Nesta
notação, a matriz representa o pagamento do jogador Y para o jogador X. Se o
valor for negativo, o pagamento se dará do jogador X para o jogador Y. O
jogador X pode escolher entre as estratégias A, B e C. O jogador Y pode
escolher entre D, E, F e G. Utilizando a teoria dos jogos, identifique se existe o
chamado ponto de cela (John Forbes Nash), existente quando ocorre a igualdade:
“Max(Min) = Min(Max)”.
y
Jogador x
Jogador
D
E
F
G
A
8
2
9
5
B
6
5
7
8
C
7
3
-4
7
183
22a. Aula
Capítulo 7: Teoria dos Jogos
Objetivo: Exercícios sobre Teoria dos Jogos.
Metodologia
1. Aula expositiva;
184
23a. Aula
Capítulo 8: Teoria das Filas
Objetivo: Apresentar os conceitos e estrutura da
Teoria das Filas.
Metodologia
1. Aula expositiva;
2. Exercícios em aula (individual).
185
Capítulo 8: Teoria das Filas – 23a. Aula
Filas de espera
• Fila de espera: mais “clientes” esperando por atendimento.
• População de clientes: uma entrada que gera clientes potenciais.
• Instalação de serviço: uma pessoa (ou equipe), uma máquina (ou grupo de
máquinas) ou ambos, necessários para executar o serviço para o cliente.
• Regra de prioridade: uma regra que seleciona o próximo cliente a ser
atendido pela instalação de serviço.
• Sistema de serviço: o número de filas e a disposição das instalações.
186
Modelos de filas de espera:
elementos básicos
187
Arranjos de instalações de serviços
Canal: uma ou mais instalações requeridas para fornecer
um serviço dado.
Fase: um passo único ao fornecer o serviço.
Regra de prioridade: a diretriz que determina qual o
próximo cliente a ser atendido.
188
Arranjos de instalações de serviço
189
Regra de prioridade
•
A regra de prioridade determina qual o próximo cliente a ser atendido.
•
A maioria dos sistemas de serviços usa a regra do primeiro a chegar,
primeiro a ser atendido (PCPA). Outras regras de prioridade incluem:
• Data de vencimento mais antiga (DVA)
• Cliente com o menor tempo de processamento esperado (TPE)
•
Norma de preferência: Uma regra que permite que um cliente de
prioridade mais alta interrompa o serviço de outro cliente.
190
Distribuição de probabilidade e tempo de atendimento
 A distribuição exponencial descreve a probabilidade de que o tempo de
atendimento ao cliente em uma instalação específica não seja maior do que
períodos de tempo T.
191
Características operacionais
•
Comprimento da fila: o número de clientes na fila.
•
Número de clientes no sistema: inclui clientes na fila de espera e
sendo atendidos.
•
Tempo de espera na fila: espera pelo início do atendimento.
•
Tempo total no sistema: tempo total decorrido entre a entrada no
sistema e a saída do sistema.
•
Utilização da instalação de serviço: reflete o percentual de tempo em
que os servidores estão ocupados.
192
Modelo de servidor único
• O modelo mais simples de fila de espera envolve um servidor único e uma fila
única de clientes.
• Suposições:
• A população de clientes é infinita e paciente.
• Os clientes chegam de acordo com uma distribuição de Poisson, com uma
média de taxa de chegada de .
• A distribuição do atendimento é exponencial, com uma média de taxa de
atendimento de µ.
• A média de taxa de atendimento ultrapassa a média da taxa de chegada.
• Os clientes são atendidos de acordo com o princípio de primeiro a chegar,
primeiro a ser atendido.
• O comprimento da fila de espera é indefinido.
193
Modelo de servidor único
194
Sistema de canal único, fase única – Exemplo
195
Analisando taxas de serviço com o modelo
de servidor único
A gerente da mercearia de Sunnyville no Exemplo C.3 deseja responder às
seguintes perguntas:
a.
Que taxa de serviço seria necessária para que os clientes gastassem em
média apenas oito minutos no sistema?
b.
Para essa taxa de atendimento, qual é a probabilidade de haver mais de
quatro clientes no sistema?
c.
Qual a taxa de atendimento necessária para que se tenha apenas uma
chance de 10 por cento de haver mais de quatro clientes no sistema?
196
de servidor único
SOLUÇÃO
O solucionador de filas de espera do OM Explorer pode ser usado
repetidamente para responder às perguntas. Aqui mostramos apenas
como resolver o problema manualmente.
a.
Usamos a equação para o tempo médio no sistema e encontramos µ.
W = 1/ µ - 
8 minutos = 0,133 hora = 1/ µ - 30
0,133 µ - 0,133(30) = 1
µ = 37,52 clientes/hora
197
de servidor único
b.
A probabilidade de haver mais de quatro clientes no sistema é igual a 1
menos a probabilidade de quatro ou menos clientes no sistema.
e
Assim,P = 1 – 0,2(1+0,8 + 0,82 + 0,83 + 0,84)= 1 – 0,672 = 0,328
Portanto, há quase 33 por cento de chances de que mais do que quatro clientes
estejam no sistema.
198
de servidor único
c. Usamos a mesma lógica que na parte (b), à exceção de que µ é agora uma variável de
decisão. O modo mais fácil de proceder é, primeiro, encontrar a utilização média correta e,
em seguida, achar a taxa de atendimento.P = 1 – 1 – 1+  +2+ 3+4)
Ou
199
de servidor
Portanto, para uma taxa de utilização de 63 por cento, a probabilidade
de haver mais de quatro clientes no sistema é de 10 por cento. Para 
= 30, a média da taxa de serviço deve ser
30/µ = 0,63
µ = 47,62 clientes/hora
200
Modelos de filas de espera:
elementos básicos
 Com o modelo de servidor múltiplo, os clientes formam uma fila única
e escolhem um dos
s servidores quando um está disponível.
 O sistema de serviço tem apenas uma fase.
 Há s servidores idênticos.
 A distribuição de atendimento para cada um é exponencial.
 A média do tempo de atendimento é 1/µ.
 A taxa de atendimento (sµ) excede a taxa de chegada ().
201
Sistemas de servidor múltiplo –
Exemplo
O Serviço Americano de Remessas está preocupado com a quantidade de
tempo que os caminhões permanecem ociosos, esperando para ser
descarregados.
O terminal opera com quatro zonas de descarga. Cada zona requer uma equipe
de dois funcionários e cada equipe custa $30/h.
O custo estimado de um caminhão ocioso é de $50/h. Os caminhões chegam a
uma taxa média de três por hora, de acordo com uma distribuição de Poisson.
Em média, uma equipe pode descarregar um veículo de carga em uma hora,
com tempos de serviço exponenciais.
4 zonas de descarga
2 funcionários/equipe
Taxa de chegada = 3/hora
Custos da equipe $ 30/hora
Custos de caminhões ociosos $ 50/hora
Tempo de atendimento = 1 hora
202
203
Modelo de servidor múltiplo
204
Modelo de servidor múltiplo
205
1. Defina o que é Teoria das Filas e explique os modelos existentes.
2. Aonde poderia ser aplicada a teoria das filas? Cite 4 exemplos.
206
24a. Aula
Capítulo 8: Teoria das Filas
Objetivo: Apresentar os conceitos e estrutura da
Teoria das Filas. Lei de Little.
Metodologia
1. Aula expositiva;
207
Lei de Little
• A Lei de Little relaciona o número de clientes em um sistema de fila de
espera com o tempo de espera dos clientes.
•
L = W
• L é o número médio de clientes no sistema.
•  é a taxa de chegada do cliente.
• W é o tempo médio gasto no sistema, incluindo o atendimento.
208
Modelo da fonte finita
• No modelo da fonte finita, as suposições do modelo de servidor único
são alteradas de modo que a população de clientes seja finita,
havendo apenas N clientes potenciais.
• Se N for maior que 30 clientes, então o modelo de servidor único com
uma população de clientes infinita é adequado.
209
Modelo da fonte finita
210
Analisando custos de manutenção com o modelo da
fonte finita – Exemplo C.6
211
Áreas de decisão para gerência
1. Taxas de chegada
2. Números de instalações de serviço
3. Número de fases
4. Números de servidores por instalação
5. Eficiência do servidor
6. Regra de prioridade
7. Disposição da fila
212
Áreas de decisão para gerência
213
Exercícios sobre Teoria das Filas.
Laboratório de Informática.
214
Capítulo 9: Simulação, Softwares e Aplicação
25a. Aula
Objetivo: Simulação
aplicação.
através
de
softwares
e
Metodologia
1. Aula expositiva;
215
SIMULAÇÃO
Capítulo 9: Simulação, Softwares e Aplicação – 25a. Aula
“APRENDER ATRAVÉS DA SIMULAÇÃO”
Características de um sistema de administração da produção atual:
•Alto volume de informações;
•Necessidade de diferenciar e diversificar a produção de um bem/serviço para
acompanhar as mudanças de mercado;
•As empresas procuram acompanhar essa revolução e, com isso, têm
implementado modificações importantes em seus sistemas. Mas os sistemas de
manufatura/serviços possuem ambientes possuidores de um grande número de
variáveis que afetam seu desempenho;
Histórico:
•Estudos de Von Neumann e Ulan ;
•Tais estudos tornaram-se conhecidos como análise ou técnica de Monte Carlo.
Essa técnica matemática é conhecida desde o século passado, na época em que
os cientistas trabalhavam secretamente no projeto denominado "Manhattan" em
Los Alamos, para o desenvolvimento da bomba atômica dos aliados.
Posteriormente porém, a simulação, como técnica para solução de problemas,
encontrou como campo mais fértil de aplicação, o tratamento dos problemas
eminentemente probabilísticos, cuja solução analítica é, geralmente, muito mais
árdua e difícil, senão impossível.
216
APLICAÇÕES DA SIMULAÇÃO
•a Draw Tite Inc. pretendia transformar suas células de manufatura em uma
linha de produção contínua, mas ao simular as modificações pretendidas,
percebeu que elas não trariam resultados positivos, e evitou o gasto de U$
80.000,00 na aquisição de novas máquinas. Boblitz ( 1991);
•a empresa de consultoria denominada Northern Research and Engineering
Corp. simulou uma nova linha de produção da Torrington Co. e verificou que 4
das 77 máquinas que seriam compradas não eram necessárias, poupando-se
U$ 750.000,00. Wild & Port (1987);
•a Exxon simulou a manufatura com a mistura, a estocagem e as operações
de expedição da gasolina, e poupou U$ 1,4 milhões na sua primeira aplicação.
Graff (1986);
o setor da Decaparia da Companhia Siderúrgica Belgo Mineira, em Contagem
- MG. Possuia movimentação de cargas através de cinco pontes rolantes que
eram o gargalo do sistema. Após várias simulações, percebeu-se que a
solução mais viável era a mudança de layout (Decaparia em linha) e projeto de
um mecanismo de retorno de ganchos (sem a necessidade do uso de ponte
rolante) . Com isso, aumentaria a produção e uma ponte rolante poderia ser
desativada (ou utilizada como reserva) (Gazzinelli, 1996).
217
DEFINIÇÃO DE SIMULAÇÃO
Naylor (1971): "simulação é uma técnica numérica para realizar
experiências em um computador digital, as quais certos tipos de modelos
lógicos que descrevem o comportamento de um sistema econômico ou de
negócios ( ou um aspecto parcial de um deles) sobre extensos intervalos de
tempo".
Martinelli (1987): "a simulação é um meio de se experimentar idéias e
conceitos sob condições que estariam além das possibilidades de se testar
na prática, devido ao custo, demora ou risco envolvidos".
Schriber (1974): "simulação implica na modelagem de um processo ou
sistema de tal forma que o modelo imite as respostas do sistema real numa
sucessão de eventos que ocorrem ao longo do tempo".
Pegden (1990): "a simulação pode ser definida como um processo de
modelagem de um sistema real e a condução de experimentos com este
modelo, com o propósito de entender o comportamento do sistema".
Banks e Carson (1994): referenciam a palavra simular como uma maneira
de fingir a essência de algo sem a realidade; é a construção de um modelo
abstrato representando algum sistema real.
218
LINGUAGENS DE SIMULAÇÃO
Inicialmente linguagens de programação de propósito geral: FORTRAN,
BASIC, PASCAL, etc.
Posteriormente linguagens de programação dedicadas à simulação:
GPSS, SIMAN, SLAM, SIMSCRIPT, etc. (bibliotecas formadas por
conjuntos de macro comandos das linguagens de propósito geral).
Alguns dos simuladores da geração seguinte, foram desenvolvidos
sobre a plataforma dessas linguagens. Como exemplo disso temos o
caso do ARENA, construído sobre a linguagem SIMAN.
219
VANTAGENS DA SIMULAÇÃO
•permite replicação precisa dos experimentos, podendo-se assim, testar
alternativas diferentes para o sistema;
•fornece um controle melhor sobre as condições experimentais do que seria
possível no sistema real;
•permite simular longos períodos em um tempo reduzido;
•é, em geral, mais econômico que testar o sistema real, e evita gastos inúteis na
compra de equipamentos desnecessários;
•uma vez criado, um modelo pode ser utilizado várias vezes a fim de avaliar
projetos e propostas;
•a simulação é, geralmente, mais fácil de aplicar do que métodos analíticos;
•enquanto os modelos analíticos exigem um grande número de simplificações para
que possam ser tratados matematicamente, os modelos de simulação não
apresentam tais restrições;
•o tempo pode ser controlado (expandido ou comprimido). Reprodução dos
fenômenos de maneira lenta ou acelerada
•pode-se compreender melhor quais variáveis são as mais importantes em relação
a performance e como as mesmas interagem entre si e com os outros elementos
do sistema;
a identificação de gargalos pode ser obtida de forma facilitada, principalmente com
ajuda visual;
220
DESVANTAGENS DA SIMULAÇÃO
•devido a sua natureza estocástica, os modelos de simulação devem ser
rodados várias vezes para poder se prever a performance do sistema;
•a simulação é muito dependente da validade do modelo desenvolvido;
•a técnica não é por si só otimizante, pois ela testa somente as alternativas
fornecidas pelo usuário;
•exige-se treinamento especial para construção de modelos;
•os resultados da simulação são, algumas vezes, de difícil interpretação e
requer do usuário, conhecimento profundo do sistema que ele programou;
a modelagem e a experimentação associadas à modelos de simulação,
consomem muitos recursos, principalmente tempo. Simplificar a modelagem
ou os experimentos na tentativa de economia, costuma gerar resultados
insatisfatórios.
ETAPAS DE UM PROJETO DE SIMULAÇÃO
Definição do Problema e Objetivos
Definição do Modelo Conceitual
Procura-se nesta etapa, responder a três perguntas:
•o que modelar ?
•como modelar ?
•como coletar os dados do sistema ?
Coleta de Dados
Codificação, Verificação e Validação do Modelo.
Projeto Experimental / Experimentação
Análise e Interpretação dos Resultados
221
Softwares para simulação
Produto
Empresa
Site
Repres.
www.sm.com
Sim
AutoMod
Systems Modeling
Corporation
Autosimulations
www.autosim.com
Sim
Extend
Imagine That
www.imaginethatinc.com
Não
GPSS H
Micro Saint
ProModel
SIMPLE ++
Wolverine Software
Micro Analysis & Design
ProModel Corporation
AESOP (Alemanha)
ND*
www.aesop.de
Sim
Sim
Sim
ND*
www.caciasl.com
ND*
www.taylorii.com
ND*
www.vissim.com
Sim
ARENA
Simscript II.5 e
CACI Products Company
MODSIM III
F&H Simulations
TAYLOR IIb
(Holanda)
VisSim
Visual Solutions
www.madboulder.com
www.promodel.com
*ND - Não disponível
222
1. Defina Simulação.
2. Quais vantagens e desvantagens podem ser descritas para uma
simulação de fila num pronto atendimento de um hospital?
Jutifique.
223
26a. Aula
Objetivo: Simulação através de
aplicação. Simulação Monte Carlo.
softwares
e
Metodologia
1. Aula expositiva;
224
Simulação Monte Carlo
• Simulação: o ato de reproduzir o comportamento de um sistema
usando um modelo que descreve os processos do sistema.
• Compressão de tempo: a característica das simulações que permite que
obtenham estimativas de características operacionais em muito menos
tempo do que é requerido para coletar os mesmos dados operacionais
de um sistema real.
• Simulação de Monte Carlo: processo de simulação que usa números
aleatórios para gerar eventos de simulação.
225
Specialty Steel Products Co.
• A Specialty Steel Products Company produz artigos como máquinas
operatrizes, equipamentos, peças de automóveis e outros artigos de
especialidade, em quantidades pequenas e sob encomenda do cliente.
• A demanda é medida em horas-máquina.
• As encomendas por produtos são convertidas em horas-máquina
requeridas
• A administração está interessada na capacidade do departamento de
tornearia mecânica.
• Reúna os dados necessários para analisar o acréscimo de mais um
torno mecânico e de um torneiro.
226
Registros históricos indicam que a demanda do departamento de
tornearia mecânica varia de semana a semana, como se segue:
227
A produção semanal média é determinada multiplicando cada requisito
de produção por sua freqüência de ocorrência.
228
Specialty Steel Products Co. – Atribuição
de números aleatórios
• Números aleatórios agora devem ser atribuídos para representar a
probabilidade de cada evento de demanda.
• Número aleatório: Um número que tem a mesma probabilidade de ser
selecionado que qualquer outro número.
• Uma vez que as probabilidades para todos os eventos de demanda
perfazem 100 por cento, usamos números aleatórios entre (e
inclusive) 00 e 99.
• Dentro desta escala, um número aleatório na escala de 0 a 4 tem uma
chance de 5% de ser selecionado.
• Podemos usá-la para representar nossa primeira demanda semanal de
200 que tem uma probabilidade de 5%.
229
Specialty Steel Products Co. – Atribuição
de números aleatórios
230
Specialty Steel Products Co. –
Formulação de modelo
• Formular um modelo de simulação requer que se especifiquem as
relações entre as variáveis.
• Modelos de simulação consistem em variáveis de decisão, variáveis
incontroláveis e variáveis dependentes.
• Variáveis de decisão: variáveis que são controladas pelo tomador de
decisão e mudam de um período a outro quando eventos diferentes
são simulados.
• Variáveis incontroláveis são eventos aleatórios que o tomador de
decisão não pode controlar.
231
232
233
Um estado estacionário ocorre quando a simulação é repetida por vezes
suficientes para que os resultados médios para medidas de
desempenho permaneçam constantes.
234
235
27a. Aula e 28a. Aula
Objetivo: Simulação Monte Carlo. Exercícios.
Metodologia
1. Aula expositiva;
236
29a. Aula – 40a. Aula
Objetivo: Simulação em Computador. Projeto de
Simulação.
Metodologia
1. Aula expositiva;
237
Capítulo 9: Simulação, Softwares e Aplicação – 29a Aula - 40a. Aula
Simulação em computador
• A simulação para a Specialty Steel Products demonstrou o básico da
simulação.
• Entretanto, ela envolveu apenas um passo do processo, com duas
variáveis incontroláveis (requisitos de produção semanal e três
horas-máquina realmente disponíveis) e os períodos multiplicados
por 20.
• Modelos de simulação simples, com uma ou duas variáveis
incontroláveis podem ser desenvolvidos usando o gerador de números
aleatórios do Excel.
• Simulações mais sofisticadas podem se tornar demoradas e
requerer um computador.
238
239
Modelo de simulação para a
revendedora de carros BestCar
• Abaixo está uma distribuição de probabilidade para o número de
carros vendido semanalmente na BestCAr
• O preço de venda por carro
é $20.000. Projete um
modelo de simulação que
determine a distribuição de
probabilidade e a média
das vendas semanais.
240
241
Simulação com SinQuick
• Simquick é um pacote fácil de usar que é simplesmente uma planilha do
Excel com algumas macros.
• Aqui consideramos o processo de segurança de passageiros em um terminal
de um aeroporto de médio porte entre as 8 e as 10 horas da manhã.
• Os passageiros chegam à área de segurança em uma fila única e passam por
um dos dois postos de inspeção consistindo de um detector de metal e um
scanner de bagagem de mão.
• Depois disso, 10% são selecionados aleatoriamente para uma inspeção
adicional por uma das duas estações.
• A gerência está interessada em examinar o efeito do aumento do número
de inspeções aleatórias para 15% e 20%.
• Eles também querem pensar sobre uma terceira estação para a segunda
inspeção.
242
243
Resultados da simulação do processo de
segurança de passageiros
244
Prova 2
Entrega do Projeto de Simulação
245
Entrega de Médias Finais
Autoavaliação do Semestre
246

0 - sandro.eng.br

Transcrição

Documentos relacionados

1. História do PVsyst 2. Visão Geral do Software 3

Roteiro

(11) 3888-9200 PRONTOS Loja SAIBA MAIS (DESCRIÇÃO)

a/0 b/0 c/0 d/1 e/1 1 0 0 0 0 1 1 1 1 0

SBDI 2007 - dinergia

CRIAÇÃO DE UMA FERRAMENTA 3D PARA SIMULAÇÃO

Tandy Leather EU oferece o nível de preços Elite a empresas, lojas

Untitled

LAVRAS NOVAS - Mapa dos bens inventariados

estandarte da loja - ARLS Domicio Moreira N.3896