Esta asignatura se sitúa en el segundo cuatrimestre del segundo curso del grado. Para cuando el/la estudiante llegue a cursarla, habrá adquirido ya el conocimiento matemático básico necesario para afrontar la formalización matemática y resolución de problemas. Dominar la resolución de sistemas de ecuaciones lineales y conocer la teoría de grafos y la combinatoria que se estudian en las asignaturas de Matemática Discreta y Álgebra de primer curso resulta fundamental.



Partiendo de este conocimiento matemático básico, la asignatura es una introducción a la resolución de problemas de optimización. A nivel de contenido, se distinguen dos partes: la programación lineal y la optimización heurística.



En la primera parte se analizan las técnicas clásicas de resolución de problemas de optimización lineal. Para empezar, se trabaja la formalización matemática de problemas, construyendo modelos lineales que los representen. A continuación, se analizan algunas de las técnicas clásicas de programación lineal para su resolución: el algoritmo Simplex, el algoritmo Simplex dual, los algoritmos para el problema de transporte y de asignación y los algoritmos de ramificación y acotación para la resolución de problemas lineales enteros.



En la segunda parte se analizan algunos métodos heurísticos que actualmente están teniendo gran éxito en la resolución de problemas de optimización. Se trabaja en la formalización de los problemas y se analizan algunos algoritmos conocidos para su resolución: los algoritmos constructivos, el algoritmo de búsqueda local, los algoritmos genéticos.



Así, partiendo de una formalización matemática básica, esta asignatura aporta el conocimiento teórico y práctico necesario para poder abordar el planteamiento y la resolución de problemas reales de optimización. En la práctica profesional de la Informática y la Inteligencia Artificial, se hace necesario hallar soluciones informáticas a problemas de optimización que frecuentemente surgen en diferentes ámbitos de aplicación. El/la estudiante que desee seguir profundizando en la resolución de problemas, podrá continuar por la especialidad de Computación o matricularse es asignaturas como Bilaketa Heuristikoak, entre otras.

* Identificar problemas susceptibles de ser analizados con las técnicas de programación lineal y los métodos heurísticos



* Ser capaz de representar dichos problemas mediante la formalización adecuada



* Comprender y saber utilizar las técnicas existentes para resolverlos, tanto desde el punto de vista teórico como utilizando el software específico existente



* Interpretar la solución obtenida para ser capaz de tomar decisiones ante un problema real

1. Algebra lineal. Modelos lineales

1.1 Resolución de sistemas de ecuaciones lineales

1.2 Espacios vectoriales. Soluciones básicas

1.3 Conjuntos convexos

1.4 Modelos lineales

1.5 Solución gráfica



2. Programación lineal

2.1 Método Simplex

2.2 Método de penalización. Método de las dos fases

2.3 Análisis de sensibilidad



3. Dualidad

3.1 Método Simplex dual

3.2 Método de la restricción artificial

3.3 Interpretación económica de la dualidad



4. Programación entera

4.1 Algoritmo de ramificación y acotación

4.2 Algoritmo de ramificación y acotación 0-1



5. El problema de transporte. El problema de asignación

5.1 Algoritmo para el problema de transporte

5.2 Método húngaro



6. Optimización heurística

6.1 Problemas de optimización combinatoria

6.2 Algoritmos constructivos

6.3 Búsqueda local

6.4 Algoritmos genéticos

En esta asignatura se utilizan diferentes metodologías de enseñanza.



* En las clases en aula se explicarán los contenidos conceptuales de la asignatura y los/as estudiantes participarán de forma activa en la puesta en práctica de los conceptos analizados mediante ejercicios. Se fomentará que el alumnado plantee preguntas y dudas ante todo el grupo, con el fin de capacitar al alumnado en la comunicación oral y resolver las cuestiones trabajando en equipo.



* En las sesiones de laboratorio, se pondrán a disposición del alumnado los recursos informáticos y bibliográficos necesarios y se les animará a que trabajen de forma autónoma en la resolución de problemas, con el apoyo del profesorado.

• Sistema de Evaluación Continua
• Sistema de Evaluación Final
• Herramientas y porcentajes de calificación:
  • Los porcentajes y tipos de evaluación se especifican en los apartados posteriores (%): 100

Los sistemas de evaluación que se contemplan son el sistema de evaluación continua y el sistema de

