(Esta asignatura se imparte solamente en castellano.)

La Programación Matemática es un área de la Investigación Operativa en la que se aplican herramientas matemáticas de optimización para encontrar la mejor solución que, satisfaciendo una serie de limitaciones, optimice un cierto objetivo. Esta asignatura tiene como objetivo el desarrollo de las bases teóricas y algoritmos para resolver problemas de optimización lineales con variables continuas y enteras.

Se estudiarán los siguientes problemas clásicos en la literatura: el problema de la mochila, de la ruta mínima, del agente viajero, del transporte, de asignación, de control inventarios, del flujo máximo, de ruta de vehículos, de localización y el de secuenciación de tareas, entre otros.

Debido a que este tipo de problemas bajo situaciones realistas son de grandes dimensiones (por la magnitud del número de variables y restricciones) o de complejidad computacional elevada, se hace necesario para resolverlos el conocimiento de técnicas de computación, así como conocimiento del software específico de optimización disponible para su resolución. También en esta asignatura se estudiarán los principios del software necesario para su resolución automatizada.

Este tipo de problemas se presentan en campos tan diversos como logística, finanzas, energía, producción, sanitario o emergencias humanitarias.

Constituye un módulo con las asignaturas Análisis Multivariante y Probabilidad y Procesos Estocásticos de cuarto de grado en matemáticas. Con este módulo se pretende que cada estudiante adquiera una formación básica y horizontal de estas materias que le permitan comprender y aplicar tales conocimientos y habilidades en múltiples direcciones interrelacionadas

COMPETENCIAS ESPECIFICAS

CM01 - Conocer en profundidad los conceptos y resultados del cálculo de probabilidades, la estadística y la programación matemática.

CM02 - Estar familiarizado con los principales algoritmos de programación matemática.

CM03 - Usar correctamente la terminología relacionada con los fenómenos aleatorios, el análisis de datos y la optimización de funciones lineales.

CM04 - Modelizar correctamente situaciones típicas relativas a fenómenos aleatorios y el tratamiento de datos.

CM05 - Estar familiarizado con recursos informáticos apropiados para el tratamiento de las situaciones mencionadas y manejar correctamente algunos de ellos.

CM06 - Seleccionar correctamente la técnica de análisis adecuada, en función del objetivo que se persigue en el estudio de esas situaciones.

CM07 - Realizar correctamente los cálculos y/o visualizaciones gráficas que requieran tales situaciones, utilizando los recursos teóricos y/o computacionales apropiados.

CM08 - Interpretar con sentido crítico los resultados de los análisis realizados.



RESULTADOS DE APRENDIZAJE

Conocer los principales conceptos, resultados teóricos, técnicas y algoritmos de resolución de la programación matemática, así como su aplicación a casos representativos.

Saber modelizar problemas utilizando técnicas de optimización lineal, entera y entera-mixta. Saber elegir razonadamente la técnica concreta más apropiada.

Resolver casos prácticos utilizando los recursos computacionales y software de optimización apropiados. Conocimiento y manejo de técnicas computacionales, funciones de COIN-OR o/y CPLEX y el lenguaje de programación C++ para la resolución de problemas de optimización lineal, entera y entera-mixta.

CONTENIDO TEÓRICO

1. PROGRAMACIÓN LINEAL

1.1 Fundamentos de la Programación lineal 1.1.1 Método geométrico. 1.1.2. Criterios de Dantzig. 1.1.3. Método de la Big

M. 1.2 Métodos Simplex primales. 1.2.1 Método Simplex primal revisado. 1.2.2 Método simplex primal por Tablas. 1.2.3 Primera fase de los métodos simplex primales. 1.2.4 Método Simplex primal para variables acotadas. 1.3 Problemas de redes. 1.3.1 Resultados de teoría de grafos. 1.3.2 Método Simplex para redes.



