Relatorio II

Universidade Estadual do Norte Fluminense Darcy Ribeiro

Modelo de programação linear para o cálculo do caminho mínimo e do fluxo máximo

Rodrigo Mageste Rocha Pereira
Março de 2015

Caminho mínimo
O problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices), custo este, dado pela soma dos pesos de cada aresta percorrida. O caminho mínimo entre D e E não é D-E, mas sim D-F-E, com uma distância de 14.

Existem várias variantes para problemas de caminho mínimo, cada uma adequada a um conjunto de problemas diferente:
• Problema de único destino: consiste em determinar o menor caminho entre cada um dos nós do grafo e um nó de destino dado.
• Problema de único origem: determinar o menor caminho entre um nó dado e todos os demais nós do grafo.
• Problema de origem-destino: determinar o menor caminho entre nós dados.
• Problemas de todos os pares: determinar o menor caminho entre cada par de nós presentes no grafo.
O problema de caminho mínimo é bastante utilizado em áreas como Engenharia de
Transportes, Pesquisa Operacional, Ciência da Computação e Inteligência Artificial. Isso decorre do seu potencial de aplicação a inúmeros problemas práticos que ocorrem em transportes, logística, redes de computadores e de telecomunicações, etc.

Modelo de programação linear para cálculo do caminho mínimo Modelagem do problema
Função objetivo
Minimizar = 5*X1_2 + 5*X1_7 + 3*X2_3 + 2*X3_6 + 2*X3_7 + 1*X4_5 + 2*X5_8 + 1*X6_4 +
1*X6_7 + 4*X6_9 + 1*X7_4 + 1*X7_5 + 2*X7_8 + 4*X8_9 + 4*X9_7 + 7*X9_11 + 2*X10_11 +
2*X11_12 + 2*X11_13 + 3*X11_16 + 2*X11_22 + 3*X12_17 + 2*X13_12 + 1*X13_14 + 1*X14_19 +
4*X15_20 + 2*X16_15 + 2*X17_14 + 2*X17_18 + 1*X18_24 + 1*X19_18 + 1*X19_24 +2*X20_21 +
1*X20_25 + 4*X21_11 + 1*X21_23 + 2*X22_21 + 1*X22_26 + 1*X23_24 + 1*X23_25 +2*X24_17 +
1*X24_27 + 3*X25_24 + 5*X25_27 + 1*X26_25 + 5*X27_19;
Restrições
-X1_2 -X1_7 = -1;
X1_2 - X2_3 = 0;
X2_3 - X3_6 - X3_7 = 0;
X6_4 + X7_4 - X4_5 = 0;
X4_5 + X7_5 -