Programación Lineal y Entera

Introducir al alumno en la programación matemática, con énfasis en las técnicas para la solución y análisis de los modelos lineales.
Aprender los procedimientos analíticos y algoritmos para resolver los problemas de programación lineal y saber analizar la estructura matemática subyacente de estos problemas.
Aprender a manejar las herramientas informáticas para la resolución práctica de estos problemas.

Tema 1. (12 horas expositivas)
Introducción a la Investigación operativa. Los problemas de programación lineal. Formulación matemática de los problemas de programación lineal. Solución gráfica de los problemas de programación lineal. Algoritmo del símplex. Dualidad y análisis de la sensibilidad.
Tema 2. (2 horas expositivas)
Programación lineal entera. Algoritmo de ramificación y acotación.
Tema 3. (2 horas expositivas)
Optimización y programación matemática: Una panorámica. Algoritmos y complejidad computacional. Resolución de problemas de optimización.
Tema 4. (12 horas expositivas)
Programación en redes de flujo. El problema de flujo en redes a coste mínimo.
El problema del transporte. Método símplex del transporte.
El problema de asignación. Método húngaro.
El problema del camino más corto. Algoritmo de Dijkstra.
El problema del flujo máximo. Algoritmo de trayectorias aumentadas.
El problema del árbol de expansión mínima. Algoritmo de Prim.
El problema del viajante. Algoritmo de Christofides.

BIBLIOGRAFÍA BÁSICA
Bazaraa, M.; Jarvis, J.; Sherali, H. (2010): “Linear Programming and Networks Flows”. Wiley. Disponible en línea a través de la USC.

BIBLIOGRAFÍA COMPLEMENTARIA
Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B. (1988): “Network Flows”, MIT. Disponible en:
https://dspace.mit.edu/handle/1721.1/49424 [Consulta: 31 de mayo 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. Disponible en línea a través de la Biblioteca de la USC.

Capacidad de analizar y modelizar problemas reales en el contexto de la programación lineal: reconocer los posibles problemas de programación lineal, identificar los problemas de programación lineal estudiados y formular el modelo matemático de estos problemas.
Ser capaces de poner en práctica los conocimientos aprendidos: planificar y ejecutar algoritmos y métodos matemáticos para resolver problemas. Utilizar herramientas informáticas de optimización.
Los alumnos después de cursar esta materia, habrán profundizado en la adquisición de las siguientes competencias del Grado en Matemáticas: CG1, CG2, CG3, CG4, CG5, CE1, CE2, CE3, CE4, CE5, CE6, CE7, CE8, CE9, CT1, CT2, CT3, CT4 y CT5.

Las clases expositivas e interactivas de seminario serán presenciales, en aula con pizarra, donde se explicarán los contenidos teóricos de la materia y los procedimientos de resolución de los problemas (resolviendo ejercicios y proponiendo otros para su resolución por parte de los alumnos).
Las clases interactivas de laboratorio se podrán impartir en aula de informática, o en su defecto, los estudiantes podrán emplear sus ordenadores portátiles.
Se utilizarán las herramientas informáticas en el contexto de la Investigación Operativa, poniendo énfasis en la aplicación práctica de los conocimientos estudiados en la materia, y con especial interés en los recursos de programación.
Se resolverán y propondrán ejercicios para su realización por parte de los alumnos. Esto nos permitirá no solo poner en práctica los conocimientos estudiados en la materia, sino también adquirir los recursos necesarios para manejar las herramientas informáticas.
En las clases expositivas se trabajarán las competencias CG1, CE1, CE2, CE3, CE4 y CT3, principalmente, mientras que en las clases interactivas de seminario y de laboratorio se hará, respectivamente, con las competencias CG3, CE5, CE6, CE7, CE8 y CT3, y CE8 y CE9.

Evaluación continua: la evaluación continua se llevará a cabo a lo largo del cuatrimestre. Consistirá en la entrega de tareas o ejercicios propuestos para los temas 1,2 y 4.

En la evaluación continua, los alumnos fortalecerán las competencias CG2, CG3, CE6, CE7, CE8, CE9, CT1, CT2, CT3, CT4 y CT5.
La calificación obtenida en la evaluación continua será conservada en las dos oportunidades del mismo curso.

Examen final: el examen final constará de cuestiones teórico-prácticas sobre los contenidos de la materia.
El examen final teórico-práctico permitirá trabajar y evaluar, especialmente, las competencias CG1, CG2, CG3, CG4, CE2, CE6, CE7 y CE8.

La evaluación continua y el examen final podrían no ser los mismos para los dos grupos expositivos, pero serán similares, buscando garantizar una evaluación equilibrada para los dos grupos de la materia.

La nota final, tanto en la primera como en la segunda oportunidad, será el máximo de la calificación del examen final teórico-práctico, por una parte, y de la media ponderada de la evaluación continua (30%) y la calificación del examen teórico-práctico (70%), por otra parte.

Los alumnos que no se presenten al examen teórico-práctico tendrán la calificación de "no presentado".

Se recomienda dedicar por lo menos una hora y media de trabajo adicional por cada hora de clase expositiva e interactiva, además de las tutorías.

Asistencia a todas las actividades docentes.
Consulta de la bibliografía recomendada.
Cursar "Espacios Vectoriales y Cálculo Matricial".

Los alumnos dispondrán de los materiales de la asignatura en el Campus Virtual (Moodle). En estos apuntes están los contenidos (teóricos y prácticos) de la materia.

Esta guía y los criterios y metodologías en ella descritos están sujetos a las modificaciones que se deriven de la normativa y las directrices de la USC.
Indicación referida al plagio y al uso indebido de las tecnologías en la realización de las tareas o pruebas: Para los casos de realización fraudulenta de ejercicios o pruebas, será de aplicación lo recogido en la “Normativa de evaluación del rendimiento académico de los estudiantes y de la revisión de las calificaciones”.