Fluxo de custo mínimo em grafos

Este capítulo generaliza o problema de Gale (seção 3.1) e procura um fluxo que satisfaça demandas dos nós, respeita as capacidades dos arcos, e faça tudo isso ao menor custo possível. Para resolver o problema, o capítulo usa as ferramentas desenvolvidas na seção 3.1, no capítulo 1 (caminhos dirigidos de custo mínimo), e no capítulo 2 (fluxos de intensidade máxima).

Os ingredientes do problema são os mesmos dos capítulos anteriores: um grafo dirigido

D := (V, E)

, uma função-demanda

(b_{v} : v \in V)

com valores em

R

, uma função-capacidade

(u_{e} : e \in E)

com valores em

R_{+}

, e uma função-custo

(c_{e} : e \in E)

com valores em

R

. [Poderíamos escrever

b \in R^{V}

u \in R_{+}^{E}

c \in R^{E}

. Seria mais realista trocar todos os

R

por

Q

, uma vez que computadores digitais não conhecem números irracionais.] Note que

u \geq 0

mas

b

c

não têm restrição de sinal.

4.1 O problema

Um fluxo numa rede

(D, b, u)

é qualquer vetor

(x_{e} : e \in E)

com valores em

R_{+}

. Um fluxo

x

respeita

u

x \leq u

e satisfaz

b

x_{-}^{+} = b .

(Como na seção 2.1, para cada nó

v

x_{-}^{+} (v)

é a quantidade de fluxo que entra em

v

menos a quantidade de fluxo que sai de

v

.) Um fluxo

x

é viável se satisfaz

b

e respeita

u

Dada uma função-custo

c

, o custo de um fluxo

x

é o número

c x

. Convém lembrar que

c

não tem restrições de sinal: podemos ter

c_{e} < 0

em alguns arcos e

c_{e} \geq 0

em outros.

(Poderíamos dizer que esse é o problema de Gale com custos.) Em inglês, o problema é conhecido como minimum-cost flow problem. Muitas vezes, dizemos simplesmente fluxo de custo mínimo, deixando o viável subentendido. Dizemos também que um fluxo é ótimo se for viável e tiver custo mínimo.

Uma rede de fluxo com custos é qualquer rede

(D, b, u, c)

que tenha os parâmetros

b

u

c

que acabamos de descrever. Uma tal rede é viável se tem um fluxo viável. De acordo com o lema 3.1 e o teorema de Gale (teorema 3.2), a rede é viável se e somente se

b (V) = 0 e b (X) \leq u_{}^{+} (X)

para todo subconjunto

X

V

. (Essas condições também podem ser escritas de maneira mais simétrica:

- u_{}^{-} (X) \leq

b (X) \leq

u_{}^{+} (X)

para todo

X \subseteq V

.) Toda rede viável tem um fluxo de custo mínimo pois todo fluxo viável é limitado:

x_{e} \leq u (E)

para todo fluxo viável

x

e todo arco

e

Exemplo 4.1: Seja $D$ o grafo dirigido com nós $p v w q$ descrito abaixo por sua matriz de adjacências. A função-demanda $b$ está representada à direita da matriz. Mais à direita, as capacidades e os custos dos arcos bem como dois diferentes fluxos viáveis, $x$ e $x^{'}$ . Verifique que $c x = 240$ e $c x^{'} = 180$ . Observe como é fácil conferir a viabilidade e o custo de um fluxo percorrendo as linhas da tabela.

