Programação Linear e Otimização Combinatória

Conhecimentos de Base Recomendados

Conhecimentos de Álgebra Linear e Matemática Discreta.

Métodos de Ensino

Aulas teórico-práticas de dois tipos: aulas em que o professor expõe os conceitos teóricos e apresenta exemplos, e aulas de discussão de exercícios e de resolução de problemas pelos alunos, pontualmente com recurso a software adequado. Ao longo do semestre é disponibilizado aos alunos apoio tutorial à resolução dos exercícios e à preparação para provas de avaliação.

Resultados de Aprendizagem

Definem-se conceitos fundamentais e demonstram-se resultados clássicos de programação linear (algoritmo simplex nas vertentes de cálculo numérico, convergência, implementação e análise de sensibilidade pós-otimal e simplificações decorrentes da aplicação a problemas de otimização em redes) e otimização combinatória (formulação algébrica, algoritmos e resultados para problemas clássicos com e sem estrutura) com ênfase nos aspetos comuns às duas áreas.

Esta unidade permite desenvolver as seguintes competências instrumentais: conhecimento de resultados matemáticos; capacidade de formular e resolver problemas; conceção ou utilização de modelos matemáticos para situações reais. A nível pessoal permite também desenvolver expressões escrita e oral rigorosas e claras, a competência na utilização de ferramentas computacionais, a iniciativa individual e o trabalho em equipa, a capacidade de aprendizagem autónoma e o espírito crítico.

Estágio(s)

Não

Programa

Programação Linear
• Programa linear. Pontos básicos admissíveis. Convexidade e pontos extremos de poliedros
• Dualidade. O problema primal e o problema dual. O teorema fundamental da Programação Linear
• Método simplex
• Análise de sensibilidade pós-optimal
• Conceitos fundamentais de grafos. Árvore geradora mínima
• Método simplex para o problema do fluxo de custo mínimo

Otimização Combinatória
• Formulação de programas lineares inteiros
• Caminhos mais curtos
• Fluxo máximo/corte mínimo
• Emparelhamentos
• Estrutura facial de poliedros e algoritmos de planos cortantes e branch-and-bound
• Análise de um problema específico (e.g., caixeiro viajante).

Docente(s) responsável(eis)

João Eduardo da Silveira Gouveia

Métodos de Avaliação

Avaliação Continua
A avaliação ao longo do semestre pressupõe a realização de duas frequências (com um peso total de 75%), a resolução de um conjunto de exercícios entregues individualmente (com um peso de 10%) e a execução de um trabalho computacional simples feito em grupos de 2 ou 3 alunos (com um peso de 15%). : 100.0%

Avaliação final
A avaliação por exame final inclui a realização de um exame com um peso de 100%: 100.0%

Bibliografia

W. Cook, W. Cunningham, W. Pulleyblank, A. Schrijver, CombinatorialOptimization, Wiley-Interscience, 1998.

J. Júdice, P. Martins, M. Pascoal, J. Santos, ProgramaçãoLinear, Departamento de Matemática da FCTUC, 2009.

J.J. Júdice, P. Martins, M. Pascoal, J. Santos, OtimizaçãoemRedes, Departamento de Matemática da FCTUC, 2009.

M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, LinearProgrammingandNetworkFlows, segunda edição, Wiley & Sons, 1990.

I. Griva, S.G. Nash, A. Sofer, Linear and Nonlinear Optimization, SIAM, 2009.