Baixe o app para aproveitar ainda mais
Prévia do material em texto
Unidade 1 CONCEITOS DE DECISÃO E O ENFOQUE GERENCIAL DA PESQUISA OPERACIONAL Profa. Marina Vargas • Conhecer as origens da pesquisa operacional; • Conhecer o processo de tomada de decisão; • Identificar o tipo de decisão; • Entender o que é pesquisa operacional. Objetivos: Origens: A expressão pesquisa operacional foi usada pela primeira vez em 1938 e se fortaleceu na 2.ª Guerra Mundial. - Natureza tática - Natureza logística - Táticas militares Fonte: <https://goo.gl/TUe2yD> Origens: das tropas, as táticas de defesa e ataques aéreos ou marítimos. Guerra: Cientistas britânicos tomavam decisões com bases científicas sobre a melhor utilização do material de guerra, o abastecimento Fonte: <https://aviacaocivilemilitar.wordpress.com/tag/alemanha-na-segunda-guerra- mundial/> Origens: • Pós-Guerra: Após a guerra, as ideias propostas para as operações militares foram adaptadas para melhorar a eficiência e a produtividade no setor Civil. Método Simplex - George Dantzig (1947), para a resolução de problemas de programação linear Final dos anos 1950: programação linear, programação dinâmica, teoria das filas e teoria de estoques. Tomar decisões é uma tarefa básica da gestão Ciência da tomada de decisão. George B. Dantzig, em entrevista que foi republicada, in memoriam, na edição de junho de 2005 pela revista “OR/MS Today”. Em 1957, a USP criou o primeiro curso de Engenharia de Produção do Brasil. Dois anos depois, o ITA também criou o curso, onde incluía disciplinas de PO, tais como teoria de jogos, simulação, filas e estatística, enquanto a USP já discutia aplicações de programação linear. PUC-RJ: primeiro computador IMPA e ENCE: programação linear No Brasil: • O primeiro Simpósio Brasileiro de Pesquisa Operacional (SBPO) foi realizado em 1968 no ITA e incluía alguns pesquisadores do país. • Na sequencia foi criada a Sociedade Brasileira de Pesquisa Operacional (SOBRAPO). No Brasil: Cabe ao decisor: Identificar e definir o problema; Formular Objetivo(s); Analisar limitações. Avaliar alternativas e escolher a melhor; A solução de problemas através de pesquisa operacional pode ser implementada a partir de um procedimento de sete etapas Modelagem e tomada de decisão em sistemas reais, determinísticos ou probabilísticos, relativos à necessidade de alocação de recursos escassos (MARINS, 2011). Ela pretende tornar científico, racional e lógico o processo decisório nas organizações (PANDOLFI, 2011). Qualitativo: problemas simples, baseados na experiência do decisor. Quantitativo: problemas complexos; ótica científica. O processo de decisão pode ter duas abordagens: QUALITATIVO QUANTITATIVO APLICAÇÕES: Diversas áreas: Determinação de mix de produtos; Escalonamento de produção; Roteirização e logística; Planejamento financeiro; Análise de projetos; Alocação de recursos de mídia; Designação de equipe, etc. Exemplificação: Qual a quantidade de cada tipo de casa que o condomínio deve ter? 2, 3 ou 4 quartos Custos e lucros diferentes para cada tamanho. Mínimo 20 casas de 2; 30 de 3; 15 de 4. Valor máximo de dinheiro para investir. Projeto de Condo- mínio REFERÊNCIAS MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: Cultura Acadêmica, 2011. PANDOLFI, C. Pesquisa operacional: notas de aula. Caxias do Sul: FSG, 2011. TAHA, H. A. Pesquisa operacional. 8. ed. São Paulo: Pearson, 2008. EHRLICH, P. J. Pesquisa operacional – curso introdutório. São Paulo: Atlas, 1988. Unidade 2 FORMULAÇÃO DE PROBLEMAS Profa. Marina Vargas Objetivos: • Conhecer algumas técnicas qualitativas de auxílio à tomada de decisão; • Entender o processo de modelagem; • Formular problemas, identificando a função objetivo, as variáveis e as restrições. Algumas Técnicas Qualitativas: • Diagrama de Ishikawa ou dos 4M´s; • Brainstorming; • Brainwriting; • Método de Delineamento de Problemas Organizacionais (MDPO); • 5W2H; • Árvore de decisão qualitativa, etc. Diagrama de Ishikawa ou dos 4M´s O diagrama de Ishikawa, também conhecido como dos 4M’s, ou de causa e efeito ou diagrama espinha de peixe, foi desenvolvido por Kaoru Ishikawa, da Universidade de Tóquio, em 1943. Os 4M’s iniciais foram: método, mão de obra, matéria-prima e máquinas. Brainstorming : “tempestade de ideias”. Dinâmica de grupo – "sem medo de críticas" Deve-se usar três etapas: - levantamento de dados gerais; - desenvolvimento de ideias como possíveis soluções; - escolha final da melhor solução. Brainwriting A técnica do brainwriting é iniciada por processo escrito e, no final, utiliza o brainstorming. A função é a mesma do brainstorming, mas garante um sigilo inicial da autoria das ideias, que pode aumentar as chances de aparecerem ideias muito criativas e desprovidas de preconceito. 5W2H: 7 perguntas sobre o assunto em estudo, em três etapas distintas da solução de problemas: diagnóstico, plano de ação e de padronização. Inglês Português What? O quê? Who? Quem? When? Quando? Why? Por quê? Where? Onde? How? Como? Howmuch? Quanto custa? Processo de Modelagem As grandezas são representadas por variáveis de decisão e suas relações por expressões matemáticas. Problema descrito com palavras Problema de Programação Matemática Modelagem Etapas e modelagem: a) entendimento do problema; b) coleta de dados relevantes; c) modelagem; d) validação. Modelo de otimização • Modelo: representações de um sistema e de seu comportamento U = f ( X i , Y j ) • Onde –U = valor do desempenho do sistema –X i = as variáveis que podem ser controladas –Y j = as constantes que afetam U –f = o relacionamento entre U, X j e Y j Um fazendeiro precisa decidir quantos hectares deve plantar de milho e arroz. Para cada hectare de milho plantado, recebe de lucro R$5, e para o arroz, R$2. Por razões técnicas, a área de milho não pode exceder 3 hectares e a de arroz não deve ser maior que 4 hectares. O milho necessita do cuidado de 1 pessoa por hectare, e o arroz, de 2 pessoas. O número total de pessoas disponíveis é 9. Qual deve ser a decisão do fazendeiro para que tenha lucro máximo? Formulação de Problemas: Formulação de Problemas: • Variáveis de decisão: – x 1 a área a ser plantada de milho – x 2 a área a ser plantada de arroz • Variáveis incontroláveis: – lucro por ha de milho plantado: $ 5,00 – lucro por ha de arroz plantado: $ 2,00 Formulação de Problemas: Formulação de Problemas: REFERÊNCIAS MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: Cultura Acadêmica, 2011. PANDOLFI, C. Pesquisa operacional: notas de aula. Caxias do Sul: FSG, 2011. TAHA, H. A. Pesquisa operacional. 8. ed. São Paulo: Pearson, 2008. EHRLICH, P. J. Pesquisa operacional: curso introdutório. São Paulo: Atlas, 1988. Unidade 3 SOLUÇÃO GRÁFICA DE PROBLEMAS LINEARES Profa. Marina Vargas Objetivos: • Identificar um problema de programação linear; • Formular o problema para a solução gráfica; • Inserir no gráfico todas as restrições; • Identificar no gráfico a solução ótima. Programação Linear: A programação linear foi um dos maiores avanços científicos dos meados do século XX e é considerado um dos mais importantes instrumentos da pesquisa Operacional. Tipos de Solução: 1.Solução : Qualquer especificação de valores, dentro do domínio da função objetivo. 1.Solução Viável : Todas as restrições são satisfeitas. 1.SoluçãoÓtima : Restrições satisfeitas e valor mais favorável da função objetivo Solução Gráfica: 1. Apenas duas variáveis de decisão; 2. x 1 e x 2 representam as informações nos eixos X e Y. 3. Equação linear com duas variáveis é uma reta. 4. Inequação linear com duas variáveis é um dos semi-planos definidos pela reta da equação Exemplo: Problema Unidade 2: Um fazendeiro precisa decidir quantos hectares deve plantar de milho e arroz. Para cada hectare de milho plantado recebe de lucro R$ 5, e para o arroz R$ 2. Por razões técnicas a área de milho não pode exceder 3 hectares e a de arroz não deve ser maior que 4 hectares. O milho necessita do cuidado de 1 pessoa por hectare e o arroz de 2 pessoas. O número total de pessoas disponíveis é 9. Qual deve ser a decisão do fazendeiro para que tenha lucro máximo? Exemplo: Passo 1: Formulação do problema: • Variáveis de decisão (controláveis): – x 1 a área a ser plantada de milho – x 2 a área a ser plantada de arroz - Eixo X para a variável x 1 (área a ser plantada de milho) - Eixo Y para a variável x 2 (área a ser plantada de arroz). • Variáveis incontroláveis (constantes): - lucro por há de milho plantado: R$ 5,00 - lucro por há de arroz plantado: R$ 2,00 • Função objetivo: • Maximizar L=5x 1 +2x 2 • ou max L=f(x i ,y i )=5x 1 +2x 2 • Restrições técnicas: - Área máxima de milho = 3 ha = x 1 ≤ 3 - Área máxima de arroz = 4 ha = x 2 ≤ 4 • Restrições técnicas: • Restrições de não negatividade (Condição de Existência): x 1 ≥ 0 x 2 ≥ 0 milho = 1 pessoa por ha arroz = 2 pessoas por ha Total de pessoas disponíveis = 9, ou seja, x 1 + 2 x 2 ≤ 9 Passo 2: Pelos teoremas da programação linear, a solução ótima estará em pelo menos um dos pontos extremos do polígono que representa o conjunto de soluções viáveis. Passo 3: Inserir a função objetivo e identificar a solução ótima. A função objetivo é max L = 5 x 1 + 2 x 2 Fonte: <https://www.geogebra.org/home> Portanto, pelos teoremas, a solução ótima está no ponto x 1 = 3 e x 2 =3, com um lucro máximo de R$ 21. Isso significa que o fazendeiro deverá plantar 3 ha de milho e 3 ha de arroz para ter o maior lucro! REFERÊNCIAS MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: Cultura Acadêmica, 2011. PANDOLFI, C. Pesquisa operacional: notas de aula. Caxias do Sul: FSG, 2011. TAHA, H. A. Pesquisa operacional. 8. ed. São Paulo: Pearson, 2008. EHRLICH, P. J. Pesquisa operacional: curso introdutório. São Paulo: Atlas, 1988. Unidade 4 PROGRAMAÇÃO LINEAR: MÉTODO SIMPLEX Profa. Marina Vargas • Conhecer a solução analítica para problemas de programação linear; Aprender a usar a forma tabular Simplex; • Resolver problemas de programação linear. Objetivos: Método Simplex O método consiste em encontrar uma solução inicial viável e fazer iterações para melhorá-la. Para isso, as inequações das restrições deverão ser transformadas em equações. Fonte: adaptado de Lachtermacher (2009) Variáveis de Folga • Se a ≤ b, podemos dizer que a + c = b, onde c, um valor maior que zero, é chamado folga de a em relação a b. • Caso a ≥ b, podemos, da mesma forma, escrever que a – c =b, e neste caso c é chamado de excesso de a em relação a b. Problema da Unidade 2 Resolvido graficamente na Unidade 3 Função objetivo: Maximizar L = 5x 1 + 2x 2 Sujeito a: -área máx. de milho = 3 ha : x 1 ≤ 3 -área máx. de arroz = 4 ha : x 2 ≤ 4 -total de pessoas disponíveis : x 1 + 2 x 2 ≤ 9 Condição de Existência: x 1 ≥ 0 x 2 ≥ 0 Inserindo as variáveis de Folga temos: Variáveis de folga x 3 , x 4 e x 5 . Assim: x1 + x3 = 3 x2 + x4 = 4 x1 + 2x2 + x5 = 9 Z – 5x1 – 2x2 = 0 com x1 , x2 , x3 , x4 , x5 ≥ 0 Calculadora Online: <http://www.phpsimplex.com/simplex/page1.php?l=pt&metodo=simplex&v=2&rt=3 &Submit=Continuar> x 1 x 2 x 3 x 4 x 5 -5 -2 0 0 0 Z x 3 1 0 1 0 0 3 L1 x 4 0 1 0 1 0 4 L2 x 5 1 2 0 0 1 9 L3 Tabela Simplex Original Procedimento Iterativo Solução inicial: (0, 0, 3, 4, 9) e Z = 0 Note que as variáveis x 3 , x 4 e x 5 formam uma base em R3 , ou seja, essas três variáveis nos dão uma solução trivial do sistema linear: x 3 = 2, x 4 = 2 e x 5 = 3. Nesse ponto, temos que x 1 = 0 e x 2 = 0, pois essas duas variáveis estão fora da base. Solução inicial (0, 0, 3, 4, 9) e Z = 0 Análise gráfica dessa solução x 1 x 2 x 3 x 4 x 5 -5 -2 0 0 0 Z x 3 1 0 1 0 0 3 L1 x 4 0 1 0 1 0 4 L2 x 5 1 2 0 0 1 9 L3 Iteração 1: Coluna 1, pois tem maior valor absoluto entre x 1 e x 2 ; L1, pois 1/3> 0/4 e 1/3> 1/9. x 1 x 2 x 3 x 4 x 5 -5 -2 0 0 0 Z= 0 x 3 0 1 0 0 3 L1 x 4 0 1 0 1 0 4 L2 x 5 1 2 0 0 1 9 L3 L3-L1 e LZ-5L1 1 Método da Redução de Gauss para escalonamento de matriz. x 1 x 2 x 3 x 4 x 5 0 -2 5 0 0 Z= 15 x 3 1 0 1 0 0 3 L1 x 4 0 1 0 1 0 4 L2 x 5 0 -1 0 1 6 L3 Resultado da primeira iteração: Iteração 2: Coluna 2, transformar x 2 ; L3, pois 2/6> 1/4 e 2/6> 0/3. 2 x 1 x 2 x 3 x 4 x 5 0 0 4 0 1 Z= 21 x 3 1 0 1 0 0 3 L1 x 4 0 0 1/2 1 -1/2 1 L2 x 5 0 1 -1/2 0 1/2 3 L3 2L2-L3 e LZ+L3 <http://www.phpsimplex.com/simplex/page4.php?f=1&l=pt> A solução ótima está no ponto x 1 = 3 e x 2 =3, com um lucro máximo de R$ 21 Além de calcula- doras online, também podemos usar o Solver do Excel ou Libre Office. Resolução Gráfica Fonte: <https://goo.gl/cMki9q> REFERÊNCIAS LACHTERMACHER, G. Pesquisa operacional na tomada de decisão. 4. ed. São Paulo: Pearson Prentice Hall, 2009. MOREIRA, Daniel A. Administração da produção e operações. São Paulo: Pioneira Thomson Learning, 2004. 619 p. MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: Cultura Acadêmica, 2011. TAHA, H. A. Pesquisa operacional. 8. ed. São Paulo: Pearson, 2008. Unidade 5 ÁRVORE DE DECISÃO Profa. Marina Vargas Objetivos: • Saber definir os elementos que constituem uma árvore de decisão; • Ter facilidade em estruturar uma árvore de decisão; • Saber resolver o problema por meio de uma árvore de decisão, encontrando a alternativa ótima; • Conhecer programas que utilizam a árvore de decisão. Sequência de Decisões Inter-Relacionadas e os Resultados Esperados. Conceitos gerais sobre árvores de decisão É um grafo composto por nós quadrados que representam as escolhas a serem feitas (alternativas possíveis), nós em forma de círculos que representam as chances de cada alternativa (estados da natureza) e nós triangulares com os resultados da decisão Árvore de Decisão Fonte: https://goo.gl/d9JrYn Deitada: Esquerda para a direita Em pé: Cima para baixo Exemplificação: Tabela de Pagamentos Caminho de um investidor. - debêntures, - ações - aplicação fixa. Probabilidades do mercado crescer, estagnar ou de haver inflação, eram de 50%, 30% e 20%, respectivamente. Exemplificação: Tabela de Pagamentos Para cada situação haveria diferentes rentabilidades, para o caso de crescimento, estagnação ou inflação: • Debêntures: R$ 12, R$ 6 e R$ 3, respectivamente; • Ações: R$ 15, R$ 3 e –R$ 2, respectivamente; • Aplicação fixa: R$ 6,5 para as três condições. Exemplificação: Tabela de Pagamentos Passo 1 – Representar as alternativas de decisão: os arcos (ramos) que saem dos nós quadrados representam as diferentes alternativas de decisão Montagem da Árvore: Passo 2 – Representar os estados da natureza: Si representa o estado de natureza e pi a probabilidade de ocorrênciado estado de natureza. Passo 3 – Representar os pagamentos atingidos (pay-offs) Passo 4 – Cálculo das Probabilidades. Passo 5 – Verificar qual a alternativa que atende ao objetivo do problema. • Debêntures: 0,5(12) + 0,3(6) + 0,2(3) = R$ 8,40 • Ações: 0,5(15) + 0,3(3) + 0,2(2) = R$ 8,00 • Aplicação fixa: 0,5(6,5) + 0,3(6,5) + 0,2(6,5) = R$ 6,5 Programas que utilizam a árvore de decisão Precision Tree®, da empresa Palisade, <http://www.palisade.com/precisiontree/>. Tree Plan®, desenvolvido pelo Prof. Michael R. Middleton, da School of Business and Management, da Universidade de São Francisco, Califórnia, <http:// www.treeplan.com/>. Planilha Excel: <http://ptcomputador.com/Software/microsoft- access/139960.html>. http://http: http://http: http://http: Bibliografia: -ACKOFF, R. L. & SASIENI, M. W. Pesquisa operacional. Livros Técnicos e Científicos e EDUSP. Rio de Janeiro, 1979. -EHRLICH, P. J. Pesquisa operacional – curso introdutório. Editora Atlas. São Paulo, 1988. -LACHTERMACHER, G. Pesquisa operacional na tomada de decisão. 4. ed. São Paulo: Pearson Prentice Hall, 2009. -WAGNER, H. Pesquisa Operacional. Prentice Hall do Brasil, 1986. Unidade 6 TEORIA DE FILAS Professora Marina Vargas Objetivos: • Conhecer os elementos que fazem parte das filas de espera; • Definir como são os componentes de um sistema de filas; • Saber quais são as características de operação das filas de espera; • Conhecer como funcionam os modelos de canal único e fase única; • Conhecer como funcionam os modelos de canais múltiplos e fase única. Elementos da análise de filas de espera Fila: uma simples fila de espera. Sistema de fila: engloba a distribuição de chegada dos clientes ao sistema; a distribuição do tempo que um cliente demora para ser atendido, dependendo do número de clientes que este encontra na fila de espera; a distribuição do serviço do cliente e o tempo que o cliente demora a ser servido e a sair do sistema. Fonte: <https://www.ime.unicamp.br/~hlachos/ME323-Teoria%20Filas.pdf> As filas são compostas pelos seguintes componentes: 1. Fonte de usuários; 2. Chegadas; 3. Linhas de espera; 4. Servidor(es); 5. Usuários atendidos. Elementos da análise de filas de espera Elementos contribuintes de um sistema de filas de espera Dimensão da população: • Infinita: quando a probabilidade de ocorrer uma nova chegada não é influenciada pelo número de clientes que já se encontram no sistema. • Finita: enumerável e contável. Dimensão da chegada: • Clientes chegam um a um; • Clientes chegam em grupo. Controle das chegadas: • Chegadas controláveis (ex.: inscrições em dias fixos.) • Chegadas incontroláveis (ex.: urgência de um hospital.) • Distribuição das chegadas: o padrão das chegadas pode ser descrito pelo tempo entre duas chegadas consecutivas (tempo entre chegadas) ou pelo número de chegadas por unidade de tempo (distribuição das chegadas). • Atitude dos clientes: • Paciente, permanecem na fila até serem atendidos. • Impaciente, desistem de esperar ou simplesmente não se juntam à fila se ela for muito grande. • Taxas das chegadas (λ): número médio de clientes que procuram o serviço por unidade de tempo. Elementos contribuintes de um sistema de filas de espera Exemplo de uma distribuição de Poisson Grandezas Distribuição de chegada Médias Taxa de chegada Poisson Tempo decorrido entre duas chegadas consecutivas Exponencial Fonte: Moreira, 2007. Fila de espera Serviço • Configuração do serviço: corresponde ao número de postos de atendimento e fases de atendimento. • Dimensão do serviço: • Simples: um cliente por vez no servidor (ex.: banco). • Grupo: vários clientes por vez no servidor (ex.: elevador) • Taxas de serviço (μ): número médio de clientes que podem ser atendidos por cada servidor e por unidade de tempo. Distribuição do tempo de serviço. Fila de espera Capacidade do sistema A capacidade do sistema corresponde ao número máximo de clientes que o sistema suporta, incluindo os que estão em espera e os que estão sendo atendidos. • Infinita: não ocorrerá problemas de espera; • Finita: caso o sistema esteja cheio, não pode entrar nenhum cliente antes que outro saia. Importante! A taxa de chegada deve ser menor que a taxa de serviço; caso contrário, o sistema entrará em colapso! (λ < μ) . Disciplina de atendimento • FIFO (First In, First Out): o primeiro que entra é o primeiro a sair (ex.: filas em um banco). • LIFO (Last in, First Out): último cliente a chegar é o primeiro a ser atendido (ex.: Torre de Hanoi). • SIRO (Service In Random Order): atendimento aleatório. • PRI (Prioritárias): filas com prioridade, onde é atribuída uma prioridade a cada cliente. Estrutura de canais únicos Canal único; fase única. Canal único; fases múltiplas. Estrutura de canais múltiplos múltiplos canais; fase única. Modelos de canal único e fase única A seguir, temos os dados do problema: Taxa de chegada, λ = 24 por hora e taxa de serviço, μ= 30 usuários por hora. Taxa de utilização “DS for Windows”: < http://wps.prenhall.com/bp_weiss_software_1/1/358/91661.cw/index.html> REFERÊNCIAS LACHTERMACHER, G. Pesquisa operacional na tomada de decisão. 4. ed. São Paulo: Pearson Prentice Hall, 2009. MOREIRA, Daniel A. Administração da produção e operações. São Paulo: Pioneira Thomson Learning, 2004. 619 p. MOREIRA, D. A. Pesquisa operacional: curso introdutório. São Paulo, 2007; MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: Cultura Acadêmica, 2011. TAHA, H. A. Pesquisa operacional. 8. ed. São Paulo: Pearson, 2008. FOGLIATTI, M. C. e Mattos, N. M. C. Teoria de filas. Rio de Janeiro, 2007; COSTA, L. C. Teoria das filas. 2017. Disponível em: <http://www.deinf.ufma.br/~mario/grad/filas/TeoriaFilas_Cajado.pdf>. Acesso em: 07 mar. 2018. Unidade 7 PROBLEMAS DE ROTA MAIS CURTA Professora Marina Vargas Objetivos • Entender como representar e lidar com rotas; • Saber fazer o cálculo da rota mais curta; • Saber fazer o cálculo da entrega mais rápida. Redes Uma rede é um conjunto de pontos, chamados nós, e um conjunto de curvas, chamadas arcos (ou ramos, ou ligações), que conectam um certo número de pares de nós. Em geral, designam-se os nós por letras maiúsculas e os ramos pelos nós que eles conectam. Correntes, trilhas e circuitos • CORRENTE = sequência de arcos tal que cada arco apresenta exatamente um vértice em comum com o arco anterior; • TRILHA = sequência de arcos tal que o nó terminal de cada arco é idêntico ao nó inicial do arco seguinte. • CIRCUITO = trilha finita em que o nó terminal coincide com o nó inicial. Ex.: Correntes, trilhas e circuitos 4 1 2 3 • Nós = { 1, 2, 3, 4}; • Arcos = {(1,2), (2,3), (3,4), (4,3), (4,1)}; • Ex. de corrente = (1,2) - (2,3) - (4,3); • Ex. de trilha = (1,2) – (2,3) – (3,4); • Ex. de circuito = (1,2) – (2,3) – (3,4) – (4,1). O problema de menor caminho representa um caso especial de problemas de rede, em que os arcos significam a distância entre dois pontos (nós). Quando desejamos achar a rota que une esses dois pontos com a menor distância, entre as possíveis, temos um problema do tipo menor caminho (LACHTERMACHER, 2009). Problema de rota mais curta Ex.: As letras envoltas em círculos representam os nós, e as linhas com números representam a distância entre esses nós. Exemplo de uma rede com nós, arcos e distâncias. Algoritmo de Dijkstra Passo 1: Faça uma marca negativa em todos os nós e coloque sua distância como infinito. Passo 2: Troque a marca da origem, ponto A, para a positiva e sua distância igual a zero. Algoritmo de DijkstraAlgoritmo de Dijkstra Passo 3: Atualize as distâncias entre o ponto A e todos os seus adjacentes (diretamente ligados ao ponto A). Passo 4: Escolha o nó com menor valor ainda com sinal de menos. Como C e I empatam, você pode escolher qualquer um deles. Escolheremos C. Faça o sinal de C ficar positivo, o que significa que a distância até ele já está definida. Assinale o caminho que foi usado para ter esse valor. Algoritmo de Dijkstra Algoritmo de Dijkstra Passo 5: Atualize as distâncias entre o nó com menor valor, no caso o ponto 3, e todos os seus adjacentes, se for para obter um valor menor; caso contrário, mantenha o valor anterior. D e F mudaram, B não, pois tinha valor 5 vindo direto de A. Algoritmo de Dijkstra Passo 6: Volte ao passo 4 até que todos os nós estejam com marca positiva. Atualize de I aos seus adjacentes e volte ao passo 4. Algoritmo de Dijkstra • Escolhemos B agora. • Escolhemos E. Algoritmo de Dijkstra • Continuamos o processo até que todos os nós estejam com marcas positivas. Caminho mais curto = A-C-F-H REFERÊNCIAS LACHTERMACHER, G. Pesquisa operacional na tomada de decisão. 4. ed. São Paulo: Pearson Prentice Hall, 2009. MOREIRA, D. A. Pesquisa operacional: curso introdutório. São Paulo, 2007; HILLIER, F.S.; LIEBERMAN, G.G. Introdução à pesquisa operacional. 8. ed. Porto Alegre: AMGH, 2010. SILVA, E. M. da; SILVA, E. M. da; GONÇALVES, V.; MUROLO, A. C. Pesquisa operacional: programação linear e simulação. 3. ed. São Paulo: Atlas, 2009. FLEURY, P. F., ÁVILA, M. G., WANKE, P. Em busca da eficiência no transporte terceirizado: estrutura de custos, parcerias e eliminação de desperdícios, 1997. Disponível em: <http://www.scielo.br/pdf/gp/v4n2/a09v4n2.pdf>. Acesso em: 07 mar. 2018. Unidade 8 PROBLEMAS DE LOCALIZAÇÃO Profa. Marina Vargas • Entender quais são os principais fatores que influenciam a localização de fábricas, depósitos e locais de vendas; • Verificar como encontrar uma região favorável; • Escolher, dentre vários pontos disponíveis, aquele que melhor se adéqua aos seus objetivos. Objetivos: Logística Serviço ao cliente Marketing = Combinação de quatro P’s (produto, preço, promoção e ponto de venda), em que o ponto de venda representa melhor a distribuição física. E é sobre a localização do ponto de venda, dos depósitos que o abastecem ou das fábricas que fornecem os produtos que iremos tratar. As instalações podem ser as seguintes: • Plantas (fábricas). • Armazéns. • Centros de distribuição. • Centros de serviço. • Operações de venda no varejo. Técnicas de análise de localização Três técnicas de localização: a classificação por fator de localização, o centro de gravidade e carga-distância. Classificação por fator de localização: • Passo 1: Identifique fatores importantes que influenciam a localização. • Passo 2: Atribua peso aos fatores (0.00 – 1.00) • Passo 3: Subjetivamente, pontue os fatores de cada site (0 – 100) • Passo 4: Ache a soma (pesos x pontuações) Fator de localização na prática: Fatores de localização e respectivos pesos e notas de cada fator. Técnicas de análise de localização Centro de gravidade: Como fazer: • Passo 1: Localizar a instalação no centro geográfico da área geográfica para minimizar os gastos com transportes. • Passo 2: Baseado em peso e distância do transporte. • Passo 3: Use um mapa com escalas da área. • Passo 4: Identifique coordenadas e pesos do transporte para cada localização. Centro de gravidade na prática (média ponderada): Centro de gravidade na prática (média ponderada): Achamos que o lugar ideal para se instalar a atividade é o ponto de coordenadas (238,444). Mas na maioria dos casos este local exato não está disponível, desta forma iremos tentar encontrar locais disponíveis próximos a este local ideal. Técnicas de análise de localização Carga-distância • Passo 1: Calcule Carga x Distância para cada local. • Passo 2: Escolha o local com mais baixa Carga x Distância. • Passo 3: Distância pode ser real ou linha reta. LD = valor de carga x distância. li = a carga, expressa como um peso, número de viagens ou unidades sendo transportadas do local proposto até a localização i. di= a distância entre o local proposto e a localização i. Carga-distância na prática: Carga-distância na prática: REFERÊNCIAS LACHTERMACHER, G. Pesquisa operacional na tomada de decisão. 4. ed. São Paulo: Pearson Prentice Hall, 2009. MOREIRA, Daniel A. Administração da produção e operações. São Paulo: Pioneira Thomson Learning, 2004. 619 p. MOREIRA, D. A. Pesquisa operacional: curso introdutório. São Paulo, 2007; MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: Cultura Acadêmica, 2011. TAHA, H. A. Pesquisa operacional. 8. ed. São Paulo: Pearson, 2008. REID, R. Dan; SANDERS, Nada R. Gestão de operações. Tradução Dalton Conde de Alencar. Rio de Janeiro: LTC Editora, 2005 Unidade 9 SIMULAÇÃO MONTE CARLO Profa. Marina Vargas • Saber que a incerteza e a grande capacidade de dados exigem a adoção de simulações para conhecer as melhores alternativas; • Entender o método de simulação de Monte Carlo; • Saber como aplicar o método de simulação de Monte Carlo. Objetivos: O nome Monte Carlo (HAMMERSELEY,1964) surgiu durante o projeto Manhattan, na Segunda Guerra Mundial (década de 1940). No projeto de construção da bomba atômica, Stanisław Ulam, von Neumann e Fermi consideraram a possibilidade de utilizar o método, que envolvia a simulação direta de problemas de natureza probabilística relacionados com o coeficiente de difusão do nêutron em certos materiais. Origem Fonte: <http://mestra.me/E2hNI> https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial https://pt.wikipedia.org/wiki/Stanis%C5%82aw_Ulam https://pt.wikipedia.org/wiki/Stanis%C5%82aw_Ulam https://pt.wikipedia.org/wiki/Stanis%C5%82aw_Ulam https://pt.wikipedia.org/wiki/Von_Neumann https://pt.wikipedia.org/wiki/Von_Neumann https://pt.wikipedia.org/wiki/Von_Neumann https://pt.wikipedia.org/wiki/Fermi Origem Contudo, há registros de que um artigo escrito por Lord Kelvin, dezenas de anos antes, já utilizava técnicas de Monte Carlo em uma discussão das equações de Boltzmann. Hoje o método de simulação Monte Carlo é utilizado para desenvolver um panorama paramétrico confiável dos resultados de um processo e é vital em setores como finanças, fabricação, extração de gás e óleo, farmácia, dentre outros. Fonte: ROSAS, 2009. Exemplificação Considere as duas tabelas que representam distribuições de probabilidade. Frequência d um evento X P(X=x) 1 0,33 2 0,67 Severidade do Evento Y P(Y=y) R$ 100 0,25 R$ 200 0,50 R$ 300 0,25 O espaço amostral das despesas agregadas resultante da interação entre as duas distribuições acima é: Severidade do Evento S P(S=s) R$ 100 0,0833 R$ 200 0,2083 R$ 300 0,2500 R$ 400 0,2500 R$ 500 0,1667 R$ 600 0,0417 Fonte: <http://mestra.me/E2hNI> Exemplificação Gráfico de frequências: Distribuição da despesa agregada. Gerado no Microsoft® Excel . Severidade do Evento S P(S=s) R$ 100 0,0833 R$ 200 0,2083 R$ 300 0,2500 R$ 400 0,2500 R$ 500 0,1667 R$ 600 0,0417 Exemplificação Fonte: <http://mestra.me/E2hNI> Mas e se ao invés de ser dois registros de frequência fossem 10? A árvore de decisão aumentaria exponencialmente e só seria possível resolvê-la com rotinas computacionais e ajuda de softwares ou programação, para calcular seu espaço amostral final.Características Essenciais A exigência básica do método é que o sistema físico ou matemático seja modelado em termos de funções de distribuição de probabilidade (FDP), que podem ser discretas ou contínuas: Bernoulli, Binomial, Chi- Quadrado, Gamma, Erlang, Normal, etc. Fonte: <http://mestra.me/OmWZh> Método Monte Carlo aplicado a aproximação do valor de π Uma vez conhecidas essas distribuições, a Simulação de Monte Carlo pode proceder fazendo as amostragens aleatórias a partir das mesmas. Este processo é repetido inúmeras vezes (milhares). Na prática, diante de um problema envolvendo incertezas, realizar uma Simulação com Monte Carlo para aproximar sua solução consiste em quatro passos padrões: A) Modelar o problema definindo uma FDP para representar o comportamento de cada uma das suas incertezas; B) Gerar valores pseudo-aleatórios aderentes à FDP de cada incerteza do problema; C) Substituir as incertezas por valores para calcular o resultado. Repetir os passos B e C até se obter uma amostra com o tamanho desejado de realizações; D) Obter uma estimativa para a solução do problema. Passo a Passo Um caixa eletrônico instalado em um shopping center atende clientes para as operações de saque, depósito e pagamentos de contas. Sempre que houver um cliente utilizando o caixa eletrônico, o próximo cliente fica na fila, aguardando a desocupação do terminal. Mas por outro lado, há o fator sorte, caso o cliente chegue ao terminal e este estiver desocupado. Para fins de análise do sistema de atendimento, foram coletados os tempos do intervalo de chegada de clientes ao terminal e os tempos de atendimento, que estão resumidos nos histogramas abaixo. (SHIBUYA, 2015) Simulação em Logística - exemplificação Simule o sistema de caixa eletrônico, prevendo o atendimento de 10 clientes e para isso, utilize os números aleatórios dados abaixo: Simulação em Logística - exemplificação Tabela: Tratamento de dados para intervalos de chegada. Simulação em Logística - exemplificação Tabela: Tratamento de dados para o tempo de atendimento. Simulação em Logística - exemplificação NF = 0,69 clientes, número médio de clientes em fila para a quantidade de atendimentos realizados (no caso, 10 atendimentos). TF = 2,40 minutos, tempo médio que os clientes permanecem em fila aguardando atendimento, para a quantidade de atendimentos realizados (no caso, 10 atendimentos). NS= 1,54 clientes, número médio de clientes que permanecem no sistema ao longo do tempo de simulação (no caso, 10 atendimentos). TS = 5,40 minutos, tempo médio que o cliente fica no sistema Simulação em Logística - exemplificação REFERÊNCIAS LACHTERMACHER, G. Pesquisa operacional na tomada de decisão. 4. ed. São Paulo: Pearson Prentice Hall, 2009. MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: Cultura Acadêmica, 2011. METROPOLIS, N., ULAM, S. The Monte Carlo Method. Journal of the American Statistical Association. 44 (247): 335–341. 1949. ROSAS, A. Método Monte-Carlo. Acessado em: 25 de fevereiro de 2018. Disponível em: <file:///C:/Users/varga/Downloads/Pesquisa%20Operacional/aulas%2008%20e %2009/aula07-montecarlo.pdf> SHIBUYA, M. INTRODUÇÃO À SIMULAÇÃO DE SISTEMAS COM O SOFTWARE ARENA®. Acessado em: 25 de fevereiro de 2018. Disponível em: <http://mestra.me/7dDUh>
Compartilhar