Fluxo de Custo Mínimo

Prévia do material em texto

FLUXO DO CUSTO MÍNIMO 
PESQUISA OPERACIONAL II 
Bianca de Oliveira 
Maria Eduarda Raposo 
 
FLUXO DO CUSTO MÍNIMO 
 Problemas de Fluxo de Custo Mínimo consistem em descobrir caminhos de menor custo 
para passar uma determinada quantidade de fluxo através de uma rede de fluxo. 
 A maioria dos problemas podem ser expressos como um problema de fluxo de custos 
mínimos mas também podem ser resolvidos de forma muito eficiente usando o algoritmo 
simplex de rede. 
PROBLEMA DE TRANSPORTE 
É um problema muito comum dentro das empresas (em ambientes de logística). As 
principais características são: 
 Minimizar o custo do transporte; 
 Atender a demanda; 
 Capacidade de entrega da produção; 
 Determinar o ponto ótimo entre esses fatores. 
PROBLEMA DE TRANSPORTE 
 Rede bipartida onde uma parte contém nós de oferta e a outra contém os nós de 
demanda. Os arcos ligam os nós de oferta diretamente aos nós de demanda. 
 
PROBLEMA DO CAMINHO MAIS CURTO 
Minimização do custo de travessia de um grafo entre dois nós (ou vértices), onde o custo é 
dado pela soma dos pesos de cada aresta percorrida. 
 Conforme no exemplo abaixo o caminho mínimo entre D e E não é D-E, mas sim D-F-E, 
com uma distância de 14. 
 
PROBLEMA DE DESIGNAÇÃO 
O problema de Designação é um dos problemas mais clássicos. Um exemplo, é a 
designação de atividades às pessoas. O problema consiste em encontrar a melhor 
designação em termos de valor. 
PROBLEMA DE DESIGNAÇÃO 
 Rede bipartida onde o número de nós de oferta é igual ao número de nós de demanda. 
Para que haja o assinalamento 1 a 1, fazemos bk=1 onde k é nó de oferta e bL=-1 onde L 
é nó de demanda. 
 
EXEMPLO RESOLVIDO 
O dígrafo abaixo ilustra uma rede de distribuição de uma companhia, onde os nós A e B são duas 
fábricas desta companhia, os nós D e E são dois estoques e o nó C é um centro de distribuição. 
Matriz de Incidência 
EXEMPLO RESOLVIDO 
Matriz de Incidência 
EXEMPLO RESOLVIDO 
Sai – Entra = Bi 
 XAD – 0 = BA 
 XAD = 50 
 
NÓ A 
EXEMPLO RESOLVIDO 
Sai – Entra = Bi 
 XDE – XE - XAD = BD 
 XDE – 0 – 50 = -30 
 XDE = -30 + 50 
 XDE = 20 
 
NÓ D 
EXEMPLO RESOLVIDO 
Sai – Entra = Bi 
 XBC – 0 = BB 
 XBC = 40 
 
NÓ B 
EXEMPLO RESOLVIDO 
Sai – Entra = Bi 
 XCE –XE – XBC = BC 
 XCE – 0 – 40 = 0 
 XCE = 40 
 
NÓ C 
EXEMPLO RESOLVIDO 
Sai – Entra = Bi 
 XE – XCE – XDE = XE 
 XE – 40 – 20 = -60 
 XE – 60 = -60 
 XE = 0 
 
NÓ E 
EXEMPLO RESOLVIDO 
Função Objetivo 
 F(x) = XAD*CAD + XDE*CDE + XBC*CBC + XCE*CCE + XE*CE 
 F(x) = 50*9 + 20*3 + 40*3 + 40*1 + 0*0 
 F(x) = 450 + 60 + 120 + 40 
 F(x) = 670 
 
OBRIGADO! 
 BIANCA DE OLIVEIRA (bianca.oliveira@catolicasc.org.br) 
 MARIA EDUARDA RAPOSO (maria.raposo@catolicasc.org.br)