Otimização Combinatória | Dicionário | Índice remissivo

Capítulo 4
Fluxo de custo mínimo

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 $\Rplus$, e uma função-custo $(c_e : e\in E)$ com valores em $\R$.  [Poderíamos escrever $b\in \R^{V}$, $u\in \Rplus^{E}$ 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$ e $c$ não têm restrição de sinal.

(Consulte o índice remissivo e os apêndices para conferir as definições de termos técnicos.)

4.1 O problema

Um fluxo numa rede $(D,b,u)$ é qualquer vetor $(x_e : e\in E)$ com valores em $\Rplus$.  Um fluxo $x$ respeita $u$ se $x \leq u$ e satisfaz $b$ se \[ \xinout \ = \ b\,\text{.} \]

(Como na seção 2.1, para cada nó $v$,  $\xinout(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 $cx$. Convém lembrar que $c$ não tem restrições de sinal: podemos ter $c_e \lt 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 \hspace{2.5ex} \text{e} \hspace{2.5ex} b(X)\leq \uin(X) \] para todo subconjunto $X$ de $V$. (Essas condições também podem ser escritas de maneira mais simétrica: $-\uout(X) \leq \text{}$ $b(X) \leq \text{}$ $\uin(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 $cx = 240$  e  $cx' = 180$. Observe como é fácil conferir a viabilidade e o custo de um fluxo percorrendo as linhas da tabela.

\[ \begin{array}[t]{*{5}{r}@{\qquad}r} & p & v & w & q & \hf b \\[0.5ex] p & - & 1 & 1 & - & \hf -2 \\ v & - & - & 1 & 1 & \hf -1 \\ w & - & - & - & 1 & \hf +1 \\ q & - & - & - & - & \hf +2 \end{array} \hspace{5ex} \begin{array}[t]{l*{5}{r}} & pv & pw & vw & vq & wq \\[0.5ex] \hline u & 3 & 3 & 3 & 3 & 3 \\ x & 0 & 2 & 0 & 1 & 1 \\ x'& 0 & 2 & 1 & 0 & 2 \\ c & \hb-30 & \hb +80 & \hb +40 & \hb +90 & \hb -10 \end{array} \]

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{equation}\label{lp:min-cost-flow} \begin{array}{rcl@{\quad}l} \text{minimize} \hspace{2ex} cx & \\[0.4ex] \text{sujeito a} \hspace{2ex} \xinout(v) & \hb = & \hb b_v & \text{para cada $v\in V$}\\ x_{e} & \hb \leq & \hb u_{e} & \text{para cada $e\in E$}\\ x_{e} & \hb \geq & \hb 0 & \text{para cada $e\in E$.} \end{array} \end{equation}

(Convém lembrar que podemos ter $c_e \geq 0$ em alguns arcos e $c_e \lt 0$ em outros.)  Esse programa linear pode ser escrito assim em termos da matriz de incidências $A$ do grafo $D$: \[ \begin{split} \text{minimize} \hspace{2ex} cx & \\ \text{sujeito a} \hspace{2ex} Ax & \ = \ b \\ x & \ \leq \ u \\ x & \ \geq \ 0\,\text{.} \end{split} \]

O dual desse pl consiste em encontrar vetores reais $(y_v : v \in V)$ e $(z_e : e \in E)$ que \[ \begin{split} \text{maximizem} \hspace{2ex} yb + zu & \\ \text{sujeito a} \hspace{2ex} yA + z & \ \leq \ c \\ z & \ \leq \ 0 \end{split} \]

e esse dual pode ser escrito por extenso assim: encontrar $y$ e $z$ que \begin{equation}\label{lp:min-cost-flow-dual} \begin{array}{rcl@{\quad}l} \text{maximizem} \hspace{2ex} yb + zu & \\ \text{sujeito a} \hspace{2ex} y_w - y_v + z_{vw} & \hb \leq & \hb c_{vw} & \hb \text{para $vw\in E$}\\ z_{vw} & \hb \leq & \hb 0 & \hb \text{para $vw\in E$.} \end{array} \end{equation}

Para qualquer solução viável $x$ do pl \eqref{lp:min-cost-flow} e qualquer solução viável $(y,z)$ do pl \eqref{lp:min-cost-flow-dual} temos então \begin{equation}\label{eq:weak-duality-proof} \begin{split} cx & \ \geq \ (yA + z) x \\ & \ = \ (yA)x + zx \\ & \ = \ y(Ax)+zx \\ & \ \geq \ yb + zu\,\text{.} \end{split} \end{equation}

Se $cx = yb + zu$ então $x$ é solução ótima de \eqref{lp:min-cost-flow} e $(y,z)$ é solução ótima de \eqref{lp:min-cost-flow-dual}. 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 $cx=yb+zu$. 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 $vw$,

1.   se  $x_{vw} > 0$  então  $y_w - y_v + z_{vw} = c_{vw}$  e
2.   se  $x_{vw} \lt u_{vw}$  então  $z_{vw} = 0$.

Segue daí imediatamente que se  $0 \lt x_{vw} \lt u_{vw}$  então  $y_w - y_v = c_{vw}$.

Algoritmo. Poderíamos resolver o problema 4.A submetendo o programa linear \eqref{lp:min-cost-flow} 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 \eqref{lp:min-cost-flow}.

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 $cx$?  Como o problema 4.A é idêntico ao programa linear \eqref{lp:min-cost-flow}, qualquer solução viável $(y,z)$ do pl dual \eqref{lp:min-cost-flow-dual} que satisfaça a igualdade $yb+zu = cx$ é 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$.

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

1. se  $x_{vw} > 0$  então  $y_w - y_v \geq c_{vw}$   e
2. se  $x_{vw} \lt u_{vw}$  então  $y_w - y_v \leq c_{vw}$.

Custo reduzido

A desigualdade $y_w - y_v \leq c_{vw}$ 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_{vw}-(y_w-y_v)$ é conhecido como custo reduzido do arco $vw$. Usaremos a notação \[ \cy_{vw} := c_{vw} - (y_w - y_v)\text{.} \]

[Essa notação deixa a desejar pois esconde a dependência do potencial $y$. Quem sabe deveríamos escrever $c^y_{vw}$.]  Com essa notação, poderemos apresentar as condições de otimalidade do teorema 4.2 de forma mais memorável: para cada arco $e$,

1. se  $x_{e} > 0$  então  $\cy_{e} \leq 0$   e
2. se  $x_{e} \lt u_{e}$  então  $\cy_{e} \geq 0$.

Isso tem a seguinte consequência:  se  $0 \lt x_{e} \lt u_{e}$  então  $\cy_{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 $\cy$ associado a $y$.

\[ \begin{array}[t]{*{5}{r}rr} & p & v & w & q & b & y \\[0.5ex] p & - & 1 & 1 & - & \he -2 & \he -10 \\ v & - & - & 1 & 1 & -1 & -40 \\ w & - & - & - & 1 & +1 & 0 \\ q & - & - & - & - & +2 & -10 \end{array} \hspace{4ex} \begin{array}[t]{l*{5}{r}} & pv & pw & vw & vq & wq \\[0.5ex] \hline u & 3 & 3 & 3 & 3 & 3 \\ x & 2 & 0 & 3 & 0 & 2 \\ c & \hb -30 & \hb +80 & \hb +40 & \hb +90 & \hb -10 \\ \cy & 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 \eqref{eq:definition-of-z} e verificar que $cx = +40 = yb +zu$.)

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$ em $D$, seja $\Eforward(C)$ o conjunto dos arcos diretos de $C$ e $\Ereverse(C)$ o conjunto dos arcos inversos. Um ciclo $C$ é compatível com um fluxo viável $x$ se $x_e \lt u_e$ para cada $e$ em $\Eforward(C)$ e $x_e > 0$ para cada $e$ em $\Ereverse(C)$.

A largura de $C$ é o maior número $\epsilon$ tal que $x_e + \epsilon \leq u_e$ para cada $e$ em $\Eforward(C)$ e $x_e-\epsilon \geq 0$ para cada $e$ em $\Ereverse(C)$. A operação de enviar $\epsilon$ unidades de fluxo ao longo do ciclo $C$ consiste em somar $\epsilon$ a $x_e$ para cada $e$ em $\Eforward(C)$ e subtrair $\epsilon$ de $x_e$ para cada $e$ em $\Ereverse(C)$. Se $\epsilon$ for menor ou igual à largura de $C$, o envio $\epsilon$ unidades de fluxo ao longo de $C$ produz um novo fluxo viável $x'$. O custo de $x'$ será $cx + \epsilon c(C)$, sendo \[ c(C) := c(\Eforward(C)) - c(\Ereverse(C))\text{.} \]

O número $c(C)$ é o custo de $C$. Se esse custo for negativo e $\epsilon$ 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.)

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

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}[t]{*{5}{r}@{\qquad}r} & a & b & c & d & b \\[0.5ex] a & - & 1 & 1 & 1 & \he -3 \\ b & - & - & 1 & 1 & +1 \\ c & - & - & - & 1 & +1 \\ d & - & - & - & - & +1 \end{array} \hspace{6ex} \begin{array}[t]{l*{6}{r}} & ab & ac & ad & bc & bd & cd \\[0.5ex] \hline u & 9 & 9 & 9 & 9 & 9 & 9 \\ c & \hb +20 & \hb +20 & \hb +20 & \hb +10 & \hb +10 & \hb +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 $\Ereverse(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.

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 $cx$. 

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 Ciclo­De­Aumento 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 Potencial na linha 07 recebe um fluxo ótimo $x$ e calcula um potencial $y$ que satisfaz as condições de otimalidade do teorema 4.2.

A rotina Envia­Fluxo na linha 12 atualiza $x$ enviando $\epsilon$ 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 $cx$.

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

1. $b(V) = 0$ e
2. $b(X)\leq 0$ para todo $X\subseteq V$ tal que $\cutin(X)=\emptyset$.

Isso é consequência do que observamos acima sobre o problema 4.A bem como de um exercício na seção 3.1.

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:

Deduzir o teorema 4.6 do teorema 4.2 é um bom exercício.

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 $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 \eqref{eq:flow-induced-by-tree}. Mas há um algoritmo mais eficiente, que chamaremos Fluxo­Induzido. Ao receber uma árvore viável $T$, o algoritmo escolhe uma folha $j$ de $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 $ij$ de $T$ tal que $b(T_j) \not\geq 0$, sendo $T_{j}$ a componente conexa de $T-ij$ 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_{ij} = y_j - y_i$  para cada arco $ij$ de $T$, como indicamos a seguir.

É fácil calcular um tal potencial. Comece com uma folha $j$ de $T$. Se o único arco incidente a $j$ é $ij$, calcule o potencial $y$ de $T-j$ e depois estenda esse potencial a $T$ adotando $y_j := y_i+c_{ij}$. Se o único arco incidente a $j$ for $ji$, calcule o potencial $y$ de $T-j$ e depois estenda esse potencial a $T$ adotando $y_j := y_i - c_{ji}$. 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$ e $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) := \text{}$ $c(\Eforward(P)) - c(\Ereverse(P))$, sendo $\Eforward(P)$ o conjunto dos arcos diretos de $P$ e $\Ereverse(P)$ o conjunto dos arcos inversos.

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$ de $D$ e um arco $vw$ de $E(D)\setm E(T)$, o ciclo fundamental de $T+vw$ é o único ciclo do grafo $T+vw$ no qual o arco $vw$ é direto. O custo desse ciclo fundamental é igual ao custo reduzido  $c_{vw}-y_w+ y_v$  de $vw$:

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 (= Trans­ship­ment­Simplex), 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

1. um fluxo $x$ e um potencial $y$ que satisfazem as condições de otimalidade enunciadas no teorema 4.6, ou
2. a informação de que a rede não tem fluxo que satisfaz $b$, ou
3. a informação de que a rede não tem fluxo que satisfaz $b$ e tem custo mínimo.

No começo de cada iteração (linha 02), $T$ é uma árvore viável da rede.

No fim da linha 05, $x$ é o fluxo induzido por $T$, $y$ é o potencial induzido por $T$, e $\cy_e=0$ para todo arco $e$ de $T$.  No linha 07, $x$ e $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 $\epsilon=\infty$ é equivalente a $\Ereverse(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 $\epsilon$ 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 $\epsilon \cy_{vw}$ é implicitamente subtraído do custo do fluxo $x$.

No fim da linha 14, poderíamos atualizar os valores de $x$, $y$, e $\cy$ 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 $\epsilon$ unidades de fluxo ao longo do ciclo $C$.)

Resta discutir a linha 01. Esta é a parte suja do algoritmo. A rotina Árvore­Viá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 Árvore­Viá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,

1. existe um arco $vr$ para cada nó $v \neq r$ tal que $b(v) \lt 0$ e
2. existe um arco $rw$ para cada nó $w \neq r$ tal que $b(w) \geq 0$.

Essas hipóteses garantem uma árvore viável trivial: o conjunto de arcos da árvore é $E_1 \cup E_2$, sendo $E_1 := \conj{vr : b(v) \lt 0}$ e $E_2 := \conj{rw : 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}[t]{*{5}{r}r} & p & v & w & q & b \\[0.5ex] p & - & 1 & 1 & - & \he -3 \\ v & - & - & 1 & 1 & +2 \\ w & - & - & - & 1 & -1 \\ q & - & - & - & - & +2 \end{array} \hspace{4ex} \begin{array}[t]{*{5}{r}} & pv & pw & vw & vq & wq \\[0.5ex] \hline c & \hb +10 & \hb +30 & \hb +10 & \hb +10 & \hb +10 \end{array} \]

Suponha que a primeira iteração do algoritmo Trans­ship­ment­Simplex 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 $\cy$. O custo do fluxo é $cx=70$.

\[ \begin{array}[t]{l@{\quad}rrrrr} & \bo{pv} & \bo{pw} & vw & vq & \bo{wq} \\[0.5ex] \hline x & 2 & 1 & 0 & 0 & 2 \\ \cy & 0 & 0 & \hb -10 & \hb -20 & 0 \end{array} \hspace{6ex} \begin{array}[t]{rr} & y \\[0.5ex] p & 0 \\ v & +10 \\ w & +30 \\ q & +40 \end{array} \]

O algoritmo escolhe o arco $vw$ e envia $1$ unidade de fluxo ao longo do ciclo induzido por $(v,w,p,v)$. O novo fluxo terá custo $cx=70-10\times 1=60$. O arco $vw$ é acrescentado a $T$ e o arco $pw$ é 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 $\cy$. O fluxo tem custo $cx=60$.

\[ \begin{array}[t]{l@{\hspace{6ex}}rrrrr} & \bo{pv} & pw & \bo{vw} & vq & \bo{wq} \\[0.5ex] \hline x & 3 & 0 & 1 & 0 & 2 \\ \cy & 0 & \hb +10 & 0 & \hb -10 & 0 \end{array} \hspace{6ex} \begin{array}[t]{rr} & y \\[0.5ex] p & 0 \\ v & +10 \\ w & +20 \\ q & +30 \end{array} \]

O algoritmo escolhe o arco $vq$ e envia $1$ unidade de fluxo ao longo do ciclo $(v,q,w,v)$. O novo fluxo terá custo $cx=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}[t]{l@{\quad}rrrrr} & \bo{pv} & pw & vw & \bo{vq} & \bo{wq} \\[0.5ex] \hline x & 3 & 0 & 0 & 1 & 1 \\ \cy & 0 & 0 & \hb +10 & 0 & 0 \end{array} \hspace{6ex} \begin{array}[t]{rr} & y \\[0.5ex] p & 0 \\ v & +10 \\ w & +10 \\ q & +20 \end{array} \]

Como $\cy\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 $cx=yb$.

Número de iterações. No fim da linha 14, o custo do fluxo induzido por $T$ é $cx + \epsilon\cy_{e}$, sendo $\cy_{e} \lt 0$ (veja a seção 4.4 e o lema 4.9).  Se $\epsilon > 0$, o novo fluxo será mais barato que o anterior e assim o algoritmo terá feito algum progresso. Se $\epsilon = 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, Trans­ship­ment­Simplex 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$ a $j$ em $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 $ij$ é um arco vazio de $T$ então $ij$ é 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$ em $T$, isto é, o último nó comum aos caminhos $P_v$ e $P_w$. Percorra o ciclo fundamental $C$ a partir de $s$ e escolha para $h$ \begin{equation}\label{eq:transshipment:leaving-arc-rule} \text{o primeiro arco em $\Ereverse(C)$ que tenha $x_h=\epsilon$.} \end{equation}

Com isso, a árvore $T{+}e{-}h$ será fortemente viável.

Se $T$ é fortemente viável no início de todas as iterações, a execução de Trans­ship­ment­Simplex 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.

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 $(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)$ se  $c_{vw} = y_w - y_v$  para cada arco $vw$ de $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$ em $L$, o ciclo fundamental de $T+e$ é o único ciclo em $T+e$ no qual $e$ é um arco direto.  Para cada $e$ em $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

• $\cy_{e} = 0$ para $e$ em $T$,
• $\cy_{e} \geq 0$ para $e$ em $L$,
• $\cy_{e} \leq 0$ para $e$ em $U$,

sendo $\cy$ 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$.

No começo de cada iteração (linha 04), $(T,L,U)$ é uma tripartição arbórea viável.

A rotina Tripar­tição­Arbó­rea­Viá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 Tripar­tição­Arbó­rea­Viável. Um truque sujo clássico consiste em escolher um nó $r$, arbitrário mas fixo, e acrescentar à rede (a) um arco $vr$ para cada nó $v \neq r$ tal que $b(v) \lt 0$ e (b) um arco $rw$ 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 := \conj{vr : b(v) \lt 0}$ e $E_2 := \conj{rw : b(w) \geq 0}$, e seja $L$ conjunto $E(D)\setm E(T)$. Agora, $(T, L, \emptyset)$ é uma tripartição arbórea viável.

Se o algoritmo Network­Simplex 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}[t]{*{5}{r}r} & p & v & w & q & b \\[0.5ex] p & - & 1 & 1 & - & \he -4 \\ v & - & - & 1 & 1 & 0 \\ w & - & - & - & 1 & +2 \\ q & - & - & - & - & +2 \end{array} \hspace{4ex} \begin{array}[t]{l@{\quad}rrrrr} & pv & pw & vw & vq & wq \\[0.5ex] \hline u & \infty & \infty & 1 & \infty & \infty \\ c & \hb +10 & \hb +20 & +8 & \hb +20 & \hb +20 \end{array} \]

