Aula 07 - Problemas de Transporte

Prévia do material em texto

Problemas de Transportes
Como transportar cargas para os pontos de demanda pelo menor custo possível? Quanto levar para cada ponto?
Devemos tentar minimizar uma função que relaciona os custos com o fluxo entre nós (pontos da malha).
= quantidade de oferta no nó.
= quantidade de demanda no nó.
= custo unitário de transporte no arco (i,j) entre nó de oferta e nó de demanda.
Em condições ideais, a demanda nos nós será igual à oferta:
Matematicamente:
 
m: origens
n: destinos
(A conferência acima é importante para saber se seu resultado está coerente).
Os fluxos entre nós são dados por:
 i=1,2,..,m
 j=1,2,..,n
Equação a ser minimizada: 
Interpretação do esquema acima:
· Os círculos são nós de oferta.
· Os quadrados são nós de demanda.
Exemplo: 
Para levar carga de A até D, gasta-se $7. Mas quanto levar para D? Será que não é melhor levar carga de C para D porque o custo é só $4?
Podemos responder essas perguntas por meio de dois métodos:
· Método do Canto Noroeste e custo reduzido (Slides 23 a 77)
	
De: 
	Para:
	
Oferta
	
	Cidade 1 
	Cidade 2
	Cidade 3
	Cidade 4
	
	Planta 1
	$8
	$6
	$10
	$9
	35
	Planta 2
	$9
	$12
	$13
	$7
	50
	Planta 3
	$14
	$9
	$16
	$5
	40
	Demanda 
	45
	20
	30
	30
	
1° Passo: contar a quantidade de origens (m). Neste caso há 3 origens.
2º Passo: contar a quantidade de destinos (n). Neste caso há 4 destinos.
3° Passo: calcular a quantidade de variáveis por meio da fórmula: m+n-1. Neste caso: 3+4-1= 6 variáveis básicas = número de células a serem preenchidas.
4º Passo: montar o quadro (mxn):
5° Passo: preencher na primeira célula (canto superior esquerdo - noroeste) o máximo valor possível. Por exemplo, a demanda é de $45, mas a oferta é somente de $35, então só é possível preencher com $35 e sobram $10 para serem atendidos.
6° Passo: como já se sabe que faltam $10 para atender completamente a demanda da cidade 1 -> completar com a contribuição da planta 2:
7° Passo: Perceba que a planta 1 não tem mais capacidade de atendimento de demandas, porque gastou tudo atendendo a cidade 1. A planta 2 ainda tem capacidade de $40, então é possível atender a demanda da cidade 2 ($20) e ainda sobram $20:
8° Passo: Como a planta 2 ainda tem $20 para gastar, ela pode atender uma parcela da demanda da cidade 2. Em seguida, a planta 3 completa com $10:
9° Passo: por fim, a planta 3 possui exatamente $30 para atender a demanda da cidade 4 (equilíbrio entre oferta e demanda):
Perceba que existem 6 células preenchidas, como havia sido estipulado inicialmente.
10° Passo: examinar se os custos diminuem ou aumentam com a configuração final acima. Para isso, é necessário perceber quais as consequências de uma variação na contribuição de cada planta.
Por exemplo, na primeira célula usamos o máximo possível para preenchê-la, então a variação lógica seria diminuí-la (). Com sua redução, seria viável a planta 1 atender a cidade 2 (), mas como uma parcela da demanda da cidade 2 foi atendida, a planta 2 pode contribuir menos com a cidade 2 (). Como diminuímos o quanto a planta 1 leva para a cidade 1, a planta 2 deve encaminhar mais () para que a cidade 1 possua toda a sua demanda atendida. Ou seja, uma variação implica em mudanças nas outras células.
11° Passo: calcular os custos reduzidos: basta somar ou subtrair os custos de cada fluxo (os quadradinhos no canto superior direito de cada célula). O sinal é o mesmo da variação: +6-12+9-8= -5 (significa que houve redução unitária de $5). 
12° Passo: preencher todas as células ainda não preenchidas com o cálculo do custo unitário, resultando em:
13° Passo: analisando os resultados acima, percebe-se que houve aumentos de custos em algumas células, isso significa que não é uma configuração ótima. 
Em resumo:
 
Outra forma de calcular os custos reduzidos:
Olhando para os custos (quadradinhos no canto superior direito).
1) Escrever do lado do quadro com u1…un.
2) Escrever acima do quadro v1…vn.
3) Assumir u1=0
4) u1+v1=8, se u1=0, v1=8.
5) Se v1=8, quanto deve ser u2 para dar 9? u2=1.
6) Se u2=1, quanto deve ser v2 para dar 12? v2=11.
7) Se u2=1, quanto deve ser v3 para dar 13? v3=12.
8) Se v3=12, quanto deve ser u4 para dar 16? u4=4.
9) Se u4=4, quanto deve ser v4 para dar 5? v4=1.
O preenchimento de um u ou v implica no resultado do outro. 
Para calcular os custos reduzidos, você olha para as células não preenchidas e subtrai do custo seu respectivo u e v:
Os resultados das duas formas devem ser iguais.
· Método de Vogel (Slides 78 a 83)
É um método mais eficiente do que o canto noroeste.
1° Passo: fazer a diferença dos custos de cada linha e coluna entre os dois MENORES VALORES(anotar): 
2° Passo verificar qual é a maior diferença e preencher a célula que possui o menor custo: No exemplo, a maior diferença é 4 (define a linha) e preenche-se a quantidade máxima na célula com menor custo unitário (5).
3° Passo: como não é mais necessário demanda para a cidade 4, a sua coluna é desconsiderada, e calcula-se novamente a diferença entre os custos. Sempre anote o quanto sobrou de oferta, por exemplo, a planta 4 ainda tinha 10 para contribuir. 
4° Realize os passos acima até todas as demandas serem atendidas.
5º Calcule os custos reduzidos unitários para a conferência: resultados positivos -> solução ótima. 
Importante: existem locais em que um zero não pode ser colocado dada a situação da solução. Condições abaixo:
image6.png
image7.png
image8.png
image9.png
image10.png
image11.png
image12.png
image13.png
image14.png
image15.png
image16.png
image1.png
image2.png
image3.png
image4.png
image5.png