Optimização Combinatória

Conhecimentos de Base Recomendados

Programação Linear e Matemática Discreta.

Métodos de Ensino

Se o aluno não reúne condições então em lugar dos trabalhos para casa e das frequências deve realizar um exame que corresponde a 90% da nota final.

Resultados de Aprendizagem

Em Otimização Combinatória estudamos técnicas combinadas de combinatória, programação linear e algoritmos para resolver problemas de otimização em estruturas discretas ou mistas. Exemplos de problemas reais são a calendarização de exames e aulas numa escola, o sequenciamento de tarefas num processo industrial, o dimensionamento de pessoal num centro de atendimento e o dimensionamento de redes de telecomunicações. Grande parte dos problemas provém de áreas como a Investigação Operacional e as Ciências de Computação.

 

Competências genéricas:

Competência na utilização de ferramentas computacionais;

Conhecimento de resultados matemáticos;

Capacidade de generalização e abstração;

Capacidade de formular e resolver problemas;

Conceção ou utilização de modelos matemáticos para situações reais;

Expressões escrita e oral rigorosas e claras;

Capacidade de investigação;

Imaginação e criatividade;

Espírito crítico;

Capacidade de comunicação.

Estágio(s)

Não

Programa

Árvore geradora mínima (Prim e Kruskal).

Caminhos mais curtos (Ford-Bellman e Dijkstra).

Fluxo Máximo e Corte Mínimo (Ford-Fulkerson).

Emparelhamentos em grafos bipartidos (Kuhn) e não bipartidos (Edmonds).

Unimodularidade Total (Hoffman-Kruskal e Ghouila-Houri).

Estrutura facial de poliedros (polar, pontos extremos, faces, facetas).

Planos cortantes (Gomory, lift-and-project, split, mir).

Um estudo computacional (e.g., o problema do caixeiro viajante).

Métodos de Avaliação

Avaliação
Apresentação de um trabalho (10%) + Trabalhos para casa e Duas frequências (90%) ou Exame (90%): 100.0%

Bibliografia

COOK, W.; CUNNINGHAM, W.; PULLEYBLANK W. [et.al.] (1998). Combinatorial Optimization, Wiley-Interscience. (Cota na Biblioteca: 90C/Com.Coo)