Escuchar

20329. Introducción a la Optimización . Grupo 9

Identificación de la asignatura

Asignatura20329 - Introducción a la Optimización
Grupo Grup 9 ( Campus Digital )
Año académico 2019-20
Créditos6 créditos
Periodo de impartición Segundo semestre
Idioma de impartición Castellano
Titulación
  • Grado en Ingeniería Telemática - Cuarto curso
  • Doble titulación: Grado en Matemáticas y Grado en Ingeniería Telemática - Cuarto curso
  • Grado en Matemáticas - Tercer curso
  • Grado en Ingeniería Informática (Plan 2014) - Tercer curso

Profesores

Profesor/aHorario de atención alumnos
Hora de inicioHora de finDía de la semanaFecha de inicioFecha de finDespacho/Edificio
Jairo Enrique Rocha Cárdenas
jairojairo@uib.esuib.es
Responsable
Hay que concertar cita previa con el profesor para hacer una tutoría

Contextualización

La optimización es una rama relativamente nueva de la matemática
que se ha estudiado y desarrollado básicamente en las últimas seis décadas.
Aún así, su crecimiento e interés han sido vertiginosos debido básicamente
al desarrollo teórico y sus múltiples aplicaciones, no sólo en el ámbito continuo sino también de la optimización combinatoria.

Una propiedad fundamental de un programa lineal es que
cuando el mínimo existe, lo hace sobre un vértice del poliedro que definen las
desigualdades. El método Simplex, inventado por George Dantzig en 1947
mientras trabajaba en el Pentágono, Departamento de Defensa de EE. UU., es un proceso iterativo que
depende de esta propiedad: busca un punto no interior al poliedro que
mejore la función a optimizar. La simplicidad del método, su facilidad
de implementación exacta y su velocidad han sido desde su descubrimiento
los guardianes de su amplia popularidad en los medios académicos e
industriales.

En 1984, Narendra Karmarkar describió un método polinomial para la PL que
era 50 veces más rápido que el método Simplex en ciertos problemas y que según
afirma Margaret Wright del Courant Institute of Mathematical
Sciences, marcó el comienzo de la ``revolución''
de los métodos de punto interior.

Un año después se mostró que había una equivalencia entre el método
de Karmarkar y los métodos de barrera clásicos. Estos métodos
fueron ampliamente usados en los 60 para problemas de optimización no
lineal pero perdieron popularidad en la siguiente
década por su ineficiencia comparada con otros métodos y sus casos
mal condicionados. Los otros métodos son métodos del lagraniano aumentado y
métodos de programación cuadrática secuencial que son populares hoy en día.

La nueva perspectiva dada a los métodos de barrera condujo no sólo
a mejorar la complejidad de los métodos para programación lineal
sino también para programación no lineal, porque a diferencia
del método Simplex, dichos métodos son generales.

La ``revolución'' de los métodos de punto interior llevó a un cambio
de actitud acerca de la optimización continua. Hoy en día, en contraste
con antes de 1984, nadie piensa que la programación lineal y no
lineal son independientes. En la práctica actual, los
programas comerciales de PL ofrecen métodos de punto interior
junto con el Simplex porque, dependiendo de las características
del problema, un método puede ser más rápido que el otro; algunos paquetes
permiten que el usuario escoja el método.

Requisitos

Ls prerequisitos matemáticos son mínimos, únicamente cálculo multidimensional, álgebra lineal y métodos numéricos básicos. Por ejemplo, el estudiante debería saber sobre la velocidad de convergencia de los métodos iterativos.

Recomendables

Es conveniente haber cursado las asignaturas obligatorias
Cálculo Integral en Varias Variables y Métodos Numéricos I.

Competencias

Los principios docentes para impartir esta asignatura son:

1- El desarrollo de habilidades más que la transmisión de conocimientos.
2- La autoformación.
3- La habilidad para buscar soluciones.
4- Evitar aplicar recetas.

Se propone que el método Simplex sea sólo esbozado
pero no estudiando en detalle por tres razones: la primera,
el objetivo no es dominar la receta porque ésta se olvidará
rápidamente, y segunda, cualquier profesional que lo necesite usar, podrá copiar una de sus cientos de implementaciones
fácilmente accesibles en Internet.

