Aula2

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Tecnologia e novas mídias
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTE
Aula 02
AULA 02
Construção de 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.
2
© Maksym Yemelyanov | Dreamstime.com
ID 9299306
2
Construção de Modelo
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.)
3
© Maksym Yemelyanov | Dreamstime.com
Tsunami: Ex Japão
Exemplo: minimizar os custos de transporte relativos à distribuição de refrigerantes.
3
Construção de Modelo
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.
4
© Maksym Yemelyanov | Dreamstime.com
Produção
Capacidade de maximizar
Capacidade homem/hora
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.
4
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. 
Construção de Modelo
© Maksym Yemelyanov | Dreamstime.com
5
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? 
Construção de Modelo
© Maksym Yemelyanov | Dreamstime.com
6
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
Construção de Modelo
© Maksym Yemelyanov | Dreamstime.com
7
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
Construção de Modelo
8
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
9
inequação
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
10
Logística
De acordo com o Council of Logistics Management, logística é o processo de planejamento, implementação e controle do fluxo eficiente e economicamente eficaz de matérias primas, estoque em processo, produtos acabados e informações relativas desde o ponto de origem até o ponto de consumo, 
com o propósito de atender às 
exigências dos clientes 
(CSCMP,2015).
11
© Madpixblue | Dreamstime.com
ID 45457548
11
O que é a logística?
Portanto, a gestão logística cuida da movimentação geral dos produtos, que se dá por três áreas principais: suprimento, apoio à produção e distribuição física. Para vencer a distância que separa os clientes dos fornecedores, a gestão logística 
enfrenta problemas 
referentes a tempo, espaço, 
custo, comunicação, 
movimentação e transporte de 
materiais e produtos (roteirização) 
12
© Madpixblue | Dreamstime.com
ID 45457548
Mediante ao anseio de organizações empresariais em minimizar os custos com transporte, pesquisas sobre métodos que venham a otimizar o processo de roteirização têm sido realizadas. O termo roteirização pode ser descrito como um processo de sequências de paradas determinadas que um veículo deva percorrer, com o objetivo de atender pontos dispersos geograficamente. Na literatura, o problema relacionado com roteirização mais conhecido é o clássico Problema do Caixeiro Viajante, que será visto mais adiante no capítulo 2.
A seguir, é feita uma introdução teórica sobre a Teoria dos Grafos, visto que a modelagem dos problemas de transporte baseia-se numa estrutura de Grafos, que possibilita sua associação com o mundo real.
12
Vídeo
13
Vídeo: Teoria dos grafos no filme A Origem;
10:09 11:04 O que é Logística
13
Teoria dos grafos
A Teoria dos Grafos é um ramo da matemática que remete ao estudo de objetos combinatórios denominados Grafos. Grafos são representados por pontos dispostos em posições arbitrárias denominados de nós, ou vértices, conectados por curvas chamadas de arestas. 
14
© Dreammasterphotographer | Dreamstime.com
ID 19042694
14
Teoria dos grafos
A Pesquisa Operacional utiliza os grafos em diversas situações, por exemplo em interligações entre “locais”. Os “locais” são chamados vértices (ou nós) e as ligações são chamadas arestas entre os “locais”. 
15
© Dreammasterphotographer | Dreamstime.com
ID 19042694
15
 
 Conjunto de vértices: V= {a,b,c,d,}.
 Arcos representam as ligações entre os vértices.
 Arcos são representados como pares ordenados.
 O par ordenado (a,b), por exemplo, representa o arco que liga os vértices a e b.
 Conjunto de todos os arcos: A={(a,b),(a,d),(d,b),(b,c),(d,c)}
a
b
d
c
Teoria dos grafos
16
Malha rodoviária ligando cidades de uma região.
Os vértices representam as cidades e os arcos representam as ligações entre as cidades.
Teoria dos grafos
 mas, se estradas forem de mão dupla, por exemplo, os arcos (a,b) e (b,a) são iguais.
Se ab, então (a,b)(b,a)
© Ttatty | Dreamstime.com © Stangot | Dreamstime.com
17
ID 45473866
ID 27985364
17
É possível definir grafo como um par G = (V,E) em que V é um conjunto finito e não vazio e E é uma relação (função) sobre os elementos de V.
Os elementos de V são chamados de vértices ( ou nós), e os pares ordenados (vi,vj), que representam as relações entre os elementos de V, são chamados de arestas ( linhas) do grafo.
Teoria dos grafos
18
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
V3
V3
V1
V2
Teoria dos grafos
19
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.
V1
V3
V2
V4
Grafo regular de grau 3 (r = 3) 
Ordem do grafo: V = 4 A = 6
Teoria dos grafos
20
4. Se o grafo é regular de grau zero, é dito nulo. Um vértice de grau 1, é dito pendente.
V1
V3
V2
V4
Grafo regular de grau zero (r = 0) 
Ordem do grafo: V = 4 A = 0
V1
V3
V2
V4
V5
Vértices pendentes: (v4 e v5)
Ordem do grafo: V = 5 A = 1
Teoria dos grafos
21
Nenhuma aresta incidente em nenhum dos vértices
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
V1
V3
V2
V4
Teoria dos grafos
22
aresta paralela / mão dupla
V1
V3
V2
V6
V5
V4
Vértices adjacentes: 
(V6,V2) (V6,V5) (V2,V3) (V2,V4) (V3,V5) (V4,V5)
Vértice isolado:
V1
Teoria dos grafos
23
Vértice de grau nulo: V4 Vértice Pendente: V2 pois gr (V2) = 1 
Arestas adjacentes que incidem sobre: V3
V1
V3
V5
V6
V2
V4
Teoria dos grafos
24
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).
Teoria dos grafos
25
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.
Teoria dos grafos
26
Atividade
Caracterize os grafos abaixo de acordo com os conceitos descritos em aula.
a)
b)
27
27
Desenvolvimento
a) 
28
Grafo simples, não orientado, incompleto.
Ordem do grafo: V = 6 A = 6
Vértice de grau nulo:V4 
Vértice Pendente V2 por gr (V2) =1 
Arestas adjacentes incidentes em V3 e V5.
Desenvolvimento
b) 
29
Multígrafo 
orientado 
completo
regular
Ordem do grafo: V = 6 A = 7
.
Tecnologia e novas mídias
VAMOS AOS PRÓXIMOS PASSOS?
AVANCE PARA FINALIZAR
A APRESENTAÇÃO.
AULA 02