Baixe o app para aproveitar ainda mais
Prévia do material em texto
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES Aula de revisão para a av1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Aula REV1: REVISÃO PARA AV1 Nesta aula vamos rever os tópicos das aulas 1, 2, 3, 4 e 5. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 REVISÃO PARA AV1 Nesta aula vamos rever o tópico da aula 1 - Fundamentos de PO. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Fundamentos em Pesquisa Operacional A Pesquisa Operacional (PO) consiste no estudo de métodos matemáticos, usualmente implementados por programas de computador, que podem ser utilizados para resolver problemas gerenciais relacionados à tomada de decisão e controle de sistemas. É vista como uma metodologia para estruturar processos por meio de construção de modelos. Coletânea de técnicas quantitativas de otimização. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 O termo “Pesquisa” O termo “pesquisa” significa que a PO faz uso de uma abordagem que lembra a forma de como as pesquisas são conduzidas em diversas áreas do conhecimento Formulação do Problema, Coleta de dados relevantes Modelagem Validação…etc. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 A origem da Pesquisa Operacional Atribuída ao serviço militar na 2a Guerra Mundial; os cientistas começaram a estudar de forma sistemática e racional os processos envolvidos na realização de uma atividade produtiva. A difusão da Pesquisa Operacional “Boom” industrial; No começo dos anos 50, profissionais introduziram o uso da PO em uma variedade de organizações (indústrias, governo, etc.). OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 A difusão da Pesquisa Operacional Dois fatores foram responsáveis pelo rápido crescimento da PO: Progresso substancial no desenvolvimento de técnicas, como; Revolução “computacional”. Aplicações da Pesquisa Operacional Manufatura; Sistemas de Transporte e Distribuição; Instituições de ensino; Hospitais; Construção; Finanças; Agricultura; Dentre Outros. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Modelo Matemático (MM) Usa notação simbólica e equações matemáticas para representar os sistemas; A PO congrega diversas das mais consagradas técnicas de MM; Os principais modelos de PO são denominados de Programação Matemática. Etapas da Modelagem Formulação do problema Coleta de dados Construção do modelo matemático Desenvolvimento de estratégias para determinar soluções a partir do modelo proposto Validação do modelo Implementação OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 REVISÃO PARA AV1 Nesta aula vamos rever o tópico da aula 2 – Modelos em PO. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 CONSTRUÇÃO DO MODELO Variáveis de decisão: É o que deve ser decidido no plano de produção ou, plano de transporte de carga, isto é, quais as quantidades periódicas que devem ser produzidas ou transportadas de cada produto: P1, P2, ..., Pn. Exemplo OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 MODELAGEM FUNÇÃO-OBJETIVO é uma função matemática que representa o principal objetivo do tomador de decisão. Ela é de dois tipos: ou de minimização (de custos, de erros, chance de perdas, desvio do objetivo, etc.) ou de maximização (de lucro, receita, utilidade, bem-estar, riqueza, chance de sobrevivência, etc.) Exemplo: minimizar os custos de transporte relativos à distribuição de refrigerantes. Exemplo OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 MODELAGEM RESTRIÇÕES são regras que dizem o que podemos e o que não podemos fazer e/ou quais são as limitações dos recursos ou das atividades que estão associadas ao modelo Exemplo: o número total de caminhões despachados pela manhã é menor ou igual ao número de motoristas que a empresa tem à disposição no primeiro turno. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 EXEMPLO: Certa empresa fabrica dois produtos: P1 e P2. O lucro unitário do produto P1 é de R$ 1.000 e o lucro unitário de P2 é de R$ 1.800. A empresa precisa de 20h para fabricar uma unidade de P1 e de 30h para fabricar uma unidade de P2. O tempo anual de produção disponível para isso é de 1.200h. A demanda esperada para cada produto é de 40 unidades anuais para P1 e 30 unidades anuais para P2. Qual é o plano de produção para que a empresa maximize seu lucro nesses itens? OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 CONSTRUÇÃO DO MODELO Variáveis de decisão: O que deve ser decidido é o plano de produção, isto é, quais as quantidades anuais que devem ser produzidas de P1 e P2 x1 quantidade anual a produzir de P1 x2 quantidade anual a produzir de P2 Retornar OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 CONSTRUÇÃO DO MODELO Função Objetivo: O objetivo é maximizar o lucro, que pode ser calculado: Lucro devido a P1: 1.000x1 (lucro por unidade de P1 “vezes” quantidade produzida de P1) Lucro devido a P2: 1.800x2 (lucro por unidade de P2 “vezes” quantidade produzida) Lucro total: z = 1.000x1 + 1.800x2 Objetivo: Max z = 1.000x1 + 1.800x2 Retornar OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 CONSTRUÇÃO DO MODELO Restrições - Disponibilidade de horas para a produção: 1.200 horas. Horas ocupadas com P1: 20x1 (uso por unidade “vezes” quantidade produzida) Horas ocupadas com P2: 30x2 (uso por unidade “vezes” quantidade produzida) Total de horas ocupadas na produção: 20x1 + 30x2 Disponibilidade: 1.200 horas Restrição descritiva da situação: 20x1 + 30x2 ≤ 1.200 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 CONSTRUÇÃO DO MODELO Restrições: Disponibilidade de horas para os produtos P1 e P2 (demanda) Disponibilidade para P1: 40 unidades Quantidade a produzir de P1: x1 Restrição descritiva da situação: x1 ≤ 40 Disponibilidade para P2: 30 unidades Quantidade a produzir de P2: x2 Restrição descritiva da situação: x2 ≤ 30 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 MODELO Max z = 1000x1 + 1800x2 Sujeito a: 20x1 + 30x2 ≤1200 x1 ≤ 40 x2 ≤ 40 X1, x2 ≥ 0 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 REVISÃO PARA AV1 Nesta aula vamos rever o tópico da aula 3 – Grafos. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Uma aresta é dita incidente com os vértices que ela liga. Se uma aresta é incidente em um único vértice é chamado de laço. 2. Dois vértices são chamados de adjacentes se estão ligados pôr arestas. Um vértice é dito isolado, se não tem aresta incidindo sobre ele. Aqui podemos ver a incidência entre o vértice “V1” e o vértice “V2”. E o vértice “V3” como vértice isolado OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 3. Define-se grau de um vértice v V, denotado pôr gr (v) como sendo o número de arestas incidentes em v. Um grafo é dito regular de grau r se todos seus vértices possuem grau r. Grafo regular de grau 3 (r = 3) Ordem do grafo: V =4 A = 6 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 4. Se o grafo é regular de grau zero, é dito nulo. Um vértice de grau 1, é dito pendente. Grafo regular de grau zero (r = 0) Ordem do grafo: V = 4 A = 0 Vértices pendentes: (v4 e v5) Ordem do grafo: V = 5 A = 1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 5. Duas arestas que incidam sobre o mesmo vértice são ditas adjacentes. Se os dois vértices de incidência são os mesmos, as arestas são ditas paralelas. Vértices (v1e v4) possuem arestas paralelas; Ordem do grafo: V = 4 A = 5 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Vértices adjacentes: (V6,V2) (V6,V5) (V2,V3) (V2,V4) (V3,V5) (V4,V5) Vértice isolado: V1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Vértice de grau nulo: V4 Vértice Pendente: V2 pois gr (V2) = 1 Arestas adjacentes que incidem sobre: OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Um grafo é dito dirigido ou dígrafo se suas arestas possuem orientação. Em caso contrário diz-se que o grafo é não dirigido. Em um grafo dirigido as arestas são chamadas arcos. Antecessor de um vértice vi é todo vértice vj que seja extremidade inicial de uma arco que termina em vi. Sucessor de um vértice vi é todo vj que seja extremidade final de um arco que parte de vi. O grau de um vértice de um grafo orientado é a soma dos graus dos arcos que saem do vértice , isto é, o grau de emissão (de saída) e o grau de recepção (de entrada). OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Um grafo onde existe um número Wij associado a cada aresta é um grafo denominado valorado e o número Wij é chamado custo da aresta. Multígrafo é o grafo que contém arestas paralelas ou laços. Grafo simples é um grafo que não contém nenhum par de arestas paralelas ou laços. Grafo completo é um grafo simples que será completo quando existir uma aresta entre cada par de seus vértices. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 REVISÃO PARA AV1 Nesta aula vamos rever o tópico da aula 4 – Árvores Binárias. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – AULA 4 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – ÁRVORES BINÁRIAS * A busca nada mais é do que um percurso em uma árvore. O percurso em uma árvore visitando cada nó uma única vez gera uma sequência linear de nós. Assim, passa a ter sentido falar em sucessor e predecessor de um nó segundo um determinado percurso. Há três maneiras recursivas de se percorrer árvores. binárias: Percurso em pré-ordem Percurso em pós-ordem Percurso em ordem PERCURSOS EM ÁRVORES BINÁRIAS OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – AULA 4 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – ÁRVORES BINÁRIAS * Percurso em Pré-Ordem Neste caso a visita aos nós acontecem de cima para baixo da esquerda para a direita, Passando pelo nó raiz antes de visitar os nós a ela ligados. Algoritmo básico: Se árvore vazia fim Visitar o nó raiz Percorrer em pré-ordem a sub-árvore esquerda Percorrer em pré-ordem a sub-árvore direita PERCURSOS EM ÁRVORES BINÁRIAS OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – AULA 4 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – ÁRVORES BINÁRIAS * PERCURSOS EM ÁRVORES BINÁRIAS A – B – C – D – E – F – G – H - I Percurso em “Pré-Ordem” (Raiz – TRE – TRD) OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – AULA 4 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – ÁRVORES BINÁRIAS * PERCURSOS EM ÁRVORES BINÁRIAS Percurso em “Em Ordem” Neste caso a visita aos nós acontecem de baixo para cima da esquerda para a direita. Algoritmo básico: Se árvore vazia fim percorrer em ordem a sub-árvore esquerda visitar o nó raiz percorrer em ordem a sub-árvore direita OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – AULA 4 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – ÁRVORES BINÁRIAS * Percurso em “Em Ordem” (TRE – Raiz –TRD) C – B – A – E – F – D – H – G - I PERCURSOS EM ÁRVORES BINÁRIAS OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – AULA 4 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – ÁRVORES BINÁRIAS * PERCURSOS EM ÁRVORES BINÁRIAS Percurso em Pós-Ordem Neste caso a visita aos nós acontecem da esquerda para a direita de baixo para cima, visitando por último a raiz. Algoritmo básico: Se árvore vazia fim percorrer em pós-ordem a sub-árvore esquerda percorrer em pós-ordem a sub-árvore direita visitar o nó raiz OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – AULA 4 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – ÁRVORES BINÁRIAS * Percurso em “Pós-Ordem” (TRE –TRD – Raiz) PERCURSOS EM ÁRVORES BINÁRIAS C – B – F – E – H – I – G – D - A OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 REVISÃO PARA AV1 Nesta aula vamos rever o tópico da aula 5 – Algoritmos. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Algoritmo - DEFINIÇÃO Introdução Em Tanembaum (2003) podemos ver que Algoritmo é: Um processo sistemático para computar um resultado a partir de dados de entrada; Podemos ver também que estruturas de dados é: Um maneira de organizar dados e operar sobre eles; E que a junção de Algoritmos + estruturas de dados = programa E um programa é: A expressão em linguagem formal (inteligível por um computador) de um algoritmo. OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Para Cassettari (2003), Projeto de Estrutura de Dados é: Uma modelagem abstrata dos objetos a serem manipulados e das operações sobre eles. PROJETO DE ESTRUTURAS DE DADOS Um bom projeto leva a uma boa implementação Todas as ideias principais já foram estudadas A tradução do projeto em programa é quase mecânica PROJETO VERSUS IMPLEMENTAÇÃO OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Tanembaum (2003) diz que: Eficiência medida objetivamente depende de: Como o programador implementou o algoritmo/ED Características do computador usado para fazer experimentos: Velocidade da CPU Capacidade e velocidade de acesso à memória primária / secundária Etc Linguagem / Compilador / Sistema Operacional / etc ALGORITMOS E COMPLEXIDADE OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 Tanembaum (2003) diz que: Complexidade assintótica É a complexidade que envolve o tamanho dos dados de entrada e quanto esse tamanho poderá aumentar. ALGORITMOS E COMPLEXIDADE Organiza dados de mesma natureza (mesmo tamanho) em posições sucessivas da memória. ARRAY (VETORES, MATRIZES) OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 É necessário empregar algoritmos de busca caso: Se todas as posições estão preenchidas, inserção ocasiona overflow Realocar o array Reportar erro O overflow nada mais é do que utilizar mais espaço do que se tem. Poderíamos comparar com recebimento de produtos em maior escala do que a distribuição. Isso nos diz duas coisas: ou estamos comprando errado ou distribuindo errado. Para qualquer uma das alternativas devemos focar uma solução, seja ela proporcionada por quem for. ARRAYS – INSERÇÃO E REMOÇÃO DE ELEMENTOS OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REV1 OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES – REVISÃO PARA AV1 BONS ESTUDOS E ATÉ A PRÓXIMA
Compartilhar