ECTS credits ECTS credits: 6
ECTS Hours Rules/Memories Student's work ECTS: 99 Hours of tutorials: 3 Expository Class: 24 Interactive Classroom: 24 Total: 150
Use languages Spanish, Galician
Type: Ordinary Degree Subject RD 1393/2007 - 822/2021
Departments: Statistics, Mathematical Analysis and Optimisation
Areas: Statistics and Operations Research
Center Faculty of Mathematics
Call:
Teaching: Sin docencia (Extinguida)
Enrolment: No Matriculable
To introduce the student to mathematical programming, with emphasis on the techniques for the solution and analysis of linear models.
To learn the analytical procedures and algorithms to solve linear programming problems and to know how to analyze the underlying mathematical structure of these problems.
To learn how to handle the computer tools for the practical solution of these problems.
Unit 1. (12 lectures hours)
Introduction to Operations Research. Linear Programming Problems. Mathematical formulation of Linear Programming Problems. Graphical solution to Linear Programming Problems. Simplex Algorithm. Duality and sensitivity analysis.
Unit 2. (2 lectures hours)
Integer Linear Programming. The Branch and Bound Algorithm.
Unit 3. (2 lectures hours)
Optimization and mathematical programming: An overview. Algorithms and computational complexity. Solving optimization problems.
Unit 4. (12 lectures hours)
Programming in Flow Networks. The Minimum Cost Network Flow Problem.
The Transport Problem. Transportation Simplex Method.
The Assignment Problem. The Hungarian method.
The Shortest Path Problem. The Dijkstra's Algorithm.
The Maximum Flow Problem. The Augmenting Path Algorithm.
The Minimum Spanning Tree Problem. The Prim's Algorithm.
The Traveling Salesman Problem. The Christofides's Algorithm.
BASIC BIBLIOGRAPHY
Bazaraa, M.; Jarvis, J.; Sherali, H. (2010): "Linear Programming and Networks Flows". Wiley. Available online through USC.
SUPPLEMENTARY BIBLIOGRAPHY.
Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B. (1988): "Network Flows", MIT. Available at:
https://dspace.mit.edu/handle/1721.1/49424 [Accessed May 31st, 2024].
Ahuja, R.K .; Magnanti, T.L .; Orlin, J.B. (1993): "Network Flows. Theory, Algorithms and Applications". Prentice-Hall.
Hillier, F.;Lieberman, G. (2010): "Introduction to operations research". McGraw-Hill.
Salazar González, J. S. (2001): "Programación matemática". Díaz de Santos.
Sierksma, G.; Zwols, Y. (2015): "Linear and Integer Optimization. Theory and Practice", CRC Press.
Thie, P. R.; Keough, G. E. (2008): "An Introduction to Linear Programming and Game Theory". Wiley. Available online through the USC Library.
Ability to analyze and model real problems in the context of linear programming: recognize possible linear programming problems, identify linear programming problems studied and formulate the mathematical model of these problems.
Be able to put into practice the knowledge learned: plan and execute algorithms and mathematical methods to solve problems. Use computer optimization tools.
After taking this subject, students will have deepened in the acquisition of the following competences of the Degree in Mathematics: CG1, CG2, CG3, CG4, CG5, CE1, CE2, CE3, CE4, CE5, CE6, CE7, CE8, CE9, CT1, CT2, CT3, CT4 and CT5.
The lectures and seminars will be in the classroom with blackboard, where the theoretical contents of the subject and the procedures for solving the problems will be explained (solving exercises and proposing others to be solved by the students).
The laboratory can be taught in a computer classroom, or otherwise, students could use their laptops.
Computer tools will be used in the context of Operations Research, emphasizing the practical application of the knowledge studied in the subject, and with special interest in programming resources.
Exercises will be solved and proposed to be carried out by the students. This will allow us not only to put into practice the knowledge studied in the subject, but also to acquire the necessary resources to handle the computer tools.
In the expository classes we will work mainly on the competences CG1, CE1, CE2, CE3, CE4 and CT3, while in the interactive seminar and laboratory classes we will work, respectively, with the competences CG3, CE5, CE6, CE7, CE8 and CT3, and CE8 and CE9.
Coursework: the coursework will be carried out throughout the semester. It will consist of the delivery of tasks or exercises proposed for units 1, 2 and 4.
In the coursework, students will strengthen the competences CG2, CG3, CE6, CE7, CE8, CE9, CT1, CT2, CT3, CT4 and CT5.
The grade obtained in the coursework will be kept in the two opportunities of the same course.
Final exam: the final exam will consist of theoretical-practical questions on the contents of the subject.
The final theoretical-practical exam will allow to work and evaluate, especially, the competences CG1, CG2, CG3, CG4, CE2, CE6, CE7 and CE8.
The coursework and the final exam may not be the same for both lectures groups, but they will be similar, seeking to guarantee a balanced assessment for the two groups of the course.
The final mark, both in the first and in the second opportunity, will be the maximum of the grade of the final theoretical-practical exam, on the one hand, and of the weighted average of the coursework (30%) and the grade of the theoretical-practical exam (70%), on the other hand.
Students who do not take the theoretical-practical exam will have the grade of "not submitted".
It is recommended to dedicate at least an hour and a half of additional work for each hour of expository and interactive class, in addition to the tutorials.
Assistance to all teaching activities.
Consult the recommended bibliography.
Undertake the course "Vector Spaces and Matrix Calculus" (Espacios Vectoriales y Cálculo Matricial).
The students will have the materials of the course in the Virtual Campus (Moodle). In these materials are the contents (theoretical and practical) of the subject.
This guide and the criteria and methodologies described in it are subject to modifications derived from the regulations and guidelines of the USC.
Indication referring to plagiarism and improper use of technologies in the performance of tasks or tests: For cases of fraudulent performance of exercises or tests, the provisions of the "Regulations for the evaluation of the academic performance of students and the review of grades" will apply.
Balbina Virginia Casas Mendez
- Department
- Statistics, Mathematical Analysis and Optimisation
- Area
- Statistics and Operations Research
- Phone
- 881813180
- balbina.casas.mendez [at] usc.es
- Category
- Professor: University Lecturer
Maria Angeles Casares De Cal
- Department
- Statistics, Mathematical Analysis and Optimisation
- Area
- Statistics and Operations Research
- Phone
- 881813183
- mariadelosangeles.casares.decal [at] usc.es
- Category
- Professor: University Lecturer
Julio Gonzalez Diaz
Coordinador/a- Department
- Statistics, Mathematical Analysis and Optimisation
- Area
- Statistics and Operations Research
- Phone
- 881813207
- julio.gonzalez [at] usc.es
- Category
- Professor: University Lecturer
Iria Rodríguez Acevedo
- Department
- Statistics, Mathematical Analysis and Optimisation
- Area
- Statistics and Operations Research
- iriarodriguez.acevedo [at] usc.es
- Category
- Xunta Pre-doctoral Contract
| Monday | |||
|---|---|---|---|
| 15:00-16:00 | Grupo /CLE_01 | Spanish | Classroom 02 |
| 17:00-18:00 | Grupo /CLIS_03 | Spanish | Classroom 08 |
| 18:00-19:00 | Grupo /CLIS_04 | Spanish | Classroom 07 |
| Tuesday | |||
| 15:00-16:00 | Grupo /CLE_01 | Spanish | Classroom 02 |
| 17:00-18:00 | Grupo /CLE_02 | Spanish | Classroom 03 |
| Wednesday | |||
| 15:00-16:00 | Grupo /CLIS_01 | Spanish | Classroom 07 |
| 15:00-16:00 | Grupo /CLIL_04 | Spanish | Computer room 3 |
| 16:00-17:00 | Grupo /CLIS_02 | Spanish | Classroom 08 |
| 16:00-17:00 | Grupo /CLIL_06 | Spanish | Computer room 3 |
| 18:00-19:00 | Grupo /CLIL_05 | Spanish | Computer room 3 |
| Thursday | |||
| 15:00-16:00 | Grupo /CLIL_01 | Spanish | Computer room 3 |
| 16:00-17:00 | Grupo /CLIL_03 | Spanish | Computer room 3 |
| 17:00-18:00 | Grupo /CLE_02 | Spanish | Classroom 03 |
| 18:00-19:00 | Grupo /CLIL_02 | Spanish | Computer room 3 |
| 01.22.2025 16:00-20:00 | Grupo /CLE_01 | Classroom 06 |
| 06.25.2025 10:00-14:00 | Grupo /CLE_01 | Classroom 06 |