AULA 6

Prévia do material em texto

AULA 6
O PROBLEMA DO TRANSPORTE
Um problema bastante comum que muitas vezes pode ser modelado como um problema de programação linear é o problema de transporte. Ele envolve o transporte de alguma carga de diversas fontes a diversos pontos de destino. Dados o custo da distribuição entre cada fonte e destino, as produções das fontes e as capacidades dos destinos, desta forma, podem minimizar o custo total do transporte.
Segundo Campos (1998), é problema de cobertura de arcos
Carteiro Chinês _ Consiste em determinar uma rota de custo mínimo que passe por todos os arcos pelo menos uma vez. É um problema de cobertura de arcos.
Carteiro Chinês capacitado - É uma generalização do carteiro chinês, onde há restrição de capacidade dos veículos.
Segundo Campos (1998), são problemas de cobertura de nós
Caixeiro Viajante - Consiste em determinar uma rota de custo mínimo que visite todos os nós uma única vez. Pode ser classificado como um problema de cobertura de nós.
Multiplos Caixeiros Viajantes - É uma generalização do caixeiro viajante na qual se considera mais de um caixeiro viajante, que iniciam e terminam suas rotas em um local comum. Não há restrições sobre o número de nós que cada um pode visitar, exceto que cada caixeiro visite no mínimo um nó.
Roteirização com um único depósito e vários veículos - É o problema clássico de roteirização de veículos (PRV). É uma generalização do problema do caixeiro viajante, onde a frota de veículos parte de um depósito central e atende todos os nós, com o objetivo de minimizar a distância total percorrida pela frota.
Os problemas de roteamento de veículos, de uma forma geral, consistem em determinar percursos ótimos para uma frota de veículos estacionada em um ou mais domicílios de forma a atender um conjunto de clientes geograficamente dispersos.
Um exemplo clássico aparece nos problemas de distribuição/coleta de mercadorias, onde cada cliente possui uma demanda específica e os veículos apresentam capacidade limitada.
Busca-se a configuração das rotas dos veículos de modo que cada cliente seja servido por um e somente um veículo, minimizando-se o custo/comprimento do percurso total.
Dado um conjunto de cidades e conhecidas as distâncias entre cada uma delas, pretende-se determinar o circuito de menor comprimento que passa por todas as cidades, exatamente uma vez, e que termina na cidade de onde partiu.
Problema do caixeiro viajante
A estrutura matemática do problema do caixeiro viajante é um grafo em que cada cidade é um nó e as linhas que unem todos os nós são denominadas por arcos. Associada a cada linha está uma distância ou custo.
 Uma viagem, que passe por todas as cidades uma única vez, corresponde a qualquer subconjunto de linhas do grafo e é designado por circuito Hamiltoniano, na teoria de grafos. O comprimento de um circuito é a soma do comprimento das linhas que fazem parte da viagem.
Grafo da estrutura matemática do problema do caixeiro viajante
Circuito ótimo
A - D - E - C - B - A
Comprimento do circuito
2 + 4 + 5 + 6 + 3 = 20
Subproblema de problemas de distribuição e planejamento de rotas de veículos
 Ex: determinar, para um dado conjunto de veículos, qual o percurso que cada veículo deve efetuar, de modo a, no seu conjunto, servir a todos os clientes.
Aula 7
Tomada de decisão I
POR QUE A TOMADA DE DECISÕES É UM DESAFIO CADA VEZ MAIOR?
Sobrecarga de informações;
Um ritmo de mudanças aceleradíssimo;
Incerteza crescente;
Poucos precedentes históricos;
Decisões frequentes;
Decisões mais importantes;
Metas conflitantes;
Mais oportunidades para falhas de comunicação;
Menos oportunidades de corrigir erros;
Apostas mais altas.
Fatores que influenciam os resultados
As maiores chances de se obter um bom resultado, a partir de uma decisão, é por meio de um bom processo de decisão.
Para se compreender melhor o dilema do processo versus resultado, deve-se analisar de onde vêm bons resultados.
As quatro etapas do processo de tomada de decisão são:
Quadro > Os quadros determinam o ponto de vista a partir do qual quem toma decisões observa a questão e define parâmetros para os aspectos da situação que considera importante e também para o que não considera importante. Eles determinam de modo preliminar quais critérios fazem preferir uma opção em lugar de outra.
Reunião inteligente > Quem reúne inteligências deve buscar os fatos e as opções já conhecidas e produzir avaliações razoáveis dos fatos “desconhecidos”, para permitir a tomada de decisão face à incerteza. É importante evitar as armadilhas do excesso de confiança nas suas crenças atuais e a tendência de só buscar informações que confirmem suas crenças.
Obtenção de conclusões > Quadros sólidos e boa inteligência não são garantia de uma decisão sábia. As pessoas não podem tomar boas decisões consistentemente utilizando apenas o julgamento baseado na experiência, mesmo tendo dados excelentes à sua disposição. Uma abordagem sistemática conduzirá a escolhas mais precisas, como geralmente acontece de modo bem mais eficiente que horas gastas com pensamento desorganizado. Isso é particularmente verdadeiro em configurações de grupos.
Aprendizado com experiência > Quem toma decisões pode aprimorar continuamente suas habilidades somente pelo aprendizado sistemático com os resultados de decisões anteriores. Além disso, se o aprendizado começa quando uma decisão é implementada da primeira vez, podem ser feitos os primeiros aprimoramentos à decisão ou plano de implementação, o que pode significar a diferença entre sucesso e fracasso.
O pensamento para se tomar uma decisão pode ser:
PENSAMENTO LINEAR > Uma causa > Um problema > Uma solução. 
PENSAMENTO SISTÊMICO
AULA 8 
TOMADA DE DECISÃO II
Ao buscar fatos em reunião de inteligência, observe se as informações possuem os seguintes quesitos:
INFORMAÇÃO COM > 
QUALIDADE/ADEQUAÇÃO/OPORTUNIDADE/CLAREZA/RELATIVIDADE/CUSTO
Não há vento favorável para aquele que não sabe aonde vai”.
Sêneca 
 
