Fichas
Cap. 5: Problemas de Transporte e Designação
Fichas del conjunto (24)
- 1—CAPÍTULO 5:
O PROBLEMA DE TRANSPORTE E DESIGNAÇÃO - 2PROBLEMA DE TRANSPORTETrata do envio de recursos de origens (como fábricas) para destinos (como depósitos)
- 3OBJETIVO DO PROBLEMA DE TRANSPORTEDeterminar a programação de expedição que minimize o custo total de expedição e satisfaça os limites de fornecimento e demanda
- 4DEFINIÇÃO DO PROBLEMA DE TRANSPORTERepresentado por uma rede, onde há:
origens + destinos = nós + arcos - 5BALANCEAMENTO DO PROBLEMA DE TRANSPORTEO algoritmo de transporte é baseada no equilíbrio entre a demanda total e o fornecimento total
- 6PROBLEMAS DE TRANSPORTE NÃO BALANCEADOSPara esses casos é possível adicionar uma ORIGEM FICTÍCIA ou um DESTINO FICTÍCIO, cujo valor é igual ao que falta para restaurar o equilíbrio
- 7CUSTO DE UMA ORIGEM OU DESTINO FICTÍCIOO custo unitário é zero, porque ele não existe. Caso queira um esgotamento dos recursos transportados entre as origens e destinos reais, pode-se adicionar um custo unitário muito alto, a fim de evitar alocações no elemento fictício
- 8MODELAGEM DE UM PROBLEMA DE TRANSPORTEPode ser modelado como um problema de programação linear, em que se quer minimizar o custo. Em FO, deve-se considerar todos os arcos entre os nós. Nas restrições, inclui-se apenas os arcos para cada possibilidade de transporte
- 9PROBLEMAS DE TRANSPORTE NÃO TRADICIONAISAlém do transporte de mercadorias, pode-se aplicar ainda nas áreas de controle de produção e estoques
- 10ALGORITMO PARA O PROBLEMA DE TRANSPORTEO algoritmo para esse tipo de problema segue as mesmas etapas do método simplex, porém de forma mais conveniente, a fim de facilitar o trabalho manual
- 11ETAPAS DO ALGORITMO PARA O PROBLEMA DE TRANSPORTE1. Determinar a solução inicial viável
2. Usar a condição de otimalidade do simplex (variável que entra na base) até satisfazê-la
3. Usar a condição de viabilidade do simplex (variável que sai da base). Volte a etapa 2. Faça esse processo até achar a solução - 12DETERMINAÇÃO DA SOLUÇÃO INICIALUsa-se três métodos:
1. Canto noroeste
2. Menor custo
3. Aproximação de Vogel - 13MÉTODO DO CANTO NOROESTEAloca-se a maior quantidade possível sempre na célula que está a noroeste, fazendo os ajustes nas linhas e colunas para respeitar os limites
- 14MÉTODO DO MENOR CUSTOAloca-se a maior quantidade prioritariamente nas células de menor custo, fazendo os ajustes nas linhas e colunas para respeitar os limites
- 15MÉTODO DE APROXIMAÇÃO DE VOGELCalcula-se a diferença entre os dois menores custos das linhas e colunas. Escolhe-se a linha ou coluna com a maior diferença e aloca-se a maior quantidade na célula de menor custo dessa linha/coluna. Repete-se até o total preenchimento
- 16OTIMIZAÇÃO E RESOLUÇÃO DO PROBLEMAApós encontrada a solução inicial, aplica-se o método Stepping Stone para encontrar a solução ótima
- 17MÉTODO STEPPING STONEMétodo usado para o teste de otimização, onde as variáveis entram e saem da base por meio de cálculos, partindo das células com valor zerado, desenhando um "polígono" com outras células não zeradas e refazendo as alocações com base em um critério
- 18PROBLEMA DE DESIGNAÇÃOA melhor pessoa para a tarefa
- 19OBJETIVO DO PROBLEMA DE DESIGNAÇÃODeterminar a designação de menor custo de trabalhadores a tarefas
- 20DEFINIÇÃO DO PROBLEMA DE DESIGNAÇÃOCaso especial de transporte:
trabalhadores = origens
tarefas = destinos
quantidade transportada = 1
Nessas condições, foi desenvolvido um um novo algoritmo: Método Húngaro - 21MÉTODO HÚNGAROAlgoritmo baseado no simplex aplicável aos problemas que apresentam as características da definição de designação
- 22ETAPAS DO ALGORITMO DO PROBLEMA DE DESIGNAÇÃO1. Subtraia o mínimo de cada linha de todas as entradas dessa linha
2. Na próxima matriz, repita a etapa um, só que nas colunas
3. Associe os elementos zerados para cada linha e coluna (uma linha para uma coluna) - 23EXTENSÃO DO ALGORITMO DO PROBLEMA DE DESIGNAÇÃO (caso não se alcance a solução ótima)2a. Trace o mínimo de linhas horizontais e verticais cobrindo todos os zeros
2b. Escolha o menor valor não traçado, subtraia das entradas não traçadas, some nas interseções e repita as traçadas
2c. Vai para a etapa 3 ou repita 2a e 2b - 24OBSERVAÇÕES DO PROBLEMA DE DESIGNAÇÃO1. Ele pode ser expresso como um problemas de PL ou de transporte
2. As alocações entre trabalhadores e tarefas é única
3. Pode-se adicionar elementos fictícios para equilibrar a matriz do problema
Información
- Descripción
- Flashcards para estudo da teoria de problemas de transporte e designação em pesquisa operacional.
- Creado por
- Natanael Lima
- Visitas
- 229
- Etiquetas
- Valoración