Otimização e Algoritmos

Ficha de Unidade Curricular – 2º Ciclo

Unidade Curricular / Curricular Unit
Otimização e Algoritmos

Ciclo de Estudos / Study Cycle
Mestrado em Engenharia Informática e Sistemas de Informação/Master in Computer Engineering and Information Systems

Nome do Docente Responsável
Ricardo Vicente Raposo Crespo de Oliveira

Nome do Docente Adicional
João Carlos Roquete Fidalgo Canto

Objectivos de aprendizagem (conhecimentos, aptidões e competências a desenvolver pelos estudantes)
Pretende-se com esta unidade curricular que o discente tenha um contacto inicial com a área da Investigação Operacional, com um foco que não se limita ao aspecto puramente algorítmico mas que engloba igualmente o aspecto funcional desta área de conhecimento. Nesse sentido, os processos de formulação do problema matemático a partir de sistemas de decisão no mundo real revestem-se de particular importância. Em paralelo introduzir-se-á o discente a software específico de resolução de programas lineares, o qual lhe permitirá observar a solução dos problemas que forem sendo propostos.

Intended learning outcomes (knowledge, skills and competences to be developed by the students)
The main objective of this curricular unit is to provide the student with an initial contact with Operations Research, focusing not only on the purely algorithmical point of view but also on the functional aspects of this knowledge area. Consequently the processes by which a mathematical problem is modeled from a real world decision system is of paramount importance. On the other hand, the student will also have the opportunity to get acquainted with software specifically designed to solve linear programs, thus allowing him/her to obtain the solution to the proposed problems.

Conteúdos programáticos
1. Metodologia da investigação operacional. 1.1. Origens, natureza e aplicações da IO. 1.2. Técnicas matemáticas – áreas de aplicação. 1.3. O problema da decisão. 1.4. Formulação de modelos. 2. Optimização linear – Introdução 2.1. Estrutura de um programa linear. 2.2. Representação e solução gráfica de programas lineares. 3. Algoritmo Simplex – Teoria 3.1. Descrição computacional do algoritmo Simplex. 4. Algoritmo Simplex – Prática 4.1. Técnicas de modelação. 4.2. Utilização do LPSolve – casos práticos 5. Problema de transportes. 5.1. Mapeamento para um PL tradicional. 5.2. Método de Vogel. 5.3. Stepping Stone. 6. Modelos em rede. 6.1. Terminologia. 6.2. Problema do caminho mais curto. Algoritmo de “Dijkstra”. 6.3. Problema da árvore geradora mínima. Algoritmo de “Kruskal”. 6.4. Problema do Fluxo Máximo. Algoritmo de “Ford-Fulkerson”.

Syllabus
1. The methodology of Operations Research. 1.1. Origins, nature and applications of OR. 1.2. Mathematical tools – areas of application. 1.3. The decision problem. 1.4. Model Formulation. 2. Introduction to Linear Optimization 2.1. Structure of a linear program. 2.2. Geometrically representing and solving a linear program. 3. The Simplex Algorithm – Theory 3.1. Computational description of the Simplex algorithm. 4. The Simplex Algorithm – Practice 4.1. Modelling Techniques 4.2. Using LPSolve – practical examples 5. The Transportation Problem 5.1. Mapping to a traditional LP. 5.2. Vogel’s Method. 5.3. Stepping Stone. 6. Network Models. 6.1. Naming Conventions. 6.2. Shortest Path – Dijkstra’s Algorithm. 6.3. Minimum Spanning Tree – Kruskal’s Algorithm. 6.4. Maximum Flow Problem – Ford-Fulkerson’s Algorithm.

Demonstração da coerência dos conteúdos programáticos com os objectivos de aprendizagem da unidade curricular
Os conteúdos programáticos são dirigidos no sentido de proporcionar ao discente um conhecimento introdutório acerca da área de conhecimento em causa, começando por metodologias de resolução mais intuitivas e só depois abordando algoritmos mais complexos. As metodologias de modelação são leccionadas no início da cadeira por forma a que os alunos possam aplicá-las ao longo do semestre.

Evidence of the syllabus coherence with the curricular unit’s intended learning outcomes
The syllabus of this curricular unit is directed towards providing the student with an introductory knowledge of the Operations Research scientific area, starting with more intuitive problem solving methods and evolving only later towards more complex approaches. Modeling Techniques are introduced early in the syllabus in order to allow the students to practice them throughout the semester.

Metodologias de ensino (avaliação incluída)
As 2 horas de contacto semanais serão divididas entre sessões teóricas, nas quais os alunos procurarão apreender as metodologias de trabalho inerentes à IO, e em sessões de índole marcadamente prática, nas quais serão propostos problemas de aplicação relacionados com matéria leccionada. Procurar-se-á, sempre que tal seja exequível, que os exercícios resolvidos em cada sessão prática reportem à sessão teórica imediatamente anterior. A aprovação à unidade curricular ocorrerá de uma das seguintes formas: a) Por avaliação contínua: Será realizado um teste no final do semestre. b) Por avaliação final: Serão realizados dois exames, um em primeira e outro em segunda época. Em qualquer dos casos, considerar-se-ão passados os discentes que atinjam uma nota mínima de 10 valores. Apenas serão admitidas melhorias de notas em exame de segunda época.

Teaching methodologies (including assessment)
The two weekly contact hours shall be divided between theoretical sessions, during which the working methodologies inherent to OR will be lectured, and practical sessions which will serve to solve application problems related to the theory. Whenever possible, exercises solved in a practical session will be related to the most recent theoretical session. In order to successfuly finish this course the student will be required either take a test at the end of the semester, or to take an exam on either of the two proposed dates. Students wishing to improve the grade will have to do so on the second exam.

Demonstração da coerência das metodologias de ensino com os objectivos de aprendizagem da unidade curricular
Decorre dos objectivos da unidade curricular em questão que o discente, por forma a ter sucesso à mesma, deverá ser capaz de conjugar a aplicação das ferramentas matemáticas com a capacidade de modelação de problemas de decisão do dia-a-dia. Nesse sentido, e apesar de a u.c. adoptar um formato tradicional de sessões teóricas e práticas, procurar-se-á tanto no decorrer do semestre como durante a avaliação conjugar este aspecto com exercícios de modelação, permitindo desta forma que o discente tome um contacto, ainda que inicial, com o processo de trabalho em Investigação Operacional.

Evidence of the teaching methodologies coherence with the curricular unit’s intended learning outcomes
From this curricular unit’s objectives it can be assumed that for a student to successfully conclude this course he / she should not only be able to use the relevant mathematical tools but also to have the modelling skills to tackle everyday decision problems. In that sense. despite the adoption of a traditional teaching methodology based on theoretical and practical sessions the student will be required to solve modelling problems which will provide him/her with the work processes typical of OR.

Bibliografia Principal / Main Bibliography
Hillier, F. S.; Lieberman, G. J. (1995). Introduction to Operations Research, McGraw-Hill. Luenberger D.G.; Yinyu Y. (2008). Linear and Non Linear Programming, Springer.