Sumários
Problema do caminho óptimo entre qualquer par de vértices
8 Março 2024, 09:00 • Maria Eugénia Captivo
Resolução de alguns exercícios da Folha 2
Fluxo máximo (s a t)
8 Março 2024, 08:00 • Maria Eugénia Captivo
Algoritmo de Ford-Fulkerson para determinação do fluxo máximo (s a t) numa rede.
Corte de capacidade mínima separando s de t.
Solução óptima do problema primal e do problema dual.
Teorema de Ford-Fulkerson. Demonstração.
Exemplo de aplicação do algoritmo de Ford-Fulkerson partindo de um fluxo inicial admissível dado. Identificação da solução óptima do problema dual.
Caminho óptimo entre qualquer par de vértices de um grafo e Fluxo máxino (s a t)
6 Março 2024, 10:00 • Maria Eugénia Captivo
Caminho Óptimo entre qualquer par de vértices de um grafo.
Conclusão do exemplo de aplicação do algoritmo de Floyd com deteção de circuitos de custo total negativo no caminho mais curto entre qualquer par de vértices de um grafo.
Exemplo de aplicação do Algoritmo de Floydo para determinar o caminho mais curto entre qualquer par de vértices. Adaptação para o caso de maximização.
Determinação do fluxo máximo (s a t) numa rede:
Exemplo de aplicação. Construção da rede. Formulação em Programação Linear. Problema dual. Condições de complementaridade.
Caminhos óptimos
5 Março 2024, 11:30 • Maria Eugénia Captivo
Explicação da utilização do software para determinar caminhos mais curtos de um vértice a todos os outros (algoritmo PDM).
Resolução computacional dos exercícios da Folha 2. (A aula funcionou no Laboratório 6.4.35)
Problemas de caminho óptimo
5 Março 2024, 10:30 • Maria Eugénia Captivo
Resolução de alguns exercícios da Folha 2.