A primeira iteração do algoritmo Network­Simplex 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}[t]{*{6}{r}} & \bo{pv} & \bo{pw} &\undr{vw} & \bo{vq} &\undr{wq} \\[0.5ex] \hline x & 2 & 2 & 0 & 2 & 0 \\ \cy & 0 & 0 & -2 & 0 & \hb +10 \end{array} \hspace{6ex} \begin{array}[t]{rr} & y \\[0.5ex] p & 0 \\ v & +10 \\ w & +20 \\ q & \hb +30 \end{array} \]

O algoritmo escolhe o arco $vw$ e envia $1$ unidades de fluxo ao longo do ciclo induzido por $(v,w,p,v)$. O arco $vw$ fica cheio e é transferido de $L$ para $U$. A tripartição $(T,L,U)$ não se altera. O novo fluxo terá custo $cx=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 $cx=98$.

\[ \begin{array}[t]{l@{\quad}rrrrr} & \bo{pv} & \bo{pw} & \ovr{vw}& \bo{vq} &\undr{wq} \\[0.5ex] \hline x & 3 & 1 & 1 & 2 & 0 \\ \cy & 0 & 0 & -2 & 0 & \hb +10 \end{array} \hspace{6ex} \begin{array}[t]{rr} & y \\[0.5ex] p & 0 \\ v & +10 \\ w & +20 \\ q & \hb +30 \end{array} \]

Como $\cy_e\geq 0$ para todo $e$ em $L$ e $\cy_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 $cx = \text{}$ $yb+zu$. (Essa é uma boa maneira de detetar eventuais erros de cálculo cometido durante a execução do algoritmo.) O vetor $z_e=\min\,\left(0,\,\cy_e\right)$ está indicado abaixo:

\[ \begin{array}[t]{*{6}{r}} & \bo{pv} & \bo{pw} & \ovr{vw} & \bo{vq} & \undr{wq} \\[0.2ex] \hline z & 0 & 0 & \hb -2 & 0 & 0 \end{array} \hspace{20ex} \]

Portanto, $cx = 98 = 100-2 = yb+zu$, como deveria ser.

Consumo de tempo. O algoritmo Network­Simplex, tal como Trans­ship­ment­Simplex, 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 $ij$ de $T$ que está vazio aponta para longe da raiz (ou seja, $ij$ é um arco de $P_j\,$), e cada arco $ij$ de $T$ que está cheio aponta na direção da raiz (ou seja, $ij$ é um arco de $P_i\,$).