Sumários

Aula prática 28

2 Junho 2017, 14:30 João Filipe Quintas dos Santos Rasga

Modelação do problema do caixeiro viajante como um problema de otimização linear inteira.


Aula prática 27

1 Junho 2017, 11:30 João Filipe Quintas dos Santos Rasga

Resolução de exercícios sobre otimização linear inteira usando a técnica branch and bound.


AT26 Optimização Linear Inteira

1 Junho 2017, 10:00 Maria Cristina De Sales Viana Serôdio Sernadas

Problema de optimização linear com matriz de restrições totalmente unimodular. Condição suficiente para que matriz seja totalmente unimodular.
O problema da atribuição revisitado. Problemas com IG diferente de 1. Técnica dos cortes.


AT25 Optimização linear inteira

29 Maio 2017, 12:30 Maria Cristina De Sales Viana Serôdio Sernadas

Problema relaxado R(P) de optimização linear induzido por problema P de optimização linear inteira. Relacionamentos entre o conjunto admissível de P e o conjunto admissível de R(P) e entre o conjunto solução de P e o conjunto solução de R(P). Gap de objectivos entre P e R(P).
Matriz quadrada unimodular. Grupo de matrizes unimodulares com dimensão n. Caracterização de matriz modular. Matriz totalmente unimodular.
Preservação da propriedade totalmente unimodular por junção de linha só com um componente 1 e todos os outros 0 e por junção de coluna só com um componente 1 e todos os outros 0.


Aula prática 26

26 Maio 2017, 14:30 João Filipe Quintas dos Santos Rasga

Realização de exercício sobre a complexidade polinomial do problema LOVP. Complexidade computacional do algoritmo do simplexo.