Sumários
Fluxo de custo mínimo
27 Abril 2017, 13:00 • Maria Eugénia Captivo
Fluxo de custo mínimo admissível numa rede.
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 de PL com 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.
Fluxo Máximo
27 Abril 2017, 10:30 • Maria Eugénia Captivo
Resolução de alguns exercícios das Folhas 2 e 3.
Fluxo Máximo
26 Abril 2017, 09:00 • Maria Eugénia Captivo
Resolução de alguns exercícios das Folhas 2 e 3.
Fluxo Máximo
24 Abril 2017, 17:30 • Maria Eugénia Captivo
Demonstração da utilização do software para determinar o fluxo máximo de s a t numa rede.
Resolução de alguns exercícios da Folha 3.
Problema do fluxo máximo (s a t) numa rede (Conclusão)
24 Abril 2017, 16:30 • Maria Eugénia Captivo
Conclusão do exemplo de aplicação do 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.
Identificação da solução óptima do problema dual.
Exemplo de aplicação do algoritmo de Ford-Fulkerson partindo de um fluxo inicial admissível não nulo.
Grafos com limites superiores e inferiores no valor do fluxo que atravessa cada arco.
Determinação de um fluxo compatível. Exemplos de aplicação.
Exemplo de aplicação do algoritmo de Ford-Fulkerson partindo de um fluxo inicial admissível não nulo para o caso em que existem limites inferiores não nulos.
Identificação da solução óptima do problema dual.