Linear Optimization
Code
10983
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Matemática
Credits
6.0
Teacher in charge
Graça Maria Marques da Silva Gonçalves
Weekly hours
5
Total hours
75
Teaching language
Português
Objectives
In this course students will improve their previous knowledge about Optimization. In a first course (Introduction to Operations Research) the students learned some topics about Optimization, namely the Primal Simplex Method. In this course the students will learn the Revised Simplex Method, the Transportation and Assignment Problems, integer Linear Programming formulations and a Branch and Bound algorithm to solve Mixed Integer Linear Programming problems.
Prerequisites
Students should have attended Introduction to OR course and should have a basic knowledge of Linear Algebra.
Subject matter
|
1. |
Linear Programming Formulations. |
|
2. |
Building Pure and Mixed Integer Linear Programming Formulations. The uses of binary variables. |
|
3. |
Simplex Method – The Artificial-Basis Technique. |
|
4. |
The Revised Simplex Method. |
|
5. |
The Dual Simplex Method. |
|
6. |
Sensitivity and Parametric Analysis. |
|
7. |
Duality. |
|
8. |
The Transportation and Assignment Problems. |
|
9. |
A Branch and Bound algorithm for Mixed Integer Programming. |
Bibliography
| 1. |
"Linear Programming and Network Flows", Bazaraa, Jarvis & Sherali, Wiley. |
| 2. |
"Mathematical Programming: Structures and Algorithms", Shapiro, Wiley |
| 3. |
"Programação Linear", Guerreiro, Magalhães & Ramalhete, Mc Graw Hill. |
| 4. |
"Elementos de apoio às aulas de Programação Matemática", "Enunciados de Exercícios de Programação Matemática", Ruy A. Costa |
Teaching method
Classes will be held in a computer lab.
Evaluation method
Rules of evaluation
The student will be excluded of the evaluation if her/his presences in problem-solving classes are less than 2/3 of the total number of classes.
The student can be evaluated by three tests, each one graded 0-20 values. The student will be approved if the unweighted average of the three tests equals at least 9.5. The final grade will be the rounded average to the near integer.
The student can also be approved by a final exam if the exam''s grade is at least 10. The grade will be the one attained in the exam (rounded) and any grade in any test will be discarded.
Any grade improvement can be done in the final exam and will be subject to the same demands as the exam.
An additional project and/or oral exam is required for grades above 17.