O problema de transporte?

O problema de transporte?

O problema de trnsporte aperece quando há a necessidade de distribuição de bens e serviços de várias fontes de suprimentos para várias localizações de demanda.

Método de Stepping-Stone?

Na aplicação deste metodo chega -se a solução ótima partindo-se de uma solução inicial qualquer viavel e pesquisa-se se uma solução melhor pode ser encontrada, por uma solução inicial viável pode escolher método do menor custo

A) Solução inicial: Método do mínimo custo:

1- Verificar o menor custo unitário e nesta célula, alocar o máximo possível ou a fonte envolvida pode enviar. Caso toda a capacidade da fonte tiver sido usada prencher as demais linhas com zero.

2- Completar a linha ou coluna da célula utilizada anteriormente apartir do menor custo existente. Após isto usada prencher as demais distintos da linhas com zero.

3- Repetir o processo para as demais variaveis com outros custos, sempre em ordem crescente, até alocar todas as células da matriz.

B) Solução ótima: Processo iterativo:

Cada célula da matriz zerada representa uma variavel não basica que poderia entrar na base e contribuir para um custo total de transporte menor do que foi obtido.

O valor alocado a está célula deve ser o máximo de modo que nenhuma variavel fique com o valor negativo. Esse valor é o menor do valores entre as variaveis com sinal negativo no caminho da variavel com maior contribuição.

Para cada uma nova solução:

deve-se calcular as contribuições para as células zeradas. Quando todas as contribuições calaculadas apresentam como resposta valores positivos, significa que a solução ótima foi encntrada pois a inclusão delas irá contribuir para aumentar o custo do trnsporte.

Casos especiais do problema de transporte:

Quando o problema de transporte não estiver balanceado deve-se criar uma nova origem ou um novo destino ficticio para tornar-se o problema de transporte balanceado e considera-se o custo da transporte igual a zero.

Problema de Designação ou de alocação de recursos:

O problema de designação envolve a atribuição de pessoas a projetos ou tarefas, de trabalhos á maquina e situações semelhantes. Neste problema assume-se a hipotese de que cada elemento a ser designado só será a unico obejetivo. Cada atribuição tem uma variavel de decisão e mante-se uma função objetiva. O custo pode ser minimizado ou maximizado.

Solução do problema de designação utilizando o algoritmo húngaro.

Para utilizar a matriz formada precisa ser quadrada . O algoritmo hungaro trabalha com o principio de redução.

As alocações ótimas são representadas pelas celulas da matriz onde se coseguir uma penalidade ou custo de oportunidade zero.

Metodologia: Algoritmo Hungaro.

Passo1: Transformar a matriz dada em uma matriz de custos de oportunidade.

a) subtrair o menor valor em cada linha e todos outros valores, gerando pelo menos um zero em cada linha.

b) Subtrair o menor valor de cada coluna e de todos os outros valores, gerando pelo menos um zero em cada coluna.

Passo2: Traçar o menor número de retas possíveis cobrindo todos os zeros da matriz. Caso o número minimo de retas traçadas seja igual ao número de ordem da matriz então a solução ótima foi encontrada ir para o passo 4. Caso não passar para o passo 3.