REVISÃO PPT AV1 - OTIM DE SISTEMAS DE TRANS GST0311

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