Fluxo de custo mínimo

30 Novembro 2022, 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, algoritmo de resolução baseado na deteção de circuitos de custo total negativo. Exemplo de aplicação.

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. Exemplo de aplicação.

Fluxo máximo entre dois vértices

23 Novembro 2022, 20:00 • Ana Maria Duarte Silva Alves Paias

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

Fluxo máximo entre dois vértices de uma rede e Emparelhamento de cardinalidade máxima.

23 Novembro 2022, 18:00 • Ana Maria Duarte Silva Alves Paias

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: algoritmo para a 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.

Arvore de suporte de custo mínimo e Caminho Ótimo

16 Novembro 2022, 20:00 • Ana Maria Duarte Silva Alves Paias

Resolução de alguns exercícios da folha de execícios  OR1

Fluxo máximo entre dois vértices de uma rede

16 Novembro 2022, 18:00 • Ana Maria Duarte Silva Alves Paias

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

Problema da determinação do fluxo máximo entre dois vértices. Noção de corte separando dois vértices, 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.