2. DUALIDAD. ANÁLISIS DE LA SENSIBILIDAD Y POSTOPTIMALIDAD 2.1 Introducción y resultados de dualidad. 2.1.1 Teoremas fundamentales de dualidad. 2.1.2. Dualidad y relaciones con el simplex primal. 2.1.3. Multiplicadores del simplex. 2.1.4. Teoremas de la holgura complementaria. 2.1.5. Interpretación económica de la dualidad.2.2. Métodos Simplex duales. 2.2.1 Método Simplex dual. 2.2.2. Método simplex dual para variables acotadas. 2.3 Sensibilidad y postoptimalidad.



3. PROGRAMACIÓN ENTERA 3.1 Introducción. 3.2 Algunos problemas representativos. 3.2.1 El problema de la mochila 0-1 (knapsack Problem, KP). 3.2.2 El problema del costo fijo. 3.2.3 Inventarios. 3.2.4. Un problema entero particular.

3.3 Métodos de resolución. 3.3.1 Métodos de cortes de Gomory. 3.3.2 Métodos de bifurcación y acotación. 3.3.3. Métodos de bifurcación y cortes 3.4 Programación entera 0-1. 3.4.1 Algunas técnicas de preprocesamiento. 3.5 Problemas enteros más fuertes.



4. ALGORITMOS Y CASOS PARTICULARES 4.1 Problema de la ruta mínima. Algoritmo de Dijkstra. 4.2 Problema del transporte. 4.2.1 Algoritmos para la búsqueda de una solución inicial básica factible. 4.2.2. Algoritmo del transporte. 4.2.3. Método general de búsqueda de una solución inicial 4.2.4. Problema del transbordo. 4.3 El problema de asignación. Algoritmo Húngaro. 4.4 Problema del flujo máximo. Algoritmo de Ford Fulkerson.



5. MODELIZACIONES E IMPLEMENTACIONES 5.1 El problema del viajero. (Travelling Salesman Problem, TSP). 5.1.1. Otra formulación. 5.2. El problema de las rutas de vehículos (Vehicule Routing Problem, VRP).

5.3 Problemas de localización. 5.3.1. Problema de la p-mediana. 5.3.2 El problema de localización de instalaciones capacitado. 5.3.3. Casos particulares de localización. 5.4 Secuenciación de tareas (Scheduling and Sequencing).



6. SOFTWARE DE OPTIMIZACIÓN 6.1 Introducción. 6.2 COIN-OR 1.8.0 (libre disposición) y C++. 6.2.1. Descripción de la aplicación y modelo. 6.3 CPLEX 12.6.1 (licencia académica). 6.4 LINDO y LINGO en Windows (libre con restricciones de tamaño).6.4. LINDO y LINGO bajo Windows. 6.4.1 LINDO. 6.4.2 LINGO



CONTENIDO PRÁCTICO

El alumnado realizará prácticas de ordenador relativas a los temas anteriormente expuestos.

Teoría (M): El contenido teórico se expondrá en clases magistrales siguiendo las referencias básicas que figuran en la Bibliografía y el material de uso obligatorio. Se trabajarán métodos generales y se desarrollarán ejemplos. En la plataforma eGela habrá material de apoyo referente al desarrollo de la asignatura.



Problemas (GA): Se proporcionarán relaciones de problemas para resolver ejercicios en los que se aplicarán los conocimientos adquiridos en las clases teóricas. En las clases de problemas se resolverán algunos de los mismos. Al finalizar cada tema se proporcionarán las soluciones de los ejercicios.



Seminarios (S): En los seminarios se desarrollarán casos prácticos y ejemplos representativos del contenido de la asignatura, que generalmente habrán sido facilitados con anterioridad al alumnado para trabajarlos y motiven la posterior reflexión y discusión en la sesión dedicada a ello. A lo largo del curso se realizarán dos tareas evaluables, preferiblemente en equipo, cada una de las cuales se abordará en tres sesiones de seminario. Los seminarios se realizarán en grupos (S1, S2), dependiendo del número de estudiantes matriculados.



