Créditos ECTS Créditos ECTS: 5
Horas ECTS Criterios/Memorias Trabajo del Alumno/a ECTS: 85 Horas de Tutorías: 5 Clase Expositiva: 20 Clase Interactiva: 15 Total: 125
Lenguas de uso Castellano, Gallego
Tipo: Materia Ordinaria Máster RD 1393/2007 - 822/2021
Departamentos: Departamento externo vinculado a las titulaciones, Estadística, Análisis Matemático y Optimización
Áreas: Área externa M.U en Técnicas Estatísticas (2ªed), Estadística e Investigación Operativa
Centro Facultad de Matemáticas
Convocatoria: Primer semestre
Docencia: Con docencia
Matrícula: Matriculable | 1ro curso (Si)
En esta materia se pretende familiarizar al alumnado con los modelos de la programación lineal y entera. Los objetivos a alcanzar como resultado del aprendizaje son:
• Saber identificar y modelizar problemas complejos de programación lineal y entera.
• Saber identificar y modelizar problemas complejos de optimización en redes.
• Conocer el software adecuado para resolver problemas de programación lineal y entera y de optimización en redes.
Tema 1. Programación lineal (21 horas).
- Introducción.
- Definiciones y ejemplos.
- Resolución gráfica de problemas de programación lineal.
- Resolución práctica de problemas de optimización.
- Ejemplos prácticos con software adecuado en el ámbito de la optimización.
- Álgebra lineal, análisis convexo y geometría.
- Propiedades de los problemas de programación lineal.
- Fundamentos del método símplex.
- El método símplex.
- Dualidad y análisis de sensibilidad.
- Reformulaciones lineales de elementos no lineales (con software adecuado).
Tema 2. Panorámica de la optimización matemática (4 horas).
- Clases de problemas de optimización.
- Algoritmos y complejidad computacional.
Tema 3. Programación entera (6 horas).
- Introducción.
- Ejemplos de problemas de programación entera.
- Formulando relaciones lógicas con variables binarias.
- Técnicas de resolución: ramificación y acotación.
- Introducción a las heurísticas (ilustración con el problema del viajante).
- Ejemplos aplicados de problemas de programación entera (con software adecuado).
Tema 4. Introducción a los problemas de optimización en redes (4 horas).
- Conceptos básicos de grafos.
- Problema de flujo en redes con coste mínimo y unimodularidad.
- Ejemplos aplicados de problemas de flujo en redes (con software adecuado).
Bibliografía básica
• AHUJA, R.K., MAGNANTI, T.L., ORLIN, J.B. (1993): "Network flows. Theory, algorithms and applications". Prentice-Hall.
• ANDERSON, D., SWEENEY, D., WILLIAMS, T. (1993): "Introducción a los modelos cuantitativos para administración". Grupo Editorial Iberoamérica.
• BAZARAA, M., JARVIS, J., SHERALI, H. (2005): "Linear programming and networks flows". John Wiley & Sons.
• HILLIER, F., LIEBERMAN, G. (2005): "Introduction to operations research". McGrawHill.
• LUENBERGER, D., YE, Y. (2021): "Linear and nonlinear programming". Springer. Consulta online: https://link.springer.com/book/10.1007/978-3-030-85450-8
• MARTÍN, Q., SANTOS, M. T., SANTANA, Y. (2005): "Investigación operativa: problemas y ejercicios resueltos". Pearson.
• VANDERBEI, R. J. (2014): "Linear programming". Springer. Consulta online: https://link.springer.com/content/pdf/10.1007%2F978-1-4614-7630-6
Bibliografía complementaria
• AARTS, E., LENSTRA, J. K. (2003): "Local search in combinatorial optimization". Ed. Princeton University Press.
• BHATTI, M. A. (2000): "Practical optimization methods", Springer-Verlag.
• CORTEZ, P. (2014): "Modern optimization with R", Springer-Verlag.
• DENARDO, E. V. (1982): "Dynamic programming. Models and applications". Ed. Prentice-Hall.
• FERRIS, M. C., MANGASARIAN, O. L., WRIGHT, S. J. (2007): "Linear programming with MATLAB". Ed. MPS-SIAM Series on Optimization.
• FOURER, R., GAY, D. M., KERNIGHAM, B. W. (2002): "AMPL: A modeling language for mathematical programming". Ed. Duxbury Press. Consulta online: https://ampl.com/resources/the-ampl-book/chapter-downloads/
• GOBERNA, M., JORNET, V., PUENTE, R. (2004): "Optimización lineal. Teoría, métodos y modelos". McGraw-Hill.
• GUROBI OPTIMIZATION. "The Fastest Solver". https://www.gurobi.com/
• JENSEN, P. A., BARD, J. F. (2003): "Operations research models and methods". Ed. Wiley.
• MARTÍN, Q. (2003): "Investigación operativa". Pearson. Hespérides.
• PARLAR, M. (2000): "Interactive operations research with Maple. Methods and models". Birkhauser.
• RÍOS INSUA, S., RÍOS INSUA, D., MATEOS, A., MARTÍN, J (1997): "Programación lineal y aplicaciones". Ra-Ma.
• RÍOS INSUA, S. (1996): "Investigación operativa. Programación lineal y aplicaciones". Centro de Estudios Ramón Areces.
• SALAZAR GONZÁLEZ, J. S. (2000): "Lecciones de optimización". Servicio de Publicaciones de la Universidad de la Laguna.
• SALAZAR GONZÁLEZ, J. S. (2001): "Programación matemática". Díaz de Santos.
• TAHA, H. (2004): "Investigación de operaciones". Ed. Pearson.
• THIE, P. R., KEOUGH, G. E. (2008): "An introduction to linear programming and game theory". Ed. Wiley.
• WINSTON, W. (2003): "Introduction to mathematical programming: operations research". Pacific Grove: Brooks/C.
En esta materia se trabajarán las competencias básicas, generales y transversales recogidas en la memoria del título. Se indican a continuación cuáles son las competencias específicas, que se potenciarán en esta materia:
E1 - Conocer, identificar, modelar, estudiar y resolver problemas complejos de estadística e investigación operativa, en un contexto científico, tecnológico o profesional, surgidos en aplicaciones reales.
E2 - Desarrollar autonomía para la resolución práctica de problemas complejos surgidos en aplicaciones reales y para la interpretación de los resultados de cara a la ayuda en la toma de decisiones.
E6 - Adquirir conocimientos teórico-prácticos avanzados de distintas técnicas matemáticas, orientadas específicamente a la ayuda en la toma de decisiones, y desarrollar capacidad de reflexión para evaluar y decidir entre distintas perspectivas en contextos complejos.
E7 - Adquirir conocimientos teórico-prácticos avanzados de distintas técnicas de optimización matemática, tanto en contextos unipersonales como multipersonales, y saber aplicarlos con autonomía suficiente en un contexto científico, tecnológico o profesional.
La enseñanza constará de clases expositivas e interactivas, así como de la tutorización del aprendizaje y de las tareas encomendadas al alumnado.
En las clases expositivas e interactivas se resolverán ejemplos mediante el software adecuado en el ámbito de la optimización, por lo que es necesario que el alumnado disponga en el aula de un ordenador.
Se propondrán actividades para el alumnado, que consistirán en la resolución de cuestiones, ejercicios y ejemplos relacionados con la programación lineal y entera.
Se proporcionarán los apuntes de la materia, así como otro material orientativo del aprendizaje del software. Los apuntes y otros instrumentos didácticos estarán disponibles a través de alguna herramienta de acceso por vía web.
La calificación final procederá, al 100%, de la evaluación continua, que consistirá en la entrega y revisión de distintos trabajos propuestos a lo largo del curso, incluyendo la posibilidad de que la evaluación se apoye en la exposición oral de alguno de los trabajos y de que se realice una evaluación por pares de los trabajos entregados. En estos trabajos, el alumnado utilizará el software de optimización adecuado en cada caso y redactará las conclusiones extraídas.
A partir de estos trabajos se podrá valorar el nivel de adquisición de las competencias básicas CB6-CB10 (modelado de problemas argumentando la adecuación de los mismos frente a otras alternativas) y generales CG1-CG5. También se evaluará el nivel alcanzado en las competencias específicas E1, E2 y E7 (resolución de problemas, empleo de algoritmos específicos y discusión y presentación de las soluciones obtenidas). Así mismo se tendrá en cuenta en la evaluación el nivel alcanzado en las competencias transversales CT1, CT3-CT5, de modo que alguno de los trabajos será realizado en grupo.
No obstante, de no superar la materia por medio de la evaluación continua, el alumno dispondrá de dos oportunidades para la realización de un examen escrito.
Cada crédito ECTS se traduce en 7 horas de clase de tipo presencial. Se estima que el alumno necesitará, por cada hora de clase presencial, una hora adicional para la comprensión global de los contenidos. Además, la realización de trabajos de evaluación continua ascenderá a 10 horas por crédito ECTS. En total resultarán 24 horas por crédito ECTS.
Es conveniente que el alumnado posea conocimientos básicos de álgebra, geometría, cálculo de probabilidades y estadística. También es recomendable disponer de unas habilidades medias en el manejo de ordenadores, y en concreto de software de estadística e investigación operativa. Para un mejor aprendizaje de la materia, conviene tener presente el sentido práctico de los métodos que se están conociendo.
Se aconseja participar activamente en el proceso de aprendizaje de la materia: asistencia y participación a las clases teóricas, prácticas, y de ordenador, utilización de horas de tutorías y la realización de un esfuerzo responsable de trabajo y asimilación personal de los métodos estudiados.
Como recursos para el aprendizaje, se hará uso de la bibliografía y apuntes, software libre o con licencia académica y material de apoyo proporcionado mediante el sitio web del Máster en Técnicas Estadísticas.
El desarrollo de los contenidos de la materia se realizará teniendo en cuenta que las competencias a adquirir por el alumnado deben cumplir con el nivel MECES3. En este sentido, si bien los contenidos de la materia se centran en modelos de programación lineal y entera, la asignatura tendrá una gran componente práctica, con énfasis en la identificación y modelizado de problemas reales.
En particular, se presentarán todas las fases de la metodología propia de la investigación operativa: definición del problema (alternativas, objetivos, restricciones y recogida de datos), formulación de un modelo (selección de variables de decisión y definición de funciones), solución del modelo (algoritmos de resolución exacta), validación del modelo, técnicas especiales, soluciones aproximadas, heurísticos y metaheurísticos (para problemas complejos) y puesta en práctica de la solución. Se prestará atención a la formulación de relaciones lógicas y a la reformulación lineal de problemas no lineales y se mostrarán ejemplos aplicados de programación lineal, entera y de flujo en redes tomados del ámbito de la economía y la ingeniería.
Como herramienta de resolución de problemas, además de trabajar con alguna herramienta específica para problemas lineales (como LPSolve o Gurobi) se estudiarán diferentes lenguajes de modelado algebraico. Estos lenguajes permiten un rápido modelizado y resolución de problemas complejos.
Para los casos de realización fraudulenta de ejercicios o pruebas, será de aplicación lo recogido en las respectivas normativas de las universidades participantes en el Máster en Técnicas Estadísticas.
Alejandro Saavedra Nieves
Coordinador/a- Departamento
- Estadística, Análisis Matemático y Optimización
- Área
- Estadística e Investigación Operativa
- Correo electrónico
- alejandro.saavedra.nieves [at] usc.es
- Categoría
- Profesor/a: Profesor Ayudante Doctor LOU