MOQ – 43
PESQUISA
OPERACIONAL
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
Programa do curso:
Semana
Conteúdo
1
Apresentação da disciplina. Formulação em programação matemática (PM).
2
Introdução à Programação Linear. (PL) Resolução de problemas de PL pelo Método Gráfico. Introdução ao
método simplex para resolução de PPL .
3
Resolução de problemas de PL pelo Método Simplex. A matemática do método simplex.
4
Problemas com soluções iniciais (Método das 2 fases e o Big-M). Degeneração, ciclagem e convergência do
método simplex.
5
Análise de Sensibilidade. Resolução computacional de problemas de programação matemática.
6
Prova 1
7
O problema dual. Formulação e Interpretação econômica do problema dual. Teoremas da dualidade.
8
Algoritmos simplex adicionais. Análise pós-otimização.
9
O Problema do Transporte.
10
O problema do Transbordo. O problema da Designação.
11
Programação Linear Inteira: Formulação, Método de Branch and Bound. Problemas de otimização combinatória.
12
Prova
13
Otimização em Redes. O problema do caixeiro viajante e do carteiro chinês. Os problemas do caminho mínimo e
do fluxo máximo.
14
Introdução à programação não-linear.
15
Princípios de otimização global. Métodos não exatos para resolução de problemas de PM.
16
Princípios de programação multiobjetivo. Fechamento da disciplina.
MOQ – 43
OTIMIZAÇÃO EM
REDES
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
Fluxo em Redes (Network Flows) :
 Muitos problemas de otimização podem ser melhor analisados se for
utilizada uma representação gráfica ou em forma de redes.
 Esses problemas são enquadrados como de otimização em redes ou
fluxo em redes (network flows)
 Principais Problemas:
•
Transporte (Transportation)
•
Atribuição ou Designação (Assignment)
•
Transbordo (Transshipment)
•
Caminho Mínimo (Shortest-Path) / Máximo
•
Circuitos Hamiltonianos (TSP)
•
Máximo fluxo (Maximum-flow problems)
•
Problema da árvore geradora mínima (Minimum Spanning Tree)
Fluxo em Redes (Network Flows) :
 Definições:
 Um grafo, ou rede, é definido por dois conjuntos de símbolos:
nós (ou vértices) e arcos.
 Um arco consiste de um par ordenado de nós e representa uma
possível direção de movimento que pode ocorrer entre os nós.
 Uma seqüência de arcos distintos que ligam nós é chamado de
caminho (path).
 Uma árvore é uma rede conectada (todos os nós estão
conectados por no mínimo 1 caminho) sem ciclos.
MOQ – 43
OS PROBLEMAS DO
CAIXEIRO VIAJANTE E
CARTEIRO CHINÊS
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
O problema do caixeiro viajante:
 O problema do caixeiro viajante é um problema de otimização associado à
determinação dos circuitos hamiltonianos num grafo qualquer.
Diz-se que um circuito é Hamiltoniano se passar uma e só uma vez por todos os
vértices de uma rede. A designação provém do islandês Hamilton que em 1857
propôs um jogo denominado “Around the World". Nesse jogo, os vértices
representavam as 20 cidades mais importantes do mundo na época. O objetivo
do jogo consistia em encontrar um percurso através dos vértices, com início e fim
no mesmo vértice e que passasse por cada vértice apenas uma vez.
0
2
0
2
4
1
3
6
4
1
5
3
6
5
O problema do caixeiro viajante:
 Formulação de Dantzig-Fulkerson-Johnson:
 Seja um grafo G = (V,A), em que V é o conjunto de vértices
(cidades) e A é o conjunto de arcos (ligações entre duas cidades).
Var. decisão: xij =
1, se o arco de i para j estiver no caminho
0, caso contrário
Minimizar
 dij xij
i
j
S . A.
 xij  1,
j
i
 xij  1,
i
j
 xij  S  1,
i , jS
S  grafo
O problema do caixeiro viajante:
 Exemplo:
1
1
2
2
6
5
3
3
5
4
4
F.O.: MIN 1x1,2 + 1x2,1 + 2x2,3 + 2x3,2 + 3x3,4 + 3x4,3 + 6x1,4 +
6x4,1 + 4x4,5 + 4x5,4 + 5x5,1 + 5x1,5
S.A. x1,2 + x1,4 + x1,5 = 1
x2,3 + x2,1 = 1
x3,2 + x3,4 = 1
x3,4 + x1,4 + x5,4 = 1
x5,4 + x5,1 = 1
x2,1 + x4,1 + x5,1 = 1
x3,2 + x1,2 = 1
x2,3 + x4,3 = 1
x4,3 + x4,1 + x4,5 = 1
x1,5 + x4,5 = 1
O problema do caixeiro viajante:
1
1
2
2
6
5
x1,2 + x2,1 + x2,3 + x3,2 +
x3,4 + x4,3 + x4,1 + x1,4  3
3
3
4
5
4
1
1
2
2
6
5
3
3
5
4
4
x1,4 + x4,1 + x4,5 + x5,4 +
x1,5 + x5,1  2
O problema do caixeiro viajante:
MIN 1x12 + 1x21
S.T.
x12 + x14 + x15
x21 + x41 + x51
x23 + x21 = 1
x32 + x12 = 1
x32 + x34 = 1
x23 + x43 = 1
x34 + x14 + x54
x43 + x41 + x45
x54 + x51 = 1
x15 + x45 = 1
x12 + x21 + x23
x14 + x41 + x45
x12 >=0
x14 >=0
x15 >=0
x21 >=0
x41 >=0
x51 >=0
x23 >=0
x32 >=0
x34 >=0
x43 >=0
x54 >=0
x45 >=0
x12 <=1
x14 <=1
x15 <=1
x21 <=1
x41 <=1
x51 <=1
x23 <=1
x32 <=1
x34 <=1
x43 <=1
x54 <=1
x45 <=1
+ 2x23 + 2x32 + 3x34 + 3x43 + 6x14 +6x41 + 4x45 + 4x54 + 5x51 + 5x15
= 1
= 1
= 1
= 1
+ x32 + x34 + x43 + x41 + x14 <= 3
+ x54 + x15 + x51 <= 2
1
1
2
2
5
3
3
5
4
4
O problema do caixeiro viajante:
Embora a formulação de Dantzig-Fulkerson-Johnson tenha conseguido
resolver o problema há uma dificuldade de implementação: colocar na
formulação de todos os subgrafos de um grafo complexo.
Exemplo:
2
1
3
5
4
O problema do caixeiro viajante:
 Resolução por branch-and-bound:
 Resolver o problema do caixeiro viajante como um problema de
atribuição (relaxado)
Minimizar
 dij xij
i
j
S . A.
 xij  1,
j
i
 xij  1,
i
j
 Se a solução do problema relaxado for viável para o problema do
caixeiro viajante, esta é ótima. Caso contrário adicione uma
restrição para bloquear o arco (xij = 0).
 Repita o procedimento até encontrar uma solução ótima para o
problema relaxado e que atenda o problema de caixeiro viajante.
O problema do caixeiro viajante:
 Resolução por branch-and-bound: Exemplo
2
1
3
5
4
O problema do caixeiro viajante:
 Resolução pela heurística do vizinho mais próximo:
 Passo 1: selecione um ponto de partida.
 Passo 2: Conecte este ponto ao seu vizinho mais próximo, desde
que esse não forme um subcircuito.
 Repita o passo 2 até que todos os nós tenham sido escolhidos.
 Exemplo:
2
1
3
1–5–2–4–3–1
5
4
D = 668
O problema do caixeiro viajante:
 Teste da solução pela heurística da inversão:
 É possível buscar melhorar a solução invertendo-se 2 a 2, 3 a 3,
…, n-1 a n-1, em que n é o número de nós de uma rede.
 Exemplo:
1–5–2–4–3–1
D = 668
1–2–5–4–3–1
D = 737
1–5–4–2–3–1
D = 962
1–5–2–3–4–1
D = 704
1–4–2–5–3–1
D = 964
1–5–3–4–2–1
D = 807
1–3–2–4–5–1
D = 962
O problema do carteiro chinês (PCC):
 O PCC é um problema de otimização que objetiva cobrir com um
passeio todos os arcos de um grafo, minimizando a distância total
percorrida, permitindo a repetição de arestas.
Ilustração:
Existem formulações do PCC para o caso orientado, não-orientado e
misto.
O problema do carteiro chinês:
 Formulação (caso não-orientado):
VD: xij é o número de vezes que o arco (i,j) é usado (no sentido i  j)
n
Minimizar
n
 d
i 1 j 1
n
S . A.
x
ij ij
n
x x
j 1
ji
j 1
ij
(MINIMIZAR A DISTÂNCIA PERCORRIDA)
 0, i  1,..., n
xij  x ji  1, i  j
xij  0
e inteiro
O problema do carteiro chinês (PCC):
 Exemplo:
M in 3x1, 2  4 x1,8    2 x 6,8 
3x 2,1  4x 8,1    2 x 8,6
S.A. x1, 2  x1,5  x1, 6  x1,8  x 2,1  x 5,1  x 6,1  x 8,1  0

x 8, 6  x 8,1  x 6,8  x1,8  0
7
2
x1, 2  x 2,1  1

x 6 ,8  x 8, 6  1
x1, 2 , , x 8, 6  0
3
5
3
7
4
6
1
3
6
2
4
8
4
4
5
6
MOQ – 43
PROBLEMA DO
CAMINHO MÍNIMO /
MÁXIMO
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
O problema do caminho mínimo / máximo:
 Problema do caminho mínimo / máximo  Otimização de redes lineares
 Decisões estratégicas: selecionar o caminho mais curto / longo entre nós
 Utilidade: caminho mais curto: rota de transporte, substituição de equipam, …
caminho mais longo: PERT, CPM e problema da mochila
2
3
4
2
4
Depósito 1
2
1
6
2
3
3
4
5
Cidade 1
Formulação do problema do caminho mínimo / máximo:
Minimizar Maximizar
 dij xij
i
j
dij é a distância entre a origem i e o destino j
Var. decisão: xij =
1, se o arco (i,j) estiver no caminho mínino / máximo
0, caso contrário
k  s ( fonte )
1 ,

S . A.  xkj   xik   0, para todos os outros k
j
i

  1 , k  r ( sorvedouro)
xij  0 , i, j
Formulação do problema do caminho mínimo / máximo:
MIN / MAX Z = 4X12 + 3X13 + 3X24 + 2X25 + 4X35 + 2X46 + 2X56
Var. decisão: xij = 1, se a ligação fizer parte do caminho mínimo / máximo
0, caso contrário
S.A. X12 + X13 = 1 (fonte)
- X46 - X13 = -1 (sorvedouro)
X12 = X24 + X25
X46 = X24
X13 = X35
X56 = X25 + X35
2
3
4
2
4
Depósito 1
2
1
6
2
3
3
4
5
Cidade 1
Resolução do problema do caminho mínimo:
Algoritmo Dijkstra:
 Início: rotule o nó fonte de forma permanente com 0 e cada um dos nós
conectados a este, de forma temporária, com a distância do arco que une
1 a este. Todos os outros nós receberão um rótulo temporário .
1
2
*
0
Depósito 1
0

4
4
3
2
4
2
1
6
2
3
4
3
1
3

5

Cidade 1
Resolução do problema do caminho mínimo:
Algoritmo Dijkstra:
 Passo 2: Selecione o nó com o menor rótulo temporário e faça-o
permanente. Então rotule cada um dos nós conectados a este, de forma
temporária, com a distância do arco que os une.
 Repita o passo 2 até chegar no nó sorvedouro.
1
2
*
0
Depósito 1
0

4
4
3
2
4
2
1
6
2
3
4
3
1
3
*

5
3
7
Cidade 1
Resolução do problema do caminho mínimo:
Algoritmo Dijkstra:
 Passo 2: Selecione o nó com o menor rótulo temporário e faça-o