Específicas

  • E26. Saber plantear y resolver analíticamente problemas de optimización relacionados con ámbitos no necesariamente matemáticos, aplicando los métodos estudiados para resolverlos.
  • E6. Conocer algunas aplicaciones del cálculo matricial y, en general, de los métodos lineales, en diferentes ámbitos del conocimiento: ciencias, ciencias sociales y económicas, ingeniería y arquitectura.
  • E41. Capacidad de realizar las diferentes etapas en el proceso de modelado matemático: planteamiento del problema, experimentación/pruebas, modelo matemático, simulación/programa, discusión de los resultados y refinamiento/replanteamiento del modelo.
  • E42. Conocer los principios y resultados básicos de la Programación Matemática.
  • E43. Plantear y resolver problemas de programación lineal y entera.

Genéricas

  • TG4. Saber desarrollar programas y utilizar aplicaciones informáticas para experimentar en matemáticas y resolver problemas, decidiendo en cada caso el entorno computacional más adecuado.
  • TG9. Capacidad de asimilar la definición de un nuevo objeto matemático, en términos de otros conocidos, y ser capaz de utilizar este objeto en diferentes contextos.
  • TG10. Capacidad para aplicar los conocimientos adquiridos a la construcción de demostraciones, detección de errores en razonamientos incorrectos y resolución de problemas.
  • TG11. Capacidad de abstraer las propiedades estructurales de objetos matemáticos, de la realidad observada y de otros ámbitos, y saber probarlas mediante demostraciones sencillas o refutarlas mediante contraejemplos.
  • TG12. Capacidad de proponer, analizar, validar e interpretar modelos de situaciones reales sencillas.

Básicas

Se pueden consultar las competencias básicas que el estudiante tiene que haber adquirido al finalizar el grado en la siguiente dirección: http://estudis.uib.cat/es/grau/comp_basiques/

Contenidos

La asignatura proporciona una discución sistemática de la optimización continua nolineal y lineal como caso particular. También introduce los conceptos básicos de la optimización entera.

Descriptores del plan de estudios:

La metodología de la investigación operativa. Introducción a los modelos lineales:
formulación de modelos lineales. Teorema fundamental de la programación lineal. El algoritmo
del símplex primal. La geometría de la programación lineal. Dualidad. Interpretaciones
económicas. Análisis de sensibilidad. Aplicaciones. Introducción a los modelos de
programación entera: formulación de modelos enteros. Métodos enumerativos. Métodos de
planos de corte. Aplicación a problemas concretos de programación entera. Introducción a la
optimización. Funciones convexas. Existencia de un mínimo. Condiciones de minimalidad.
Restricciones convexas. Punto de silla y Teorema de Kuhn-Tucker. Algoritmos de optimización
sin restricciones: relajación, gradiente a paso fijo y paso optimal. Velocidad de convergencia.
Algoritmos con restricciones: relajación, gradiente a paso fijo con proyección. Algoritmo de
Uzawa. Aplicaciones. Ilustración de los principales conceptos y algoritmos con paquetes de
optimización de uso habitual.

Contenidos temáticos

1 Introducción y aplicaciones

La metodología de la investigación operativa. Introducción a la optimización. Introducción a los modelos lineales: formulación de modelos lineales fraccionados y enteros. Modelos de problemas concretos de programación matemática en áreas de procesos industriales, horarios, cortes, transporte, telecomunicaciones, economía, y distribución. Simplex y dualidad lineal.

Resumen histórico.

Programación entera: ramificación y acotación, corte de Gomory, matrices totalmente unimodulares.

2 Las condiciones de Karush-Kuhn-Tucker

Condiciones de Karush-Kunh-Tucker.

3 Optimizacion sin restricciones

Conjuntos convexos, Métodos de búsqueda lineal, métodos de descenso, de Newton, de Levenberg-Marquardt, de gradiente conjugado y de cuasi_Newton.

4 Optimización con restricciones

Métodos de penalización y SQP (programación cuadrática secuencial)

Metodología docente

Actividades de trabajo presencial (2,4 créditos, 60 horas)

ModalidadNombreTip. agr.DescripciónHoras
Clases teóricas Clases de teoría Grupo grande (G)

El profesor explica los contenidos y ejemplos del libro en la pizarra.

23
Seminarios y talleres Exposiciones Grupo mediano (M)

Los estudiantes presentan algunos contenidos del libro y adicionales.

18
Clases prácticas Clases de resolución de problemas Grupo mediano (M)

Los estudiantes resuelven los ejercicios en la pizarra con ayuda de los compañeros y el profesor. Resolución en grupos.

12
Evaluación Primer Parcial Grupo mediano (M)

Examen de los primeros temas de la asignatura.

