Nombre: OPTIMIZACIÓN I
Código: 525101008
Carácter: Básica
ECTS: 6
Unidad Temporal: Cuatrimestral
Despliegue Temporal: Curso 1º - Segundo cuatrimestre
Menciones/Especialidades:
Lengua en la que se imparte: Castellano
Carácter: Presencial
Nombre y apellidos: MOLINA LEGAZ, ROQUE
Área de conocimiento: Matemática Aplicada
Departamento: Matemática Aplicada y Estadística
Teléfono: 968338896
Correo electrónico: roque.molina@upct.es
Horario de atención y ubicación durante las tutorias:
martes - 16:00 / 18:00
HOSPITAL DE MARINA, planta 3, Despacho 3060
Las tutorías serán presenciales y/o online. Siempre hay que solicitar cita previa por email (roque.molina@upct.es).
Durante todo el curso se atenderán tutorías individualizadas por email (especialmente para resolver dudas puntuales).
miércoles - 16:00 / 18:00
HOSPITAL DE MARINA, planta 3, Despacho 3060
Las tutorías serán presenciales y/o online. Siempre hay que solicitar cita previa por email (roque.molina@upct.es).
Durante todo el curso se atenderán tutorías individualizadas por email (especialmente para resolver dudas puntuales).
jueves - 16:00 / 18:00
HOSPITAL DE MARINA, planta 3, Despacho 3060
Las tutorías serán presenciales y/o online. Siempre hay que solicitar cita previa por email (roque.molina@upct.es).
Durante todo el curso se atenderán tutorías individualizadas por email (especialmente para resolver dudas puntuales).
Titulaciones:
Categoría profesional: Profesor Titular de Universidad
Nº de quinquenios: 7
Nº de sexenios: 1 de investigación
Curriculum Vitae: Perfil Completo
[CB1 ]. Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio
[CB2 ]. Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio
[CB3 ]. Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética
[CG1 ]. Conocer y aplicar la analítica de datos y técnicas estadísticas apropiadas para descubrir nuevas relaciones en los datos y realizar aportaciones a procesos de las organizaciones, así como apoyar en la toma de decisiones.
[CE25 ]. Capacidad para la resolución de los problemas matemáticos básicos que puedan plantearse en la ciencia e ingeniería de datos, aplicando los conocimientos adquiridos (sobre álgebra, geometría, cálculo diferencial e integral, métodos numéricos, algorítmica numérica, estadística y optimización), y planificando su resolución en función de las herramientas de que se disponga y de las restricciones de tiempo y recursos.
[CE28 ]. Capacidad para la modelización matemática, implementación algorítmica y resolución de problemas de optimización relacionados con la ciencia de datos.
[CE31 ]. Conocimiento de herramientas informáticas en el campo del análisis de los datos y modelización estadística, y capacidad para seleccionar las más adecuadas para la resolución de los diferentes problemas.
Desarrollar analíticas especializadas para permitir la toma de decisiones.
Ilustrar ideas destacadas para resolver problemas complejos.
Formular problemas de optimización.
Aplicar el método del símplex para resolver problemas de optimización lineal.
Aplicar técnicas de ramificación y acotación y de hiperplanos de corte para la resolución de problemas enteros.
Conocer y aplicar métodos heurísticos para la resolución de problemas de programación lineal entera.
Optimización lineal (con variables continuas).<br> Método símplex.<br> Dualidad.<br> Optimización con variables enteras.<br> Métodos de ramificación y acotación.<br> Métodos de hiperplanos de corte.<br> Métodos heurísticos.
BLOQUE 1: PROGRAMACIÓN LINEAL CONTINUA
TEMA 1. INTRODUCCIÓN: Modelo general de programación lineal. Ejemplos de modelos lineales. Conjuntos poliédricos. Solución gráfica.
TEMA 2. EL MÉTODO SIMPLEX: Puntos extremos y optimalidad. Soluciones básicas factibles. Mejora de una solución básica factible. Optimalidad y no acotamiento. El método símplex. Solución básica factible inicial. Degeneración y ciclado
TEMA 3. DUALIDAD: Formulación del problema dual. Relación entre las soluciones del problema primal y el problema dual. Interpretación económica del dual. El método dual simplex.
BLOQUE 2: PROGRAMACIÓN LINEAL ENTERA
TEMA 4. INTRODUCCIÓN: Ejemplos de formulación de problemas de optimización discreta. Relajación lineal. Matrices totalmente unimodulares. Problemas que se reducen a continuos.
TEMA 5. RAMIFICACIÓN Y ACOTACIÓN: El concepto de ramificación. Inclusión de cotas en el método de ramificación. Importancia de la formulación en la resolución de problemas. Incorporación al método dual símplex.
TEMA 6. HIPERPLANOS DE CORTE: Hiperplano de corte todo entero. Hiperplano de corte mixto. Incorporación al método dual símplex.
TEMA 7. HEURÍSTICOS: Introducción a los métodos heurísticos de obtención de soluciones factibles.
PRÁCTICAS
Práctica 1. Introducción al paquete XPress y al lenguaje de programación MOSEL: Global Las prácticas de la asignatura se realizarán mediante un lenguaje de modelización. Las prácticas se basan en la formulación e implementación de modelos de programación lineal y entera por lo que todas las sesiones están relacionadas con los contenidos globales de la asignatura. A partir de una sesión inicial en la que se explicarán las nociones básicas del lenguaje, se irán introduciendo paulatinamente modelos más elaborados. Práctica 2. Modelos de programación lineal continua y programación lineal entera: Global En el resto de sesiones se irán introduciendo paulatinamente modelo más elaborados abordando, entre otros, los siguientes tópicos: - Uso de parámetros, conjuntos, arrays. - Definición de distintos tipos de variables. - Entrada de datos. - Salida de la solución óptima. - Bucles y condicionales.
La Universidad Politécnica de Cartagena considera como uno de sus principios básicos y objetivos fundamentales la promoción de la mejora continua de las condiciones de trabajo y estudio de toda la Comunidad Universitaria. Este compromiso con la prevención y las responsabilidades que se derivan atañe a todos los niveles que integran la Universidad: órganos de gobierno, equipo de dirección, personal docente e investigador, personal de administración y servicios y estudiantes. El Servicio de Prevención de Riesgos Laborales de la UPCT ha elaborado un "Manual de acogida al estudiante en materia de prevención de riesgos" que puedes encontrar en el Aula Virtual, y en el que encontraras instrucciones y recomendaciones acerca de cómo actuar de forma correcta, desde el punto de vista de la prevención (seguridad, ergonomía, etc.), cuando desarrolles cualquier tipo de actividad en la Universidad. También encontrarás recomendaciones sobre cómo proceder en caso de emergencia o que se produzca algún incidente. En especial, cuando realices prácticas docentes en laboratorios, talleres o trabajo de campo, debes seguir todas las instrucciones del profesorado, que es la persona responsable de tu seguridad y salud durante su realización. Consúltale todas las dudas que te surjan y no pongas en riesgo tu seguridad ni la de tus compañeros.
PART 1. LINEAR PROGRAMMING
UNIT 1. INTRODUCTION: General linear programming model. Examples of linear models. Polyhedral sets. Graphical solution.
UNIT 2. THE SIMPLEX METHOD: Extreme points and optimality. Basic feasible solutions. Improvement of a basic feasible solution. Optimality and non-constraint. The simplex method. Initial basic feasible solution. Degeneracy and cycling.
UNIT 3: DUALITY: Dual problem formulation. Relationship between the solutions of the primal problem and the dual problem. Economic Interpretation of the dual. The dual simplex method.
PART 2. INTEGER PROGRAMMING
UNIT 4. INTRODUCTION: Examples of discrete optimization problem formulation. Linear relaxation. Totally unimodular matrices. Problems that reduce to continuous.
UNIT 5. BRANCH AND BOUND: The concept of branching. Inclusion of coordinates in the branching method. Importance of the formulation in Problem solving. Incorporation into the dual simplex method.
UNIT 6. CUTTING PLANE: All-integer cutting hyperplane. Mixed cutting hyperplane. Incorporation to the dual simplex method.
UNIT 7: HEURISTICS: Introduction to heuristic methods of obtaining feasible solutions.
Exposición teórica: Exposición de los contenidos teóricos de la asignatura por parte del profesor. También se contemplan las sesiones informativas sobre el desarrollo del trabajo de fin de grado o prácticas externas.
Exposición teórica, clase magistral, proyección, dirigida al grupo completo de estudiantes, con independencia de que su contenido sea teórico o práctico/aplicado. Junto a la exposición de conocimientos, en las clases se plantean cuestiones, se aclaran dudas, se realizan ejemplificaciones, se establecen relaciones con las diferentes actividades prácticas que se realizan y se orienta la búsqueda de información.
30
100
Seminarios y actividades de aula: Exposición, análisis y debate dentro del contexto de aplicaciones específicas de contenidos teóricos, así como planteamiento y resolución de ejercicios y casos prácticos en el aula, tanto al grupo completo como en grupos reducidos. También se contemplan conferencias, debates y seminarios temáticos.
Exposición, análisis y debate, dentro del contexto de aplicaciones específicas de contenidos teóricos, así como planteamiento y resolución de ejercicios y casos prácticos en el aula, tanto al grupo completo, como en grupos reducidos. También se contemplan conferencias, debates y seminarios temáticos.
12
100
Prácticas de laboratorio: Ejercicios y resolución de problemas, aprendizaje orientado a proyectos, estudio de casos, exposición y discusión de trabajos, simulaciones y/o prácticas con ordenadores, generalmente desarrolladas en grupos reducidos.
Ejercicios y resolución de problemas, aprendizaje orientado a proyectos, estudio de casos, exposición y discusión de trabajos, simulaciones y/o prácticas con ordenadores, generalmente desarrolladas en grupos reducidos.
12
100
Trabajo autónomo del alumno: Estudio y preparación de contenidos teórico-prácticos, trabajo individual consistente en lecturas, búsquedas de información, sistematización de contenidos, elaboración de informes o estudio para la elaboración de casos entre otras actividades.
Trabajo personal del alumno.
90
0
Tutorías formativas y resolución de dudas: Asistencia individualizada -tutorías individuales- o en grupo -tutorías colectivas- a los estudiantes por parte del profesor.
Asistencia individualizada (tutorías individuales) o en grupo (tutorías colectivas) a los estudiantes por parte del profesor.
2
100
Evaluación: Pruebas individuales, ya sean escritas, orales o con medios informáticos, donde el estudiante demostrará los conocimientos teóricos y prácticos adquiridos durante las actividades formativas asociadas a la enseñanza de la materia.
Pruebas individuales, ya sean escritas, orales o con medios informáticos, donde el estudiante demostrará los conocimientos teóricos y prácticos adquiridos durante las actividades formativas asociadas a la enseñanza de la materia.
4
100
Exámenes individuales: Pruebas objetivas, de desarrollo, de respuesta corta, de ejecución de tareas o de escala de actitudes, realizadas por los estudiantes para mostrar los conocimientos teóricos y prácticos adquiridos ya sea de forma oral, escrita o utilizando un ordenador.
El examen constará de una parte de resolución de ejercicios, otra de formulación de un modelo de programación lineal o
programación lineal entera y otra parte de carácter teórico-práctico sobre contenidos del temario. Se valorará la correcta resolución de los ejercicios propuesta, detallando los métodos seguidos y los resultados teóricos utilizados. En la parte de formulación se valorará la validez del modelo, teniendo en cuenta que este recoja las características requeridas en el enunciado. Si un modelo no es válido podría perder toda la puntuación del apartado. En la parte teórico-práctica se valorarán la correcta redacción de los enunciados y demostraciones requeridas y la correcta aplicación de los resultados necesarios para resolver las cuestiones planteadas.
80 %
Informe técnico. En este instrumento incluimos los resultados de actividades prácticas, o de laboratorio, junto con sus memorias descriptivas y posibles resúmenes del estado del arte sobre temas concretos. La opción de realizar entrevistas personales o presentaciones de los trabajos realizados también entran en esta categoría.
A lo largo del curso se realizarán dos prácticas especiales en la que se les propondrá a los estudiantes la modelización e
implementación de unos o varios problemas de optimización lineal y/o optimización lineal entera. Se valorará la correcta formulación e implementación en XPress de los modelos planteados, así como la correcta interpretación de los resultados obtenidos.
20 %
Exámenes individuales: Pruebas objetivas, de desarrollo, de respuesta corta, de ejecución de tareas o de escala de actitudes, realizadas por los estudiantes para mostrar los conocimientos teóricos y prácticos adquiridos ya sea de forma oral, escrita o utilizando un ordenador.
El examen constará de una parte de resolución de ejercicios, otra de formulación de un modelo de programación lineal o
programación lineal entera y otra parte de carácter teórico-práctico sobre contenidos del temario. Se valorará la correcta resolución de los ejercicios propuesta, detallando los métodos seguidos y los resultados teóricos utilizados. En la parte de formulación se valorará la validez del modelo, teniendo en cuenta que este recoja las características requeridas en el enunciado. Si un modelo no es válido podría perder toda la puntuación del apartado. En la parte teórico-práctica se valorarán la correcta redacción de los enunciados y demostraciones requeridas y la correcta aplicación de los resultados necesarios para resolver las cuestiones planteadas.
80 %
Informe técnico. En este instrumento incluimos los resultados de actividades prácticas, o de laboratorio, junto con sus memorias descriptivas y posibles resúmenes del estado del arte sobre temas concretos. La opción de realizar entrevistas personales o presentaciones de los trabajos realizados también entran en esta categoría.
A lo largo del curso se realizarán dos prácticas especiales en la que se les propondrá a los estudiantes la modelización e
implementación de unos o varios problemas de optimización lineal y/o optimización lineal entera. Se valorará la correcta formulación e implementación en XPress de los modelos planteados, así como la correcta interpretación de los resultados obtenidos.
20 %
Convocatoria de mayo:
- Examen final (EF): 80%. Examen escrito de problemas, formulación y cuestiones teóricas y teórico-prácticas.
- Prácticas del curso (PC): 20%. A lo largo del curso se realizarán dos prácticas especiales en la que se les propondrá a los estudiantes la modelización e implementación de unos o varios problemas de optimización lineal y/o optimización lineal entera.
- Examen final de prácticas (EP): 20%. Optativo para aquellos estudiantes con calificación PC>=5.
La calificación final (CF) se obtendrá como
CF=0.8*EF+0.2*PR ,
donde PR=max{PC,EP} es la calificación de la parte práctica.
Para aprobar la asignatura es necesario obtener una calificación igual o superior a 3.5 en el examen final (EF>=3.5), una calificación igual o superior a 5 en la parte de prácticas (PR>=5) y una calificación final igual o superior a 5 (CF>=5).
Aquellos estudiantes que no aprueben la asignatura, pero cuya calificación en la parte práctica sea igual o superior a 6.5 (PR>=6.5), tendrán superada la parte práctica para las convocatoria de junio y enero.
Convocatorias de junio y enero:
- Examen final (EF): 80%. Examen escrito de problemas, formulación y cuestiones teóricas y teórico-prácticas.
- Examen final de prácticas (EP): 20%. Obligatorio para aquellos estudiantes que no tengan superadas las prácticas (calificación >=6.5) en convocatorias anteriores.
La calificación final (CF) se obtendrá como
CF=0.8*EF+0.2*EP.
Para aprobar la asignatura es necesario obtener una calificación igual o superior a 3.5 en el examen final (EF>=3.5), una calificación igual o superior a 5 en la parte de prácticas (PR>=5) y una calificación final igual o superior a 5 (CF>=5).
Autor: Wolsey, Laurence A.
Título: Integer programming
Editorial: John Wiley & Sons
Fecha Publicación: 1998
ISBN: 0471283665
Autor: Bazaraa, M.S.
Título: Linear programming and network flows
Editorial: Jonh Wiley & Sons
Fecha Publicación: 2005
ISBN: 0471485993
Autor: Michalewicz, Zbibniew
Título: How to solve it: modern heuristics
Editorial: Springer
Fecha Publicación: 2004
ISBN: 3540224947
Autor: H. Salkin y K. Mathur
Título: Foundations of integer programming
Editorial: Elsevier Science Ltd
Fecha Publicación: 1989
ISBN: 978-0444012319
Autor: C.R. Reeves (ed.).
Título: Modern heuristic techniques for combinatorial problems.
Editorial: John Wiley & Sons Inc
Fecha Publicación: 1993
ISBN: 978-0470220795
Autor: R. Vanderbei
Título: Linear programming: Foundations and extensions
Editorial: Springer
Fecha Publicación: 2020
ISBN: 978-3-030-39415-8
Aula virtual de la asignatura