Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Nesta aula. . .
Modelos de redes
Definições básicas
Um grafo ou rede é contituído por dois elementos fundamentais:
1
Modelos de redes
2
Problema da árvore de suporte de custo mínimo
Exemplos:
3
Problema do caminho mais curto
Algoritmo de Dijkstra
Problema de transexpedição
Grafo não dirigido
um conjunto V de vértices (ou nós, ou nodos, ou pontos)
um conjunto E de arestas (ou um conjunto A de arcos)
Problemas de fluxo em grafos
Problema do fluxo máximo
Algoritmo de Ford-Fulkerson
Problema do fluxo de custo mínimo
4
João Pedro PEDROSO
Grafo dirigido (ou digrafo)
1
4
1
4
2
3
2
3
V = {1, 2, 3, 4}
V = {1, 2, 3, 4}
E = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}
Métodos de Apoio à Decisão
A = {(1, 2), (2, 3), (3, 4), (4, 1), (4, 3)}
João Pedro PEDROSO
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Métodos de Apoio à Decisão
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Modelos de redes
Problema da árvore de suporte de custo mínimo
Definições básicas
Dados: um grafo (em que cada aresta tem um comprimento/peso).
arestas são pares não ordenados de vértices, e significam que pode
haver movimento entre esse vértices; e.g., {2, 3}
arcos são pares ordenados de vértices, e representam a direcção em
que o movimento entre esse vértices pode ser feito;
(i, j) significa que pode haver movimento do vértice i para o j
i – vértice inicial
j – vértice final, ou terminal
diz-se que o arco vai de i para j
Pretende-se determinar o conjunto de arestas que permite ligar todos os
vértices, de tal forma que o comprimento (/peso) das arestas utilizadas
seja mínimizado.
Uma árvore de suporte é um grupo de n − 1 arestas que liga todos os
vértices do grafo e que não contém ciclos.
Algoritmo para a árvore de suporte de custo mínimo:
1
cadeia é uma sequência de arcos tal que cada um deles tem
exatamente um vértice em comum com o anterior (excepto o primeiro),
e.g. (1,2),(2,3),(4,3)
2
Começar por qualquer vértice i; juntar i ao vértice que j lhe está mais
próximo; seja C = {i, j} e C 0 = {restantes vértices}; {i, j} fará parte da
árvore de suporte de custo mínimo.
Escolher o elemento n de C 0 mais próximo de um dos vértices de C; seja m
o vértice de C mais próximo de n.
1
caminho é uma cadeia tal que o vértice terminal de cada arco é o
vértice inicial do arco seguinte, e.g, (1,2),(2,3),(3,4)
2
3
3
{m, n} fará parte da árvore de suporte de custo mínimo;
C := C ∪ {n}
C 0 := C 0 \{n}
Repetir até que todos os vértices estejam em C.
João Pedro PEDROSO
Métodos de Apoio à Decisão
João Pedro PEDROSO
Métodos de Apoio à Decisão
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Algoritmo de Dijkstra
Problema de transexpedição
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Algoritmo de Dijkstra
Problema de transexpedição
Problema do caminho mais curto
Exemplo
Uma companhia de eletricidade pretende enviar energia de uma central
de produção para uma cidade, através de arcos de transmissão e de
sub-estações.
Cada arco no grafo tem um comprimento associado
A distância entre os nodos é dada:
Começamos num dado nodo;
2
4
Queremos determinar a forma de ir para um outro nodo com o custo
mínimo.
3
4
2
2
1
3
2
3
3
6
5
Supondo que o custo de transmissão é proporcional às distâncias, qual
é a forma mais económica de enviar energia?
João Pedro PEDROSO
Métodos de Apoio à Decisão
João Pedro PEDROSO
Métodos de Apoio à Decisão
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Algoritmo de Dijkstra
Problema de transexpedição
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Algoritmo de Dijkstra
Problema de transexpedição
Algoritmo de Dijkstra
Problema de transexpedição
Método para determinar o caminho mais curto no grafo quando todos os
comprimentos são não negativos
1
Por uma etiqueta permanente 0 no nó e partida.
2
Por uma etiqueta temporária a cada nó ligado a esse, com o
comprimento do arco que os liga.
3
Por em todos os outros nós a etiqueta temporária ∞.
4
Escolher o nó com a etiqueta temporária mais baixa; tornar a sua
etiqueta permanente.
5
A cada nó j com etiqueta temporária lidado a i, substituir a etiqueta por
min{etiqueta temporária de j, etiqueta de i + comprimento de (i, j)}
6
Continuar desde o passo 4 até colocar uma etiqueta permanente no nó
de destino.
João Pedro PEDROSO
Métodos de Apoio à Decisão
Enviar produtos de determinados vértices a outros, minimizando o custo de
transporte.
Grafo: G(V , A), V é o conjunto de vértices e A o de arcos.
Cada vértice i é:
Centro consumidor:
Centro intermédio:
Centro produtor:
Entrada - Saída = Procura
Entrada = Saída
Saída - Entrada = Produção
Formulação:
Variáveis: xij ≥ 0, ∀(i, j) ∈ A: fluxo no arco (i, j)
X
Objetivo: minimizar z =
cij xij
Restrições:
X
(j,i)∈A
(i,j)∈A
xji −
X
xij = di
(i,j)∈A
João Pedro PEDROSO
i∈V
Métodos de Apoio à Decisão
di > 0
di = 0
di < 0
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Algoritmo de Dijkstra
Problema de transexpedição
Problema do caminho mais curto como transexpedição
Problema do fluxo máximo
Algoritmo de Ford-Fulkerson
Problema do fluxo de custo mínimo
Problema do fluxo máximo
Muitas situações podem ser modeladas através de um grafo em que:
arcos têm uma capacidade que limita a quantidade que pode ser através
deles enviada
um vértice é a origem, a partir da qual se quer enviar produtos para um
outro vértice, o destino
Se:
Exemplo: uma companhia petrolífera pretende enviar a máxima
quantidade horária possível de petróleo de o para d.
fizermos cij igual à distância entre i e j
minimizarmos o custo de enviar uma unidade do nodo de origem para o
nodo de destino
então esta formulação resolve o problema do caminho mais curto.
3
3
qual é a solução?
o
2
3
1
2
1
2
d
3
Formule o problema linear que permite determinar o número máximo de
barris por hora que podem ser enviados.
João Pedro PEDROSO
Métodos de Apoio à Decisão
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
João Pedro PEDROSO
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Problema do fluxo máximo
Algoritmo de Ford-Fulkerson
Problema do fluxo de custo mínimo
Problema do fluxo máximo
Métodos de Apoio à Decisão
Problema do fluxo máximo
Algoritmo de Ford-Fulkerson
Problema do fluxo de custo mínimo
Algoritmo de Ford-Fulkerson
Formulação em programação linear
Dados do problema:
Grafo: conjunto de vértices V , e conjunto de arcos A
Vértices de origem o e de destino d
Capacidade em cada um dos arcos: cij , (i, j) ∈ A
Variáveis:
Seja I o conjunto de arcos em que se pode aumentar o fluxo
Seja R o conjunto de arcos em que se pode diminuir o fluxo
1
determinar um fluxo admissível (e.g., zero em todos os arcos)
2
encontrar uma cadeia de arcos com etiqueta que permita etiquetar o
vértice de destino:
por uma etiqueta no vértice de origem;
por etiquetas em vértices e arcos de acordo com:
xij fluxo através do arco (i, j), (i, j) ∈ A
y , fluxo que parte da origem (e chega ao destino)
1
Restrições:
capacidade dos arcos: 0 ≤ xij ≤ cij , (i, j) ∈ A
conservação do fluxo:
X
X
xji =
xij i ∈ V \{o, d}
(j,i)∈A
(i,j)∈A
y=
X
xij
(i,j)∈A:i=o
y=
X
xij
(i,j)∈A:j=d
Objetivo: maximizar y
João Pedro PEDROSO
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
2
se o vértice x tem etiqueta, y não tem, e (x, y ) ∈ I, então colocar etiqueta em y
e em (x, y ); (x, y ) é um arco em frente;
se o vértice x tem etiqueta, y não tem, e (y , x) ∈ R, então colocar etiqueta em y
e em (y , x); (y , x) é um arco para trás;
se não se consegue etiquetar o vértice de destino, o fluxo atual é máximo,
STOP;
3
Aumentar o fluxo:
Se a cadeia utilizada para etiquetar o destino tem apenas arcos em frente:
aumentar o fluxo em cada um deles tanto quanto possível (mantendo a
solução admissível);
Se a cadeia tem também arcos para trás: aumentar o fluxo nos arcos em
frente, e reduzí-lo nos arcos para trás, tanto quanto possível (mantendo a
solução admissível);
Voltar ao passo 2.
Métodos de Apoio à Decisão
Problema do fluxo máximo
Algoritmo de Ford-Fulkerson
Problema do fluxo de custo mínimo
Problema do fluxo máximo
João Pedro PEDROSO
Métodos de Apoio à Decisão
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Problema do fluxo máximo
Algoritmo de Ford-Fulkerson
Problema do fluxo de custo mínimo
Problema do fluxo de custo mínimo
Pretende-se enviar uma determinada quantidade de um determinado
produto através de um grafo, de um ponto (a origem) a um outro ponto
(o destino), de tal forma que o custo de expedição seja mínimo.
Dados do problema:
Pode ser resolvido por programação linear ou através do algoritmo de
Ford-Fulkerson;
Este último é eficiente: os recursos computacionais necessários para o
resolver são limitados por um polinómio, em termos dos dados do
problema.
Grafo: conjunto de vértices V , e conjunto de arcos A
Vértices de origem o e de destino d
Custo unitário de transporte em (i, j): cij , (i, j) ∈ A
Majorante para o fluxo em cada um dos arcos: Uij , (i, j) ∈ A
Minorante para o fluxo em cada um dos arcos: Lij , (i, j) ∈ A
Produção no vértice i: bi (negativo se houver consumo em i)
Variáveis:
xij fluxo através do arco (i, j),
Restrições:
(i, j) ∈ A
capacidade dos arcos: P
Lij ≤ xij ≤ UijP
, (i, j) ∈ A
conservação do fluxo: (i,j)∈A xij − (k ,i)∈A xki = bi ,
i∈V
P
Objetivo: minimizar
(i,j)∈A cij xij
Notas: o problema de fluxo máximo pode ser formulado como um problema
de fluxo a custo mínimo; para o problema do fluxo a custo mínimo, existe
uma versão mais eficiente do método do simplex: o método dos simplex para
redes.
João Pedro PEDROSO
Métodos de Apoio à Decisão
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
João Pedro PEDROSO
Métodos de Apoio à Decisão
Modelos de redes
Problema da árvore de suporte de custo mínimo
Problema do caminho mais curto
Problemas de fluxo em grafos
Noções estudadas
Noções estudadas
Próxima aula
Noções básicas de grafos: vértice, aresta, arco, caminho.
Problema do caminho mais curto; algoritmo de Dijkstra.
Problema da transexpedição.
Problema do fluxo máximo: formulação em programação matemática.
Problemas de gestão de projetos.
Algoritmo de Ford-Fulkerson.
Noção de corte num grafo; relação entre a capacidade do corte e o fluxo
máximo no grafo.
Problema do fluxo a custo mínimo.
João Pedro PEDROSO
Métodos de Apoio à Decisão
João Pedro PEDROSO
Métodos de Apoio à Decisão