Calculando o Fluxo de uma
Árvore Geradora
Uma árvore com ofertas e
demandas. (Assuma que
todos os demais arcos
apresentam um fluxo
igual a 0).
15.053
Animações Simplex
de Rede
Qual é o fluxo no arco
(4,3)?
1
Animações Simplex de Rede
Animações Simplex de Rede
Calculando o Fluxo de uma
Árvore Geradora
2
Animações Simplex de Rede
Calculando o Fluxo de uma
Árvore Geradora
Para calcular os fluxos,
itere a árvore e encontre
um arco cujo fluxo pode
ser unicamente
determinado.
Qual é o fluxo no arco
(3,2)?
Qual é o fluxo no arco
(5,3)?
3
Animações Simplex de Rede
Calculando o Fluxo de uma
Árvore Geradora
4
Calculando o Fluxo de uma
Árvore Geradora
Qual é o fluxo no arco
(2,6)?
5
Animações Simplex de Rede
Animações Simplex de Rede
Qual é o fluxo no arco
(7,1)?
6
Animações Simplex de Rede
1
Calculando o Fluxo de uma
Árvore Geradora
Calculando o Fluxo de uma
Árvore Geradora
Essa é uma árvore
geradora com custos dos
arcos. Como é possível
escolher os potenciais de
nós de forma que o custo
reduzido dos arcos da
árvore seja 0?
Observação: existem duas
formas diferentes de
calcular o fluxo em (1,2) e
ambas as formas dão o
fluxo em 4. Isso é uma
coincidência?
Lembre-se: o custo
reduzido de (i, j) é
cij 7
Animações Simplex de Rede
Calculando Multiplicadores
Simplex para a Árvore Geradora
+
j
Animações Simplex de Rede
Calculando Multiplicadores
Simplex para a Árvore Geradora
Pode-se assumir o valor
de 1 de forma arbitrária.
Assumiremos que i = 0
Lembre-se: o custo
reduzido de (i, j) é
Qual é o multiplicador
simplex para o nó 2?
i
+
Existe uma restrição
redundante no problema
de fluxo de custo mínimo.
j
Animações Simplex de Rede
Calculando Multiplicadores
Simplex para a Árvore Geradora
10
O custo reduzido de (1,2) é
c12 - 1 + 2 = 0.
Pode-se assumir o valor
de 1 de forma arbitrária.
Assumiremos que i = 0
Então 5 - 0 +
Qual é o multiplicador
simplex para o nó 2?
Animações Simplex de Rede
Animações Simplex de Rede
Calculando Multiplicadores
Simplex para a Árvore Geradora
Existe uma restrição
redundante no problema
de fluxo de custo mínimo.
11
i
Essa é uma árvore
geradora com custos dos
arcos. Como é possível
escolher os potenciais de
nós de forma que o custo
reduzido dos arcos da
árvore seja 0?
cij 9
8
2
= 0.
Qual é o multiplicador
simplex para o nó 7?
12
Animações Simplex de Rede
2
Calculando Multiplicadores
Simplex para a Árvore Geradora
Calculando Multiplicadores
Simplex para a Árvore Geradora
O custo reduzido de (1,2) é
c71 –
7
+
Então -6 -
1
2
= 0.
+ 0 = 0.
Qual é o multiplicador
simplex para o nó 6?
Qual é o multiplicador
simplex para o nó 3?
13
Animações Simplex de Rede
Calculando Multiplicadores
Simplex para a Árvore Geradora
14
Calculando Multiplicadores
Simplex para a Árvore Geradora
Qual é o multiplicador
simplex para o nó 4?
15
Animações Simplex de Rede
Calculando Multiplicadores
Simplex para a Árvore Geradora
Animações Simplex de Rede
Qual é o multiplicador
simplex para o nó 5?
16
Animações Simplex de Rede
Algoritmo Simplex de Rede
Esses são os
multiplicadores simplex
associados à essa árvore.
Eles não dependem dos
fluxos de arco, nem dos
custos dos arcos não
pertencentes à árvore.
O Problema de Fluxo de Custos Mínimos
17
Animações Simplex de Rede
18
Animações Simplex de Rede
3
Fluxos da árvore geradora
Multiplicadores Simplex e Custos
Reduzidos
Uma Solução Inicial de Árvore Geradora
19
Animações Simplex de Rede
Os multiplicadores simplex iniciais e
custos reduzidos
20
Quais arcos
estão violando?
Animações Simplex de Rede
Adicione um arco violador à
árvore geradora, criando um ciclo
Enviar o Fluxo ao Redor do Ciclo
Qual é o ciclo e
qual a
quantidade de
fluxo que pode
ser enviada?
Qual é a
próxima árvore
geradora?
Arco (2,1) é adicionado à árvore
21
Animações Simplex de Rede
Após um pivô
A Árvore Geradora Atualizada
23
2 unidades de fluxo foram enviadas
ao longo do ciclo.
22
Animações Simplex de Rede
Atualizando os Multiplicadores
Em um pivô,
um arco é
adicionado a T
e um arco é
retirado de T.
Animações Simplex de Rede
Os multiplicadores atuais e custos
reduzidos
24
Como podemos
estabelecer c 21
= 0 e garantir
que os 3 arcos
restantes
tenham um
custo reduzido?
Animações Simplex de Rede
4
Deletar (2,1) de T divide T em
duas partes
Adicionar D aos nós em um lado da
árvore não afeta os custos reduzidos
de nenhum arco da árvore, exceto
(2,1). Por quê?
25
Que valor de D
deveria ser
escolhido para
que os custos
reduzidos de
(2,1) = 0?
Animações Simplex de Rede
Adicionar um arco violador à
árvore geradora, criando um ciclo
Adicionar o arco (3,4) à árvore
geradora
27
Os multiplicadores atualizados e
custos reduzidos
Os multiplicadores atualizados e os
custos reduzidos
26
A próxima solução da árvore
geradora
1 unidade do fluxo foi enviada ao
redor do ciclo.
28
Animações Simplex de Rede
Esses são os multiplicadores atuais
Animações Simplex de Rede
Qual é a próxima
solução da árvore
geradora?
Multiplicadores Atualizados
Essa é a solução da árvore geradora
atualizada
29
Animações Simplex de Rede
Enviar o Fluxo ao Redor do Ciclo
Qual é o ciclo e
qual a
quantidade de
fluxo que pode
ser enviada?
Animações Simplex de Rede
A solução da
árvore geradora
é ótima?
30
Como devemos
modificar os
multiplicadores?
Animações Simplex de Rede
5
Multiplicadores Atualizados
Esses são os multiplicadores atuais
31
Multiplicadores Atualizados
Que valor D deve
assumir?
Esses são os multiplicadores atualizados.
Animações Simplex de Rede
32
A solução da
árvore geradora
atual é ótima?
Animações Simplex de Rede
A Solução Ótima
Essa é a solução ótima.
33
Nenhum arco viola
as condições
ótimas.
Animações Simplex de Rede
6