2
Evaluación Segundo Parcial Grupo mediano (M)

Examen de los siguientes temas de la asignatura.

2
Evaluación Examen Final Grupo mediano (M)

Examen de todos los contenidos.

3

Al inicio del semestre estará a disposición de los estudiantes el cronograma de la asignatura a través de la plataforma UIBdigital. Este cronograma incluirá al menos las fechas en las que se realizarán las pruebas de evaluación continua y las fechas de entrega de los trabajos. Asimismo, el profesor o la profesora informará a los estudiantes si el plan de trabajo de la asignatura se realizará a través del cronograma o mediante otra vía, incluida la plataforma Aula Digital.

Actividades de trabajo no presencial (3,6 créditos, 90 horas)

ModalidadNombreDescripciónHoras
Estudio y trabajo autónomo individual Estudio de la teoría

El estudiante estudia del libro los conceptos y los ejemplos

30
Estudio y trabajo autónomo individual o en grupo Resolución de problemas

Búsqueda de las soluciones a los problemas planteados. Algunas veces los ejercicios se entregan escritos. Algunos ejercicios se implementan en un paquete informático de modelos de optimización. Implementación de soluciones en el ordenador y redacción de informes usando GAMS, SciLab, R, Sage o cualquier otro que se indique.

40
Estudio y trabajo autónomo individual o en grupo Preparación de exámenes

Estudio de todos los contenidos asignados a los exámenes y sus ejercicios.

20

Riesgos específicos y medidas de protección

Las actividades de aprendizaje de esta asignatura no conllevan riesgos específicos para la seguridad y salud de los alumnos y, por tanto, no es necesario adoptar medidas de protección especiales.

Evaluación del aprendizaje del estudiante

Se permite la evaluación anticipada en los términos contemplados en el reglamento académico.

Para aprobar la asignatura se necesita una media ponderada de los examenes parciales y final de 4,5.

De acuerdo con el artículo 33 del Reglamento Académico, "con independencia del procedimiento disciplinario que se pueda seguir contra el estudiante infractor, la realización demostradamente fraudulenta de alguno de los elementos de evaluación incluidos en guias docentes de las asignaturas comportará, a criterio del profesor, una minusvaloración en la calificación que puede suponer la cualificación de «suspenso 0» en la evaluación anual de la asignatura".

Primer Parcial
Modalidad Evaluación
Técnica Pruebas de respuesta larga, de desarrollo ( recuperable )
Descripción

Examen de los primeros temas de la asignatura.

Criterios de evaluación
Porcentaje de la calificación final: 15% para el itinerario A
Porcentaje de la calificación final: 25% para el itinerario B

Segundo Parcial
Modalidad Evaluación
Técnica Pruebas de respuesta larga, de desarrollo ( recuperable )
Descripción

Examen de los siguientes temas de la asignatura.

Criterios de evaluación
Porcentaje de la calificación final: 15% para el itinerario A
Porcentaje de la calificación final: 25% para el itinerario B

Examen Final
Modalidad Evaluación
Técnica Pruebas de respuesta larga, de desarrollo ( recuperable )
Descripción

Examen de todos los contenidos.

Criterios de evaluación
Porcentaje de la calificación final: 50% para el itinerario A
Porcentaje de la calificación final: 50% para el itinerario B

Resolución de problemas
Modalidad Estudio y trabajo autónomo individual o en grupo
Técnica Pruebas de respuesta larga, de desarrollo ( no recuperable )
Descripción

Búsqueda de las soluciones a los problemas planteados. Algunas veces los ejercicios se entregan escritos. Algunos ejercicios se implementan en un paquete informático de modelos de optimización. Implementación de soluciones en el ordenador y redacción de informes usando GAMS, SciLab, R, Sage o cualquier otro que se indique.

Criterios de evaluación
Porcentaje de la calificación final: 20% para el itinerario A
Porcentaje de la calificación final: 0% para el itinerario B

Recursos, bibliografía y documentación complementaria

Bibliografía básica

Los problemas de modelización con aplicaciones serán del libro:
Guéret, C y otros. Applications of Optimization with Xpress-MP. Dash Optimization., 2002. ISBN 0-9543503-0-8

El temario es del libro:
Chong, E.; Zak, S. An Introduction to Optimization. Fourth Edition. Wiley Series. ISBN 978-1-118-27901-4

Bibliografía complementaria

Las páginas web de paquetes de optimización de R, Maxima, Mathematica, Matlab, Scilab, GAMS,Sage, entre otros.