Transporte, Designação e Redes

Transporte, Designação e Redes

1. Transporte: É o envio de mercadorias de uma origem para um destino

   • Objetivo: Minimizar o custo total de Expedição, além de satisfazer os limites de fornecimento e demanda
     • O algoritmo para problema de transporte segue exatamente as mesmas etapas do método simplex. Porém, em vez de usar a tabela simplex normal, aproveitaremos à estrutura especial do problema de transporte para organizar os cálculos de maneira mais conveniente.
       • Resumo do algoritmo para o problema de transporte.
         • Etapa 1. Determine uma solução básica inicial viável e passe para a etapa 2.
           • Etapa 2. Use a condição de otimalidade do método simplex para determinar a variável que entra entre todas as variáveis não básicas. Se a condição de otimalidade for satisfeita, pare. Caso contrário, passe para a etapa 3.
             • Etapa 3. Use a condição de viabilidade do método simplex para determinar a variável que sai entre todas as variáveis básicas atuais e ache a nova solução básica. Volte para a etapa 2.
   • Balanceamento do problema de transporte. O algoritmo de transporte é baseado na premissa de que o problema é balanceado. Se o problema não for balanceado, sempre podemos adicionar uma origem fictícia ou um destino fictício para restaurar o equilíbrio.
     • Balanceamento do problema de transporte. O algoritmo de transporte é baseado na premissa de que o problema é balanceado, o que significa que a demanda total é igual ao fornecimento total. Se o problema não for balanceado, sempre podemos adicionar uma origem fictícia ou um destino fictício para restaurar o equilíbrio
   • Determinação da solução inicial
     • Método do canto noroeste.
       • noroeste (rota) da tabela simplex (variável x, ] Etapa 1, Aloque o máximo possível à célula selecionada e ajuste as quantidades associadas fornecidas e demandadas subtraindo a quantidade alocada.  Etapa 2. Cancele a linha ou coluna com suprimento ou demanda zero para indicar que nenhuma outra designação pode ser feita àquela linha ou coluna. uma linha e uma coluna chegam a zero simultaneamente, cancele somente uma e deixe um suprimento (de- manda) zero na linha(coluna) não cancelada.  Etapa 3, Se restar exatamente uma linha ou coluna não cancelada, pare. Caso contrário, passe para a célula à direita se uma coluna acabou de ser cancelada ou para a célula abaixo se uma linha foi cancelada. Volte à etapa 1. 
     • Método do menor custo.
       • Método do menor custo. O método do menor custo acha uma solução melhor concentrando-se nas rotas mais baratas. O mé- todo designa o máximo possível à célula que tiver o menor custo unitário (empates são resolvidos arbitrariamente). Em seguida, a linha ou coluna satisfeita é cancelada e as quantidades fornecidas ou demandadas são ajustadas de acordo. Se ambas, uma linha e uma coluna, forem satisfeitas simultaneamente, só uma delas é cancelada, semelhantemente ao método do canto noroeste, Em seguida, procure a célula não cancelada que tenha o menor custo unitário e repita o processo até restar exatamente uma linha ou coluna não cancelada.
     • Método de aproximação de Vogel.
       • O MAY(Vogel Approximation Method) é uma versão melhorada do método do menor custo que, em geral, mas não sempre,produz soluções iniciais melhores: Etapa1, Para cada linha (coluna), determine uma multa subtraindo e elemento de menor custo unitário da linha (coluna) do próximo elemento de menor custo da mesma linha (coluna).  Etapa 2. Identifique à linha ou coluna que tenha a maior multa.   Resolva os empates arbitrariamente. Aloque o máximo possível à variável que tiver o menor custo unitário da linha ou coluna selecionada. Ajuste o fornecimento e a demanda, e cancele a linha ou coluna satisfeita. Se uma linha e uma coluna forem satisfeitas simultaneamente, cancele apenas uma das duas atribua fornecimento (demanda) zero à linha (coluna) restante.  Etapa 3: (a) Se exatamente uma linha ou coluna com zero fornecimento ou demanda permanecer não cancelada, pare. (b) Se uma linha (coluna) com fornecimento (demanda) positivo permanecer não cancelada, determine as variáveis básicas na linha (coluna) pelo método do menor custo. Pare. (e) Se todas as linhas e colunas não canceladas (restantes) tiverem fornecimento e demanda zero, determine as variáveis básicas zero pelo método do menor custo. Pare. (d) Casocontrário, volte à ctapa 1. 

2. DESIGNAÇÃO

   • A situação pode ser ilustrada pela designação de trabalhadores com graus variáveis de habilidade a determinadas tarefas. Uma tarefa que combine coma habilidade de um trabalhador custa menos do que uma tarefa para a qual o trabalhador não seja tão habilidoso.
     • O problema de designação é, na realidade, um caso especial do problema de transporte no qual os trabalhadores representam as origens e as tarefas representamos destinos. À quantidade fornecida (demandada) em cada origem (destino) é exatamente igual a 1. O custo de “transportar” trabalhadores para a tarefa j é c, Na verdade,o problema de designação pode ser resolvido diretamente como um problema de transporte comum.
       • método húngaro
         • Etapa 1. Na matriz de custo original, identifique o mínimo de cada linha e o subtraia de todas as entradas da linha.  Etapa 2. Na matriz resultante da etapa 1, identifique o mínimo de cada coluna e o subtraia de todas as entradas da coluna.  Etapa 3. Identifique a solução ótima como a designação viável asso- ciada com os elementos zero da matriz obtida na etapa 2.
         • Etapa 2a. Se não for possível garantir nenhuma designação viável (com todas as entradas zero) pelas etapas 1 c 2, (i) trace o número mínimo de linhas horizontais e verticais na última matriz reduzida que abrangerá todas as entradas zero; (ii) selecione a menor entrada não abrangida, subtraia essa entrada de todas as entradas não abrangidas e então a adicione a todas as entradas na interseção de duas linhas; (iii) se não for possível encontrar nenhuma designação viável entre as entradas zero resultantes,repita a etapa 2a. Caso contrário,passe para a etapa 3 a fim de determinara designação ótima.
   • O objetivo do problema é determinar a designação de menor custo de trabalhadores à tarefas.

3. Redes

   • Os problemas de otimização de redes buscam encontrar o método mais eficiente de ligar várias localidades direta ou indiretamente, achar o caminho mais curto entre duas cidades, determinar o fluxo máximo em uma rede de tubulações que satisfaça requisitos de suprimentos e demanda em diferentes locais e programar as atividade de um projeto.
   • Uma rede consiste em um conjunto de nós, conectados por arcos ou ramos
     • Associado a cada rede está um fluxo
   • A solução dos problemas de rede são realizadas por algorítimos
     • Árvore Geradora Mínima
     • Caminho mais curto
     • Fluxo Máximo
     • Caminho Crítico(CPM)