Problemas de fluxo de custo mínimo

24 Novembro 2021, 18:00 • Ana Maria Duarte Silva Alves Paias

 Determinação do fluxo de custo mínimo e valor fixo, entre dois vértices de uma rede:

Definição do problema e algoritmo de resolução baseado na deteção de circuitos de custo total negativo.

 Determinação do fluxo de custo mínimo numa rede: 

Formulação em programação linear, dual linear e relações de complementaridade. Condição de otimalidade.

Algoritmo out-of kilter: fase primal e fase dual.

Problemas de fluxo em redes

17 Novembro 2021, 20:00 • Ana Maria Duarte Silva Alves Paias

Resolução de alguns exercícios da ficha OR2

Problemas de fluxo em redes

17 Novembro 2021, 18:00 • Ana Maria Duarte Silva Alves Paias

Determinação do fluxo máximo entre dois vertices)

Noção de caminho de aumento,  caminho saturado e de fluxo saturante,

Teorema de Ford-Fulkerson. Condição de otimalidade. 

Algoritmo de Ford-Fulkerson e suas limitações. Algoritmo de Malhotra et al.

Grafos com várias origens e destinos.

Grafos com capacidades nos arcos e nos vértices

Grafos com limites inferiores e superiores no fluxo que passa em cada arco: determinação de um fluxo admissível. Adaptação dos algoritmos Ford-Fulkerson e Malhotra et al.

Emparelhamento de cardinalidade máxima: definição e transformação num problema de determinação do fluxo máximo entre dois vértices.

Exercicios

10 Novembro 2021, 20:00 • Ana Maria Duarte Silva Alves Paias

Resolução de exercícios das folhas OR1 e OR2.

Caminho ótimo e fluxo em redes

10 Novembro 2021, 18:00 • Ana Maria Duarte Silva Alves Paias

Caminho ótimo:  Algoritmo PDM e algoritmo de Floyd.

Fluxo em redes:

Introdução aos problemas de fluxo em redes. Noções básicas.

Fluxo Máximo entre dois vértices: definição, noção de corte separando dois vértices.

Relação entre o valor do fluxo máximo entre dois vértices e a capacidade de um corte separando esses dois vértices