Fluxo de custo mínimo

3 Dezembro 2019, 18:00 • Ana Maria Duarte Silva Alves Paias

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.

Fluxo Máximo

26 Novembro 2019, 20:00 • Ana Maria Duarte Silva Alves Paias

Resolução de exercícios da folha de exercícios OR2.

Fluxos em rede

26 Novembro 2019, 18:00 • Ana Maria Duarte Silva Alves Paias

Determinação do Fluxo Máximo entre dois vértices de uma rede:

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.

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

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

Caminho ótimo

19 Novembro 2019, 20:00 • Ana Maria Duarte Silva Alves Paias

Resolução de exercícios de caminho ótimo da ficha OR_1.

Fluxo em Redes

19 Novembro 2019, 18:00 • Ana Maria Duarte Silva Alves Paias

Problema da determinação do fluxo máximo entre dois vértices. Noção de caminho de aumento, de caminho saturado e de fluxo saturante,