“A maior dificuldade do mundo não é fazer com que as pessoas aceitem novas ideias, mas sim fazê-las esquecer as velhas”. 
John Maynard Keynes 
 
“Dai-me a coragem para mudar as coisas que podem ser mudadas, a serenidade para aceitar as coisas que não podem ser mudadas e, principalmente, a sabedoria para distinguir umas das outras”. 
Santo Inácio de Loyola
 
“Não existe nenhum caminho sem riscos para o futuro; devemos escolher que série de riscos desejamos correr”. 
Theobald
 
“Quando os ventos da mudança chegarem, não construa abrigos, construa cata-ventos”. 
Claus Möller
UMA DEFINIÇÃO DE INSANIDADE
“CONTINUAR FAZENDO O QUE SEMPRE FIZEMOS E ESPERAR RESULTADOS DIFERENTES”
As frases que representam insanidade e previsões e decisões associadas são pensamentos que fizeram com que grandes empresas perdessem grandes oportunidades. As pessoas mudam o tempo todo, o mercado é movimentado por pessoas, logo podemos afirmar que o mercado muda o tempo todo.
AULA 9
PROBLEMA DO FLUXO MAXIMO
O que é o problema de encontrar fluxo máximo?
 
Definição: dada uma rede, com um nó de entrada e um nó de saída, com capacidades associadas a cada ramo, pretende-se saber qual é o fluxo máximo, de certo bem, que se pode enviar da entrada para a saída.
Para Cormen (2009),
 
Algoritmo de fluxo máximo
 
1. Injetar um fluxo nulo no nó de entrada;
2. Capacidades iniciais dos ramos = capacidade total dos ramos;
3. Determinar um caminho não saturado (capacidade 6 = 0) entre o nó de entrada e o nó de 
    saída; se não existir, foi encontrada a SOLUÇÃO ÓTIMA;
4. Somar ao fluxo de entrada um fluxo igual à capacidade do caminho selecionado;
5. Alterar as capacidades dos ramos do caminho selecionado, diminuindo-lhes o fluxo injetado;
6. Voltar ao ponto 3.
Cormen (2009) explica como resolver o problema:
Precisamos de duas definições básicas para entender como resolver fluxo em redes:Poderemos ver em Cormen (2009), a sugestão para o seguinte algoritmo:
 
    Inicie com nenhum fluxo em todas as arestas e aumente o fluxo total na rede enquanto há 
    um aumento no caminho desde o source até o sink - um caminho de aumento na 
    rede residual. 
    
    O algoritmo (conhecido como o método Ford-Fulkerson) sempre termina: devido às 
    capacidades e fluxos inteiros não negativos, a cada passo obtemos um novo fluxo que está 
    mais próximo do máximo.
