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
     • CPM é um método de apuração do caminho crítico dada uma sequência de atividades, isto é, quais atividades de uma sequência não podem sofrer alteração de duração sem que isso reflita na duração total de um projeto. o CPM utiliza apenas uma estimativa, considerada "mais precisa".    •Problemas cuja estrutura permite fácil representação como grafos ou redes (em geral, problemas de distribuição de produtos)   
     • método de apuração do caminho crítico
       • Seguindo uma sequência de atividades, que não podem sofrer alteração de duração sem que isso reflita na duração total de um projeto.
   • Fluxo Máximo
     • Desenvolver um esquema de transporte que maximize a quantidade de material enviada entre dois pontos de origem e destino.
       • Várias rotas interligam a origem ao destino
         • As escalas não podem estocar materiais
           • A origem, o destino e as escalas são representados por nós, enquanto os ramos representam as rotas por meio das quais os materiais são transportados.
             • Associa-se a cada nó N e a cada ramo NM originado de N um número não negativo, ou capacidade, representando a maior quantidade de material possível de ser transportada por NM, a partir de N.
   • 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