TRANSPORTE, DESIGNAÇÃO E REDES

TRANSPORTE, DESIGNAÇÃO E REDES

1. Transporte

   • Balanceado
     • Fornecimento supre a demanda
       • Restrições são todas iguais
   • Desbalanceado
     • Capacidade excede a demanda
       • Criação de ponto fictício de demanda
         • Demanda = ao excedente da capacidade
           •  A demanda nesse ponto será igual ao excedente da capacidade.
     • Demanda maior que a capacidade
       • O problema não possui solução viável
         • Como alternativa, pode-se adicionar um ponto fictício de fornecimento. O custo de fornecimento daquele ponto será igual à penalização incorrida pelo não fornecimento do insumo.
   • Canto Noroeste
     • 1° passo: construção de uma tabela (retângulo), divisão da tabela em sub-retângulos. Assim o retângulo inicial conterá linhas e colunas. 2° passo: Anota-se, a direita de cada linha as disponibilidades e abaixo de cada coluna as demandas. 3° passo: começar pelo sub-retângulo superior esquerdo (canto noroeste); 4° passo: colocar no sub-retângulo superior esquerdo a menor quantidade permitida pela oferta e demanda correspondente; 5° passo: atualizar os valores da oferta e da demanda que foram modificados pelo passo anterior; 6° passo: seguir para o sub-retângulo da direita se houver alguma oferta restante e volte para o passo 4.Caso contrário, siga para o sub-retângulo inferior e volte ao passo 4.   observação: O processo estará concluído quando o sub-retângulo inferior a direita do quadro de soluções for alcançado.  
     • Construção a tabela
       • Preenchimento da tabela
         • Sempre iniciar pelo quadrado mais acima e mais a esquerda (da tabela)
           • preencher o quadrado com a menor quantidade permitida pela oferta e demanda correspondente. (até concluir)
             • atualizar os valores da oferta e da demanda que foram modificados pelo passo anterior. (até concluir)
   • Menor Custo
     • Este método fornece uma solução inicial que depende não somente dos valores da oferta e da demanda, mais também dos custos de transporte, visando basicamente se houver uma solução inicial mais próxima da ótima do que aquela fornecida pelo método do canto noroeste.    1° passo: localizar no quadro de custos o menor custo, que não tenha oferta ou demanda nula; 2° passo: colocar no sub-retângulo correspondente do quadro de soluções a menor quantidade permitida pela oferta e demanda correspondente; 3° passo: atualizar os valores da oferta e demanda que foram modificados pelos passos anteriores.    Observação: O processo continua até que sejam esgotados as ofertas de todos as origens e atendidas as demandas de todos os destinos.  
     • localizar no quadro de custos o menor custo, que não tenha oferta ou demanda nula;
       • colocar no sub-retângulo correspondente do quadro de soluções a menor quantidade permitida pela oferta e demanda correspondente. (até concluir)
         • atualizar os valores da oferta e demanda que foram modificados pelos passos anteriores. (até concluir)

2. Designação

   • Algoritmo Húngaro
     • Passo 1 - determinar o elemento de custo mínimo em cada linha da tabela dos transportes. Construir uma nova tabela subtraindo de cada custo o custo mínimo da linha correspondente. Determine então o custo mínimo em cada coluna. Construa uma novo tabela subtraindo de cada custo o custo mínimo da coluna correspondente. Passo 2 - determine o n° mínimo de linhas (horizontais e/ou verticais) necessárias para cobrir todos os zeros na tabela de custos reduzidos. Se forem necessárias m linhas, a resposta ótima é dada pelos zeros cobertos por linhas na tabela. Se menos de m linhas forem necessárias, siga para o passo 3. Passo 3 - determine o menor elemento≠ 0 dentre os elementos não cobertos por linhas na tabela; seja k o valor deste elemento. Subtraia k de cada elemento não-coberto da tabela e adicione k a cada elemento coberto por duas linhas na tabela. Volte ao passo 2.  Observação: somente problemas balanceados podem ser resolvidos pelo algoritmo húngaro. Se um problema for não balanceado, adicione pontos artificiais de demanda ou capacidade.
     • determine o elemento de custo mínimo em cada linha da tabela dos transportes.
       • Construa uma nova tabela subtraindo de cada custo o custo mínimo da linha correspondente.
         • Determine então o custo mínimo em cada coluna.
           • Construa uma novo tabela subtraindo de cada custo o custo mínimo da coluna correspondente.
             • determine o n° mínimo de linhas (horizontais e/ou verticais) necessárias para cobrir todos os zeros na tabela de custos reduzidos. Se forem necessárias m linhas, a resposta ótima é dada pelos zeros cobertos por linhas na tabela. Se menos de m linhas forem necessárias, siga para o passo 3.
               • determine o menor elemento≠ 0 dentre os elementos não cobertos por linhas na tabela; seja k o valor deste elemento. Subtraia k de cada elemento não-coberto da tabela e adicione k a cada elemento coberto por duas linhas na tabela. Volte ao passo 2.

3. Redes

   • CPM
   • Fluxo Máximo
   • Caminho Mínimo
     • Menor caminho entre dois pontos
       • Busca encontrar o menor caminho entre dois pontos.
       • Determinar as variáveis de decisão
         • determinar as variáveis de decisão e expressá-las algebricamente. Neste caso: Xij: ação de deslocar-se da cidade i à cidade j (0 indica que não há deslocamento e 1 que há deslocamento)
         • Determinar a função objetivo
           • Determinar as restrições
             • Determinar as restrições e expressá-las como equações ou inequações dependentes das variáveis de decisão. Tais restrições são deduzidas do balanço entre os possíveis caminhos que partem de cada cidade e os caminhos que chegam até ela (ignorando as estradas que nos retornam ao ponto de partida e àquelas que vêm do destino)
   • Transporte C/ Transbordo
     • Ponto de fornecimento
       •  pode remeter insumos para outros pontos mas não pode receber. 
     • Ponto de demanda
       • pode receber insumos de outros pontos mas não pode remeter.
     • Ponto de transbordo
       • remete e recebe insumos de outros pontos.
     • Balancear o problema (se necessário)
       • Cada ponto de transbordo terá:
         • Capacidade
           • capacidade do ponto original + capacidade total de fornecimento.
         • Demanda
           • demanda do ponto original + capacidade total de fornecimento.
         • Interpretação da solução ótima:
           • Ignorar remessas
             • Aos pontos artificiais
             • De um ponto para ele mesmo