O algoritmo Ford-Fulkerson descrito obtém o resultado correto, não importa como resolvermos o subproblema, que é encontrar um caminho de aumento.
No entanto, a cada novo caminho, podemos aumentar o fluxo total muito pouco. Daí o número de iterações do algoritmo poder ser muito grande se nos descuidarmos da escolha que no caminho de aumento o algoritmo deve usar.
Problemas Relacionados
Como reconhecer problemas de fluxo máximo? 
Muitas vezes, eles são difíceis de detectar. Geralmente, precisamos prestar muita atenção nas restrições quando achamos que temos uma solução baseada em fluxo máximo - que deve, pelo menos, sugerir uma solução O(N³). Se o número de vértices é grande, um outro algoritmo (como a programação dinâmica ou o guloso), pode ser mais adequado.
AULA 10
PROBLEMAS DE CONGESTIONAMENTOS
TEORIA DAS FILAS
SEGUNDO TANENBAUM 2002 –
A teoria de filas é uma das mais interessantes aplicações da teoria da probabilidade, sendo de grande importância para a análise e dimensionamento de sistemas de comunicações e também em sistemas ligados à ciência da computação. 
É possível inclusive se aplicar em um sistema de recebimento e distribuição de produtos, possibilitando a otimização do sistema de transporte.
Dando continuidade às concepções de Tanenbaum (2002), o sistema de filas aparece em diversas situações do nosso cotidiano, tais como: Filas de bancos, congestionamentos, supermercados etc
Para Tenenbaum :
Fila de pacotes aguardando por transmissão;
fila de pacotes aguardando por roteamento/comutação;
fila de pacotes recebidos na placa de rede de um terminal;
fila de chamadas telefônicas aguardando por linha em um PABX;
fila de amostras de voz recebidas em um telefone IP;
fila de símbolos a serem codificados em um transmissor de TV Digital;
fila de pedidos a serem separados dentro de uma Central de distribuição;
O que Sistema de filas ?
Em Tanenbaum (2002), pode ser visto que, um sistema de filas (Q – Queuing System) é um sistema composto pelos itens descritos abaixo : 
Uma ou mais filas (W – Waiting Line) onde são armazenados os elementos que aguardam por atendimento.
Um ou mais servidores (S – Servers) que atendem os elementos.
Um processo de chegada, que define como os elementos chegam ao sistema.
Um processo de atendimento, que define como os elementos são atendidos pelo sistema.
O tamanho da população que gera os elementos.
Caminhões aguardando para carregar ou descarregar.
Seja o caso de uma Central de Distribuição, em que o “conferente da plataforma” leva em média 40min para carregar ou descarregar um caminhão, e que o número médio de caminhões que chegam à Central é de 20 caminhões/dia e a Central fica em operação 10h por dia.
Solução: Utilização da facilidade 
P = E ( n ) . E ( T2 ) = ( 40 . 60 ) : 60 = 13,33
 Vamos refletir quanto ao resultado. Se a Central funciona 10h por dia e, o tempo necessário para atender o funcionamento descrito é de 13,33h, podemos concluir que teremos a formação de uma fila de espera, sem possibilidade de atendimento de parte dos caminhões. Neste caso, deve ser pensado em como poderemos criar uma janela de horário que permita atender à necessidade dentro do tempo disponível.
Na logística do transporte, podemos utilizar as técnicas da teoria das filas para se evitar o congestionamento dentro de uma central de distribuição. Utilizando - se da técnica de janela de horários, que determina o horário para chegada e horário para partida dos veículos envolvidos nas tarefas, pode ser ordenado entrada e saída sem que se forme o congestionamento.
Notação de Kendall e Notação Expandida para Andrade (1998)
A notação de Kendall (David Kendall) foi desenvolvida em 1951 para descrever o comportamento de um sistema de fila em uma única frase:
X		Disciplina de serviço
S		Tamanho da População
K		Numero total de elementos no sistema
J		Número de elementos na fila
M		Numero de servidores
B		processos de atendimento
A		processo de chegada
Andrade (1998) também diz que é comum vermos sistemas definidos com a notação simplificada:
A/B/m
Andrade (1998) também diz que é comum vermos sistemas definidos com a notação simplificada:
A/B/m/ ∞ / ∞   /FIFO
O Processo de Chegada (A) descreve o processo que modela as chegadas de elementos ao sistema.
Também é possível encontrar em Andrade (1998) que o Processo de Atendimento (B) descreve o processo que modela o atendimento de elementos no sistema.
Segundo Andrade (1998), Tamanho da População (S) descreve o tamanho da população que gera elementos para o sistema. Tipicamente é considerada como infinito. Ex.: Ligações chegando, clientes na lanchonete.
Disciplina de Serviço (X)
Os elementos que aguardam por serviço na fila podem ser selecionados de acordo com uma regra chamada disciplina de serviço. Dentre as principais disciplinas estão:
FCFS – First Come First Served (**FIFO) > Primeiro elemento que chega é o primeiro a ser atendido.
LCFS – Last Come First Served > Último elemento que chega é o primeiro a ser atendido.
 SIRO – Service In a Random Order > Elementos são atendidos em ordem aleatória.
Processo de Nascimento e Morte e Diagrama de Estado.
É uma classe especial de processos estocásticos em que são permitidas somente transições aos estados vizinhos. As probabilidades de transição são determinadas em função do estado atual e das médias das distribuições dos processos de chegada e de atendimento.
É Assim, para um sistema em equilíbrio tem-se:
P = {1 Nascimento} = yK
P = {1 Nascimento} =gZ
Onde : 		yK (Média de chegada de elementos no estado K )
		gZ (Média de saída de elementos no estado K. )
Para cada novo elemento que chega, se for possível ele será atendido, caso não seja possível, ele entra na fila (é armazenado), acontece o nascimento de um estado. Isso acontecerá enquanto o atendimento estiver sendo feito a outro elemento, quando é finalizado o atendimento de um elemento (ele sai do sistema de filas) nesse momento acontece o que se chama de “morte” de um estado.