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

28 Abril 2022, 13:00 • Maria Eugénia Captivo

Introdução.
Formulação em PL.
Problema dual. Determinação da solução óptima do dual.
Exemplo de aplicação.
Condições de complementaridade.
Propriedades. Aplicações.
Ideia base do algoritmo out-of-kilter. Fase primal e fase dual. Estado de um arco. Número de kilter de um arco.
Condições de optimalidade num problema variáveis limitadas. Objectivo da Fase primal e da Fase dual. Solução óptima.
Aplicação do algoritmo out-of-kilter a uma instância partindo de um fluxo inicial identicamente nulo.

Problemas de máximo de s a t

28 Abril 2022, 10:30 • Maria Eugénia Captivo

Resolução de alguns exercícios da Folha 3.

Problemas de máximo de s a t

26 Abril 2022, 14:30 • Maria Eugénia Captivo

Resolução de alguns exercícios da Folha 3.

Aula Laboratorial - Caminho Óptimo e Fluxo máximo

21 Abril 2022, 14:00 • Maria Eugénia Captivo

Explicação da utilização do software para determinar caminhos óptimos entre todos os pares de vértices.
Resolução computacional dos exercícios da Folha 2.

Explicação da utilização do software para determinar o fluxo máximo de s a t numa rede.
Resolução computacional de alguns exercícios da Folha 3.

Problema do fluxo máximo (s a t) numa rede (Conclusão)

21 Abril 2022, 13:00 • Maria Eugénia Captivo

Exemplo de aplicação do algoritmo de Ford-Fulkerson partindo de um fluxo inicial admissível dado, para o caso em que existem limites inferiores não nulos,

Grfos com limites superiores e inferiores no valor do fluxo que atravessa cada arco.
Determinação de um fluxo compatível. Exemplos de aplicação.
Adaptação do algoritmo de Ford-Fulkerson para determinar o fluxo máximo de s a t neste caso.