permanente. Então rotule cada um dos nós conectados a este, de forma
temporária, com a distância do arco que os une.
 Repita o passo 2 até chegar no nó sorvedouro.
*
1
2
*
0
Depósito 1
0
2
4
7
4
3
2
4
2
1
6
2
3
4
3
1
3
*

5
2
6
Cidade 1
Resolução do problema do caminho mínimo:
Algoritmo Dijkstra:
 Passo 2: Selecione o nó com o menor rótulo temporário e faça-o
permanente. Então rotule cada um dos nós conectados a este, de forma
temporária, com a distância do arco que os une.
 Repita o passo 2 até chegar no nó sorvedouro.
*
1
2
*
0
Depósito 1
0
2
4
7
4
3
2
4
2
1
2
1
4
3
*
8
6
3
3
5
5
2
6
*
Cidade 1
Resolução do problema do caminho mínimo:
Algoritmo Dijkstra:
 Passo 2: Selecione o nó com o menor rótulo temporário e faça-o
permanente. Então rotule cada um dos nós conectados a este, de forma
temporária, com a distância do arco que os une.
 Repita o passo 2 até chegar no nó sorvedouro.
*
1
Depósito 1
4
2
*
0
*
0
2
7
4
3
2
4
2
1
2
1
4
3
*
8
6
3
3
5
5
2
6
*
Cidade 1
Resolução do problema do caminho mínimo:
Algoritmo Dijkstra:
 Passo 2: Selecione o nó com o menor rótulo temporário e faça-o
permanente. Então rotule cada um dos nós conectados a este, de forma
temporária, com a distância do arco que os une.
 Repita o passo 2 até chegar no nó sorvedouro.
*
1
Depósito 1
4
2
*
0
*
0
2
7
4
3
*
2
4
2
1
2
1
4
3
*
8
6
3
3
5
5
2
6
*
Cidade 1
Resolução do problema do caminho mínimo:
Algoritmo Dijkstra:
*
1
Depósito 1
4
2
*
0
*
0
2
7
4
3
*
2
4
2
1
2
1
4
3
*
8
6
3
3
5
5
2
6
*
 Caminho mais curto: 1 – 2 – 5 – 6 : distância = 8
Cidade 1
Resolução do problema do caminho mínimo:
Problema do Transbordo:
2
3
4
2
4
Depósito 1
2
1
6
2
3
3
2
1
2
3
4
5
Demanda
Cidade 1
4
3
5
4
5
6
4
3
M
M
M
0
M
3
2
M
M
0
M
4
M
M
M
0
M
2
M
M
M
0
2
1
1
1
1
1
Oferta
1
1
1
1
1
Exemplo - problema do caminho mínimo:
Um carro novo é comprado por US$12,000.00. O custo de manutenção e seu
preço de revenda dependem da idade do carro como segue:
Idade do carro (anos) Custo de Manutenção (US$)
0
2,000.00
1
4,000.00
2
5,000.00
3
9,000.00
4
12,000.00
Idade do carro (anos) Preço de Revenda (US$)
1
7,000.00
2
6,000.00
3
2,000.00
4
1,000.00
5
0,000.00
Formule o problema que determine a política ótima de troca de veículos no
horizonte de 5 anos (leia-se política ótima aquela que minimiza a soma dos custos
de compra, manutenção e revenda).
5
4
3
2
1
0
Exemplo - problema do caminho mínimo:
Custo total: Ficar com o carro 1 ano (US$ mil) = 12+2 -7 = 7
Ficar com o carro 2 anos (US$ mil) = 12 +2 +4 -6 = 12
Ficar com o carro 3 anos (US$ mil) = 12 +2 +4 +5 -2 = 21
Ficar com o carro 4 anos (US$ mil) = 12+2 +4 +5 +9 -1 = 31
Ficar com o carro 5 anos (US$ mil) = 12+2 +4 +5 +9 +12 -0 = 44
5
0
0
5
2
3
4
7
5
12
5
21
1
5
31
0
5
44
Exemplo - problema do caminho mínimo:
5
0
0
5
5
0
0
7
5
12
4
7
5
12
19
1
4
2
3
4
5
2
3
4
4
19
3
19
28
0
4
1
3
24
38
0
3
33
Exemplo - problema do caminho mínimo:
5
0
0
5
5
0
0
7
5
12
4
19
3
19
7
5
12
1
3
2
3
4
5
2
3
4
4
19
3
19
24
0
2
1
3
24
31
0
2
31
1
31
Exemplo - problema do caminho mínimo:
5
0
0
5
2
3
4
7
5
12
4
19
3
19
1
3
 Caminhos mais curtos: 5 – 3 – 1 – 0 : distância = 31