Prácticas (GO): Se realizarán prácticas de ordenador orientadas a la consecución de las competencias de la asignatura. Para ello, se utilizará el software de optimización COIN-OR o/y CPLEX en las aulas de informática de la Facultad de Ciencia y Tecnología, siempre que la situación socio-sanitaria lo permita. Son un total de 12 horas que se distribuirán en sesiones de dos horas. Se realizarán dos tareas evaluables de casos prácticos, preferiblemente en equipo, cada una de las cuales se abordará en tres sesiones de prácticas. Las prácticas se realizarán en grupos (GO1, GO2), dependiendo del número de estudiantes matriculados.

• Ebaluazio Jarraituaren Sistema
• Azken Ebaluazioaren Sistema
• Kalifikazioko tresnak eta ehunekoak:
  • Garatu beharreko proba idatzia (%): 70
  • Praktikak egitea (ariketak, kasuak edo buruketak) (%): 5
  • alde lanak (arazoen ebazpenak, proiektuen diseinuak) (%): 5
  • Prácticas de ordenador e informes (%): 20

ORIENTACIONES PARA LA EVALUACIÓN CONTINUA

- Examen escrito 70%

- Prácticas de ordenador e informe 20%

- Realización de prácticas (ejercicios, problemas), trabajos en equipo y seminarios 10%.

La prueba escrita y las prácticas de ordenador serán de carácter obligatorio. Las tareas de seminarios se llevarán a cabo

en equipo y serán de carácter opcional. La no entrega de las tareas de seminarios implicará la pérdida del porcentaje del 10% de la nota.

Para aprobar la asignatura es necesario obtener al menos un 4 (sobre 10) en la prueba escrita y un 4 (sobre 10) en las tareas de prácticas de ordenador. Además, la nota final debe ser al menos un 5 (sobre10).

El hecho de no haber superado las actividades evaluables complementarias al examen escrito no exime al alumnado de demostrar la capacidad y conocimientos para realizar esas actividades, con lo que se propondrán unas pruebas que garanticen la evaluación de dichos conocimientos y computen para la nota final en la misma proporción que en la convocatoria ordinaria con evaluación continua. Las pruebas pueden ser una exposición oral, una demostración ante un ordenador o una descripción escrita de los conocimientos prácticos abordados en las actividades complementarias.



Aunque las actividades realizadas durante el curso hayan sido evaluadas, como el peso de la prueba final (examen escrito) es superior al 40% de la calificación de la asignatura, bastará con no presentarse a dicha prueba final para que la calificación final de la asignatura sea no presentado o no presentada.



RENUNCIA A LA EVALUACIÓN CONTINUA

En todo caso el alumnado tendrá derecho a ser evaluado mediante el sistema de evaluación final, independientemente de que haya participado o no en el sistema de evaluación continua. Para ello, el alumnado deberá presentar por escrito al profesorado responsable de la asignatura la renuncia a la evaluación continua, para lo que dispondrán de un plazo de 9 semanas, a contar desde el comienzo del cuatrimestre, de acuerdo con el calendario académico del centro.



ORIENTACIONES PARA LA EVALUACIÓN FINAL

- Examen escrito 80%

- Prácticas de ordenador e informe 20%



El hecho de no haber realizado las actividades evaluables complementarias al examen escrito en la evaluación continua no exime al alumnado de demostrar la capacidad y conocimientos para realizar esas actividades. Se propondrán unas pruebas que garanticen la evaluación de los conocimientos y computen para la nota final en la misma proporción que en la convocatoria ordinaria con evaluación continua. Las pruebas pueden ser una exposición oral, una demostración ante un ordenador o una descripción escrita de los conocimientos prácticos abordados en las actividades complementarias.



La no presentación al examen escrito supondrá la renuncia automática a la convocatoria.



Durante el desarrollo de las pruebas de evaluación el material permitido será indicado por el equipo docente de la asignatura. Ante cualquier caso de práctica deshonesta o fraudulenta se procederá aplicando lo dispuesto en el protocolo sobre ética académica y prevención de las prácticas deshonestas o fraudulentas en las pruebas de evaluación y en los trabajos académicos en la UPV/EHU.