evaluación final. El sistema de evaluación continua es el que se utilizará de forma preferente, según se indica en la normativa actual de la UPV/EHU.



El alumnado que, cumpliendo las condiciones para continuar en el sistema de evaluación continua, decidiese optar por la evaluación final, deberá informar al profesorado responsable de la asignatura en los plazos y forma indicados a continuación: vía eGela, después de conocer la calificación de la prueba escrita.



EVALUACIÓN CONTINUA:

- Prueba escrita (60%)

- Prueba práctica de ordenador (20%)

- Trabajos en grupo (20%)



Para aprobar la asignatura en evaluación continua, se deben aprobar la prueba escrita y la prueba práctica de ordenador, se deben entregar los trabajos grupales y se debe obtener un mínimo de 50/100 puntos en total.



EVALUACIÓN FINAL:

- Prueba escrita (80%)

- Prueba práctica de ordenador (20%)



Para aprobar la asignatura en evaluación final, se deben aprobar la prueba escrita y la prueba práctica de ordenador. Si el/la estudiante no realiza ni la prueba escrita ni la prueba práctica de ordenador, se entenderá que renuncia a la evaluación.

La convocatoria extraordinaria será igual que la evaluación final de la convocatoria ordinaria.

- Prueba escrita (80%)

- Prueba práctica de ordenador (20%)



Para aprobar la asignatura, se deben aprobar la prueba escrita y la prueba práctica de ordenador. Si el/la estudiante no realiza ni la prueba escrita ni la prueba práctica de ordenador, se entenderá que renuncia a la evaluación.

El profesorado publicará el material imprescindible en el aula virtual eGela de la asignatura.

Además, para la parte de programación lineal se utilizará el siguiente material publicado en la plataforma OpenCourseWare (OCW) de la UPV/EHU (https://ocw.ehu.eus/):

Investigación Operativa. Programación Lineal
Fernández González, Victoria
Zelaia Jauregi, Ana
OpenCourseWare, eCampus, UPV/EHU (2011)
https://ocw.ehu.eus/course/view.php?id=19

En los laboratorios se utilizará el lenguaje de programación R.

Bibliografía básica

Investigación Operativa. Optimización

Sixto Ríos Insua

Centro de Estudios Ramón Areces. 1990



Investigación Operativa. Modelos determinísticos y estocásticos

Sixto Ríos Insua, Alfonso Mateos Caballero, Maria Concepción Bielza Lozoya, Antonio Jiménez Martín

Centro de Estudios Ramón Areces. 2004



Programación Lineal y Aplicaciones. Ejercicios resueltos

Sixto Ríos Insua, David Ríos Insúa, Alfonso Mateos, Jacinto Martín

Edición Ra-Ma. 1997



Métodos y modelos de Investigación de Operaciones

Juan Prawda Witenberg

Limusa. 1995



Investigación de Operaciones. Aplicaciones y algoritmos

Wayne L. Winston.

Thomson. 2004



Introducción a la Investigación de Operaciones

Frederick S. Hillier, Gerald J. Lieberman

McGraw-Hill. 2006



Investigación de Operaciones

Hamdy A. Taha

Prentice Hall. 1997



Bilaketa Heuristikoak: Teoria eta Praktika.

Borja Calvo, Josu Ceberio, Usue Mori.

UPV/EHU, 2017.

https://addi.ehu.es/handle/10810/25757?locale-attribute=es

Bibliografía de profundización

Linear Programming and Network Flows
Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali
John Wiley and Sons. 1990

Linear Programming
James E. Calvert, William L. Voxman
Harcourt Brace Jovanovich, Publishers. 1989

Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison
Christian Blum, Andrea Roli
ACM Computing Surveys, 35(3), pp. 268-308, 2003.

Revistas

European Journal of Operational Research
Computers and Operations Research
Combinatorial Optimization and Applications
IEEE Transactions on Evolutionary Computation
Optimization Letters

Direcciones web

http://www.r-project.org/ (R, Official website)
http://www.rstudio.com/ (RStudio, Official website)
http://lpsolve.sourceforge.net/5.5/index.htm (lpSolveAPI)
https://github.com/b0rxa/metaheuR (metaheuR)
http://www.sc.ehu.es/ccwikera/index.html (software para programación lineal)
http://www.lindo.com (software para programación lineal)
https://winqsb.uptodown.com/windows (software para programación lineal)