5 – 4 – 2 – 0 : distância = 31
5 – 3 – 2 – 0 : distância = 31
24
0
2
31
1
31
Problema do caminho máximo:
 CPM (critical path method)
Exemplo (caminho máximo): CPM (critical path method)
Número
0
1
2
3
4
5
6
7
8
9
10
Atividade
Início do Trabalho
Projeto de Simulação
Treinamento de Pessoal
Construção das Instalações
Certificação das Instalações
Aquisição de material
Aferição dos instrumentos
Teste do material adquirido
Montagem da cabine de simulação
Execução da simulação
Fim
Atividade de pré-requisito
0
1
1
3,6
1
5
2,4
7
8
9
2
0
1
7
3
5
Duração
0
2
6
4
1
1
3
3
1
2
0
4
6
8
9
10
Exemplo (caminho máximo): CPM (critical path method)
X_27
2
X_12
7
3
X_47
6
3
X_01
0
2
X_13
1
4
X_34
3
4
1
X_64
X_15
1
5
X_56
3
1
X_78
1
8
9
10
X_89
X_910
2
0
6
Variável de decisão: x_ij = 1 se a ligação da etapa i para a etapa j estiver no
caminho crítico e 0 caso contrário.
Restrições:
x_01 = 1
x_12 + x_13 + x_15 = x_01
x_27 = x_12
x_34 = x_13
x_56 = x_15
x_64 = x_56
x_47 = x_34 + x_64
x_78 = x_27 + x_47
x_89 = x_78
x_910 = x_89
x_ij = 0,1
Função Objetivo: MAX 2*x_01 + 6*x_12 + 4*x_13 + 1*x_15 + 3*x_27 + 1*x_34
+ 3*x_56 + 1*x_64 + 3*x_47 + 1*x_78 + 2*x_89
Problema do caminho máximo: Resolução
 CPM (critical path method)
Os cálculos do caminho crítico envolvem dois passos:
Passo 1: Forward pass (tempo mais cedo de ocorrência)
Passo 2: Backward pass (tempo mais tarde de ocorrência)
Uma atividade estará no caminho crítico se:
Exemplo (caminho máximo): CPM (critical path method)
11
11
8
8
3
2
7
6
6
2
0
4
1
2
2
3
1
3
4
1
14
14
12
12
8
2
9
0
1
1
0
0
7
5
4
3
3
6
8
7
14
14
7
6
 Caminho crítico: 0 – 1 – 2 – 7 – 8 – 9 – 10 : distância = 14
10
Exemplo (caminho máximo): CPM (critical path method)
 Caminho crítico: 0 – 1 – 2 – 7 – 8 – 9 – 10 : distância = 14
11
11
8
8
3
2
7
6
6
2
0
4
1
1
4
5
2
4
3
3
8
7
6
7
6
7
8
3
9
5
4
6
2
6
8
11 12
1
14
14
12
12
8
2
9
1
2
2
0
0
3
3
1
1
7
14
tempo
14
14
0
10
MOQ – 43
PROBLEMA DA
ÁRVORE GERADORA
MÍNIMA
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
O problema da árvore geradora mínima:
 Exemplo:
O problema da árvore geradora mínima:
 Em uma rede com n nós, uma árvore geradora é um grupo de n-1 arcos
que conectam todos os nós de uma rede sem formar loopings.
A árvore geradora mínima é uma árvore geradora em que a soma dos n1 arcos é a menor possível
Exemplo:
O problema da árvore geradora mínima:
 Exemplo:
F.O. MIN 2Xab + 1Xac + 4Xae + 2Xbd + 3Xbc + 2Xcd + 2Xce + 5Xcg +
3Xeg + 2Xdf + 4Xfg + 4Xfh + 5 Xgh
S.A.
Xab + Xac + Xae  2
Xab + Xbc + Xbd  2
Xac + Xbc + Xcd + Xce + Xcg  2
Xbd + Xcd + Xdf  2
Xae + Xce + Xeg  2
Xdf + Xfg + Xfh  2
Xeg + Xfg + Xgh  1
Xfh + Xgh  1
1  Xab, Xac, Xae, ..., Xgh  0
Xab, Xac, Xae, ..., Xgh inteiras
b
d
a
c
f
h
e
g
Resolução do problema da árvore geradora mínima:
Algoritmo de resolução:
 Seja N={1, 2, …, n} o conjunto de nós de uma rede, Ck o conjunto de nós
conectados de forma permanente na iteração k e Ĉk o conjunto de nós anda
não conectados de forma permanente na iteração k.
 Passo 0: C0 =  e Ĉ0 = N
 Passo 1: Comece em qualquer nó i do conjunto Ĉ0, faça C1 = {i} e Ĉ1 = N-{i}
 Passo geral k: selecione o nó j* de Ĉk-1 que resulte no menor arco até um nó
do conjunto Ck-1. Coloque j* permanentemente em Ck-1 e remova este de
Ĉk-1, ou seja,
Ck = Ck-1 + {j*}
e
Ĉk = Ĉk-1 – {j*}
Resolução do problema da árvore geradora mínima:
 Solução:
Passo 0: C0 =  e Ĉ0 = {a,b,c,d,e,f,g,h}
Passo 5: C5 = {e,c,a,d,b} e Ĉ5 = {f,g,h}
Passo 1: C1 = {e} e Ĉ1 = {a,b,c,d,f,g,h}
Passo 6: C5 = {e,c,a,d,b,f} e Ĉ5 = {g,h}
Passo 2: C2 = {e,c} e Ĉ1 = {a,b,d,f,g,h}
Passo 7: C5 = {e,c,a,d,b,f,g} e Ĉ5 = {h}
Passo 3: C3 = {e,c,a} e Ĉ1 = {b,d,f,g,h}
Passo 8: C5 = {e,c,a,d,b,f,g,h} e Ĉ5 = 
Passo 4: C4 = {e,c,a,d} e Ĉ1 = {b,f,g,h}
EXEMPLO: ÁRVORE GERADORA MÍNIMA
MOQ – 43
PROBLEMA DO FLUXO
MÁXIMO
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
Problema do fluxo máximo:
• O problema do fluxo máximo é um problema de enumeração de cortes.
• Um corte define um conjunto de arcos que, quando eliminado da rede,
causará um rompimento total do fluxo entre o nó de origem e o nó
sorvedouro.
• A capacidade do corte é igual à soma das capacidades de seus arcos.
Formulação do problema do fluxo máximo:
Var. decisão: xij = qtde (volume) que deve ir da origem i para o destino j
Maximizar Z 
 x
ij
i  corte j  corte
S . A.
x x
kj
j
xij  Cij
ik
 0 , (i, j)  origem ou destino