\begin{array}{rr} p & v & w & q & b \\ p & - & 1 & 1 & - & - 2 \\ v & - & - & 1 & 1 & - 1 \\ w & - & - & - & 1 & + 1 \\ q & - & - & - & - & + 2 \end{array} \begin{array}{lr} p v & p w & v w & v q & w q \\ u & 3 & 3 & 3 & 3 & 3 \\ x & 0 & 2 & 0 & 1 & 1 \\ x^{'} & 0 & 2 & 1 & 0 & 2 \\ c & - 30 & + 80 & + 40 & + 90 & - 10 \end{array}

Exercícios 4.1

Suponha que $a$ é um arco de custo máximo na rede, ou seja, $c_{a} := max (c_{e} : e \in E)$ . Se $x$ é um fluxo viável de custo mínimo, é verdade que $x_{a} = 0$ ?
O problema do caminho dirigido de custo mínimo (problema 1.A no capítulo 1) é um caso particular do problema fluxo de custo mínimo (problema 4.A)?
Mostre que o problema do fluxo de intensidade máxima de um nó $r$ a um nó $s$ numa rede capacitada (problema 2.A no capítulo 2) é um caso particular do problema 4.A. (Dica: acrescente arco $s r$ ao grafo.) [CCPS 4.7]
★ Seja $(D, b, u, c)$ uma rede viável. Mostre que a rede não é ilimitada, ou seja, tem um fluxo ótimo.
Um emparelhamento num grafo não-dirigido é perfeito se incide em todos os nós. Considere o problema de encontrar um emparelhamento perfeito de custo mínimo em um grafo não-dirigido bipartido. Formule esse problema como um caso particular do problema 4.A. [CCPS 4.2]
Seja $D$ um grafo dirigido tal que o número $| \partial_{}^{+} (v) | + | \partial_{}^{-} (v) |$ é par em cada nó $v$ . Para cada arco $v w$ , seja $c_{v w}$ o custo de inverter $v w$ (isto é, trocar $v w$ por $w v$ ). Queremos encontrar um conjunto de arcos de custo mínimo cuja inversão faz com que $D$ tenha um ciclo dirigido euleriano (veja exercício na seção 3.1). Formule esse problema como um caso particular do problema 4.A. [CCPS 4.5]
Atribuição de terminais a concentradores. Uma rede de teleprocessamento tem um grande número de terminais geograficamente dispersos e uma CPU. É dado um conjunto de concentradores, instalados em certos lugares, sendo cada um ligado à CPU por uma linha de alta capacidade e custo nulo. Cada terminal precisa ser ligado à CPU e a ligação pode ser direta ou pode passar por um concentrador. Cada concentrador pode cuidar de até $k$ terminais. Para cada terminal $j$ , o custo de uma ligação direta com a CPU é $d_{j}$ e o custo de uma ligação com um concentrador $i$ é $d_{i j}$ . Queremos determinar a maneira mais barata de ligar os terminais à CPU. Formule esse problema como um caso particular do problema 4.A. [AMO 9.7]
★ Roteamento de cargueiros vazios. Para um certo conjunto $V$ de portos marítimos, temos os seguinte dados relativos ao ano que passou: para cada porto $v$ , temos o número $p_{v}$ de toneladas de carga que entraram no porto e o número $q_{v}$ de toneladas de carga que saíram do porto. Em cada porto $v$ , a diferença $b_{v} := p_{v} - q_{v}$ é uma medida do suprimento de cargueiros vazios em $v$ e $- b_{v}$ é uma medida da demanda por cargueiros vazios em $v$ . Cada cargueiro vazio saiu de um porto $v$ em que $b_{v}$ é positivo e foi para um porto $w$ em que $b_{w}$ é negativo. Se a distância do porto $v$ ao porto $w$ é de $c_{v w}$ milhas, o deslocamento de $v$ a $w$ de um cargueiro vazio com capacidade para $t$ toneladas representa um desperdício de $t c_{v w}$ toneladas $\times$ milha. Queremos organizar a movimentação de cargueiros vazios de modo a minimizar o desperdício total anual. [Sch17 p.73]

4.2 Programação linear

Na linguagem da programação linear, o problema do fluxo de custo mínimo (problema 4.A) pode ser formulado assim: encontrar um vetor real

(x_{v} : v \in V)

que

\begin{matrix} (1) & \begin{array}{rcll} minimize c x \\ sujeito a x_{-}^{+} (v) & = & b_{v} & para cada v \in V \\ x_{e} & \leq & u_{e} & para cada e \in E \\ x_{e} & \geq & 0 & para cada e \in E . \end{array} \end{matrix}

(Convém lembrar que podemos ter

c_{e} \geq 0

em alguns arcos e

c_{e} < 0

em outros.) Esse programa linear pode ser escrito assim em termos da matriz de incidências

A

do grafo

D

\begin{aligned} minimize c x \\ sujeito a A x & = b \\ x & \leq u \\ x & \geq 0 . \end{aligned}

O dual desse pl consiste em encontrar vetores reais

(y_{v} : v \in V)

(z_{e} : e \in E)

que

\begin{aligned} maximizem y b + z u \\ sujeito a y A + z & \leq c \\ z & \leq 0 \end{aligned}

e esse dual pode ser escrito por extenso assim: encontrar

y

z

que

\begin{matrix} (2) & \begin{array}{rcll} maximizem y b + z u \\ sujeito a y_{w} - y_{v} + z_{v w} & \leq & c_{v w} & para v w \in E \\ z_{v w} & \leq & 0 & para v w \in E . \end{array} \end{matrix}

Para qualquer solução viável

x

do pl

(1)

e qualquer solução viável

(y, z)

do pl

(2)

temos então

\begin{matrix} (3) & \begin{aligned} c x & \geq (y A + z) x \\ = (y A) x + z x \\ = y (A x) + z x \\ \geq y b + z u . \end{aligned} \end{matrix}

c x = y b + z u

então

x

é solução ótima de

(1)

(y, z)

é solução ótima de

(2)

. O teorema forte da dualidade garante a recíproca: se os dois pl's são viáveis então existe

x

viável no primal e existe

(y, z)

viável no dual tais que

c x = y b + z u

. Essa igualdade equivale às condições de folgas complementares:

As condições 1 e 2 de folgas complementares podem também ser formuladas assim: para cada arco

v w

Segue daí imediatamente que se

0 < x_{v w} < u_{v w}

então

y_{w} - y_{v} = c_{v w}

Algoritmo. Poderíamos resolver o problema 4.A submetendo o programa linear

(1)

ao algoritmo Simplex. Mas isso é ineficiente, uma vez que o Simplex, que foi projetado para programas lineares arbitrários, não leva em conta as muitas peculiaridades do pl

(1)

Exercícios 4.2

Verifique que o pl $(2)$ é dual do pl $(1)$ .
★ Mostre que o pl dual $(2)$ é viável, ou seja, exiba alguma solução viável $(y, z)$ do pl.
Suponha que $b (V) \neq 0$ numa rede $(D, b, u, c)$ de fluxo com custos. Mostre que o pl $(1)$ é inviável nesse caso. Mostre que o pl dual $(2)$ é ilimitado nesse caso (ou seja, $y b + z u$ não tem máximo).
Suponha que $b (X) > u_{}^{+} (X)$ para algum $X \subseteq V$ . Mostre que pl $(1)$ é inviável nesse caso. Mostre que o pl dual $(2)$ é ilimitado nesse caso (isto é, $y b + z u$ não tem máximo).
A leitura descuidada das condições no enunciado do lema 4.1 pode levar a interpretações erradas. Qual a diferença entre as duas afirmações a seguir? Afirmação A: para cada $v w$ temos $x_{v w} = 0$ ou $y_{w} - y_{v} + z_{v w} = c_{v w}$ . Afirmação B: temos $x_{v w} = 0$ para cada $v w$ ou temos $y_{w} - y_{v} + z_{v w} = c_{v w}$ para cada $v w$ .
Enuncie o problema do fluxo viável de custo máximo. Escreva o pl do problema. Escreva o pl dual. Como poderíamos usar um algoritmo para o problema 4.A para resolver o problema do fluxo viável de custo máximo?

4.3 Condições de otimalidade

Obtida uma solução

x

do problema do fluxo de custo mínimo (problema 4.A), que informação é possível apresentar para certificar a minimalidade de

c x

? Como o problema 4.A é idêntico ao programa linear

(1)

, qualquer solução viável

(y, z)

do pl dual

(2)

que satisfaça a igualdade

y b + z u = c x

é um excelente certificado.

Alternativamente, podemos exibir uma solução viável

(y, z)

que satisfaz as condições de folgas complementares do lema 4.1. Melhor ainda: podemos omitir

z

e exibir apenas um vetor

y

apropriado, como mostra o seguinte teorema. Para enunciar o teorema, convém usar a palavra potencial para designar qualquer vetor

(y_{v} : v \in V)

com valores em

R

Prova: Para provar a parte se, suponha que $y$ é um potencial que satisfaz as condições 1 e 2. Seja $z$ o vetor definido por $\begin{matrix} (4) & z_{v w} := min (0, c_{v w} - y_{w} + y_{v}) \end{matrix}$

para cada arco $v w$ . Em outras palavras, se $y_{w} - y_{v} \leq c_{v w}$ então $z_{v w} := 0$ , senão $z_{v w} :=$ $c_{v w} - y_{w} + y_{v}$ . Observe que o par $(y, z)$ é solução viável do pl $(2)$ . Além disso, para cada arco $v w$ , temos $x_{v w} = 0$ ou $y_{w} - y_{v} + z_{v w} = c_{v w}$ bem como $x_{v w} = u_{v w}$ ou $z_{v w} = 0$ . O lema 4.1 garante agora que $c x = y b + z u$ e portanto $x$ minimiza $c x$ .

Para provar o somente se, suponha que $x$ minimiza $c x$ . De acordo com o teorema forte da dualidade, existe uma solução viável $(y, z)$ do pl $(2)$ tal que $c x = y b + z u$ . De acordo com o lema 4.1, temos

$x_{v w} = 0$ ou $y_{w} - y_{v} + z_{v w} = c_{v w}$ e
$x_{v w} = u_{v w}$ ou $z_{v w} = 0$

para cada arco $v w$ . Como $y_{w} - y_{v} + z_{v w} \leq c_{v w}$ e $z_{v w} \leq 0$ em $(2)$ , as condições 1 e 2 estão satisfeitas. ■

Para algumas aplicações, é conveniente colocar as condições 1 e 2 do teorema 4.2 na seguinte forma: para cada arco

v w

Custo reduzido

A desigualdade

y_{w} - y_{v} \leq c_{v w}

na condição 2 é familiar: ela caracteriza os arcos relaxados no problema do caminho de custo mínimo (seção 1.2). O número

c_{v w} - (y_{w} - y_{v})

é conhecido como custo reduzido do arco

v w

. Usaremos a notação

{\bar{c}}_{v w} := c_{v w} - (y_{w} - y_{v}) .

[Essa notação deixa a desejar pois esconde a dependência do potencial

y

. Quem sabe deveríamos escrever

c_{v w}^{y}

.] Com essa notação, poderemos apresentar as condições de otimalidade do teorema 4.2 de forma mais memorável: para cada arco

e

Isso tem a seguinte consequência: se

0 < x_{e} < u_{e}

então

{\bar{c}}_{e} = 0

Exemplo 4.2: Considere a rede $(D, b, u, c)$ do exemplo 4.1. Veja novamente a matriz de adjacências de $D$ e o vetor de demandas $b$ . À direita de $b$ temos um potencial $y$ . Mais à direita, um fluxo viável $x$ (diferente dos fluxos do exemplo 4.1), o custo $c$ dos arcos, e o custo reduzido $\bar{c}$ associado a $y$ .

\begin{array}{rrr} p & v & w & q & b & y \\ p & - & 1 & 1 & - & - 2 & - 10 \\ v & - & - & 1 & 1 & - 1 & - 40 \\ w & - & - & - & 1 & + 1 & 0 \\ q & - & - & - & - & + 2 & - 10 \end{array} \begin{array}{lr} p v & p w & v w & v q & w q \\ u & 3 & 3 & 3 & 3 & 3 \\ x & 2 & 0 & 3 & 0 & 2 \\ c & - 30 & + 80 & + 40 & + 90 & - 10 \\ \bar{c} & 0 & + 70 & 0 & + 60 & 0 \end{array}

O fluxo $x$ e o potencial $y$ satisfazem as condições de otimalidade. Portanto, $x$ é um fluxo ótimo e $y$ é um certificado de otimalidade, conforme o teorema 4.2. (Embora isso seja redundante, podemos calcular o vetor $z$ definido em $(4)$ e verificar que $c x = + 40 = y b + z u$ .)

4.4 Ciclos de aumento

Dado um fluxo viável

x

numa rede

(D, b, u, c)

, como obter um novo fluxo viável mais barato? Usaremos um mecanismo análogo ao dos caminhos de aumento do algoritmo de Ford–Fulkerson (seção 2.5).

Para qualquer ciclo

C

D

, seja

É (C)

o conjunto dos arcos diretos de

C

È (C)

o conjunto dos arcos inversos. Um ciclo

C

é compatível com um fluxo viável

x

x_{e} < u_{e}

para cada

e

É (C)

x_{e} > 0

para cada

e

È (C)

A largura de

C

é o maior número

ϵ

tal que

x_{e} + ϵ \leq u_{e}

para cada

e

É (C)

x_{e} - ϵ \geq 0

para cada

e

È (C)

. A operação de enviar

ϵ

unidades de fluxo ao longo do ciclo

C

consiste em somar

ϵ

x_{e}

para cada

e

É (C)

e subtrair

ϵ

x_{e}

para cada

e

È (C)

. Se

ϵ

for menor ou igual à largura de

C

, o envio

ϵ

unidades de fluxo ao longo de

C

produz um novo fluxo viável

x^{'}

. O custo de

x^{'}

será

c x + ϵ c (C)

, sendo

c (C) := c (É (C)) - c (È (C)) .

O número

c (C)

é o custo de

C

. Se esse custo for negativo e

ϵ

for positivo, o fluxo

x^{'}

será mais barato que

x

. Por isso, qualquer ciclo compatível com

x

que tenha custo negativo é chamado ciclo de aumento. (Quem sabe deveríamos dizer ciclo de decremento, já que o custo do fluxo diminui.)

Exemplo 4.3: No exemplo 4.1, o ciclo induzido por $(v, w, q, v)$ é compatível com o fluxo $x$ e tem largura $1$ . O custo do ciclo é $40 - 10 - 90 = - 60$ e portanto o ciclo é de aumento. Se enviarmos $1$ unidade de fluxo ao longo desse ciclo teremos o fluxo viável $x^{'}$ do exemplo 4.1. Observe que $c x^{'} = c x - 60 \times 1 = 240 - 60 = 180$ .

Ainda no exemplo 4.1, o ciclo $(p, v, w, p)$ é compatível com o fluxo $x^{'}$ e tem largura $2$ . O custo do ciclo é $- 30 + 40 - 80 = - 70$ e portanto trata-se de um ciclo de aumento. Se enviarmos $2$ unidades de fluxo ao longo desse ciclo teremos o fluxo viável $x^{″}$ abaixo. Observe que $c x^{″} = c x^{'} - 70 \times 2 = 180 - 140 = 40$ .

\begin{array}{lrrrrr} p v & p w & v w & v q & w q \\ c & - 30 & + 80 & + 40 & + 90 & - 10 \\ x^{″} & 2 & 0 & 3 & 0 & 2 \end{array}

O seguinte teorema mostra que a ausência de ciclos de aumento caracteriza fluxos ótimos:

Prova: Considere inicialmente a parte somente se do teorema. Suponha que o custo de $x$ é mínimo. Se existisse um ciclo de aumento, poderíamos usar esse ciclo, como indicado acima, para obter um novo fluxo viável de custo menor que $c x$ . Portanto, um tal ciclo não existe.

Agora considere a parte se do teorema, ou seja, suponha que não existe ciclo de aumento para $x$ . Gostaríamos de usar os resultados do capítulo 1, desenvolvidos para caminhos e ciclos dirigidos, para mostrar que $x$ tem custo mínimo. Para fazer isso, será preciso construir uma rede auxiliar $(D^{'}, c^{'})$ que chamaremos residual. O grafo dirigido residual $D^{'}$ é definido da seguinte maneira. O conjunto de nós de $D^{'}$ é $D \cup {r}$ , sendo $r$ um novo nó. Para cada arco $v w$ de $D$ tal que $x_{v w} < u_{v w}$ , há um arco $v w$ de custo $c_{v w}^{'} = c_{v w}$ em $D^{'}$ . Para cada arco $v w$ de $D$ tal que $x_{v w} > 0$ , há um

arco $w v$ de custo $c_{w v}^{'} = - c_{v w}$

em $D^{'}$ . (Se $0 < x_{v w} < u_{v w}$ então $D^{'}$ tem arcos $v w$ e $w v$ .) Finalmente, para cada nó $v$ de $D$ , o grafo residual $D^{'}$ tem um arco $r v$ de custo $c_{r v}^{'} = 0$ . É fácil entender a relação entre $D$ e $D^{'}$ : todo ciclo $C$ em $D$ que é compatível com $x$ corresponde a um ciclo dirigido $C^{'}$ em $D^{'}$ , e vice-versa. Ademais, o custo de $C$ em $D$ é igual ao custo de $C^{'}$ em $D^{'}$ .

Submeta a rede $(D^{'}, c^{'})$ , com nó inicial $r$ , ao algoritmo de Ford para caminhos dirigidos de custo mínimo (seção 1.3). Por hipótese, a rede não tem ciclo dirigido de custo negativo. Portanto, de acordo com o teorema de Ford–Bellman (teorema 1.5), o algoritmo produzirá um potencial viável, ou seja, um potencial $y$ tal que $y_{w} - y_{v} \leq c_{v w}^{'}$ para cada arco $v w$ de $D^{'}$ .

Agora considere as propriedades do potencial $y$ no grafo dirigido original $D$ . Se $x_{v w} < u_{v w}$ então $v w$ é um arco de $D^{'}$ e $c_{v w}^{'} = c_{v w}$ , donde $y_{w} - y_{v} \leq c_{v w}$ , e portanto o custo reduzido de $v w$ não é negativo: ${\bar{c}}_{v w} \geq 0 .$ Por outro lado, se $x_{v w} > 0$ então $w v$ é um arco de $D^{'}$ e $c_{w v}^{'} = - c_{v w}$ , donde $y_{v} - y_{w} \leq c_{w v}^{'}$ . Logo $y_{w} - y_{v} \geq c_{v w}$ , e portanto ${\bar{c}}_{v w} \leq 0 .$ Assim, o par $(x, y)$ satisfaz as condições de otimalidade (seção 4.3). Isso garante que $x$ é ótimo. ■

Exemplo 4.4: Seja $D$ o grafo dirigido descrito abaixo por sua matriz de adjacências. À direita da matriz, temos as demandas $b$ . Mais à direita, as capacidades $u$ , os custos $c$ , e um fluxo viável $x$ . O ciclo induzido por $(c, b, a, c)$ é de aumento. Envie $1$ unidade de fluxo ao longo do ciclo. O novo fluxo é ótimo?

\begin{array}{rr} a & b & c & d & b \\ a & - & 1 & 1 & 1 & - 3 \\ b & - & - & 1 & 1 & + 1 \\ c & - & - & - & 1 & + 1 \\ d & - & - & - & - & + 1 \end{array} \begin{array}{lr} a b & a c & a d & b c & b d & c d \\ u & 9 & 9 & 9 & 9 & 9 & 9 \\ c & + 20 & + 20 & + 20 & + 10 & + 10 & + 10 \\ x & 3 & 0 & 0 & 1 & 1 & 0 \end{array}

(No nosso problema 4.A, as capacidades dos arcos são finitas. Mas imagine por um momento que permitíssemos capacidades infinitas. Então a presença de um ciclo de aumento dirigido — um ciclo de aumento

C

com

È (C) = \emptyset

— levaria a fluxos viáveis de custo arbitrariamente negativo e tornaria essa instância ilimitada.)

Soluções inteiras

Muitas aplicações precisam de fluxos

x

que são inteiros e de potenciais

y

que são inteiros. Surpreendentemente, tais fluxos e potencias existem sempre que os parâmetros da rede são inteiros.

Exercícios 4.4

★ Seja $x$ um fluxo viável numa rede $(D, b, u, c)$ . Seja $ϵ$ a largura de um ciclo $C$ compatível com $x$ . Prove que o envio de $ϵ$ unidades de fluxo ao longo de $C$ produz um novo fluxo viável. Prove que o custo do novo fluxo é $c x + c (C) ϵ$ , sendo $c (C) := c (É (C)) - c (È (C))$ .
A figura mostra um fluxo viável $x$ numa rede $(D, b, u, c)$ . Os três números ao lado de cada arco $e$ são $c_{e}, u_{e}, x_{e}$ . O custo do fluxo é $c x = 25$ . Encontre um ciclo de aumento. Calcule um fluxo viável de custo menor que o de $x$ . Parte 2: Exiba um fluxo viável de custo mínimo e um potencial que prove a otimalidade do fluxo. [CCPS fig.4.1]
Considere a rede de fluxo $(D, b, u, c)$ da figura. Ao lado de cada nó $v$ vemos a demanda $b_{v}$ . Ao lado de cada arco $e$ vemos os números $c_{e}, u_{e}, x_{e}$ . Verifique que $x$ é um fluxo viável. Prove que existe um fluxo viável de custo menor que $c x$ ou prove que $x$ é ótimo. [CCPS 4.8]
Rede residual. Considere o exemplo 4.1. Faça uma figura da rede residual correspondente ao fluxo $x$ . Faça uma figura da rede residual correspondente ao fluxo $x^{'}$ .
Caminhos dirigidos disjuntos. Sejam $r$ e $s$ dois nós de um grafo dirigido $D$ . Queremos encontrar uma coleção de $k$ caminhos dirigidos de $r$ a $s$ , sem arcos em comum, que use o menor número possível de arcos. Formule esse problema como um caso particular do problema 4.A. Repita o problema com caminhos dirigidos sem nós em comum exceto $r$ e $s$ . [AMO 11.8]
Considere o grafo dirigido $D$ definido pela matriz de adjacências abaixo. À direita da matriz, uma função-demanda $b$ , as capacidades $u$ e custos $c$ dos arcos. Não confunda o nó $b$ com a função-custo $b$ . Encontre um fluxo ótimo $x$ na rede $(D, b, u, c)$ . Encontre um potencial $y$ que satisfaça as condições de otimalidade do teorema 4.2. Calcule os custos reduzidos $\bar{c}$ . Faça uma tabela de resultados para que seja fácil comparar $x$ com $\bar{c}$ e assim conferir a validade das folgas complementares. [AMO 9.22]
$\begin{array}{rr} a & b & c & d & e & b \\ a & - & 1 & - & - & 1 & - 25 \\ b & - & - & 1 & - & 1 & 0 \\ c & - & - & - & 1 & - & 0 \\ d & - & - & - & - & - & + 25 \\ e & - & - & 1 & - & 1 & 0 \end{array} \begin{array}{lr} a b & a e & b c & b e & c d & e c & e d \\ u & 25 & 20 & 10 & 25 & 20 & 20 & 25 \\ c & + 7 & + 6 & + 4 & + 5 & + 1 & + 2 & + 2 \end{array}$
A figura mostra um potencial $y$ numa rede de fluxo $(D, b, u, c)$ . Ao lado de cada nó $v$ vemos os números $b_{v}$ e $y_{v}$ . Ao lado de cada arco $e$ vemos os números $c_{e}$ e $u_{e}$ . Encontre um fluxo viável $x$ que satisfaça as condições de otimalidade do teorema 4.2. [CCPS 4.9]

4.5 Algoritmo dos ciclos de aumento

O algoritmo abaixo, proposto por Kantorovich em 1942, usa ciclos de aumento para resolver o problema do fluxo de custo mínimo (problema 4.A) como sugerido na seção 4.4. O algoritmo obtém um primeiro fluxo viável resolvendo a instância apropriada do problema de Gale (seção 3.1). A partir daí, cada iteração começa com um fluxo viável

x

e tenta transformar

x

num fluxo viável

x^{'}

de custo menor que

c x

A rotina Gale com argumentos

(D, b, u)

devolve um fluxo

x

que satisfaz

b

e respeita

u

. Se tal fluxo não existe,

x

fica indefinido. Na linha 03, o algoritmo poderia devolver um conjunto de nós que viola as condições de Gale antes de parar.

A rotina CicloDeAumento na linha 05 devolve um ciclo de aumento para

x

. Para implementar a rotina, podemos usar as ideias contidas na prova do teorema 4.3. Se não existe ciclo de aumento,

C

fica indefinido e o fluxo

x

é ótimo.

A rotina EnviaFluxo na linha 12 atualiza

x

enviando

ϵ

unidades de fluxo ao longo do ciclo

C

, conforme discussão no início da seção 4.4.

Número de iterações. Se os vetores

b

u

, e

c

são racionais e a rede

(D, b, u, c)

é viável, o número de iterações do algoritmo Kantorovich é finito, a exemplo do que acontece com o algoritmo de Ford–Fulkerson para o problema do fluxo máximo (seção 2.5).

O algoritmo Kantorovich é útil para redes muito pequenas, quando pode ser executado com lápis e papel. Para redes grandes, entretanto, o algoritmo é ineficiente pois cada iteração consome muito tempo e o número de iterações pode aumentar explosivamente com o número de nós da rede. Isso acontece pelos mesmos motivos que tornam ineficiente o algoritmo de Ford–Fulkerson.

4.6 Algoritmo Simplex para redes de transbordo

O algoritmo Kantorovich (algoritmo dos ciclos de aumento) é lento e ineficiente. Para obter um algoritmo mais rápido, é preciso encontrar uma maneira mais eficiente de procurar ciclos de aumento. Discutiremos uma tal maneira ao longo das próximas seções. A ideia básica é representar o fluxo por meio de uma subárvore da rede. Essa ideia será introduzida a seguir no contexto de uma versão simplificada do problema 4.A, versão esta conhecida como problema do transbordo.

Uma rede de transbordo é uma rede de fluxo em que não há restrições de capacidade nos arcos. [Acredito que a palavra transbordo poderia ser substituída por baldeação. De qualquer forma, não vale a pena discutir a etimologia do termo transshipment.] Mais formalmente, uma rede de transbordo (= transshipment network) é uma rede

(D, b, c)

em que

b

é uma função-demanda nos nós e

c

é uma função-custo nos arcos. O custo de um fluxo

x

é o número

c x

Podemos imaginar que o problema 4.B é o caso especial do problema 4.A em que

u_{e} = \infty

para todo arco

e

. (É preciso forçar um pouco a imaginação, pois o enunciado do problema 4.A não permite arcos de capacidade infinita.)

O primeiro passo para resolver uma instância do problema 4.B é obter algum fluxo que satisfaz

b

. Uma rede

(D, b)

tem um fluxo que satisfaz

b

se e somente se

Um fluxo

x

que satisfaz

b

numa rede de transbordo

(D, b, c)

é ótimo se não existe fluxo

x^{'}

que satisfaz

b

e tem custo menor que o de

x

. A adaptação do teorema 4.2 ao problema 4.B toma a seguinte forma:

Fluxos induzidos por árvores. Vamos procurar uma solução do problema 4.B entre os fluxos que fluem por alguma árvore da rede. Começamos por definir a terminologia necessária.

Uma árvore de um grafo dirigido

D

é uma árvore orientada

T

tal que

V (T) = V (D)

E (T) \subseteq E (D)

. (Num outro contexto, diríamos que

T

é uma árvore geradora de

D

Para garantir que as redes em estudo tenham árvores, restringimos a atenção, daqui em diante, a redes conexas. Para redes não conexas, o problema 4.B pode ser resolvido separadamente em cada componente conexa.

Uma árvore

T

da rede

(D, b)

é viável se

E (T)

contém o suporte de algum fluxo que satisfaz

b

. Como mostra o seguinte lema, existe no máximo um fluxo dotado dessa propriedade:

Diremos que o único fluxo descrito no lema 4.7 é induzido por

T

. Para calcular o fluxo induzido por

T

podemos usar

(5)

. Mas há um algoritmo mais eficiente, que chamaremos FluxoInduzido. Ao receber uma árvore viável

T

, o algoritmo escolhe uma folha

j

T

, aplica o algoritmo recursivament a

T - j

depois de modificar

b

, e finalmente define o valor do fluxo no único arco de

T

que incide em

j

. É um bom exercício escrever o código do algoritmo.

Nem toda árvore de uma rede

(D, b)

é viável. Para provar que uma dada árvore

T

não é viável, basta observar que

b (V) \neq 0

ou exibir um arco

i j

T

tal que

b (T_{j}) ≱ 0

, sendo

T_{j}

a componente conexa de

T - i j

que contém

j

Potenciais induzidos por árvores. Para certificar a otimalidade de um fluxo, usamos um potencial apropriado. Quando o fluxo é induzido por uma árvore, o potencial pode ser facilmente calculado a partir da árvore. Dada uma árvore

T

de uma rede

(D, c)

, um potencial induzido por

T

é qualquer potencial

y

tal que

c_{i j} = y_{j} - y_{i}

para cada arco

i j

T

, como indicamos a seguir.

É fácil calcular um tal potencial. Comece com uma folha

j

T

. Se o único arco incidente a

j

i j

, calcule o potencial

y

T - j

e depois estenda esse potencial a

T

adotando

y_{j} := y_{i} + c_{i j}

. Se o único arco incidente a

j

for

j i

, calcule o potencial

y

T - j

e depois estenda esse potencial a

T

adotando

y_{j} := y_{i} - c_{j i}

. Vamos nos referir a esse algoritmo como PotencialInduzido. Formalizar o algoritmo é um bom exercício.

Um potencial induzido por uma árvore é quase único: se

y

y^{'}

são dois potenciais induzidos então a diferença

y_{i} - y_{i}^{'}

é a mesma para todos os nós

i

. Como trabalhamos apenas com a diferença de potencial entre nós, podemos viver com a ilusão de que existe um só potencial induzido e trocar a expressão um potencial induzido pela expressão o potencial induzido.

O potencial induzido por uma árvore mede os custos de caminhos na árvore, como mostraremos a seguir. O custo de um caminho

P

numa rede

(D, c)

é o número

c (P) :=

c (É (P)) - c (È (P))

, sendo

É (P)

o conjunto dos arcos diretos de

P

È (P)

o conjunto dos arcos inversos.

Prova: Se $P$ tem um só nó então a afirmação é trivialmente verdadeira. Agora suponha que $P = (v_{0}, e_{0}, v_{1}, e_{1}, \dots, e_{k - 1}, v_{k})$ com $k > 0$ . Para cada nó $v_{i}$ , seja $y_{i}$ uma abreviatura de $y_{v_{i}}$ e $c_{i}$ uma abreviatura de $c_{e_{i}}$ . Seja $P^{'}$ o caminho $P - v_{k}$ e suponha, a título de hipótese de indução, que $y_{k - 1} - y_{0} =$ $c (P^{'})$ . Se $e_{k - 1}$ é um arco direto de $P$ , ou seja, se $e_{k - 1} = v_{k - 1} v_{k}$ , então $c (P) =$ $c (P^{'}) + c_{k - 1} =$ $y_{k - 1} - y_{0} + y_{k} - y_{k - 1} =$ $y_{k} - y_{0}$ . Se $e_{k - 1}$ é um arco inverso de $P$ , ou seja, se $e_{k - 1} = v_{k} v_{k - 1}$ , então $c (P) =$ $c (P^{'}) - c_{k - 1} =$ $y_{k - 1} - y_{0} - (y_{k - 1} - y_{k}) =$ $y_{k} - y_{0}$ . ■

Para trazer a ideia de circuito de aumento para o presente contexto, é preciso estabelecer a relação entre o potencial induzido e o custo de ciclos que têm apenas um arco fora de uma dada árvore. Faremos isso no lema 4.9 abaixo, que decorre do lema 4.8.

Dada uma árvore

T

D

e um arco

v w

E (D) ∖ E (T)

, o ciclo fundamental de

T + v w

é o único ciclo do grafo

T + v w

no qual o arco

v w

é direto. O custo desse ciclo fundamental é igual ao custo reduzido

c_{v w} - y_{w} + y_{v}

v w

Algoritmo Simplex-para-transbordo

O terreno está preparado para um algoritmo que resolve o problema 4.B trabalhando apenas com fluxos em árvores. O algoritmo, que chamaremos Simplex-para-transbordo (= TransshipmentSimplex), pode ser visto como uma versão especializada do algoritmo Simplex de programação linear (seção C.4).

O algoritmo Simplex-para-transbordo recebe uma rede de transbordo

(D, b, c)

tal que

D

é conexo e

b (V) = 0

e devolve

No fim da linha 05,

x

é o fluxo induzido por

T

y

é o potencial induzido por

T

, e

{\bar{c}}_{e} = 0

para todo arco

e

T

. No linha 07,

x

y

satisfazem as condições de otimalidade enunciadas no teorema 4.6 e portanto

x

é um fluxo ótimo.

No fim da linha 09, o custo de

C

é negativo em virtude do lema 4.9. Na linha 11, a condição

ϵ = \infty

é equivalente a

È (C) = \emptyset

e portanto o ciclo

C

é dirigido, o que mostra que a rede não tem fluxo de custo mínimo.

Na linha 13,

C

é um ciclo de aumento. Se enviarmos

ϵ

unidades de fluxo ao longo de

C

, o valor do fluxo no arco

h

será reduzido a zero.

Na linha 14, o arco

h

é removido de

T

e o arco

e

é acrescentado a

T

. No fim da linha 14,

T

é uma árvore viável. (Por quê?) Durante a linha 14, o número

ϵ {\bar{c}}_{v w}

é implicitamente subtraído do custo do fluxo

x

No fim da linha 14, poderíamos atualizar os valores de

x

y

, e

\bar{c}

evitando assim a necessidade de recalculá-los no início da iteração seguinte (linhas 03 a 05 do código). (No caso de

x

, por exemplo, bastaria enviar

ϵ

unidades de fluxo ao longo do ciclo

C

Resta discutir a linha 01. Esta é a parte suja do algoritmo. A rotina ÁrvoreViável deve produzir uma árvore viável, conhecida como solução inicial, ou decidir que uma tal árvore não existe e apresentar um conjunto de nós que viola a condições de Gale da seção 3.1. Não há uma maneira limpa de implementar a rotina ÁrvoreViável. Adotaremos o truque sujo clássico de forçar a existência de uma árvore viável. Para isso, suporemos que, em relação a um certo nó

r

da rede,

Essas hipóteses garantem uma árvore viável trivial: o conjunto de arcos da árvore é

E_{1} \cup E_{2}

, sendo

E_{1} := {v r : b (v) < 0}

E_{2} := {r w : b (w) \geq 0}

. Essa árvore inicial é viável uma vez que, por hipótese,

b (V) = 0

Se a rede não tiver todos os arcos exigidos por (a) e (b), basta acrescentar os arcos faltantes atribuindo-lhes custo

\infty

; diremos que esses arcos são artificiais. (É bem verdade que a formulação do problema 4.B supõe que todos os custos são finitos, mas vamos aceitar esse desvio sem fazer escândalo. Poderíamos também trocar

\infty

por um número suficientemente grande.) Se o algoritmo devolver um fluxo cujo suporte contém arcos artificiais, saberemos que a rede original (sem os arcos artificiais) não tem fluxo que satisfaz

b

Exemplo 4.5: Considere a rede de transbordo $(D, b, c)$ descrita a seguir. O grafo dirigido $D$ é dado por sua matriz de adjacências. A função-demanda $b$ e os custos $c$ dos arcos são dadas nas tabelas.

\begin{array}{rr} p & v & w & q & b \\ p & - & 1 & 1 & - & - 3 \\ v & - & - & 1 & 1 & + 2 \\ w & - & - & - & 1 & - 1 \\ q & - & - & - & - & + 2 \end{array} \begin{array}{r} p v & p w & v w & v q & w q \\ c & + 10 & + 30 & + 10 & + 10 & + 10 \end{array}

Suponha que a primeira iteração do algoritmo TransshipmentSimplex começa a árvore $T$ indicada em magenta na tabela abaixo. A tabela também registra o fluxo $x$ e o potencial $y$ induzidos por $T$ , bem como os custos reduzidos $\bar{c}$ . O custo do fluxo é $c x = 70$ .

\begin{array}{lrrrrr} p v & p w & v w & v q & w q \\ x & 2 & 1 & 0 & 0 & 2 \\ \bar{c} & 0 & 0 & - 10 & - 20 & 0 \end{array} \begin{array}{rr} y \\ p & 0 \\ v & + 10 \\ w & + 30 \\ q & + 40 \end{array}

O algoritmo escolhe o arco $v w$ e envia $1$ unidade de fluxo ao longo do ciclo induzido por $(v, w, p, v)$ . O novo fluxo terá custo $c x = 70 - 10 \times 1 = 60$ . O arco $v w$ é acrescentado a $T$ e o arco $p w$ é retirado de $T$ .

A segunda iteração começa com a árvore $T$ indicada abaixo em magenta. A tabela dá o fluxo induzido $x$ , o potencial induzido $y$ , e o custo reduzido $\bar{c}$ . O fluxo tem custo $c x = 60$ .

\begin{array}{lcrrrrr} p v & p w & v w & v q & w q \\ x & 3 & 0 & 1 & 0 & 2 \\ \bar{c} & 0 & + 10 & 0 & - 10 & 0 \end{array} \begin{array}{rr} y \\ p & 0 \\ v & + 10 \\ w & + 20 \\ q & + 30 \end{array}

O algoritmo escolhe o arco $v q$ e envia $1$ unidade de fluxo ao longo do ciclo $(v, q, w, v)$ . O novo fluxo terá custo $c x = 60 - 10 \times 1 = 50$ .

A terceira iteração começa a árvore $T$ , o fluxo $x$ , e o potencial $y$ indicados a seguir:

\begin{array}{lrrrrr} p v & p w & v w & v q & w q \\ x & 3 & 0 & 0 & 1 & 1 \\ \bar{c} & 0 & 0 & + 10 & 0 & 0 \end{array} \begin{array}{rr} y \\ p & 0 \\ v & + 10 \\ w & + 10 \\ q & + 20 \end{array}

Como $\bar{c} \geq 0$ , a execução do algoritmo termina. Para detetar eventuais erros de cálculo cometidos durante a execução do algoritmo, convém verificar que $c x = y b$ .

Número de iterações. No fim da linha 14, o custo do fluxo induzido por

T

c x + ϵ {\bar{c}}_{e}

, sendo

{\bar{c}}_{e} < 0

(veja a seção 4.4 e o lema 4.9). Se

ϵ > 0

, o novo fluxo será mais barato que o anterior e assim o algoritmo terá feito algum progresso. Se

ϵ = 0

, o fluxo não se altera, embora a árvore

T

seja modificada. Se isso acontece, a iteração é considerada degenerada. É claro que uma iteração é degenerada se a árvore

T

no início da iteração tiver um arco vazio, ou seja, um arco

e

tal que

x_{e} = 0

. Diremos que uma tal árvore é degenerada.

É possível, no pior caso, que o algoritmo comece com uma árvore

T_{0}

, execute algumas iterações degeneradas, e volte à árvore $T_{0}$ . Essa sequência de iterações pode então se repetir para sempre e a execução do algoritmo não para mais. Portanto, TransshipmentSimplex não é um algoritmo no sentido pleno da palavra.

Mesmo que não tenhamos iterações degeneradas, entretanto, o número de iterações pode ser muito grande pois o algoritmo pode ser levado a examinar todas as árvores da rede.

Felizmente, esses cenários de pior caso são muito raros. Na prática, o número de iterações é relativamente pequeno. Por isso, o algoritmo é bastante usado em aplicações no mundo real.

Viabilidade forte. Apesar das considerações que acabamos de fazer, é desejável evitar que o número iterações seja infinito. Para isso, basta que no início de cada iteração a árvore viável

T

seja mais que viável, no sentido que passamos a definir.

Antes de começar a execução do algoritmo, escolha um nó

r

(arbitrário mas fixo) para fazer o papel de raiz. No início de cada iteração, para cada nó

j

, seja

P_{j}

o único caminho simples de

r

j

T

. A árvore (viável)

T

é considerada fortemente viável se o fluxo induzido por

T

tem a seguinte propriedade: cada arco vazio de

T

aponta para longe de

r

, ou seja, se

i j

é um arco vazio de

T

então

i j

é um arco direto de

P_{j}

Suponha agora que

T

é fortemente viável no início de uma iteração. Para que a árvore

T - e + h

no início da linha 14 do código também seja fortemente viável, é preciso escolher o arco

h

na linha 13 do código como passamos a explicar. Seja

s

o nó de

C

que está mais próximo de

r

T

, isto é, o último nó comum aos caminhos

P_{v}

P_{w}

. Percorra o ciclo fundamental

C

a partir de

s

e escolha para

h

\begin{matrix} (6) & o primeiro arco em È (C) que tenha x_{h} = ϵ . \end{matrix}

T

é fortemente viável no início de todas as iterações, a execução de TransshipmentSimplex termina depois de um número finito de iterações.

Resta apenas encontrar uma maneira de fazer com que a primeira árvore viável (linha 01 do código) seja fortemente viável. Isso é um bom exercício.

Exemplo 4.6: Considere a rede de transbordo $(D, b, c)$ descrita a seguir. (Não confunda o nó $b$ com a função-demanda $b$ .) O grafo dirigido $D$ é dado por sua matriz de adjacências. Complete a figura usando o gabarito de posição dos nós. A função-demanda $b$ e os custos $c$ dos arcos são dados nas tabelas.

\begin{array}{rr} a & b & c & d & e & f & b \\ a & - & 1 & 1 & - & - & - & - 4 \\ b & - & - & - & - & 1 & - & 0 \\ c & - & - & - & 1 & 1 & - & - 1 \\ d & - & 1 & - & - & - & 1 & 0 \\ e & - & - & - & - & - & 1 & + 1 \\ f & - & - & - & - & - & - & + 4 \end{array} \begin{array}{lrrrrrrrr} a b & a c & b e & c d & c e & d b & d f & e f \\ c & + 20 & + 50 & + 60 & + 30 & + 30 & + 30 & + 20 & + 30 \end{array}

\begin{array}{cccccccc} b & e \\ a & f \\ c & d \end{array}

A primeira iteração do algoritmo TransshipmentSimplex começa com a árvore $T$ indicada abaixo em magenta. A tabela dá o fluxo induzido $x$ , o potencial induzido $y$ , e o correspondente custo reduzido $\bar{c}$ . O custo do fluxo é $c x = 560$ .

\begin{array}{lrrrrrrrr} a b & a c & b e & c d & c e & d b & d f & e f \\ x & 4 & 0 & 5 & 1 & 0 & 1 & 0 & 4 \\ \bar{c} & 0 & + 90 & 0 & 0 & - 90 & 0 & - 100 & 0 \end{array} \begin{array}{rr} y \\ a & + 10 \\ b & + 30 \\ c & - 30 \\ d & 0 \\ e & + 90 \\ f & + 120 \end{array}

O algoritmo escolhe o arco $c e$ e envia $1$ unidade de fluxo ao longo do ciclo induzido por $(c, e, b, d, c)$ . Os arcos $c d$ e $d b$ ficam vazios. O primeiro sai da árvore mas o segundo continua na árvore. O novo fluxo tem custo $c x =$ $560 - 90 \times 1 =$ $470$ .

A segunda iteração começa com os dados a seguir. A árvore viável é degenerada.

\begin{array}{lrrrrrrrr} a b & a c & b e & c d & c e & d b & d f & e f \\ x & 4 & 0 & 4 & 0 & 1 & 0 & 0 & 4 \\ \bar{c} & 0 & 0 & 0 & + 90 & 0 & 0 & - 100 & 0 \end{array} \begin{array}{rr} y \\ a & + 10 \\ b & + 30 \\ c & + 60 \\ d & 0 \\ e & + 90 \\ f & + 120 \end{array}

O algoritmo escolhe o arco $d f$ e portanto o ciclo $(d, f, e, b, d)$ . Apenas $0$ unidades de fluxo podem ser enviadas ao longo do ciclo. A iteração é degenerada. O fluxo $x$ não se altera mas o arco $d f$ é arescentado a $T$ e o arco $d b$ é retirado em $T$ . A terceira iteração começa com os dados indicados a seguir:

\begin{array}{lrrrrrrrr} a b & a c & b e & c d & c e & d b & d f & e f \\ x & 4 & 0 & 4 & 0 & 1 & 0 & 0 & 4 \\ \bar{c} & 0 & 0 & 0 & - 10 & 0 & + 100 & 0 & 0 \end{array} \begin{array}{rr} y \\ a & - 90 \\ b & - 70 \\ c & - 40 \\ d & 0 \\ e & - 10 \\ f & + 20 \end{array}

O algoritmo escolhe o arco $c d$ e envia $1$ unidade de fluxo ao longo do ciclo $(c, d, f, e, c)$ . O novo fluxo tem custo $c x = 470 - 10 \times 1 = 460$ . A quarta iteração começa com os seguintes dados:

\begin{array}{lrrrrrrrr} a b & a c & b e & c d & c e & d b & d f & e f \\ x & 4 & 0 & 4 & 1 & 0 & 0 & 1 & 3 \\ \bar{c} & 0 & - 10 & 0 & 0 & + 10 & + 100 & 0 & 0 \end{array} \begin{array}{rr} y \\ a & - 90 \\ b & - 70 \\ c & - 30 \\ d & 0 \\ e & - 10 \\ f & + 20 \end{array}

O algoritmo escolhe o arco $a c$ e envia $3$ unidades de fluxo ao longo do ciclo $(a, c, d, f, e, b, a)$ . O novo fluxo tem custo $c x = 460 - 10 \times 3 = 430$ . A quinta iteração começa com os seguintes dados:

\begin{array}{lrrrrrrrr} a b & a c & b e & c d & c e & d b & d f & e f \\ x & 1 & 3 & 1 & 4 & 0 & 0 & 4 & 0 \\ \bar{c} & 0 & 0 & 0 & 0 & 0 & + 90 & 0 & + 10 \end{array} \begin{array}{rr} y \\ a & - 80 \\ b & - 60 \\ c & - 30 \\ d & 0 \\ e & 0 \\ f & + 20 \end{array}

Como $\bar{c} \geq 0$ , a execução do algoritmo termina.

Exemplo 4.7: Considere a rede de transbordo $(D, b, c)$ descrita a seguir. O grafo dirigido $D$ é dado por sua matriz de adjacências. (Faça uma figura.) Os custos $c$ , o potencial $y$ , e o custos reduzidos $\bar{c}$ foram omitidos. Adote o nó $r$ como raiz e suponha que ${\bar{c}}_{i j} < 0$ .

\begin{array}{rr} r & i & j & k & l & p & q & b \\ r & - & - & - & - & 1 & - & - & - 2 \\ i & - & - & 1 & - & - & - & 1 & - 1 \\ j & - & - & - & - & - & - & - & + 1 \\ k & - & - & 1 & - & - & - & - & + 1 \\ l & - & - & - & 1 & - & 1 & - & 0 \\ p & - & - & - & - & - & - & - & + 1 \\ q & - & - & - & - & - & 1 & - & 0 \end{array} \begin{array}{lrrrrrrr} r l & i j & k j & l k & l p & q p & i q \\ x & 2 & 0 & 1 & 2 & 0 & 1 & 1 \end{array}

Execute uma iteração do TransshipmentSimplex começando com a árvore viável $T =$ ${r l, k j, l k, l p, q p, i q}$ . Note que $T$ é fortemente viável. O algoritmo escolhe o arco $i j$ pois ${\bar{c}}_{i j} < 0$ . O ciclo fundamental de $T + i j$ é $(i, j, k, l, p, q, i)$ . A largura do ciclo é $1$ . Qualquer um dos arcos $k j$ , $q p$ , $i q$ poderia ser removido de $T$ para dar lugar a $i j$ . Para garantir que a nova árvore viável seja fortemente viável, o algoritmo remove o arco $q p$ .

Exemplo 4.8: Considere a rede de transbordo $(D, b, c)$ descrita a seguir. O grafo dirigido $D$ é dado por sua matriz de adjacências. (Faça uma figura.) A função-demanda $b$ e os custos $c$ dos arcos são dadas nas tabelas. Adote o nó $p$ como raiz. [CCPS fig.4.10]

\begin{array}{rrr} p & v & w & q & b \\ p & - & - & - & - & + 10 \\ v & 1 & - & 1 & 1 & - 10 \\ w & 1 & - & - & 1 & - 10 \\ q & - & - & - & - & + 10 \end{array} \begin{array}{r} v p & w p & v w & v q & w q \\ c & + 10 & + 10 & + 10 & + 10 & + 20 \end{array}

A primeira iteração do TransshipmentSimplex começa com a árvore viável $T$ indicada a seguir (os arcos de $T$ estão destacados em magenta). A árvore é degenerada mas fortemente viável. O fluxo induzido tem custo $c x = 30$ .

\begin{array}{lrrrrr} v p & w p & v w & v q & w q \\ x & 1 & 0 & 0 & 0 & 1 \\ \bar{c} & 0 & + 10 & 0 & - 20 & 0 \end{array} \begin{array}{rr} y \\ p & 0 \\ v & - 10 \\ w & 0 \\ q & + 20 \end{array}

O algoritmo escolhe o arco $v q$ . A sequência de nós do correspondente ciclo fundamental, escrita a partir do nó mais próximo da raiz, é $(v, q, w, v)$ . Como $ϵ = 0$ , a iteração é degenerada. O envio de $0$ unidades de fluxo ao longo do ciclo não altera o fluxo mas altera a árvore viável.

A segunda iteração começa com uma árvore viável degenerada mas fortemente viável. O fluxo induzido tem custo $c x = 30$ .

\begin{array}{lrrrrr} v p & w p & v w & v q & w q \\ x & 1 & 0 & 0 & 0 & 1 \\ \bar{c} & 0 & - 10 & + 20 & 0 & 0 \end{array} \begin{array}{rr} y \\ p & 0 \\ v & - 10 \\ w & - 20 \\ q & 0 \end{array}

O algoritmo escolhe o arco $w p$ . O correspondente ciclo fundamental, a partir do nó mais próximo da raiz, é $(p, v, q, w, p)$ . Temos $ϵ = 1$ e o arco $v p$ faz o papel de $h$ . O envio de $1$ unidade de fluxo ao longo do ciclo produz um novo fluxo de custo $c x = 30 - 10 \times 1 = 20$ .

A terceira iteração começa com uma árvore viável degenerada mas fortemente viável. (Se a iteração anterior tivesse escolhido $h = w q$ , a árvore não seria fortemente viável.)

\begin{array}{lrrrrr} v p & w p & v w & v q & w q \\ x & 0 & 10 & 0 & 10 & 0 \\ \bar{c} & + 10 & 0 & 0 & 0 & 0 \end{array} \begin{array}{rr} y \\ p & 0 \\ v & 0 \\ w & - 10 \\ q & + 10 \end{array}

Como $\bar{c} \geq 0$ , a execução do algoritmo termina.

Exercícios 4.6

★ Prove o teorema 4.6 a partir do teorema 4.2.
Em que condições uma instância do problema do transbordo (problema 4.B) é inviável? Em que condições é ilimitada?
Seja $x$ um fluxo num grafo dirigido conexo $D$ . Suponha que todo ciclo (dirigido ou não) em $D$ tem um arco vazio, isto é, um arco $e$ tal que $x_{e} = 0$ . Mostre que existe uma árvore $T$ de $D$ tal que o suporte de $x$ é subconjunto de $E (T)$ .
★ Fluxo viável implica fluxo arbóreo. Suponha que uma rede conexa $(D, b)$ tem um fluxo que satisfaz $b$ . Prove que o suporte de algum fluxo que satisfaz $b$ é subconjunto de alguma árvore da rede. Parte 2: Suponha que uma rede conexa $(D, b, c)$ tem um fluxo ótimo e prove que o suporte de algum fluxo ótimo é subconjunto de alguma árvore da rede.
★ Complete os detalhes da prova do lema 4.7.
★ FluxoInduzido. Escreva um algoritmo que receba uma árvore viável $T$ de uma rede $(D, b)$ e devolva o único fluxo em $T$ que satisfaz $b$ .
Escreva uma versão completa do algoritmo FluxoInduzido. O algoritmo deve receber uma árvore $T$ e uma função-demanda $b$ tal que $b (V) = 0$ e devolver o único fluxo em $T$ que satisfaz $b$ ou uma prova de que tal fluxo não existe. A prova consiste em um arco $k l$ de $T$ tal que $b (T_{l}) < 0$ .
★ PotencialInduzido. Escreva um algoritmo que receba uma árvore $T$ de uma rede $(D, c)$ e devolva o potencial induzido por $T$ .

Mais exercícios

Custo de arcos artificiais, Seja $(D, b, c)$ uma rede de transbordo com arcos arficiais. Atribua custo $1 + | V | max {| c_{e} | : e \in E}$ a cada arco artificial. Suponha que o algoritmo Simplex-para-Transbordo termina com fluxo não nulo em algum arco artificial. Mostre que a instância original do problema (antes da introdução dos arcos artificiais) não tem fluxo viável. [CCPS 4.21]
Resolva a instância do problema do transbordo indicada na figura. Use o algoritmo TransshipmentSimplex. Os números junto aos nós são as demandas $b$ . Os números nos arcos são os custos $c$ . Comece com o fluxo $x$ induzido pela árvore viável $T$ representada pelas linhas contínuas. [CCPS 4.22]
Solução inicial no Simplex-para-transbordo. Escreva uma implementação da rotina ÁrvoreViável sob as hipóteses (a) e (b). Prove que sua implementação está correta.
Solução inicial no Simplex-para-transbordo. Discuta a seguinte ideia de implementação da rotina ÁrvoreViável. 1. Calcule um fluxo $x$ em $(D, b)$ que satisfaz $b$ como sugere a seção 3.1, que trata do problema de Gale. (É assim que começa o algoritmo Kantorovich.) 2. Se houver um ciclo em que todos os arcos têm fluxo positivo, envie fluxo ao longo do ciclo de modo a anular o fluxo em algum arco. 3. Repita o processo até que o suporte de $x$ seja subconjunto do conjunto de arcos de uma árvore). 4. Extraia uma árvore $T$ do suporte de $x$ .
Árvore fortemente viável inicial. Encontre uma maneira de construir a árvore viável $T$ na linha 01 de TransshipmentSimplex de modo que ela seja fortemente viável.
Mostre como representar $T$ de maneira eficiente no algoritmo TransshipmentSimplex. Mostre como os valores $x$ , $y$ , e $\bar{c}$ podem ser calculados, a cada iteração, a partir dos valores de $x$ , $y$ , e $\bar{c}$ na iteração anterior (evitando assim que os valores sejam calculadas diretamente a partir de $T$ ). [CCPS 4.23]
No algoritmo TransshipmentSimplex, suponha que $T$ é fortemente viável no início de uma iteração em que $ϵ = 0$ . Mostre que $h$ estará em $P_{w}$ (e não em $P_{v}$ ). Mostre que $h$ será o último arco direto vazio de $P_{w}$ .
Exemplo 4.6. Analise o exemplo 4.6. Adote o nó $d$ como raiz e verifique que no início de cada iteração do algoritmo a árvore viável $T$ é fortemente viável.
Mostre que toda árvore não-degenerada é fortemente viável.
De fortemente viável a fortemente viável. Suponha que $T$ é fortemente viável e $h$ é escolhido de acordo com a regra $(6)$ . Mostre que no início da linha 14 de TransshipmentSimplex a árvore viável $T + e - h$ é fortemente viável.
O número de iterações é finito. Seja $r$ a raiz de $D$ e defina $y$ na linha 04 de TransshipmentSimplex de modo que $y_{r} = 0$ (e portanto $y_{v} = c (P_{v})$ para cada $v$ ). Suponha que $T$ é fortemente viável no início de uma iteração e seja $Y$ o valor da soma $\sum (y_{v} : v \in V)$ no fim da linha 04. Suponha que $ϵ$ é nulo nessa iteração. Prove que na próxima iteração, no fim da linha 04, a soma $\sum (y_{v} : v \in V)$ será menor que $Y$ . Deduza daí que o número de iterações degeneradas é finito.

4.7 Algoritmo Simplex para redes arbitrárias

O algoritmo Simplex-para-redes (= Network Simplex) é uma generalização do algoritmo Simplex-para-transbordo discutido na seção anterior. O algoritmo resolve o problema do fluxo de custo mínimo (problema 4.A). Esse é o algoritmo mais usado na prática para resolver o problema.

Tripartições arbóreas e fluxo induzido. Para apresentar o Simplex-para-redes, é preciso generalizar os conceitos que introduzimos para tratar do Simplex-para-transbordo.

Uma tripartição arbórea de um grafo

D

é um terno

(T, L, U)

em que

T

é uma árvore de

D

(E (T), L, U)

é uma partição do conjunto de arcos de

D

. Para garantir que as redes em estudo tenham árvores, restringimos a atenção a redes conexas daqui em diante.

Como no início do capítulo, um fluxo numa rede

(D, b, u)

é viável se satisfaz

b

e respeita

u

. Em relação a um fluxo viável

x

, diremos que um arco

e

está vazio se

x_{e} = 0

e está cheio se

x_{e} = u_{e}

. (Se

u_{e} = 0

, o arco

e

está simultaneamente vazio e cheio. Pode ser conveniente remover tais arcos da rede — o que certamente não afeta o problema 4.A — e passar a supor que

u_{e} > 0

para cada arco

e

Uma tripartição arbórea

(T, L, U)

da rede

(D, b, u)

é viável se algum fluxo viável em

(D, b, u)

deixa todos os arcos de

L

vazios e todos os arcos de

U

cheios. (Nada impede que esse mesmo fluxo deixe alguns arcos de

T

vazios e alguns arcos de

T

cheios.) Segue do lema 4.7 que existe no máximo um tal fluxo:

Dizemos que o único fluxo viável a que se refere o lema 4.10 é induzido por

(T, L, U)

, Se o fluxo induzido deixa algum arco de

T

vazio ou algum arco cheio, dizemos que a tripartição

(T, L, U)

é degenerada.

Potenciais induzidos por tripartições arbóreas. Numa rede

(D, c)

, um potencial

y

é induzido por uma tripartição arbórea

(T, L, U)

c_{v w} = y_{w} - y_{v}

para cada arco

v w

T

. Tal como no caso das redes de transbordo, toda tripartição arbórea tem um potencial induzido e esse potencial é essencialmente único.

Seja

(T, L, U)

uma tripartição arbórea do grafo

D

. Para cada

e

L

, o ciclo fundamental de

T + e

é o único ciclo em

T + e

no qual

e

é um arco direto. Para cada

e

U

, o ciclo fundamental de

T + e

é o único ciclo em

T + e

no qual

e

é um arco inverso. O seguinte lema generaliza o lema 4.9:

Algoritmo Simplex-para-redes

Ao receber uma rede

(D, b, u, c)

com

D

conexo e

b (V) = 0

, o algoritmo Simplex-para-redes produz uma tripartição arbórea viável

(T, L, U)

e um potencial

y

que satisfazem as condições

sendo

\bar{c}

o custo reduzido associado a

y

. De acordo com teorema 4.2 (veja a formulação alternativa do teorema), o fluxo

x

induzido por

(T, L, U)

é ótimo.

O algoritmo consiste em duas cópias do algoritmo Simplex-para-transbordo trabalhando simultaneamente: uma cópia normal, idêntica à discutida na seção anterior, que cuida da restrição

x \geq 0

, e uma cópia invertida que cuida da restrição

x \leq u

NetworkSimplex

(D, b, u, c)

⊳

D

conexo e

b (V) = 0

01 .

(T, L, U) \leftarrow

TripartiçãoArbóreaViável

(D, b, u)

02 . se

(T, L, U)

é indefinida

03 .ooo então pare

⊳

rede inviável

04 . repita

05 .ooo seja

x

o fluxo induzido por

(T, L, U)

06 .ooo seja

y

um potencial induzido por

(T, L, U)

07 .ooo seja

\bar{c}

o custo reduzido associado a

y

08 .ooo se

{\bar{c}}_{e} \geq 0

quando

e \in L

{\bar{c}}_{e} \leq 0

quando

e \in U

09 .oooooo então devolva

(T, L, U)

y

e pare

⊳

fluxo ótimo

10 .ooo escolha

e \in L

tal que

{\bar{c}}_{e} < 0

e \in U

tal que

{\bar{c}}_{e} > 0

11 .ooo seja

C

o ciclo fundamental de

T + e

12 .ooo

ϵ \leftarrow min (u_{h} - x_{h} : h \in É (C))

13 .ooo

ϵ^{'} \leftarrow min (x_{h} : h \in È (C))

14 .ooo se

ϵ < ϵ^{'}

15 .oooooo então escolha

h

É (C)

tal que

u_{h} - x_{h} = ϵ

16 .oooooo senão escolha

h

È (C)

tal que

x_{h} = ϵ^{'}

17 .ooo

T \leftarrow T + e - h

18 .ooo se

e \in L

então

L \leftarrow L - e

senão

U \leftarrow U - e

19 .ooo se

h \in É (C)

então

U \leftarrow U + h

senão

L \leftarrow L + h

No começo de cada iteração (linha 04),

(T, L, U)

é uma tripartição arbórea viável.

A rotina TripartiçãoArbóreaViável na linha 01 deve produzir uma tripartição arbórea viável. Se tal tripartição não existe, a rede não admite fluxo viável.

Não há uma maneira limpa de implementar a rotina TripartiçãoArbóreaViável. Um truque sujo clássico consiste em escolher um nó

r

, arbitrário mas fixo, e acrescentar à rede (a) um arco

v r

para cada nó

v \neq r

tal que

b (v) < 0

e (b) um arco

r w

para cada nó

w \neq r

tal que

b (w) \geq 0

. Esses arcos artificiais devem ter capacidade infinita e custo infinito. Feito isso, considere a árvore

T

com conjunto de arcos

E_{1} \cup E_{2}

, sendo

E_{1} := {v r : b (v) < 0}

E_{2} := {r w : b (w) \geq 0}

, e seja

L

conjunto

E (D) ∖ E (T)

. Agora,

(T, L, \emptyset)

é uma tripartição arbórea viável.

Se o algoritmo NetworkSimplex terminar com um fluxo cujo suporte contém arcos artificiais, saberemos que a rede original não tem fluxo viável.

Exemplo 4.9: Considere a rede $(D, b, u, c)$ descrita a seguir. O grafo dirigido $D$ é dado por sua matriz de adjacências. A função-demanda $b$ e os custos $c$ dos arcos são dadas nas tabelas.

\begin{array}{rr} p & v & w & q & b \\ p & - & 1 & 1 & - & - 4 \\ v & - & - & 1 & 1 & 0 \\ w & - & - & - & 1 & + 2 \\ q & - & - & - & - & + 2 \end{array} \begin{array}{lrrrrr} p v & p w & v w & v q & w q \\ u & \infty & \infty & 1 & \infty & \infty \\ c & + 10 & + 20 & + 8 & + 20 & + 20 \end{array}

A primeira iteração do algoritmo NetworkSimplex começa com a tripartição arbórea viável $(T, L, U)$ indicada abaixo. Os arcos de $T$ estão indicados em magenta, os arcos de $L$ estão sublinhados, e $U$ é vazio. Veja na tabela o fluxo $x$ e o potencial $y$ induzidos pela tripartição.

\begin{array}{r} p v & p w & \underset{―}{v w} & v q & \underset{―}{w q} \\ x & 2 & 2 & 0 & 2 & 0 \\ \bar{c} & 0 & 0 & - 2 & 0 & + 10 \end{array} \begin{array}{rr} y \\ p & 0 \\ v & + 10 \\ w & + 20 \\ q & + 30 \end{array}

O algoritmo escolhe o arco $v w$ e envia $1$ unidades de fluxo ao longo do ciclo induzido por $(v, w, p, v)$ . O arco $v w$ fica cheio e é transferido de $L$ para $U$ . A tripartição $(T, L, U)$ não se altera. O novo fluxo terá custo $c x = 100 - 2 \times 1 = 98$ .

A segunda iteração começa com a tripartição arbórea $(T, L, U)$ indicada abaixo com uma barra acima dos arcos de $U$ . [Pode ser necessário aumentar ou diminuir (Ctrl+ ou Ctrl-) o tamanho da fonte no seu browser para que a barra fique visível.] O fluxo tem custo $c x = 98$ .

\begin{array}{lrrrrr} p v & p w & \overset{―}{v w} & v q & \underset{―}{w q} \\ x & 3 & 1 & 1 & 2 & 0 \\ \bar{c} & 0 & 0 & - 2 & 0 & + 10 \end{array} \begin{array}{rr} y \\ p & 0 \\ v & + 10 \\ w & + 20 \\ q & + 30 \end{array}

Como ${\bar{c}}_{e} \geq 0$ para todo $e$ em $L$ e ${\bar{c}}_{e} \leq 0$ para todo $e$ em $U$ , o fluxo $x$ é ótimo e a execução do algoritmo termina.

Por via dúvidas, convém verificar que $c x =$ $y b + z u$ . (Essa é uma boa maneira de detetar eventuais erros de cálculo cometido durante a execução do algoritmo.) O vetor $z_{e} = min (0, {\bar{c}}_{e})$ está indicado abaixo:

\begin{array}{r} p v & p w & \overset{―}{v w} & v q & \underset{―}{w q} \\ z & 0 & 0 & - 2 & 0 & 0 \end{array}

Portanto, $c x = 98 = 100 - 2 = y b + z u$ , como deveria ser.

Consumo de tempo. O algoritmo NetworkSimplex, tal como TransshipmentSimplex, pode executar um número infinito de iterações, embora tal evento seja muito raro na prática. Para evitar que isso aconteça, basta fazer o seguinte: (i) antes de iniciar a execução do algoritmo, escolha um nó

r

como raiz; (ii) adote

y_{r} = 0

em todas as iterações; (iii) tome providências para que a tripartição arbórea

(T, L, U)

seja fortemente viável no início de cada iteração.

Uma tripartição arbórea viável

(T, L, U)

é fortemente viável se o fluxo induzido pela tripartição tem a seguinte propriedade: cada arco

i j

T

que está vazio aponta para longe da raiz (ou seja,

i j

é um arco de

P_{j}

), e cada arco

i j

T

que está cheio aponta na direção da raiz (ou seja,

i j

é um arco de

P_{i}

Exercícios 4.7

Seja $(D, b)$ uma rede conexa. Mostre que um fluxo $x$ é induzido por uma tripartição arbórea se e somente se todo ciclo de $D$ tem um arco vazio ou um arco cheio (ou ambos).
★ Fluxo viável implica fluxo arbóreo. Suponha que uma rede $(D, b, u)$ tem um fluxo viável e prove que a rede também tem um fluxo viável induzido por alguma tripartição arbórea. Parte 2: Suponha que uma rede $(D, b, u, c)$ tem um fluxo ótimo e prove que a rede também tem um fluxo ótimo induzido por alguma tripartição arbórea. [CCPS 4.27]
Prove o lema 4.10.
Escreva um algoritmo que receba uma tripartição arbórea $(T, L, U)$ de uma rede $(D, b, u)$ , decida se a tripartição é viável, e em caso afirmativo calcule o fluxo induzido pela tripartição.
Dê condições necessárias e suficientes para que uma tripartição arbórea $(T, L, U)$ seja viável.

Mais exercícios

★ Prove o lema 4.11.
★ É possível ter $h = e$ no começo da linha 17 do NetworkSimplex? Como o algoritmo se comporta nesse caso?
Tripartição arbórea inicial. Eis um truque feio mas efetivo para calcular a tripartição $(T, L, U)$ inicial na linha 01 de NetworkSimplex. Antes de invocar o algoritmo, acrescente a $D$ um novo nó $r$ e novos arcos da seguinte maneira: para cada nó $v$ com $b_{v} < 0$ , acrescente um novo arco $v r$ ; para cada $v$ tal que $b_{v} \geq 0$ , acrescente um novo arco $r v$ . Seja $B^{+}$ o conjunto dos novos arcos do tipo $v r$ e $B^{-}$ o conjunto dos novos arcos do tipo $r v$ . Cada novo arco deve ter custo $M$ e capacidade $\infty$ . A constante $M$ deve ser positiva e muito grande. Seja $T := B^{+} \cup B^{-}$ . Adote fluxo $x_{v r} := - b_{v}$ para cada $v r \in B^{+}$ e fluxo $x_{r v} := b_{v}$ para cada $r v \in B^{-}$ . Faça $L$ igual ao conjunto dos arcos originais e faça $U$ igual a $\emptyset$ . A tripartição arbórea $(T, L, U)$ é fortemente viável se tomarmos $r$ como raiz. Como o custo $M$ é muito grande, nenhum dos arcos artificiais estará na árvore produzida por NetworkSimplex.

Capítulo 4
Fluxo de custo mínimo

4.1 O problema

Exercícios 4.1

4.2 Programação linear

Exercícios 4.2

4.3 Condições de otimalidade

Custo reduzido

Exercícios 4.3

4.4 Ciclos de aumento

Soluções inteiras

Exercícios 4.4

4.5 Algoritmo dos ciclos de aumento

Exercícios 4.5

4.6 Algoritmo Simplex para redes de transbordo

Algoritmo Simplex-para-transbordo

Exercícios 4.6

Mais exercícios

4.7 Algoritmo Simplex para redes arbitrárias

Algoritmo Simplex-para-redes

Exercícios 4.7

Mais exercícios

Capítulo 4Fluxo de custo mínimo

4.1 O problema

Exercícios 4.1

4.2 Programação linear

Exercícios 4.2

4.3 Condições de otimalidade

Custo reduzido

Exercícios 4.3

4.4 Ciclos de aumento

Soluções inteiras

Exercícios 4.4

4.5 Algoritmo dos ciclos de aumento

Exercícios 4.5

4.6 Algoritmo Simplex para redes de transbordo

Algoritmo Simplex-para-transbordo

Exercícios 4.6

Mais exercícios

4.7 Algoritmo Simplex para redes arbitrárias

Algoritmo Simplex-para-redes

Exercícios 4.7

Mais exercícios

Capítulo 4
Fluxo de custo mínimo