15.053
Quinta-feira, 14 de março
• Introdução aos Fluxos de Rede
• Handouts: Notas de Aula
1
Modelos de Rede
• Modelos de programação linear que exibem uma
estrutura muito especial.
• Podem utilizar essa estrutura para reduzir
significativamente a complexidade dos cálculos.
• As primeiras aplicações de PL amplamente
utilizadas em problemas de logística industrial.
• Utilizados em um grande número de aplicações.
2
Notação e Terminologia
Observação: A terminologia das redes não é (e nunca será) padronizada.
O mesmo conceito pode ser aplicado de modos diferentes.
Termo:
• REDE
• Grafo direcionado
• Dígrafo
• Grafo
Handouts de Aula
Também Utilizado
(Ahuja, Magnanti, Orlin)
Grafo G = (V, E)
Rede G = (N, A)
Conjunto de vértices V = {1, 2, 3, 4}
Conjunto de nós N = {1, 2, 3, 4}
Conjunto de bordas: A = {1-2, 1-3,
Conjunto de arcos {(1, 2), (1, 3), (3, 2), (3, 4), (2, 4)} 3-2, 3-4, 2-4}
3
Redes Direcionadas e Nãodirecionadas
Um grafo não-direcionado
Um grafo direcionado
• As redes são utilizadas no transporte de
produtos.
• Bens físicos (objetos, líquidos)
• Comunicação
• Eletricidade, etc.
• O campo da otimização de redes trata de
problemas de otimização em redes.
4
Uma Visão Geral de Algumas
Aplicações da Otimização de Redes
Aplicações
Sistemas de
comunicação
Sistemas hidráulicos
Circuitos integrados
Sistemas mecânicos
Sistemas de
transporte
Equivalentes físicos
Equivalentes físicos
Fluxo
dos nós
dos arcos
Centrais telefônicas,
Cabos, enlaces de
Transmissões de
computadores,
fibra óptica, enlaces de mensagens de voz,
instalações de
relés de microondas
dados e vídeo
transmissão, satélites
Estações de
Tubulações
Água, gás, óleo,
bombeamento,
fluidos hidráulicos
reservatórios, lagos
Portas, registradores,
Fios
Corrente elétrica
processadores
Juntas
Hastes, vigas, molas
Calor, energia
Interseções,
Rodovias, rotas
Passageiros, carga,
aeroportos, pátios
aéreas, ferrovias
veículos,
ferroviários
operadores
5
Exemplos
de termos
Percurso: Exemplo: 5, 2, 3, 4
(ou 5, c, 2, b, 3, e, 4)
Note que o sentido é ignorado.
Percurso direcionado: Exemplo: 1, 2, 3, 4
(ou 1, a, 2, b, 3, e)
O sentido é importante.
Dois percursos a-b-e (ou 1-2-3-4)
e a-c-d-e (ou 1-2-5-3-4)
Ciclo ou circuito (ou loop)
1, 2, 3, 1 (ou 1, a, 2, b, 3, e)
Note que o sentido é ignorado.
Ciclo direcionado: (1, 2, 3, 4, 1) ou
1, a, 2, b, 3, c, 4, d, 1
O sentido é importante.
Ciclos (loops):
a-b-c-d (ou 1-2-3-4-1)
b-a-d-c (ou 3-2-1-4-3)
e-b-a (ou 1-3-2-1)
c-d-e (ou 3-4-1-3)
6
Mais Definições
Uma rede está conectada se cada nó pode ser
alcançado a partir de qualquer nó, seguindo-se
uma seqüência de arcos na qual o sentido é
ignorado.
Uma árvore geradora é um subconjunto conectado de uma rede
incluindo todos os nós, mas sem nenhum loop.
7
O Problema do Fluxo de Custos
Mínimos
Rede G = (N, A)
- Conjunto de nós N, conjunto de
arcos A
- Capacidades uij no arco (i, j)
- Custo cij no arco (i, j)
- Suprimento/demanda bi para o nó i
(O sinal positivo indica suprimento)
Uma rede com custos, capacidades,
suprimentos e demandas
Minimize o custo da aplicação do fluxo
Fluxo para fora de i – Fluxo para dentro de i = bi
Fluxo no arco (i, j) ≤ uij
8
O Problema do Fluxo de Custos
Mínimos
Considere xij o fluxo no arco (i, j).
Minimize o custo da aplicação do fluxo
Fluxo para fora de i – Fluxo para dentro de i = bi
Minimize
para todo i
para todo i-j)
9
Exemplo de Formulação
10
Uma Aplicação do Problema do Fluxo
de Custos Mínimos
Depósitos
Fábricas
Suprimentos
200
Clientes
Demandas
Expedir dos fornecedores aos clientes, possivelmente por meio
dos depósitos, ao custo mínimo para atender à demanda.
11
Fatos Importantes sobre o Problema
do Fluxo de Custos Mínimos
• Suponha que as seguintes propriedades
da matriz de restrições A (ignorando os
limites simples de variável superior e
inferior, como x ≤ 7) estabeleçam que:
(1) todos os itens de A são 0, 1 ou –1.
(2) existe no máximo um 1 em qualquer coluna
e no máximo um –1.
• Então, este é um problema do fluxo de
custos mínimos.
12
Fatos Importantes (continuação)
Teorema. Se o algoritmo simplex for
utilizado no problema do fluxo de custos
mínimos com RHS e capacidades de valor
inteiro, em cada iteração do algoritmo
simplex, cada coeficiente no quadro
(exceto pelos custos e o RHS) será igual a
0, -1 ou 1.
Colorário. A solução ótima do PL é um valor
inteiro.
13
O Problema do Fluxo de Custos
Uma rede com custos, capacidades,
Mínimos
suprimentos e demandas
Rede G = (N, A)
– Conjunto de nós N, conjunto de arcos A
– Capacidades uij no arco (i, j)
– Custo cij no arco (i, j)
– Suprimento/demanda bi para o nó i
(O sinal positivo indica suprimento)
Minimize o custo da aplicação do fluxo
Fluxo para fora de i – Fluxo para dentro de i = bi
Fluxo no arco (i, j) ≤ uij
14
O Problema do Transporte
Suponha que seja necessário expedir a
partir dos depósitos aos varejistas.
Neste exemplo
3 depósitos
4 varejistas
ai é o suprimento no depósito i.
bj é a demanda no varejista j.
cij é o custo da expedição de i a j.
Não existem capacidades nos arcos.
xij é a quantidade de fluxo expedida do
depósito i ao varejista j.
Como formulamos um PL?
15
O Problema do Transporte é um
Problema do Fluxo de Custos Mínimos
Minimize o custo da aplicação do fluxo
Fluxo para fora de i – Fluxo para dentro de i = bi
O fluxo para fora ocorre nos nós de suprimento
O fluxo para dentro ocorre nos nós de demanda
As capacidades são infinitas: uij = ∞
16
O Problema do Transporte
Em geral, a formulação do LP é a seguinte:
Minimize
Todos os arcos
são de um nó
em S para um
nó em D e sem
capacidades.
S: Nós de suprimento
D: Nós de demanda
17
Fatos Importantes sobre o Problema
do Transporte
Suponha que:
(1) A matriz de restrições pode ser particionada em
A1 x = b1 e A2x = b2
(2) Todos os itens de A1 e A2 são 0 ou 1.
(3) Existe no máximo um 1 em qualquer coluna de A1 ou A2
Então, este é um problema do transporte.
Teorema. Se o algoritmo simplex for utilizado no problema do transporte
em cada iteração do algoritmo, cada coeficiente no quadro (exceto
pelos custos e o RHS) será igual a 0, -1 ou 1. Os custos e o RHS
serão valores inteiros.
Colorário. A solução ideal do PL é um valor inteiro.
18
O Problema da Atribuição
Suponha que seja necessário atribuir tarefas a pessoas
Tarefas
Pessoas
Neste exemplo
4 tarefas
3 pessoas
Não devem ser atribuídas duas tarefas à mesma
pessoa.
A cada pessoa é atribuída somente uma tarefa.
cij é o “custo” da atribuição da tarefa i à pessoa j.
xij = 1, se a tarefa i é atribuída a j.
Caso contrário, xij = 0.
Como formulamos um PL?
19
O Problema da Atribuição
Em geral, a formulação do LP é a seguinte:
Minimize
Cada suprimento é 1
Cada demanda é 1
20
Mais sobre o Problema da Atribuição
Tarefas
Pessoas
O problema da atribuição é um caso
especial do problema do transporte.
O algoritmo simplex pode solucionar a
relaxação do PL e fornecer soluções inteiras,
isto é, soluciona o problema da atribuição.
21
Uma Aplicação do Problema da
Atribuição
Suponha que existam alvos móveis no espaço. Você pode identificar cada
alvo como um pixel em uma tela de radar. Após observar duas telas
sucessivas, determine como os alvos se movem.
22
O Problema do Fluxo Máximo
Rede G = (N, A)
– Fonte s e ponto de convergência t
– Capacidades uij no arco (i, j)
– Variável: Fluxo xij no arco (i, j)
Grafo com capacidades
Maximize o fluxo que sai de s
Fluxo para fora de i – Fluxo para dentro de i = 0 para i ≠ s, t
23
O Problema do Fluxo Máximo
Em geral, a formulação do PL é a seguinte:
Maximize
de outro modo
O PL não é formulado como um caso especial de
uma formulação do fluxo de custos mínimos.
Podemos reformular desse modo?
24
Mais sobre o problema do fluxo
máximo
O fluxo atual é ideal?
Um corte s-t é uma separação dos nós em
duas partes, S e T, com s em S e t em T.
Grafo com capacidades e fluxos
(sublinhados)
A capacidade do corte é a soma das
capacidades de S a T.
O fluxo máximo de s a t é, no máximo, a
capacidade de qualquer corte s-t.
25
O Problema do Caminho Mais Curto
Qual é o caminho mais curto entre um nó de origem ou fonte
(muitas vezes denotado como s) e um nó de destino ou
convergência (muitas vezes denotado como t)? Qual é o caminho
mais curto do nó 1 ao nó 6?
Suposições atuais:
1. Existe um caminho do nó s a todos os outros nós.
2. Todos os comprimentos de arco são positivos ou nulos.
26
Aplicações Diretas
• Qual é o caminho com o menor tempo de
viagem entre a 77 Massachusetts Avenue
e o Boston City Hall?
• Qual é o caminho entre os edifícios 7 e
E40, o qual minimiza o tempo gasto no
lado de fora?
• Qual é o percurso de comunicação mais
rápido entre i e j (considerando-se o
congestionamento nos nós)?
27
Formulação como um programa linear
Em geral, a formulação do LP é a seguinte:
Minimize
de outro modo
28
O Problema do Caminho Mais Curto
• Fato: O problema do caminho mais curto é
um caso especial do problema do fluxo de
custos mínimos.
• Muitas aplicações interessantes (em
breve)
• Algoritmo extremamente rápido (em
breve)
• Vínculo com a programação dinâmica
(daqui a muitas aulas)
29
Conclusões
• As vantagens dos problemas do transporte e
do fluxo de custos mínimos
– Soluções inteiras
– Métodos de solução extremamente rápidos
– Métodos comuns em modelagem
• Hoje, vimos o seguinte:
–
–
–
–
–
O problema do fluxo de custos mínimos
O problema do transporte
O problema da atribuição
O problema do fluxo máximo
O problema do caminho mais curto
30