i
, (i, j)
xij  0 , (i, j)
Planejamento da Freqüência de Vôos:
Uma empresa de transporte aéreo deseja determinar quantos vôos com
conexão podem ser realizados entre Manaus e Salvador. Os vôos devem
fazer conexão primeiro em Belém e depois em Brasília ou em Fortaleza.
Em função da previsão de demanda e do tamanho da frota, determinou-se
o numero máximo de vôos diários entre pares de cidade. Formular e
resolva o problema objetivando maximizar o número de vôos diários entre
Manaus e Salvador.
Manaus
Cidades
Belém
Manaus - Belém
Belém - Brasília
Belém - Fortaleza
Brasília - Salvador
Fortaleza - Salvador
Fortaleza
Brasília
Salvador
Número Máximo
de Vôos Diários
3
2
3
1
2
Planejamento da Freqüência de Vôos:
Variável de Decisão: Qi-j=Qtde de i para j
Manaus
3
F.O. MAX = QMAN-BEL
2
Belém
1
Salvador
Brasília
2
Manaus
3
1
Belém
Fortaleza
1
2
Salvador
Brasília
2
Restrições de
Balanceamento
Solução:
Restrições de
3
Limite
S.A.
QMAN-BEL  3
QBEL-BRA  3
QBEL-FOR  2
QBRA-SAL  2
QFOR-SAL  1
QMAN-BEL = QBEL-BRA + QBEL-FOR
QBEL-BRA = QBRA-SAL
QBEL-FOR = QFOR-SAL
Qi-j  0
Fortaleza
Resolução do problema do fluxo máximo:
• Resolução do problema de fluxo máximo por enumeração:
• Entre todos os possíveis cortes na rede, o que tiver a menor
capacidade dá o fluxo máximo na rede.
• Uma alternativa para determinar o fluxo máximo é enumerar
todos os cortes.
• Em grandes redes a enumeração pode ser uma tarefa difícil.
Assim, nestes casos, a necessidade de um algoritmo (ou
heurística) eficiente é imperativa.
Resolução do problema do fluxo máximo:
• Algoritmo do fluxo máximo:
IT1:
SMANAUS = {Belém}
K = Belém e
[3,Manaus]
3
Manaus
[3,Belém]
3
SBELÉM = {Fortaleza;Brasília}
Belém
Fortaleza
[,-]
CMANAUS-BELÉM = MAX{3} = 3
K = Fortaleza pois
2
2
[2,Fortaleza]
Salvador
Brasília
1
CBELÉM-FORTALEZA = MAX{3,2} = 3
SFORTALEZA = {Salvador}
K = Salvador e
CFORTALEZA-SALVADOR = MAX{2} = 2
FLUXO NA ITERAÇÃO 1 = MIN{,3,3,2} = 2  Atualizar as capacidades (C)
Resolução do problema do fluxo máximo:
• Algoritmo do fluxo máximo:
IT2:
SMANAUS = {Belém}
K = Belém e
[1,Manaus]
1
Manaus
CMANAUS-BELÉM = MAX{1} = 1
1
SBELÉM = {Fortaleza;Brasília}
Belém
Fortaleza
[,-]
K = Brasília pois
0
2
[1,Belém]
Salvador
Brasília
[2,Belém]
1
CBELÉM-BRASÍLIA = MAX{1,2} = 2
SBRASÍLIA = {Salvador}
K = Salvador e
CBRASÍLIA-SALVADOR = MAX{1} = 1
FLUXO NA ITERAÇÃO 2 = MIN{,1,2,1} = 1  Atualizar as capacidades (C)
Resolução do problema do fluxo máximo:
• Algoritmo do fluxo máximo:
IT3:
Como todos os nós que partem
de Manaus (ou chegam a
[1,Manaus]
0
Manaus
Salvador) têm capacidade
1
Belém
residual 0, não há mais nenhuma
Fortaleza
[,-]
0
1
Assim,
[1,Belém]
Salvador
Brasília
[2,Belém]
rota de passagem possível.
0
FLUXO MÁXIMO NA REDE (F) = f1 + f2 = 2 + 1 = 3 vôos
Para casa:
• Lista de Exercícios 10
• Leitura Taha: 6, 9.1.2 e 9.3
Winston: 8.1 a 8.6 e 9.5 a 9.6
OBSERVAÇÃO
Este material refere-se às notas de aula do curso
MOQ-43 (Pesquisa Operacional) do Instituto
Tecnológico de Aeronáutica (ITA). Não substitui o
livro texto, as referências recomendadas e nem as
aulas expositivas. Este material não pode ser
reproduzido sem autorização prévia do autor.
Quando autorizado, seu uso é exclusivo para
atividades de ensino e pesquisa em instituições
sem fins lucrativos.