Aula – Fluxo de Custo Mınimo – Ultima atualizacao: 13 de maio de 2019
IA881 – Otimizacao Linear
Aula: Fluxo de Custo Mınimo (Minimum Cost Flow)
Ricardo C. L. F. Oliveira
Faculdade de Engenharia Eletrica e de ComputacaoUniversidade Estadual de Campinas
1o Semestre 2019
R. C. L. F. Oliveira IA881 - Otimizacao Linear 1/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Topicos
1 Definicoes e notacoes
2 Fluxo de Custo Mınimo
3 Simplex para redes
R. C. L. F. Oliveira IA881 - Otimizacao Linear 2/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Conceitos, Definicoes, Notacoes I
Definicao 1
Sejam N um conjunto de vertices e A um conjunto de arestas ligando os verticesv ∈N . Define-se grafos como sendo G(N ,A ). n = |N | representa o numero(cardinalidade) de vertices e m = |A | o numero (cardinalidade) de arestas.
� Observacao: vertice = no; aresta = ramo (nao-orientado) ou arco (orientado)
a b
c
de
f
g
1 2
3 4
5
Figura 1: Grafo nao orientado.
N = {1,2,3,4,5}
A = {a,b,c,d ,e, f ,g}
R. C. L. F. Oliveira IA881 - Otimizacao Linear 3/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Conceitos, Definicoes, Notacoes II
� Uma alternativa para representar uma aresta e por meio da notacao (x ,y) comx ,y ∈N . Por exemplo, no grafo da Figura 1, a aresta b poderia ser representadapor (2,5) ou (5,2). Caso a aresta seja direcionada (arco), convenciona-se que aprimeira componente seja o vertice de origem e a segunda o vertice de destino.
Definicao 2
Grafo orientado ou direcionado (nao orientado ou nao direcionado) – quando asarestas tem (nao tem) orientacao.
1
2
3
4
5
Figura 2: Exemplo de um grafoorientado.
1
2 3
4
5
Figura 3: Exemplo de um grafo naoorientado.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 4/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Conceitos, Definicoes, Notacoes III
Definicao 3
Um grafo e dito ponderado (ou valorado) se suas arestas possuem custos (oupesos) associados. Usa-se a notacao cij (ou c(i , j)) para denotar o custo da arestaentre os vertices i e j.
Definicao 4
Gs (Ns ,As) e um sub-grafo de G(N ,A ) se Ns ⊆N e As ⊆A tal que se(i , j) ∈As ⇒ i , j ∈Ns . Um grafo Gs(Ns ,As) e um sub-grafo gerador deG(N ,A ) se Ns = N e As ⊆A .
R. C. L. F. Oliveira IA881 - Otimizacao Linear 5/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Conceitos, Definicoes, Notacoes IV
1
1
1
2
2
2 3
3
3
4
4
5
5
5
subgrafo
subgrafo gerador
Figura 4: Exemplo de subgrafos (gerador e nao gerador).
R. C. L. F. Oliveira IA881 - Otimizacao Linear 6/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Conceitos, Definicoes, Notacoes V
Definicao 5
Grau de um vertice e o numero de arestas que incidem nele (no caso orientado,arcos que entram mais que saem). Um no de grau 1 tambem e chamado de nofolha.
Definicao 6
Cadeia e uma sequencia consecutiva de arestas em que todos os nos visitados saodistintos. Exemplo: na Figura 2 – {(2,3)(5,3)(4,5)(1,4)}.
Definicao 7
Caminho e um caso particular de cadeia na qual os arcos tem os mesmos
sentidos. Exemplo Figura 2 – {(2,3)(3,1)(1,4)(4,5)}
Definicao 8
Comprimento de um caminho e a soma dos pesos (ou custos) das arestas docaminho.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 7/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Conceitos, Definicoes, Notacoes VI
Definicao 9
Um grafo e dito ser conexo se sempre existe uma cadeia entre qualquer par devertices.
Definicao 10
Ciclo ou laco e uma cadeia fechada (termina no no que iniciou). Exemplo naFigura 2 – {(3,1)(1,4)(3,4)}
Definicao 11
Circuito (ciclo direcionado) e um caminho fechado. Exemplo na Figura 2 –{(2,3)(3,1)(1,2)}
Definicao 12
Uma arvore e um grafo conexo que nao contem ciclos.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 8/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Conceitos, Definicoes, Notacoes VII
� Exemplos de arvore obtidas a partir do grafo da Figura 2: (1) removendo-se asarestas (2,3), (1,4) e (5,3); (2) removendo-se as arestas (1,4), (3,1) e (3,4);Existem outras possibilidades.
Propriedades de uma arvore
Um grafo G com n vertices e uma arvore se e somente se ele satisfaz qualqueruma das seguintes condicoes
G possui n−1 arestas e nenhum ciclo.
G possui n−1 arestas e e conexo.
G e conexo, mas a remocao de uma aresta torna-o desconexo.
G nao tem ciclos (acıclico), mas introduzir uma nova aresta produz umciclo.
Quaisquer dois vertices de G estao conectados por um caminho unico.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 9/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Conceitos, Definicoes, Notacoes VIII
Definicao 13
Uma arvore T e uma arvore geradora de um grafo G(N ,A ) se T e umsub-grafo gerador de G.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 10/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Definicoes e hipoteses
� Considere um grafo (rede) direcionado G(N ,A ) com n nos e m arcos. A todosos nos i ∈N , considerados como pontos de entrada e saıda da rede, associa-seum coeficiente bi tal que
Se bi > 0 entao e um no de fornecimento (ou de producao).
Se bi < 0, entao e um no de demanda (ou de consumo).
Se bi = 0, entao e um no de passagem (ou de transbordo).
� A rede e considerada equilibrada, com excedente de producao ou com excedentede demanda, se ∑i∈N bi e nula, positiva ou negativa, respectivamente.
� A cada arco (i , j) do grafo, seja xij a quantidade de fluxo que passa pelo arco(assume-se que xij ≥ 0) e cij o custo unitario de transporte pelo arco. Assume-seque a rede esta equilibrada. Para o caso de excedente de producao, pode-se criarum no adicional n+1 com bn+1 =−∑i∈N bi e arcos de custo nulo ligando estenovo no e todos os nos de fornecimento.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 11/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Definicao do problema I
Problema do fluxo de custo mınimo (PFCM)
Enviar os recursos disponıveis de modo a atender a demanda com o menor custopossıvel.
Matematicamente, tem-se
min z = ∑(i ,j)∈A
cijxij
s.a ∑(i ,j)∈A
xij − ∑(k ,i)∈A
xki = bi
xij ≥ 0 ∀(i , j) ∈A
� As restricoes
∑(i ,j)∈A
xij − ∑(k ,i)∈A
xki = bi
sao chamadas de“balanco de fluxo” (ou de conservacao de fluxo ou equacoes deKirchhoff) nos nos e indicam que nenhum fluxo pode ser criado ou destruıdo pelarede. A primeira parcela indica o fluxo que sai do no (sinal positivo), e a segundao fluxo que entra no no (sinal negativo), conforme indica a Figura 5.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 12/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Definicao do problema II
ibi
xij
xikxmi
xℓi−xmi −xℓi︸ ︷︷ ︸
entra
+xij +xik︸ ︷︷ ︸
sai
= bi
Figura 5: Balanco de fluxo no no.
� A Figura 6 apresenta um exemplo para o qual e obtida a modelagemmatematica.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 13/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Definicao do problema III
1
3 4
2
1 3 ←− cij
4
b1 = 5
56
7
b4 =−7
b2 =−8
b3 = 10
Figura 6: Grafo com 4 nos e 6 arestas.
min z = 4x12+6x14+3x24+x31+5x32+7x34
s.a
x12 +x14 −x31 = 5−x12 +x24 −x32 =−8
+x31 +x32 +x34 = 10−x14 −x24 −x34 =−7
xij ≥ 0,∀(i , j) ∈A
R. C. L. F. Oliveira IA881 - Otimizacao Linear 14/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Forma padrao e matriz A I
� O exemplo anterior pode ser colocado na forma padrao de programacao linear:
Forma padrao de PL:
min z = cT xs.a Ax = b
x ≥ 0
(1)
sendo que a matriz A e conhecida como matriz de incidencia no-arco. Que talestudarmos algumas de suas propriedades? Para o exemplo anterior, tem-se
A=
(1,2) (3,1) (1,4) (2,4) (3,2) (3,4)1 −1 1 0 0 0 1−1 0 0 1 −1 0 20 1 0 0 1 1 30 0 −1 −1 0 −1 4
Note que cada coluna esta relacionada a um arco e cada linha a um no. Seja ovetor unitario
ei =
[
0 0 · · · 1︸︷︷︸
i-esimo
· · · 0 0
]T
R. C. L. F. Oliveira IA881 - Otimizacao Linear 15/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Forma padrao e matriz A II
Observe que qualquer coluna da matriz A, referente ao arco (i , j), pode serrepresentada na forma
A(i ,j) = ei −ej =
...+1...−1...
0← i...← j0
Propriedade
Para um grafo G(N ,A ) conexo, a matriz A tem rank igual a n−1
� Observacoes: E imediato verificar (a partir da estrutura das colunas) que amatriz A nao tem rank completo (de linhas) pois a soma de todas as linhasfornece uma linha de zeros. Ou seja, o rank e menor que n. Para mostrar que orank e igual a n−1, tome uma arvore geradora (sempre existe) do grafo e mostre
R. C. L. F. Oliveira IA881 - Otimizacao Linear 16/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Forma padrao e matriz A III
que a matriz AT correspondente (uma submatriz de A) e tal querank(AT )=n−1.
� Seja AT uma arvore geradora (n nos e n−1 arcos), cuja representacao matricialfornece uma matriz de dimensao n× (n−1). Usando propriedades, sempre epossıvel representar essa matriz na seguinte forma
AT =
[±1 0
× AT ′
]
sendo AT ′ uma subarvore obtida com a retirada de um no de grau 1 (folha) e seuarco associado, portanto de dimensao (n−1)× (n−2) (ver Figura 7).
R. C. L. F. Oliveira IA881 - Otimizacao Linear 17/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Forma padrao e matriz A IV
ℓ
k
TT ′
Figura 7: Remocao de um no folha de uma arvore geradora.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 18/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Forma padrao e matriz A V
� Aplicando o mesmo processo em A′T e assim sucessivamente, obtem-se aseguinte representacao
AT =
±1 0 · · · 0× ±1 · · · 0...
.... . .
...× × ·· · ±1× × ·· · ∓1
Removendo a ultima linha, tem-se uma matriz de dimensao (n−1)× (n−1)triangular inferior, com ±1 nos elementos da diagonal. Portanto, essa matriz temrank=(n−1) e seu determinante (produto dos elementos da diagonal) vale ±1.
� Considere o exemplo anterior e a arvore geradora (escolhida arbitrariamente)apresentada na Figura 8.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 19/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Forma padrao e matriz A VI
PSfrag1
3 4
2
Figura 8: Arvore geradora para o grafo da Figura 6.
A matriz de incidencia AT dessa arvore e
AT =
(1,2) (2,4) (3,2)1 0 0 1−1 1 −1 20 0 1 30 −1 0 4
⇒ AT =
(1,2) (2,4) (3,2)1 0 0 10 −1 0 40 0 1 3−1 1 −1 2
R. C. L. F. Oliveira IA881 - Otimizacao Linear 20/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Forma padrao e matriz A VII
Descartando-se a ultima linha, chega-se a
AT =
(1,2) (2,4) (3,2)1 0 0 10 −1 0 40 0 1 3
que e uma matriz de rank n−1 = 3.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 21/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Criando uma base I
� Metodo simplex → necessita de uma base (submatriz de A com rank completo(n)) para iniciar o algoritmo.
� Artifıcio: acrescentar um arco artificial a algum no. Este arco e chamado dearco raiz e o no associado de no raiz. No exemplo anterior, introduzindo o arcoraiz no no 2, terıamos a arvore geradora enraizada mostrada na Figura 9.
1
3 4
2
Figura 9: Arvore geradora enraizada para o grafo da Figura 6.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 22/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Criando uma base II
fornecendo a seguinte solucao basica para o problema original (naonecessariamente factıvel)
AT = B =
(1,2) (2,4) (3,2) a.r .1 0 0 0 10 −1 0 0 40 0 1 0 3−1 1 −1 1 2
(2)
Note que a matriz continua com estrutura bloco triangular inferior (tem rank
completo). Outro detalhe importante e que a coluna referente ao arco raiz (a.r.)sempre estara presente em qualquer solucao basica (por que sera?).
� Tambem e facil perceber que uma solucao basica nao poderia conter um ciclo,pois nesse caso a coluna correspondente a um dos arcos do ciclo pode ser escritacomo combinacao dos outros arcos do ciclo (linearmente dependente).
� Em resumo, mostrou-se que uma arvore geradora enraizada corresponde a umasolucao basica. Tambem e possıvel mostrar o oposto, ou seja, toda solucao basicacorresponde a uma arvore geradora enraizada. Assim, temos
R. C. L. F. Oliveira IA881 - Otimizacao Linear 23/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Criando uma base III
Teorema
Considere o problema de fluxo de custo mınimo em um grafo direcionado conexoG com um no raız. Entao a matriz B e uma solucao basica para o problema se esomente se ela for uma matriz de incidencia associada a uma arvore geradoraenraizada de G .
R. C. L. F. Oliveira IA881 - Otimizacao Linear 24/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Integralidade
� Seja B uma matriz base para um grafo conexo enraizado (garantidamente estaassociada a uma arvore geradora enraizada). Uma solucao basica pode sercomputada pela expressao (considerando n= 4)
BxB = b⇒
±1 0 0 0× ±1 0 0× × ±1 0× × × ±1
xB1xB2xB3xB4
=
b1b2b3b4
Pela estrutura triangular inferior, o sistema de equacoes pode ser resolvido porsubstituicoes sucessivas. Como os elementos da triangular inferior so podemassumir os valores {−1,0,1}, nota-se que todas as variaveis so podem resultar emnumeros inteiros se bi ∈ Z. Assim, caso solucoes inteiras sejam uma restricao doproblema, a solucao pode ser calculada ignorando essa restricao sempre quebi ∈ Z.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 25/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Unimodularidade
Definicao 14
Seja A uma matriz qualquer e AS qualquer uma de suas submatrizes quadradas.A e totalmente unimodular se o determinante de qualquer AS vale 0 ou −1 ou 1.
� Usando inducao, e possıvel mostrar que uma matriz de incidencia no-arco A etotalmente unimodular. Note que a propriedade se mantem se acrescentarmoscolunas unitarias ei (oriundas de arcos associados a variaveis de folga, excesso eartificiais) a A.
� Como consequencia, qualquer base B tambem e totalmente unimodular. Alem,B−1 contem entradas valendo apenas 0 ou −1 ou 1. Finalmente, note que apos aatualizacao de qualquer coluna de A por meio da operacao B−1A(i ,j), obtem-seum vetor y(i ,j) tambem composto apenas de 0 ou −1 ou 1, pois
y(i ,j)k =detBk
detB(regra de Cramer)
R. C. L. F. Oliveira IA881 - Otimizacao Linear 26/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Metodo Simplex adaptado para redes
� O metodo simplex tradicional pode ser resumido da seguinte maneira:Determine uma solucao basica inicial factıvel; Determine os custos reduzidos paracada variavel nao basica; Se a otimalidade foi atingida, pare; caso contrarioselecione uma coluna nao basica para entrar na base; Se uma solucao ilimitadanao for detectada, determine a coluna que sai (por bloqueio) e realize opivoteamento.
� Na sequencia sao discutidas cada uma dessas operacoes para o Simplexadaptado para redes.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 27/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando o valor das variaveis basicas I
� Considere o grafo da Figura 6 com um arco raiz no no 2 e como solucao basicainicial a arvore geradora enraizada formada pelos arcos x14, x32, x34 e xar , comomostra a Figura 10.
1
3 4
2
5
10 -7
-8
Figura 10: Arvore geradora enraizada no no 2 para o grafo da Figura 6.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 28/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando o valor das variaveis basicas II
As variaveis basicasxB =
[x14 x32 x34 xar
]T
podem ser determinadas de duas maneiras. A primeira seria pela resolucao dosistema de equacoes BxB = b, isto e
1 0 0 00 −1 0 10 1 1 0−1 0 −1 0
x14x32x34xar
=
5−810−7
⇒
x14 = 5x32 = 8x34 = 2xar = 0
(3)
que pode ser resolvido por substituicoes sucessivas.
� A segunda possibilidade e obter os valores diretamente no grafo aplicando obalanco de fluxo nos nos, comecando com os nos folhas e indo em direcao ao noraiz. Por exemplo, no no folha 1 tem-se diretamente que x14 = 5. Para o no 4,tem-se −x14−x34 =−7⇒ x34 = 2, e assim por diante.
� Note que essa solucao basica coincidentemente e factıvel. A busca sistematicapor uma solucao basica inicial factıvel e discutida mais adiante.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 29/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando os custos relativos I
� No Simplex classico e necessario avaliar os custos relativos c referentes asvariaveis nao basicas. Esse computo pode realizado por meio do computo de π
(multiplicadores Simplex),
π = cBB−1⇒ πB = cB
sendo cB o vetor de custos associado aos arcos presentes na base, e na sequenciacomputando os custos relativos
cij = cij −πA(i ,j)
� Uma alternativa e determinar o vetor π e os custos relativos das variaveis naobasicas de modo grafico. Para o computo de π, inicia-se com o calculo domultiplicador associado ao no raiz e prossegue-se em direcao aos nos folhasusando a relacao πi −πj = cij . Em posse de π, os custos relativos referentes aosarcos nao basicos sao calculados por
cij = cij −πA(i ,j) = cij − (πi −πj )
R. C. L. F. Oliveira IA881 - Otimizacao Linear 30/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando os custos relativos II
Se todos os custos relativos forem nao negativos, entao a solucao e otima. Casocontrario uma variavel nao basica com custo negativo e escolhida para entrar nabase.
� Considere a solucao basica inicial factıvel dada pela arvore mostrada naFigura 3. A Figura 11 mostra o calculo de π graficamente, partindo de π2 = 0 (noraiz).
R. C. L. F. Oliveira IA881 - Otimizacao Linear 31/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando os custos relativos III
1
3 4
2
56
7
π1−π4 = 6⇒ π1 = 4
π3−π2 = 5⇒ π3 = 5 π3−π4 = 7⇒ π4 =−2
π2 = 0
Figura 11: Computo do vetor π graficamente.
� A Figura 12 mostra o calculo grafico dos custos relativos para os arcos naobasicos. Como todos os custos relativos sao nao negativos, tem-se a solucaootima z⋆ = 6x14+5x32+7x34 = 30+40+14 = 84.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 32/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando os custos relativos IV
7
1
3 4
2
1−π3+π1 = 0 3−π2+π4 = 1
4−π1+π2 = 0π1 = 4
π3 = 5 π4 =−2
π2 = 0
Figura 12: Computo dos custos relativos dos arcos nao basicos.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 33/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando os custos relativos V
� As variaveis πi tambem podem ser interpretadas como as variaveis duaisassociadas a cada restricao (balanco do fluxo em cada no) do problema primaldado em (1). Um fato importante e que o valor de πi tambem pode serinterpretado como o custo de transportar uma unidade de fluxo do no i ate o noraiz (respeitando as direcoes dos arcos). De modo simetrico −πi = πi pode servisto como o custo para transportar uma unidade de fluxo do no raiz ate o no i .Desse modo, se
πj > πi + cij
entao e melhor (mais vantajoso) transportar uma unidade de fluxo do no origemate o no i e traze-lo ate o no j por meio do arco (i , j). Alguma semelhanca com oconceito que serve de base para os algoritmos de caminho mınimo (Dijkstra eBellman-Ford)?
R. C. L. F. Oliveira IA881 - Otimizacao Linear 34/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Saıda da base e teste de bloqueio I
� Caso o custo relativo associado a alguma variavel nao basica seja negativo,entao esta variavel e uma candidata a entrar na base, pois o aumento de fluxo noarco associado diminui o valor da funcao objetivo.
� Quando o arco nao basico candidato entra na base, cria-se um ciclo (por que?)e um dos arcos basicos deve ser removido de modo a restaurar a arvore geradoraenraizada. Essa remocao e realizada por meio do teste do bloqueio, como ilustraa Figura 13.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 35/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Saıda da base e teste de bloqueio II
p
q
r
s
t
raiz
xpq +∆
xtq −∆
xts +∆
xrs −∆
xrp +∆
Figura 13: Fluxo adicional ∆ no ciclo criado pela introducao do arco (p,q).
R. C. L. F. Oliveira IA881 - Otimizacao Linear 36/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Saıda da base e teste de bloqueio III
� A partir do arco que entra na base (arvore), no caso (p,q), introduz-se umaquantidade extra de fluxo ∆ que ira percorrer o ciclo. Nos arcos com mesmadirecao de (p,q) soma-se ∆. Nos arcos com direcao contraria, subtrai-se ∆(garantindo o equilıbrio e consequentemente a factibilidade).
� A primeira variavel basica (caso exista) a anular seu fluxo devera sair da base.Este teste e feito de forma similar ao teste de bloqueio do Simplex tradicional.Por exemplo, na Figura 13 considere os seguintes valores para as variaveis basicasdo ciclo: xtq = 4, xts = 3, xrs = 2 e xrp = 5. Assim tem-se
4−∆ ≥ 0⇒∆= 4
3+∆ ≥ 0⇒∆= ∞
2−∆ ≥ 0⇒∆= 2
5+∆ ≥ 0⇒∆= ∞
Portanto xrs define o bloqueio (∆ = 2) e sai da base. Note que apenas os arcoscom direcao contraria ao arco que entra e que podem criar um bloqueio (se nao
R. C. L. F. Oliveira IA881 - Otimizacao Linear 37/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Saıda da base e teste de bloqueio IV
houver nenhum ⇒ solucao ilimitada), assim o valor de ∆ pode ser determinadopor
∆=min(xij ) : (i , j) e um arco reverso do ciclo
� Determinado o arco que sai da base, atualiza-se o fluxo dos arcos basicos erepete-se o procedimento ate a otimalidade (ou solucao ilimitada) ser detectada.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 38/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes I
Algorithm 1 Algoritmo Simplex para redes1: Determinar uma solucao basica inicial (arvore geradora enraizada) factıvel.2: Determinar os multiplicadores π e os custos relativos nao basicos.3: enquanto houver arcos candidatos a entrar na base faca
4: Selecionar um arco para entrar na base.5: se bloqueio e factıvel entao6: Determinar o arco que sai da base.7: Atualizar os multiplicadores e custos relativos.8: else
9: Pare, solucao ilimitada.10: fim se
11: fim enquanto
� A atualizacao realizada na linha 7 pode ser otimizada, notando que parte daarvore nao sera alterada por conta da remocao e insercao dos arcos.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 39/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes II
� Exemplo: Resolva o problema de fluxo de custo mınimo para o grafoapresentado na Figura 14.
1
3 4
21
3
3
4
b1 = 2
-2
b4 =−3
b2 =−1
b3 = 2
Figura 14: Grafo com 4 nos e 5 arestas.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 40/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes III
� Considere a arvore geradora enraizada dada na Figura 15, na qual os fluxos nosarcos basicos ja estao determinados, isto e, xB = [x12 x13 x34 xar ]
T = [1 1 3 0]T .O valor da funcao objetivo para essa base e z = 13.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 41/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes IV
xar = 0
−x12 =−1⇒ x12 = 1
x13+x12 = 2⇒ x13 = 1
−x34 =−3⇒ x34 = 3
1
3 4
2
Figura 15: Arvore geradora enraizada e os fluxos associados (factıvel).
R. C. L. F. Oliveira IA881 - Otimizacao Linear 42/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes V
� A Figura 16 mostra o computo dos multiplicadores e dos custos relativos dosarcos nao basicos x14 e x32. O arco x14 tem um custo relativo negativo eportanto e um candidato a entrar na base.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 43/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes VI
−2−
π3+
π2=0
4−π2+π4 = -1
π1 = 0 π1−π2 = 1⇒ π2 =−1
π1−π3 = 3⇒ π3 =−3 π3−π4 = 3⇒ π4 =−6
1
3 4
2
Figura 16: Computo dos multiplicadores e custos relativos nao basicos.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 44/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes VII
� A Figura 17 mostra o teste de bloqueio a partir do ciclo gerado pela introducaodo arco x14 na arvore geradora. O arco x13 gera o bloqueio e sai da base. Osnovos fluxos basicos sao xB = [x12 x24 x34 xar ]
T = [2 1 2 0]T . O valor da funcaoobjetivo para essa base e z = 12.
1+∆
∆
3−∆
1−∆ ∆=1
1
3 4
2
Figura 17: Teste de bloqueio.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 45/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes VIII
� Iteracao 2: A Figura 18 mostra o computo dos multiplicadores e dos custosrelativos dos arcos nao basicos x13 e x32. O arco x32 tem um custo relativonegativo e portanto e um candidato a entrar na base.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 46/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes IX
−2−
π3+
π2=
-1
3−π1+π3 = 1
π1 = 0 π1−π2 = 1⇒ π2 =−1
π2−π4 = 4⇒ π4 =−5π3−π4 = 3⇒ π3 =−2
1
3 4
2
Figura 18: Computo dos multiplicadores e custos relativos nao basicos.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 47/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes X
� A Figura 19 mostra o teste de bloqueio a partir do ciclo gerado pela introducaodo arco x32 na arvore geradora. O arco x34 gera o bloqueio e sai da base. Osnovos fluxos basicos sao xB = [x12 x24 x32 xar ]
T = [2 3 2 0]T . O valor da funcaoobjetivo para essa base e z = 10.
∆1+∆
2−∆
∆=2
3 4
2
Figura 19: Teste de bloqueio.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 48/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes XI
� Iteracao 3: A Figura 20 mostra o computo dos multiplicadores e dos custosrelativos dos arcos nao basicos x13 e x34. Como todos os custos relativos sao naonegativos, tem-se a solucao otima (z⋆ = 10). Como uma das variaveis tem custorelativo nulo, pode-se considerar que existem outras solucoes de mesmo custo.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 49/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Algoritmo Simplex para redes XII
3−π3−π4 = 1
3−π1+π3 = 0
π1 = 0 π1−π2 = 1⇒ π2 =−1
π2−π4 = 4⇒ π4 =−5π3−π2 =−2⇒ π3 =−3
1
3 4
2
Figura 20: Computo dos multiplicadores e custos relativos nao basicos.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 50/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Exercıcio
� Resolva o problema de fluxo de custo mınimo para o grafo apresentado naFigura 21.
2
3
4
6
7
−5
−1b1 = 4
b2 = 2
b3 =−1
b4 =−51
2
3
4
Figura 21: Grafo com 4 nos e 7 arestas.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 51/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando uma solucao basica inicial factıvel I
� Caso uma solucao basica inicial factıvel nao esteja disponıvel, o algoritmoSimplex nao podera ser iniciado. Nesse caso e necessario um procedimentosistematico para obter uma solucao inicial factıvel.
� Seja o problema de fluxo de custo mınimo na forma padrao dada em (1) comA= A0. Uma solucao base inicial factıvel pode ser produzida seguindo os passos
Adicione n colunas artificiais em A0 sendo n o numero de nos do grafo,gerando a matriz [A0 D]. A i-esima coluna sera o vetor ±ei , dependendo dosinal do bi correspondente (mesmo sinal).
Adicione uma nova linha em [A0 D], formada pela soma das linhas e com ainversao do sinal.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 52/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando uma solucao basica inicial factıvel II
Seguindo esse procedimento, tem-se a nova restricao linear aumentada
±1±1
A0 . . .
±1
−1A0 ∓1 ∓1 · · · ∓1
11x 1
1
xa
=
11b 1
1
1b
sendo 1= [1 1 · · · 1].
� Note que a matriz aumentada preserva a estrutura de rede, pois todas ascolunas possuem apenas elementos iguais a 0, -1 ou 1, e alem disso cada colunatem apenas um 1 e um -1 e o resto de zeros.
� Com relacao a linha adicional, ela pode ser vista como um no adicional nografo. Note que existem n novos arcos, cada um comecando no no adicional eterminando nos nos existentes (o grafo continua conexo). Finalmente, adicionadoa raiz nesse no adicional, tem-se que a nova matriz e de rank completo. Assim, a
R. C. L. F. Oliveira IA881 - Otimizacao Linear 53/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando uma solucao basica inicial factıvel III
arvore geradora inicial pode ser construıda com os n arcos artificiais mais o arcoraiz.
� Considere o grafo mostrado na Figura 21. Aplicando o procedimentoapresentado, obtem-se o grafo mostrado na Figura 22. O metodo da fase I ou dobig-M podem ser aplicados para encontrar uma solucao basica inicial compostaapenas de arcos originais.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 54/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Determinando uma solucao basica inicial factıvel IV
2
3
4
6
7
−5
−1
c15
c53
c54
c25
b1 = 4
b2 = 2
b3 =−1
b4 =−5
b5 = 0
1
2
3
4
5
Figura 22: Grafo com no e arcos artificiais (em azul).
R. C. L. F. Oliveira IA881 - Otimizacao Linear 55/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Metodo da Fase I
� Para aplicar o metodo da fase I, os custos associados aos arcos artificiaisassumem valores unitarios e os custos dos arcos originais sao zerados. Nasequencia aplica-se o metodo Simplex para redes ate que todos os arcos artificiaissaiam da base. Para o exemplo anterior, o grafo preparado para a fase I emostrado na Figura 23.
0
0
0
0
0
0
0
1
1
1
1
b1 = 4
b2 = 2
b3 =−1
b4 =−5
b5 = 0
1
2
3
4
5
Figura 23: Grafo preparado para a fase I.R. C. L. F. Oliveira IA881 - Otimizacao Linear 56/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Metodo da Fase I
� Na forma matricial, tem-se
x12 x13 x23 x24 x32 x34 x41 x1 x2 x3 x4 x51 1 0 0 0 0 −1 1 0 0 0 0−1 0 1 1 −1 0 0 0 1 0 0 00 −1 −1 0 1 1 0 0 0 −1 0 00 0 0 −1 0 −1 1 0 0 0 −1 00 0 0 0 0 0 0 −1 −1 1 1 1
b42−1−50
e a arvore geradora enraizada no no artificial (ja com os fluxos factıveis) emostrada na Figura 24.
x15 = 4
x53 = 1
x54 = 5x25 = 2
x5 = 0
1
2
3
4
5
Figura 24: Arvore geradora inicial factıvel.R. C. L. F. Oliveira IA881 - Otimizacao Linear 57/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Metodo da Fase I
� A partir da arvore geradora inicial, aplica-se o Simplex especializado para redesate que:
Todos os arcos artificiais a menos de um, saiam da arvore. O arco artificialque ficou na arvore deve ter fluxo nulo. Na sequencia despreza-se todos osarcos artificiais e continua-se a otimizacao no grafo original (fase II). Casomais de um arco artificial esteja na arvore geradora (com fluxo nulo) nofinal da fase I, uma estrategia e continuar a otimizacao conservando essesarcos artificiais com custo nulo, mas garantindo que seus fluxos jamaissejam positivos (perderia-se a factibilidade).
Se no final algum arco artificial tiver fluxo nao nulo, entao o problema einfactıvel.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 58/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Metodo do big-M
� A aplicacao do metodo do big-M e similar ao metodo da fase I, apenasatribuindo um custo muito alto, M, aos arcos artificiais e conservando-se oscustos originais nos outros arcos, como mostra a Figura 25. A arvore geradorainicial e a mesma da Figura 24.
2
3
4
6
7
−5
−1
M
M
M
M
b1 = 4
b2 = 2
b3 =−1
b4 =−5
b5 = 0
1
2
3
4
5
Figura 25: Grafo preparado para o big-M.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 59/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Variaveis canalizadas
� Ate este ponto foi tratado o caso de arcos nao capacitados e com limite inferiornulo. Contudo, podemos adaptar o algoritmo sem grandes dificuldades paratratar o caso mais geral
PL canalizado:
min z = cT xs.a Ax = b
ℓ≤ x ≤ L
(4)
A Figura 26 mostra um grafo com arestas canalizadas e a notacao (ℓ,L,c) indicao limite inferior, superior e custo, respectivamente, para cada arco.
1
3 4
2(0,4,1)
(1,5,3)
(1,5,3)
(2,6,4)
b1 = 2
(0,3,-2)
b4 =−3
b2 =−1
b3 = 2
Figura 26: Grafo com 4 nos e 5 arestas canalizadas.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 60/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Otimalidade
� A condicao de deteccao de otimalidade a ser atendida no caso canalizado e
Otimalidade:
{cij ≥ 0 se xij = ℓijcij ≤ 0 se xij = Lij
∀xij nao basico
O grafo da Figura 27 mostra um conjunto de arcos nao basicos atendendo ocriterio de otimalidade.
1
2 3
4
(2,5,1)x32 = 2
c32 > 0
(0,5,1)
x24 = 5c24 < 0
(0,4,1)
x43 = 4c43 < 0
Figura 27: Grafo os arcos nao basicos atendendo a otimalidade.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 61/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Calculo do fluxo de bloqueio
� Duas situacoes precisam ser analisadas: se o arco que entra esta com fluxo nolimite inferior (a) ou no limite superior (b). A situacao (a) e ilustrada naFigura 28.
j
i k
m
xij = ℓij ⇒+∆ +∆
−∆−∆
∆
ℓij
ℓij
Lij
Lij
xij
xij
Figura 28: Arco nao basico xij entrando com fluxo no mınimo.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 62/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Calculo do fluxo de bloqueio
� A situacao (b) e ilustrada na Figura 29
j
i k
m
xij = Lij ⇒−∆ −∆
+∆+∆
∆
ℓij
ℓij
Lij
Lij
xij
xij
Figura 29: Arco nao basico xij entrando com fluxo no maximo.
� Em ambos os casos, o valor de ∆ pode ser computado da seguinte forma
∆ =min(∆ij), ∆ij =
Lij − ℓij para xij nao basicoLij −xij para xij basico no mesmo sentidoxij − ℓij para xij basico no sentido contrario
R. C. L. F. Oliveira IA881 - Otimizacao Linear 63/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Solucao basica inicial factıvel
� Para o problema com variaveis canalizadas, caso os limites inferiores de todos osarcos sejam nulos, entao aplica-se o mesmo procedimento do caso naocanalizado. Caso contrario pode-se utilizar o seguinte procedimento
Para cada no k do grafo, calcular
fk = bk + ∑(i ,k)∈A
ℓik − ∑(k ,j)∈A
ℓkj
Para cada no k do grafo
Se fk > 0 criar um arco artificial de k para (n+1) com custo Mgrande e fluxo fk .Se fk < 0 criar um arco artificial de (n+1) para k com custo Mgrande e fluxo −fk .Se fk = 0 criar um arco artificial entre (n+1) e k (direcaoarbitraria) com custo M grande e fluxo fk .
Fazer, para todos os arcos do grafo original xij = ℓij .
Otimizar.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 64/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Exemplo
� Considere o grafo apresentado na Figura 30, no qual existem arcos com limiteinferior maior que zero (arcos (1,2) e (2,3)).
1 2 3
4
(1,5,1) (2,5,2)
(0,5,3) (0,5,3)(0,5,3)
b1 = 5 b2 = 0 b3 =−5
b4 = 0
Figura 30: Problema canalizado em que existem arcos com ℓij > 0.
Calculando os coeficientes fk , tem-se
f1 = 5−1−0 = 4f2 = 0+1+0−2 =−1
f3 =−5+2−0 =−3f4 = 0+0−0 = 0
R. C. L. F. Oliveira IA881 - Otimizacao Linear 65/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Exemplo
� A Figura 31 mostra os arcos artificias bem como seus fluxos iniciais.
1 2 3
4
5
(0,4,M)
x15 = f1 = 4
(0,3,M)
x53 =−f3 = 3
(0,10,M)
x53 = f4 = 0
(0,1,M)
x52 =−f2 = 1
x12 = 1 x23 = 2
Figura 31: Problema canalizado com arcos artificiais.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 66/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Exemplo
� A Figura 32 mostra o calculo dos potenciais e dos custos relativos nao basicos.O menor custo relativo (em modulo) e c12 = 1−2M e portanto (1,2) entra nabase.
1 2 3
4
5
c12 = 1−2M c23 = 2
c14 = 3c34 = 2M+3c42 = 3−2M
π1 =M
π2 =−M
π3 =−M
π4 =M
π5 = 0
Figura 32: Computo dos potenciais e custos relativos nao basicos.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 67/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Exemplo
1 2
5
+∆
−∆−∆
Figura 33: Teste de bloqueio.
∆=min(∆12,∆15,∆52),∆12 = L12− ℓ12 = 5−1 = 4∆15 = x15− ℓ15 = 4−0 = 4∆52 = x52− ℓ52 = 1−0 = 1
⇒∆= 1
Fluxos atualizados: x12 = 2, x15 = 3 e x52=0 (sai da base).
R. C. L. F. Oliveira IA881 - Otimizacao Linear 68/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Exemplo
� A Figura 34 apresenta os novos potenciais e os custos relativos nao basicosatualizados. Repete-se o procedimento ate todos os arcos artificiais terem saıdoda base com excecao de um, que devera ter fluxo nulo (se nao tiver o problemaoriginal e infactıvel).
1 2 3
4
5
c12 = 1
c23 = 3−2M
c14 = 3c34 = 2M+3c42 = 2
π1 =M
π2 =M−1
π3 =−M
π4 =M
π5 = 0
Figura 34: Computo dos potenciais e custos relativos nao basicos.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 69/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Problema do caminho mınimo
� O problema do caminho mınimo investigado em aulas anteriores pode sermodelado como um caso particular do problema de fluxo de custo mınimo:
Apenas um no de fornecimento (no origem) com bs = n−1.
Todos os demais nos sao de demanda unitaria (bi =−1).
Os arcos sao nao capacitados (Lij = ∞)
Matematicamente tem-se
min z = ∑(i ,j)∈A
cijxij
s.a ∑(i ,j)∈A
xij − ∑(k ,i)∈A
xki =
{n−1 se i e a origem−1 caso contrario
xij ≥ 0 ∀(i , j) ∈A
Terminada a execucao do Simplex para redes, tem-se a arvore de caminhosmınimos do no origem para todos os outros nos. Os custos dos caminhos saodados por −πi (potenciais com sinal trocado).
R. C. L. F. Oliveira IA881 - Otimizacao Linear 70/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Problema do fluxo maximo I
� Seja um grafo G(N ,A ) com arcos cujas capacidades de fluxo sao limitadassuperiormente Lij ≤ ∞, e dois nos especiais s e d (origem e destinorespectivamente). O problema do fluxo maximo consiste em determinar amaxima quantidade de fluxo que pode partir de s e chegar em d respeitando ascapacidades dos arcos.
Matematicamente temos
max xsd
s.a ∑(i ,j)∈A
xij − ∑(k ,i)∈A
xki =
xsd se i e a origem (s)0 se i e no de passagem−xsd se i e o destino (d)
0≤ xij ≤ Lij ∀(i , j) ∈A
sendo xsd o fluxo entre a origem e o destino, que neste modelo pode serinterpretado como um arco ligando s e d com capacidade ilimitada.
� Exemplos de aplicacoes: Maximizar:
R. C. L. F. Oliveira IA881 - Otimizacao Linear 71/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Problema do fluxo maximo II
o fluxo de uma rede de distribuicao de produtos de uma empresa a partir desuas fabricas ate seus consumidores.
o fluxo de um determinado fluıdo (agua, oleo, etc) por meio de uma rede detubos;
o fluxo de veıculos por meio de uma rede de transporte.
� Exemplo: Considere o grafo mostrado na Figura 35, em que os valoresmostrados sao os limitantes superiores dos fluxos nos arcos.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 72/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Problema do fluxo maximo III
s
2
3 4
5
d
Ls2=16
10
13 4
4 9
14
12
20
Figura 35: Grafo com os limitantes superiores dos fluxos nos arcos.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 73/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Problema do fluxo maximo IV
s
2
3 4
5
dx32=1 7
4
11
11
12
12
19
Figura 36: Solucao do problema de fluxo maximo para o grafo daFigura 35. Nesse caso, xs2+ xs3 = x5d + x4d = 23.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 74/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Problema do fluxo maximo V
� O algoritmo Simplex especializado para o problema de fluxo de custo mınimopode ser utilizado para resolver o problema de fluxo maximo, transformando aformulacao apresentada num problema de minimizacao (funcao objetivo igual a−xsd ).
� Alternativa: Algoritmo de Ford-Fulkerson (usa os conceitos de corte-mınimo erede residual).
R. C. L. F. Oliveira IA881 - Otimizacao Linear 75/76
Definicoes e notacoes Fluxo de Custo Mınimo Simplex para redes
Referencias I
M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali.
Linear Programming and Network Flows.
Jonh Wiley & Sons, Hoboken, New Jersey, 4 edition, 2010.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.
Introduction to Operations Research.
MIT Press, Cambridge, Massachusetts, 3 edition, 2009.
R. C. L. F. Oliveira IA881 - Otimizacao Linear 76/76