Investigación Operativa26023
- Centro
- Facultad de Informática
- Titulación
- Grado en Inteligencia Artificial
- Curso académico
- 2024/25
- Curso
- 2
- Nº Créditos
- 6
- Idiomas
- Castellano
- Euskera
- Inglés
- Código
- 26023
DocenciaAlternar navegación
Guía docenteAlternar navegación
Descripción y Contextualización de la AsignaturaAlternar navegación
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. En la asignatura de Heurísticos de Búsqueda de tercero el/la estudiante podrá profundizar en la resolución de problemas de optimización.
Competencias/ Resultados de aprendizaje de la asignaturaAlternar navegación
* 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
Contenidos teórico-prácticosAlternar navegación
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
MetodologíaAlternar navegación
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.
Sistemas de evaluaciónAlternar navegación
- 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
Convocatoria Ordinaria: Orientaciones y RenunciaAlternar navegación
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.
Si se detecta alguna copia en una prueba de evaluación (plagio), ésta se calificará con la puntuación de "suspenso, 0" a cada estudiante implicada o implicado.
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.
Convocatoria Extraordinaria: Orientaciones y RenunciaAlternar navegació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.
Si se detecta alguna copia en una prueba de evaluación (plagio), ésta se calificará con la puntuación de "suspenso, 0" a cada estudiante implicada o implicado.
Materiales de uso obligatorioAlternar navegació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íaAlternar navegación
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)
GruposAlternar navegación
16 Teórico (Castellano - Tarde)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 17:00-18:30 (1) | 14:00-15:30 (2) |
Profesorado
16 P. Laboratorio-1 (Castellano - Tarde)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 15:30-17:00 (1) |
Profesorado
16 P. Laboratorio-2 (Castellano - Tarde)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 14:00-15:30 (1) |
Profesorado
31 Teórico (Euskera - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 12:00-13:30 (1) | 09:00-10:30 (2) |
Profesorado
31 P. Laboratorio-1 (Euskera - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 10:30-12:00 (1) |
Profesorado
31 P. Laboratorio-2 (Euskera - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 09:00-10:30 (1) |
Profesorado
31 P. Laboratorio-3 (Euskera - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 12:00-13:30 (1) |
Profesorado
61 Teórico (Inglés - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 12:00-13:30 (1) | 09:00-10:30 (2) |
Profesorado
61 P. Laboratorio-1 (Inglés - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 10:30-12:00 (1) |
Profesorado
61 P. Laboratorio-2 (Inglés - Mañana)Mostrar/ocultar subpáginas
Semanas | Lunes | Martes | Miércoles | Jueves | Viernes |
---|---|---|---|---|---|
16-30 | 09:00-10:30 (1) |