OPTIMIZAÇÃO E DECISÃO
Modelos de Optimização de Redes
Responsável: Prof. Alexandra Moutinho
João Raposo Nº 43633
Carlos Costa Nº 55518
27 / 10 / 2008
Representação em Rede
• Amplamente usadas em diversos tipos de
problemas tais como:
–
–
–
–
–
Produção
Distribuição
Planeamento de projectos
Rotas
Planeamento de recursos / plan. Financeiro
• Muitos modelos de optimização de redes, são
casos especiais de Programação Linear.
2
Terminologia de Redes
• Exemplos de componentes típicos de redes:
Nós
Arcos
Fluxo
Cruzamentos
Aeroportos
Comutadores
Estações de Elevação
Postos de Trabalho
Estradas
Rotas
Fios / Canais
Condutas
Rotas de transporte de materiais
Carros
Aviões
Mensagens
Fluidos
Tarefas
Orientada – Arcos Dirigidos
Rede
Não Orientada – Arcos
sem sentido definido
Caminho
Directo – Liga dois nós
consecutivos
Indirecto – A ligação
entre dois nós não tem
direcção definida
Spanning Tree → Rede em que todos os nós estão
ligados e que não contém ciclos indirectos.
3
Tipos de Problemas de Redes
• Caminho Mais Curto
Algoritmo:
•Objective of nth iteration: find the nth nearest node to the
origin (n = 1, 2, …) until the nth nearest node is reached.
•Input for the nth iteration: n – 1 nearest nodes to the origin,
including their shortest path and distance to the origin (these are
the solved nodes).
•Candidates for the nth nearest node: each solved that is
directly connected to unsolved nodes provides one candidate –
the unsolved node with the shortest connecting link.
•Calculation of the nth nearest node: for each solved node
and its candidate, add the distance between them to the distance
of the shortest path from the origin to this solved node. The
candidate with the smallest total distance is the nth nearest node,
and its shortest path is the one generating this distance.
Nó inicial: MEC
Nó final: CV
4
Caminho Mais Curto
n
Nós resolvidos
directamente ligados
a nós não resolvidos
Nó não resolvido
mais próximo
Distância total
envolvida
1
Mec
TN
100
2
Mec
TN
C
CV
120
100+80=180
3
Mec
C
TS
CV
200
120+30=150
Nó mais
próximo
Distância
mínima
Ligação
TN
100
MecTN
C
120
Mec-C
CV
150
C-CV
Caminho Óptimo: Mec-C-CV
Tipo de aplicações:
•Minimização de distância percorrida
•Minimização do custo de uma sequencia de actividades…
5
Tipos de Problemas de Redes
• Minimum Spanning Tree
Algoritmo:
•Escolher um nó arbitrariamente.
•Ligar esse nó seguinte mais próximo
•Identificar qual a ligação mais próxima dos
nós já ligados e ligar.
•Repetir até todos os nós estarem ligados
Em caso de haver mais do que uma ligação numa das etapas, o
desempate é feito arbitrariamente. Apenas indica que existe mais
do que uma solução óptima.
6
Tipos de Problemas de Redes
• Problema de Fluxo Máximo
– Maximizar o fluxo entre uma fonte e um poço
através de uma rede orientada e ligada.
– O fluxo nos arcos é apenas permitido na direcção
indicada no mesmo
• Resolução:
– Augmented Path Algorithm
• Determinar um caminho entre a fonte O e o poço T e
reduzir a capacidade residual máxima possível na
direcção directa desse caminho.
7
Problema de Fluxo Máximo
• Iteração 1
• Determinar o caminho
– Partindo da fonte seguir pelos caminhos com
capacidade maior que zero.
– Partindo dos nós atingidos repetir o processo até
chegar ao poço.
• Determinar Optimalidade
– Para uma rede com uma fonte e um poço, o fluxo
máximo praticável corresponde ao valor mínimo de
todos os cortes da rede.
8
Tipos de Problemas de Redes
• Fluxo de Custo Mínimo
– Generalização, inclui arcos com capacidade limitada,
custos e pode incluir múltiplas fostes e poços com
custos associados.
– Pode ser definido como um problema de programação
linear: Simplex de redes.
• Definição do problema:
– Rede orientada e conectada.
– Contem pelo menos uma fonte e um poço.
– Os arcos te capacidade para que todo fluxo “criado”
nas fontes chegue aos poços.
– Objectivo: Minimizar o custo da transferência do fluxo
9
Fluxo de Custo Mínimo
• Exemplo:
• Condição de existência de solução:
∑ bi = 0
10