Programación Linear e Enteira

Introducir ao alumno na programación matemática, con énfase nas técnicas para a solución e análise dos modelos lineais.
Aprender os procedementos analíticos e algoritmos para resolver os problemas de programación lineal e saber analizar a estrutura matemática subxacente destes problemas.
Aprender a manexar as ferramentas informáticas para a resolución práctica destes problemas.

Tema 1. (12 horas expositivas)
Introdución á Investigación operativa. Os problemas de programación lineal. Formulación matemática dos problemas de programación lineal. Solución gráfica dos problemas de programación lineal. Algoritmo do símplex. Dualidade e análise da sensibilidade.
Tema 2. (2 horas expositivas)
Programación lineal enteira. Algoritmo de ramificación e anotación.
Tema 3. (2 horas expositivas)
Optimización e programación matemática: Unha panorámica. Algoritmos e complexidade computacional. Resolución de problemas de optimización.
Tema 4. (12 horas expositivas)
Programación en redes de fluxo. O problema de fluxo en redes a custo mínimo.
O problema do transporte. Método símplex do transporte.
O problema de asignación. Método húngaro.
O problema do camiño máis curto. Algoritmo de Dijkstra.
O problema do fluxo máximo. Algoritmo de traxectorias aumentadas.
O problema da árbore de expansión mínima. Algoritmo de Prim.
O problema do viaxante. Algoritmo de Christofides.

BIBLIOGRAFÍA BÁSICA
Bazaraa, M.; Jarvis, J.; Sherali, H. (2010): "Linear Programming and Networks Flows". Wiley. Dispoñible en liña a través da USC.

BIBLIOGRAFÍA COMPLEMENTARIA
Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B. (1988): "Network Flows", MIT. Dispoñible en:
https://dspace.mit.edu/handle/1721.1/49424 [Consulta: 31 de maio de 2024]
Ahuja, R.K .; Magnanti, T.L .; Orlin, J.B. (1993): "Network Flows. Theory, Algorithms and Applications". Prentice-Hall.
Hillier, F.;Lieberman, G. (2010): "Introducción a la investigación de operaciones". 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. Dispoñible en liña a través da Biblioteca da USC.

Capacidade de analizar e modelizar problemas reais no contexto da programación lineal: recoñecer os posibles problemas de programación lineal, identificar os problemas de programación lineal estudados e formular o modelo matemático destes problemas.
Ser capaces de pór en práctica os coñecementos aprendidos: planificar e executar algoritmos e métodos matemáticos para resolver problemas. Utilizar ferramentas informáticas de optimización.
Os alumnos despois de cursar esta materia, profundarían na adquisición das seguintes competencias do Grao en Matemáticas: CG1, CG2, CG3, CG4, CG5, CE1, CE2, CE3, CE4, CE5, CE6, CE7, CE8, CE9, CT1, CT2, CT3, CT4 e CT5.

As clases expositivas e interactivas de seminario serán presenciais, en aula con lousa, onde se explicarán os contidos teóricos da materia e os procedementos de resolución dos problemas (resolvendo exercicios e propondo outros para a súa resolución por parte dos alumnos).
As clases interactivas de laboratorio poderanse impartir en aula de informática, ou na súa falta, os estudantes poderán empregar os seus computadores portátiles.
Utilizaranse as ferramentas informáticas no contexto da Investigación Operativa, poñendo énfase na aplicación práctica dos coñecementos estudados na materia, e con especial interese nos recursos de programación.
Resolveranse e proporán exercicios para a súa realización por parte dos alumnos. Isto permitiranos non só pór en práctica os coñecementos estudados na materia, senón tamén adquirir os recursos necesarios para manexar as ferramentas informáticas.
Nas clases expositivas traballaranse as competencias CG1, CE1, CE2, CE3, CE4 e CT3, principalmente, mentres que nas clases interactivas de seminario e de laboratorio farase, respectivamente, coas competencias CG3, CE5, CE6, CE7, CE8 e CT3, e CE8 e CE9.

Avaliación continua: a avaliación continua levará a cabo ao longo do cuadrimestre. Consistirá na entrega de tarefas ou exercicios propostos para os temas 1, 2 e 4.
Na avaliación continua, os alumnos fortalecerán as competencias CG2, CG3, CE6, CE7, CE8, CE9, CT1, CT2, CT3, CT4 e CT5.
A cualificación obtida na avaliación continua será conservada nas dúas oportunidades do mesmo curso.

Exame final: o exame final constará de cuestións teórico-prácticas sobre os contidos da materia.
O exame final teórico-práctico permitirá traballar e avaliar, especialmente, as competencias CG1, CG2, CG3, CG4, CE2, CE6, CE7 e CE8.

A avaliación continua e o exame final poderían non ser os mesmos para os dous grupos expositivos, pero serán similares, buscando garantir unha avaliación equilibrada nos dos grupos da materia.

A nota final, tanto na primeira como na segunda oportunidade, será o máximo da cualificación do exame final teórico-práctico, por unha banda, e da media ponderada da avaliación continua (30%) e a cualificación do exame teórico-práctico (70%), por outra banda.
Os alumnos que non se presenten ao exame teórico-práctico terán a cualificación de "non presentado".

Recoméndase dedicar polo menos unha hora e media de traballo adicional por cada hora de clase expositiva e interactiva, ademais das titorías.

Asistencia a todas as actividades docentes.
Consulta da bibliografía recomendada.
Cursar "Espacios Vectoriais e Cálculo Matricial".

Os alumnos disporán dos materiais da materia no Campus Virtual (Moodle). Nestes materiais están os contidos (teóricos e prácticos) da materia.

Esta guía e os criterios e metodoloxías nela descritos están suxeitos ás modificacións que se deriven da normativa e das directrices da USC.
Indicación referida ao plaxio e ao uso indebido das tecnoloxías na realización das tarefas ou probas: Para os casos de realización fraudulenta de exercicios ou probas, será de aplicación o recolleito na “Normativa de avaliación do rendemento académico dos estudantes e da revisión das cualificacións”.