ORIENTACIONES PARA LA EVALUACIÓN EXTRAORDINARIA:

- Examen escrito 80%

- Prácticas de ordenador e informe 20%



Si la nota de prácticas de ordenador de la convocatoria ordinaria es al menos un 4 (sobre 10) no es necesario volver a evaluarse de prácticas de ordenador.



El hecho de no haber superado las actividades evaluables complementarias al examen escrito no exime al alumnado de demostrar la capacidad y conocimientos para realizar esas actividades, con lo que se propondrán unas pruebas que garanticen la evaluación de dichos conocimientos y computen para la nota final en la misma proporción que en la convocatoria ordinaria con evaluación continua. La prueba pueden ser una exposición oral, una demostración ante un ordenador o una descripción escrita de los conocimientos prácticos abordados en las actividades complementarias.



La no presentación al examen escrito supondrá la renuncia automática a la convocatoria.



Durante el desarrollo de las pruebas de evaluación el material permitido será indicado por el equipo docente de la asignatura. Ante cualquier caso de práctica deshonesta o fraudulenta se procederá aplicando lo dispuesto en el protocolo sobre ética académica y prevención de las prácticas deshonestas o fraudulentas en las pruebas de evaluación y en los trabajos académicos en la UPV/EHU.

Al comienzo de curso se publicará en eGela una guía para el estudiante con la programación docente del curso, especificando el calendario y aula asignada de las clases magistrales (M), Seminarios(S), prácticas de aula (GA) y prácticas de ordenador (GO). Horarios de tutorías, fechas de exámenes, fechas de entrega de las tareas programadas de las prácticas de ordenador y trabajos de seminarios.
Se pondrá a disposición del alumnado en la plataforma virtual eGela, los apuntes de la asignatura y el manual con instrucciones para el manejo del compilador C++, el software de optimización COIN-OR y el optimizador CPLEX. También se publicará la relación de ejercicios y problemas para resolver en las prácticas de aula, casos prácticos para resolver en las prácticas de ordenador y seminarios a realizar durante el curso.

Oinarrizko bibliografia

FREDERICH S. HILLIER Y GERARD J. LIEBERMAN. Introducción a la investigación de operaciones.

Editorial McGraw-Hill. Séptima Edición (2001). Novena edición 2010.

FREDERICH S. HILLIER Y MARK. S. HILLIER. Introduction to Management Science: A modeling and case studies

approach with Spread sheets. Editorial McGraw-Hill (2011).

G. NEMHAUSER, L. WOLSEY. Integer and combinatorial optimization. Editorial Wiley (1999).

Gehiago sakontzeko bibliografia

GÉRARD CORNUÉJOLS. Revival of the Gomory cuts in the 1990s. Annals of Operations Research (2007),149,1,63-66.
Y. POCHET, L.A. WOLSEY. Production planning by mixed integer programming. Springer Series in Operations research
and Financial Engineering (2006).

Aldizkariak

Computers & Operations Research, http://www.sciencedirect.com/science/journal/03050548
TOP, http://www.springer.com/business+%26+management/operations+research/journal/11750
Journal of Global Optimization, http://link.springer.com/journal/10898
European Journal of Operational Research, http://www.journals.elsevier.com/european-journal-of-operational-research
Operations Research Letters, http://www.journals.elsevier.com/operations-research-letters
Operations Research, http://www.jstor.org/action/showPublication?journalCode=operrese
Computational and management science,
http://www.springer.com/business+%26+management/operations+research/journal/10287

Web helbideak

COIN-OR http://www.coin-or.org, código abierto
Visual Studio Community C++ 2017 , software libre https://www.visualstudio.com/products/visual-studio-express-vs
Tutorial de C++ http://www.cplusplus.com/doc/tutorial/
CPLEX http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/, Licencia académica
Lingo http://www.lindo.com/, Versión de prueba (demo)